(完整word版)編譯原理期末試題(二)含答案,文檔

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦(完整word版)編譯原理期末試題(二)含答案,文檔《編譯原理》期末試題（二）

一、是非題：

1.一個(gè)上下文無(wú)關(guān)文法的開(kāi)頭符，可以是終結(jié)符或非終結(jié)符。()

2.一個(gè)句型的直接短語(yǔ)是唯一的。（）

3.已經(jīng)證實(shí)文法的二義性是可判定的。（）

4.每個(gè)基本塊可用一個(gè)DAG表示。（）

5.每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。（）

6.2型文法一定是3型文法。（）

7.一個(gè)句型一定句子。()

8.算符優(yōu)先分析法每次都是對(duì)句柄舉行歸約。X()

9.采納三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼舉行優(yōu)化。（）

10.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。()

11.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。X()

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

13.遞歸下降分析法是一種自下而上分析法。()

14.并不是每個(gè)文法都能改寫(xiě)成LL(1)文法。()

15.每個(gè)基本塊惟獨(dú)一個(gè)入口和一個(gè)出口。()

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

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

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

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

20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。()

21.3型文法一定是2型文法。()

22.假如一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。()

答案：1.×2.×3.×4.√5.√6.×7.×8.×9.√10.×

11.×

12.√13.×14.√15.√16.√17.×18.√19.√20.×21.√22.√

二、填空題：

2.編譯過(guò)程可分為（詞法分析），（語(yǔ)法分析），（語(yǔ)義分析與中間代碼生成），（優(yōu)化）和（目標(biāo)

代碼生成）五個(gè)階段。

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

4.從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（執(zhí)行性）語(yǔ)句和（說(shuō)明性）語(yǔ)句兩大類(lèi)。

5.語(yǔ)法分析器的輸入是（單詞符號(hào)），其輸出是（語(yǔ)法單位）。

6.掃描器的任務(wù)是從（源程序中）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)）。

7.符號(hào)表中的信息欄中記下了每個(gè)名字的有關(guān)的性質(zhì)，如(類(lèi)型、種屬、所占單元大小、地址）等等。

8.一個(gè)過(guò)程相應(yīng)的DISPLAY表的內(nèi)容為(現(xiàn)行活動(dòng)記錄地址和全部外層最新活動(dòng)記錄的地址)

10.常用的兩種動(dòng)態(tài)存貯分配方法是（棧式）動(dòng)態(tài)分配和（堆式）動(dòng)態(tài)分配。

11.一個(gè)名字的屬性包括(類(lèi)型)和(作用域)。

12.常用的參數(shù)傳遞方式有(傳地址），（傳值），（傳名）

13.按照優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個(gè)級(jí)別。

14.語(yǔ)法分析的辦法大致可分為兩類(lèi)，一類(lèi)是（自上而下）分析法，另一類(lèi)是（自下而上）

分析法。

15.預(yù)測(cè)分析程序是使用一張（分析表）和一個(gè)（符號(hào)棧）舉行聯(lián)合控制的。

17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為是（初）態(tài);而且實(shí)際上至少要有一個(gè)（終）態(tài)。

19.語(yǔ)法分析是依據(jù)語(yǔ)言的（語(yǔ)法）規(guī)章舉行。中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（語(yǔ)義）規(guī)章舉行的。

21.一個(gè)文法G，若它的預(yù)測(cè)分析表M不含多重定義，則該文法是（LL(1)文法）文法。

22.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采納(靜態(tài)策略，PASCAL采納(動(dòng)態(tài))策略。

24.最右推導(dǎo)亦稱(chēng)為（規(guī)范推導(dǎo)），由此得到的句型稱(chēng)為（規(guī)范）句型。

26.對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱(chēng)為(句子)。

27.所謂自上而下分析法是指(從開(kāi)頭符號(hào)動(dòng)身，向下推導(dǎo)，推出句子）

29.局限于基本塊范圍的優(yōu)化稱(chēng)（局部?jī)?yōu)化）。

31.2型文法又稱(chēng)為（上下文無(wú)關(guān)）文法；3型文法又稱(chēng)為（正則）文法。

32.每條指令的執(zhí)行代價(jià)定義為(指令拜訪主存次數(shù)加1）

33.算符優(yōu)先分析法每次都是對(duì)(最左素短語(yǔ)）舉行歸約。

三、名詞解釋題：

1.局部?jī)?yōu)化局限于基本塊范圍的優(yōu)化稱(chēng)。

2.二義性文法假如一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義性文法。

3.DISPLAY表過(guò)程的嵌套層次顯示表，記錄該過(guò)程的各外層過(guò)程的最新活動(dòng)記錄的起始地址。

5.最左推導(dǎo)任何一步α=>β都是對(duì)α中的最右非終結(jié)符替換。

6.語(yǔ)法一組規(guī)章，用它可形成和產(chǎn)生一組合式的程序。

7.文法描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)章。

8.基本塊指程序中一挨次執(zhí)行的語(yǔ)句序列，其中惟獨(dú)一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)

