編譯原理試題

一選擇題

1、編譯原理各階段工作都涉及（第1章）：

A.詞法分析B.表格管理C.語(yǔ)法分析D.語(yǔ)義分析

2、正則表達(dá)式R1和R2等價(jià)是指（第4章）

A.R1和R2都是定義在一個(gè)字母表上的正則表達(dá)式

B.R1和R2中使用的運(yùn)算符相同

C.R1和R2代表同一正則集

D.R1和R2代表不同正則集

3、在以下的語(yǔ)法分析中，特別適合于表達(dá)式的分析。（第5,6,7章）

A.LR分析

B?LL（1）分析

C.遞歸下降分析

D.算符優(yōu)先分析

4、與（a|b）*（a|b）等價(jià)的正規(guī)式是。（第4章）

A.a*|b*B.（ab）*（a|b）C.（a|b）（a|b）*D.（a|b）*

5、在語(yǔ)法制導(dǎo)翻譯中不采用拉鏈回填技術(shù)的語(yǔ)句是。（第8章）

A.跳轉(zhuǎn)語(yǔ)句B.賦值語(yǔ)句C.條件語(yǔ)句D.循環(huán)語(yǔ)句

6、在屬性文法中，終結(jié)符只具有屬性。（第8章）

A.傳遞B.繼承C.抽象D.綜合

7、過(guò)程的Display表中記錄了。（第10章）

A.過(guò)程的連結(jié)數(shù)據(jù)B.過(guò)程的嵌套層數(shù)

C.過(guò)程的返回地址D.過(guò)程的入口地址

二判斷題

1、最左歸約也稱(chēng)為規(guī)范歸約。（第3章）

2、逆波蘭法表示的表達(dá)式把運(yùn)算對(duì)象放在運(yùn)算符的后面。（第8章）

3、同心集的合并有可能產(chǎn)生“歸約/歸約”沖突。（第7章）

4、DFA可以通過(guò)多條路徑識(shí)別一個(gè)符號(hào)串。（第4章）

5、動(dòng)態(tài)數(shù)組的存儲(chǔ)空間在編譯時(shí)就可完全確定。（第10章）

三填空題

1、詞法分析所依循的是語(yǔ)言的;而中間代碼生成所依循的

是。（第4,8章）

2、在LR（0）分析法中，若a,BwV”且aeVT則稱(chēng)“S->a.A”為待約項(xiàng)

日，稱(chēng)“S-a.ab”為項(xiàng)目。（笫7章）

3、規(guī)范規(guī)約每次規(guī)約的是句型的o（第6章）

4、無(wú)符號(hào)常數(shù)的識(shí)別和計(jì)算該常數(shù)的工作，通常在階段完成的。（第

4章）

四、設(shè)字母表為｛a,b｝的語(yǔ)言L的句子是滿(mǎn)足下述條件的串：每個(gè)a都有b直接跟

在右邊。構(gòu)造該語(yǔ)言的正則式,（第4章）

五、將下圖的NFA確定化為DTA,圖中初態(tài)為X,終態(tài)為Y。（第4章）

六、寫(xiě)一個(gè)2型文法G,使得L(G)={ai+2bi|i>=0}U{aibi+2|i>=0}。(第3章)

七、設(shè)文法G（S）：（第5章）

S-S+aF|aF|+aF

F-*aF|*a

（1）消除左遞歸和左因子；

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

（3）構(gòu)造預(yù)測(cè)分析表。

八、對(duì)文法G[S]:S-aSbIP（第6章）

P-bPcIbQc

Q-?QaIa

請(qǐng)構(gòu)造簡(jiǎn)單優(yōu)先關(guān)系表，該文法是否是簡(jiǎn)單優(yōu)先文法?

九、設(shè)有以下程序段（第10章）

programmain;

varazb:integer;

procedurep(xFyzz:integer);

y:=y*2;

z:=z+x

begin

a:=5;b:=2;p(a*b,a,a);write(a)

end.

對(duì)于下列參數(shù)傳遞方式，分別寫(xiě)出執(zhí)行程序后a的輸出值。

(1)傳值；(2)傳地址；(3)值結(jié)果；(4)傳名。

十、文法G[S]及其LR分析表如下，請(qǐng)給出對(duì)串dada#的分析過(guò)程。(第7章)

G[S]:1)S-VdB2)V-e

3)V-w4)B-a

5)B-Bda6)B…

ACTIONGOTO

狀態(tài)

dea#SBV

0r3S312

1acc

2S4

3r2

4r6S5r66

5r4r4

6S7rl

7S8

8r5r5

十一、試將下述程序段翻譯成三地址形式的中間代碼表示。(第8章)

while(a+b<cORa=b)

while(a<5ANDb<10)

(

a=a+l;

b=b+l；

十二、將下面程序劃分為基本塊，并畫(huà)出其程序流圖。

read(A,B)

F:=l

C：=A*A

D:=B*B

ifC<DgotoLI

E:=A*A

F:=F+1

E:=E+F

write(E)

halt

LI:E:=B*B

F:=F+2

E;=E+F

write(E)

ifE>100gotoL2

halt

L2:F:=F-1

gotoLI

十三、對(duì)PL/0語(yǔ)言擴(kuò)充單詞-=和--：(第2章)

請(qǐng)完成下列識(shí)別單詞和(設(shè)單詞內(nèi)碼分別為MINUS,

MINUSBECOME和MINUSMINUS)的詞法分析算法：

if(CH=='-*){

①；

SYM=MINUSBECOME;

GetChO;

}elseif(CH=='-f){

③

}else

④

}

答案

一選擇題

b,czd,c,b,d,b

二判斷題

yX^XX

填空題

1、文法語(yǔ)義2、待約項(xiàng)目移進(jìn)項(xiàng)目

3、句柄4、詞法

四(blab)*

五

解：用子集法確定化如下表

I工alb狀態(tài)

{X,0,l,3}{0,1,31{2,3,Y}-X

{0,1,3}{0,1,3){2,3,Y}1

{2,3,Y){1,3}{Y}+2

{1/3}0{2,Y}3

{2ZY}{1,3}{Y}+4

{Y}00+Y

確定化后如下圖

六解：文法G(S):

S―>aSb

S―

Sfbb

七解：

(1)(消除左遞歸，提公因左因子)

S-aFS'I+aFS*

S'-+aFS'|￡

F-*aF'

F'-F|￡

(2)

FIRST(S)={a,十)FOLLOW(S)={4)

FIRST(50)={+,￡}FOLLOW(S*)={#}

FIRST(F)={*}FOLLOW(F)=(+,#)

FIRST(F*)={*,s)FOLLOW(+,#)

(3)

4-*#

sSf+aFS，

s，Sj+aFS，S,"

VIfaal

VfF

八Head(S)={azP,b}Head(P)={b}Head(Q)={Qza}

Tail(S)={b,P,c}Tail(P)={c}Tail(Q)={a}

(1)"="關(guān)系：a=SS=bb=PP=cb=QQ=cQ=a

(2)關(guān)系：a<Head(S)b<Head(P)b<HeadiQ)

九(1)5;(2)20；(3)15;(4)3Co

十對(duì)輸入串dada#的分析過(guò)程

步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作

10#dada#用V-E歸約

202#Vdada#移進(jìn)

3024#vdada#移進(jìn)

40245#Vdada#用B-a歸約

50246#VdBda#移進(jìn)

602467