编译原理(第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的逆}

答案:

(1) S→AA A→aAb|ε (2) S→1S0|A A→0A1|ε (3)

S→0S0|1S1|ε

联系客服:779662525#qq.com(#替换为@)