語(yǔ)句，出口就是其中的最后一個(gè)語(yǔ)句。

9.語(yǔ)法制導(dǎo)翻譯在語(yǔ)法分析過(guò)程中，按照每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序舉行翻譯的方法叫做語(yǔ)法

制導(dǎo)翻譯。

10.短語(yǔ)令G是一個(gè)文法，S劃文法的開(kāi)頭符號(hào)，假定αβδ是文法G的一個(gè)句型，假如有S

αAδ且Aβ，則稱(chēng)β是句型αβδ相對(duì)非終結(jié)符A的短語(yǔ)。

11.待用信息假如在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)

有A的其它定值，則稱(chēng)j是四元式i的變量A的待用信息。

12.規(guī)范句型由規(guī)范推導(dǎo)所得到的句型。

13.掃描器執(zhí)行詞法分析的程序。

14.超前搜尋在詞法分析過(guò)程中，有時(shí)為了確定詞性，需超前掃描若干個(gè)字符。

15.句柄一個(gè)句型的最左直接短語(yǔ)。

16.語(yǔ)法制導(dǎo)翻譯在語(yǔ)法分析過(guò)程中，按照每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義程序舉行翻譯的辦法叫做語(yǔ)

法制導(dǎo)翻譯。

17.規(guī)范句型由規(guī)范推導(dǎo)所得到的句型。

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

素短語(yǔ)。

19.語(yǔ)法是組規(guī)章，用它可形成和產(chǎn)生一個(gè)合式的程序。

20.待用信息假如在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)

有A的其它定值，則稱(chēng)j是四元式i的變量A的待用信息。

21.語(yǔ)義定義程序的意義的一組規(guī)章。

四、簡(jiǎn)答題：

1.寫(xiě)一個(gè)文法G,使其語(yǔ)言為不以0開(kāi)始的偶數(shù)集。

2.已知文法G(S)及相應(yīng)翻譯計(jì)劃

S→aAb{print“1”}

S→a{print“2”}

A→AS{print“3”}

A→c{print“4”}

輸入acab,輸出是什么？

3.已知文法G(S)

S→bAa

A→(B|a

B→Aa)

寫(xiě)出句子b(aa)b的規(guī)范歸約過(guò)程。

4.考慮下面的程序：

…

procedurep(x,y,z)；

begin

y:=x+y;

z:=z*z;

end

begin

A:=2;

B:=A*2;

P(A,A,B);

PrintA,B

end.

試問(wèn)，若參數(shù)傳遞的方式分離采納傳地址和傳值時(shí)，程序執(zhí)行后輸出A,B的值是什么?5．文法G(S)

S→dAB

A→aA|a

B→Bb|ε

描述的語(yǔ)言是什么？

6.證實(shí)文法G(S)

S→SaS|ε

是二義性的。

7.已知文法G(S)

S→BA

A→BS|d

B→aA|bS|c

的預(yù)測(cè)分析表如下

給出句子adccd的分析過(guò)程。

8.寫(xiě)一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)={albmclanbn|l>=0,m>=1,n>=2}

9.已知文法G(S):

S→a|(T)

T→T,S|S

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

請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。

10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？

11.目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？

12.一字母表Σ={a,b}，試寫(xiě)出Σ上全部以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。

13.基本的優(yōu)化辦法有哪幾種？

14.寫(xiě)一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)={abncn|n≥0}

15.考慮下面的程序：

…

procedurep(x,y,z);

begin

y:=y+z;

z:=y*z+x

end;

begin

a:=2;

b:=3;

p(a+b,b,a);

printa

end.

試問(wèn)，若參數(shù)傳遞的方式分離采納傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么?

16.寫(xiě)出表達(dá)式a＋b*(c-d)/e的逆波蘭式和三元序列。

