对文法[E]:E→TG G→+TG|-TG|ε T→FS S→*FS|/FS|ε F→(E)|i 编写c++程序实现对输入串的语法分析。 1.递归下降分析法的功能 递归下降分析方法是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2.递归下降分析法的前提 改造文法:消除二义性,消除左递归,提取公共左因子,判断是否 LL(1)文法。
时间: 2024-02-01 21:13:12 浏览: 114
实验二 递归子程序方法
好的,下面是基于递归下降分析法的 C++ 代码实现:
```c++
#include <iostream>
#include <string>
using namespace std;
// 定义文法符号的枚举类型
enum Symbol {
PLUS, // +
MINUS, // -
TIMES, // *
DIVIDE, // /
LPAREN, // (
RPAREN, // )
ID, // 标识符
END // 输入串结束标记
};
// 全局变量,指向输入串的当前位置
int pos = 0;
// 从输入串中获取下一个字符
char getNextChar(string input) {
if (pos < input.length()) {
return input[pos++];
} else {
return '\0';
}
}
// 预处理输入串,去掉空格等无用字符
string preprocessInput(string input) {
string processedInput = "";
for (int i = 0; i < input.length(); i++) {
if (input[i] == ' ' || input[i] == '\t' || input[i] == '\n') {
continue;
} else {
processedInput += input[i];
}
}
return processedInput;
}
// 判断是否为字母
bool isLetter(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
// 判断是否为数字
bool isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
// 将字符串转换为标识符或关键字
Symbol getSymbol(string str) {
if (str == "+") {
return PLUS;
} else if (str == "-") {
return MINUS;
} else if (str == "*") {
return TIMES;
} else if (str == "/") {
return DIVIDE;
} else if (str == "(") {
return LPAREN;
} else if (str == ")") {
return RPAREN;
} else {
return ID;
}
}
// E -> TG
bool parseE(string input) {
return parseT(input) && parseG(input);
}
// G -> +TG | -TG | ε
bool parseG(string input) {
int oldPos = pos;
string str = "";
str += getNextChar(input);
str += getNextChar(input);
if (str == "+T") {
return parseT(input) && parseG(input);
} else if (str == "-T") {
return parseT(input) && parseG(input);
} else {
pos = oldPos;
return true; // ε
}
}
// T -> FS
bool parseT(string input) {
return parseF(input) && parseS(input);
}
// S -> *FS | /FS | ε
bool parseS(string input) {
int oldPos = pos;
char ch = getNextChar(input);
if (ch == '*') {
return parseF(input) && parseS(input);
} else if (ch == '/') {
return parseF(input) && parseS(input);
} else {
pos = oldPos;
return true; // ε
}
}
// F -> (E) | i
bool parseF(string input) {
int oldPos = pos;
char ch = getNextChar(input);
if (ch == '(') {
bool result = parseE(input);
if (getNextChar(input) == ')') {
return result;
} else {
// 括号不匹配,语法错误
return false;
}
} else if (isLetter(ch)) {
// 读入标识符或关键字
string str = "";
while (isLetter(ch) || isDigit(ch)) {
str += ch;
ch = getNextChar(input);
}
pos--; // 回退一个字符
Symbol symbol = getSymbol(str);
return symbol == ID;
} else {
// 非法字符,语法错误
return false;
}
}
int main() {
string input;
cout << "请输入待分析的字符串:";
getline(cin, input);
input = preprocessInput(input);
input += '$'; // 添加输入串结束标记
bool result = parseE(input);
if (result && input[pos] == '$') {
cout << "输入串符合语法规则!" << endl;
} else {
cout << "输入串不符合语法规则!" << endl;
}
return 0;
}
```
由于输入串可能包含空格等无用字符,我们需要先进行预处理,去掉这些无用字符。在 `parseF` 函数中,我们需要读入标识符或关键字,因此需要定义一个 `getSymbol` 函数来判断字符串是标识符还是关键字。在 `parseG` 和 `parseS` 函数中,我们需要先读入两个字符来判断是否为 `+T` 或 `-T`,以及 `*F` 或 `/F`,因此需要先保存当前位置,读入两个字符后再判断。在 `parseF` 函数中,我们需要读入多个字符来判断标识符或关键字,因此需要使用一个循环来读取。最后,在判断输入串是否符合语法规则时,我们需要判断输入串是否已经到达末尾,并且当前栈顶符号是否为文法的开始符号。
阅读全文