編譯原理復習題及答案解析

編譯原理復習題及答案

一、選擇題

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

A一個正規(guī)文法B一個最小有限狀態(tài)自動機2.文法G[A]：

A-￡AfaBB-AbB-a是(A)

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

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

是LALR(1)文法

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

(1)文法的(A)

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

A一個正規(guī)式只能對應一個確定的有限狀態(tài)自動機B一個正規(guī)語言可能對

應多個正規(guī)文法

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

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

LALR(1)文法(B)

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

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

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

正確的是(A)

A一個正規(guī)文法也一定是二型文法

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

A、機器語言的執(zhí)行B、匯編語言的翻譯

C、高級語言的翻譯

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

D.PASCAL

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

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

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

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

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

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

C.設備管理程序

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

間代碼生成，代碼優(yōu)化，目標代碼生成等六個部分，還應包括(C)。A.模擬執(zhí)

行器B.解釋器C.表格處理和出錯處理D.符號執(zhí)行器16.編譯程序絕大多數(shù)

時間花在(D)上。A.出錯處理B.詞法分析

C.目標代碼生成

D.表格管理

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

樹C.完全圖18.詞法分析器的輸出結(jié)果是(D)。A、單詞自身值

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

D.堆棧

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

的注釋D.發(fā)現(xiàn)括號不匹配

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

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

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

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

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

必定相同

C、某某y某某

D、某ny某n(n-0)

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

法(A)二義性的。

A.可以是B.一定不是

C.一定是

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

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

為該文法句子的是(C)A.bbaB.cabC.bca

D.cba

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

子有(D)A.abOB.aOcOlC.aObOaD.bcl026.文法G產(chǎn)生的(D)的全體是該文法描述

的語言。A.句型B.終結(jié)符集C.非終結(jié)符集27.若文法G定義的語言是無限

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

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

的B.不唯一的30.采用自上而下分析，必須(A)。A、消除回溯

C、消除右遞歸

C.可能唯一C.可能唯一

B、消除左遞歸

D.句子

D.無二義性的

D、提取公共左因子

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

串如何構(gòu)成語句③分析語句是如何構(gòu)成程序④分析程序的結(jié)構(gòu)

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

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

是指它們的(C)。A.狀態(tài)數(shù)相等

C.所識別的語言相等

B.有向弧數(shù)相等

D.狀態(tài)數(shù)和有向弧數(shù)相等

34.若狀態(tài)k含有項目“AfQ?”，且僅當輸入符號a￡FOLLOW(A)時，

才用規(guī)則“A-a”歸約的語法分析方法是(D)。A.LALR分析法B.LR(O)分析

法C.LR(1)分析法D.SLR⑴分析法35.若a為終結(jié)符，貝I」Afa*aP為(B)

項目。A.歸約B.移進

C.接受

D.待約

36.在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部和部

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

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

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

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

接短語

C.終結(jié)符D.非終結(jié)符

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

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

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

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

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

態(tài)。A.句柄B.前綴C.活前綴D.LR(0)項目

42.一個上下文無關文法G包括四個組成部分，它們是一組非終結(jié)符號，

一組終結(jié)符號，一個開始符號，以及一組(B)A.句子B.產(chǎn)生式C.單詞D.句型

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

C.單詞

D.句型D.目標程序D.代碼生成D.狀態(tài)集D.句子

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

C.解釋程序

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

語法分析46.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合均是(B)A.非終結(jié)

符集B.終結(jié)符集C.字母表47.編譯程序中語法分析器接收以(A)為單位的輸

入。A.單詞B.表達式C.產(chǎn)生式48.編譯過程中，語法分析器的任務就是(B)A.

分析單詞是怎樣構(gòu)成的

C.分析語句和說明是如何構(gòu)成程序的

B.分析單詞串是如何構(gòu)成語句和說明的D.分析程序的結(jié)構(gòu)

D.個數(shù)是常量D.圖靈機D.語義分析

