期末考試試卷A卷

天津理工大學考試試卷

2009?2010學年度第二學期

《編譯原理》期末考試試卷

課程代碼：0660116試卷編號:1-A命題日期：2010年6月15日

答題時限：120分鐘考試形式：閉卷筆試

得分統(tǒng)計表:

號

—'二三四

一、單項選擇題(請從4個備選答案中選擇最適合的一項，每小題2分，共20

分)

得分

注意：須將本題答案寫在下面的表格中，寫在其它地方無效

12345678910

DCBDDBCBDC

1.編譯程序是對()

A.匯編程序的翻譯B.高級語言程序的解釋執(zhí)行

C.機器語言的執(zhí)行D.高級語言的翻譯

2.詞法分析器的輸出結(jié)果是()

A.單詞的種別編碼B.單詞在符號表中的位置

C.單詞的種別編碼和自身值D.單詞自身值

3.在規(guī)范規(guī)約中，用()來刻畫可規(guī)約串。

A.直接短語B.句柄C.最左素短語D.素短語

**

4.與正規(guī)式(a|b)(c|d)等價的正規(guī)式是()

****

A.a(c|d)|b(c|d)B.a(c|d)|b(c|d)

****

C.a(c|d)|b(c|d)D.(a|b)c|(a|b)d

5.若項目集IK含有Afa?,則在狀態(tài)K時，僅當面臨輸入符號awFOLLOW(A)時，才采取

ATa?動作的一定是()

A.LALR文法B.LR(0)文法C.LR(1)文法D.SLR⑴文法

6.四元式之間的聯(lián)系是通過()實現(xiàn)的。

A.指示器B.臨時變量C.符號表D.程序變量

7.文法G：S->xSx|y所識別的語言是（）

***

A.xyxB.（xyx）C.xnyxn（nNO）D.xyx

8.有一語法制導翻譯如下所示：

