總復習編譯原理（一）基本概念題：一、編譯程序的概念編譯程序是現代計算機系統的基本組成部分之一。簡而言之,

編譯程序就是一種語言翻譯程序。所謂翻譯程序，是指這樣一個程序，它能將高級程序設計語言程序翻譯成邏輯等價的低級語言(匯編語言,機器語言)程序。編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標代碼生成程序、代碼優化程序、表格管理程序和出錯處理程序等成分構成。

一個編譯軟件，實際涉及三種語言：源語言、目標語言、實現語言。源語言：SourceLanguage

目標語言：TargetorObjectLanguage

實現語言：ImplementationL

常常使用T型圖來表示的一個編譯器涉及的三個語言之間的關系。二、請解釋編譯程序的前端和后端的概念，試問前端通常包括那些階段，后端包括那些階段？編譯程序的前端只依賴于源語言，由幾乎獨立于目標機器的階段或階段的一部分組成。編譯程序的前端通常包括詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序及相關的表格管理程序和出錯處理程序。編譯程序的后端是指編譯器中依賴于目標機器的部分,它們一般獨立于源語言，而與中間代碼有關。通常包括目標代碼生成程序、代碼優化程序以及相關的表格管理程序和出錯處理程序。三、語言的語法描述語言的語法描述方法有其三，用自然語言描述語言的語法，用語法圖描述語言的語法和用巴科斯-瑙爾范式及擴充的巴科斯-瑙爾范式(EBNF)兩種形式給出語言的語法描述。用語法圖描述語言的語法與EBNF描述相比較：

語法圖描述：直觀，易讀，易寫。

EBNF表示：形式化強，易機器識別。

四、闡明語法的一個工具是文法，這是形式語言理論的基本概念之一。當我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。事實上，使用文法作為工具，不僅為了嚴格地定義句子的結構，也是為了用適當條數的規則把語言的全部句子描述出來，是以有窮的集合刻劃無窮的集合的工具。在形式上語言是符號串的集合。符號串是由字母表中的符號所組成的任何有窮序列。符號串的運算和符號串集合的運算。和、乘積、方冪與閉包。五、請寫出Chomcky關于文法的定義。

Chomcky文法的定義：文法G定義為四元組,記為:G=(VN,VT,P,S)其中：VN—非空有限的非終結符號集

VT—非空有限的終結符號集

P—產生式集

S—開始符號/識別符號

S∈VN六、例：已知文法：E→X|E+XX→Y|X*YY→（E）|i

請判定該文法是那類文法？答：根據Chomcky文法的定義，該文法是2類文法，即上下文無關文法。七、*請說明有關句型、句子、句柄概念？答：設G[S]是一文法，如果符號串x是從文法的識別符號推導出來的，則稱符號串x是文法G[S]的句型。若符號串x還滿足僅由終結符號組成的條件，則稱x為G[S]的句子。一個句型的最左直接短語稱為該句型的句柄。八、請說明有關規范句型的概念？答：最右推導，即推導的每一步都是替換當前句型最右邊的非終結符，被稱為規范推導，由規范推導得到的句型稱為規范句型。九、簡單說明詞法分析程序的主要任務。答：詞法分析程序是編譯程序的一個構成成分，它的主要任務是掃描源程序，按構詞規則識別單詞，并報告發現的詞法錯誤。十、程序設計語言的單詞符號一般可分成下列5種：①保留字，也稱關鍵字。

②標識符，用來表示各種名字，如常量名、變量名和過程名等。

③常數，各種類型的常數，如25，3.1415，TRUE和“ABC”等。

④運算符，如+，*，<=等。

⑤界符，如逗點，分號，括號等。十一、程序設計語言的單詞可用正規文法描述。正規文法是右線性文法,文法G=(VN,VT,P,S),P中的每一條規則形為A→aB或A→a,其中A,B∈VN,a∈VT

。正規文法所描述的是VT上的正規集（正規文法描述的語言的句子的集合）。正規式也稱正則表達式，也是表示正規集的數學工具。正規式說明單詞的模式，也就是說明單詞組成的形式規則，正規集則是滿足這些規則的單詞的集合。十二、*確定的有窮自動機也稱有限自動機，它是作為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合。具體而言，一個確定的有窮自動機可以用一個五元組表示，即M=(K,Σ,f,S,Z)。K是一個有窮狀態集，Σ是一個有窮字母表，f是轉換函數，S是初態，Z是一個終態集。

