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

问题 6：

已知文法 G[E]:

E→ET+|T

T→TF* | F

F→F^ | a

试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.

答案：

该句型对应的语法树如下：

该句型相对于 E 的短语有 FF^^*

相对于 T 的短语有 FF^^*,F

相对于 F 的短语有 F^;F^^

简单短语有 F;F^

句柄为 F.

问题 7：

适当变换文法，找到下列文法所定义语言的一个无二义的文法：

S → SaS . SbS . ScS . d

答案：

该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。

设 a、b 和 c 的优先级别依次增高，根据优先级联规则将文法变换为：

S → SaS . A

A → AbA . C

C → CcC . d

规定结合性为左结合，进一步将文法变换为：

S → SaA. A

A → AbC .C

C → CcF . F

F → d

该文法为非二义的。

问题 8：

构造产生如下语言的上下文无关文法：

（1） {anb2ncm | n，m ? 0}

（2） {anbmc2m | n，m ? 0}

（3） { ambn . m ? n }

（4）{ a m b n c p d q . m+n = p+q }

（5）{ uawb . u,w ∈{a, b}* ∧ | u | = | w | }

答案：

（1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如 anb2n 和 形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是

特别指明，通常可以忽略这一点。

对于该语言，存在一个由以下产生式定义的上下文无关文法 G[S]：

S → AB

A → ε . aAbb

B → ε . cB

（2）同样，要产生形如anbmc2m的串，可以分别产生形如 an 和形如 bmc2m 的串。对于该语

言，存在一个由以下产生式定义的上下文无关文法G[S]：

S → AB

A → ε . aA

B → ε . bBcc

（3）考虑在先产生同样数目的 a,b，然后再生成多余的 a。以下 G[S]是一种解法：

S → aSb . aS . ε

（4）以下 G[S]是一种解法：

S → aSd . A . D

A → bAd . B

D → aDc . B

B → bBc . ε

注：a 不多于 d 时，b 不少于 c；反之，a 不少于 d 时，b 不多于 c。前一种情形通过 对应 A，后一种情形对应 D。

（5）以下 G[S]是一种解法：

S → Ab

A → BAB . a