SfbAb{print"1”}

A->（B{print"2”}

Afa{print“3”，

BfAa）{print"4”j

若輸入序列為b（（（aa）a）a）b,且采用自下而上的分析方法，則輸出序列為（）

A.32224441B.34242421C.12424243D.34442212

9.關于必經(jīng)結(jié)點的二元關系，下列敘述不正確的是（）

A.滿足自反性B.滿足傳遞性C.滿足反對稱型D.滿足對稱性

10.錯誤的局部化是指（）。

A.把錯誤理解成局部的錯誤B.對錯誤在局部范圍內(nèi)進行糾正

C.當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去

D.當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

二、判斷題（每小題1分，共5分）

得分

1.文法G的一個句子對應于多個推導，則G是二義性的。（X）

2.動態(tài)的存儲分配是指在運行階段為源程序中的數(shù)據(jù)對象分配存儲單元。（J）

3.算符優(yōu)先文法采用“移進一規(guī)約”技術，其規(guī)約過程是規(guī)范的。（X）

4.刪除歸納變量是在強度削弱以后進行。（V）

5.在目標代碼生成階段，符號表用于目標代碼生成。（X）

三、簡答題（每小題5分，共15分）

得分

*

1.構造正規(guī)式（0I1）00相應的正規(guī)式并化簡。（共5分）

（1）根據(jù)正規(guī)式，畫出相應的NFAM（2分）

0

（2）用子集法將NFA確定化（2分）

IIoII

{x,l,2}{1,2,31HZ

[1,2,3}{1,2,3,41{1,2}

[1,2}[1,2,3}{1,2}

{1,2,3,4){1,2,3,4}{1,2}

將所有子集重命名，得到轉(zhuǎn)換矩陣:

S01

012

132

212

332

（3）化簡，并畫出DFAM（1分）

劃分為狀態(tài)：{0,2}{1}{3}將這三個狀態(tài)命名為0,1,2三個狀態(tài)

S01

010

120

220

2.設文法G[S]:（共5分）

S-S+aT|aT|+aT

T―**aT|*a

（1）寫出句型aT+a*a*a的最右推導并畫出語法樹（2分）

SnS+aTnS+a*aTnS+a*a*anaT+a*a*a

（2）寫出該句型中所有的短語、直接短語、句柄和最左素短語。（3分）

短語：aT、*a*a、*a、aT+a*a*a

直接短語：aT、*a

句柄：aT

最左素短語：aT

3.將下列語句翻譯為逆波蘭表示，三元式、間接三元式和四元式表示：（共5分）

a=（b+c）*e+（b+c）/f

（1）逆波蘭表示（1分）

abc+e*bc+f/+=

⑵①

②什b,

*(①C⑻)

③,

④什b,c)

@②,,f,)

⑤(/什,

(4

⑥⑤

("=a,漢

刀

、

可

—

(3)①

②湍

③

④

承

⑤

間-

(4)①四元式(2分)

②(+,b,c,Tl)

③(*,Tl,e,T2)

④(+,b,c,T3)

⑤(/,T3,f,T4)

⑥(+,T2,T4,T5)

(=,T5,-,a)

四、綜合題（共60分）

得分

1.已知文法G(S)：(共15分)

S->*A

AT0A1|*

⑴求文法G的各非終結(jié)符號的FIRSTVT和LASTVT集合。(5分)

FIRSTVT(S)={*}LASTVT(S)={1,*}

FIRSTVT(A)={0,*}LASTVT(S)={1,*}

（2）構造文法G的優(yōu)先關系矩陣，并判斷該文法是否是算符優(yōu)先文法。（5分）

*01

*<<>

0<<=

1>

文法G中的任何終結(jié)符對至多只存在利優(yōu)先關系，所以文法G是一個算符優(yōu)先文法。

（3）分析句子*0*1,并寫出分析過程。（5分）

步驟符號棧輸入串輸出

0#*0*1#

1#*0*1#

2#*0*1#

3#*0*1#

4#*0A1#

5#*OA1#

6H*A#

7#S江分析正確

2.已知文法G(S)：(共15分)

SfaS|bS|a

(1)構造該文法的拓廣文法。(1分)

(o)s」s

(1)S-aS

⑵A-bS

(3)A-*a

⑵構造其LR(O)項目集規(guī)范族，并給出識別活前綴的DFA。(7分)

⑶構造其SLR分析表，并判斷該文法是否是SLR(l)文法。(7分)

狀態(tài)h移進一規(guī)約沖突，計算S的Follow集合：Follow(S)={#},可以采用SLR沖突消解法,

得到如下SLR分析表：

ACTIONGOTO

狀態(tài)ab#S

03

S1s2

14

Sis2n

25

Sis2

3acc

4ri

5刈

該文法是SLR(1)文法。

3.設有如下基本塊：(共10分)

T1=A+B

T2=5

M=T2*4

T3=C-D

T4=M+T3

L=T1*T3

T4=A+B

N=T4

AB520CD

（2）假設變量L,M,N在基本塊出口之后是活躍的，給出優(yōu)化后的四元式序列。（5分）

N=A+B

M=20

T3=C-D

L=N*T3

4.以下程序段是最內(nèi)循環(huán)（共13分）

A=0

1=1

LI:B=J+1

C=B+I

A=C+A

if1=100GOTOL2

1=1+1

GOTOLI

L2:

流圖中有一條回邊B3一＞B2,且B2DOMB3,所以，有一個循環(huán){B2,B3},B2是循環(huán)入口

結(jié)點，也是出口結(jié)點。

(2)對循環(huán)優(yōu)化(8分)

1.代碼外提：對于B2中的賦值四元式B=J+1,由于循環(huán)中沒有對J的定值操作，所有對J

的定值都在循環(huán)外，所以，它是循環(huán)中的不變運算，可以進行代碼外提。

2.刪除歸納變量：循環(huán)中I是基本歸納變量，C是與I同族的歸納變量，兩者有如下線性關

系：C=B+L則1=100可以用C=B+100替代，相應的1=1+1可用C=C+1替代，再將新的不變

運算提到循環(huán)外。

B4

5.有一程序如下：

programex;

a:integer;

procedurePP(x:integer);

begin:

x:=5;x:=a+l

end;

begin

a:=2;

PP(a)；

write(a)

end

試用圖表示ex調(diào)用PP(a)前后活動記錄的過程。(共7分)