十三、確定的有窮自動機DFA和不確定的有窮自動機NFA的概念，對每個NFAN一定存在一個DFAM，使得L(M)=L(N)。對每個NFAN存在著與之等價的DFAM。與某一NFA等價的DFA不唯一。ε-閉包和子集法算法將NFA轉換成接受同樣的語言的DFA。十四、語法分析是編譯程序的核心部分。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子(程序)，目前語法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）分析兩大類。十五、自頂向下分析法也稱面向目標的分析方法，也就是從文法的開始符號出發企圖推導出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯。自頂向下分析法又可分為確定的和不確定的兩種，確定的分析方法需對文法有一定的限制，但由于實現方法簡單、直觀，便于手工構造或自動生成語法分析器，因而仍是目前常用的方法之一。不確定的方法即帶回溯的分析方法，這種方法實際上是一種窮舉的試探方法，因此效率低，代價高，因而極少使用。在確定的自頂向下語法分析中用的是最左推導。

十六、請說明有關預測符號集的概念？答：產生式A→α預測符號集表示：在確定的自上而下的語法分析過程中，當需要替換的非終結符是A時，而當前需要匹配的終結符屬于產生式A→α預測符號集中的符號，則能夠采用該產生式進行推導。當α不能推出ε時，產生式A→α預測符號集是α的首符號集；當α能推出ε時，產生式A→α預測符號集是α的首符號集與A的后跟符號集的并集，但是不包括ε。十七、LL(1)文法：LL(1)文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導，'1'表明只需向右看一個符號便可決定選擇哪個產生式或規則進行推導。LL（1）方法是LL（K）方法的特例。一個上下文無關文法是LL(1)文法的充分必要條件是：對每個非終結符A的兩個不同產生式，A→α,A→β,滿足

SELECT(A→α)∩SELECT(A→β)=Φ其中α，β不同時能ε

十八、預測分析方法是自頂向下分析的方法，一個預測分析器是由三個部分組成。

·預測分析程序(總控程序)

·先進后出棧(stack)

·預測分析表：預測分析表以終結符號和“#”號作為列標志，以非終結符號作為行標志，對每個終結符號或“#”號用a表示，若a∈SELECT(A→α),則把A→α放入M[A,a]中,把所有無定義的M[A,a]標上出錯標記。這就構成了預測分析表。要求學員能夠對一個給定的文法判斷是否是LL(1)文法；能構造預測分析表；能用預測分析方法判斷給定的輸入符號串是否是該文法的句子。（基本要求）十九、某些含有左遞歸和左公共因子的文法在通過等價變換把它們消除以后可能變為LL(1)文法，但需要用LL(1)文法的定義判別。（基本要求）二十、自底向上分析法，也稱移進-歸約分析法，或自下而上分析。自底向上分析是自頂向下分析的逆過程,它是從待分析的句子出發逆向使用產生式逐步歸約的過程。從語法分析樹的角度講，就是從語法樹的葉結點（句子）出發自下而上逐層構造語法樹，每一層對應歸約過程中的一個句型。常用的自底向上語法分析方法有優先分析方法和LR方法。優先分析方法又分為簡單優先方法和算符優先方法；LR方法也有多種。二十一、簡單優先分析法的基本思想是：通過優先關系的定義，確定了在VT∪VN中任何二個符號之間的優先關系；（兩個符號之間最多只有一種關系成立），對于當前的句型，通過從右至左的掃描，利用優先關系，先找到句柄的尾符號，然后找到句柄的頭符號，從而找到了當前句型中應該歸約的句柄。通過歸約，構造一層語法樹；如此反復，直到歸約到文法的開始符號。二十二、算符優先分析的基本思想是只規定算符(廣義為終結符)之間的優先關系，也就是只考慮終結符之間的優先關系，不考慮非終結符之間的優先關系。它是根據算符（終結符）之間的優先關系確定句型中歸約子串的方法。它采用的不是規范歸約，因此它的歸約子串并不是規范歸約意義上的句柄，為了和規范歸約區分開來稱之為最左素短語，也就是說，在算符優先分析法每步自底向上歸約時，識別和歸約的是當前的最左素短語。二十三、LR分析法的分析過程是一種規范歸約過程，規范歸約是規范推導的逆過程。規范推導是最右推導，規范歸約是其逆過程，則是最左歸約。LR分析法的可歸約串是當前句型的句柄，即最左直接短語。對于大多數用無二義性上下文無關文法描述的語言都可以用相應的LR分析器進行識別，而且這種方法還具有分析速度快，能準確、及時地指出出錯位置。二十四、一個LR分析器由3個部分組成：

