递归下降程序.doc

《递归下降程序.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、递归下降分析程序实验报告1.实验内容编程实现给定算术表达式的递归下降分析器。算术表达式文法如下：EàE+T

2、TTàT*F

3、FFà(E)

4、i2.实验分析(1)对所给表达式进行分析，如果是左递归则对算术表达式进行改写消除其左递归。改写的算术表达式如下：E→TE’E’→+TE’

5、εT→FT’T’→*FT’

6、εF→(E)

7、i(2)写出上面表达式的FIRST集和FOLLOW集，然后对有多个规则的FIRST集求并集，看是否等于空集；对规则右部出现空串的FIRST集与FOLLOW集求并集，看是否等于空集。对E’：FIRST(+TE′)

8、∩FOLLOW(E′)={+，ε}∩{#,)}=Φ对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（）④当某个非终结符

9、的规则有多个候选式时，按LL（1）文法的条件能惟一地选择一个侯选式进行推导。3.源程序代码#includeusingnamespacestd；#include#definen100charch[n];intk=0;voidscaner();voidE();voidE1();voidT();voidT1();voidF();voidError();voidscaner(){k++;}voidE(){T();E1();}voidE1(){if(ch[k]=='+'){scaner();T(

10、);E1();}elseif(ch[k]!=')'&&ch[k]!='#')Error();}voidT(){F();T1();}voidT1(){if(ch[k]=='*'){scaner();F();T1();}elseif(ch[k]=='+'&&ch[k]!=')'&&ch[k]=='#')Error();}voidF(){if(ch[k]=='('){scaner();E();if(ch[k]==')')scaner();elseError();}elseif(ch[k]=='i'){scaner();}els

11、eError();}voidError(){cout<<"语法错误!!!"<>ch;E();if(ch[k]=='#'){cout<<"分析成功!"<

12、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：输入ii时

13、失败图12输入ii时匹配失败13．图13：输入（）时失败图13输入（）匹配失败5.实验总结本次实验主要是根据一个算术表达式文法构造一个识别该文法句子的递归下降分析程序。它的主要功能是当输入一个算术表达式时，判断该表达式是否能从文法开始符号出发推导出来。若能，则说明语法分析成功，否则失败。实验主要使用了C++和VisualStudio2005，定义了几个函数然后调用函数，程序比较简单。本次实验的最终运行结果与预期结果是完全一致的。同时在程序由于不能把全部的错误与正确的用例都包含进去，所以不能验证程序的正确性。在实验开始写程

14、序前要做好充分的准备。例如判断文法是否含有文法左递归、是不是LL（1）文法，并想好测试用例，用例的选择非常重要，因为若某一方面没有考虑到就会导致程序错误。我在写程序时并未考虑用例“i)#”，因此运行出错，最后经修改得到正确的结果。当然程序还不是很完善，例如程序只能分析一个算术表达式就运行完了，再想分析其它表达式就必须