第五章
第5章自顶向下语法分析方法
练习（P99） 1.文法 S->a|^|(T) T->T,S|S
(1) 对(a,(a,a)和(((a,a),^,(a)),a)的最左推导。
(3)经改写后的文法是否为LL（1）的给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 (1) 对(a,(a,a)的最左推导为： S=>(T)
=>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(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) (3)改写文法为： 0) S->a 1) S->^ 2) S->( T ) 3) T->S N 4) N->, S N 5) N->ε
S T a ^ ( a ^ ( FIRST FOLLOW # , ) ) N
, ε ) 对左部为N2的产生式可知： FIRST （->, S N2）={，} FIRST （->ε）={ε} FOLLOW （N2）={)} {，}∩ { )}= 所以文法是LL(1)的。
预测分析表 S T N
也可由预测分析表中无多重入口判定文法是LL(1)的。 (4)对输入串（a,a）#的分析过程为：
a ->a ->S N ^ ->^ ->S N ( ->( T ) ->S N ) ->ε , ->, S N #
步骤 1 2 3 4 5 6 7 8 9 10 11 状态栈 #S #)T( #)T #)N2S #)N2a #)N2 #)N2S, #)N2S #)N2a #)N2 #) 当前字符 ( ( A A A , , a a ) ) 剩余输入串 操作 a,a)# a,a)# ,a)# ,a)# ,a)# a)# a)# )# )# # # S->(T) 匹配 T->SN2 S->a 匹配 N2->,SN2 匹配 S->a 匹配 N2->ε 匹配 12 # # 可见输入串（a,a）#是文法的句子。 2．对下面的文法G： E→TE′ E′→+E|ε T→FT′ T′→T|ε F→PF′ F′→* F′|ε P→(E)|a|b|^
(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。 (2) 证明这个文法是LL(1)的。 (3) 构造它的预测分析表。 (4) 构造它的预测下降分析程序
【解】(1)由题意分析得可推导出ε的非终结符表为： 各非终结符的FIRST集为：
FIRST(E)= FIRST(T)={(，a，b，^} FIRST(E′)={+}∪{ ε}={+，ε} FIRST(T)= FIRST(F)={(，a，b，^}
FIRST(T′)= FIRST(T) ∪{ ε}={(，a，b，^，ε}
FIRST(F)= FIRST(P)={(，a，b，^} FIRST(F′)={*}∪{ ε}={*，ε} FIRST(P)={(，a，b，^}
∴最终求得各非终结符的FIRST集为：
FIRST(E)={(，a，b，^} FIRST(E′)={+，ε} FIRST(T)={(，a，b，^} FIRST(T′)= {(，a，b，^，ε} FIRST(F)={(，a，b，^} FIRST(F′)={*，ε} FIRST(P)={(，a，b，^} 各非终结符的FOLLOW集为： FOLLOW(E)={#}∪FOLLOW(E′) ∪{ )} FOLLOW(E′)= FOLLOW(E)
FOLLOW(T)= FOLLOW(T′) ∪(FIRST(E′)-{ ε})∪FOLLOW(E) FOLLOW(T′)= FOLLOW(T)
FOLLOW(F)= (FIRST(T′)-{ ε})∪FOLLOW(T)
编译原理 第二版 第五章答案
