用c++实现对文法[E]:E→TG G→+TG|-TG|ε T→FS S→*FS|/FS|ε F→(E)|i 编写程序实现对输入串的语法分析。 1.递归下降分析法的功能 递归下降分析方法是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2.递归下降分析法的前提 改造文法:消除二义性,消除左递归,提取公共左因子,判断是否 LL(1)文法。
时间: 2024-02-01 11:13:09 浏览: 126
基于C++设计与实现递归下降语法分析【100012999】
递归下降分析法是一种自上而下的语法分析方法,它的核心思想是从文法的开始符号开始,利用函数之间的递归调用模拟语法树自上而下的构造过程,直到构造出整个语法树或者发现语法错误为止。对于该文法,我们需要先进行改造,消除二义性和左递归,提取公共左因子,使其成为LL(1)文法,然后才能进行递归下降分析。
改造后的文法如下:
```
E -> TG
G -> +TG | -TG | ε
T -> FS
S -> *FS | /FS | ε
F -> (E) | i
```
其中,E、T、F为非终结符,+、-、*、/、(、)、i为终结符。
对于该文法,我们需要先构建一个预测分析表,然后再编写程序实现对输入串的语法分析。
预测分析表如下:
| | + | - | * | / | ( | ) | i | $ |
|---|---|---|---|---|---|---|---|---|
| E | | | | | E -> TG | | E -> TG | |
| G | +TG | -TG | | | | ε | ε | ε |
| T | | | | | T -> FS | | T -> FS | |
| S | | | *FS | /FS | | | | ε |
| F | | | | | (E) | | F -> i | |
其中,每个非终结符对应一行,每个终结符对应一列,表格中的每个元素表示对应的产生式。
根据预测分析表,我们可以编写程序实现递归下降分析。具体实现步骤如下:
1. 编写一个函数match(char ch),用于匹配输入串中的字符和预测分析表中的终结符,如果匹配成功,则返回true,并读入下一个字符;否则返回false,表示语法错误。
2. 编写一个函数E(),用于分析E的产生式。根据预测分析表,当输入字符为(T)或i时,使用产生式E -> TG;否则出错。
3. 编写一个函数G(),用于分析G的产生式。根据预测分析表,当输入字符为+、-时,使用相应的产生式;当输入字符为),$时,使用G -> ε;否则出错。
4. 编写一个函数T(),用于分析T的产生式。根据预测分析表,当输入字符为(i)或i时,使用产生式T -> FS;否则出错。
5. 编写一个函数S(),用于分析S的产生式。根据预测分析表,当输入字符为*、/时,使用相应的产生式;当输入字符为+、-、)、$时,使用S -> ε;否则出错。
6. 编写一个函数F(),用于分析F的产生式。根据预测分析表,当输入字符为(i)时,使用产生式F -> (E);当输入字符为i时,使用产生式F -> i;否则出错。
7. 编写主函数,读入输入串,调用E()函数进行递归下降分析,如果分析成功,则输出“分析成功”,否则输出“分析失败”。
具体代码如下:
阅读全文