针对文法:G[E]:E->E+T|T T->TF|F F->(E)|i 用c++编写程序利用LR(0)分析方法对该文法进行语法分析,构建i+ii句型分析过程中符号栈的变化过程并输出分析表的代码
时间: 2024-06-09 20:04:46 浏览: 133
以下是针对该文法的LR(0)语法分析程序代码:
```c++
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// 定义文法符号和产生式
enum Symbol { E, T, F, PLUS, LPAREN, RPAREN, ID, END };
enum Production { P1, P2, P3, P4, P5, P6 };
// 定义符号栈和状态栈
stack<int> symStack;
stack<int> stateStack;
// 定义状态转换表
const int table[10][8] = {
{5, -1, -1, -1, 4, -1, 1, -1},
{-1, 6, 7, -1, -1, -1, -1, 0},
{-1, -1, -1, 2, -1, -1, -1, -1},
{-1, -1, -1, 2, -1, -1, -1, -1},
{5, -1, -1, -1, 4, -1, 8, -1},
{-1, -1, -1, 9, -1, -1, -1, -1},
{5, -1, -1, -1, 4, -1, -1, 10},
{5, -1, -1, -1, 4, -1, -1, 11},
{-1, 6, 7, -1, -1, 12, -1, -1},
{-1, -1, -1, 2, -1, -1, -1, -1}
};
// 定义产生式右部的符号列表
const vector<vector<int>> productions = {
{E, PLUS, T},
{T},
{T, F},
{F},
{LPAREN, E, RPAREN},
{ID}
};
// 获取符号的类型
int getSymbolType(char c) {
switch (c) {
case '+': return PLUS;
case '(': return LPAREN;
case ')': return RPAREN;
case 'i': return ID;
case '$': return END;
default: return -1;
}
}
// 获取产生式的右部
vector<int> getProductionRight(int production) {
return productions[production];
}
// 将符号和状态推入栈中
void pushSymbolAndState(int symbol, int state) {
symStack.push(symbol);
stateStack.push(state);
}
// 分析输入的句子
void analyze(string sentence) {
// 初始化栈和状态
pushSymbolAndState(END, 0);
int pos = 0;
// 逐个读入字符
while (pos < sentence.length()) {
char c = sentence[pos];
int symbol = getSymbolType(c);
// 判断当前字符是否是文法符号
if (symbol >= 0) {
int state = stateStack.top();
int action = table[state][symbol];
// 如果是移进操作
if (action > 0) {
pushSymbolAndState(symbol, action);
pos++;
}
// 如果是规约操作
else if (action < 0) {
int production = -action - 1;
vector<int> right = getProductionRight(production);
// 将产生式右部的符号和新状态推入栈中
for (int i = 0; i < right.size(); i++) {
symStack.pop();
stateStack.pop();
}
int newState = table[stateStack.top()][production + 2];
pushSymbolAndState(getSymbolType('E'), newState);
}
// 如果是错误操作
else {
cout << "Error: Invalid input\n";
break;
}
}
// 如果不是文法符号
else {
cout << "Error: Invalid input\n";
break;
}
}
// 判断是否分析成功
if (symStack.top() == END && stateStack.top() == 2) {
cout << "Success\n";
} else {
cout << "Error: Invalid input\n";
}
}
int main() {
string sentence;
cout << "Enter a sentence: ";
cin >> sentence;
sentence += '$';
analyze(sentence);
return 0;
}
```
下面是分析表:
| | + | ( | ) | i | $ | E | T | F |
|---|---|---|---|---|---|---|---|---|
| 0 | s5| | | s6| | 1 | | 2 |
| 1 | | | | | acc | | | |
| 2 | | s7| | | | | | |
| 3 | | | | | | | | |
| 4 | s5| | | s8| | | | 2 |
| 5 | r3| | r3| r3| r3| | | |
| 6 | s9| | | s6| | | | 2 |
| 7 | s10| | | s6| | | | 2 |
| 8 | r1| | r1| r1| r1| | | |
| 9 | | s7| | | | | 11| |
| 10| | s11| | | | | | 12|
| 11| r4| | r4| r4| r4| | | |
| 12| r2| | r2| r2| r2| | | |
其中,s表示移进,r表示规约,acc表示接受。例如,第一行第一列的s5表示在状态0时,如果读入的是+号,则应该进行移进操作,并转移到状态5。第五行第二列的acc表示在状态1时,如果读入的是$符号,则应该接受该句子。
阅读全文