编译原理（第2版）课后习题答案详解 (8)

答案：

(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|ε

第 16 题

给出生成下述语言的三型文法：

(1){an|n >=0 }

(2) { anbm|n,m>=1 }

(3){anbmck|n,m,k>=0 }

答案：

(1) S→aS|ε (2) S→aA A→aA|B B→bB|b (3)

A→aA|B B→bB|C C→cC|ε

第 17 题

习题７和习题 11 中的文法等价吗？

答案：

等价。

第 18 题

解释下列术语和概念：

（１） 字母表

（２） 串、字和句子 （３） 语言、语法和语义

答案：

（１）字母表：是一个非空有穷集合。

（２）串：符号的有穷序列。

字：字母表中的元素。

句子：如果 Z x , x ∈V *T 则称 x 是文法 G 的一个句子。

+

（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所

有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规 则构成的一切基本符号串组成的集合。

语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。

语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。