精品文档
第五章 习题参考答案
1、(1) 对(a,(a,a)的最左推导为：S(a,(a,S))((S,S,S),S)
(a,(a,a))
(T)
(T,S)
(S,S)
((T),S)
((T,S),S)
((T,S,S),S)(((a,a),∧,S),S)
(((T),S,S),S)
(((T,S),S,S),S)(((a,a),∧,(S)),S)
(((S,S),S,S),S)(((a,a),∧,(a)),S)
(((a,S),S,S),S)
(((a,a),S,S),S)
(T)
(T,S)
(S,S)
(a,S)
(a,(T))
(a,(T,S))
(a,(S,S))
对(((a,a),∧,(a)),a) 的最左推导为：S(((a,a),∧,(T)),S)
(((a,a),∧,(a)),a)
对((( a, a ), ?, ( a )), a )的最左推导为：S ? ( T ) ? ( T, S ) ? ( S, S ) ? (( T ), S ) ? (( T, S ), S )
?(( T, S, S ), S )
? (( S, S, S ), S ) ? ((( T ), S, S ), S ) ? ((( T, S ), S, S ), S ) ? ((( S, S ), S, S ), S ) ? ((( a, S ), S, S ), S ) ? ((( a, a ), S, S ), S ) ? ((( a, a ), ?, S ), S ) ? ((( a, a ), ?, ( T )), S ) ? ((( a, a ), ?, ( S )), S ) ? ((( a, a ), ?, ( a )), S ) ? ((( a, a ), ?, ( a )), a )
对((( a, a ), ?, ( a )), a )的最左推导为：S ? ( T ) ? ( T, S ) ? ( T, a ) ? ( S, a ) ? (( T ), a ) ? (( T, S ), a )? (( T, ( T )), a ) ? (( T, ( S )), a ) ? (( T, ( a )), a ) ? (( T, S, ( a )), a ) ? (( T, ?, ( a )), a ) ? (( S, ?, ( a )), a ) ? ((( T ), ?, ( a )), a ) ? ((( T, S ), ?, ( a )), a ) ? ((( T, a ), ?, ( a )), a ) ? ((( S, a ), ?, ( a )), a ) ? ((( a, a ), ?, ( a )), a )
(2) 改写文法为：
0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε
S: T: 入口 入口 N: 入口 N
a
Y S Y ， Read(w) N ^ N Y N ( Y N
出口 S Read(w) 出错 N T
出口 N ) 精品文档
精品文档
Read(w) 出口 (3) 非终结符 S T N 对左部为N的产生式可知：
SELECT(S→a)∩SELECT(S→∧) ∩SELECT(S→( T ))= SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是LL(1)的。 预测分析表
FIRST集 {a,∧,(} {a,∧,(} {,,ε}. FOLLOW集 {#,,,)} {)}.... {)}.... S T N a →a →S N ∧ ( →(T) →S N ) →ε , →, S N # →∧ →S N 也可由预测分析表中无多重入口判定文法是LL(1)的。 (4) 对输入串（a,a）#的分析过程为：
栈（STACK） 当前输入符（CUR_CHAR） 剩余输入符（INOUT_STRING） 所用产生式（OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a 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）#是文法的句子。
精品文档
精品文档
6.(2) 不是LL(1)文法
以A的产生式代入S，以D的产生式代入B中，提取左公共因子并删除多余产生式得文法： S→BC 分析表为 S B C F a BC F aB ε b BC F b d BC dF # BC F ε ε C→aB|ε
B→dF|F F→b|ε
结论：经改写之后的文法Ｇ是ＬＬ（１）文法。 递归下降分析器如同题1，从略
6.(4)消除左递归为： S→i E F S S→(E)
+ +SF
E→SF
- -SF F→+SF
i SF i F→-SF
F→ε ( SF (E) ) ε ﹟ 分析表为：
结论：经改写之后的文法Ｇ是ＬＬ（１）文法。 递归下降分析器如同题1，从略
7.(1)文法不存在左递归
第一种改法：以A的产生式替入B 产生式中 B→baBbb B→bC B C B→bb
B→a
B→a
b bC b # 消除左公共因子：
C→aBbb C→b
a a aBbb 改写之后的文法的分析表：
改写之后的文法是LL(1)文法
第二种改法：以B的产生式替入A产生式中 A→baAbb A→ε
A→baa
A→ε
C→a
消除左公共因子后为
A→baC
C→Abb
SELECT(A→baC) ∩ SELECT(A→ε) ={ b}∩ {# ,b }≠ 所以，改写之后的文法不是LL(1)文法
7.(3)第1种改写：用A的产生式右部代替S的产生式右部的A得：
精品文档
精品文档
S→SBa|b B→ab 消除左递归后文法变为： 0) S→b N 1) N→B a N 2) N→ε 3) B→a b
非终结符 S B N FIRST集 {b}... {a}... {ε,a} FOLLOW集 {#} {a} {#} SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }= 所以文法是LL(1)的。 预测分析表
S B N a →a b →B a N b →b N # →ε 第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
非终结符 S A B N FIRST集 {b}... {b}... {a}... {a,ε}
FOLLOW集 {#} {a} {a} {a} SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠所以文法不是LL(1)的。
7.(5)以A、B的产生式代入S的产生式中的A、B，得新文法： S→aC S→aC S→aC S→aC
C→Ab|b|a
A→aA|a
A→aA|a
以A的产生式代入C中提取左公共因子得：
C→aD|b D→Ab|b|ε C→aD|b D→aE|ε C→aD|b D→aE|ε
以A的产生式代入D中提取左公共因子得：
E→Ab|b A→aA|a E→aF
F→Ab|b A→aA|a
以A的产生式代入E中提取左公共因子得：
精品文档