編譯原理復習題及答案

一、選擇題

1.一個正規語言只能對應(B)

A一個正規文法B一個最小有限狀態自動機2.文法G[A]：

ATEA—aBB->AbB->a是(A)

A正規文法B二型文法3.下面說法正確的是(A)

A一個SLR(1)文法一定也是LALR(1)文法B一個LR(1)文法一定也是

LALR(l)文法

4.一個上下文無關文法消除了左遞歸，提取了左公共因子后是滿足

口(1)文法的公)

A必要條件B充分必要條件5.下面說法正確的是(B)

A一個正規式只能對應一個確定的有限狀態自動機B一個正規語言可

能對應多個正規文法

6.算符優先分析與規范歸約相比的優點是(A)

A歸約速度快B對文法限制少7.一個LR(1)文法合并同心集后若不

是LALR(l)文法(B)

A則可能存在移進/歸約沖突B則可能存在歸約/歸約沖突

C則可能存在移進/歸約沖突和歸約/歸約沖突8.下面說法正確的是

ALe某是一個詞法分析器的生成器BYacc是一個語法分析器9.下面

說法正確的是(A)

A一個正規文法也一定是二型文法

B一個二型文法也一定能有一個等價的正規文法10.編譯原理是對

。。

A、機器語言的執行B、匯編語言的翻譯

C、高級語言的翻譯

D、高級語言程序的解釋執行C.FORTRAN

D.PASCAL

11.(A)是一種典型的解釋型語言。A.BASICB.C

12.把匯編語言程序翻譯成機器可執行的目標程序的工作是由(B)完成

的。A.編譯器B.匯編器C解釋器D.預處理器13.用高級語言編寫的程序經編

譯后產生的程序叫(B)A,源程序B.目標程序C.連接程序14.(C)不是編譯

程序的組成部份。A.詞法分析程序B.代碼生成程序

D.解釋程序D.語法分析程序

C.設備管理程序

15.通常一個編譯程序中，不僅包含詞法分析，語法分析，語義分析，

中間代碼生成，代碼優化，目標代碼生成等六個部份，還應包括(C)。

A.摹擬執行器B.解釋器C.表格處理和出錯處理D.符號執行器16.編

譯程序絕大多數時間花在(D)上。A.出錯處理B.詞法分析

C.目標代碼生成

D.表格管理

17.源程序是句子的集合，(B)可以較好地反映句子的結構。A.線性

表B.樹C.徹底圖18.詞法分析器的輸出結果是(D)。A、單詞自身值C、

單詞的種別編碼19.詞法分析器不能(D)A.識別出數值常量D.堆

棧

R、單詞在符號表中的位置口、單詞的種別編碼和自身值R.過濾源程

序中的注釋D.發現括號不匹配

C.掃描源程序并識別記號

20.文法：G：S—某S某|y所識別的語言是(D)。

A、某y某B、(某y某)某21.如果文法G是無二義的，則它的任何句

子a(A)A.最左推導和最右推導對應的語法樹必然相同

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

右推導必然相同

C、某某y某某

D、某ny某n(山0)

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

則文法(A)二義性的。

A.可以是B.一定不是

C.一定是

23.(B)這樣一些語言，它們能被確定的有窮自動機識別，但不能用

正則表達式表示。A.存在B.不存在C無法判定是否存在24.給定文法A

->bA|ca,為該文法句子的是(C)A.bbaB.cabC.bca

D.cba

25.設有文法G[S]：SSl|SO|Sa|Sc|a|b|c,下列符號串中是該文法的句

子有(D)A.ab0B.a0c01C.a0b0aD.bcl026.文法G產生的(D)的全體是該文法

描述的語言。A.句型B.終結符集C.非終結符集27.若文法G定義的語言

是無限集，則文法必然是(A)A.遞歸的B.上下文無關的C.二義性的28.

描述一個語言的文法是(B)A,惟一的B.不惟一的29.一個文法所描述的

