編譯原理試卷D(含答案)

編譯原理試題

計(jì)算機(jī)學(xué)院級(jí)一班學(xué)號(hào)姓名

題號(hào)三四五0:q七八九十總分

滿(mǎn)分

得分

-選擇題

[]1.詞法分析器的輸入是。

A.符號(hào)串B.源程序C.語(yǔ)法單位D.目標(biāo)程序

[12.兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的o

A.狀態(tài)數(shù)相等B.有向弧數(shù)相等

C.所識(shí)別的語(yǔ)言相等D.狀態(tài)數(shù)和有向弧數(shù)相等

[]3.文法G：S—xSxly所識(shí)別的語(yǔ)言是。

A.xy*xB.(xyx)*C.xx*yxx*D.x*yx?

[】4.設(shè)a,b,c為文法的終結(jié)符，且有優(yōu)先關(guān)系a三b和b三c,則。

A.必有a=cB.必有c三a

C.必有b三aD.選項(xiàng)A、B和C都不一定成立

【]5.若狀態(tài)k含有項(xiàng)目“A-a.”，且僅當(dāng)輸入符號(hào)aWFOLL邠(A)時(shí)，才用規(guī)則“A

-a”歸約的語(yǔ)法分析方法是。

A.LALR分析法B.LR(O)分析法

C.LR(1)分析法D.SLR(1)分析法

二判斷題

1、一個(gè)LL(1)文法一定是無(wú)二義的。

2、逆波蘭法表示的表達(dá)式亦稱(chēng)前綴式。

3、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。

4、同心集的合并有可能產(chǎn)生“移進(jìn)/歸約”沖突。

5、若主程序?yàn)?。層，過(guò)程p層次為匕則p的DISPLAY表中就有k+1個(gè)元素。

三填空題

1、詞法分析的任務(wù)是從中識(shí)別出一個(gè)個(gè)o

2、在LR(O)分析法中，若a,pcV*且ac匕?則稱(chēng)“Sfa.A”為項(xiàng)目，稱(chēng)“S

->a.apn為項(xiàng)目o

3、規(guī)范規(guī)約每次規(guī)約的是句型的。算符優(yōu)先分析法每次規(guī)約的是當(dāng)前句型

的o

四寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。

五已知文法G(S)：

S->a|(T)

JT,S|S

(1)給出句子(a,(a,a))的最左推導(dǎo)并畫(huà)出語(yǔ)法樹(shù)；

(2)給出句型((T,S),a)的短語(yǔ)、直接短語(yǔ)、句柄。

六把語(yǔ)句

ifx>0andy>0thenz：=x+y

elsebegin

x：=x+2

y：=y+3

end；

翻譯成四元式序列。

七設(shè)文法G(S)：

S->S+aF|aF|+aF

F—>*aF|*a

(1)消除左遞歸和左因子；

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

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

八設(shè)有以下程序段

programmain;

vara,b:integer;

procedurep(xzy,z:integer);

begin

y：=y+i;

z:=z+x

end;

begin

a:=2;b:=3;p(a+b,a,a);write(a)

end.

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

(1)傳名；

(2)傳地址。

九下列文法是否為SLR(l)文法？若是，請(qǐng)構(gòu)造相應(yīng)的分析表。若不是，請(qǐng)說(shuō)明理由。

SSab|bR

R-S|a

十文法S~>(L)|a

L->L,S|S

(a)給出句子(a,((a,a),(a,a)))的一個(gè)最右推導(dǎo)；

(b)按照(a)的最右推導(dǎo)，給出移進(jìn)一歸約分析器的工作步驟。

H---對(duì)PL/0語(yǔ)言擴(kuò)充單詞：

+=++

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

和PLUSPLUS)的詞法分析算法：

if(CH==,4-'){

①____________________________；

if(?){

SYM=PLUSBECGME;GetCh();

}elseif(CH=='+*){

}else

?_____________________

}

答案

—選擇題

b,C,D,D,C

二判斷題