49.若一個文法是遞歸的，則它所產(chǎn)生的語言的句子(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-ALA-Al|S0|0o與G等價的正規(guī)式是(C)

A.0(0|l)某B.1某|0某1C.O(1|1O)某154.與(a|b)某(a|b)等價的正規(guī)

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

遞歸

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

D.1(10|01)某OD.(a|b)某

D.含有公共左因子的

56.給定文法A-*bA|cc,則符號串①cc②bcbc③bcbcc④bccbcc⑤bbbcc

中，是該文法句子的是(D)A.①B.③④⑤C.②④D.①⑤57.LR(1)文法都是()

A.無二義性且無左遞歸

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

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

D.7

58.文法E-E+E|E某E|i的句子i某i+i某i有(C)棵不同的語法樹。

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

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

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

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

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

B.移進/移進

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

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

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

A.bbaaB.abbaC.ababD.￡abb

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

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

C.正規(guī)語言

D.0型文法定義的語言

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

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

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

定相同

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

DFA的成分

A.有窮字母表B.多個初始狀態(tài)的集合

C.多個終態(tài)的集合

D.轉(zhuǎn)換函數(shù)

D.a+b某c+d

D.(a(b+c))+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+c))+d

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

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

D.有限狀態(tài)集合

二、問答題

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

子。G[S]：S-*bSAe|bAA-*Abd答：

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

S—bBB-SAe|AA-dA'

A'-bA'|e

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

子。G[S]：S->SAe|Ae

A-dAbAdA|d答：

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

S-AeS'S'-AeS'|￡A->dA,-ABIeB-bA|e

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

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

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

Sf[AAfB]A'A'-SA'|￡B-aB'

B，fB|￡

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

S-*aH

H-*aMd|dM-*Ab|eA-*aMe答:

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

文法的FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集

S{a}..................{#}...H{#}.??{a,d}...........M{a,e,e){d,b}A....{a,

e).........由于predict(HfaMd)Apredict(H—d)-{a}Clzkpuhbh-

predict(MfAb)PIpredict(M-*E)={a,e}A{d,b}=predict

(A-*aM)-predict(Afe):{a}Cl{e}二所以該文法是LL(1)文法，LL(1)分析

表如下表。adbS-aH.H-aMd-d.M-Ab.-￡-￡A-aM.5.判斷下面文法是否

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

S-*aDD-STe|eT-bH|HH->d￡答：

首先計算文法的FIRST集和FOLLOW集如下表。非終結(jié)符FIRST集FOLLOW

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

efAbfe.#

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

存在移進-歸約沖突，所以G不是LR(O)文法。

若產(chǎn)生式排序為：(O)S'-E(l)EfaTd(2)Ef￡(3)TfEb(4)T-a

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

由產(chǎn)生式知：

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

Follow(E)n{a}={#,b}C{a}二在15中：

Follow(E)A{a}={#?b)A(a)=Follow(T)C{a}=mtaxfpuQ(a}=

Follow(T)nFollow(E)=xllzzjvn{#,b}=

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

G'是SLR(l)文法。構(gòu)造的SLR(1)分析表如下表:

ACTI0NG0T0nameabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r243

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

目。G[S]為:S-*BD|DB-aD|bD-*B

10:

答：10：

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

為：SfD;D|DDfDB|BBfa|b

10:

答：10:

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

為：S->S;V|W->VaA|AA->b(S)|e

10:

答：10:

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

G[M]:l)M->VbA

2)V-d3)V-e

4)A-a5)AfAba

6)A-￡ACTI0NG0T0namebda#MA0r3S311acc2s43r24r6s5r665r4r46s7rl7S8

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

作#(1帥@#移進10#dbba#用V-d歸約203#Vbba#移進302#Vbba#用A-*￡歸約

4024#VbAba#50246#VbAba#移進602467#VbAba#移進7024678#VbA#用A-Aba歸

約80246#M#用MfVbA歸約901接受

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

程。

G[S]:0)SzfS

1)S-dSoS

2)S-dS

3)S-S;S

V2

4)S-aname012345678dS2S2S2S2aS3r4S7r3rlACTI0N;S4r4S4r3S4aS3S3S3S

3#accr4r2r3rlG0T0S1568答：輸入串da;aoa#的分析過程如下表：步驟狀態(tài)棧

文法符號棧

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

#dSoal002573#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