《編譯原理》軟件工程2005級(jí)期終考卷

學(xué)號(hào)：姓名：

說(shuō)明：1.本考卷中大寫(xiě)字母WVN,其他符號(hào)WVT：2、試卷中一、二兩題請(qǐng)作在考卷上

一、概念題（15分）

1、編譯過(guò)程一般分為幾個(gè)階段？各階段的輸入輸出分別為什么？

2、對(duì)下列狀態(tài)轉(zhuǎn)換圖，寫(xiě)出狀態(tài)0的處理過(guò)程:

其中：狀態(tài)2的過(guò)程為pr℃2.

3、文法G為：

SfaAB

Afa

則判斷G為L(zhǎng)L（1）文法的條件是：

二、判斷題（10分。注：每答對(duì)一題得+2分；答錯(cuò)一題得.2分；不答者得0分）

1、設(shè)￡為{a,b},則a,ba,{E},。都是￡上的正規(guī)式。（）

2、對(duì)于上下文無(wú)關(guān)文法G[S],若S=>aAB=a伊/則A./一定是一條產(chǎn)生式規(guī)則，

其中（VTVVN）*（）

3、對(duì)于逆波蘭后綴式，無(wú)論從哪頭開(kāi)始分析均可得到唯一正確的分解。（）

4、LR（0）分析法是一種規(guī)范歸約法。（）

5、算符優(yōu)先分析法只能用來(lái)分析算符優(yōu)先文法。（）

三、（10分）設(shè)文法G3為：S-AaBc

AfAa|a

Bfb

求句型AaBc的最左素語(yǔ)。

四、(20分)設(shè)文法G［S］為

S^aAcB問(wèn)：1、該文法是否為算符文法，為什么？

A^Ab|b2、構(gòu)造算符優(yōu)先關(guān)系表。

B-d3、該文法是否可改造為L(zhǎng)L(1)文法，為什么？

五、(本題20分)設(shè)文法G為：E^eAfleBg

A->aA|a

B^Bbja

對(duì)于輸入串eaaaf,采用LR(0)、LL(1).SLR(1)等方法中合適的一種進(jìn)行分析。

六、(25分)有作控制用的布爾表達(dá)式文法G［E］及其語(yǔ)義動(dòng)作如下:

1、構(gòu)造SLR(1)分析表(若不是SLR(D)的，則說(shuō)明理由)

2、分析布爾式aVb<c的四元式生成過(guò)程，并畫(huà)出最后的真假鏈表。

3、給出語(yǔ)句IFaVb<cTHENI:=m*nELSEI:=m+n的完整四元式序列。

文法G[E]：

⑴E-i⑴姆⑵{E.TC:=NXQ;E.FC=NXQ+1;

GEN(J<,ENTRY(i(，)),ENTRY(i⑵)，0);GEN(J,0)}

⑵EfAE⑴{E.FC:=E(，).FC;E.FC::MERGE(A.TC,E(，).TC)}

(3)A->BV{BACKPATCH(B.FC,NXQ);A.TC:=B.TC)

(4)B—i{B.TC:=NXQ;B.FC:=NXQ+1;

GEN(Jnz,ENTRY(i),_,0);GEN(J,0)}

軟件0501班編譯原理考試答案及評(píng)分細(xì)則

一：1、(5分)

源程序

_____________I______________

詞法分析

I單詞符號(hào)

語(yǔ)法分析

］語(yǔ)法單位

語(yǔ)義分析與中間代碼產(chǎn)生

］中間代碼

優(yōu)化

］中間代碼

目標(biāo)代碼生成

目標(biāo)代碼

2、(5分)

Proc0:

ge(char();

CASEcharOF

‘a(chǎn)'/b',???,'z':

，A'B，,???,'Z':proc1

elseerror

ENDCASE

3、(5分)

條件：

(1)文法G不含左遞歸；

(2)對(duì)于每個(gè)非終結(jié)符,First(a)First(P)>First(丫)兩兩不相交；

(3)對(duì)于每個(gè)非終結(jié)符，不含能推出￡的產(chǎn)生式，故不考慮非終結(jié)符的

First集和Follow集相交的情況。

二、(每小題2分)

1、X；2、X；3、V；4、V；5、Vo

三、(10分)

方法一：

句型AaBc的語(yǔ)法樹(shù)為:

故AaBc即為所求最左素短語(yǔ)。

方法二：

FlRSTVT(S)={a},LASTVT(S)={c},

FIRSTVT(A)={a},LASTVT(A)={a),

FIRSTVT(B)=,LASTVT(B)=o

則有:

abc#

a><二>

b>>

c>

#<<<=

對(duì)于#AaBc#,#<a,a=c,c>#,則最左素短語(yǔ)為AaBc。

四、(20分)

1、該文法是算符文法。因?yàn)槠淙我划a(chǎn)生式的右部都不含相繼(并列)的非

