編譯原理總復(fù)習(xí)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 alphabet字母表 symbol符號(hào) string串 length長(zhǎng)度 catenation連接power方冪 gather集合 product乘積 empty set空集 closure 閉包program程序 logic structure邏輯結(jié)構(gòu) generating產(chǎn)生 executing執(zhí)行machine language機(jī)器語(yǔ)言 instruction指令 function函數(shù) assembler匯編程序interpreter解釋程序 translator翻譯程序 source language源語(yǔ)言 finite有窮的source program源

2、程序 target language目標(biāo)語(yǔ)言 attribute屬性 possess占有preprocess預(yù)處理 compiler編譯程序 break中斷 Intermediate language中間語(yǔ)言definition定義 reconstructed重構(gòu) normal正規(guī) character sequences 符號(hào)序列programming language程序設(shè)計(jì)語(yǔ)言 operand操作數(shù) instead替換 memory內(nèi)存element元素 high-level language高級(jí)語(yǔ)言 object program目標(biāo)程序address地址 input輸入 output輸出

3、 terminal終結(jié)符 compilation編輯equivalence等價(jià) nonterminal非終結(jié)符 recursion遞歸 deterministic確定的nondeterministic非確定的 Backus-Normal Form巴科斯范式 syntax語(yǔ)法tree樹 expression表達(dá)式 grammar文法 automata自動(dòng)機(jī) prefix前綴suffix后綴 infix中綴 identify識(shí)別 identifier標(biāo)識(shí)符 analyses分析predigest化簡(jiǎn) symbol set符號(hào)集 performed執(zhí)行 forecast預(yù)測(cè) state狀態(tài)formu

4、la產(chǎn)生式 conversion變換 precedence優(yōu)先 simple簡(jiǎn)單 handle句柄operator算符 terminal state終態(tài) first state初態(tài) optimizer優(yōu)化程序concatenation連接 word單詞 alphabet字母表 lexical詞法 scanner掃描器analyzer分析器 syntax tree語(yǔ)法樹 symbol table符號(hào)表 pass趟，遍regular expression正規(guī)表達(dá)式 code generator代碼生成器 backdate回溯derivation推導(dǎo) educe推導(dǎo) derivation tree推

5、導(dǎo)樹 path路徑 ambiguous二義性simple phrase簡(jiǎn)單短語(yǔ) context-sensitive上下文有關(guān) context-free上下文無(wú)關(guān)right-linear 右線形 phrase-structured短語(yǔ)結(jié)構(gòu) regular grammar文法direct derivation直接推導(dǎo) sentence句子 sentential form句型 root node根結(jié)點(diǎn)subtree子樹 semantic語(yǔ)義的 terminal node端末結(jié)點(diǎn) attribute grammar屬性文法canonical derivation規(guī)范推導(dǎo) top-down自上而下 bo

6、ttom-up自下而上viable prefix活前綴 nondeterminate finite automata非確定的有窮自動(dòng)機(jī)總復(fù)習(xí)一、基本概念： 1、請(qǐng)簡(jiǎn)單解釋編譯程序的概念。答：編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一。簡(jiǎn)而言之, 編譯程序就是一種語(yǔ)言翻譯程序。所謂翻譯程序，是指這樣一個(gè)程序，它能將高級(jí)程序設(shè)計(jì)語(yǔ)言程序翻譯成邏輯上等價(jià)的低級(jí)語(yǔ)言(匯編語(yǔ)言,機(jī)器語(yǔ)言) 程序。編譯程序一般由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、目標(biāo)代碼生成程序、代碼優(yōu)化程序、表格管理程序和出錯(cuò)處理程序等成分構(gòu)成。2、請(qǐng)解釋編譯程序的前端和后端的概念，試問(wèn)前端通常包括那些階段，后

7、端包括那些階段？ (10分)答：編譯程序的前端只依賴于源語(yǔ)言，由幾乎獨(dú)立于目標(biāo)機(jī)器的階段或階段的一部分組成。編譯程序的前端通常包括詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序及相關(guān)的表格管理程序和出錯(cuò)處理程序。編譯程序的后端是指編譯器中依賴于目標(biāo)機(jī)器的部分,它們一般獨(dú)立于源語(yǔ)言，而與中間代碼有關(guān)。通常包括目標(biāo)代碼生成程序、代碼優(yōu)化程序以及相關(guān)的表格管理程序和出錯(cuò)處理程序。3、語(yǔ)言的語(yǔ)法描述方法有其三，請(qǐng)列舉出來(lái)。答：用自然語(yǔ)言描述語(yǔ)言的語(yǔ)法，用語(yǔ)法圖描述語(yǔ)言的語(yǔ)法和用巴科斯-瑙爾范式及擴(kuò)充的巴科斯-瑙爾范式 (EBNF)兩種形式給出語(yǔ)言的語(yǔ)法描述。答：根據(jù) Chomcky文法的定

