《編譯原理》考試試題及答案

《編譯原理》考試試題及答案（附錄）

一、判斷題：

1.一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。（X）

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

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

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

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

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

7一個(gè)句型一定句子。（x）

8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。（應(yīng)是最左素短語(yǔ)）（X）

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

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

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

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

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

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

15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。（）

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

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

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

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

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

21.3型文法一定是2型文法。（）

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

二、填空題：

1.（最右推導(dǎo)）稱為規(guī)范推導(dǎo)。

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

標(biāo)代碼生成）五個(gè)階段。

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

4.從功能上說，程序語(yǔ)言的語(yǔ)句大體可分為（）語(yǔ)句和（）語(yǔ)句兩大類。

5.語(yǔ)法分析器的輸入是（）,其輸出是（）。

6.掃描器的任務(wù)是從（）中識(shí)別出一個(gè)個(gè)（）＜.

7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（）等等。

8.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為（）＜.

9.一個(gè)句型的最左直接短語(yǔ)稱為句型的（）。

1Q.常用的兩種動(dòng)態(tài)存貯分配辦法是（）動(dòng)態(tài)分配和（）動(dòng)態(tài)分配。

1L一個(gè)名字的屬性包括（）和（）。

12.常用的參數(shù)傳遞方式有（），（）和（）。

13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（），（）和（）三個(gè)級(jí)別。

14.語(yǔ)法分析的方法大致可分為兩類，一類是（）分析法，另一類是（）分析法。

15.預(yù)測(cè)分析程序是使用一張（）和一個(gè)（）進(jìn)行聯(lián)合控制的。

16.常用的參數(shù)傳遞方式有（）,（）和（）。

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

18.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（），（）和（）三個(gè)級(jí)別。

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

20.一個(gè)句型的最左直接短語(yǔ)稱為句型的（

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

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

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

24.最右推導(dǎo)亦稱為（）,由此得到的句型稱為（）句型。

25.語(yǔ)法分析的方法大致可分為兩類，一類是（）分析法，另一類是（）分析法。

26.對(duì)于文法G,僅含終結(jié)符號(hào)的句型稱為（）o

27.所謂自上而下分析法是指（

28.語(yǔ)法分析器的輸入是（）,其輸出是（）<>

29.局限于基本塊范圍的優(yōu)化稱（）o

30.預(yù)測(cè)分析程序是使用一張（）和一個(gè)（）進(jìn)行聯(lián)合控制的。

31.2型文法又稱為（）文法；3型文法又稱為（）文法。

32.每條指令的執(zhí)行代價(jià)定義為（

33.算符優(yōu)先分析法每次都是對(duì)（）進(jìn)行歸約。

三、名詞解釋題：

1.局部?jī)?yōu)化

2.二義性文法

3.DISPLAY表

4.詞法分析器

5.最左推導(dǎo)

6.語(yǔ)法

7.文法

8.基本塊

9.語(yǔ)法制導(dǎo)翻譯

10.短語(yǔ)

11.待用信息

12.規(guī)范句型

13.掃描器

14.超前搜索

15.句柄

16.語(yǔ)法制導(dǎo)翻譯

17.規(guī)范句型

18.素短語(yǔ)

19.語(yǔ)法

20.待用信息

21.語(yǔ)義

四、簡(jiǎn)答題：

1.寫一個(gè)文法G,使其語(yǔ)言為不以。開頭的偶數(shù)集。

2.已知文法G（S）及相應(yīng)翻譯方案

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)

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

4.考慮下面的程序：

procedurep(x,y,z)；

begin

y:=x+y;

2：=Z*Z；

end

begin

A:=2;

B:=A*2;

P(A,A,B);

PrintA,B

end.

試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出A,B的值是什么？

5.文法G(S)

S-*dAB

A—aA|a

B->Bb|e

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

6.證明文法G(S)

S-SaS|E

是二義性的。

7.已知文法法S)

S-BA

A^BS|d

B-*a?.|bS|c

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

abcd

