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

计算机科学与工程学院 PAGE  PAGE 9 《编译原理》实验报告 武 汉 工 程 大 学 计算机科学与工程学院 《编译原理》实验报告 专业班级实验地点学生学号指导教师学生姓名实验时间实验项目实验二、算术表达式递归下降分析程序设计实验类别操作性（） 验证性（） 设计性（√） 综合性（ ） 其它实验目的及要求 （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函数用于字符串的输入。 程序代码 #include stdio.h #include string.h #include iostream 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(输入需要分析的字符串（以#键结尾）:); cina; } void Scaner() { sym = a[i]; i++; } void Error() { coutErrorendl; exit (0); } void main() { while(1) { input(); Scaner(); E(); if (sym == #) 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