大三下課件匯總編譯原理習(xí)題集

1、習(xí)題一、單項(xiàng)選擇題1、將編譯程序分成若干個(gè)“遍”是為了 a提高程序的執(zhí)行效率 b使程序的結(jié)構(gòu)更加清晰。c利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率 d利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2、構(gòu)造編譯程序應(yīng)掌握 a源程序 c編譯方法。b目標(biāo)語(yǔ)言 d以上三項(xiàng)都是3、變量應(yīng)當(dāng) a持有左值。b持有右值 d既不持有左值也不持有右值上。b詞法分析 d管理表格c既持有左值又持有右值 4、編譯程序絕大多數(shù)時(shí)間花在a出錯(cuò)處理 c目標(biāo)代碼生成5、不可能是目標(biāo)代碼。a匯編指令代碼 c絕對(duì)指令代碼b可重定位指令代碼 d中間代碼6、使用可以定義一個(gè)程序的意義。a語(yǔ)義規(guī)則 c產(chǎn)生規(guī)則7、詞法分析器的輸入是 a單詞符號(hào)串

2、c語(yǔ)法單位b詞法規(guī)則 d詞法規(guī)則。b源程序 d目標(biāo)程序8、中間代碼生成時(shí)所遵循的是- a語(yǔ)法規(guī)則c語(yǔ)義規(guī)則。b詞法規(guī)則 d等價(jià)變換規(guī)則9、編譯程序是對(duì) a匯編程序的翻譯 c機(jī)器語(yǔ)言的執(zhí)行10、語(yǔ)法分析應(yīng)遵循 a語(yǔ)義規(guī)則 c構(gòu)詞規(guī)則解答。b高級(jí)語(yǔ)言程序的解釋執(zhí)行 d高級(jí)語(yǔ)言的翻譯。b語(yǔ)法規(guī)則 d等價(jià)變換規(guī)則1、將編譯程序分成若干個(gè)“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選 b。2、構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語(yǔ)言及編譯方法等三方面的知識(shí)，故選 d。3、對(duì)編譯而言，變量既持有左值又持有右值，故選 c。4、編譯程序打交道最多的就是各種表格，因此選 d。5、目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼

3、和絕對(duì)指令代碼 3 種，因此不是目標(biāo)代碼的只能選 d。6、詞法分析遵循的是構(gòu)詞規(guī)則，語(yǔ)法分析遵循的是語(yǔ)法規(guī)則，中間代碼生成遵循的是語(yǔ)義規(guī)則，并且語(yǔ)義規(guī)則可以定義一個(gè)程序的意義。因此選 a。7、b8、c9、d10、c二、多項(xiàng)選擇題1、編譯程序各階段的工作都涉及到。a語(yǔ)法分析b表格管理c出錯(cuò)處理d語(yǔ)義分析2、編譯程序工作時(shí)，通常有 a詞法分析碼生成d語(yǔ)義檢查解答1b、c2. a、b、c、e三、填空題e詞法分析階段。 b語(yǔ)法分析c中間代e目標(biāo)代碼生成1、解釋程序和編譯程序的區(qū)別在于2、編譯過程通?？煞譃?5 個(gè)階段，分別是。、語(yǔ)法分析、代碼優(yōu)化，最后3、編譯程序工作過程中，第一段輸入是程序。和目標(biāo)代

4、碼生成。階段的輸出為4、編譯程序是指將是否生成目標(biāo)程序程序翻譯成程序的程序。2、詞法分析目標(biāo)語(yǔ)言中間代碼生成3、源程序目標(biāo)代碼生成4、源程序一、單項(xiàng)選擇題1、文法 G：SxSx|y 所識(shí)別的語(yǔ)言是。c. xnyxn(n0)a. xyxb. (xyx)*d. x*yx*2、文法 G 描述的語(yǔ)言 L(G)是指a. L(G)=|S+ , VT*。b. L(G)=|S*, VT*c. L(G)=|S*,(VTVN*)d. L(G)=|S+ , (VTVN*)3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別。a.b. 上下文有關(guān)文法d. 短語(yǔ)文法上下文無關(guān)文法c.正規(guī)文法4、設(shè) G 為算符優(yōu)先文法，G 的任意終結(jié)符對(duì)a、b 有