語言是(A)A.惟一的B.不惟一的30.采用自上而下分析，必須

(A)oA、消除回溯

C、消除右遞歸

C.可能惟一C.可能惟一

B、消除左遞歸

D.句子

D.無二義性的

D、提取公共左因子

31.編譯過程中，語法分析器的任務是(A)①分析單詞的構成②分析

單詞串如何構成語句③分析沿句是如何構成程序④分析程序的結構

A.②?B.④C.①②@④D.②③④32.詞法分析器的輸入是(A)o

A.符號串B.源程序C.語法單位D.目標程序33.兩個有窮自動機

等價是指它們的(C)。A.狀態數相等

C.所識別的語言相等

B.有向弧數相等

D.狀態數和有向弧數相等

34.若狀態k含有項目—且僅當輸入符號a￡FOLLOW(A)

時，才用規則“A—a”歸約的語法分析方法是(D)。A.LALR分析法B.

LR(O)分析法C.LR(1)分析法D.SLR⑴分析法35.若a為終結符，則A

-crap為(BA頁目。A.歸約B.移進

C.接受

D.待約

36.在使用高級語言編程時，首先可通過編譯程序發現源程序的全部

和部份(A)錯誤。A.語法B.語義C.語用D.運行

37.喬姆斯基(Chomky)把文法分為四種類型，即0型、1型、2型、3型。

其中3型文法是(B)A.非限制文法B.正則文法C.上下文有關文法D.上下文無

關文法38.一個句型中的(A)稱為該句型的句柄。A.最左直接短語B.最右

直接短語

C.終結符D.非終結符

39.在自底向卜?的語法分析方法中，分析的關鍵是(D)

A.尋覓句柄B.尋覓句型C.消除遞歸40.在自頂向下的語法分析方法

中，分析的關鍵是(C)A.尋覓句柄B.尋覓句型C.消除遞歸

D.選擇候選式D.選擇候選式

41.在LR分析法中，分析棧中存放的狀態是識別規范句型(C)的DFA

狀態。A.句柄B.前綴C.活前綴D.LR(O)項目

42.一個上下文無關文法G包括四個組成部份，它們是一組非終結符

號，一組終結符號，一個開始符號，以及一組(B)A.句子B.產生式C.單詞

D.句型43.詞法分析器用于識別(C)A.句子B.產生式

C.單詞

D.句型D.目標程序D.代碼生成D.狀態集D.句子

44.編譯程序是一種(B)A.匯編程序B.翻譯程序

C.解釋程序

45.按邏輯上劃分，編譯程序第三步工作是(A)A.語義分析B.詞法分

析C.語法分析46.在語法分析處理中，FIRST集合、FOLLOW集合均是

(B)A.非終結符集B.終結符集C字母表47.編譯程序中語法分析器接收以

(A)為單位的輸入。A.單詞B.表達式C.產生式48.編譯過程中，語法

分析器的任務就是(B)A.分析單詞是怎樣構成的

C.分析語句和說明是如何構成程序的

B.分析單詞串是如何構成語句和說明的D.分析程序的結構

D.個數是常量D.圖靈機D.語義分析

49.若一個文法是遞歸的，則它所產生的語言的句子(A)。A.是無窮

多個B.是有窮多個C.是可枚舉的50.識別上下文無關語言的自動機是

(C)A.下推自動機B.NFA51.編譯原理各階段工作都涉及(B)A.詞法分析B.

表格管理

C.DFA

C.語法分析

52.正則表達式R1和R2等價是指(C)

A.R1和R2都是定義在一個字母表上的正則表達式

B.R1和R2中使用的運算符相同C.R1和R2代表同一正則集D.R1和R2

代表不同正則集

53.已知文法G[S]:S-A1,A—A1|SO|O。與G等價的正規式是(C)

A.O(O|1)某B.1某|0某1C.O(1|10)某154.與(a|b)某(a|b)等價的正規式是

(C)oAa某|b某B.(ab)某(a|b)55.(D)文法不是LL(1)的。A.遞歸B.右遞歸

C.(a|b)(a|b)某C.2型

D.l(lOIOl)某OD.(alb)某

D.含有公共左因子的

56.給定文法A—bA|cc,則符號串

①cc②bcbc③bcbcc④bccbcc⑤bbbcc中，是該文法句子的是

(D)A.①B.③④⑤C.②④D.①@57.LR(1)文法都是0

A.無二義性且無左遞歸

C.無二義性但可能是左遞歸

B.可能有二義性但無左遞歸D.可以既有二義性又有左遞歸

D.7

58.文法E-E+E|E某Eli的句子i某i+i某i有(?？貌煌恼Z法樹。

A.1B.3C.559.文法S->aaS|abc定義的語言是(C)。

A.{a2kbe|k>O}B.{akbc|kX)}C.{a2k-lbc|kX)}C.接受項目C.移進/歸約