SS-*BAS-BAS-BA

AAfBSAfBSA-BSA-d

BB-*aAB-bSB-*c

給出句子adccd的分析過程。

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

9.已知文法G(S):

S-*a|(T)

T-T,S|S

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

關(guān)系a()

a.>.>

(<.一.

).>.>

(z.>.>

請(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è)問題？

12.一字母表2={a,b},試寫出S上所有以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。

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

14.寫一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)={abnen|n^O}

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.

試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？

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

17.證明文法G(A)

2AA|(A)|e

是二義性的。

18.令2={a,b},則正規(guī)式/bEa表示的正規(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.

試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？

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

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

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

24.已知文法G[S]

S，S*aF|aF|*aF

Ff+aF|+a

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

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

五、計(jì)算題：

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

S一|a|⑴

T-*T,S|S

(1?消除左遞歸；

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

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

2.語(yǔ)句ifEthenS

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

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

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

STT)|a

T-T+S|S

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

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

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

fori:=E(I>toE⑵doS

其語(yǔ)義解釋為

i:=E(,)

LIMIT:=E(2)

again:ifi<=LIMITthen

Begin

S;

i:=i+1

gotoagain

End;

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

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

5.把語(yǔ)句

whilea<10do

ifc>0thena:=a+l

elsea:=a*3-l;

翻譯成四元式序列。

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í)只有M還被弓用，請(qǐng)寫出優(yōu)化后的四元序列。

7.已知文法法S)

S-ar|⑴

T-T,S|S

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

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

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

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

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

9.已知文法G(S)

S-*aAcRp

A-*Ab|b

B-*d

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

(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>0VY<0

thenwhileX>0doX:=A*3

elseY:=B+3;

翻譯成四元式序列。

12.己知文法G(5)

EfE+T|T

T-*T*F|F

F-(E)|i

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

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

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

S-*T|SvT

T-U|TAU

U-i|-U

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

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

參考答案

一、是非題：

1.X2.X3.X4.V5.V6.X7.X8.X9.V10.X11.X

12.J13.X14.V15.V16.J17.X18.V19.J20.X21.V22.J

二、填空題：

1.（最右推導(dǎo)）

2.（詞法分析），（語(yǔ)法分析），（中間代碼生成），（代碼優(yōu)化），（目標(biāo)代碼生成）

3.（二義性的）

4.（執(zhí)行性），（說明性）

5.（單詞符號(hào)），（語(yǔ)法單位）。

6.（源程序），（單詞符號(hào)）

，.（類型、種屬、所占單元大小、地址）

8.（現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址）

9.（句柄）

10.（棧式），（堆式）

11.（類型），（作用域）

12.（傳地址）,（傳值），（傳名）

13.（局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）

".（自上而下），（自下而上）

15.（分析表），（符號(hào)棧）

16.（傳地址），（傳值），（傳名）

17.（初），（終）

18.（局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）

19.（語(yǔ)法），（語(yǔ)義）

20.（句柄）

21.（LL（1）文法）

22.（靜態(tài)）,（動(dòng)態(tài)）

23.（二義性文法）

24.（規(guī)范推導(dǎo)），（規(guī)范）

25.（自上而下），（自下而上）

26.（句子）

27.（從開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）

28.（單詞符號(hào)），（語(yǔ)法單位）

2g.（局部?jī)?yōu)化）

30.（分析表），（符號(hào)棧）

31.（上下文無關(guān)文法），（正規(guī)）

32.（指令訪問主存次數(shù)加1）

33.（最左素短語(yǔ)）

三、名詞解釋題：

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

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

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

4.詞法分析器——執(zhí)行詞法分析的程序。

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

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

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

8.基本塊----指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)

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

第1頁(yè)共7頁(yè)

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

制導(dǎo)翻譯。*

10.短語(yǔ)---令G是一個(gè)文法，S劃文法的開始符號(hào)，假定aB6是文法G的一個(gè)句型，如果有S=>