5、以下關(guān)系成立。a. 若 f(a)g(b)，則 abb.若 f(a)g(b)，則 ag)(b)或 f(a)0d. anbncmdm|n,m0c. anbmcmdn|n,m0e. dn|n05、自下而上的語(yǔ)法分析中，應(yīng)從a. 句型詞為單位的程序開始分析。句子b.c. 以單d. 文法的開始符e. 句柄6、對(duì)正規(guī)文法描述的語(yǔ)言，以下有能力描述它。c.上下文無關(guān)文法a.0 型文法性文法e.左線性文法b.1 型文法d.右線解答 1、e、a、c2、a、c、e3、b、c、d b、c、d、e三、填空題4、a、c5、b、c6、a、1、文法中的終結(jié)符和非終結(jié)符的交集是。詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定是，它一

6、定只出現(xiàn)在產(chǎn)生式的部。2、最左推導(dǎo)是指每次都對(duì)句型中的非終結(jié)符進(jìn)行擴(kuò)展。3、在語(yǔ)法分析中，最常見的兩種方法一定是分析法，另一是分析法。4、采用5、語(yǔ)法分析時(shí)，必須消除文法的左遞歸。樹代表推導(dǎo)過程，樹代表歸約過程。、歸約、錯(cuò)誤處理、6、自下而上分析法采用 7、Chomsky 把文法分為法，它們分別產(chǎn)生所產(chǎn)生的語(yǔ)言。等四種操作。種類型，編譯器構(gòu)造中采用和文和語(yǔ)言，并分別用和自動(dòng)機(jī)識(shí)別解答1、空集2、最左3、自上而上自下而上4、自上而上終結(jié)符右5、語(yǔ)法6、移進(jìn)7、4分析接受2型3 型上下文無關(guān)語(yǔ)言正規(guī)語(yǔ)言下推自動(dòng)機(jī)有限四、判斷題1、文法 SaS|bR| 描述的語(yǔ)言是(a|bc)* RcS2、在自下而

7、上的語(yǔ)法分析中，語(yǔ)法樹與分析樹一定相同。（）3、二義文法不是上下文無關(guān)文法。（）4、語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。6、一個(gè)文法所有句型的集合形成該文法所能接受的語(yǔ)言。（解答1、對(duì)五、簡(jiǎn)答題 1、句柄解答）2、錯(cuò)3、錯(cuò)4、錯(cuò)5、錯(cuò)6、錯(cuò)2、素短語(yǔ)3、語(yǔ)法樹4、歸約5、推導(dǎo)1、句柄：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。2、素短語(yǔ)：至少含有一個(gè)終結(jié)符的素短語(yǔ)，并且除它自身之外不再含任何更小的素短語(yǔ)。3、語(yǔ)法樹：滿足下面 4 個(gè)條件的樹稱之為文法 GS的一棵語(yǔ)法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為 VNVT 中的一個(gè)符號(hào)；樹的根結(jié)點(diǎn)以文法 GS的開始符 S

8、 標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為 VN 中的一個(gè)符號(hào)；若一個(gè)以 A 為標(biāo)記的結(jié)點(diǎn)有 K 個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為 X1,X2,XK，則 AX1,X2,XK，必然是 G 的一個(gè)產(chǎn)生式。 4、歸約：我們稱 直接歸約出 A，僅當(dāng) A是一個(gè)產(chǎn)生式，且 、 (VNVT)*。歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開始符。5、推導(dǎo)：我們稱 A 直接推出 ，即 A，僅當(dāng) A 是一個(gè)產(chǎn)生式，且 、(VNVT)*。如果 12n，則我們稱這個(gè)序列是從 1 至 2的一個(gè)推導(dǎo)。若存在一個(gè)從 1n 的推導(dǎo)，則稱 1 可推導(dǎo)出 n。推

