編譯原理期末考試題目及答案

1、2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。x二、單項(xiàng)選擇題（每小題 2 分，共 1詞法分析器的輸出結(jié)果是 _C。A 單詞的種別編碼C 單詞的種別編碼和自身值2 正規(guī)式 M1 和 M 2 等價(jià)是指A M1 和 M2 的狀態(tài)數(shù)相等 C M1 和 M2 所識(shí)別的語(yǔ)言集相等3.文法 G:STxSx|y 所識(shí)別的語(yǔ)言是_C.A. xyx B. （xyx）* C. xnyxn（n 0）4. 如果文法 G 是無(wú)二義的，則它的任何句子A 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同C 最左推導(dǎo)和最右推導(dǎo)必定相同5構(gòu)造編譯程序應(yīng)掌握 _ D_。A .源程序B .目標(biāo)語(yǔ)言20 分）B.D.C_。C.單詞在符號(hào)表中

2、的位置單詞自身值B.D.M1 和 M2 的有向邊條數(shù)相等M1 和 M2 狀態(tài)數(shù)和有向邊條數(shù)相等Dx*yx*aA編譯方法oB 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同D.以上三項(xiàng)都是6四元式之間的聯(lián)系是通過(guò)_B_實(shí)現(xiàn)的。A 指示器B 臨時(shí)變量7. 表達(dá)式（nAVB）A（CVD）的逆波蘭表示為A nABVACDVB8. 優(yōu)化可生成 _D_的目標(biāo)代碼。A 運(yùn)行時(shí)間較短C 運(yùn)行時(shí)間短但占用內(nèi)存空間大c.符號(hào)表_B_ 。AnBVCDVAD .程序變量C.ABVnCDVAD.AnB VACDVB 占用存儲(chǔ)空間較小D 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列_C_優(yōu)

3、化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A.強(qiáng)度削弱B 刪除歸納變量10編譯程序使用_B_區(qū)別標(biāo)識(shí)符的作用域。A. 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)名C 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的動(dòng)態(tài)層次C 刪除多余運(yùn)算D 代碼外提B說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的靜態(tài)層次D. 標(biāo)識(shí)符的行號(hào)三、判斷題（對(duì)的打，錯(cuò)的打X,每小題1 分，共 10 分）一、填空題（每空 2 分，共 20 分）1編譯程序首先要識(shí)別出源程序中每個(gè)單詞，然后再分析每個(gè) 句子 并翻譯其意義。2編譯器常用的語(yǔ)法分析方法有自底向上 和自頂向下 兩種。3通常把編譯過(guò)程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的分析 ，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生

4、成則是對(duì)源程序的 綜合 。4程序設(shè)計(jì)語(yǔ)言的發(fā)展帶來(lái)了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類(lèi)，即靜態(tài)存儲(chǔ)分配 方案和 動(dòng)態(tài)存儲(chǔ)分配方案。5對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是 目標(biāo)程序 。1計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：解釋和編譯 。2掃描器是 詞法分析器，它接受輸入的 源程序，對(duì)源程序進(jìn)行 詞法分析 并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞 符號(hào)，供語(yǔ)法分析器使用。3自下而上分析法采用 移進(jìn) 、歸約、錯(cuò)誤處理、 接受等四種操作。4一個(gè) LL （1）分析程序需要用到 一張分析表 和符號(hào)棧。5.后綴式 abc-/所代表的表達(dá)式是 a/（b-c）。3一個(gè)算符優(yōu)先文法的每

5、個(gè)非終結(jié)符號(hào)間都也可能存在優(yōu)先關(guān)系。 4語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。 X6逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。R9兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。X1編譯程序是對(duì)高級(jí)語(yǔ)言程序的編譯執(zhí)行。X2一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的初始態(tài)。R3一個(gè)算符優(yōu)先文法的每個(gè)非終結(jié)符號(hào)間都不存在優(yōu)先關(guān)系。R4LL （1）語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。 R5 LR 分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。R6逆波蘭表示法表示表達(dá)式時(shí)根據(jù)表達(dá)式會(huì)使用括號(hào)。X7靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。X8進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)