A/XA/X"

三填空題

源程序單詞符號(hào)

待約項(xiàng)目移進(jìn)項(xiàng)目

句柄最左素短語(yǔ)

四解:文法G(S)：

S->AB|B|AO

ArAD|C

B一2|4|6|8

C->1|3|5|7|9|B

D-0|C

五

（2）短語(yǔ)：（2分）((T,S),a)

a?tT.St)

,4?.<S.S>|?r<*?<<#<>>

—??(???

??????<>

(T,S),a

（T,S）

T,S

a

直接短語(yǔ)：（1分）T,S

a

句柄：（1分）T,S

六解：（1）（j>0,x,0,3）

(2)(j>—,—,8)

(3)(j>,y,0,5)

(4)(j,—,—?8)

(5)(+,x,y,T1)

(6)(：=,Tl,一,z)

(7)(j,—,—?12)

(8)(+,x,2,T2)

(9)(：=,T2,x)

(10)(+,y,3,T3)

(11)(：=,T3,y)

(12)

七解：

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

S—aFSl+aFS'

SJ+aFS'|￡

F1*aF

F'rF|￡

(2)

FIRST(S)={a?十}FOLLOW(S)={#}

FIRST(50)={+,s}FOLLOW(S')={#}

FIRST(F)={*)FOLLoW(F)=(+,#)

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

(3)

寸

S-?aKS*ST?aFS*

rI

—>rFT'

八

九.該文法的拓廣文法G，為：

(O)S'今S(1)SSab

(2)SfbR(3)R9S

(4)R-?a

其LR(0)項(xiàng)目集規(guī)范族如下：

10:S5->S?13:SSa?b

ST?Sab14:SbR?

Sf?bR15:R今S?

S今S?ab

Il:S?16:Ra?

S今S?ab

12:Sb-R17:SSab?

R->?S

R9?a

ST?Sab

S->?bR

文法G，的識(shí)別活前綴的DFA如下所示：

+.(a)S(k.S)-?(L,(L))■>(L,(L^))f(L,(L,_(L)))今(L,(L,(L^)))

-?(L,(L,(L,a)))-?(L,(L,(S,a)))■?(L,(L,(a,a)))-?(L,⑤(a,a)))

今(L,GL),(a,a)))今(L,((L,S),(a,a)))->(L,((L,a),(a,a)))■>(L,((S,a),(a,a)))

■>(L,(⑧a),(a,a)))->(S,((a,a),(a,a)))》(a,((a,a),(a,a)))

(注：下劃線(xiàn)部分為句柄)

(b)

步驟棧輸入動(dòng)作

1$(a,((a,a),(a,a)))$移進(jìn)

2$(a,((a,a),(a,a)))$移進(jìn)

3$(a,((a,a),(a,a)))$歸約，STa

4$(S,((a,a),(a,a)))$歸約，L9S

5$(L,((a,a),(a,a)))$移進(jìn)

6$(L,((a,a),(a,a)))$移進(jìn)

7$(L,((a,a),(a,a)))$移進(jìn)

8$(L,((a,a),(a,a)))$移進(jìn)

9$(L,((a,a),(a,a)))$歸約，S->a

10$(L,((S，a),(a,a)))$歸約，L^S

11$(L,((L,a),(a,a)))$移進(jìn)

12$(L,((L,a),(a,a)))$移進(jìn)

13$(L,((L,a),(a,a)))$歸約，S->a

14$(L,((L,S),(a,a)))$歸約，L~>L,S

15$(L,((L),(a,a)))$移進(jìn)

16$(L,((L),(a,a)))$歸約，S->(L)

17$(L,(S,(a,a)))$歸約，LTS

18$(L,(L,(a,a)))$移進(jìn)

19$(L,(L,(a,a)))$移進(jìn)

20$(L,(L,(a,a)))$移進(jìn)

21$(L,(L,(a,a)))$歸約，S^a

22$(L,(L,(S,a)))$歸約，L9S

23$(L,(L,(L