編譯原理復習題及答案一、 選擇題1 一個正規語言只能對應(B)A 一個正規文法B 一個最小有限狀態自動機2 文法GA：A AaB BAb Ba是(A)A 正規文法B 二型文法3 下面說法正確的是(A)A 一個SLR（1）文法一定也是LALR（1）文法B 一個LR（1）文法一定也是LALR（1）文法4 一個上下文無關文法消除了左遞歸，提取了左公共因子后是滿足LL（1）文法的(A)A 必要條件B 充分必要條件5 下面說法正確的是(B)A 一個正規式只能對應一個確定的有限狀態自動機B 一個正規語言可能對應多個正規文法6 算符優先分析與規范歸約相比的優點是(A)A 歸約速度快B 對文法限制少7 一個LR（1）文法合并同心集后若不是LALR（1）文法(B)A 則可能存在移進/歸約沖突B 則可能存在歸約/歸約沖突C 則可能存在移進/歸約沖突和歸約/歸約沖突8 下面說法正確的是(A)A Lex是一個詞法分析器的生成器B Yacc是一個語法分析器9 下面說法正確的是(A)A 一個正規文法也一定是二型文法B 一個二型文法也一定能有一個等價的正規文法10 編譯原理是對(C)。A、機器語言的執行B、匯編語言的翻譯C、高級語言的翻譯D、高級語言程序的解釋執行11 用高級語言編寫的程序經編譯后產生的程序叫(B)A源程序B目標程序C連接程序D解釋程序12 (C)不是編譯程序的組成部分。A.詞法分析程序B.代碼生成程序C.設備管理程序D.語法分析程序13 通常一個編譯程序中，不僅包含詞法分析，語法分析，語義分析，中間代碼生成，代碼優化，目標代碼生成等六個部分，還應包括(C)。A模擬執行器B解釋器C表格處理和出錯處理 D符號執行器14 源程序是句子的集合，(B)可以較好地反映句子的結構。A. 線性表B. 樹C. 完全圖D. 堆棧15 詞法分析器的輸出結果是(D)。A、單詞自身值B、單詞在符號表中的位置C、單詞的種別編碼D、單詞的種別編碼和自身值16 詞法分析器不能(D)A. 識別出數值常量B. 過濾源程序中的注釋C. 掃描源程序并識別記號D. 發現括號不匹配17 文法：G：SxSx | y所識別的語言是(D)。A、xyxB、(xyx)*C、x*yx*D、xnyxn (n0)18 如果文法G是無二義的，則它的任何句子 (A)A最左推導和最右推導對應的語法樹必定相同B最左推導和最右推導對應的語法樹可能不同C最左推導和最右推導必定相同D可能存在兩個不同的最左推導，但它們對應的語法樹相同19 正則文法(A)二義性的。A. 可以是B. 一定不是C. 一定是20 (B)這樣一些語言，它們能被確定的有窮自動機識別，但不能用正則表達式表示。A. 存在B. 不存在C. 無法判定是否存在21 給定文法AbA | ca，為該文法句子的是(C)A. bbaB. cabC. bcaD. cba22 設有文法GS：SS1|S0|Sa|Sc|a|b|c，下列符號串中是該文法的句子有(D)A. ab0B. a0c01C. a0b0aD. bc1023 描述一個語言的文法是(B)A唯一的B. 不唯一的C. 可能唯一24 一個文法所描述的語言是(A)A唯一的B. 不唯一的C. 可能唯一25 采用自上而下分析，必須(A)。A、消除回溯B、消除左遞歸C、消除右遞歸D、提取公共左因子26 編譯過程中，語法分析器的任務是(A) 分析單詞的構成 分析單詞串如何構成語句 分析語句是如何構成程序 分析程序的結構A. B. C. D. 27 詞法分析器的輸入是( A)。A符號串 B源程序 C語法單位 D目標程序28 兩個有窮自動機等價是指它們的(C)。A狀態數相等 B有向弧數相等C所識別的語言相等D狀態數和有向弧數相等29 若狀態k含有項目“A ”，且僅當輸入符號aFOLLOW(A)時，才用規則“A ”歸約的語法分析方法是(D)。ALALR分析法BLR(0)分析法CLR(1)分析法 DSLR(1)分析法30 若a為終結符，則A a為(B)項目。A歸約B移進C接受D待約31 在使用高級語言編程時,首先可通過編譯程序發現源程序的全部和部分(A)錯誤。A. 語法B. 語義C. 語用D. 運行32 喬姆斯基(Chomsky)把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是(B)A. 非限制文法B. 正則文法C. 上下文有關文法D. 上下文無關文法33 一個上下文無關文法G包括四個組成部分，它們是一組非終結符號，一組終結符號，一個開始符號，以及一組(B)A. 句子B. 產生式C. 單詞D. 句型34 詞法分析器用于識別(C)A. 句子B. 產生式C. 單詞D. 句型35 編譯程序是一種(B)A. 匯編程序B. 翻譯程序C. 解釋程序D. 目標程序36 按邏輯上劃分，編譯程序第三步工作是(A)A. 語義分析B. 詞法分析C. 語法分析D. 代碼生成37 在語法分析處理中，FIRST集合、FOLLOW集合均是(B)A. 非終結符集B.終結符集C. 字母表D. 狀態集38 編譯程序中語法分析器接收以(A)為單位的輸入。A. 單詞B. 表達式C. 產生式D. 句子39 編譯過程中，語法分析器的任務就是(B)A. 分析單詞是怎樣構成的B. 分析單詞串是如何構成語句和說明的C. 分析語句和說明是如何構成程序的D. 分析程序的結構40 若一個文法是遞歸的，則它所產生的語言的句子(A)。A.是無窮多個B.是有窮多個C.是可枚舉的D.個數是常量41 識別上下文無關語言的自動機是(C)A. 下推自動機B. NFAC. DFAD. 圖靈機42 編譯原理各階段工作都涉及(B)A.詞法分析B.表格管理C.語法分析D.語義分析43 正則表達式R1和R2等價是指(C)A. R1和R2都是定義在一個字母表上的正則表達式B. R1和R2中使用的運算符相同C. R1和R2代表同一正則集D. R1和R2代表不同正則集44 已知文法GS:SA1， AA1|S0|0。與G 等價的正規式是(C)A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*045 與(a|b)*(a|b)等價的正規式是(C)。A.a*| b*B.(ab)*(a|b)C. (a|b)(a|b)*D.(a|b)*46 (D)文法不是LL(1)的。A. 遞歸B. 右遞歸C. 2型D.含有公共左因子的47 給定文法AbA|cc，則符號串cc bcbc bcbcc bccbcc bbbcc中，是該文法句子的是(D)A. B. C. D. 48 LR(1)文法都是()A. 無二義性且無左遞歸B. 可能有二義性但無左遞歸C. 無二義性但可能是左遞歸D. 可以既有二義性又有左遞歸49 文法EE+E|E*E|i的句子i*i+i*i有(C)棵不同的語法樹。A. 1B. 3C. 5D.750 文法 SaaS|abc 定義的語言是(C)。A.a2kbc|k0B.akbc|k0C.a2k-1bc|k0D.akakbc|k051 若B為非終結符，則 Aa.Bb 為(D)。A.移進項目B.歸約項目C.接受項目D.待約項目52 同心集合并可能會產生新的(D)沖突。A.二義B.移進/移進C.移進/歸約D.歸約/歸約53 就文法的描述能力來說，有(C)ASLR(1) LR(0)BLR(1) LR(0)CSLR(1) LR(1)D無二義文法 LR(1)54 如圖所示自動機M，請問下列哪個字符串不是M所能識別的(D)。A. bbaaB. abbaC. ababD. aabb55 有限狀態自動機能識別(C)A.上下文無關語言B.上下文有關語言C.正規語言D.0型文法定義的語言56 已知文法G是無二義的，則對G的任意句型(A)A.最左推導和最右推導對應的語法樹必定相同B.最左推導和最右推導對應的語法樹可能相同C.最左推導和最右推導必定相同D.可能存在兩個不同的最左推導，但他們對應的語法樹相同57 (B)不是DFA的成分A.有窮字母表B.多個初始狀態的集合C.多個終態的集合D.轉換函數58 與逆波蘭式(后綴表達式)ab+c*d+對應的中綴表達式是(B)A. a+b+c*dB. (a+b)* c+dC. (a+b)* (c+d)D. a+b*c+d59 后綴式abc+d+可用表達式(B)來表示。A( (a+b)c)+d B(a+(bc)+d C (a(b+c)+d D(a(b+c)+d60 表達式A*(B-C*(C/D)的后綴式為(B)。AABC-CD/* BABCCD/*-* CABC-*CD/* D以上都不對61 (D)不是NFA的成分。A. 有窮字母表B. 初始狀態集合C. 終止狀態集合D. 有限狀態集合二、 問答題1 將文法GS 改寫為等價的GS，使GS不含左遞歸和左公共因子。GS： SbSAe | bA AAb | d答：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為：SbB BSAe | AAd A A bA | 2 將文法GS 改寫為等價的GS，使GS不含左遞歸和左公共因子。GS： SSAe|Ae AdAbA|dA|d答：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為： S AeSS AeS| A dA A AB| B bA | 3 將文法GS 改寫為等價的GS，使GS不含左遞歸和左公共因子。GS： SA AB|AS BaB|a答：文法GS 改寫為等價的不含左遞歸和左公共因子的GS為：S AA BAASA|B aBBB|4 判斷下面文法是否為LL(1)文法，若是,請構造相應的LL(1)分析表。SaHHaMd | dMAb | AaM | e答：首先計算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非終結符FIRST集FOLLOW集Sa.# .Ha ，d.# .Ma ，e ，d ，bAa ，e.b.由于predict（HaMd）predict（Hd）=ad = predict（MAb）predict（M）=a ，ed ，b = predict（AaM）predict（Ae）= a e = 所以該文法是LL(1)文法，LL(1)分析表如下表。adbe#SaH.HaMdd.MAb.AbAaM.e.5 判斷下面文法是否為LL(1)文法，若是，請構造相應的LL(1)分析表。SaDDSTe|TbH|HHd|答：首先計算文法的 FIRST集和FOLLOW集如下表。 非終結符FIRST集FOLLOW集Sa#，b，d，e.Da，#，b，d，e Tb，d，eHd，e由于predict（DSTe）predict（D）=a# ，b ，d ，e =predict（TbH）predict（TH）=be =predict（Hd）predict（H）= d e =所以該文法是LL(1)文法，LL(1)分析表如下表：aebd#SaD.DSTeTH.bHH.Hd.6 判斷下面文法是否為LL(1)文法，若是，請構造相應的LL(1)分析表。SaDDSTe|TbMMbHHM|答：文法的 FIRST集和FOLLOW集非終結符FIRST集FOLLOW集Sa.# ，bDa ，# ，bTb.e.Mb.e.Hb ，e.由于predict（DSTe）predict（D）=a# ，b=predict（HM）predict（H）= b e =所以該文法是LL(1)文法，LL(1)分析表如下表：aeb#SaD.DSTeTbMMbHHM.7 某語言的拓廣文法G為：(0) SS(1) S Db|B(2) D d|(3) B Ba|證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。答：拓廣文法G，增加產生式SS在項目集I0中：有移進項目D d 歸約項目D 和B 存在移進-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產生式排序為：(0) SS(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)項目集族及識別活前綴的DFA如下圖：由產生式知Follow(S)=# Follow(D)= bFollow(B)= a ,#在I0中:Follow(D) d= b d=Follow(B) d= a ,# d=Follow(D) Follow(B)= ba ,# =在I3中:Follow(S) a=#a=所以在I0，I3中的移進-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法, 構造的SLR(1)分析表如下表：狀態ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r58 給出與正規式R（ab）*（a|b*）ba等價的NFA。答：與正規式R等價的NFA如下圖9 給出與正規式R（(ab)*|b）*（a|(ba)*）a 等價的NFA。答：與正規式R等價的NFA如下圖10 給出與正規式 R（aba）*（(ba)*|b）b等價的NFA。答：與正規式R等價的NFA如下圖11 將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123確定化后如下圖：12 將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態X,0,1,30,1,3.2,3,Y.1,3.2,Y.Y.0,1,30,1,31,3.1,3.2,3,Y2,3,YY.2,Y.Y.X1234Y確定化后如下圖13 某語言的拓廣文法G為：(0) ST (1) T aBd|(2) B Tb| 證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。答：拓廣文法G，增加產生式ST 在項目集I0中：有移進項目T aBd和歸約項目T 存在移進-歸約沖突，所以G不是LR(0)文法。 若產生式排序為： (0) ST(1) T aBd(2) T (3) B Tb(4) B G的LR(0)項目集族及識別活前綴的DFA如下圖所示：識別G活前綴的DFA由產生式知：Follow(T)=#,b Follow(B)= d在I0中： Follow(T) a=# ，b a=在I2中：Follow(B) a= d a=Follow(T) a=# ，b a=Follow(B) Follow(T) = d# ，b=所以在I0，I2，中的移進-歸約和歸約-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。 構造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r314 某語言的文法G為： E aTd| T Eb|a證明G不是LR(0)文法而是SLR(1)文法，請給出該文法的SLR(1)分析表。答：拓廣文法G，增加產生式SE在項目集I0中： 有移進項目E aTd和歸約項目E 存在移進-歸約沖突，所以G不是LR(0)文法。 .若產生式排序為：(0) SE (1) E aTd (2) E (3) T Eb (4) T aG的LR(0)項目集族及識別活前綴的DFA如下圖：由產生式知：Follow(E)=# ，b Follow(T)= d在I0 ，I2中:Follow(E) a=# ，b a=在I5 中:Follow(E) a=# ，b a=Follow(T) a= d a=Follow(T) Follow(E) = d # ，b=所以在I0 ， I2 ， I5中的移進-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法。構造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r315 給出文法GS的LR(1)項目集規范族中I0項目集的全體項目。GS為： S BD|D B aD|b D BI0:答：I0：16 給出文法GS的LR(1)項目集規范族中I0項目集的全體項目。GS為： S D;D|D D DB|B B a|bI0:答：I0:17 文法GM及其LR分析表如下，請給出對串dbba#的分析過程。GM: 1) M VbA2) V d3) V 4) A a5) A Aba6) A nameACTIONGOTObda#MAV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對串dbba#的分析過程如下表步驟狀態棧文法符號棧剩余輸入符號動作12345678900302024024602467024678024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移進用V d歸約移進用A 歸約移進移進用A Aba 歸約用M VbA 歸約接受18 文法GS及其LR分析表如下，請給出對輸入串da;aoa#的分析過程。GS: 0) SS1) SdSoS2) S dS3) S S;S 4) S a nameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：輸入串da;aoa#的分析過程如下表：步驟狀態棧文法符號棧剩余輸入符號動作123456789101112 002023025025402543025460250257025730257801#d#da#dS#dS;#dS;a#dS;S#dS#dSo#dSoa#dSoS#Sda;aoa#a;aoa#;aoa#;aoa#aoa#oa #oa #oa #a #移進移進用S a 歸約移進移進用S a 歸約用S S;S 歸約移進移進用S a 歸約用SdSoS 歸約接受19 文法GM及其LR分析表如下，請給出對串dada#的分析過程。GM: 1) S VdB2) V e3) V 4) B a 5) B Bda6) B 狀態ACTIONGOTOdea#SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對串dada#的分析過程如下表步驟狀態棧文法符號棧剩余輸入符號動作1234567890020240245024602467024678024601#V#Vd#Vda#VdB#VdBd#VdBda#VdB#Sdada#dada#ada#da#da#a#用V 歸約移進移進用B a歸約移進移進用B Bda 歸約用S VdB 歸約接受20 按指定類型給出下列語言的文法。(1) L1= anbm c| n0，m0 用正規文法。(2) L2= a0n1n bdm | n0，m0 用二型文法。 答：(1) 描述L1語言的正規文法如下： S aS|AA bA|bB B c(2) 描述L2語言的二型文法如下：S AB A aT T 0T1|01 B bD D dD|d 21 下列語言或文法確切屬于按喬姆斯基（Chomsky）分類的哪種類型,請填在（ ）內。（1） L1= a0n1nbdm | n0，m 0 ( ) （2） L2= anbncnbm | n0,m0 ( ) （3） L3= anbmc| n0,m0 ( ) （4） GA:AaB| BAb|a ( )（5） GE:EE+E|E*E|(E)|i ( )答：（1） L1= a0n1nbdm | n0，m 0 ( 2 型 ) （2） L2= anbncnbm | n0,m0 ( 1型 ) （3） L3= anbmc| n0,m0 ( 3型 ) （4） GA:AaB| BAb|a ( 2型 ) （5） GE:EE+E|E*E|(E)|i ( 2型 )22 按指定類型給出下列語言的文法。(1) L1= candbm| n0