9、導(dǎo)是歸約的逆過程。六、問答題1、給出上下文無關(guān)文法的定義。 解答一個(gè)上下文無關(guān)文法 G 是一個(gè)四元式（VT,VN,S, P），其中：VT 是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)；VN 是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VTVN=；S 是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)；P 是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是 P，其中，PVN， (VTVN)*。開始符號(hào) S 至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2、文法 GS：SaSPQ|abQ QPPQbPbb bQbc cQcc它是 Chomsky 哪一型文法？它生成的語(yǔ)言是什么？解答（1）由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符

10、號(hào)的長(zhǎng)度均小于等于產(chǎn)生式右部的符號(hào)長(zhǎng)度，所以文法 GS是 Chomsky1 型文法，即上下文有關(guān)文法。（2）按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低（否則無法推出句子），我們可以得到：SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQ QaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是得到文法 GS生成的語(yǔ)言 L= 3、按指定類型，給出語(yǔ)言的文法。 L=aibj|ji1的上下文無關(guān)文法?！窘獯稹縷n1（1）由 L=aibj|ji

11、1知，所求該語(yǔ)言對(duì)應(yīng)的上下文無關(guān)文法首先應(yīng)有 SaSb型產(chǎn)生式，以保證 b 的個(gè)數(shù)不少于 a 的個(gè)數(shù)；其次，還需有 SSb 或 SbS 型的產(chǎn)生式，用以保證 b 的個(gè)數(shù)多于 a 的個(gè)數(shù)；也即所求上下文無關(guān)文法 GS為： GS：SaSb|Sb|b4、有文法 G：SaAcB|Bd AAaB|cBbScA|b試求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄；寫出句子 acabcbbdcc 的最左推導(dǎo)過程。【解答】（1）分別畫出對(duì)應(yīng)兩句型的語(yǔ)法樹，如圖 2-8-2 所示句柄:AaBBd圖 2-8-2語(yǔ)法樹（2）句子 acabcbbdcc 的最左推導(dǎo)如下： SaAcBaAaBcBacaBcB

12、acabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc5、對(duì)于文法 GS：S（L）|aS|aLL, S|S（1）畫出句型（S,（a）的語(yǔ)法樹。（2）寫出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。【解答】（1）句型（S,（a）的語(yǔ)法樹如圖 2-8-3 所示（2）由圖 2-8-3 可知：短語(yǔ)：S、a、(a)、S,(a)、(S,(a)；直接短語(yǔ)：a、S；句柄：S；素短語(yǔ)：素短語(yǔ)可由圖 2-8-3 中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即；因此素短語(yǔ)為 a。 6、考慮文法 GT：TT*F|F FFP|P P（T）|i證明 T*P（T*F）是該文法的一個(gè)句型，并指出直接

13、短語(yǔ)和句柄?！窘獯稹渴紫葮?gòu)造 T*P（T*F）的語(yǔ)法樹如圖 2-8-4 所示。由圖 2-8-4 可知，T*P（T*F）是文法 GT的一個(gè)句型。直接短語(yǔ)有兩個(gè)，即 P 和 T*F；句柄為 P。一、單項(xiàng)選擇題1、詞法分析所依據(jù)的是。a. 語(yǔ)義規(guī)則d. 等價(jià)變換規(guī)則b. 構(gòu)詞規(guī)則c. 語(yǔ)法規(guī)則2、詞法分析器的輸出結(jié)果是。a.c.b. 單詞在符號(hào)表中的位置d. 單詞自身值單詞的種別編碼單詞的種別編碼和自身值3、正規(guī)式 M1 和 M2 等價(jià)是指a. M1 和 M2 的狀態(tài)數(shù)相等相等c. M1 和 M2 所識(shí)別的語(yǔ)言集相等。b. M1 和 M2 的有向弧條數(shù)d. M1 和 M2 狀態(tài)數(shù)和有向弧條數(shù)相等4、

