《编译原理》课后习答案第五章 第5章自顶向下语法分析方法 第1题 对文法GS T-T.S/S ()给出(a(a,a》和a,a,人，a,a)的最左推导。 (②)对文法G,进行改写，然后对每个非终结符写出不带回湖的递归子程序。 ③)经改写后的文法是否是1山1)的：给出它的预测分析表。 (给出输入串(a,a)4的分析过程，并说明该串是否为G的句子。 答案： ()对(a(aa)的最左推导为： S→T) TS) →(S,S →(aS) →(a(T) →(a(T,S) (a (SS)) →a(as →a,(a,a) 对(aa,人，(a),a)的最左推导为： S→T TS) →S,S) →(TS) →(T.S).S) →T,S,S),S) S SS)S) →(T,S),S,S,S) →SS).S.S).S →(a,S),s,S),S) →(a.alS.S).S) →(a,aΛ，S.S) →a,aA.(.S →(a,a,A,S),S)】 盛威网(ww.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第五章 第 5 章 自顶向下语法分析方法 第 1 题 对文法 G[S] S→a| |(T) ∧ T→T,S|S (1) 给出(a,(a,a))和(((a,a), ,(a)),a) ∧ 的最左推导。 (2) 对文法 G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (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) ∧ 盛威网（www.snwei.com）专业的计算机学习网站 1
《编译原理》课后习题答案第五章 (2)改写文法为： 0)s→a 1)S+A 2)ST) 3)T-SN 4)N-.SN 5)N+E 非终结符 FIRST集 FOLLOW集 aΛ.C #月 T {a,Λ，0 ) N 对左部为N的产生式可知： FIRST(→，SN)={,} FIRST(→E)={E} FOLLOW (N)=0 由于SELECT(N→，SN OSELECT(N-→g)={,n{)e 所以文法是L()的。 预测分析表(Predicting Analysis Table) a →a (I T→sN→sN SN N →，SN 也可由预测分析表中无多重入口判定文法是LL()的。 盛威网(wwsnwei.cor)专业的计算机学习网站
《编译原理》课后习题答案第五章 (((a,a), ,(a)),S) ∧ (((a,a), ,(a)),a) ∧ (2) 改写文法为： 0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε 非终结符 FIRST 集 FOLLOW 集 S {a, ,(} ∧ {#,)} T {a, ,(} ∧ {)}. N {,ε}. {)}. 对左部为 N 的产生式可知： FIRST （→, S N）={，} FIRST （→ε）={ε} FOLLOW （N）={)} 由于 SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是 LL(1)的。 预测分析表（Predicting Analysis Table） a ∧ ( ) , # S →a →∧ →(T) T →S N →S N →S N N →ε →, S N 也可由预测分析表中无多重入口判定文法是 LL(1)的。 盛威网（www.snwei.com）专业的计算机学习网站 2
《编译原理》课后习答案第五章 (3)对输入串(aa)#的分析过程为： 当前输入符 到金输入符 所用产生式 栈(STACK) (CUR_CHAR) (INOUT_STRING) (OPERATION) a,a)# S-T) #T( a.a)# a #Na a N a) N-,SN #NS. #NS S-a N→E 可见输入串(aa)#是文法的句子。 盛威网(wsnwei.com)专业的计算机学习网站
《编译原理》课后习题答案第五章 (3) 对输入串（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）#是文法的句子。 盛威网（www.snwei.com）专业的计算机学习网站 3
《编译原理》课后习题答案第五章 第3题 已知文法GS: S→MHa H-LSole K-dMLE LeHf M-KbLM 判断G是香是L()文法，如果是，构造L山1)分析表。 答案： 文法展开为： 0)S-MH 1)S-a 2)H-LSo 3)H-8 4)K→+dML 5)K8 8)M-bLM 非终结符 FIRST集 FOLLOW集 fa.d.b.c.e} {# M {d.cb) {e,#,o} H #,Eo} L {e} ia.d.b.e,o# (d.s) {e,#,o} 对相同左部的产生式可知 SELECT(S-M H)NSELECT(S-a)={d.be,#a)- SELECT(H→LSo)nSELECT(H→+e)=e}∩I#.f.o,=⑦ SELECT(K-→dML)nSELECT(K-→e)={d;n{e,#,oe SELECT(M-K)NSELECT(M-b L M)={d,e,#on(b 所以文法是LL()的。 盛威网(wwsnwei.cor)专业的计算机学习网站
《编译原理》课后习题答案第五章 第 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)的。 盛威网（www.snwei.com）专业的计算机学习网站 4
《编译原理》课后习答案第五章 预测分析表： a d f b -a →MH →MH →MH →MH →MH 女 K →K K -bLM K +8 -LSo L eHf K →dML 由预测分析表中无多重入口也可判定文法是LL()的。 盛威网(ww.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第五章 预测分析表： 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)的。 盛威网（www.snwei.com）专业的计算机学习网站 5