6、代碼的效率將起更大作用。X9兩個(gè)正規(guī)集相等的必要條件是他們產(chǎn)生的符號(hào)串是相同的。R10一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。X1什么是 S-屬性文法？什么是 L-屬性文法？它們之間有什么關(guān)系？S-屬性文法是只含有綜合屬性的屬性文法。（2 分）L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式 A X1X2Xn,其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是 Xj 的一個(gè)繼 承屬性，且該屬性?xún)H依賴(lài)于：（1） 產(chǎn)生式 Xj 的左邊符號(hào) X1,X2Xj-1 的屬性；（2） A 的繼承屬性。（2 分）S-屬性文法是 L-屬性文法的特例。（1分）2什么是 LL（1）分析器2.什么是 LR（0）分析器所謂 LR（O

7、）分析，是指從左至右掃描和自底向上的語(yǔ)法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移 進(jìn)和歸約出的全部文法符號(hào),并至多再向前查看 0 個(gè)輸入符號(hào),就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是 否已在分析棧的頂部形成,從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作（是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等 ）五、綜合題（共 40 分）1.（10 分）對(duì)于文法 GS:ST1A | 0B |AT0S | 1AA B 宀 1S | 0BB （3 分 ） 請(qǐng)寫(xiě)出三個(gè)關(guān)于 GS 的句子； （4 分 ） 符號(hào)串 11A0S 是否為 G S 的句型？試證明你的結(jié)論。 （3 分 ） 試畫(huà)出 001B 關(guān)于 G S 的語(yǔ)法樹(shù)。答:

8、（ 1 ） 三個(gè) 0 和 1 數(shù)量相等的串 （每個(gè) 1 分）（ 2） S = 1A = 11AA = 11A 0S（ 3）2.（10 分）設(shè)有語(yǔ)言 L= a |a0,1+，且a不以 0 開(kāi)頭，但以 00 結(jié)尾。23分）試寫(xiě)出描述 L 的正規(guī)表達(dá)式；（7分）構(gòu)造識(shí)別L 的 DFA （要求給出詳細(xì)過(guò)程，并畫(huà)出構(gòu)造過(guò)程中的NFA、 DFA 的狀態(tài)轉(zhuǎn)換圖，以及最小第三步（2分）：將 DFA 最小化：（1分）將狀態(tài)劃分終態(tài)與非終態(tài)兩個(gè)集合：A=qO,q1,q2,q3, E=q4根據(jù)A、E集合的情況，對(duì)A集合進(jìn)行劃分狀態(tài)輸入I 011q0Aq1AA狀態(tài)輸入I 0I 1tS一A,D,Bq0A,D,BD,B,

9、CD,B重新命名q1D,B,CD,B,C,ZD,Bq2D,BD,B,CD,Bq3D,B,C,ZD,B,C,ZD,Bq40 1q1q2q3q4q3q2q3q4q31DFA 的狀態(tài)轉(zhuǎn)換圖）。答：（1 ）（3分）正規(guī)表達(dá)式： 1（0|1） * 00（2 ）（7分）第一步（3分）：將正規(guī)表達(dá)式轉(zhuǎn)換為NFA3.(20 分)給定文法 GE:ETE+T | TTTT*F | FFT(E) | i該文法是 LL(1)文法嗎？(要求給出詳細(xì)過(guò)程，如果是LL (1),給出分析表)答：(1)該文法不是 LL (1)文法，因?yàn)橛凶筮f歸，消除左遞歸可獲得一個(gè)LL (1)文法(2)消除左遞歸，得新文法(3 分)ETTEE