14、狀態(tài)轉(zhuǎn)換圖（見圖 3-6-1）接受的字集為。a.c.合以 0 開頭的二進(jìn)制數(shù)組成的集合含奇數(shù)個(gè) 0 的二進(jìn)制數(shù)組成的集合b. 以 0 結(jié)尾的二進(jìn)制數(shù)組成的集合d. 含偶數(shù)個(gè) 0 的二進(jìn)制數(shù)組成的集5、詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此，。a. 詞法分析器應(yīng)作為獨(dú)立的一遍子程序較好c. 詞法分析器分解為多個(gè)過程，由語(yǔ)法分析器選擇使用為一個(gè)獨(dú)立的階段b.詞法分析器作為d.詞法分析器并不作解答1、b2、c3、c4、d5、b二、多項(xiàng)選擇題1、在詞法分析中，能識(shí)別出。b. 四元式e. 常數(shù)a.d.基本字 逆波蘭式c. 運(yùn)算符2、令=a,b，則上所有以 b 開頭，后跟若干個(gè) a

15、b 的字的全體對(duì)應(yīng)的正規(guī)式為。a. b(ab)*c.(ba)*bd. (ba)+b解答 1、a、c、e三、填空題b. b(ab)+e. b(a|b)2、a、b、d1、確定有限自動(dòng)機(jī) DFA 是2、若二個(gè)正規(guī)式所表示的的一個(gè)特例。相同，則認(rèn)為二者是等價(jià)的。3、一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由所。解答1、NFA四、判斷題2、正規(guī)集3、DFA（NFA）所識(shí)別1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一終態(tài)。2、設(shè) r 和 s 分別是正規(guī)式，則有 L（r|s）=L(r)|L(s)。3、自動(dòng)機(jī) M 和 M的狀態(tài)數(shù)不同，則二者必不等價(jià)。4、確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。5、對(duì)任意一個(gè)右

16、線性文法 G，都存在一個(gè) NFA M，滿足 L(G)=L(M)。（）（）6、對(duì)任意一個(gè)右線性文法 G，都存在一個(gè) DFA M，滿足 L(G)=L(M)。（）7、對(duì)任何正規(guī)表達(dá)式 e，都存在一個(gè) NFA M，滿足 L(G)=L(e)。（）8、對(duì)任何正規(guī)表達(dá)式 e，都存在一個(gè) DFA M，滿足 L(G)=L(e)。（）解答1 、2、3、錯(cuò)4、5、6、7、8、正確五、基本題1、設(shè) M（x,y, a,b, f,x,y）為一非確定的有限自動(dòng)機(jī)，其中 f 定義如下：f（x,a）x,y f（y,a）f（x,b）y f（y,b）x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī) M。解答：對(duì)照自動(dòng)機(jī)的定義 M=(S,f,S0,

17、Z)，由 f 的定義可知 f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動(dòng)機(jī)，先畫出 NFA M 相應(yīng)的狀態(tài)圖，如圖 3-6-2所示。用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表 3-6-3 所示。Ixyx,yIax,yx,yIbyx,yx,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表 3-6-4 所示的狀態(tài)轉(zhuǎn)換矩陣。表 3-6-4狀態(tài)轉(zhuǎn)換矩陣a 2 2b 122012即得到 M=（0,1,2, a,b, f,0, 1,2），其狀態(tài)轉(zhuǎn)換圖如圖 3-6-5 所示。將圖 3-6-5 的 DFA M最小化。首先，將 M的狀態(tài)分成終態(tài)組1，2與非終態(tài)組0；其次，考察1,2。由于1,2a=1,2b=21,2，所

18、以不再將其劃分了，也即整個(gè)劃分只有兩組0，1,2：令狀態(tài) 1 代表1,2，即把原來到達(dá) 2 的弧都導(dǎo)向 1，并刪除狀態(tài) 2。最后，得到如圖 3-6-6 所示化簡(jiǎn) DFA M。2、對(duì)給定正規(guī)式 b*（d|ad）（b|ab）+，構(gòu)造其 NFAM；解答：首先用 A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式的 NFA M，如圖 3-6-7 所示?！?歷年試題附參考答案 】來源： 劉龍的日志歷年試題及答案一 （每項(xiàng)選擇 2 分，共 20 分）選擇題1將編譯程序分成若干個(gè)“遍”是為了b。 a.提高程序的執(zhí)行效率b.使程序的結(jié)構(gòu)更加清晰c.利用有限的機(jī)器內(nèi)存并提高

