已知文法G[E]: E→E+E| E-E|E*E |E/E| (E) | i 设计LR分析表,使用C++编写语法分析器。
时间: 2023-09-09 18:08:22 浏览: 314
基于C++设计与实现LR语法分析器【100012416】
5星 · 资源好评率100%
好的,这是一个关于语法分析的问题,我会尽力回答。首先,根据文法G[E],我们可以画出它的语法分析树,如下所示:
```
E
/ / | \ \
E + E * E
/|\ /|\
i - E i / i
/ \ |
i i i
```
接下来,我们可以使用LR分析算法来构建LR分析表。具体步骤如下:
1. 构建LR(0)自动机
```
+ - * / ( ) i E $
0 S2 S3 S4 S5 S1 S6 S7
1 R3 R3 R3 R3
2 S2 S3 S4 S5 S1 S6 S8
3 S2 S3 S4 S5 S1 S6 S9
4 S2 S3 S4 S5 S1 S6 S10
5 S2 S3 S4 S5 S1 S6 S11
6 S2 S3 S4 S5 S1 S6 S12
7 S2 S3 S4 S5 S1 S6 S13
8 S2 S3 S4 S5 S1 S6 S14
9 R1 R1 S4 R1 R1 R1
10 R2 R2 R2 S7 R2 R2
11 R3 R3 R3 R3 R3 R3
12 R4 R4 R4 R4 R4 R4
13 R5 R5 R5 R5 R5 R5
14 R6 R6 R6 R6 R6 R6
```
其中,S表示shift操作,R表示reduce操作,数字表示下一个状态的编号,空表示无效操作。例如,在状态0遇到+,应该将它shift到状态2。
2. 构建LR分析表
```
+ - * / ( ) i E $
0 S2 S3 S4 S5 S1 S6 S7
1 R3 R3 R3 R3
2 S2 S3 S4 S5 S1 S6 S8
3 S2 S3 S4 S5 S1 S6 S9
4 S2 S3 S4 S5 S1 S6 S10
5 S2 S3 S4 S5 S1 S6 S11
6 S2 S3 S4 S5 S1 S6 S12
7 S2 S3 S4 S5 S1 S6 S13
8 S2 S3 S4 S5 S1 S6 S14
9 R1 R1 S4 R1 R1 R1
10 R2 R2 R2 S7 R2 R2
11 R3 R3 R3 R3 R3 R3
12 R4 R4 R4 R4 R4 R4
13 R5 R5 R5 R5 R5 R5
14 R6 R6 R6 R6 R6 R6
```
其中,每个状态对应一行,每个终结符对应一列,每个格子存储一个操作。例如,表格中第2行第1列的S2表示:在状态1遇到+,应该将它shift到状态2。
3. 编写语法分析器
最后,我们可以使用C++来实现LR语法分析器。具体实现方式有很多,这里提供一种基于栈的实现方法:
```
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
// LR分析表
const unordered_map<string, unordered_map<string, string>> lr_table = {
{"0", {{"+", "S2"}, {"-", "S3"}, {"(", "S1"}, {"i", "S6"}}},
{"1", {{"$", "accept"}}},
{"2", {{"+", "S2"}, {"-", "S3"}, {"*", "S4"}, {"/", "S5"}, {")", "S7"}, {"$", "R3"}}},
{"3", {{"+", "S2"}, {"-", "S3"}, {"*", "S4"}, {"/", "S5"}, {")", "S8"}, {"$", "R3"}}},
{"4", {{"+", "R1"}, {"-", "R1"}, {"*", "S4"}, {"/", "S5"}, {")", "R1"}, {"$", "R1"}}},
{"5", {{"+", "R2"}, {"-", "R2"}, {"*", "R2"}, {"/", "R2"}, {")", "R2"}, {"$", "R2"}}},
{"6", {{"+", "R6"}, {"-", "R6"}, {"*", "R6"}, {"/", "R6"}, {")", "R6"}, {"$", "R6"}}},
{"7", {{"+", "R4"}, {"-", "R4"}, {"*", "R4"}, {"/", "R4"}, {")", "R4"}, {"$", "R4"}}},
{"8", {{"+", "R5"}, {"-", "R5"}, {"*", "R5"}, {"/", "R5"}, {")", "R5"}, {"$", "R5"}}},
};
// LR分析器
bool lr_parser(const string& input) {
stack<string> state_stack;
stack<string> symbol_stack;
state_stack.push("0");
symbol_stack.push("$");
size_t pos = 0;
while (!state_stack.empty()) {
string state = state_stack.top();
string symbol = input.substr(pos, 1);
if (lr_table.count(state) == 0 || lr_table.at(state).count(symbol) == 0) {
cout << "Error: invalid input at position " << pos << endl;
return false;
}
string action = lr_table.at(state).at(symbol);
if (action == "accept") {
cout << "Accept" << endl;
return true;
}
if (action[0] == 'S') {
state_stack.push(action.substr(1));
symbol_stack.push(symbol);
pos++;
} else if (action[0] == 'R') {
int rule = stoi(action.substr(1));
int len = (rule == 6) ? 1 : 3;
for (int i = 0; i < len; i++) {
state_stack.pop();
symbol_stack.pop();
}
string new_state = state_stack.top();
string new_symbol = "E";
if (lr_table.count(new_state) == 0 || lr_table.at(new_state).count(new_symbol) == 0) {
cout << "Error: invalid grammar" << endl;
return false;
}
state_stack.push(lr_table.at(new_state).at(new_symbol));
symbol_stack.push(new_symbol);
} else {
cout << "Error: invalid action " << action << endl;
return false;
}
}
cout << "Error: invalid input" << endl;
return false;
}
// 测试
int main() {
string input;
cout << "Input an expression: ";
getline(cin, input);
input += '$';
lr_parser(input);
return 0;
}
```
这个分析器可以接收一个表达式作为输入,并判断它是否符合文法G[E]的规则。你可以将它复制到本地环境中运行,并根据需要进行修改和优化。
阅读全文