编译原理答案++陈意云+高等教育出版社

编译原理的课后答案

《编译原理》习题参考答案(一)

Bug report: zpli@Or find: 电一楼二楼全球计算实验室 李兆鹏

第二章

2.3 叙述由下列正规式描述的语言 a) 0(0|1)*0 b) ((ε|0)1*)*

c) (0|1)*0(0|1)(0|1) d) 0*10*10*10*

e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

Answer:

a) 以0开始和结尾，而且长度大于等于2的0、1串 b) 所有0,1串（含空串） c) 倒数第三位是0的0、1串 d) 仅含3个1的0、1串

e) 偶数个0和偶数个1的0、1串（含空串）

2.4 为下列语言写出正规定义：

f) 由偶数个0和偶数个1构成的所有0和1的串 g) 由偶数个0和奇数个1构成的所有0和1的串

Answer:

标准答案见《编译原理习题精选》P1-P2 1.1&1.2题

2.7 用算法2.4为下列正规式构造非确定的有限自动机，给出它们处理输入串ababbab的转换序列。 c)（（ε|a）b*）* d)(a|b)*abb(a|b)*

Answer: c)NFA：

编译原理的课后答案

输入串ababbab的转换序列：

0 1456789 145678 789 1456789 10

Or 0 1456789 1456789 1236789 1456789 10

d) NFA：

输入串ababbab的转换序列：

0 1236 1456 789 10 11 12 13 16 11 14 15 16 17

2.8 用算法2.2把习题2.7的NFA变换成DFA。给出它们处理输入串ababbab的状态转换序列。

Answer: //针对2.7 (c)

3个不同的状态集合：

A = {0, 1, 2, 3, 4, 6, 7, 9, 10} B = {1, 2, 3, 4, 5, 6, 7, 9, 10} C = {1, 2, 3, 4, 6, 7, 8, 9, 10} NFA的转换表:

状态

输入符号

子集构造法应用于2.7(c)得DFA:

编译原理的课后答案

2.11 我们可以从正规式的最简DFA同构来证明两个正规式等价。使用这种技术，证明下面正规式等价。 (a) (a|b)* (b) (a*|b*)* (c) ((ε|a)b*)* Answer:

（c）NFA见2.7（c）用子集构造法化简得DFA见2.8。 最简的DFA为：

a

同理可求出(a)(b)正规式对应的最简DFA亦是如此，故(a)(b)(c)等价。

2.15 修改算法2.4,使之尽可能少使用ε转换，并保持所产生的NFA只有一个接收状态。

Answer:

算法2.4 改进

(3)(a)

N(s)N(t)开始状态合并作为N(s|t)的开始状态

N(s)N(t)接受状态合并作为N(s|t)的接受状态 (3)(c)

N(s) 开始状态与接受状态合并成一个状态j。

　　　　　　　注意：必须保留一个ｉ和ｆ，否则可能在算法递归产生　　　　　　　　　　　　　ＮＦＡ过程中会出问题

编译原理的课后答案

第三章

3.2 考虑文法 SaSbS | bSaS |ε

（a） 为句子abab构造两个不同的最左推导，以此说明该文法是二义的。 （b） 为abab构造对应的最右推导。 （c） 为abab构造对应的分析树。 （d） 这个文法产生的语言是什么？ Answer:

(a)

S lm aSbS S lm aSbS lm abS lm abSaSbS lm abaSbS lm abaSbS lm ababS lm ababS

1 2 lm abab ---------○ lm abab----------○

可知，对于句子abab存在两个不同的最左推导，所以该文法是二义的

(b)

S rm aSbS rm aSb rm abSaSb rm abSab

3 rm abab----------○

S rm aSbS rm aSbaSbS rm aSbaSb rm aSbab

4 rm abab------------○

1○4对应的分析树： ○2○3对应的分析树： (c) ○

(d) 该文法产生a、b个数相等的ab串（含空串）

编译原理的课后答案

3.4 文法

‘|’R | RR | R* | (R) | a | b

产生字母表{a,b}上所有不含ε的正规式。注意，第一条竖线是正规式的符号“或”，而不是文法产生式右部各选择之间的分隔符，另外“*”在这儿是一个普通的终结符。该文法是二义的。

(b) 为该文法写一个等价的非二义的文法。它给予算符*、链接和|的优先级和结合性同2.2节中定义的一致。

(c) 按上面两个文法构造句子 ab|b*a 的分析树。 Answer:

(b) (c)

标准答案见《编译原理习题精选》P17

原文法的分析树： //文法二义 ，存在多个分析树 R

RR|

a|R RR

b

R*

Ra

a

bR

*

a

b

b

无二义文法的分析树：

EETTFb|TTa

编译原理的课后答案

3.6 为字母表{a,b}上的下列每个语言设计一个文法，其中哪些语言是正规的？ (a) 每个a后面至少有一个b跟随的所有串 (b) a和b的个数相等的所有串

Answer:

ε

该语言是正规，对应的正规式是 (ab|b)* (b) 解法一：

ε

解法二:

ε 解法三:

该文法不是正规的。

3.8 （a）消除习题3.1文法的左递归。 (b) 为(a)的文法构造预测分析器。

Answer:

ε

(b) 上述文法的预测分析器为：

procedure match(t:token); begin

if lookahead = t then

lookahead := nexttoken() else error() end;

procedure s; begin

if lookahead = ‘(’ then begin

match(‘(’); L(); match(‘)’) end

else if lookahead = ‘a’ then match(‘a’) else error() end;

ε

编译原理的课后答案

procedure L; begin

S();L1() end;

procedure L1; begin

if lookahead = ‘,’ then begin

match(‘,’); S(); L1() end

else match(‘’) end;

———————————————————————————————————————————

The End 2004-3-7