《编译原理》课后习恩答案第三章 第10题 文法S*SSS ()生成的语言是什么？ 2该文法是二义的吗？说明理由 答案： (1)嵌套的括号 (2)是二义的，因为对于()()可以构造两棵不同的语法树。 第11题 令文法GE为： E◆TE+TE-1 T一→TFT/F F(Ei 证明E+TF是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列 E=>E+T=>E+TF,所 以E+T*F句型 此句型相对于E的短语有E+TF:相对于T的短语 有 直接短语为：TF 句柄为：T*F ]· 第13题 一个上下文无关文法生成句子abbaa的推导树如下： (山)给出串abbaa最左推导、最右推导。 2)该文法的产生式集合P可能有哪些元素？ 3)找出该句子的所有短语、直接短语、句柄。 A B a bb a 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 第 10 题 文法 S→S(S)S|ε (1) 生成的语言是什么？ (2) 该文法是二义的吗？说明理由。 答案： （１） 嵌套的括号 （２） 是二义的，因为对于（）（）可以构造两棵不同的语法树。 第 11 题 令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以 E+T*F 句型 此句型相对于 E 的短语有:E+T*F；相对于 T 的短语 有 T*F 直接短语为：T*F 句柄为：T*F 第 13 题 一个上下文无关文法生成句子 abbaa 的推导树如下： (1)给出串 abbaa 最左推导、最右推导。 (2)该文法的产生式集合 P 可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 B a S A B S a S B A ε b b a 盛威网（www.snwei.com）专业的计算机学习网站 6
《编译原理》课后习题答案第三章 答案： ()串abbaa最左推导 AB >aBS->aSBBS->aBBS->abBS->abbS-abbAa->abbaa 最石推导： S=>ABS=>ABAa=→ABaa=→ASBBaa=>ASBbaa=>ASbbaa=→Abbaa=>abbaa (2)产生式有：S→ABS1AaeA→aB→SBBb 可能元素有：￡aaab abbaa aaabbaa (3)该句子的短语有 a是相对A的短语 ε是相对S的短请 b是相对B的短语 cbb是相对B的短语 aa是相对S的短语 acbbaa是相对S的短语 直接短语有：aeb 句柄是：a 第14题 给出生成下述语言的上下文无关文法。 (1){aba"b"1n,m>=0 2)1r1a,m>-0 (3)WaWW属于0，Wr表示W的逆 答案： (1) S-AA A→aA ble (2) S1SOIA A→0A13 (3) S→0s01S川 盛成网(www.snwei.com)专业的计算机学习网站 7
《编译原理》课后习题答案第三章 答案： (1)串 abbaa 最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b 可能元素有：ε aa ab abbaa aaabbaa . (3)该句子的短语有： a 是相对 A 的短语 ε 是相对 S 的短语 b 是相对 B 的短语 εbb 是相对 B 的短语 aa 是相对 S 的短语 aεbbaa 是相对 S 的短语 直接短语有：a ε b 句柄是：a 第 14 题 给出生成下述语言的上下文无关文法： （1）{ an bn ambm| n，m>=0} （2）{ 1n 0m 1m0n | n，m>=0} （3）{WaWr|W 属于{0|a}*，Wr 表示 W 的逆} 答案： （１） S→AA A→aAb|ε （２） S→1S0|A A→0A1|ε （３） S→0S0|1S1|ε 盛威网（www.snwei.com）专业的计算机学习网站 7