2024年4月15日发(作者：)

福州大学软件学院2007～2008学年第一学期

《编译原理》课程 期末考试（A卷）

参考答案与评分标准

一、 单项选择题（每小题1分，共10分）

1、D 2、B 3、A 4、A 5、B 6、A 7、D 8、 D 9、A 10、D

二、 填空分析题（每个空格1分，共10分）

1、可规约符号串，左部

2、从左到右进行分析，采用最右推导的逆过程即最左归约，不向前看输入字符

3、移进-规约，规约-规约

4、栈式，堆式

5、活动记录

三、 综合题（共80分）

1、设

M=({x,y},{a,b},f,x,{y}}

为一非确定的有限自动机，其中

f

定义如下：

f

(

x,a

)

=

{

x,y

}

f(x,b)={y}

f(y,a)=

φ

f(y,b)={x,y}

试构造相应的确定有限自动机

M'

并最小化。

(16

分

)

解答：

(1)

先画出

NFA M

相应的状态图：

(4

分

)

a a

b

b

XY

b

(2)

用子集法构造状态转换矩阵：

(3

分

)

I Ia Ib

0 {x} 2 {x,y} 1 {y}

1 {y} 2 {x,y}

2 {x,y} 2 {x,y} 2 {x,y}

(3)

得到

M'=({0,1,2}, {a,b}, f, 0, {1,2})

，其状态转换图如下：

(4

分

)

a

a,b

2

0

b b

1

b

第 1 页 共 5 页

(4)

最小化：首先，将

M'

的状态分成终态组

{1,2}

和非终态组

{0}

；考察

{1,2}

。由于

{1,2}

a

={1,2}

b

={2}

，所以不能再划分了。

(5

分

)

a

0

b

a,b

1

=

=

2

、有如下文法，给出每个产生式的

Predict

集。

=

P

Æ

begin S end

S

Æ

id := E ; S |

λ

E

Æ

n | id

（

8

分）

解答：

Follow( S ) ={ end } (2

分

)

Predict( P

Æ

begin S end ) = { begin } (1

分

)

Predict( S

Æ

id := E ; S ) = { id } (1

分

)

Predict ( S

Æ

λ

) = { end } (2

分

)

Predict ( E

Æ

n ) = { n } (1

分

)

Predict ( E

Æ

id )= { id } (1

分

)

3

、下面是产生字母表Σ

= { 0, 1, 2}

上数字串的一个文法：

→

D S D | 2 S

→

0 | 1

D

写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和

从右向左读都一样时，称它为回文数）。请用

print

函数打印出

true or false

。

(12

分

)

解答：

S

′

→

S print()

S

→

D1 S1 D2 = ( = ) and

2 true S

→

0 0

D

→

1 1 D

→

4

、设有文法

G

：

→

A a | b A c | d c | b d a S

→

d

A

(1)

画出文法的

LR(0)

状态机，按构造

SLR(1)

分析表的算法构造文法

G

的

SLR(1)

分析

表。（

SLR

分析表请填写在下一页表格中）

(2)

文法

G

是

SLR(1)

文法吗？为什么？

（

14

分）

解答：

(1)

构造文法的识别规范句型活前缀的

DFA

如下图所示：

(8

分

)

第 2 页 共 5 页