编译原理答案

《编译原理》练习题参考答案

一

一、填空题

(1) 开始符号S (2) 终结符号 (3) 标记为ε (4) 一个句子 (5) 已化简的文法 (6) 内部表示 (7) 类别 (8) (VN,VT,P,S) (9) 字汇表 (10) 手工的方式 (11) 自动生成 (12) 直接递归的 (13) 递归的 (14) 所区分 (15) 非终态

(16) 规范推导 (17) 规范句型 (18) 终态结点 (19) 标记字符 二、选择题

1. C 2. A 3. D 4. A 5. B 6. B 7. A 8. C 9. B 三、证明题 1．

证明： 因为文法G[S]的一个句子aaabaaba对应如下的两个最左推导序列： S ? aB ? aaBB ? aabSB ? aabbAB ? aabbaB ? aabbab

S ? aB ? aaBB ? aabB ? aabbS ? aabbaB ? aabbab

所以文法G[S]为二义性文法。 2．

证明： 因为文法G[S]的一个句子aaab对应如下的两个最左推导序列： S ? aAB ? aaAB ? aaaB ? aaab

S ? aAB ? aaB ? aaaB ? aaab

所以文法G[S]为二义性文法。 四、简答题

1．解：对应的文法为： S→aAd

A→aAd∣bBc B→bBc∣ε

2．解：首先求出如下集合

W(S)={S,A,B}, W(A)={A,B}, W(B)={B}

然后按如下步骤得到产生式集P′：

将P中的所有非单产生式添加到P′中：

S→AbB A→AB∣caB B→Aa∣b

因为A,B∈W(S)，故将A,B的所有非单产生式的右部作为S-产生式的右部添加到P′中：

S→AB∣caB S→Aa∣b

因为B∈W(A)，故将B的所有非单产生式的右部作为A-产生式的右部添加到P′中：

A→Aa∣b

由此得到消除单产生式后的文法如下：

S→AbB∣AB∣caB∣Aa∣b A→AB∣caB∣Aa∣b B→Aa∣b

3．解： 与正规式相应的状态转换图如图所示：

4． 解：对于G，我们可得到W={A,B}，于是得到消除ε-产生式后的文法为：

S→ABb∣a∣Bb∣Ab∣b A→aB∣caB∣a∣ca B→aA∣b∣a

5．解： 产生的语言为： L(G)={ abecd∣m,n≥1 }

6．解： 首先求出如下集合

W(S)={S,F,M}, W(F)={F,M}, W(M)={M}

然后按如下步骤得到产生式集P′：

将P中的所有非单产生式添加到P′中：

S→aFbM F→abc M→abF∣c

因为F,M∈W(S)，故将F,M的所有非单产生式的右部作为S-产生式的右部添加到P′中：

S→abc S→abF∣c

因为M∈W(F)，故将M的所有非单产生式的右部作为F-产生式的右部添加到P′中：

F→abF∣c

由此得到消除单产生式后的文法如下：

S→aFbM∣abc∣abF∣c F→abc∣abF∣c M→abF∣c

7．解：因为由非终结符号C,D推导不出终结符号串，因此C,D是无用符号，含有C,D的产生式S→Cc,C→Da,D→Cb∣CDa都是无用产生式，应予以删除。

因此我们最后得到与原文法等价且不含无用符号及无用产生式的文法为:

S→Bab B→bS∣b

8． 解： 与正规式相应的状态转换图如图所示：

nmmn

9．解：对应的文法为： S→aA

A→bB B→bB∣cC C→bC∣a

10．解： L[G]={a(ab)ba(ab)cd∣n,m,k≥0}

五、应用题

1．解： (1) 相应的状态转换图如图所示：

n

mk

BaaSbccDcAbabC (2) 相应的3型文法为：

S→aA∣bA∣cA A→aB∣bC∣cD∣a∣b∣c

B→aA C→bA D→cA

2．解：(1) 将NFA M确定化后得DFA M′，其状态转换矩阵如图(a)所示，给各状态重新命名，即令：

[A]=1, [B,C]=2, [E,F] =3, [C]=4 [C,E]=5, [F]=6, [E]=7

且由于3,5,6和7的组成中均含有M的终态E,F，故3,5,6和7组成了DFA M′的终态集Z′。