编译原理分知识点习题自上而下语法分析.doc

1.设有文法GS：SABAbB|AaBSb|a试消除该文法的左递归。解：本题考查消除左递归的方法。应用消除文法左递归的算法对文法GS消除左递归的过程如下：（1） 将非终结符排序为：U1=S，U2=A，U3=B（2） 进入算法排序：i=1时，对文法无影响i=2，j=1时：AAa有直接左递归，消去该直接左递归，得AbBAAaA|i=3，j=1时：改写文法，有BABb|aj=2时：改写文法，有BbBABb|a无左递归。（3） 所以文法GS消除左递归后变为：GS：SABAbBAAaA|BbBABb|a2.设有文法GE:EAa|BbAcA|eBBbd试按照递归子程序法为该文法构造语法分析程序。解：本题考查递归子程序的构造方法。首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。因为：（1） 该文法无左递归。（2） 文法的产生式EAa|Bb和AcA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。对产生式EAa|Bb，有FIRST(Aa)FIRST(Bb)=c，eb=对产生式AcA|eB，有FIRST(cA)FIRST(eB)=ce=文法中其他产生式都只有一个非空的右部。综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。下面为该文法的每一个非终结符号构造递归子程序。假设用READAWORD代表读下一个单词。用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。约定输入符号串以“#”作为输入结束符。P(E)的递归子程序为：PROCEDUREP(E);BEGINIFWORDINFIRST(Aa)THENBEGINP(A);READAWORD;IFWORD=aTHENREADAWORDELSEERRORENDELSEIFWORDINFIRST(Bb)THENBEGINP(B);READAWORD;IFWORD=bTHENREADAWORDELSEERRORENDELSEERROREND;P(A)的递归子程序为：PROCEDUREP(A);BEGINIFWORDD=cTHENBEGINREADAWORD;P(A)ENDELSEIFWORD=eTHENBEGINREADWORD;P(B)ENDELSEERROREND;P(B)的递归子程序为：PROCEDUREP(B);BEGINIFWORD=bTHENBEGINREADAWORD;IFWORD=dTHENREADAWORDELSEERRORENDELSEERROREND;主程序中的主要内容为：READAWORD;P(E);IFWORD=”#”THENWRITE(“RIGHT!”)ELSEWRITE(“ERROR!”)3.已知文法GE：GE：EE+T|TTT*F|FFi|(E)请按递归子程序法为其构造语法分析程序。解：本题考查递归子程序的构造方法。本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。因为文法只有左递归，采用扩充的BNF范式消除文法左递归得到：GE：ET+TTF*FFi|(E)然后再应用书中介绍的方法即可求解。假定用“ADVANCE;”表示对读取下一个单词的过程的调用。相应的递归子程序为：PROCEDUREP(E);BEGINP(T);WHILESYM=+DOBEGINADVANCE;P(T)ENDEND;PROCEDUREP(T);BEGINP(F);WHILESYM=*DOBEGINADVANCE;P(F)ENDEND;PROCEDUREP(F);BEGINIFSYM=iTHENADVANCEELSEIFSYM=(THENBEGINADVANCE;P(E);IFSYM=)THENADVANCEELSEERRORENDELSEERROREND;主程序中的主要内容为：ADVANCE;P(E);IFWORD=”#”THENWRITE(“RIGHT!”)ELSEWRITE(“ERROR!”)4文法GM是否是LL(1)文法，说明理由。GM：MTBTBa|BDb|eT|Dd|解：本题考查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)=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） 根据题目要求句子为不包括两个相邻的1的非空串，首先得到一个能够描述所有句子的文法GS：S0S|1A|0|1A0S|0再根据LL(1)文法的要求，将文法改写为GS：S0B|1CA0BBS|CA|（2） 下面证明文法GS是LL(1)文法。对产生式S0B|1C，没有空产生式右部()，所以只要考查终结首符号集是否两两互不相交。有FIRST(0B)FIRST(1C)=01=对产生式A0B，只有唯一的不为空的右部，不用考查。对产生式BS|，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。由于FIRST(S)=0，1FIRST()=FOLLOW(B)= FOLLOW(S) FOLLOW(A)= FOLLOW(S) FOLLOW(C)=FOLLOW(S)=#FOLLOW(B)=#所以有FIRST(S)FIRST()=和FIRST(B)FOLLOW(B)=对产生式CA|，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。由于FIRST(A)=0FIRST()=FOLLOW(C) =FOLLOW(S) =#所以有FIRST(A)FIRST()=和FIRST(C)FOLLOW(C)=综上所述，文法GS的每一条形如UX1|X2|Xn的产生式都满足FIRST(Xi)FIRST(Xj)=(ij)如果Xj时，还满足FIRST(X1)FOLLOW(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为开始符号，且有产生式AASdBSAhCSfFOLLOW(S)=#FIRST(d)FIRST(Ah)FIRST(f)=#，d，a，h，fSaABbcdAASdBSAhFOLLOW(A)=FIRST(Bbcd)FIRST(Sd)FIRST(h)=b，a，d，h，eSaABbcdFOLLOW(B)=FIRST(bcd)=bBeCCCgFOLLOW(C)=FOLLOW(B)FIRST(g)=b，g对每一个非终结符号的产生式右部选项，构造FIRST集合对S：FIRST(aABbcd)=aFIRST()=对A：FIRST(ASd)=a，dFIRST()=对B：FIRST(SAh)=a，d，hFIRST(eC)=eFIRST()=对C：FIRST(Sf)=a，fFIRST(Cg)=a，f，gFIRST()=由于存在产生式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)方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为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#AAaaAA（3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表5.2所示表5.2 对符号串“aaaa”的分析过程步 骤分析栈输入串产生式/动作1#Aaaaa#AaaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#AaaA5#Aaaaa#匹配6#Aaa#匹配7#A#A8#接受（4）构造文法GA的递归子程序如下（假定用“ADVANCE；”表示对读取下一个单词的过程的调用）：PROCEDUREP(A);BEGINIFWORD=aTHENBEGINADVANCE;IFWORD=aTHENBEGINREADAWORD;P(A);ENDELSEERRORENDELSEIFNOT(WORDINFOLLOW(A)THENERROREND;主程序中的主要内容为：ADVANCE;P(A);IFWORD=”#”THENWRITE(“RIGHT!”)ELSEWRITE(“ERROR!”)8.设文法GS：SSbA|aABSbABc将该文法改写成LL(1)文法。求文法的每一个非终结符号的FIRST集合和FOLLOW集合。构造相应的LL(1)分析表。解：本题考查“LL(1)文法”的概念及LL(1)分析表的构造方法，涉及文法符号串的FIRST集，文法非终结符号的FOLLOW集的求法。 将该文法改写成LL(1)文法。 因为SSbA|aA有左递归，将其改写为SaAbA 文法变为GS：SaAbA BSb ABc 文法GS满足LL(1)文法的条件 文法GS中每一个非终结符号的FIRST集合为FIRST(S)=aFIRST(A)=aFIRST(B)=a 文法GS中每一个非终结符号的FOLLOW集合为S为开始符号，且有产生式BSbFOLLOW(S)=#FIRST(b)=#，bSaAbAFOLLOW(A)=FIRST(bA)FOLLOWS=#，bABcFOLLOW(B)=FIRSTc=c 构造相应的LL(1)分析表FIRST(aAbA)=aMS，a=SaAbAFIRST(A)=aMA，a=BBcFIRST(B)=aMB，a=BSb 文法GS的分析表如表5.3所示。表5.3 文法GS的分析表abc#SSaAbAAABcBBSb9.考虑文法G：AAB|BBBC|CCD|DD(A)|i 试问该文法是否是LL(1)文法，为什么？ 写出与该文法等价的LL(1)文法G1。 构造G1的LL(1)分析表。 解：本题考查LL(1)文法的要求，以及LL(1)分析表构造方法，涉及文法符号串的FIRST集合的求法，文法非终结符号的FOLLOW集合求法。该文法不是LL(1)文法。 因为对产生式AAB|B，有FIRST(AB)FIRST(B)=FIRST(B) 不满足LL(1)文法的条件。 构造与该文法等价的LL(1)文法G1。 这一问题实际上是要使该文法满足LL(1)文法的要求。 文法含有左递归，将导致无限循环。将文法消除左递归，得G1ABAA BA|BCBB CB|CD|DD(A)|i 对产生式A BA|，有 FIRST(BA)FOLLOW(A)=#，)= 对产生式B CB|，有 FIRST(CB)FOLLOW(B)=#，)，= 对产生式CD|D，有 FIRST(D)FIRST(D)=(，i= 对产生式D(A)|i，有 FIRST(A)FIRST(i)=(i= 文法中其他产生式都只有一个非空()的右部，所以文法G1已满足LL(1)文法的要求。 因为 对产生式ABA有FIRST(BA)=，(，i 对产生式BCB有FIRST(CB)=，(，i 对产生式A BA|有FIRST(BA)=和FOLLOW(A)=#，) 对产生式B CB|有FIRST(CB)=和FOLLOW(B)=，#，) 对产生式CD|D有FIRST(D)=和FIRST(D)=(，i 对产生式D(A)|i有FIRST(A)=()和FIRST(i)=i 所以文法G1的LL(1)分析表如表5.4所示。表5.4 文法G1的LL(1)分析表（）i#ABABABAABABCBCBCBBCBCDDDD(A)i10.已知文法GA为：AaABe|aBBb|d (1)试给出与GA等价的LL(1)文法GA。 (2)构造GA的预测分析表并给出输入串aade#的分析过程。 解：本题考查“LL(1)文法”的条件，LL(1)分析表的构造方法和LL(1)语法分析过程等内容。 预测分析表就是LL(1)分析表。 (1)文法GA不是LL(1)文法，原因在于： 存在产生式AaABe|a，使得FIRST(aABe)FIRST(a)=a将造成语法分析过程中出现回朔。存在含有左递归的产生式BBb|d，使得语法分析过程中会出现无限循环。要构造与GA等价的LL(1)文法，实质上就是要修改原文法中存在上述两种问题的产生式。对产生式AaABe|a修改为AaCCABe|对产生式BBb|d修改为BdBBbB|因此得到文法GA：AaCCABe|BdBBbB|求出每一个非终结符号的FIRST集和FOLLOW集：FIRST(A)=aFOLLOW(A)=FIRST(Be)#=#，dFIRST(B)=dFOLLOW(B)=FIRST(e)=eFIRST(B)=b，FOLLOW(B)=FOLLOW(B)=eFIRST(C)=a，FOLLOW(C)=FOLLOW(A)=#，d可以看出，对产生式BbB|有FIRST(bB)FOLLOW(B)=be=对产生式CABe|有FIRST(ABe)FOLLOW(C)=a#，d=而文法的其他产生式都只有一个非空的产生式右部，在自上而下的语法分析过程中不会出现回朔。所以文法GA就是所求的与原文法等价的LL(1)文法。 (2)构造GA的预测分析表。 分析表M的构造算法为：对FIRST(x)中