S→AB A→bB|Aa B→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|a
j=2时：改写文法，有 B→bBA’Bb|a无左递归。
（3） 所以文法G[S]消除左递归后变为：
G’[S]：S→AB
A→bBA’ A’→aA’|ε B→bBA’Bb|a
2.设有文法G[E]:
E→Aa|Bb A→cA|eB B→bd
试按照递归子程序法为该文法构造语法分析程序。 解：本题考查递归子程序的构造方法。
首先判断文法是否满足递归子程序法对文法的要求，然后再构造递归子程序。
因为：
（1） 该文法无左递归。
（2） 文法的产生式E→Aa|Bb和A→cA|eB的右部有若干选项，判断这两条
产生式右部各候选式的终结首符号集合是否两两互不相交。
对产生式E→Aa|Bb，有
FIRST(Aa)∩FIRST(Bb)={c，e}∩{b}=ø
对产生式A→cA|eB，有
FIRST(cA)∩FIRST(eB)={c}∩{e}=ø
文法中其他产生式都只有一个非空ε的右部。 综合（1）、（2），该文法可以采用自上而下分析方法进行语法分析而不会出
现回朔和无限循环。
下面为该文法的每一个非终结符号构造递归子程序。
假设用READAWORD代表读下一个单词。用P(E)、P(A)、P(B)分别表示非
终结符号E、A、B对应的子程序名。约定输入符号串以“#”作为输入结束符。 P(E)的递归子程序为： PROCEDURE P(E); BEGIN IF WORD IN FIRST(Aa) THEN BEGIN P(A); READAWORD; IF WORD=’a’ THEN READAWORD ELSE ERROR END ELSE IF WORD IN FIRST(Bb) THEN BEGIN P(B); READAWORD; IF WORD=’b’ THEN READAWORD ELSE ERROR END ELSE ERROR END; P(A)的递归子程序为： PROCEDURE P(A); BEGIN IF WORDD=’c’ THEN BEGIN READAWORD; P(A) END ELSE IF WORD=’e’ THEN BEGIN READWORD; P(B) END ELSE ERROR END; P(B)的递归子程序为： PROCEDURE P(B); BEGIN IF WORD=’b’ THEN BEGIN READAWORD;
IF WORD=’d’ THEN READAWORD ELSE ERROR END ELSE ERROR END; 主程序中的主要内容为： READAWORD; P(E); IF WORD=”#” THEN WRITE(“RIGHT!”) ELSE WRITE(“ERROR!”)
3.已知文法G[E]：
G[E]：E→E+T|T
T→T*F|F F→i|(E)
请按递归子程序法为其构造语法分析程序。 解：本题考查递归子程序的构造方法。
本题所给文法存在左递归，不满足递归子程序法对文法的要求，必须首先消除文法左递归，然后再构造分析程序。
因为文法只有左递归，采用扩充的BNF范式消除文法左递归得到：
G[E]：E→T{+T}
T→F{*F} F→i|(E)
然后再应用书中介绍的方法即可求解。
假定用“ADVANCE;”表示对读取下一个单词的过程的调用。 相应的递归子程序为： PROCEDURE P(E); BEGIN P(T); WHILE SYM=’+’ DO BEGIN
ADVANCE;
P(T) END END; PROCEDURE P(T); BEGIN P(F); WHILE SYM=’*’ DO BEGIN ADVANCE; P(F) END END; PROCEDURE P(F); BEGIN
IF SYM=’i’ THEN ADVANCE ELSE IF SYM=’(’ THEN BEGIN ADVANCE; P(E); IF SYM=’)’ THEN ADVANCE ELSE ERROR END ELSE ERROR END;
主程序中的主要内容为： ADVANCE; P(E); IF WORD=”#” THEN WRITE(“RIGHT!”) ELSE WRITE(“ERROR!”)
4．文法G[M]是否是LL(1)文法，说明理由。
G[M]：M→TB
T→Ba|ε B→Db|eT|ε D→d|ε
解：本题考查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，#，a} FOLLOW(D)=FIRST(b)\\{ε}={b}
可以看出，对文法G[M]的产生式T→Ba|ε，有 FIRST(Ba)∩FOLLOW(T)={d，b，e，a}∩{d，b，e，#，a}={d，b，e，a}≠ø
仅此一条就会导致在自上而下的语法分析过程中出现回朔。 所以文法G[M]不是LL(1)文法。
5．构造一个LL(1)文法G，识别语言L：
L={ω|ω为{0，1}上不包括两个相邻的1的非空串}
并证明你的结论。
解：本题考查文法的构造方法以及LL(1)文法的要求。
首先构造出描述该语言的文法，然后证明该文法是LL(1)文法。
（1） 根据题目要求——句子为不包括两个相邻的1的非空串，首先得到一
个能够描述所有句子的文法
G’[S]：S→0S|1A|0|1
A→0S|0
再根据LL(1)文法的要求，将文法改写为
G[S]：S→0B|1C
A→0B B→S|ε C→A|ε
（2） 下面证明文法G[S]是LL(1)文法。
对产生式S→0B|1C，没有空产生式右部(ε)，所以只要考查终结首符号集是否两两互不相交。有 FIRST(0B)∩FIRST(1C)={0}∩{1}=ø
对产生式A→0B，只有唯一的不为空ε的右部，不用考查。
对产生式B→S|ε，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。由于 FIRST(S)={0，1} FIRST(ε)={ε} FOLLOW(B)= FOLLOW(S) ∪FOLLOW(A)= FOLLOW(S) ∪FOLLOW(C) =FOLLOW(S)={#}∪FOLLOW(B)={#} 所以有 FIRST(S)∩FIRST(ε)=ø 和 FIRST(B)∩FOLLOW(B)=ø 对产生式C→A|ε，因为有空产生式右部，所以要考查终结首符号集与后继终结符号集是否相交。由于 FIRST(A)={0} FIRST(ε)={ε} FOLLOW(C) =FOLLOW(S) ={#} 所以有 FIRST(A)∩FIRST(ε)=ø 和 FIRST(C)∩FOLLOW(C)=ø
综上所述，文法G[S]的每一条形如U→X1|X2|…|Xn的产生式都满足 FIRST(Xi)∩FIRST(Xj)=ø (i≠j)
如果Xjε时，还满足 FIRST(X1)∩FOLLOW(U)=ø 所以，文法G[S]是LL(1)文法。
6．有文法G[S]：
S→aABbcd|ε
A→ASd|ε B→SAh|eC|ε C→Sf|Cg|ε D→aBD|ε
①求每一个非终结符号的FOLLOW集合。
②对每一个非终结符号的产生式选择，构造FIRST集合。 ③该文法是LL(1)文法吗？
*解：本题考查LL(1)文法的要求，涉及文法符号串FIRST集，文法非终结符号的FOLLOW集的求法。 首先将文法压缩，得到
S→aABbcd|ε
A→ASd|ε B→SAh|eC|ε C→Sf|Cg|ε
①求每一个非终结符号的FOLLOW集合：
∵S为开始符号，且有产生式 A→ASd B→SAh C→Sf
∴FOLLOW(S)={#}∪FIRST(d)∪FIRST(Ah)∪FIRST(f)={#，d，a，h，f} ∵S→aABbcd A→ASd B→SAh
∴FOLLOW(A)=FIRST(Bbcd)∪FIRST(Sd)∪FIRST(h)={b，a，d，h，e} ∵S→aABbcd
∴FOLLOW(B)=FIRST(bcd)={b} ∵B→eC C→Cg
∴FOLLOW(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(Cg)={a，f，g} FIRST(ε)={ε}
③由于存在产生式C→Sf|Cg|ε FIRST(Sf)∩FIRST(Cg)={a，f}∩{a，f，g}≠ø 所以该文法不是LL(1)文法。 7．已知文法
G[A]：A→aAa|ε
（1）该文法是LL(1)文法吗？为什么？
（2）若采用LL(1)方法进行语法分析，如何得到该文法的LL(1)分析表？ （3）若输入符号串“aaaa”，请给出语法分析过程。 （4）请给出该文法的递归下降分析子程序。 解：（1）因为产生式A→aAa|ε有空产生式右部，而 FOLLOW(A)={#}∪FIRST(a)={a，#} 造成FIRST(A)∩FOLLOW(A)={a，ε}∩{a，#}≠ø 所以该文法不是LL(1)文法。
（2）若采用LL(1)方法进行语法分析，必须修改该文法。 因该文法产生偶数（可以为0）个a，所以得到文法 G’[A]：A→aaA|ε
此时对产生式A→aaA|ε，有FOLLOW(A)={#}∪FOLLOW(A)={#}，因而 FIRST(A)∩FOLLOW(A)={a，ε}∩{#}= ø
所以文法G’[A]是LL(1)文法，按LL(1)分析表构造算法构造该文法的LL(1)分析表如表5.1所示。
A 表5.1 文法G’[A]的LL(1)分析表 A A→aaA # A→ε （3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表5.2所示 步 骤 1 2 3 4 5 6 7 8 表5.2 对符号串“aaaa”的分析过程 分析栈 输入串 #A aaaa# #Aaa aaaa# #Aa aaa# #A aa# #Aaa aa# #Aa a# #A # # # 产生式/动作 A→aaA 匹配 匹配 A→aaA 匹配 匹配 A→ε 接受 （4）构造文法G’[A]的递归子程序如下（假定用“ADVANCE；”表示对读取下一个单词的过 程的调用）： PROCEDURE P(A); BEGIN IF WORD=’a’ THEN BEGIN ADVANCE; IF WORD=’a’ THEN BEGIN READAWORD; P(A); END ELSE ERROR END ELSE IF NOT(WORD IN FOLLOW(A)) THEN ERROR END; 主程序中的主要内容为： ADVANCE; P(A); IF WORD=”#” THEN WRITE(“RIGHT!”) ELSE WRITE(“ERROR!”) 8.设文法G[S]： S→SbA|aA B→Sb A→Bc
①将该文法改写成LL(1)文法。
②求文法的每一个非终结符号的FIRST集合和FOLLOW集合。 ③构造相应的LL(1)分析表。
解：本题考查“LL(1)文法”的概念及LL(1)分析表的构造方法，涉及文法符号串的FIRST集，文法非终结符号的FOLLOW集的求法。 ①将该文法改写成LL(1)文法。
因为S→SbA|aA有左递归，将其改写为 S→aA{bA} 文法变为 G’[S]：S→aA{bA} B→Sb A→Bc
文法G’[S]满足LL(1)文法的条件
②文法G’[S]中每一个非终结符号的FIRST集合为 FIRST(S)={a} FIRST(A)={a} FIRST(B)={a} 文法G’[S]中每一个非终结符号的FOLLOW集合为 ∵S为开始符号，且有产生式B→Sb ∴FOLLOW(S)={#}∪FIRST(b)={#，b} ∵S→aA{bA}
∴FOLLOW(A)=FIRST(bA)\\{ε}∪FOLLOW{S}={#，b} ∵A→Bc
∴FOLLOW(B)=FIRST{c}\\{ε}={c} ③构造相应的LL(1)分析表
∵FIRST(aA{bA})={a} ∴M[S，a]=’S→aA{bA}’
∵FIRST(A)={a} ∴M[A，a]=’B→Bc’ ∵FIRST(B)={a} ∴M[B，a]=’B→Sb’ 文法G[S]的分析表如表5.3所示。 表5.3 文法G[S]的分析表 a b c # S S→aA{bA} A A→Bc B B→Sb 9.考虑文法G： A→A∨B|B B→B∧C|C C→﹁D|D D→(A)|i
①试问该文法是否是LL(1)文法，为什么？ ②写出与该文法等价的LL(1)文法G1。 ③构造G1的LL(1)分析表。
解：本题考查LL(1)文法的要求，以及LL(1)分析表构造方法，涉及文法符号串的FIRST集合的求法，文法非终结符号的FOLLOW集合求法。 ①该文法不是LL(1)文法。 因为对产生式A→A∨B|B，有
FIRST(A∨B)∩FIRST(B)=FIRST(B)≠ø
不满足LL(1)文法的条件。
②构造与该文法等价的LL(1)文法G1。
这一问题实际上是要使该文法满足LL(1)文法的要求。
文法含有左递归，将导致无限循环。将文法消除左递归，得G1 A→BA’
A’→ ∨BA’|ε B→CB’
B’→ ∧CB’|ε C→﹁D|D D→(A)|i
对产生式A’→ ∨BA’|ε，有
FIRST(∨BA’)∩FOLLOW(A’)={∨}∩{#，)}=ø 对产生式B’→ ∧CB’|ε，有
FIRST(∧CB’)∩FOLLOW(B’)={∧}∩{#，)，∨}=ø 对产生式C→﹁D|D，有
FIRST(﹁D)∩FIRST(D)={﹁}∩{(，i}=ø 对产生式D→(A)|i，有
FIRST((A))∩FIRST(i)={(}∩{i}=ø
文法中其他产生式都只有一个非空(ε)的右部，所以文法G1已满足LL(1)文法的要求。 ③因为
对产生式A→BA’有 FIRST(BA’)={﹁，(，i} 对产生式B→CB’有 FIRST(CB’)={﹁，(，i} 对产生式A’→ ∨BA’|ε有 FIRST(∨BA’)={∨} 和 FOLLOW(A’)={#，)} 对产生式B’→ ∧CB’|ε有 FIRST(∧CB’)={∧} 和 FOLLOW(B’)={∨，#，)}
对产生式C→﹁D|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 # A BA’ BA’ BA’ A’ ∨BA’ ε ε B CB’ CB’ CB’ B’ ε ∧CB’ ε ε C ﹁D D D D (A) i 10.已知文法G[A]为： A→aABe|a B→Bb|d
(1)试给出与G[A]等价的LL(1)文法G’[A]。
(2)构造G’[A]的预测分析表并给出输入串aade#的分析过程。
解：本题考查“LL(1)文法”的条件，LL(1)分析表的构造方法和LL(1)语法分析过程等内容。
预测分析表就是LL(1)分析表。
(1)文法G[A]不是LL(1)文法，原因在于： ① 存在产生式A→aABe|a，使得
FIRST(aABe)∩FIRST(a)={a}≠ø 将造成语法分析过程中出现回朔。 ②存在含有左递归的产生式B→Bb|d，使得语法分析过程中会出现无限循环。 要构造与G[A]等价的LL(1)文法，实质上就是要修改原文法中存在上述两种问题的产生式。
对产生式A→aABe|a修改为 A→aC C→ABe|ε
对产生式B→Bb|d修改为 B→dB’ B’→bB’|ε 因此得到文法G’[A]： A→aC C→ABe|ε B→dB’ B’→bB’|ε
求出每一个非终结符号的FIRST集和FOLLOW集： FIRST(A)={a} FOLLOW(A)=FIRST(Be)\\{ε}∪{#}={#，d} FIRST(B)={d} FOLLOW(B)=FIRST(e)\\{ε}={e} FIRST(B’)={b，ε} FOLLOW(B’)=FOLLOW(B)={e} FIRST(C)={a，ε} FOLLOW(C)=FOLLOW(A)={#，d} 可以看出，对产生式B’→bB’|ε有 FIRST(bB’)∩FOLLOW(B’)={b}∩{e}=ø 对产生式C→ABe|ε有 FIRST(ABe)∩FOLLOW(C)={a}∩{#，d}=ø
而文法的其他产生式都只有一个非空的产生式右部，在自上而下的语法分析过程中不会出现回朔。
所以文法G’[A]就是所求的与原文法等价的LL(1)文法。 (2)构造G’[A]的预测分析表。 分析表M的构造算法为：
①对FIRST(x)中的每一终结符号a，置M[U，a]=“U→x”；
②如果ε∈FIRST(x)，则对于属于FOLLOW(U)的每一个终结符号b或#，分别置M[U，b]=“U→x”和M[U，#]=“U→x”；
③将M中所有不能按规则①与②构造的元素置出错标志ERROR(用空格表示)。
在应用算法的第二条时要注意，“对于属于FOLLOW(U)的每一个终结符号b或#”是指FOLLOW(U)中含有b或者FOLLOW(U)中含有#时，而不是指对#以及FOLLOW(U)中的b都进行处理。如果FOLLOW(U)中有#，则置M[U，#]=“U→x”；如果FOLLOW(U)中无#，则不置M[U，#]=“U→x”。
下面为G‘[A]构造预测分析表。 对产生式A→aC ∵FIRST(aC)={a} ∴M[A，a]=“A→aC”
对产生式B→dB’ ∵FIRST(dB)={d} ∴M[B，d]=“B→dB’”
对产生式B’→bB’|ε ∵FIRST(bB’)={b} ∴M[B’，b]=“B’→bB’” 又∵FOLLOW(B’)={#，e} ∴M[B’，#]=“B’→ε”，M[B’，e]=“B’→ε” 对产生式C→AB|ε ∵FIRST(AB)={a} ∴M[C，a]=“C→AB” ∵FOLLOW(C)={#，d} ∴M[C，#]=“C→ε”，M[C，d]= “C→ε” 根据LL(1)分析表的构造算法得到:LL(1)分析表如表5.5所示。
表5.5 文法G’[A]的预测分析表 a b d e A→aC B→dB’ B’→bB’ B’→ε C→AB C→ε A B B’ C # B’→ε C→ε 下面给出对输入串aade#的分析过程，如表5.6所示。
表5.6 对符号串aade#的分析过程 分析栈 输入串 #A aade# #Ca aade# #C ade# #eBA ade# #eBCa ade# #eBC de# #eB de# #eB’d de# #eB’ e# #e e# # # 步骤 1 2 3 4 5 6 7 8 9 10 11
产生式/动作 A→aC 匹配 C→ABe A→aC 匹配 C→ε B→dB’ 匹配 B’→ε 匹配 接受
因篇幅问题不能全部显示，请点此查看更多更全内容