编译原理递归算法实验.doc

《编译原理递归算法实验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归下降分析一、实验目的根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。程序开始变得复杂起来，需要利用到程序设计语言的知识和大量编程技巧，递归下降分析法是一种较实用的分析法，通过这个练习可大大提高软件开发能力。通过练习，掌握函数间相互调用的方法。二、实验内容递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数或子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成分。（1）递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（

2、1）文法，（2）递归下降分析法实验设计思想及算法为文法G的每个非终结符号A构造一个递归过程。A的产生式的右边指出这个过程的代码结构：若是终结符号，则向前看符号对照，若匹配则向前进一个符号；否则出错。若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。最后编写程序以实现上述功能。三、实验步骤根据上述算法描述，编写程序以实现相应的功能，该程序由C语言编写，然后在VS运行环境下进行调试，并不断完善，直到能正确的实现递归下降分析功能，判断输入的字符串是否是一个文法的句子。编程识别由下列文法所定义的表达式的递归下降语法分析器。EàE+T

3、TTàT*F

4、FFà(E)

5、

6、i消除左递归之后的文法为：E→TE¢E¢→+TE¢

7、eT→FT¢T¢→*FT¢

8、eF→(E)

9、i输入字符串为：i+i*i。代码如下所示：#includevoidS();voidT();voidT1();voiderror();voidscaner();charsym;intmain(){scaner();S();if(sym=='$')printf("是该文法的句子);elseprintf("不是该文法的句子Á");return0;}voidS(){if(sym=='a'

10、

11、sym=='^')scaner();elseif(sym=='('){scaner();T();if(

12、sym==')')scaner();elseerror();}elseerror();}voidT(){S();T1();}voidT1(){if(sym==','){scaner();S();T1();}elseif(sym!=')')error();}voidscaner(){scanf("%c",&sym);}voiderror(){printf("不是该文法的句子");}