实验三 递归下降法实现的语法分析器

实验3 递归下降法的语法分析器

一、实验目的

学习语法分析器的构造原理，掌握递归下降法的编程方法。

二、实验内容

用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。（注意，需要改写文法，消除左递归等）

program

→ block

block → { stmts } stmts → stmt stmts | ?

stmt

→ id = expr ;

if ( bool ) stmt if ( bool) stmt else stmt while (bool) stmt do stmt while (bool ) ; break ; block

|

| | | | |

bool → expr < expr

| expr <= expr | expr > expr | expr >= expr | expr

expr → expr + term

| expr - term | term

term → term * factor

| term / factor | factor

factor → ( expr ) | id | num

三、实验要求

１．个人完成，提交实验报告。

２．实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。

例如，程序片断

{

i = 2;

while (i <=100) { sum = sum + i; i = i + 2; } }

对应的推导过程为：

program

? block ? { stmts } ? { stmt stmts }

? { id = expr ; stmts } ? { id = num; stmts } ? { id = num; stmt stmts }

? { id = num; while (bool) stmt stmts }

? { id = num; while (expr<= expr) stmt stmts } ? { id = num; while (id <= expr) stmt stmts } ? { id = num; while (id <= num) stmt stmts } ? { id = num; while (id <= num) block stmts } ? { id = num; while (id <= num) { stmts }stmts } ? ．．．．．．．

四、实验步骤

1、构造词法分析器

这个部分主要是在第二个实验的基础上做一定的修改。首先定义一个头文件“lex.yy.h”，内容为各个终结符的数值代号。然后使用实验二中的创建的“*.l”文件，把其中对终结符的处理由print语句改为return语句，return其相应的数值代号。使用lex生成“lex.yy.c” 2、构造语法分析器

首先对文法进行修改去除左递归、提取左因子，以及对“悬空else”、“运算优先级”

所造成的二义性进行消除。

之后根据每个非终结符创建一个函数，实现各个函数的功能。这个可以模仿实验一。不过与实验一不同的是，这里采用ylex()读入下一个终结符。 3、测试设计

采用文件的方式进行测试。在main函数里输入文件名，将文件读入缓冲区。

五、实验结果

六、心得体会

刚开始觉得这个实验比较难，无从下手。不知道如何调用yylex()，以及如何修改.l文件。后来参考了叶柯同学的代码，发现其实也不是很难。本次实验除了知识上的收获外，更大的收获是懂得如何去做一个自己以前没做过的事。可以和同学讨论或者上网查询。当然，网上的解法五花八门，和同学讨论效率更好！最后还得感谢叶柯同学，不然我应该做不出来了。

本文来源：https://www.bwwdw.com/article/ewsx.html