《编译原理分知识点习题 自上而下语法分析》由会员分享，可在线阅读，更多相关《编译原理分知识点习题 自上而下语法分析（11页珍藏版）》请在金锄头文库上搜索。
1、1.设有文法 GS：SABAbB|AaBSb|a试消除该文法的左递归。解：本题考查消除左递归的方法。应用消除文法左递归的算法对文法 GS消除左递归的过程如下：（1） 将非终结符排序为：U 1=S，U 2=A，U 3=B（2） 进入算法排序：i=1 时，对文法无影响i=2，j=1 时： AAa 有直接左递归，消去该直接左递归，得AbBAAaA|i=3，j=1 时：改写文法，有BABb|aj=2 时：改写文法，有BbBABb|a 无左递归。（3） 所以文法 GS消除左递归后变为：GS：SABAbBAA aA|BbBABb|a2.设有文法 GE:EAa|BbAcA|eBBbd试按照递归子程序法为该文
2、法构造语法分析程序。解：本题考查递归子程序的构造方法。首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。因为：（1） 该文法无左递归。（2） 文法的产生式 EAa|Bb 和 AcA|eB 的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。对产生式 EAa|Bb，有FIRST(Aa)FIRST(Bb)=c，eb= 对产生式 AcA|eB ，有FIRST(cA)FIRST(eB)=ce=文法中其他产生式都只有一个非空 的右部。综合（1） 、 （2） ，该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。下面为该文法的每一个非终结符号构
3、造递归子程序。假设用 READAWORD 代表读下一个单词。用 P(E)、P(A)、P(B)分别表示非终结符号 E、A、B 对应的子程序名。约定输入符号串以“#”作为输入结束符。P(E)的递归子程序为：PROCEDURE P(E);BEGINIF WORD IN FIRST(Aa)THENBEGINP(A);READAWORD;IF WORD=aTHEN READAWORDELSE ERRORENDELSE IF WORD IN FIRST(Bb)THENBEGINP(B);READAWORD;IF WORD=bTHEN READAWORDELSE ERRORENDELSE ERROREND;
4、P(A)的递归子程序为：PROCEDURE P(A);BEGINIF WORDD=cTHENBEGINREADAWORD;P(A)ENDELSE IF WORD=eTHENBEGINREADWORD;P(B)ENDELSE ERROREND;P(B)的递归子程序为：PROCEDURE P(B);BEGINIF WORD=bTHENBEGINREADAWORD;IF WORD=dTHEN READAWORDELSE ERRORENDELSE ERROREND;主程序中的主要内容为：READAWORD;P(E);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“
5、ERROR!”)3.已知文法 GE：GE：EE+T|TTT*F|FFi|(E)请按递归子程序法为其构造语法分析程序。解：本题考查递归子程序的构造方法。本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。因为文法只有左递归，采用扩充的 BNF 范式消除文法左递归得到：GE：ET+TTF*FFi|(E)然后再应用书中介绍的方法即可求解。假定用“ADVANCE;”表示对读取下一个单词的过程的调用。相应的递归子程序为：PROCEDURE P(E);BEGINP(T);WHILE SYM=+ DOBEGINADVANCE;P(T)ENDEND;PROCED
6、URE P(T);BEGINP(F);WHILE SYM=* DOBEGINADVANCE;P(F)ENDEND;PROCEDURE P(F);BEGINIF SYM=i THEN ADVANCEELSE IF SYM=( THENBEGINADVANCE;P(E);IF SYM=) THEN ADVANCEELSE ERRORENDELSE ERROREND;主程序中的主要内容为：ADVANCE;P(E);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR!”)4文法 GM是否是 LL(1)文法，说明理由。GM：MTBTBa|BDb|eT| Dd
7、|解：本题考查 LL(1)方法对文法的要求，涉及到 FIRST 集、FOLLOW 集的求法。首先求出文法的每一个非终结符号的 FIRST 集、 FOLLOW 集：FIRST(D)=FIRST(d)FIRST( )=d, FIRST(B)=FIRST(Db)FIRST(eT)FIRST()=FIRST(db)FIRST(b)FIRST(eT)FIRST()=d，b，e，FIRST(T)=FIRST(Ba)FIRST()=d，b，e，a ，FIRST(M)=FIRST(Tb)= d，b，e，a，FOLLOW(M)=#FOLLOW(B)=FOLLOW(M)FIRST(a)=a，#FOLLOW(T)=
8、FOLLOW(B)FOLLOW(M) FOLLOW(B)=d，b，e，#，aFOLLOW(D)=FIRST(b)=b可以看出，对文法 GM的产生式 TBa|，有FIRST(Ba)FOLLOW(T)=d ，b，e，ad，b，e，#，a=d，b，e，a仅此一条就会导致在自上而下的语法分析过程中出现回朔。所以文法 GM不是 LL(1)文法。5构造一个 LL(1)文法 G，识别语言 L：L=| 为 0，1上不包括两个相邻的 1 的非空串并证明你的结论。解：本题考查文法的构造方法以及 LL(1)文法的要求。首先构造出描述该语言的文法，然后证明该文法是 LL(1)文法。（1） 根据题目要求句子为不包括两个
9、相邻的 1 的非空串，首先得到一个能够描述所有句子的文法GS：S0S|1A|0|1A0S|0再根据 LL(1)文法的要求，将文法改写为GS：S0B|1CA0BBS| CA|（2） 下面证明文法 GS是 LL(1)文法。对产生式 S 0B|1C，没有空产生式右部()，所以只要考查终结首符号集是否两两互不相交。有FIRST(0B)FIRST(1C)=01=对产生式 A0B，只有唯一的不为空 的右部，不用考查。对产生式 BS|，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。由于FIRST(S)=0，1 FIRST()= FOLLOW(B)= FOLLOW(S) FOLLOW(A
10、)= FOLLOW(S) FOLLOW(C)=FOLLOW(S)=#FOLLOW(B)=#所以有FIRST(S)FIRST()= 和 FIRST(B)FOLLOW(B)=对产生式 CA|，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。由于FIRST(A)=0 FIRST()= FOLLOW(C) =FOLLOW(S) =#所以有FIRST(A)FIRST()= 和 FIRST(C)FOLLOW(C)=综上所述，文法 GS的每一条形如 UX 1|X2|Xn 的产生式都满足FIRST(Xi)FIRST( Xj)= (ij)如果 Xj* 时，还满足FIRST(X1)FOLLOW
11、(U)=所以，文法 GS是 LL(1)文法。6有文法 GS：SaABbcd|AASd| BSAh|eC| CSf|Cg|DaBD|求每一个非终结符号的 FOLLOW 集合。对每一个非终结符号的产生式选择，构造 FIRST 集合。该文法是 LL(1)文法吗？解：本题考查 LL(1)文法的要求，涉及文法符号串 FIRST 集，文法非终结符号的 FOLLOW 集的求法。首先将文法压缩，得到SaABbcd|AASd| BSAh|eC| CSf|Cg|求每一个非终结符号的 FOLLOW 集合：S 为开始符号，且有产生式 AASd BSAh CSfFOLLOW(S)=#FIRST(d)FIRST(Ah)F
12、IRST(f)=#，d，a，h，fSaABbcd AASd BSAhFOLLOW(A)=FIRST(Bbcd)FIRST(Sd)FIRST(h)=b，a ，d，h，eSaABbcdFOLLOW(B)=FIRST(bcd)=bBeC CCgFOLLOW(C)=FOLLOW(B)FIRST(g)=b ， g对每一个非终结符号的产生式右部选项，构造 FIRST 集合对 S：FIRST(aABbcd)=a FIRST()=对 A：FIRST(ASd)=a，d FIRST()=对 B：FIRST(SAh)=a，d，h FIRST(eC)=e FIRST()=对 C：FIRST(Sf)=a，f FIRST
13、(Cg)=a，f，g FIRST()=由于存在产生式 CSf|Cg|FIRST(Sf)FIRST(Cg)=a，fa，f，g所以该文法不是 LL(1)文法。7已知文法GA：AaAa|（1）该文法是 LL(1)文法吗？为什么？（2）若采用 LL(1)方法进行语法分析，如何得到该文法的 LL(1)分析表？（3）若输入符号串“aaaa” ，请给出语法分析过程。（4）请给出该文法的递归下降分析子程序。解：（1）因为产生式 AaAa| 有空产生式右部，而FOLLOW(A)=#FIRST(a)=a， #造成 FIRST(A)FOLLOW(A)=a，a，#所以该文法不是 LL(1)文法。（2）若采用 LL(1
14、)方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为 0）个 a，所以得到文法GA：AaaA|此时对产生式 AaaA|，有 FOLLOW(A)=#FOLLOW(A)=# ，因而FIRST(A)FOLLOW(A)=a，#= 所以文法 GA是 LL(1)文法，按 LL(1)分析表构造算法构造该文法的LL(1)分析表如表 5.1 所示。表 5.1 文法 GA的 LL(1)分析表A #A AaaA A（3）若采用 LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表 5.2所示表 5.2 对符号串“aaaa”的分析过程步 骤 分析栈 输入串 产生式/动作1 #A aaaa# AaaA
15、2 #Aaa aaaa# 匹配3 #Aa aaa# 匹配4 #A aa# AaaA5 #Aaa aa# 匹配6 #Aa a# 匹配7 #A # A8 # # 接受（4）构造文法 GA的递归子程序如下（假定用“ADVANCE；”表示对读取下一个单词的过 程的调用）：PROCEDURE P(A);BEGINIF WORD=aTHEN BEGIN ADVANCE;IF WORD=aTHEN BEGIN READAWORD;P(A);ENDELSE ERRORENDELSE IF NOT(WORD IN FOLLOW(A)THEN ERROREND;主程序中的主要内容为：ADVANCE;P(A);IF WORD=”#”THEN WRITE(“RIGHT!”)ELSE WRITE(“ERROR
