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

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

一、判斷題：

1.一個上下文無關文法的開始符，可以是終結符或非終結符。（X）

2.一個句型的直接短語是唯一的。（X）

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

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

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

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

7一個句型一定句子。（x）

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

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

10.編譯過程中，語法分析器的任務是分析單詞是怎樣構成的。（x）

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

12.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。（）

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

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

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

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

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

18.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。（）

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

20.一個優(yōu)先表一定存在相應的優(yōu)先函數。（）

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

22.如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。（）

二、填空題：

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

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

標代碼生成）五個階段。

3.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（）。

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

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

6.掃描器的任務是從（）中識別出一個個（）＜.

7.符號表中的信息欄中登記了每個名字的有關的性質，如（）等等。

8.一個過程相應的DISPLAY表的內容為（）＜.

9.一個句型的最左直接短語稱為句型的（）。

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

1L一個名字的屬性包括（）和（）。

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

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

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

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

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

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

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

19.語法分析是依據語言的（；規(guī)則進行。中間代碼產生是依據語言的（）規(guī)則進行的。

20.一個句型的最左直接短語稱為句型的（

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

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

23.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（）。

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

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

26.對于文法G,僅含終結符號的句型稱為（）o

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

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

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

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

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

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

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

三、名詞解釋題：

1.局部優(yōu)化

2.二義性文法

3.DISPLAY表

4.詞法分析器

5.最左推導

6.語法

7.文法

8.基本塊

9.語法制導翻譯

10.短語

11.待用信息

12.規(guī)范句型

13.掃描器

14.超前搜索

15.句柄

16.語法制導翻譯

17.規(guī)范句型

18.素短語

19.語法

20.待用信息

21.語義

四、簡答題：

1.寫一個文法G,使其語言為不以。開頭的偶數集。

2.已知文法G（S）及相應翻譯方案

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.

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

5.文法G(S)

S-*dAB

A—aA|a

B->Bb|e

描述的語言是什么？

6.證明文法G(S)

S-SaS|E

是二義性的。

7.已知文法法S)

S-BA

A^BS|d

B-*a?.|bS|c

的預測分析表如下

abcd

SS-*BAS-BAS-BA

AAfBSAfBSA-BSA-d

BB-*aAB-bSB-*c

給出句子adccd的分析過程。

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

9.已知文法G(S):

S-*a|(T)

T-T,S|S

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

關系a()

a.>.>

(<.一.

).>.>