8、義，該文法是2類文法，即上下文無(wú)關(guān)文法。4、請(qǐng)寫出Chomcky關(guān)于文法的定義。答： Chomcky文法的定義：文法G定義為四元組,記為: G=(VN,VT,P,S)其中：VN 非空有限的非終結(jié)符號(hào)集 VT 非空有限的終結(jié)符號(hào)集 P 產(chǎn)生式集 S 開始符號(hào)/識(shí)別符號(hào)5、已知文法：（20分） EX|E+X XY|X*Y Y（E）|i請(qǐng)判定該文法是那類文法？5、簡(jiǎn)單說(shuō)明詞法分析程序的主要任務(wù)。答：詞法分析程序是編譯程序的一個(gè)構(gòu)成成分，它的主要任務(wù)是掃描源程序，按構(gòu)詞規(guī)則識(shí)別單詞，并報(bào)告發(fā)現(xiàn)的詞法錯(cuò)誤。6、請(qǐng)簡(jiǎn)單介紹確定的有窮自動(dòng)機(jī)。答：確定的有窮自動(dòng)機(jī)也稱有限自動(dòng)機(jī)，它是作為一種識(shí)別裝置，它能準(zhǔn)確

9、地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語(yǔ)言和正規(guī)式所表示的集合。具體而言，一個(gè)確定的有窮自動(dòng)機(jī)可以用一個(gè)五元組表示，即M=(K,f, S,Z)。K是一個(gè)有窮狀態(tài)集，是一個(gè)有窮字母表，f是轉(zhuǎn)換函數(shù)，S是初態(tài)，Z是一個(gè)終態(tài)集。7、簡(jiǎn)單說(shuō)明語(yǔ)法分析程序。答：語(yǔ)法分析程序是編譯程序的核心部分。語(yǔ)法分析的作用是識(shí)別由詞法分析給出的單詞符號(hào)序列是否是給定文法的正確句子(程序)，目前語(yǔ)法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）分析兩大類。8、請(qǐng)說(shuō)明有關(guān)句型、句子、句柄概念？（10分） 答：設(shè)GS是一文法，如果符號(hào)串x是從文法的識(shí)別符號(hào)推導(dǎo)出來(lái)的，則稱符號(hào)串x是文法GS的句型。若符號(hào)串x還

10、滿足僅由終結(jié)符號(hào)組成的條件，則稱x為GS的句子。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。9、請(qǐng)說(shuō)明有關(guān)規(guī)范句型的概念？答：最右推導(dǎo)，即推導(dǎo)的每一步都是替換當(dāng)前句型最右邊的非終結(jié)符，被稱為規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)得到的句型稱為規(guī)范句型。10、請(qǐng)說(shuō)明有關(guān)預(yù)測(cè)符號(hào)集的概念？答：產(chǎn)生式A預(yù)測(cè)符號(hào)集表示：在確定的自上而下的語(yǔ)法分析過(guò)程中，當(dāng)需要替換的非終結(jié)符是A時(shí)，而當(dāng)前需要匹配的終結(jié)符屬于產(chǎn)生式A預(yù)測(cè)符號(hào)集中的符號(hào)，則能夠采用該產(chǎn)生式進(jìn)行推導(dǎo)。當(dāng)不能推出時(shí)，產(chǎn)生式A預(yù)測(cè)符號(hào)集是的首符號(hào)集；當(dāng)能推出時(shí)，產(chǎn)生式A預(yù)測(cè)符號(hào)集是的首符號(hào)集與A的后跟符號(hào)集的并集，但是不包括。11、簡(jiǎn)單說(shuō)明LR分析器由那幾部分組成？

11、答：簡(jiǎn)單而言LR分析器由3部分組成，它們是：總控程序、分析表（ACTION表和GOTO表）和分析棧（符號(hào)棧和狀態(tài)棧）。12、簡(jiǎn)單說(shuō)明拓廣文法、活前綴和可歸前綴的概念？答：拓廣文法：在原文法中增加一個(gè)產(chǎn)生式，得到的新文法稱之為原文法的拓廣文法；活前綴：在規(guī)范句型中，不包括該句型句柄右邊符號(hào)的前綴稱之為活前綴；可歸前綴：活前綴與句柄有3種關(guān)系，：活前綴不含句柄的任何符號(hào)；：活前綴含有句柄的部分符號(hào)；：活前綴包含句柄的全部符號(hào)。包含句柄的全部符號(hào)的活前綴稱之為可歸前綴。13、請(qǐng)簡(jiǎn)單說(shuō)明編譯中的語(yǔ)義處理。答：編譯中的語(yǔ)義處理是指兩個(gè)功能：第一，審查每個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義，即驗(yàn)證語(yǔ)法結(jié)構(gòu)合法的程序是否真

