編譯原理樣題1(有答案)

編譯原理

一、是非題（下列各題你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打錯(cuò)的打“X”。每題1分,

共5分）

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

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

3、目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。.........（）

4、正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。..................（）

5、一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。

..................................................................（）

二、填空題（每題2分，共5分）

1、語(yǔ)法分析是依據(jù)語(yǔ)言的（）規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（）規(guī)進(jìn)行的。

2、程序語(yǔ)言的單詞符號(hào)一般可以分為（）等等。

3、語(yǔ)法分析器的輸入是（）,其輸出是（）o

4、所謂自上而下分析法是指（）。

5、如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是（）。

6、對(duì)于文法G,僅含終結(jié)符號(hào)的句型稱(chēng)為（）。

7、逆波蘭式ab十c+d*e—所表達(dá)的表達(dá)式為（）。

8、一個(gè)名字的屬性包括（）和（）o

9、對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用（）策略，PASCAL采用（）策略。

10、所謂優(yōu)化是指（）。

三、名詞解釋題（每題2分，共10分）

1、詞法分析器：______________

2、語(yǔ)法：_____________

3、最右推導(dǎo)：______________

4、語(yǔ)法制導(dǎo)翻譯：

5、基本塊；_______________

四、簡(jiǎn)述題（每題4分，共24分）

1、考慮下面的程序：

Vari：integer；

a：array[l--2]ofinteger；

procedureQ(b)；

Varb：integer；

Begin

i：=1；b：=b十2；

i：=2；b：=b+3

End：

Begin

a[l]：=5；a[2]：=6：

i：=1；

Q(a[i])；print(a[l],a[2])

End.

試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a山，a[2]的值

是什么？

2、畫(huà)出識(shí)別pascal中實(shí)常數(shù)(可帶正負(fù)號(hào)，但不含指數(shù)部分)的狀態(tài)轉(zhuǎn)換圖。

3、已知文法G(S)：

S->a|(A)

T—T,S|S

的優(yōu)先關(guān)系如下：

()，

a>

(<

)

，<<>>

4、寫(xiě)出表達(dá)式(a+b)/(a-b)-(a+b*c)的三元序列及四元序列。

5、符號(hào)表的作用是什么？符號(hào)表的查找和整理技術(shù)有哪幾種？

6、何謂DISPLAY表？其作用是什么？

五、計(jì)算題(10分)

]、寫(xiě)一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(shù)不以0開(kāi)頭。(5分)

2、已知文法G(S)：

S-a|(T)

T—T,S|S

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

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

3、把語(yǔ)句

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

elseBegin

x：=x+2

y：=y+3

End；

翻譯成四元式序列。(6分)

4、設(shè)某語(yǔ)言的for語(yǔ)句的形式為

fori:=E(DtoE⑵doS

其語(yǔ)義解釋為

i:=E(,)

LIMIT:=E(2)

again:ifi<=LIMITthen

Begin

S；

i:=i+l

gotoagain

End;

(1)寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；

(2)寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。(6分)

5、設(shè)文法G(S)：

S->S+aF|aF|+aF

F-**aF|*a

(1)消除左遞歸和回溯；

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

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

6、對(duì)以下基本塊

Tl=2

T2：=A—B

T3=A+B

T4=T2*T3

T5=3*T1

T6=A-B

T：=A+B

T7=T6+L

T8=T5*4

M；-T84-T7

L：=M

(1)畫(huà)出DAG圖；

(2)假設(shè)只有L在基本塊出口之后還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元式序列。(6分)

編譯原理答案

一、是非題（下列各題你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“小，錯(cuò)的打“X”。每題1分,

共5分）

1W2.X3.74.A/5.X

二、填空題（每題2分，共5分）

1.語(yǔ)法；語(yǔ)義2.基本字、標(biāo)識(shí)符、常量、算符。界符

3.單詞符號(hào)串；語(yǔ)法單位4.從開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子

5二.義的6.句子

7（.a+b+c）*d—e8.類(lèi)型；作用域

9.靜態(tài)存儲(chǔ)分配

10.對(duì)程序進(jìn)行各種等價(jià)變化，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼

三、名詞解釋題（每題2分，共10分）

1.指執(zhí)行詞法分析的程序。

2.是一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合法的程序。

3.指任何一步a推出p都是a中的最右北終結(jié)符替換。

4.在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的辦法叫做語(yǔ)法制

導(dǎo)翻譯。

5.指程序中一個(gè)順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口，一個(gè)出口，入口即第一個(gè)語(yǔ)

句。出口即第二個(gè)語(yǔ)句。

四、簡(jiǎn)述題（每題4分，共24分）

1.答：傳地址：a=10,b=6

傳值：a=5,b=6（每個(gè)值1分）

2.答:

答:

4.（1）（三元式2分）

①(+,a,b)

②(—>a,b)

③（/,①，②）

④（*,b,c）

⑤（十，a,④）

?（―,③，⑤）

（2）（四元式2分）

①（+,a,b,Tl）

②（一，a,b,T2）

③（/,Tl,T2,T3）

④（*,b,c,T4）

⑤（+,a,T4,T5）

⑥（一，T3,T5,T6）

5.作用：（2分）登記源程序中出現(xiàn)的各種名字及信息，以及編譯各階段的進(jìn)展?fàn)顩r。

主要技術(shù)：（2分）線性表，對(duì)折查表與二叉樹(shù)，雜湊技術(shù)。

6.答：display表是嵌套層次顯示表。

由于過(guò)程嵌套允許內(nèi)層過(guò)程引用外層過(guò)程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過(guò)程運(yùn)行時(shí)必須

跟蹤它的所有外層過(guò)程的最新活動(dòng)記錄起始地址，而display表就是用于登記每個(gè)外層過(guò)程

的最新活動(dòng)記錄起始地址。

五、計(jì)算題（10分）

1.解：文法G（S）：

S->AB|B|A0

ATAD|C

B一2|4|6|8

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

D->0|C

2.

解，

發(fā)左推導(dǎo),(2分)

S-(T)2(T,S)

"I.,S-T))5a八,S))

》(a,(S,S)),>(a,(a,$)J

Wn,(a>o))

諳法樹(shù)，(2分)

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

(T,S),a

(T,S)

T,S

a

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

a

句柄：(1分)T,S

3.解:(1)ifx>0goto3

(2)goto8

(3)ify>0goto5

(4)goto8

(5)tl=x+y

(6)z=tl

(7)goto12

(8)t2=x+2

(9)x=t2

(10)t3=y+3

(11)y=t3

(12)

(控制結(jié)構(gòu)3分，其它3分)

4.解：(1)(2分)

F—fbri：=E⑴loE⑵do

S—FS

(2)(每個(gè)語(yǔ)義動(dòng)作2分)

F->fori=E(,)toE，2>do

{GEN(：=E-place,一,entry(i)；

F-place：=entry(i)；

LIMIT：=Newtemp；

GEN(：=,E(2>-place,一,LIMIT)；

q：=NXQ；

FQUAD：=q；

GEF(j<,(entry(i),LIMIT,q+2)

F-chain：=NXQ；

G(j,—,一,0)}

STFs⑴

{BACKPATCH(S⑴chain,NXQ)；

GEN(十，F(xiàn)-place,1,F-place)；

GEN(j,一，F(xiàn)QUAD)；

Schain:=F-chain)：

5.解:

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

S->aFS*|+aFS'

SJ+aFS'|￡

F1*aF'

F->F|e

(2)(3