编译原理实验报告算术表达式递归下降分析程序设计

计算机科学与工程学院

《编译原理》实验报告

专业班级 学生学号 学生姓名 实验项目 实验类别 实验地点 指导教师 实验时间 实验二、算术表达式递归下降分析程序设计 操作性（） 验证性（） 设计性（√） 综合性（ ） 其它 （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 实验目的及要求 成 绩 评 定 表 类 别 上机表现 评 分 标 准 积极出勤、遵守纪律 主动完成实验设计任务 及时递交、填写规范 内容完整、体现收获 分值 30分 得分 合 计 实验报告 70分 说明： 评阅教师： 日 期： 实 验 内 容 计算机科学与工程学院

一、 实验目的 （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 二、 实验内容 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下： EE+T | T TT*F | F F(E) | i 设计说明：首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归函数，函数的名字表示规则左部的非终结符；函数体按规则右部符号串的顺序编写。 三、 设计分析 （1）消去该文法左递归，得到文法： ETE1 E1+TE1|ε TFT1 T1*FT1|ε F(E)| I （2）根据LL（1）文法的判断条件，计算这个文法的每个非终结符的FIRST集和FOLLOW集，经验证，改后的文法已经是LL（1）文法。 （3）最后构造递归下降分析程序，每个函数名是相应的非终结符，函数体则是根据右部符号串的结构编写。 a.当遇到非终结符时，如：+。 则编写语句 if(当读来的输入符号 == +) 读下一个输入符号 b.当遇到非终结符时，例如：T。则编写语句调用T()。 c.当遇到非终结符ε规则时，例如：Tε。 则编写语句 if(当前读来的输入字符不属于FOLLOW(T)) error() d.当某个非终结符的规则有很多个候选式时。 按LL(1)文法的条件能唯一的选择一个候选式进行推导。 （4）递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。因此需要分别构造E,E1,T,T1,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。Scaner函数用于字符串的推进，input函数用于字符串的输入。 《编译原理》实验报告 2

计算机科学与工程学院

四、 程序代码 #include #include #include using namespace std; char a[80]; char sym; int i=0; void E(); void E1(); void T(); void T1(); void F(); void input(); void Scaner(); void Error(); void input() { puts(\"输入需要分析的字符串（以#键结尾）:\"); cin>>a; } void Scaner() { sym = a[i]; i++; } void Error() { cout<<\"Error\"<3

计算机科学与工程学院

printf(\"此字符串是该文法的字符串!\\n\"); else printf(\"Error!\\n\"); i=0; } } void E() { T(); E1(); } void E1() { if (sym == '+') { Scaner(); T(); E1(); } else if ((sym!=')') && (sym!='#')) Error(); } void T() { F(); T1(); } void T1() { if (sym == '*') { Scaner(); F(); T1(); } else if ((sym!='+' && sym!=')') && sym!='#') Error(); } void F() { 《编译原理》实验报告

4

计算机科学与工程学院

} if (sym == '(') { Scaner(); E(); if (sym == ')') Scaner(); else Error(); } else if (sym =='i') Scaner(); else Error(); 五、 测试用例 1. 输入的字符串只含有一个字符时： 输入 i# a# 2．输入的字符串含有 + 时： 输入 ++# 输入 i++# 《编译原理》实验报告

5

计算机科学与工程学院

输入 i+i# 3．输入的字符串含有 * 时： 输入 **# 输入 **i# 输入 *i*# 输入 i*i# i*i*# 3．输入的字符串含有 （） 时： 《编译原理》实验报告

6

计算机科学与工程学院

输入 （）# （i）# 4．输入的字符串含有多种字符： 输入i+i*i# (i+i)*i# (i+i)*(i+i)# (i+*# 《编译原理》实验报告

7

计算机科学与工程学院

实 验 总 结 此次实验，使我掌握自上而下语法分析的要求与特点，也更加了解递归下降语法分析的基本原理和方法并学会相应数据结构的设计方法。递归下降分析法简单、直观，易于构造程序，但它对文法要求较高，必须是LL（1）文法，同时递归调用较多，在编程的时候要特别注意，函数的顺序不能打乱，函数声明要位置明确，不能乱，掌握一定的规律，使程序有条理。在实验中也出现了一些错误和碰到了一些难题，不过在同学的帮助下基本上都解决了。在刚开始的设计分析思路和程序设计中，也遇到过一些问题，一般的情况是对所学的知识还没有完全掌握好，没有透彻理解，对所学知识不能够灵活运用，在课后需要多巩固。在以后的日子里，需要学习的还有很多，不能懈怠。

《编译原理》实验报告 8