(z.>.>

請計算出該優(yōu)先關系表所對應的優(yōu)先函數表。

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

11.目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？

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

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

14.寫一個文法G,使其語言為L(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.

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

16.寫出表達式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.

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

21.寫一個文法G,使其語言為L(G)={anbQ|n>0為奇數，m>0為偶數}

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

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

24.已知文法G[S]

S，S*aF|aF|*aF

Ff+aF|+a

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

25.符號表的作用是什么？符號表查找和整理技術有哪幾種？

五、計算題：

1.設文法G(S):

S一|a|⑴

T-*T,S|S

(1?消除左遞歸；

⑵構造相應的FIRST和FOLLOW集合；

⑶構造預測分析表

2.語句ifEthenS

(1)改寫文法，使之適合語法制導翻譯；

(2)寫出改寫后產生式的語義動作。

3.設文法G(S)：

STT)|a

T-T+S|S

(1?計算FIRSTVT和LASTVT；

(2〕構造優(yōu)先關系表。

4.設某語言的for語句的形式為

fori:=E(I>toE⑵doS

其語義解釋為

i:=E(,)

LIMIT:=E(2)

again:ifi<=LIMITthen

Begin

S;

i:=i+1

gotoagain

End;

(1)寫出適合語法制導翻譯的產生式：

(2)寫出每個產生式對應的語義動作。

5.把語句

whilea<10do

ifc>0thena:=a+l

elsea:=a*3-l;

翻譯成四元式序列。

6.設有基本塊

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

假設基本塊出口時只有M還被弓用，請寫出優(yōu)化后的四元序列。

7.已知文法法S)

S-ar|⑴

T-T,S|S

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

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

8.對于C語言doSwhileE語句

(1)改寫文法，使之適合語法制導翻譯；

(2)寫出改寫后產生式的語義動作。

9.已知文法G(S)

S-*aAcRp

A-*Ab|b

B-*d

(1)給出句子abbcde的最左推導及畫出語法樹；

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

10.設文法G(S):

S-(T)|aS|a

T-T,S|S

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

⑵構造相應的FIRST和FOLLOW集合；

⑶構造預測分析表。

11.把語句

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的最左推導及畫出語法樹；

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

13.設文法G(S)：

S-*T|SvT

T-U|TAU

U-i|-U

(1)計算FIRSTVT和LASTVT；

(2)構造優(yōu)先關系表。

參考答案

一、是非題：

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.（最右推導）

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

3.（二義性的）

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

5.（單詞符號），（語法單位）。

6.（源程序），（單詞符號）

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

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

9.（句柄）

10.（棧式），（堆式）

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

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

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

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

15.（分析表），（符號棧）

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

17.（初），（終）

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

19.（語法），（語義）

20.（句柄）

21.（LL（1）文法）

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

23.（二義性文法）

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

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

26.（句子）

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

28.（單詞符號），（語法單位）

2g.（局部優(yōu)化）

30.（分析表），（符號棧）

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

32.（指令訪問主存次數加1）

33.（最左素短語）

三、名詞解釋題：

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

2.二義性文法----如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。

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

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

5.最左推導---任何一步a=>3都是對a中的最右非終結符替換。

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

7.文法----描述語言的語法結構的形式規(guī)則。

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

語句，出口就是其中的最后一個語句。

第1頁共7頁

9.語法制導翻譯----在語法分析過程中，根據每個產生式所對應的語義子程序進行翻譯的辦法叫做語法

制導翻譯。*

10.短語---令G是一個文法，S劃文法的開始符號，假定aB6是文法G的一個句型，如果有S=>

aA6且A=±5B,則稱B是句型aB6相對非終結符A的短語。

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

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

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

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

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

15.句柄-----個句型的最左直接短語。

16.語法制導翻譯---在語法分析過程中，根據每個產生式所對應的語義程序進行翻譯的方法叫做語

法制導翻譯。

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

18.素短語---素短語是指這樣一個短語，至少含有一個終結符，并且，除它自身外不再含任何更小的

素短語。

19.語法---是組規(guī)則，用它可形成和產生一個合式的程序。_

20.待用信息----如果在一個基本塊中，四元式i對A定值，的元式j要引用A值，而從i到j之間沒

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

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

四、簡答題：

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ī)范歸約過程：

步驟符號棧輸入串動作

0#b(aa)b#預備

1#b(aa)b#移進

2#b(aa)btt移進

3#b(aa)b#移進

4#b(Aa)b#歸約

5#b(Ma)b#移進

6#b(Ma)b#移進

7#b(Bb#歸約

8#bAb#歸約

9#bAb移進

10#Sn接受

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

傳值A=2,B=4

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

6.證明：

因為文法G[S]存在句子aa有兩個不同的最左推導，所以文法G[S]是是二義性的。

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

第2頁共7頁

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

7.句子adccd的分析過程：

步驟符號棧輸入串產生式

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.目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。

應著重考慮的問題：

(1)如何使生成的目標代碼較獨；

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

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

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

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

14.文法G[S]:

S-aB|a

B—be|bBc

15.傳值a=2

傳地址a=15

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

三元序列：oparglarg2

第3頁共7頁

(1)—Cd

⑵*b(1)

(3)/⑵<?

(4)+a(3)

17.證明：

因為文法G[S]存在句子()有兩個不同的最左推導，所以文法G[S]是是二義性的。

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

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

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

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

由于過程嵌套允許內層過程引用外層過程定義的數據，因此，當一個過程運行時必須跟蹤它的所有外

層過程的最新活動記錄起始地址，display表就是用于登記每個外層過程的最新活動記錄起始地址。

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別是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)的各種名字及其信息，以及了解各階段的進展狀況。

主要技術：線性表，對折查找，雜奏技術。

五、計算題：

1.

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

S1|a|(T)'

T-ST'|S

V|￡

此文法無左公共左因子。

(2)構造相應的FIRST和FOLLOW集合：

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

第4頁共7頁

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

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

(3)構造預測分析表：

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頁共7頁

(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.最左推導

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

短語

((T,S),a)

(T,S),a

(T,S)

T,S

a

直接短語

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)短語：aAbcde,Ab,d

素短語：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頁共7頁

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)短語i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F

素短語i,E+T

最左素短語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<..>.><.

一<..>.><.

一、單項選擇題

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

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

B.使程序的結構更加清晰

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

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

2.不可能是目標代碼的是（D）

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

C.絕對指令代碼D.中間代碼

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

第7頁共7頁

A.單詞符號串B.源程序

C.語法單位D.目標程序

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

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

C.語義規(guī)則D.等價變換規(guī)則

5.編譯程序是對（D）

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

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

6.詞法分析應遵循（C）

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

C.構詞規(guī)則D.等價變換規(guī)則

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

A.單詞的種別編碼B.單詞在符號表中的位置

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

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

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

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

9.詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確，因此，（B）

A.詞法分析器應作為獨立的一遍

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

C.詞法分析器分解為多個過程，由語法分析器選擇使用.

D.詞法分析器并不作為一個獨立的階段

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

A.等價B.都是二義的

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

11.文法G：SfxSxly所識別的語言是（C）

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

12.文法G描述的語言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)自動機能識別（C）

