編譯原理樣題3有答案

編譯原理樣題

一選擇題

[]1.型文法也稱為正規(guī)文法。

[A]0[B]1[C]2[D]3

【]2.文法不是LL(1)的。

[A]遞歸[B]右遞歸[C]2型[D]含有公共左因子的

[]3.文法E^E+E|E*E|i的句子i*i+i*i的不同語(yǔ)法分析樹的總數(shù)為。

[A)l[B]3[C]5[D]7

[14.四元式之間的聯(lián)系是通過(guò)實(shí)現(xiàn)。

[A]臨時(shí)變量[B]指示器[C]符號(hào)表[D]程序變量

[15.同心集合并可能會(huì)產(chǎn)生的新沖突為o

[A]二義[B]移進(jìn)/移進(jìn)[C]移進(jìn)/歸約[D]歸約/歸約

(16.代碼優(yōu)化時(shí)所依據(jù)的是o

[A]語(yǔ)法規(guī)則[B]詞法規(guī)則[C]等價(jià)變換規(guī)則[D]語(yǔ)義規(guī)則

[17.表達(dá)式a-(-b)*c的逆波蘭表示為o

[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*(注：?為單目減運(yùn)算符)

[]8.過(guò)程的D工SPLAY表記錄了o

[A]過(guò)程的連接數(shù)據(jù)[B]過(guò)程的嵌套層次

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

二填空題

1.編譯過(guò)程的六個(gè)階段為：詞法分析、、語(yǔ)義分析、代碼優(yōu)化和目標(biāo)

代碼生成。

2.詞法分析階段的任務(wù)式從左到右掃描,從而逐個(gè)識(shí)別。

3.對(duì)于文法G1和G2,若有,則稱文法G：[和G2是等價(jià)的。

4.對(duì)于文法G[E]：E-TIE+TT-F|T*FF-PAF|PP-(E)|i,句型T+T*F+i的句柄

是，最左素短語(yǔ)是o

所謂素短語(yǔ)是指這樣的一個(gè)短語(yǔ)，它至少含有一個(gè)終結(jié)符，并且，除它自身之外不再含任何更小的素短

語(yǔ)。所謂最左素短語(yǔ)是指處于句型最左邊的那個(gè)素短語(yǔ)。如，P*P和i是句型P*P+i的素短語(yǔ)，而P*P

是它的最左素短語(yǔ)。

5.最右推導(dǎo)的逆過(guò)程稱為,也稱為。

6.規(guī)范規(guī)約中的可規(guī)約串是,算符優(yōu)先分析中的可規(guī)約串是。

7.(AVB)A(Cv->DAE)的逆波蘭式是o

8.在屬性文法中文法符號(hào)的兩種屬性分別稱為和o

9.符號(hào)表的每一項(xiàng)是由名字欄和兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表

是的依據(jù)。

10.一個(gè)過(guò)程的D工SPLAY表的內(nèi)容是它的的D工SPLAY表的內(nèi)容力口上。

三有窮自動(dòng)機(jī)M接受字母表2={0,1}上所有滿足下述條件的串：每個(gè)1都有0直接跟在右

邊。構(gòu)造一個(gè)最小的DFAM及和M等價(jià)的正規(guī)式。

四證明正規(guī)式(ab)*a與正規(guī)式a(ba)*等價(jià)(用構(gòu)造他們的最小的DFA方法)。

五寫一個(gè)文法，使其語(yǔ)言是：

L={ln0mlm0nIm,n20}

六對(duì)文法G[S]

SfaSbIP

PfbPc|bQc

QfQa|a

(1)它是否是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表

(2)文法G[S]消除左遞歸、提取左公因子后是否是LL(1)文法？請(qǐng)證實(shí)。

已知文法G為：

(0)s'-*■S

(1)S一aAd

(2)S-bAc

(3)S-aec

(4)s-*bed

(5)A-e

試構(gòu)造它的LR(1)項(xiàng)目集、可歸前綴圖和LR(1)分析表。

八已知源程序如下：

prod:=0;

i:=1;

whileiW20do

begin

prod:=prod+a[i]*b[i];

i:=i+l

end;

試按語(yǔ)法制導(dǎo)翻譯法將源程序翻譯成四元式序列(設(shè)A是數(shù)組a的起始地址，B是數(shù)組b的起

始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié))。

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

procedureP(x,y,z)

begin

Y:=y*3;

Z:=X+z;

end;

begin

a:=5;b:=2;

p(a*b,a,a);

print(a);

end

若參數(shù)傳遞的方法分別為(1)傳值、(2)傳地址、(3)傳名，試問(wèn)結(jié)果分別什么？

十對(duì)以下文法，請(qǐng)寫出關(guān)于括號(hào)嵌套層數(shù)的屬性文法。(為S,L引入屬性h,用來(lái)記錄輸出配

對(duì)的括號(hào)個(gè)數(shù))

文法規(guī)則語(yǔ)義規(guī)則

Sf(T)

TfT,S

T->S

H--對(duì)PL/0語(yǔ)言的while語(yǔ)句while條件BDO語(yǔ)句S的編譯程序,

請(qǐng)?jiān)诳杖碧幪羁眨瓿稍撜Z(yǔ)句的編譯算法：

switch(SYM){

caseWHILESYM:

GetSym();

CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);

GEN(JPC,0,0);

if(SYM==DOSYM)

elseError(18);

STATEMENT(FSYS,LEV,TX);

GEN(JMP,OZCX1);

break;

編譯原理樣題參考答案

—選擇題(12分)

l.D2.D3.B4.A5.D6.C7.B8.B

二填空題(8分)

1.語(yǔ)法分析中間代碼生成6.城最左素短語(yǔ)

2.源程序單詞7.ABVCD-?EAV/\

3.L(G1)=L(G2)(或G1和G2的語(yǔ)言相同)8.繼承屬性綜合屬性(次序可換)

4.TT*F9.信息欄地址分配

5.規(guī)范歸約最左歸約10.直接外層本過(guò)程的SP的地址

三最小的DFAM如下圖所示：

與M等價(jià)的正規(guī)式為：(0|(10))

四正規(guī)式(ab)*a對(duì)應(yīng)的NFA如圖:

正規(guī)式a(ba)，對(duì)應(yīng)的NFA如圖:

這兩個(gè)正規(guī)式最終都可得到最簡(jiǎn)的DFA如圖所示:

所以這兩個(gè)正規(guī)式等價(jià)。

五文法G：S-ISOIA

A-0A1|￡

六1.求出G[S]的FIRSTVT集和LASTVT集:

FIERSTVT(S)={a,b}LASTBVT(S)={b,c}

FIERSTVT(P)=LASTBVT(P)={c}

FIERSTVT(Q)={a}LASTBVT(Q)={a}

構(gòu)造優(yōu)先關(guān)系表為:

abc

a<><>

b<>

c>>

由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了和。a以及和b>b,所以該文法不是算符優(yōu)先文法。

2.消除左遞歸和提取左公因子后的文法為：

S-aSbIP

P一bP'

P-Pc|Qc

Q-aQz

QJaQzIe

求具有相同左部的兩個(gè)產(chǎn)生式的Select集的交集：

Select(S-aSb)ASelect(S-P)={a}DFirst(P)={a}D=6

Select(Pz-Pc)ASelect(Pz-?Qc)=First(P)ClFirst(Q)=A{a}=6

Select(Qz-*aQz)ASelect(Qz-c)={a}AFollow(Q)=<a}A{c}=6

所以修改后的文法是LL(1)文法。

七LR(1)項(xiàng)目集和可歸前綴圖如下:

構(gòu)造LR(1)分析表如下:

狀態(tài)abcde#sA

0S2S31

1acc

2S5

3S7

4S8

5S9r5

6S10

7r5Sil

8rl

9r3

10