D.{akakbc|k>O}D彳寺約項目D.歸約/歸約

60.若B為非終結符，則A—.B為(D)。

A.移進項目B.歸約項目61.同心集合并可能會產生新的(D)沖突。A.二

義B.移進/移進

62.就文法的描述能力來說，有(C)

A.SLR(l)LR(0)B.LR(l)LR(0)C.SLR(1)LR(1)D.無二義文法

LR(1)63.如圖所示自動機M,請問下列哪個字符串不是M所能識別的(D)。

A.bbaaB.abbaC.ababD.aabb

64.有限狀態自動機能識別(C)

A.上下文無關語言B.上下文有關語言

C.正規語言

D0型文法定義的語言

65.已知文法G是無二義的，則對G的任意句型a(A)

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

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

導必然相同

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

不是DFA的成份

A.有窮字母表B.多個初始狀態的集合

C.多個終態的集合

D.轉換函數

D.a+b某c+d

D.(a(b+c)>4-d

67.與逆波蘭式(后綴表達式)ab+c某d+對應的中綴表達式是(B)

A.a+b+c某dB.(a+b)某c+dC.(a+b)某(c+d)68.后綴式abc+d+可用表達式

(B)來表示。A.((a+b)c)+dB.(a+(bc))+d69.表達式A某(B~C某

(C/D))的后綴式為(B)。A.ABC-CD/某某B.ABCCD/某-某

C.(a(b+€))-Kj

C.ABC.某CD/某D.以上都不對

70.(D)不是NFA的成份。A.有窮字母表B.初始狀態集合C.終止狀態

集合D.有限狀態集合

二、問答題

1.將文法G圖改寫為等價的G[S],使GIS]不含左遞歸和左公共因

子。G[S]：S-bSAe|bAA—Ab|d答：

文法G[S]改寫為等價的不含左遞歸和左公共因子的G[S]為：S

bBB-SAe|AA—dA'

A'—bAg

2.將文法G[S]改寫為等價的G1S],使G[S]不含左遞歸和左公共因

子。G[S]：S—SAe|Ae

A—dAbA|dA|d答：

文法G[S]改寫為等價的不含左遞歸和左公共因子的GTS]為：S

TAeSSTAeS|￡ATlA'A'TAB|￡BTbA|￡

3.將文法G[S]改寫為等價的G[S],使GIS]不含左遞歸和左公共因

子。G[S]：S-[AA—B]|ASB—aB|a答：

文法G⑶改寫為等價的不含左遞歸和左公共因子的G[S]為：S

->[AA.B]A'A'—SA佃B—aB，

BJB|￡

4.判斷下面文法是否為LL(1)文法，若是,請構造相應的LL(1)分析

表。S—>aH

H—>aMd|dM-Ab|8A-^aM|e答：

首先計算文法的FIRST集和FOLLOW集如下表。

文法的FIRST集和FOLLOW集非終結符FIRST集FOLLOW集

