《编译原理》课后习答案第五章 第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
《编译原理》课后习题答案第五章 第7题 对于一个文法若消除了左递自，提取了左公共因子后是香一定为山（文法试对下面 文法进行改写，并对改写后的文法进行判断。 (1)A-baB]e B→Abbia (2)A→aABela B一Bhbd )S一Aab A-SB B→ab 答案： (1)先改写文法为： 0)A→baB 1)A 2)B-baBbb 3)B-b 4)B→a 再改写文法为： 0)A-baB 1)A→E 2)B→bN 3)B-a 4)N-→aBbb 5)N-+b FIRST FOLLOW h N (b,a b 预测分析表： a b A →baB B →bN N aBbb→b 由预测分析表中无多重入口判定文法是()的 (2)文法： A-aABela B→Bbld 提取左公共因子和消除左递归后文法变为： 盛咸网(ww.snwi.cor专业的计算机学习网站 6
《编译原理》课后习题答案第五章 第 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 盛威网（www.snwei.com）专业的计算机学习网站 6
《编译原理》课后习恩答案第五章 2)N→e 3)B-dNI 4)N1-bNI 5)N1→e 非终结符 FIRST集 FOLLOW集 A (a) {#,d B (dy fe N (as) {#,d NI (b.e) fe) 对相同左部的产生式可知： SELECT(N-→ABe)OSELECT(N-→e={a}n{#,d-2 SELECT(NI-→bNI)OSELECT(NI-→e)={b;n{e=2 所以文法是LL(1)的 预测分析表(Predicting Analysis Table】 a e h d aN -d NI bNI N →ABe 一8 →8 也可由预测分析表中无多重入口判定文法是LL(1)的。 (3)文法： A-→SB B-ab 第1种支写： 用A的产生式右部代替S的产生式右部的A得： S-SBalb B→ab 消除左递归后文法变为： 0)S→bN 1)N-BaN 2)N-e 3)B-ab 盛威网(ww.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第五章 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 盛威网（www.snwei.com）专业的计算机学习网站 7
《编译原理》课后习题答案第五章 非终结符 FIRST集 FOLLOW集 (b {#} B (a) a! N {e,a} 对相同左部的产生式可知： SELECT(N-B a N)OSELECT(N-8)=an#=2 所以文法是LL(1)的。 预测分析表(Predicting Analysis Table) b →bN -ab N →BaN 也可由预测分析表中无多重入口判定文法是(1)的。 第2种故写： 用S的产生式右部代替A的产生式右部的S得： S→Aalb A→AaB/bB 消除左递归后文法变为： 0)S-Aa 1)9h 2)AhBN 3)N-aBN 4)N一e 5)B→ab 非终结符 FRST集 FOLLOW集 (b) A b fay B a N (as) (a] 对相同左部的产生式可知： SELECT(S-→Aa)nSELECT(S-→b)={bn(b}={be SELECT(N-BNNSELECTON- 所以文法不是LL(I)的 盛威网(ww.snwei.com)专业的计算机学习网站 8
《编译原理》课后习题答案第五章 非终结符 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} 盛威网（www.snwei.com）专业的计算机学习网站 8 对相同左部的产生式可知： SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠ SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠ 所以文法不是 LL(1)的
《编译原理》课后习答案第五章 预测分析表： a b Aa →b -bBN B →ab N +8 也可由预测分析表中含有多重入口判定文法不是LL()的。 盛威网(ww.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第五章 预测分析表： a b # S →A a. →b. A →b B N B →a b. N →a B N →ε. 也可由预测分析表中含有多重入口判定文法不是 LL(1)的。 盛威网（www.snwei.com）专业的计算机学习网站 9
《编译原理》课后习题答案第五章 附加题 问题1： 已知文法GA如下，试用类C或类PASCAL语言写出其递归下降子程序.（主程序不需 GIA]:A-[B B-XI(A) X→(abab时 答案： 不妨约定：在进入一个非终结符号相应的子程序前，已读到一个单词.od:存放当前读 到的单词，Getsym()为一子程序，每调用一次，完成读取一单词的工作。cror0为出错处理 程序FIRST(A)为终结符A的FIRST集. 类C程序如下： void A() void B() void X() {X0: if word= if word=T if(word==allword='b) Getsym(). Getsvmo: BO: while(word in while(word=-a'llword-b') FIRST(A)) Getsym(). AO: se error() 问题2： 设有文法GA的产生式集为： A→BaC]CbB B→Aele C→Bbb 试消除GA的左递归。 答案： 提示：不妨以A、B、C排序先将A代入B中，然后消除B中左递归：再将A、B代 入C中。再消除C中左递归。 最后结果为：GA A→BaClCbB B→CbBcB'IcBB→aCcB] C→cBbC'bC C→bBcB'bCLE 盛威网(ww.snwei.com)专业的计算机学习网站 10
《编译原理》课后习题答案第五章 附加题 问题 1： 已知文法 G[A]如下，试用类 C 或类 PASCAL 语言写出其递归下降子程序.(主程序不需 写) G[A]: A→[B B→X]{A} X→(a|b){a|b} 答案： 不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词.word：存放当前读 到的单词，Getsym()为一子程序，每调用一次，完成读取一单词的工作。error()为出错处理 程序.FIRST(A)为终结符 A 的 FIRST 集. 类 C 程序如下： void A() { if word=='[' { Getsym(); B(); } else error(); } void B() { X(); if word==']' { Getsym(); while(word in FIRST(A)) A(); } else error(); } void X() { if (word= ='a'||word=='b') { Getsym(); while(word= ='a'||word=='b') Getsym(); } else error(); } 问题 2： 设有文法 G[A]的产生式集为: A→BaC|CbB B→Ac|c C→Bb|b 试消除 G[A]的左递归。 答案： 提示：不妨以 A、B、C 排序.先将 A 代入 B 中，然后消除 B 中左递归；再将 A、B 代 入 C 中。再消除 C 中左递归。 最后结果为:G[A]: A→BaC|CbB B→CbBcB'|cB' B'→aCcB'|ε C→cB'bC'|bC' C'→bBcB'bC'|ε 盛威网（www.snwei.com）专业的计算机学习网站 10