发布时间 : 星期六 文章编译原理(第2版)课后习题答案详解更新完毕开始阅读
或者：因为存在推导序列: 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
答案：
(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）{ anbnambm| n，m>=0} （2）{ 1n0m 1m0n| n，m>=0}
（3）{WaWr|W 属于{0|a}*，Wr 表示 W的逆}
答案：
（１） S→AA A→aAb|ε （２） S→1S0|A A→0A1|ε （３）
S→0S0|1S1|ε