17.證實(shí)文法G(A)

A→AA|(A)|ε

是二義性的。

18.令Σ={a,b}，則正規(guī)式a*b|b*a表示的正規(guī)集是什么？

19.何謂DISPLAY表？其作用是什么？

20.考慮下面的程序：

…

procedurep(x,y,z)；

begin

y:=y+2;

z:=z+x;

end

begin

a:=5;

b:=2;

p(a+b,a-b,a);

printa

end.

試問(wèn)，若參數(shù)傳遞的方式分離采納傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么?

21.寫(xiě)一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)={anbncm|n>0為奇數(shù)，m>0為偶數(shù)}

22.寫(xiě)出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。

23.一個(gè)文法G別是LL(1)文法的充要條件是什么？

24.已知文法G[S]

S→S*aF|aF|*aF

F→+aF|+a

消退文法左遞歸和提公共左因子。

25.符號(hào)表的作用是什么？符號(hào)表查找和收拾技術(shù)有哪幾種？

答案：1.所求文法是G[S]:

S→AB|BA0

A→AD|C

B→2|4|6|8

C→1|3|5|7|9|B

D→0|C

2.輸出是4231

3.句子

4.

傳值A(chǔ)=2,B=4

5.L(G)={danbm|n>0,m≥0}

6.證實(shí)：

由于文法G[S]存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。

S=>SaS=>SaSaS=>aSaS=>aaS=>aa

S=>SaS=>aS=>aSaS=>aaS=>aa

7.句子

8.

S→AB

A→aAc|D

D→bD|b

B→aBb|aabb

9.

10.

三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化

11.目標(biāo)代碼通常采納三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。

應(yīng)著重考慮的問(wèn)題：

(1)如何使生成的目標(biāo)代碼較短；

(2)如何充分利用寄存器，以削減拜訪內(nèi)存次數(shù)；

(3)如何充分利用指令系統(tǒng)的特點(diǎn)。

12.正規(guī)式a(a|b)*。

13.刪除多余運(yùn)算，代碼外提，強(qiáng)度減弱，變換循環(huán)控制條件，合并已知量，復(fù)寫(xiě)傳揚(yáng)和刪除無(wú)用賦值。

14.文法G[S]:

S→aB|a

B→bc|bBc

15.傳值a=2

傳地址a=15

16.逆波蘭式:abcd-*e/+

三元序列:oparg1arg2

(1)-cd

(2)*b(1)

(3)/(2)e

(4)+a(3)

17.證實(shí)：

由于文法G[S]存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。

A=>AA=>(A)A=>()A=>()

A=>AA=>A=>(A)=>()

18.(a*b|b*a)={a,b,ab,ba,aab,bba……}

19.Display表:嵌套層次顯示表

因?yàn)檫^(guò)程嵌套允許內(nèi)層過(guò)程引用外層過(guò)程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過(guò)程運(yùn)行時(shí)必需跟蹤它的全部外層過(guò)程的最新活動(dòng)記錄起始地址，display表就是用于記下每個(gè)外層過(guò)程的最新活動(dòng)記錄起始地址。

20.傳地址a=12

傳值a=5

21.所求文法是G[S]:

S→AC

A→aaAbb|ab

C→ccC|cc

22.逆波蘭式abc+e*bc+f/+:=

三元序列oparg1arg2

(1)+bc

(2)*(1)e

(3)+bc

(4)/(3)f

(5)+(2)(4)

(6):=a(5)

23.一個(gè)文法G別是LL(1)文法的充要條件是:

(1)FIRST(α)∩FIRST(β)=Ф

(2)假如β=*>ε,FIRST(α)∩FOLLOW(A)=Ф

24.消退左遞歸

S→aFS’|*aFS’

S’→*aFS’|ε

F→+aF|+a

提公共左因子,文法G’(S)

S→aFS’|*aFS’

S’→*aFS’|ε

F→+aF’

F’→F|ε

25.作用：記下源程序中浮現(xiàn)的各種名字及其信息，以及了解各階段的發(fā)展情況。主要技術(shù)：線(xiàn)性表，對(duì)折查找，雜奏技術(shù)。

五、計(jì)算題：

1.設(shè)文法G(S):

S→^|a|(T)

T→T,S|S

⑴消退左遞歸；

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

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

2.語(yǔ)句ifEthenS

(1)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯；