S{a}........{#}…H{#}…{a,d}.….M{a,e,￡}{d,b}A.…{a,

e).....由于predict(H—>aMd)predict(H—>d)={a}Clbcxh00d=

predict(M-Ab)npredict(M一￡)={a,e}A{d,b}=predict(A

—aM)npredictA—e)={a}D{e}二所以該文法是LL⑴文法，LL(1)分析表如

下表。adbS—>aH.H—aMd—dM—Ab.—g->￡A—aM.5.判斷下面

文法是否為LL(1)文法，若是，請構造相應的LL(1)分析表。

S—aDD—STe|￡T->bH|HH->dB答：

首先計算文法的HRST集和FOLLOW集如下表。非終結符HRST

集FOLLOW集S{a}{#,b,d,e}.D{a,e}{#,b,d,e}

e—>Ab-^e.#

在項目集10中：有移進項目E一?aTd和歸約項目E1?存在移

進■歸約沖突，所以G不是LR(0)文法。

*

若產生式排序為：(0)S，TE(l)E-aTd(2)E—e(3)T-Eb(4)T-aG的

LR(0)項目集族及識別活前綴的DFA如下圖：

由產生式知：

Follow(E)={#,b}Follow(T)=zgkign0在10,12中：

Follow(E)n{a}={#,陰口歸}=在15中：

Follow(E)A{a}={#,b}Cl{a}=Follow(T)A{a}=0c5l62dA{a}=

Follow(T)AFollow(E)=c5qe0loA{#,b}=

所以在10,12,15中的移進.歸約和歸約.歸約沖突可以由Follow集解決，所以

G，是SLR(l)文法。構造的SLR⑴分析表如下表：

ACTIONGOTOnameabd#ETOS2r2r211acc2s5r2r2433s64s75s5r2r4r243

67rlr3rll5.給出文法G[S]的LR⑴項目集規范族中10項目集的全體

項目。G[S]為：S-BD|DB—aDgD—B

10:

答：10：

16.給出文法G[S]的LR(1)項目集規范族中10項R集的全體項go

G[S]為：S-D;D|DDTDB|BB—a|b

10:

答：I。

17.給出文法G[S]的LR(1)項目集規范族中10項目集的全體項目。

G[S]為：S^S;V|W->VaA|AA->b(S)18

10:

答：10：

18.文法G[M]及其LR分析表如下，請給出對串dbba#的分析過程。

G[M]:1)M—VbA

2)VX)Vf

4)A—a5)A一Aba

6)A一

8ACTIONGOTOnamebda#MAOr3S311acc2S43r24r6S5r665r4r46S7r17S88r5r5

答：對串dbba#的分析過程如下表步驟狀態棧文法符號棧剩余輸入符號動

作#dbba#移進10#dbba#用V-d歸約203#Vbba#移進302#Vbba#用A一￡

歸約4024#VbAba#50246#VbAba#移進602467#VbAba#移進7024678#VbA#用

A—Aba歸約80246#M#用M—VbA歸約901接受

19.文法G[S]及其LR分析表如下，請給出對輸入串da;aoa#的分析

過程。

G[S]:0)S'—S

l)S—dSoS

2)S^dS

3)S一S;S

V2

4)S^aname012345678dS2S2S2S2aS3r4S7r3rlACTION;S4r4S4r3S4aS3S

3S3S3#accr4r2r3rlGOTOS1568輸入串da;aoa#的分析過程如下表：步

驟狀態棧文法符號棧

#10#d202#da3023#dS4025#dS;50254#dS;a602543#dS;S702546#dS8025#dSo

90257#dSoa1002573#dSoS1102578#S1201剩余輸入符號

da;aoa#a;aoa#;aoa#;aoa#aoa#oa#oa#oa#a####動作移進移進用S—a歸約移進

移進用S—a歸約用S-S;S歸約移進移進用S->a歸約用S-dSoS歸約接受

20.文法G[M]及其LR分析表如下，請給出對串dada#的分析過程。

G|M]:1)S—VdB

2)VT

3)Vf