递归下降程序

1、递归下降分析程序实验报告1.实验内容编程实现给定算术表达式的递归下降分析器。算术表达式文法如下：EàE+T | T TàT*F | F Fà(E) | i 2.实验分析(1 ) 对所给表达式进行分析，如果是左递归则对算术表达式进行改写消除其左递归。改写的算术表达式如下：ETE E+TE| TFT T*FT | F(E) | i( 2) 写出上面表达式的FIRST集和FOLLOW集，然后对有多个规则的FIRST集求并集，看是否等于空集；对规则右部出现空串的FIRST集与FOLLOW集求并集，看是否等于空集。 对E：FIRST(+TE) FOLLOW(E)=+， #,

2、 )=对T：FIRST(*FT) FOLLOW(T)=* ， +,#, )=对F： FIRST(i) FIRST( (E) )=i ( =故由上面可知此改写后的文法是LL（1）文法。（3）对上述LL（1）文法编程。编程规则如下：当遇到终结符a时，则编写语句If（当前读来的输入符号=a）读下一个输入符号当前遇到非终结符A时，则编写语句调用A（）。当前遇到A规则时，则编写语句If（当前读来的输入符号不属于FOLLOW（A） error（）当某个非终结符的规则有多个候选式时，按LL（1）文法的条件能惟一地选择一个侯选式进行推导。3.源程序代码#include<iostream>using

3、 namespace std； #include<string> #define n 100 char chn; int k=0; void scaner(); void E(); void E1(); void T(); void T1(); void F();void Error();void scaner()k+;void E()T();E1();void E1()if (chk='+') scaner();T();E1(); else if(chk!=')'&&chk!='#') Error();void T(

4、)F();T1();void T1() if(chk='*') scaner();F();T1();else if(chk='+'&&chk!=')'&&chk='#')Error();void F()if(chk='(') scaner(); E(); if(chk=')') scaner();else Error();else if(chk='i')scaner();else Error();void Error() cout<<&qu

5、ot;语法错误 !"<<endl;cout<<"分析失败"<<endl; exit（0）； void main() k=0; cout<<"请输入表达式:"cin>>ch; E(); if (chk='#')cout<<"分析成功!"<<endl; elsecout<<"分析失败"<<endl;4.测试用例1图1：输入i时成功图1 输入i匹配成功2图2：输入i+i*i时成功图2 输入

6、i+i*i匹配成功3图3：输入（i）时成功图 3 输入（i）匹配成功4图4：输入（i+（i*i）时成功图 4 输入（i+（i*I）匹配成功5图5：输入i+i时成功图 5 输入i+i匹配成功6图6：输入i*i时成功图6 输入i*i匹配成功7图7：输入（i*i）时成功图 7 输入（i*i）时匹配成功8图8：输入（i+i）时成功图8 输入（i+i）时匹配成功9图9：输入i+i+i+i+i+i时成功图9 输入i+i+i+i+i+i时匹配成功10图10：输入i*i*i*i*i*i*i*i时成功图 10 输入i*i*i*i*i*i*i时匹配成功11图11：输入+i时失败图11 输入+i时匹配失败12图12

7、：输入ii时失败图12 输入ii时匹配失败13图13：输入（）时失败图 13 输入（）匹配失败5.实验总结本次实验主要是根据一个算术表达式文法构造一个识别该文法句子的递归下降分析程序。它的主要功能是当输入一个算术表达式时，判断该表达式是否能从文法开始符号出发推导出来。若能，则说明语法分析成功，否则失败。实验主要使用了C+和Visual Studio 2005，定义了几个函数然后调用函数，程序比较简单。本次实验的最终运行结果与预期结果是完全一致的。同时在程序由于不能把全部的错误与正确的用例都包含进去，所以不能验证程序的正确性。在实验开始写程序前要做好充分的准备。例如判断文法是否含有文法左递归、是不是LL（1）文法，并想好测试用例，用例的选择非常重要，因为若某一方面没有考虑到就会导致程序错误。我在写程序时并未