aA6且A=±5B,則稱B是句型aB6相對(duì)非終結(jié)符A的短語(yǔ)。

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

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

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

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

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

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

16.語(yǔ)法制導(dǎo)翻譯---在語(yǔ)法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義程序進(jìn)行翻譯的方法叫做語(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ò)之間沒

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

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

四、簡(jiǎn)答題：

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

SfAB|BAO

A-AD|C

B-2|4|6|8

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

D-*0|C

2.輸出是4231

3.句子b(aa)b的規(guī)范歸約過程：

步驟符號(hào)棧輸入串動(dòng)作

0#b(aa)b#預(yù)備

1#b(aa)b#移進(jìn)

2#b(aa)btt移進(jìn)

3#b(aa)b#移進(jìn)

4#b(Aa)b#歸約

5#b(Ma)b#移進(jìn)

6#b(Ma)b#移進(jìn)

7#b(Bb#歸約

8#bAb#歸約

9#bAb移進(jìn)

10#Sn接受

4.傳地址A=6,B=16

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

5.L(G)={danbB|n>0,m20}

6.證明：

因?yàn)槲姆℅[S]存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法G[S]是是二義性的。

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

第2頁(yè)共7頁(yè)

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

7.句子adccd的分析過程：

步驟符號(hào)棧輸入串產(chǎn)生式

0#Sadccd#

1#ABadccd#S-BA

2#AAaadccd#B-*aA

3#AAdeed#

4#Addeed#A-*d

5#Accd#

6#SBccd#A-BS

7#Scccd#B-*c

8#Scd#

9#ABcd#B-*c

10#Acd#

11#Ad#

12#dcl=A-*d

13

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

S-AB

A--aAc|D

D-bD|b

B-*aBb|aabb

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

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

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

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

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

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

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

14.文法G[S]:

S-aB|a

B—be|bBc

15.傳值a=2

傳地址a=15

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

三元序列：oparglarg2

第3頁(yè)共7頁(yè)

(1)—Cd

⑵*b(1)

(3)/⑵<?

(4)+a(3)

17.證明：

因?yàn)槲姆℅[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表:嵌套層次顯示表

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

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

20.傳地址a:12

傳值a=5

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

SfAC

A-*aaAbbIab

C-*ccC|cc

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

三元序列oparglarg2

(1)+bc

(2)*(1)e

(3)+bc

(4)/(3)f

(5)+(2)(4)

(6):=a(5)

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

(1)FIRSTS)nFIRST(B)=中

(2)如果B=*>￡,FIRST(a)nFOLLOW(A)=①

24.消除左遞歸

S-aFS'|*aFS,

S'->*aFS'|￡

F-*+aF|+a

提公共左因子，文法1(S)

S-aFS'|*aFS,

S'f*aFS'|￡

1+aF'

F'-F|￡

25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。

主要技術(shù)：線性表，對(duì)折查找，雜奏技術(shù)。

五、計(jì)算題：

1.

(1)消除左遞，文法變?yōu)镚'[S]：

S1|a|(T)'

T-ST'|S

V|￡

此文法無左公共左因子。

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

