编译原理(第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|ε