1.设有文法G[S]：S—ABA—bB|AaB—Sb|a试消除该文法的左递归。解：本题考查消除左递归的方法。应用消除文法左递归的算法对文法G[S]消除左递归的过程如下：(1)将非终结符排序为：U1=S，U2=A，U3=B(2)进入算法排序：i=1时，对文法无影响i=2,j=1时：A—Aa有直接左递归，消去该直接左递归，得A—bBA'A—aA£|i=3，j=1时：改写文法，有B—ABb|aj=2时：改写文法，有B—bBABb|e无左递归。(3)所以文法G[S]消除左递归后变为：G'[S：]S—ABA—bBA'A'—aA'£|B—bBA'Bb|a2.设有文法G[E]:E—Aa|BbA—cA|eBB—bd试按照递归子程序法为该文法构造语法分析程序。解：本题考查递归子程序的构造方法。首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。因为：(1)该文法无左递归。(2)文法的产生式E—Aa|Bb和A—cA|eB的右部有若干选项，判断这两条产生式右部各候选式的终结首符号集合是否两两互不相交。对产生式E—Aa|Bb，有FIRST(Aa)nFIRST(Bb)={c,e}n{b}=?对产生式A—cA|eB，有FIRST(cA)nFIRST(eB)={c}n{e}=?文法中其他产生式都只有一个非空&的右部。综合(1)、(2)，该文法可以采用自上而下分析方法进行语法分析而不会出现回朔和无限循环。下面为该文法的每一个非终结符号构造递归子程序。假设用READAWORD代表读下一个单词。用P(E)、P(A)、P(B)分别表示非终结符号E、A、B对应的子程序名。约定输入符号串以符。P(E)的递归子程序为：PROCEDUREP(E);BEGINIFWORDINFIRST(Aa)#”作为输入结束THENBEGINP(A);READAWORD;IFWORD'=a'THENREADAWORDELSEERRORENDELSEIFWORDINFIRST(Bb)THENBEGINP(B);READAWORD;IFWORD'=b'THENREADAWORDELSEERRORENDELSEERROREND;P(A)的递归子程序为：PROCEDUREP(A);BEGINIFWORDD'=c'THENBEGINREADAWORD;P(A)ENDELSEIFWORD'=e'THENBEGINREADWORD;P(B)ENDELSEERROREND;P(B)的递归子程序为：PROCEDUREP(B);BEGINIFWORD'=b'THENBEGINREADAWORD;IFWORD'=d'THENREADAWORDELSEERRORENDELSEERROREND;主程序中的主要内容为：READAWORD;P(E);IFWORD”=#”THENWRITE(“RIGHT!”)ELSEWRITE(“ERROR”!)3.已知文法G[E]：G[E]:E—E+T|TT—T*F|FF—i|(E)请按递归子程序法为其构造语法分析程序。解:本题考查递归子程序的构造方法。本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。因为文法只有左递归，采用扩充的BNF范式消除文法左递归得到:G[E]:E—T{+T}T—F{*F}F—i|(E)然后再应用书中介绍的方法即可求解。假定用“ADVANCE;”表示对读取下一个单词的过程的调用。相应的递归子程序为:PROCEDUREP(E);BEGINP(T);WHILESYM='+'DOBEGINADVANCE;P(T)ENDEND;PROCEDUREP(T);BEGINP(F);WHILESYM='*'DOBEGINADVANCE;P(F)ENDEND;PROCEDUREP(F);BEGINIFSYM='i'THENADVANCEELSEIFSYM='('THENBEGINADVANCE;P(E);IFSYM=')'THENADVANCEELSEERRORENDELSEERROREND;主程序中的主要内容为：ADVANCE;P(E);IFWORD”=#”THENWRITE(“RIGHT!”)ELSEWRITE(“ERROR”!)4•文法G[M]是否是LL(1)文法，说明理由。G[M]:M—TBT—Ba|£B—Db|eT|&D—d|£解：本题考查LL(1)方法对文法的要求，涉及到FIRST集、FOLLOW集的求法。首先求出文法的每一个非终结符号的FIRST集、FOLLOW集：FIRST(D)=FIRST(d)nFIRST(&)={d,£}FIRST(B)=FIRST(Db)nFIRST(eT)nFIRST(&)=FIRST(db)nFIRST(b)nFIRST(eT)nFIRST(&)={d,b,e,£}FIRST(T)=FIRST(Ba)nFIRST(&)={d,b,e,a,&}FIRST(M)=FIRST(Tb)={d,b,e,a,&}FOLLOW(M)={#}FOLLOW(B)=FOLLOW(M)U{£}={a#}FOLLOW(T)=FOLLOW(B)\{£}UFOLLOW(M)UFOLLOW(B)={d,b,e，#，a}FOLLOW(D)=FIRST(b)\{£}={b}可以看出，对文法G[M]的产生式T—Ba|£，有FIRST(Ba)nFOLLOW(T)={d，b，e，a}n{d，b，e，#，a}={d，b，e，a}工？仅此一条就会导致在自上而下的语法分析过程中出现回朔。所以文法G[M]不是LL(1)文法。5•构造一个LL(1)文法G,识别语言L:L={CD|3为{0,1}上不包括两个相邻的1的非空串}并证明你的结论。解：本题考查文法的构造方法以及LL(1)文法的要求。首先构造出描述该语言的文法，然后证明该文法是LL(1)文法。1)根据题目要求——句子为不包...