12、正有意義。有時(shí)把這個(gè)工作稱為靜態(tài)語(yǔ)義分析或靜態(tài)審查。第二，如果靜態(tài)語(yǔ)義正確，語(yǔ)義處理則要執(zhí)行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標(biāo)代碼。14、編譯程序所使用的中間代碼經(jīng)常見(jiàn)的有那幾種形式？答：編譯程序所使用的中間代碼常見(jiàn)的有逆波蘭記號(hào)、三元式、四元式和樹形表示。15、簡(jiǎn)單說(shuō)明代碼優(yōu)化的概念。答：所謂代碼優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲(chǔ)空間少，或兩者都有。16、簡(jiǎn)單說(shuō)明代碼生成器的概念。答；代碼生成器是把某種高級(jí)程序設(shè)計(jì)語(yǔ)言編寫的程序經(jīng)過(guò)語(yǔ)法、語(yǔ)義分析，或再經(jīng)過(guò)優(yōu)化后

13、的中間代碼作為輸入，將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語(yǔ)言或匯編語(yǔ)言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器。二、應(yīng)用題（每題10分，共40分）1、文法G（S）的產(chǎn)生式為：SaAS,ASbA,AaA,Ab,Sa,請(qǐng)寫出該文法的非終結(jié)符號(hào)集、終結(jié)符號(hào)集及文法的開始符號(hào)，根據(jù)文法畫出句型aSbSbaAa的語(yǔ)法樹，并且指出該句型的短語(yǔ)、直接短語(yǔ)和句柄？答：該文法的非終結(jié)符號(hào)集是S,A、終結(jié)符號(hào)集是a,b及文法的開始符號(hào)是S 句型aSbSbaAa的語(yǔ)法樹為： 該句型的短語(yǔ)為：aA,SbaA, SbSbaAa, aSbSbaAa,a直接短語(yǔ)為：aA, a句柄為：aA2、正規(guī)式為：b(ab)*|bb)ba，請(qǐng)根據(jù)所列

14、正規(guī)式，畫出對(duì)應(yīng)的NFA的狀態(tài)轉(zhuǎn)換圖，并且將NFA確定化，畫出對(duì)應(yīng)的DFA的狀態(tài)轉(zhuǎn)換圖。答： （1）正規(guī)式為：b(ab)*|bb)ba 對(duì)應(yīng)的NFA的狀態(tài)轉(zhuǎn)換圖如下： （2）利用轉(zhuǎn)換矩陣將以上NFA確定化，轉(zhuǎn)換矩陣如下： I IaIb12,3,4,72,3,4,756,854,76,8974,75878899 （3）將狀態(tài)重新編號(hào)，NFA確定化后，生成DFA狀態(tài)轉(zhuǎn)換矩陣如下： ab011232437542656677 （4）DFA狀態(tài)轉(zhuǎn)換圖如下： 3、請(qǐng)根據(jù)文法G寫出所有產(chǎn)生式的預(yù)測(cè)符號(hào)集，并且判定該文法是否是LL(1)文法，如果是，請(qǐng)畫出對(duì)應(yīng)的預(yù)測(cè)符號(hào)表。文法G(S)：SaBA ABa| B

15、bB|a答：（1）求出各個(gè)產(chǎn)生式的預(yù)測(cè)符號(hào)集： Select(SaBA)=a Select(ABa)=b,a Select(A)=# Select(BbB)=b Select(Ba)=a (2) 由于Select(ABa) Select(A)= Select(BbB) Select(Ba)= 所以該文法是LL(1)文法。(3) 該文法對(duì)應(yīng)的LL(1) 預(yù)測(cè)符號(hào)表如下： ab#SaBAABaBaBabB4、寫出下面所列的文法的拓廣文法，并且找出該拓廣文法所有的項(xiàng)目，請(qǐng)構(gòu)造識(shí)別該文法所有活前綴的NFA。 文法G(S)：SSbBa|B Ba| 答：（1）該文法的拓廣文法是： SS SSbBa|B B

16、a| (2) 該拓廣文法所有的項(xiàng)目為： (0) S.S SS. S.SbBa SS.bBaSSb.Ba SSbB.aSSbBa. S.BSB. B.aBa. B. (3) 識(shí)別該文法所有活前綴的NFA如下： 5、根據(jù)以下文法，直接寫出該文法的拓廣文法和所有項(xiàng)目，構(gòu)造項(xiàng)目集規(guī)范族及識(shí)別該文法所有活前綴的DFA，由識(shí)別該文法所有活前綴的DFA，判定該文法是否是LR(0)文法，如果是請(qǐng)構(gòu)造相應(yīng)的LR（0）分析表，通過(guò)查找 LR（0）分析表寫出對(duì)于輸入串a(chǎn)de#的分析過(guò)程。文法G(S)：SABC Aa Bb Bd Ce答：（1）該文法的拓廣文法是：SS SABC Aa Bb Bd Ce 該文法的所有項(xiàng)目：共計(jì)14個(gè) S.S SS. S.ABC SA.BC SAB.C SABC. A.a Aa. B.b Bb. B.d Bd. C.e Ce. （2）直接構(gòu)造項(xiàng)目集規(guī)范族及識(shí)別該文法所有活前綴的DFA，如下圖所示： 從DFA可以看出項(xiàng)目集規(guī)范族中不存在移進(jìn)與歸約的沖突，也不存在歸約與歸約的沖突，所以可以判定該文法屬于LR(0)文法 (3)由DFA直接構(gòu)造相