10、T+TEITTFTTT*FT|FT(E) | i(3)求產(chǎn)生式右部的 First 集(2.5 分)First(TE ) = First(T)= First(F)=(,iFirst(+TE ) = +First(FT ) = First(F)=(,iFirst(*FT ) = *First(E) = (First(i) = i(4)求所有非終結(jié)符的 Follow 集(2.5 分)Follow(E) = $,)q2EAq3AA將狀態(tài)集A劃分為兩個(gè)集合：A=q0,q1,q3根據(jù)A、B集合的情況，狀態(tài)對(duì)A集合進(jìn)行劃分,B=2qqq輸入013I 1AAA將狀態(tài)集A劃分為兩個(gè)集合：A=q0, C=q根據(jù)A

11、、C集合的情況，狀態(tài)輸入I 0q1Bq3B對(duì)C集合進(jìn)行劃分I 1AA最小 DFA 的狀態(tài)轉(zhuǎn)換圖（1分）1,q3(2 分)Follow(E ) = Follow(E) = $,)Follow(T) = First(E)UFollow(E)=+U$,)=$,+,)Follow(T ) = Follow(T) =$,*,)Follow(F) = First(T)UFollow(T)UFollow(T)= $,*,)(5)求所有產(chǎn)生式的 Select 集(2.5 分)Select(ETTE)=First(TE )=:(,iSelect(+TE)=First (+TE)=+Select( )= =Fol

12、low(E )=$,)Select(TTFT)=First(FT )=:(,iSelect(TT*FT)=First(*FT)=*Select(TT )= =Follow(T )=$,+,)Select(FT(E)=First(E)=(Select(FTi) =First(i)=i(6) 對(duì)相同左部的所有 Select 即求交集(2.5 分)Select(ET+TE)nSelect(E)=Select(T*FT)nSelect(T)=Q1. （10 分）對(duì)于文法 G:Sr aSbS|aS|d證明該文法是二義性文法。答：一個(gè)文法，如果存在某個(gè)句子有不只一棵語(yǔ)法分析樹(shù)與之對(duì)應(yīng)，那么稱(chēng)這個(gè)文法是二義

13、性文法。（5 分）句子 aadbd 有兩棵語(yǔ)法樹(shù)（5 分，劃一棵樹(shù)給 3 分）。如下圖：（6分）(1) (2)由此可知，S aSbS|aS|d 定義的文法是二義性文法。Selec；t (FT(E)nSelect(FTi)=Q所以,改造后的文法是LL (1)文法， 其分析表如下(7)LL（1）分析表（5 分）VNVT+*i(EETTEETTEEET+TETTTFTTTFTTTTTT*FTFFT(E)$ETE TT TT TFTi3. (20 分)給定一個(gè)簡(jiǎn)單的算術(shù)表達(dá)式文法GE:ETE+T | TTTT*F | FFT(E) | i該文法是 SLR(1)文法嗎？(要求給出詳細(xì)過(guò)程，如果是SLR

14、文法，給出分析表)答：(1)該文法的拓廣文法是：(2 分)ETE(1)ETE+T(2)ETT( 3)TTT*F(4)TTF( 5)FT(E)(6)FTi(7)(2) 相應(yīng)的 LR( 0)的 DFA (10 分)(3)沖突與解決(3 分)111 狀態(tài)中有移進(jìn)一規(guī)約沖突Follow(E )=$ 不含 + 可解決移進(jìn)一規(guī)約沖突212 狀態(tài)中有移進(jìn)一規(guī)約沖突Follow(E)=+,), $ 不含 * 可解決移進(jìn)一規(guī)約沖突318 狀態(tài)中有移進(jìn)一規(guī)約沖突Follow(E)=+,), $ 不含 * 可解決移進(jìn)一規(guī)約沖突(4) SLR 分析表(5 分)ACTIONGOTO+*i()$ETF0S5S41231S

15、6接受2r3S7r3r33r5r5r5R5r5r54S5S49235r7r7r7r7r7r76S5S4837S5S4118r2S7r2r29S6S1010r6r6r6r6r6r611r4r4r4r4r4r4二、單項(xiàng)選擇題(每小題 2 分，共 20 分)1 .語(yǔ)言是_ C_A 終結(jié)符與非終結(jié)符的符號(hào)串的集合B.非終結(jié)符符號(hào)串的集合C.終結(jié)符符號(hào)串的集合D.產(chǎn)生式的集合2.編譯程序分兩階段工作，前階段完成的工作是_CA 詞法分析、語(yǔ)法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成D.詞法分析、語(yǔ)法分析和代碼優(yōu)化3.個(gè)句型中稱(chēng)為句柄的是該句型的最左 CA.句型 B.短語(yǔ)C.直接短語(yǔ)D.最左直接短語(yǔ)4 .自動(dòng)機(jī)識(shí)別的語(yǔ)言是 DA 0 型語(yǔ)言B. 1 型語(yǔ)言 C. 2 型語(yǔ)言 D. 3 型語(yǔ)言5.自動(dòng)機(jī)所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)法單位即BA. 字符B.單詞C.句子D.句型6.對(duì)應(yīng) Chomsky 四種文法的四種語(yǔ)言之間的關(guān)系是BA. Lo二 Lj二 L2二 L3B. L3二