19、機(jī)器的執(zhí)行效率 d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率 2構(gòu)造編譯程序應(yīng)掌握d。a.源程序 b.目標(biāo)語(yǔ)言c.編譯方法 d.以上三項(xiàng)都是 3變量應(yīng)當(dāng)c。a.持有c.既持有b.持有右值又持有右值 d.既不持有也不持有右值4編譯程序絕大多數(shù)時(shí)間花在d 上。a.出錯(cuò)處理 b.詞法分析c.目標(biāo)代碼生成 d.管理表格 5詞法分析器的輸出結(jié)果是c。a.單詞的種別編碼 b.單詞在符號(hào)表中的位置 c.單詞的種別編碼和自身值 d.單詞自身值 6正規(guī)式MI 和M2 等價(jià)是指c。a. MI 和M2 的狀態(tài)數(shù)相等 b.Ml 和M2 的有向弧條數(shù)相等。C.M1 和M2 所識(shí)別的語(yǔ)言集相等 d. Ml 和 M2 狀態(tài)

20、數(shù)和有向弧條數(shù)相等7中間代碼生成時(shí)所依據(jù)的是c。a語(yǔ)則 b詞則 c語(yǔ)義規(guī)則 d等價(jià)變換規(guī)則8后綴式ab+cd+/可用表達(dá)式b 來表示。a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d 9程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為c 管理技術(shù)。a.動(dòng)態(tài)b.棧式c.靜態(tài)d.堆式空間遵守d 原則。10.堆式動(dòng)態(tài)分配申請(qǐng)和a.先請(qǐng)先放 b.先請(qǐng)后放 c.后請(qǐng)先放 d.任意二（每小題 10 分，共 80 分）簡(jiǎn)答題1.畫出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。2. 已知文法GE:EET+|T TTF* | | a試證：FF*是文法的句型，該句型的短語(yǔ)、簡(jiǎn)

21、單短語(yǔ)和句柄.3為正規(guī)式(a|b) *a(a|b)構(gòu)造一個(gè)確定的有限自。設(shè)文法G(S)： S(L)|a S|aLL，S|S消除左遞歸和回溯；計(jì)算每個(gè)非終結(jié)符的和 FOLLOW；(3) 構(gòu)造分析表。5 已知文法A-aAd| aAb|判斷該文法是否SLR（1）文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過程。6 構(gòu)造算符文法GH的算符優(yōu)先關(guān)系（含）。 GH：HH;M|MMd|aHb7已構(gòu)造出文法G（S）（1）S BB（2）B aB（3）B b 1）。給出DFA 圖2）.給出LR 分析表3）假定輸入串為abaab，請(qǐng)給出LR 分析過程（即狀態(tài)，符號(hào)，輸入串的變化過程）。8 將下面的語(yǔ)句翻譯成四

22、元式序列：while ACBA (1) A-aAd (2)A- aAb (3)A-(2)構(gòu)造識(shí)別活前綴的DFAFOLLOW(A)=d,b,#對(duì)于狀態(tài)I0：FOLLOW(A)a=對(duì)于狀態(tài)I1：FOLLOW(A)a=因?yàn)?，在DFA 中無的現(xiàn)象，所以該文法是SLR(1)文法。 (3)SLR(1)分析表狀態(tài) ACTION GOTOa B d # A 0 S2 r3 r3 r3 1 1 acc2 S2 r3 r3 r3 3 3 S5 S4r1 r1 r1r2 r2 r2(4)串a(chǎn)b#的分析過程步驟 狀態(tài)棧 符號(hào)棧 當(dāng)前字符 剩余字符串 動(dòng)作1 0 # a b# 移進(jìn)02 #a b # 歸約A-023 #aA b # 移進(jìn)0235 #aAb # 歸約A- aAb5 01 #A # 接受6 【解答】由Md 和Ma得：VT(M)=d,a；由H-H;得：由HM 得：VT(H)=；VT(M) cVT(H)，即VT(H)=;,d,a由Md 和Mb 得：LASTVT(M)=d,b；由H-，；m 得：LA