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

第 9 题

考虑下面上下文无关文法：

S→SS*|SS+|a

(1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？

答案：

(1)此文法生成串 aa+a*的最右推导如下

S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

S A c a b S a B b c S S S * S S + a a a

第 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