(1)總控程序，也可以稱為驅動程序。對所有的LR分析器總控程序都是相同的。

(2)分析表或分析函數,分析表又可分為動作表(ACTION)和狀態轉換(GOTO)表兩個部分，它們都可用二維數組表示。

(3)分析棧，包括文法符號棧和相應的狀態棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態和當前輸入符號所決定(LR(0)分析器不需向前查看輸入符號)。二十五、拓廣文法：在原文法G中增加一個產生式Ｓ′→S，S是原文法G的開始符號，所得到的新文法稱為原文法G的拓廣文法。而S′為拓廣后文法G′的開始符號。活前綴：在規范句型中，不包括該句型句柄右邊符號的前綴稱之為活前綴。可歸前綴：活前綴與句柄有3種關系，：活前綴不含句柄的任何符號；：活前綴含有句柄的部分符號；：活前綴包含句柄的全部符號。包含句柄的全部符號的活前綴稱之為可歸前綴。

LR(0)項目：在文法G中每個產生式的右部適當位置添加一個圓點構成項目。項目分為4種：移進項目、待約項目、歸約項目、接受項目。二十六、把拓廣文法的第一個項目{S′→·S}作為初態集的核，通過求核的閉包和轉換函數，求出LR(0)項目集規范族，再由轉換函數建立狀態之間的連接關系得到識別活前綴的DFA；由識別活前綴的DFA構造LR（0）分析表；設計總控程序，利用分析表和分析棧對服從LR（0）文法的語言進行語法分析。（基本要求）

LR(0)項目集規范族的方法是通過定義和構造拓廣文法的項目I的閉包（closure（I）），和轉換函數（Go（I，X）），從而直接構造出識別文法活前綴的DFA。要求學生能夠根據文法，采用LR(0)項目集規范族的方法，直接構造出LR(0)分析表。

LR(0)文法的限制是一個文法的LR(0)項目集規范族中不存在移進-歸約沖突和歸約-歸約沖突。二十七、簡單說明語法制導翻譯的概念？答：一句話解釋：語法分析控制引導下的語義翻譯。語義翻譯即是把源程序的語義，用另一種語言正確的表示出來。具體步驟是：1、根據描述源程序的語法的文法，對源程序進行語法分析，構造一棵與源程序匹配的語法樹；2、按照語法分析的順序，執行相應產生式后面的語義子程序，得到翻譯結果，完成源程序的語法制導翻譯。二十八、語法分析與語義翻譯有什么關系呢？

它們之間的聯系就在語法樹。語法分析就是通過采用自上而下的方法，或者采用自底向上的方法構造一棵與輸入符號串匹配的語法樹。從而分析判斷源程序在形式上是否存在語法錯誤，是否服從程序設計語言的語法規則。而語義與語法樹有關。我們在討論二義性文法時，就是用語法樹說明的。二義性文法的定義如下：如果對于某文法的一個句子存在兩棵不同的語法樹，則該句子是二義性的。而該文法是二義性文法。二十九、描述語義的工具什么？描述語義的工具是屬性文法。屬性文法建立了每個文法符號的屬性。屬性又分為繼承屬性和綜合屬性。它們的區分，不在屬性本身，而在于屬性的表示方式。一個文法符號的屬性可以用其它文法符號的屬性表示。簡單說：如果這種表示與繼承有關則稱之為繼承屬性；而如果表示與繼承無關的則稱之為綜合屬性。一個產生式中各個文法符號屬性之間的關系實際上表達了該產生式的語義。三十、編譯中的語義處理是指兩個功能：第一，審查每個語法結構的靜態語義，即驗證語法結構合法的程序是否真正有意義。有時把這個工作稱為靜態語義分析或靜態審查。第二，如果靜態語義正確，語義處理則要執行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標代碼。語義處理又稱為語義動作，它是依靠執行語義子程序完成的。