A.上下文無關文法B.上下文有關文法

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

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

A.最左推導和最右推導對應的語法樹必定相同

B.最左推導和最右推導對應的語法樹可能不同

C.最左推導和最右推導必定相同

D.可能存在兩個不同的最左推導，但它們對應的語法樹相同

15.由文法的開始符經0步或多步推導產生的文法符號序列是（C）

第8頁共7頁

A.短語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.產生正規(guī)語言的文法為(D)

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

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

A.有一個B.沒有C.有若干個D.可能有若干個

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

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

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

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

A.直接短語B.句柄C.最左素短語D.素短語

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

T-*T+i|i

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

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

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

A.最左推導的逆過程B.最右推導的逆過程

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

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

TfT*P|P

P-(S)|i

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

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

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

A.指示器B.臨時變量C.符號表D.程序變量

26.后綴式ab+cd+/可用表達式(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é)省存儲空間D.生成中間代碼更容易

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

A.-]ABVACDVB.AqBVCDVA

C.ABV-|CDVAD,A-iBVACDV

第9頁共7頁

二、判斷題

i.一個確定有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。

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

3.自動機Ml和M2的狀態(tài)數不同，則二者必不等價。（X）

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

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

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

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

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

9.從一個句型到另一個句型的推導過程是唯一的。（義）

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

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

12.二義文法不是上下文無關文法。（義）

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

14.文法是描述語言的語法結構的形式規(guī)則。（J）

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

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

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

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

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

三、填空題

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

2.編譯過程通常可分為5個階段，分別是（詞法分析）、（語法分析）、語義分析與中間代碼產生、代

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

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

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

5.目標代碼可以是（匯編）指令代碼或（可重定位）指令代碼或絕對機器指令代碼。

6.詞法分析的任務是：輸入源程序，對構成源程序的（字符串）進行掃描和分解。

7.源程序中的錯誤通常分為（語法錯誤）和（語義錯誤）兩大類。

8.（編譯程序）是將源程序翻譯成目標程序的程序。

9.一個上下文無關文法G包括四個部分：（終結符號）、（非終結符號）、（開始符號）和一組（產生式）。

10.若%na2n…，則稱這個序列是從四到%的一個（推導）。

11.設文法G的開始符號為S,如果s!a則稱a是L（G）的一個（句型）。

12.文法G所產生的句子的全體是文法G所定義的（語言）。

13.若一個文法存在某個句子對應的兩棵不同的語法樹，則稱這個文法是（二義文法）。

14.程序語言的單詞符號一般可分為五種：（關鍵字）、（標識符）、常數、（運算符）和界符。

15.（確定有限自動機DFA）是非確定有限自動機NFA的一個特例。

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