2024年5月25日发(作者：)

实验三 递归下降法判断算术表达式的正确性

学时数：2-4

一、实验目的和要求

1、 用递归下降技术实现语法分析器；

2、 理解自顶向下语法分析方法；

3、 熟练掌握预测分析程序的构造方法。

二、实验内容

算术表达式的文法是G[E]：

E→E+T| T

T→T*F| F

F→(E)| i

用递归下降分析法按文法G[E]对算术表达式（包括+、*、（）的算术表达式）进行

语法分析，判断该表达式是否正确。

三、实验步骤

1、准备：阅读课本有关章节，将上述算术表达式的文法改造成LL(1)文法（即消除左递

归和提取左公因子）；设计出预测分析表；按P87例4.12编写程序。

2、 上机调试，发现错误，分析错误，再修改完善。

四、测试要求

1、 为降低难度，表达式中不含变量（只含单个无符号整数或i）；

2、 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；

3、 测试用的表达式建议事先放在文本文件中，一行存放一个表达式，以分号结束。而

语法分析程序的输出结果写在另一个文本文件中；

4、 选作：对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果。

5、程序输入/输出示例：

如参考C语言的运算符。输入如下表达式（以分号为结束）和输出结果：

（a）1; 或 i;

输出：正确

（b）1+2; 或 i+i;

输出：正确

（c）(1+2)*3+4-(5+6*7); 或 (i+i)*i+i-(i+i*i);

输出：正确

（d）((1+2)*3+4 或 ((i+i)*i+i;

输出：错误，缺少右括号

（e）1+2+3+(*4/5) 或 i+i+i+(*4/5);

输出：错误

五、实验报告要求

1、写出修改后LL(1)文法

2、通过对核心代码做注释或通过程序流程图的方式说明递归下降分析程序的实现思想。

3、写出调试程序出现的问题及解决的方法。

4、给出测试的结果。

六、思考（选作）

文法G[E]所构造算术表达式只包含+和*。请修改文法和程序，使得该语法程序可判断

包含减号和除号的算术表达式的正确性。

[实验指导]

将文法G[E]改造为LL(1)文法如下：

G’[E]：

E → TE’

E’ → +TE’| ε

T → FT’

T’→ *FT’|ε

F → (E)| i

示例程序test.c，运行时首先输入文件名，该文件中存放要进行分析的算术表达式；

然后输入存放结果的文件名，可任意取名，但类型为.txt。

[补充说明]

预测分析法分析程序可以从网上下载，但要求：

（1）理解该程序，在实验报告中说明该程序所使用的文法及修改后的文法；

（2）实验报告要求同上