編譯原理樣題5有答案

編澤原理試題

計算機(jī)W羊院_一級班學(xué)?3_姓名—

踵號三E9五六七八九十總分

滿分

得分

-選擇題

(11.詞法分析器的輸入是O

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

[12.兩個有窮自動機(jī)等價是指它們的o

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

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

[】3.文法G：S-xSxly所識別的語言是o

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

[14.設(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都不一定成立

[15.若狀態(tài)k含有項(xiàng)目“Ara.”,且僅當(dāng)輸入符號aWFOLLOW(A)時，才用規(guī)則“A-

a”歸約的語法分析方法是o

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

C.LRU)分析法D.SLR(l)分析法

二判斷題

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

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

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

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

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

三填空題

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

2、在LR(0)分析法中，若a,肥V*且aw吟則稱“Sfa.A”為項(xiàng)目，稱“S

fa?ap”為項(xiàng)目。

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

的。

四寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。

五已知文法G(S)：

Sia|(T)

T—T,S|S

(1)給出句子(a,(a,a))的最左推導(dǎo)并畫出語法樹；

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

六把語句

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

elsebegin

x：=x+2

y：=y+3

end；

翻譯成四元式序列。

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

S->S4-aFjaF|+aF

F—>*aF|*a

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

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

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

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

programmain;

vara,b:integer;

procedurep(x,y,z:integer);

begin

y:=y+l;

z:=z+x

end;

begin

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

end.

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

(1)傳名；

(2)傳地址。

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

S-?Sab|bR

R-?S|a

+文法ST(L)|a

L今L,S|S

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

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

十一.對PL/0語言擴(kuò)充單詞：

+=++

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

和PLUSPLUS)的詞法分析算法：

if(CH==,+,){

?____________________________；

if(?){

SYM=PLUSBECOME;GetCh();

}elseif(CH=='+1){

}else

④

答案

一選擇題

b,C,D,D,C

二判斷題

,yx'vx'v

三填空題

源程序單詞符號

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

句柄最左素短語

四.解：文法G(S)：

S->AB|B|AO

A-tAD|C

B一2|4|6|8

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

D-*O|C

五

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

醺左推42分)

S)?CS>S>

a9S?S))

-><aS,S>)-><aa,S)>

*t><<b>(ft/AJ)

a

(T,S),a

(T,S)

T,S

直接短語：（1分）T,S

句柄：(1分)T,S

六解：(1)(j>0,x,0,3)

(2)(j?—?一,8)

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

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

<5)(+,x,y,Tl)

(6)(：=,Tl,z)

(7)(j,—>一,12)

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

(9)(：=,T2,x)

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

(11)(：=,T3,y)

(12)

七.解：

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

S->aFS'|+aFS'

S—+aFS'|￡

F->*aFr

F—F|￡

(2)

HRST(S)={a,十}FOLLOW(S)={#}

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

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

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

(3)

a#

s"+aFS'

s，

V卜*aFy

I',FT'

八

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

(0)S9S(1)SBSab

(2)S今bR(3)R今S

(4)R->a

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

10:STS?13:S-?Sa?b

S今?Sab14:SbR?

S->?bRI5:R->S-

S->S,ab

11:s'->s?16:Ra?

S->S?ab

12:Sb?R17:S->Sab?

R?S

R9?a

ST,Sab

Sf-bR

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

FOLLOW(S)=FOLLOW?:{a,$}

構(gòu)造的SLR分析表如下：

actiongoto

狀態(tài)

ab$SR

0S21

1S3acc

2S6S254

觀察左表，對狀態(tài)5,可

3S7

歸納又可移進(jìn)，即存在為重

4r2r2

定義的入口。

5r3/S3r3

所以，該文法不是

6r4r4

SLR⑴文法。

7rlrl

+.(a)S(L,S)f(L,(L))>>(L,(L,S))f(L,(L,(L)))-?(L,(L,(L,S)))

今(L,(L,(L,a)))->(L,(L,(S,a)))-?(L,(L,(a,a)))今(L,(S,(a,a)))

■>(L,?L),(a,a)))“(L,—,(a,a)))-?(L,((L,a),(a,a)))->(L,(⑤a),(a,a)))

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

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

(b)

步驟棧輸入動作

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

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

3$(a,((a,a),(a,a)))$歸約,S9a

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

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

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

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

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

9$(L,((a,a),(a,a)))$歸約，STa

IU$(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)))$歸約，L9S

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

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

20$(L,(L,(a,a)))$