(2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。

3.設(shè)文法G（S）：

S→(T)|a

T→T+S|S

(1）計(jì)算FIRSTVT和LASTVT；

（2）構(gòu)造優(yōu)先關(guān)系表。

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

fori:＝E(1)toE(2)doS

其語(yǔ)義解釋為

i:＝E(1)

LIMIT:＝E(2)

again:ifi＜＝LIMITthen

Begin

S;

i:＝i＋1

gotoagain

End;

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

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

5.把語(yǔ)句

whilea0thena:=a+1

elsea:=a*3-1;

翻譯成四元式序列。

6.設(shè)有基本塊

D:=A-C

E:=A*C

F:=D*E

S:=2

T:=A-C

Q:=A*C

G:=2*S

J:=T*Q

K:=G*5

L:=K+J

M:=L

假設(shè)基本塊出口時(shí)惟獨(dú)M還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。

7.已知文法G(S)

S→a|^|(T)

T→T,S|S

(1)給出句子(a,(a,a))的最左推導(dǎo)；

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

8.對(duì)于C語(yǔ)言doSwhileE語(yǔ)句

(1)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯；

(2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。

9.已知文法G(S)

S→aAcBe

A→Ab|b

B→d

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

(2)給出句型aAbcde的短語(yǔ)、素短語(yǔ)。

10.設(shè)文法G(S):

S→(T)|aS|a

T→T,S|S

⑴消退左遞歸和提公共左因子；

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

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

11.把語(yǔ)句

ifX>0∨Y0doX:=A*3

elseY:=B+3;

翻譯成四元式序列。

12.已知文法G(S)

E→E+T|T

T→T*F|F

F→(E)|i

(1)給出句型(i+i)*i+i的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；

(2)給出句型(E+T)*i+F的短語(yǔ)，素短語(yǔ)和最左素短語(yǔ)。

13.設(shè)文法G（S）：

S→T|S∨T

T→U|T∧U

U→i|-U

（1）計(jì)算FIRSTVT和LASTVT；

（2）構(gòu)造優(yōu)先關(guān)系表。

答案：(1)消退左遞，文法變?yōu)镚’[S]：

S→^|a|(T)'

T→ST’|S

T’→,ST’|ε

此文法無(wú)左公共左因子。

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

FIRST(S)={a,^,(}，F(xiàn)OLLOW(S)={#,,,)}

FIRST(T)={a,^,(}，F(xiàn)OLLOW(T)={}}

FIRST(T’)={,,ε}，F(xiàn)OLLOW(F)={)}

C→ifEthen

S→CS(1)

(2)

C→ifEthen{BACK(E.TC,NXQ);C.chain:=E.FC}S→CS(1){S.chain:=MERG(C.Chain,S(1).Chain)}3.(1)FIRSTVT(S)={a,(}

FIRSTVT(T)={+,aa,(}

LASTVT(S)={a,)}

LASTVT(T)={+,a,)}

S→FS(1)

(2)F→fori:=E(1)toE(2)do

{GEN(:=,E(1).place,_,entry(i));

F.place:=entry(i);

LIMIT:=Newtemp;

GEN(:=,E(2).place,_,LIMIT);

Q:=NXQ;

F.QUAD:=q;

GEN(j≤,entry(i),LIMIT,q+2)

F.chain:=NXQ;

GEN(j,_,_,0)}

S→FS(1)

{BACKPATCH(S(1).chain,NXQ);

GEN(+,F.place,1,F.place);

GEN(j,_,_,F.QUAD);

S.chain:=F.chain

}

5.(1)(j,c,‘0’,(5))

(4)(j,_,_,(8))

(5)(+,a,‘1’,T1))

(6)(:=,T1,_,a)

(7)(j,_,_,(1))

(8)(*,a,‘13’,T2)

(9)(-,T2,‘1’,T3)

(10)(:=,T3,_,a)

(11)(j,_,_,(1))

6.優(yōu)化后的四元序列

D:=A-C

E:=A*C

F:=D*E

M:=F+20

7.最左推導(dǎo)

S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))

短語(yǔ)

((T,S),a)

(T,S),a

(T,S)

T,S

a

直接短語(yǔ)

T,S

a

句柄

T,S

8.(1)

S→doM1S1whileM2E

M→ε

(2)

M→ε{M.quad=nestquad;}

S→doM1S1whileM2E{backpatch(s1.nextlist,M2.quad);

backpatch(E.truelist,M1.quad