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

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