清华大学第二版编译原理答案
a , , a a ) ) #
a,a)#... a,a)#... ,a)#... ,a)#... ,a)#... a)#... a)#... )#... )#... #... #... S→(T) .
T→SN S→a .
N→,SN . S→a .
N→ε
可见输入串（a,a）#是文法的句子。 第3 题
已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM
判断G 是否是LL(1)文法，如果是，构造LL(1)分析表。 答案：
文法展开为： 0） S→M H 1） S→a 2） H→L S o 3） H→ε
清华大学第二版编译原理答案
4） K→d M L 5） K→ε 6） L→e H f 7） M→K 8） M→b L M
非终结符 FIRST 集 FOLLOW 集 S {a,d,b,ε,e} {#,o}........ M {d,ε,b}.... {e,#,o}...... H {ε,e}...... {#,f,o}...... L {e}......... {a,d,b,e,o,#}
K {d,ε}...... {e,#,o}......
对相同左部的产生式可知：
SELECT(S→M H)∩SELECT(S→a) ={ d,b ,e，#,o }∩ { a }= SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }= SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }= SELECT(M→K)∩SELECT(M→b L M) ={ d，e,#,o }∩ { b }= 所以文法是LL(1)的。 预测分析表： a o d e f b #
S →a →MH →MH →MH →MH →MH M →K →K →K →bLM →K H →ε →LSo →ε →ε L →eHf
K →ε →dML →ε →ε
由预测分析表中无多重入口也可判定文法是LL(1)的。 第7 题
对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面 文法进行改写，并对改写后的文法进行判断。 (１)A→baB|ε B→Abb|a (2) A→aABe|a B→Bb|d (3) S→Aa|b A→SB B→ab 答案：
(１)先改写文法为： 0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a
再改写文法为： 0) A→baB
清华大学第二版编译原理答案
1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b
FIRST FOLLOW A {b} {#} B {b,a} {#,b} N {b,a} {#,b }
预测分析表： a b #
A →baB →ε B →a →bN N →aBbb →b
由预测分析表中无多重入口判定文法是LL(1)的。 （2） 文法： A→aABe|a B→Bb|d
提取左公共因子和消除左递归后文法变为： 0) A→a N 1) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε
非终结符 FIRST 集 FOLLOW 集 A {a}... {#,d} B {d}... {e}.. N {a,ε} {#,d} N1 {b,ε} {e}..
对相同左部的产生式可知：
SELECT(N→A B e)∩SELECT(N→ε) ={ a }∩ {#,d }= SELECT(N1→b N1)∩SELECT(N1→ε) ={ b }∩ { e }= 所以文法是LL(1)的。
预测分析表（Predicting Analysis Table） a e b d # A →a N B →d N1
N1 →ε →b N1 N →ABe →ε →ε
也可由预测分析表中无多重入口判定文法是LL(1)的。 （3）文法： S→Aa|b A→SB
清华大学第二版编译原理答案
B→ab
第1 种改写：
用A 的产生式右部代替S 的产生式右部的A 得： S→SBa|b B→ab
消除左递归后文法变为： 0) S→b N 1) N→B a N 2) N→ε 3) B→a b
非终结符 FIRST 集 FOLLOW 集 S {b}... {#} B {a}... {a}
N {ε,a} {#}
对相同左部的产生式可知：
SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }= 所以文法是LL(1)的。
预测分析表（Predicting Analysis Table） a b # S →b N B →a b
N →B a N →ε
也可由预测分析表中无多重入口判定文法是LL(1)的。 第2 种改写：
用S 的产生式右部代替A 的产生式右部的S 得： S→Aa|b A→AaB|bB B→ab
消除左递归后文法变为： 0) S→A a 1) S→b 2) A→b B N 3) N→a B N 4) N→ε 5) B→a b
非终结符 FIRST 集 FOLLOW 集 S {b}... {#} A {b}... {a} B {a}... {a} N {a,ε} {a}
SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠ SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠ 所以文法不是LL(1)的。 预测分析表：
清华大学第二版编译原理答案
a b #
S →A a.. →b.... A →b B N B →a b.. N →a B N →ε...
也可由预测分析表中含有多重入口判定文法不是LL(1)的。