E→T|E+T|E-T T→F|T*F|T/F F→i|(E) 消去上面文法的左递归 , 按消去左递归的文法,使用C++写出对应的递归下降语法分析器。
时间: 2023-09-04 10:12:34 浏览: 158
基于C++设计与实现递归下降语法分析【100012999】
消除左递归后的文法如下:
E → TE'
E' → +TE' | -TE' | ε
T → FT'
T' → *FT' | /FT' | ε
F → i | (E)
对应的递归下降语法分析器如下:
```cpp
#include <iostream>
#include <string>
using namespace std;
string input;
int index;
void parse_E();
void parse_E_prime();
void parse_T();
void parse_T_prime();
void parse_F();
void match(char expected) {
if (input[index] == expected) {
index++;
} else {
throw "Error: Invalid input";
}
}
void parse_E() {
parse_T();
parse_E_prime();
}
void parse_E_prime() {
if (input[index] == '+') {
match('+');
parse_T();
parse_E_prime();
} else if (input[index] == '-') {
match('-');
parse_T();
parse_E_prime();
} else {
// E' → ε
}
}
void parse_T() {
parse_F();
parse_T_prime();
}
void parse_T_prime() {
if (input[index] == '*') {
match('*');
parse_F();
parse_T_prime();
} else if (input[index] == '/') {
match('/');
parse_F();
parse_T_prime();
} else {
// T' → ε
}
}
void parse_F() {
if (input[index] == 'i') {
match('i');
} else if (input[index] == '(') {
match('(');
parse_E();
match(')');
} else {
throw "Error: Invalid input";
}
}
int main() {
// 初始化
input = "i+i*i";
index = 0;
// 开始解析
try {
parse_E();
if (input[index] == '\0') {
cout << "Parsing succeeded" << endl;
} else {
throw "Error: Invalid input";
}
} catch(const char* msg) {
cerr << msg << endl;
}
return 0;
}
```
其中,`input` 是输入的字符串,`index` 表示当前读到了第几个字符。`parse_E`、`parse_E_prime`、`parse_T`、`parse_T_prime` 和 `parse_F` 分别对应文法中的非终结符号,`match` 用于匹配当前读入的字符。最后判断是否解析成功,如果成功则输出 `Parsing succeeded`,否则输出错误信息。
阅读全文