编译原理第二版第五章答案

编译原理 第二版五章答案

本页仅作为文档封面，使用时可以删除

This document is for reference only-rar21year.March

第

第五章

第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 FIRST a ^ ( a ^ ( FOLLOW # , ) ) N

, ε ) 对左部为N2的产生式可知： FIRST （->, S N2）={，} FIRST （->ε）={ε} FOLLOW （N2）={)} {，}∩ { )}=?

所以文法是LL(1)的。

预测分析表 S T N

也可由预测分析表中无多重入口判定文法是LL(1)的。 (4)对输入串（a,a）#的分析过程为：

步骤 1 2 3 4 5 6 7 8 9 10 11 12 状态栈 #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->ε 匹配 a ->a ->S N ^ ->^ ->S N ( ->( T ) ->S N ) ->ε , ->, S N #