三十一、靜態語義分析通常包括：①類型檢查。②控制流檢查。③一致性檢查。④相關名字檢查。⑤名字的作用域分析。在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯的辦法稱作語法制導翻譯。三十二、編譯程序所使用的中間代碼有多種形式。常見的有逆波蘭記號、三元式、四元式和樹形表示。三十三、符號表的作用：

①收集保存符號屬性

②上下文語義的合法性檢查的依據

③作為目標代碼生成階段地址分配的依據。三十四、代碼優化：某些編譯程序在中間代碼或目標代碼生成之后要對生成的代碼進行優化。所謂優化，實質上是對代碼進行等價變換，使得變換后的代碼運行結果與變換前代碼運行結果相同，而運行速度加大或占用存儲空間少，或兩者都有。編譯過程中可進行的優化可按階段劃分：優化可在編譯的不同階段進行，分為中間代碼一級和目標代碼一級的優化。可按優化涉及的程序范圍劃分：對同一階段，分為局部優化,循環優化和全局優化。最常用的代碼優化技術有刪除多余運算，循環不變代碼外提，強度削弱，變換循環控制條件，合并已知量與復寫傳播，以及刪除無用賦值等等。三十五、代碼生成器是把某種高級程序設計語言編寫的程序經過語法、語義分析，或再經過優化后的中間代碼作為輸入，將其轉換成特定機器的機器語言或匯編語言作為輸出，這樣的轉換程序稱為代碼生成器。代碼生成器的設計要著重考慮目標代碼的質量問題。衡量目標代碼的質量主要從占用空間和執行效率兩個方面綜合考慮。提高目標代碼的運行效率,需要討論在一個基本塊內如何充分利用寄存器和根據寄存器分配的原則給出寄存器分配的一般算法。一個高級程序設計語言編譯程序的代碼生成部分在編譯中起著關鍵性的作用，而它又與計算機硬件的結構乃致細節緊密相關，這導致了代碼生成的可移植性及自動生成算法的研究，無論在理論上還是在實踐上都相當困難。

（二）應用題1、文法G（S）的產生式為：S→aAS,A→SbA,A→aA,A→b,S→a,請寫出該文法的非終結符號集、終結符號集及文法的開始符號，根據文法畫出句型aSbSbaAa的語法樹，并且指出該句型的短語、直接短語和句柄？答：該文法的非終結符號集是{S,A}、終結符號集是{a,b}及文法的開始符號是{S}

句型aSbSbaAa的語法樹為：

該句型的短語為：aA,SbaA,SbSbaA,aSbSbaAa,a直接短語為：aA,a句柄為：aA2、正規式為：b((ab)*|bb)ba，請根據所列正規式，畫出對應的NFA的狀態轉換圖，并且將NFA確定化，畫出對應的DFA的狀態轉換圖。答：（1）正規式為：b((ab)*|bb)ba對應的NFA的狀態轉換圖如下：（2）利用轉換矩陣將以上NFA確定化，轉換矩陣如下：

（3）將狀態重新編號，NFA確定化后，生成DFA狀態轉換矩陣如下：

（4）DFA狀態轉換圖如下：

3、請根據文法G寫出所有產生式的預測符號集，并且判定該文法是否是LL(1)文法，如果是，請畫出對應的預測符號表。文法G(S)：S→aBAA→Ba|εB→bB|a答：（1）求出各個產生式的預測符號集：

Select(S→aBA)={a}Select(A→Ba)={b,a}Select(A→ε)={#}Select(B→bB)={b}Select(B→a)={a}(2)由于Select(A→Ba)∩Select(A→ε)=ΦSelect(B→bB)∩Select(B→a)=Φ

所以該文法是LL(1)文法。(3)該文法對應的LL(1)預測符號表如下：4、寫出下面所列的文法的拓廣文法，并且找出該拓廣文法所有的項目，請構造識別該文法所有活前綴的NFA。文法G(S)：S→SbBa|BB→a|ε

答：（1）該文法的拓廣文法是：