FIRST(S)={a,\(},FOLLOW(S)={#,,,)}

第4頁(yè)共7頁(yè)

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

FIRST1')={,,e},FOLLOW(F)={)}

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

aA()#

sS—>aS—AS->(T)'

TT—ST'T->ST,T—ST'

T'T'fTJ,sr

2.(1)

ifEthen

S-CS⑴

(2)

"ifEthen{BACK(E.TC,NXQ);C.chain:=E.FC}

S-CS⑴{S.chain:=MERG(C.Chain,S⑴.Chain)}

3.(1)FIRSTVT(S)={a,(}

FIRSTVT(T)={+,()

LASTVT(S)={a,))

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

(2)

a+()

a.>.>

+<..><..>

(<.<.<.=e

).>.>>.

4.(1)F—fori:=E(l>toE⑵do

STS⑴

(2)Fffori:=E<0toE"do

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

F.place:=entry(i);

LIMIT:=Newtemp;

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

Q:=NXQ;

F.QUAD:二q;

GENgentry(i),LIMIT,q+2)

F.chain:=NXQ;

GEN(j,0)}

STS⑴

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

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

GEN(j,F.QUAD);

S.chain:=F.chain

5.(1)(j<?a,'10',(3))

⑵(j,(12))

(3)(j>,c,'O',(5))

(4)(j,(8))

(5)(+,a,T,Tl))

(6)(:=,Tl,a)

⑺(j,(D)

(8)(*,a,'13',T2)

第5頁(yè)共7頁(yè)

(9)(-,T2,T,T3)

(10)(:=,T3,a)

(11)(j,(D)

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-d。M]StwhileM2E

M-e

(2)

M-*e{M.quad=nestquad;}

S-*doMiSiwhileM2E{backpatchCsj.nextlist,M?.quad)

backpatch(E.truelist,M).quad);

S.nextlist=E.falelist;

}

9.(1)S=>aAcBe=>AAbcBe=>abbcBe=>abbcde

：2)短語(yǔ)：aAbcde,Ab,d

素短語(yǔ)：Ab,d

10.(1)Sf(L)|aS,

S，-S|￡

LfSL'

I?f,SI/|￡

