发布时间 : 星期六 文章编译原理(第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