递归下降分析器设计与实现

实验二递归下降分析器设计与实现1、实验目的：(1) 掌握自上而下语法分析的要求与特点。(2) 掌握递归下降语法分析的基本原理和方法。(3) 掌握相应数据结构的设计方法。2、实验内容：编程实现给定算术表达式的递归下降分析器。算术表达式文法如下：EE+T|TTT *F|FF(E)|i3、设计说明：首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归过程， 过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。4、设计分析这个题目属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写 为LL(1 )文法为：ETEE+TE| sTFTT-*FT| sF-(E)|i然后再为每个非终结符设计一个对应的函数，通过各函数之间的递归调用从而 实现递归下降语法分析的功能。具体方法为：(1) 当遇到终结符a时，则编写语句If(当前读到的输入符号=a)读入下一个输入符号(2) 当遇到非终结符A时，则编写语句调用A()。(3) 当遇到As规则时，则编写语句If(当前读到的输入符号不属于Follow(A)error()(4) 当某个非终结符的规则有多个候选式时，按LL(1)文法的条件能唯一地选择一 个候选式进行推导.5、程序代码#includevoid E();void T();void E1();void T1();void F();char s100;int i, SIGN;int main()printf(请输入一个语句，以#号结束语句(直接输入#号推出)n); while( 1 )SIGN = 0; i=0；scanf(%s，& s);if( s0 = #)return 0;E();if(si=#)printf(“正确语句！ n);prin tf(请输入一个语句，以#号结束语句n);return 1;void E()if(SIGN=0)T(); E1();void E1()if(SIGN=0)if(si二二+)+i；T(); El();else if(si!=# & si!=) printf(语句有误！ n); SIGN=1;void T()if(SIGN=0)F(); T1();void T1()if(SIGN=0)if(si =*)+i;F(); T1();else if(si!=# &si!=) &si!=+) printf(语句有误！ n);SIGN=1;void F()if(SIGN=0)if(si=()+i；E();if(si=)+i；else if(si= #)printf(语句有误！ n);SIGN=1;+i；else if(si=i)+i；elseprintf(语句有误！ n);SIGN=1;6、测试用例(1) 只含有一个字符的形式：iaA(2) 含有+ 的形式: i+ii+i+ii+rC：DocuBeiits and Set tings V Ada iiti str at or面l室鲨二:負术表达式递归下降分析程序设请输h需唄别药句子：i州error!二口昱Press an key to co n t in Lie(3) 含有*的形式: i*ii*i*ii*I c：. *C 2 VDocuaentE and SettingEVkdBiiii str at or 桌面实整二:谆术表达式递归下降分靳程序设|n|X请输入需识别的句子:*非 error?Press any key to continued(4) 含有()的形式:(i)()(i)c： *C： VDocuaents and SettingsVAdaini strator面实墓二：算术表达式递归下降分析程序设I请输入需识别的句子汽fail(5) 综合形式： (i+i) *i (i+i) *(i+i) i+i*i i+i * (* i+(i+Iiic：-. *C 2 Docoeiits and SettingsAdBini strator面实墓二-算术表达式递归下降分析程序设-|n|X请输入需识别的句子:*i#5 LI 匚 CC S S请输入需识别的句子请输入需识别的句子:佬 n 厂 厂 尸 吒 电请输入需识别的句子:i-i#error*Press any key to continuecC CADocuBBiitE and. SettingEAdBiiii strator面二:直术表达式递归下降分析程序设.lnlX请输人需识别的句子3jIlerror!ftess any key to continues*C 2 Docoeiits and SettingsAdBini strator面实整二-算术表达式递归下降分析程序设-|请输入需识别的句子:iii# error?Press any key to continue7、系统实施系统实施环境为VC+6.0,在系统的实施过程中存在的问题主要是程序输入错 误，没有大的技术问题，经过调试和修改，系统最终能够运行并实现上述所有功 能。以下列出程序运行时的几个界面：(1)系统运行初始界面：(2)导入文法打开刃选择要导入的文本(3)生成非终结符集合，终结符集合，空串的非终结符集合，非终结符号的 FIRST集合，非终结符号的FOLLOW集合，各产生式的SELECT集合，预测分析表:输出二弋二口于丿于P禾1=1丿砂：K Uj 丄,U JGS:S-MHS-aH-LSoH-K-dMLK-L-eHfM-KM-bLM可以推出空串的非终结符集台为: S, H, K, M 非终结符号的FI盟T集合：FIRST(S)虬 a, d, b, e FIRST (H) , e FIRST(K) d, FIRST (L) e rrr输出SELECT(S-a)二且SELECT(H-LSo) = e SELECT二歐也 SELECT(K-dML)= f d SELECT(K-)二歐 电 SELECT(L-eHf)二巴SELECT (M-K) = d, e, o SELECT(M-bLM) = f b abe0fd#SaMHMHMHMHMHHLSoKdJULLeHfMbLMKKKK输入的文祛是一个LL(1)文祛。 下面是生成的预测分析表：轴句子|保存结果(E) |匚关町8、实验总结通过本次试验实践掌握了自上而下语法分析法的特点。掌握了递 归下降语法分析的基本原理和方法。运用递归下降分析法完成了本试 验的语法分析构造，并且成功的分析出每种正确的句子和错误的句 子。函数的构造是根据文法分析的递归过程，所编写每个函数的功 能，以文法的右部为函数名，对应的左部为相应分析过程。此分析法 简单，直观，易构造分析程序，但是不适于文法过于复杂的，不易检 查出错误。在试验的过程中，遇到了一些问题，都是粗心大意而造 成，并非是对文法分析和编程的熟悉问题，说明了我再以后的试验中 应该更细心的编写程序的每一步，对于本次试验所出现的马虎，应该 牢记，以后不再犯同样的错误。