(2)FIRST(S)={a,(}FIRST(S,)={a,(,e)

FIRST(L)=(a,()FIRST(L")=(,,e)

FOLLOW(S)={,?),#}FOLLOW(S,)={,,),#}

FOLLOW(L)={)}FOLLOW(L,)={)}

()a#

sSf(L)S-aS'

s*S'-SS'-￡S'-SS'f￡S'-￡

LLfSL'L-SUL」,SL，

L，L'fe

第6頁(yè)共7頁(yè)

11.(1)(j>,X,0,(5))

z

f2

\(j,,,(3))

/\

f3l

xz(j<.Y,0,(5))

zK

(4}

\z(j,(ID)

/\

(5J

XZ(j>0,X,0,(7))

y6\

f!

\/(j,(7))

/7\

(—

X/(*,A,3,T.)

/8X

(I

X/(：=,T.,N)

z9\

(!

\0/(j,(5))

1\

117(j,(13))

1

1

2(十,B,3,T2)

1\

!

1/

(：=,T2,Y)

12.(1)E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T

=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T

=>(i+i)*i+F=>(i+i)*i+i

：2)短語(yǔ)i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F

素短語(yǔ)i,E+T

最左素短語(yǔ)E+T

13.(1)FIRSTVT(S)-{V,A,i,一}

FIRSTVT(T)={A,i,-)

FIRSTVT(U)=(i,-}

LASTVT(S)={V,A,i,-)

LASTVT(T)={A,i,-}

LASTVT(U)={i,-}

(2)

iVA-

s.>.>

V<..><.<.

A<..>.><.

一<..>.><.

一、單項(xiàng)選擇題

1.將編譯程序分成若干個(gè)“遍”是為了（B）

A.提高程序的執(zhí)行效率

B.使程序的結(jié)構(gòu)更加清晰

C.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率

D.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率

2.不可能是目標(biāo)代碼的是（D）

A.匯編指令代碼B.可重定位指令代碼

C.絕對(duì)指令代碼D.中間代碼

3.詞法分析器的輸入是（B）

第7頁(yè)共7頁(yè)

A.單詞符號(hào)串B.源程序

C.語(yǔ)法單位D.目標(biāo)程序

4.中間代碼生成時(shí)所遵循的是（C）

A.語(yǔ)法規(guī)則B.詞法規(guī)則

C.語(yǔ)義規(guī)則D.等價(jià)變換規(guī)則

5.編譯程序是對(duì)（D）

A.匯編程序的翻譯B.高級(jí)語(yǔ)言程序的解釋執(zhí)行

C.機(jī)器語(yǔ)言的執(zhí)行D.高級(jí)語(yǔ)言的翻譯

6.詞法分析應(yīng)遵循（C）

A.語(yǔ)義規(guī)則B.語(yǔ)法規(guī)則

C.構(gòu)詞規(guī)則D.等價(jià)變換規(guī)則

7.詞法分析器的輸出結(jié)果是（C）

A.單詞的種別編碼B.單詞在符號(hào)表中的位置

C.單詞的種別編碼和屬性值D.單詞屬性值

8.正規(guī)式Ml和M2等價(jià)是指（C）

A.Ml和M2的狀態(tài)數(shù)相等B.Ml和M2的有向弧條數(shù)相等

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

9.詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此，（B）

A.詞法分析器應(yīng)作為獨(dú)立的一遍

B.詞法分析器作為子程序較好

C.詞法分析器分解為多個(gè)過程，由語(yǔ)法分析器選擇使用.

D.詞法分析器并不作為一個(gè)獨(dú)立的階段

10.如果L（M1）=L（M2）,則Ml與M2[A）

A.等價(jià)B.都是二義的

C.都是無二義的D.它們的狀態(tài)數(shù)相等

11.文法G：SfxSxly所識(shí)別的語(yǔ)言是（C）

A.xyxB.（xyx）*c.xnyxn（n20）d.x*yx*

12.文法G描述的語(yǔ)言L（G）是指（A）

A.L（G）=\a\S=>a,aG>B.L（G）=?a|S=>a,a￡（吟uV”）“?

C.L（G）=（a|S=>a,a￡4]D.L（G）=-a\S=>a,ae.（VruV^）"

13.有限狀態(tài)自動(dòng)機(jī)能識(shí)別（C）

A.上下文無關(guān)文法B.上下文有關(guān)文法

C.正規(guī)文法D.短語(yǔ)文法

14.如果文法G是無二義的，則它的任何句子（A）

A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同

B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同

C.最左推導(dǎo)和最右推導(dǎo)必定相同

D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹相同

15.由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是（C）

第8頁(yè)共7頁(yè)

A.短語(yǔ)B.句柄C.句型D.句子

16.文法G：E-E+TlT

T-*T*P|P

Pf(E)|i

則句型P+T+i的句柄為(B)

A.P+TB.PC.P+T-iD.i

17.文法G：S-*b|A|(T)

T-TVS|S

則FIRSTVT(T)=(C)

A.{b,A,(}B.{b,A,))

C.{b,A,(,V)D.{b,A,),V)

18.產(chǎn)生正規(guī)語(yǔ)言的文法為(D)

A.0型B.1型C.2型D.3型

19.任何算符優(yōu)先文法(D)優(yōu)先函數(shù)。

A.有一個(gè)B.沒有C.有若干個(gè)D.可能有若干個(gè)

20.采用自上而下分析，必須(C)

A.消除左遞歸B.消除右遞歸

C.消除回溯D.提取公共左因子

21.在規(guī)范歸約中，用(B)來刻畫可歸約串。

A.直接短語(yǔ)B.句柄C.最左素短語(yǔ)D.素短語(yǔ)

22.有文法G：EfE*T|T

T-*T+i|i

句子l+2*8+6按該文法G歸約，其值為(B)

A.23B.42C.30D.17

23.如果文法是無二義的，那么規(guī)范歸約是指(B)

A.最左推導(dǎo)的逆過程B.最右推導(dǎo)的逆過程

C.規(guī)范推導(dǎo)D.最左歸約的逆過程

24.文法G:S-S+T|T

TfT*P|P

P-(S)|i

句型P+T+i的短語(yǔ)有(B)

A.i,P+TB.P,P+T,i,P+T+iC.P+T+iD.P,P+T,i

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

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

26.后綴式ab+cd+/可用表達(dá)式(B)來表示。

A.a+b/c+dB.(a+b)/(c-d)C.a+b/(c+d)D.a+b+c/d

27.使用間接三元式表示法的主要目的(A)

A.便于優(yōu)化處理B.便于表的修改

C.節(jié)省存儲(chǔ)空間D.生成中間代碼更容易

28.表達(dá)式(1AVB)A(CVD)的逆波蘭表示為(B)

A.-]ABVACDVB.AqBVCDVA

C.ABV-|CDVAD,A-iBVACDV

第9頁(yè)共7頁(yè)

二、判斷題

i.一個(gè)確定有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。

2.設(shè)R和S分別是字母表￡上的正規(guī)式,則有L（R|S）=L（R）UL（S）°（7）

3.自動(dòng)機(jī)Ml和M2的狀態(tài)數(shù)不同，則二者必不等價(jià)。（X）

4.確定有限自動(dòng)機(jī)以及非確定有限自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。（J）

5.對(duì)任意一個(gè)右線性正規(guī)文法G,都存在一個(gè)NFAM,滿足L（G）=L（M）。（V）

6.對(duì)任意一個(gè)右線性正規(guī)文法G,都存在一個(gè)DFAM,滿足L（G）=L（M）.（V）

7.對(duì)任何正規(guī)式e,都存在一個(gè)NFAM,滿足L（M）=L（e）。（V）

8.對(duì)任何正規(guī)式e,都存在一個(gè)DFAM,滿足L（M）=L（e）°（J）

9.從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程是唯一的。（義）

10.詞法分析作為單獨(dú)的一遍來處理較好。（X）

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

12.二義文法不是上下文無關(guān)文法。（義）

13.自上而下分析法是一種“移進(jìn)一歸約”法。（X）

14.文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。（J）

15.產(chǎn)生式是定義語(yǔ)法范疇的一種書寫規(guī)則。（J）

16.要構(gòu)造行之有效的自上而下的分析器，則必須消除左遞歸。（X）

17.如果文法G是無二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（V）

18.自下而上的分析法是一種“移進(jìn)一歸約”法。（V）

19.如果文法G是二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程.（*）

三、填空題

I.解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)代碼）。

2.編譯過程通?？煞譃?個(gè)階段，分別是（詞法分析）、（語(yǔ)法分析）、語(yǔ)義分析與中間代碼產(chǎn)生、代

碼優(yōu)化和目標(biāo)代碼生成。

3.編譯程序工作過程中，第一階段輸入是（源程序），最后階段的輸出為（目標(biāo)代碼）程序。

4.把語(yǔ)法范疇翻譯成中間代碼所依據(jù)的是（語(yǔ)義規(guī)則）。

5.目標(biāo)代碼可以是（匯編）指令代碼或（可重定位）指令代碼或絕對(duì)機(jī)器指令代碼。

6.詞法分析的任務(wù)是：輸入源程序，對(duì)構(gòu)成源程序的（字符串）進(jìn)行掃描和分解。

7.源程序中的錯(cuò)誤通常分為（語(yǔ)法錯(cuò)誤）和（語(yǔ)義錯(cuò)誤）兩大類。

8.（編譯程序）是將源程序翻譯成目標(biāo)程序的程序。

9.一個(gè)上下文無關(guān)文法G包括四個(gè)部分：（終結(jié)符號(hào)）、（非終結(jié)符號(hào)）、（開始符號(hào)）和一組（產(chǎn)生式）。

10.若%na2n…，則稱這個(gè)序列是從四到%的一個(gè)（推導(dǎo)）。

11.設(shè)文法G的開始符號(hào)為S,如果s!a則稱a是L（G）的一個(gè)（句型）。

12.文法G所產(chǎn)生的句子的全體是文法G所定義的（語(yǔ)言）。

13.若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)的兩棵不同的語(yǔ)法樹，則稱這個(gè)文法是（二義文法）。

14.程序語(yǔ)言的單詞符號(hào)一般可分為五種：（關(guān)鍵字）、（標(biāo)識(shí)符）、常數(shù)、（運(yùn)算符）和界符。

15.（確定有限自動(dòng)機(jī)DFA）是非確定有限自動(dòng)機(jī)NFA的一個(gè)特例。

16.對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M,若L（G）=L（M）