第二版编译原理课后答案

第 1 章

1．(1) × (2) √ (3) × (4) × (5) × (6) √

第 2 章

1．(1) √(2) √ (3) × (4) × (5) × (6) ×

2．（1）终结符：0，1，2，3，4，5，6，7，8，9，10

非终结符：N，S，E，D

（2）

①N SE S10 D10 110

（2）此文法产生的语言是：所有 a 的个数与 b 的个数相等的由 a 和 b 组成的字符串。

4．能被 5 整除的数从形式上看，是以 0，5 结尾的数字串。题目要求不以 0 开头，注意 0

不是该语言的句子。

所求文法 G[S]:

S→MF|5

F→5|0

N→1|2|3|4|5|6|7|8|9

D→N|0

M→MD|N

其中，S 代表能被 5 整除且不以 0 开头的无符号整数;

1

D

N 代表所有非零数字;

M 代表不以零开头的数字串。

5．（1）令 S 为开始符号，产生的 w 中 a 的个数恰好比 b 多一个，令 E 为一个非终结符号，

产生含相同个数的 a 和 b 的所有串，则产生式如下：

（2）设文法开始符号为 S，产生的 w 中满足|a|≤|b|≤2|a|。因此，可想到 S 有如下的产生式

（其中 B 产生 1 到 2 个 b）：

H→1|2|3|4|5|6|7|8|9

T→ 1|3|5|7|9

M→MN|N

N→0|H

其中，H 代表奇数头，T 代表奇数尾，M 代表整数，N 代表数字

6．（1）1 型（2）2 型（3）3 型

7．正确的程序为：

var a,b,c;

begin

read(a,b);

write(a,b,c);

end.

8．(1) 扩充条件语句的语法图为：

EBNF 的语法描述为：〈条件语句〉→if〈条件〉then〈语句〉[else〈语句〉]

(2) 扩充 repeat 语句的语法图为：

EBNF 的语法描述为：〈repeat 循环语句〉→ repeat〈语句〉{；〈语句〉 }until〈条

件〉

第 3 章

1．(1) √ (2) √ (3) × (4) × (5) √ (6) √ (7) × (8) √ (9) × (10) ×

2．注意 正规式不唯一

（1）(0|1)*01 （2）1*01* （3）(11)*

（4）(0*10*10*)* （5）(0|1)*01(0|1)* （6）1*0*

3．（1）必须以 x 开头和 x 结尾的串

（2）每个 y 至少有一个 x 跟在后边的串

（3）所有含两个相继的 x 或两个相继的 y 的串

4．

标记为others的边是指字符集中未被别的边指定的任意其它字符。

分析：这个DFA的状态数及含义并不难确定，见下面的五个状态说明。

状态1：注释开始状态。

这下一个字符看成可能是结束注释的第一个字符。若没有这个边，那么象

这样的注释就被拒绝。

另外，上面的状态转换图并不完整。例如，对于状态1，没有指明遇到其它字符怎么办。

要把状态转换图画完整，还需引入一个死状态6，.进入这个状态就再也出不去了。因为它

不是接受状态，因此进入这个状态的串肯定不被接受。完整的状态转换图见下图，其中all

表示任意字符。在能够说清问题时，通常我们省略死状态和所有到它的边。

5．先写出渡河的方法，串中对象顺序为人来回渡河时所运的货物的顺序：

*

/

6

others

others

all

all

①羊空菜羊狼空羊

②羊空狼羊菜空羊

其中 Σ={羊，空，菜，狼}

Q={0,1,2,3,4,5,6,7,8,9}

6．这个 DFA 和无符号数的 DFA 有类似的地方。

首先考虑 device:和.extension 全都出现的情况。（即：device:name.extension）这时的

DFA 比较容易构造。

然后考虑缺省情况：

(1) 因为.extension 可缺省（即：device:name），因此把状态 4 也作为接受状

态。

(2) 因为 name 和 device 一样，都是字母序列，所以在 device:缺省时，把到状

(3) （即：name.extension）因为 name 和 device 一样，都是字母序列，因此在

device:缺省时，把到状态 2 为止得到的字母序列看成是 name，所以从状

7

．

文

法

所

对

应

l l

1 2 3 4 5

.

接受文件名的 DFA

的正规式为：

S=0A|1B

=0(1S|1)| 1(0S|0)

=0(1S|1)|1(0s!0) 分配率

=01S|01|10S|10 交换率

=01S|10S|01|10 分配率

=(01|10)S|(01|10)

=(01|10)*(01|10)

8．该正规式所表示的语言为：

L(G)={X|X 以三个 0 结尾的二进制数字串}

文法时，将句子分成(0|1)*和 000 两部分考虑。(0|1)*可以通过递归实现，000 则只需要逐个

生产即可。所以构造其等价的右线性文法如下：

G[S]:

9．（1）根据题意，得到相应的正规式：0(0|1)*1

（3）NFA 确定化后的 DFA 如下图所示：

10．（1）L(G)={X|X 是至少含有两个连续 1 的二进制数字串}

（2）正规式为：(0|1)*11(0|1)*

正规式到正规文法的转换过程为：

0