編譯原理期末考試試卷(C卷)

編譯原理期末考試試卷（C卷）

編譯原理期末考試試卷（c卷）

?、單項選擇題（每小題2分，共30分）

1、編譯程序是對程序進(jìn)行翻譯。

A.自然語言B.匯編語言

C.高級語言D.機(jī)器語言

2、描述語言L={ambn

B.S-AB

A-*a

B一b

A.S-ABA-Aa|aB-Bb|b

faSb|abC.SD.S-aSb|e

3、設(shè)有文法G=(,{S,B},S,{S-*bB,B-bS|e}),下列哪個符號串不是該文法

的句子。

A.bB.bbC.bbbD.bbbbb

4、下圖DFA所識別的語言為.?

A.含有偶數(shù)個0

偶數(shù)個1的二進(jìn)制串

B.含有偶數(shù)個0奇數(shù)個1的二進(jìn)制串

C.含有奇數(shù)個0偶數(shù)個1的二進(jìn)制串

D.含有奇數(shù)個0奇數(shù)個1的二進(jìn)制串

5、下述正規(guī)式等價的是。

A.(a|b)與(ab)B.(ab)與abC.(a|b)與(ab)D.(a|b)與a|b

6、設(shè)有一個LR(1)項目集I={Xf.bB,aB-.,a}則該項目集

A.不含沖突項目B.含有移進(jìn)-歸約沖突

C.含有歸約-歸約沖突D.含有移進(jìn)-待約沖突

7、LR語法分析棧中存放的狀態(tài)是識別文法規(guī)范句型__________的DFA狀態(tài)。

A.句柄B.前綴C.活前綴D.項目

8、有文法如S-*rD

1************DfD,i|i

貝FIRSTVT(D)=。

A.{i}B.{i,}C.{ir}D.{ir,}

9、有文法如S-rD

D-D,ii

則i和，的優(yōu)先關(guān)系是。

A.沒有優(yōu)先關(guān)系B.等于C.低于D.高于

10、算符優(yōu)先分析法從左到右掃描輸入串，采用移進(jìn)-歸約的方式，當(dāng)棧頂出現(xiàn)

___________時進(jìn)行歸約。

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

11、局部優(yōu)化是局限于一個范圍內(nèi)的一種優(yōu)化。

A.程序B.函數(shù)C.基本塊D.循環(huán)

12、在編譯中，動態(tài)存儲分配的含義是。

A.在運(yùn)行階段對源程序中的量進(jìn)行存儲分配

B.在編譯階段對源程序中的量進(jìn)行存儲分配

C.在說明階段對源程序中的量進(jìn)行存儲分配

D.以上都不正確

13、以下說法正確的是.一

A.對任何一個編譯程序來說，產(chǎn)生中間代碼不是不可缺少的一部分。

B.在屬性文法中，文法的終結(jié)符只有綜合屬性，不存在繼承屬性。

C.自下而上語法制導(dǎo)翻譯中語法分析棧與語義分析棧必需同步操作。

D.以上都正確

14、后綴式abcd+*的中綴表達(dá)式是。

A.ab*(c+d)B,a(b*c+d)

C.a(b*(c+d))D.a*(b+c)d

15、有翻譯模式如下：

DfintL{print(L.s);}

L-id{L.s=l;}

LfLI,id{L.s=LI.s+1;}

采用移進(jìn)歸約的分析方法，當(dāng)分析器的輸入為inta,b.c時，輸出的結(jié)果是。

A.4B.3C.2D.12

三、應(yīng)用題(1、4、5每題10分，2、3每題15分，共60分)

2、有文法如下：

S-TL

Tfint|float

L-*idR

Rf,idR|e

(1).計算文法的每個非終結(jié)符的FIRST和FOLLOW集合：

(1)(8分)FIRST(S)={int,float}FOLLOW(S)={#}

FIRST(T)={int,float}FOLLOW(T)={id}

FIRST(L)={id}FOLLOW(L)={#}

FIRST(R)={,e}FOLLOW(R)={#}

4、有定義算術(shù)表達(dá)式的文法如下：

E-E+T〔E-T|T

T-T*FT/F|F

F-pF|P

P-(E)i

構(gòu)造句型E-T*PF+i的語法樹；并指出該句型的所有短語、直接短語、素短語、句

柄。

4、句型ET*PF+i的語法樹：(5分)

短語：E-T*PF+i、E-T*PF、T*PF、PF、i

直接短語：PF、i

素短語：PF^i

句柄：PF

12345678910111213

cABDAACBI)BCAD

3

編譯原理期末考試試卷(B卷)

一、簡述編譯程序的工作過程。(10)

編譯程序的工作過程，是指從輸入源程序開始到輸出目標(biāo)程序為止的

整個過程，是非常復(fù)雜的，就其過程而言，一般可以劃分為五個工作階段：①詞法分

析，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的單詞；②語法分析，根據(jù)語

言的語法規(guī)則，把單詞符號串分解成各類語法單位；③語義分析與中間代碼產(chǎn)生，即對各

類語法單位，分析其漢一并進(jìn)行初步翻譯；④代碼優(yōu)化，以期產(chǎn)生更高效的代碼；⑤目標(biāo)

代碼生成，把中間代碼變換成特定機(jī)器上的低級語言指令形式。

二、給出下面的正規(guī)表達(dá)式(15)(1)以01結(jié)尾的二進(jìn)制數(shù)串；(2)能被5整

除的十進(jìn)制整數(shù)；

(3)包含偶數(shù)個1或偶數(shù)個0的二進(jìn)制數(shù)串。

(1)(0|1)*01

(2)digit=0|1|2|3|4|5|67|8|9

digit*(05)(3)((0*10*1)*0*)|((1*01*0)*1*)三、對下面的文法G：

S-aIb(T)T-T,S|S

(1)消去文法的左遞歸，得到等價的文法G2；

(2)判斷文法G2是否LL(1)文法，如果是，給出其預(yù)測分析表。(15)

G2：

S-ab(T)

T-ST'VST'|e四、對下面的文法G：

ab()

sS—aS—bS—(T)

TT-ST'T—ST，T-ST,

rT'一，S

S-AB4

A-AOO|0B-Bll|1

(1)消去文法的左遞歸，得到等價的文法G2；

(2)判斷文法G2是否LL(1)文法，如果是，給出其預(yù)測分析表。(15)

G'：S-ABA-OA,

A'fOOA'|eBfIB'

B'f11B'|e

文法G'[S]是LL(1)文法。

01#

sS-AB

AA-OA'

A'A'"*00A'A'

BBTB'

B'B'f11B'B'F

五、設(shè)有文法G[A]：

AfBCc|gDB

FIRSTFOLLOW

AA,b,c,d,g

BbA,c,d

CA,c,dC,d,g

DDA,b,c,g

EC,g

B-*bCDE|eC-*DaBcaD-*dDeE-gAf|c

(1)計算該文法的每一個非終結(jié)符的FIRST集和FOLLOW集；(2)(2)是LL(1)文

法。

5

編譯原理期末考試試卷(D卷)

三、應(yīng)用題(1、4、5每題10分，2、3每題15分，共60分)

1、為正規(guī)式(a|b)a(a|b)構(gòu)造等價且狀態(tài)最少的確定有限自動機(jī)。

(要求給出主要步驟)

*

2、有文法如下：

SfBAAfBSd

B-aA|bS|c

(1).計算文法的每個非終結(jié)符的FIRST和FOLLOW集合；(2).判斷文法是否LL(1)

文法，如果是，給出其預(yù)測分析表，否則說明理由。

4、有文法如下：

T-T*FFF-PFPP-(T)|i

證明T*iP是該文法的一個句型，但不是規(guī)范句型；

指出T*iP的所有短語、直接短語、素短語、句柄。

三、應(yīng)用題(1、4、5每題10分，2、3每題15分，共60分)

1、（a|b）*a（a|b）狀態(tài)最少的DFA。

a

NFA如圖（5分）：c=

（也可是其它等價的FA）

Ilalb

1[AJ{A}

用子集法得到的狀態(tài)轉(zhuǎn)換矩陣:{A,B?

2{A,B){A,B,C}{A,C}

3{A,B,C){A,B,C}{A,C}

確定化（3分）后的DFA如4{A,C}{A,B}{A}

圖，已是狀態(tài)最少的。如不說

明是最簡的扣1分。

化簡（2分）

注：初態(tài)或終態(tài)錯扣1分

6

2、(1)(6分)FIRST(S)={a,b,c}FOLLOW(S)={#,a,b,c,d}

FIRST(A)={a,b,c,d}FOLLOW(A)={#,a,b,c,d}

FIRST(B)={a,b,c}FOLLOW(B)={a,b,c,d}

（2）因為文法不含左遞歸，關(guān)于A的兩個規(guī)則的SELECT集不相交，關(guān)于B的3個規(guī)則

的SELECT集兩兩不相交，所以文法是LL（1）文法（2分）。

abc(i#

sSBASfBAS—BA

AA-BSA-BSA-BSAfd

BBfaABfbSBc

4、對于符號串T*iP存在如下推導(dǎo)：(或畫一顆語法樹證明是句型)

TT*FT*PFT*PPT*iP

所以T*iP是該文法的一個句型，但不存在一個規(guī)范推導(dǎo)能推導(dǎo)出該句型，所以不是

規(guī)范句型。(5分)

短語：T*iP、iP、i、p

直接短語：i、p

素短語：i

句柄：i

2.考慮文法G[S]:

S-(T)?a+S|a

T-T,SS

消除文法的左遞歸及提取公共左因子。

解：消除文法G[S]的左遞歸：

S-(T)|a+S|a

TTT，

丁-*.ST,Ie

提取公共左因子：

Sf(T)|aSz

S'f+S|

T-ST'

T;-.ST*e7

24.已知文法G[S]

S->S*aF|aF|*aF

Ff+aF|+a

消除文法左遞歸和提公共左因子。

答：消除左遞歸

S-aFS'*aFS'

S'f*aFS，|￡

Ff+aF|+a

提公共左因子,文法G'(S)

S-aFS'*aFS'

S'-*aFS，|e

F-+aF'

F'-F|e

1、設(shè)文法G(S):

S-a(T)

T-T,S|S

⑴消除左遞歸；

⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合;

⑶構(gòu)造預(yù)測分析表

(1)消除左遞，文法變?yōu)镚，[S]：

S--|a(T)'

T-ST,|S

r-.ST)|e

此文法無左公共左因子。

10.設(shè)文法G(S):

S-(T)|aS|a

TT,S|S

⑴消除左遞歸和提公共左因子；

⑵構(gòu)造相應(yīng)的FIRST和FOLLOW集合；

⑶構(gòu)造預(yù)測分析表。

.(1)Sf(L)|aS，

S，fS|￡

LfSL'

ffSL，|e

(2)FIRST(S)={a,(}FIRST(S*)={a,(,e}FIRST(L)={a,(}FIRST(L')={,,e}

FOLLOW(S)={,,),#}FOLLOW(S*)={,,),#}FOLLOW(L)={)}FOLLOW(f)={)}

(3)8

()a#

sS-(L)S-*aS'

s，S'-SS'-￡S'-SS'-￡

LL-SL'L-*SLL'~,SL'

E一￡

s

T)

-----?

T,S

I

s(T)

I小

aI,S

II

Sa

I

a

1.已知文法G(S)：

S—>a(T)T—>T,S|S

①給出句子((a,a),a)的最左推導(dǎo)并畫出語法樹；②給出句型(T,a,(T))所有的短語、直

接短語、素短語、最左素短語、句柄和活前綴。

解：(1)最左推導(dǎo)：S(T)(T,S)(S,S)

(a,S)(a,(T))(a,(T,S))(a,(S.S))(a,(a