終結(jié)符，即不含如下形式…QR…的產(chǎn)生式右部。(4分)

2、FIRST(S)={a},LAST(S)={c},

FIRST(A)=,LAST(A)=,

FIRST(B)=mueeico,LAST(B)=kgmsycmo(3分)

構(gòu)造算符優(yōu)先關(guān)系表如下：(5分)

abcd

a<=>

b>>>

c<>

d>

#<<<=

3、該文法可以改造為L(zhǎng)L(1)文法。(8分)

原因：

①消除左遞歸：S-aAcB

AfbA'

A'-*bA,|￡

B-d；

②FIRST(A)={a},FOLLOW(A)={c),

FIRST(A,)={b,e},FOLLOW(Ay)={c},

FIRST(B)=qiawmay,FOLLOW(B)={#},

FIRST(S)={a),FOLLOW(S)={#},

對(duì)于每個(gè)非終結(jié)符的各個(gè)產(chǎn)生式的FIRST集兩兩不相交;

③對(duì)于A',FIRST(A)AFOLLOW(A)=①。

綜上所述，原文法可以改造成LL(1)文法。

五、(20分)

原文法不是LL(1)文法，故不能直接使用LL(1)分析法進(jìn)行分析。

步驟如下：

1、拓廣文法：①E，-E②E-eAf

③EfeBg④AfaA

⑤Afa⑥BfBb

⑦B-a(2分)

2、項(xiàng)目集規(guī)范族：

(6分)

由此項(xiàng)目集規(guī)范族可判斷，原文法非LR(0)文法，故不能直接使用LR(0)

分析法進(jìn)行分析。因此，使用SLR(1)分析法分析原文法。

3、構(gòu)造SLR(1)分析表如下：

FOLLOW(A)={f};FOLLOW(B)={b,g}；FOLLOW(E)={嘰

ACTIONGOTO

狀態(tài)abefg#ABE

0S21

1acc

2S435

3S6

4S8r7r5r77

5S10S9

6r2

7r4

8S8r57

9r3

10r6r6

(6分)

4、分析輸入串eaaaf如下：

步驟狀態(tài)符號(hào)輸入串動(dòng)作

10#eaaaf#預(yù)備

202Ueaaaf#移進(jìn)

3024#eaaaf#移進(jìn)

40248#eaaaf#移進(jìn)

502488#eaaaf#移進(jìn)

602487#eaaAf#歸約

70247#eaAf#歸約

8023#aAf#歸約

90236#aAf#移進(jìn)

1001#E#歸約

11acc接受

(6分)

六、（25分）

1、步驟：

（1）拓廣文法：①E'-E②E-i⑴</

③EfAE⑴④AfBV

⑤B-i（2分）

（2）項(xiàng)目集規(guī)范族：

8______

i⑴<i.⑵

（6分）

(3)SLR(1)分析表如下:

FOLLOW(E)={#};FOLLOW；A)={i}:FOLLOW(B)={V)0

ACTIONGOTO

狀態(tài)i<VnEAB

0S2134

1acc

2S6r4

3S2734

4S5

5r3

6S8

7r2

8rl

（6分）

2、分析輸入串a(chǎn)Vb〈c如下:

步驟狀態(tài)棧符號(hào)輸入串動(dòng)作四元式

10aVb<c#預(yù)備

202Vb<c#移進(jìn)

B.TC=1,B.FC=2;

Gen(Jnz,a,0);

304#BVb<c#歸約

Gen(J,3);

4045#BVb<c#移進(jìn)

A.TC=B.TC=1;

503#Ab<c#歸約BackPatch(2,3);

6032#Ai<c#移進(jìn)

70326#Ai<C#移進(jìn)

803268#Ai<i#移進(jìn)