1、總復習總復習編譯原理編譯原理（一）（一） 基本概念題：基本概念題：一、一、編譯程序的概念編譯程序的概念 編譯程序是現代計算機系統的基本組成部分之一。編譯程序是現代計算機系統的基本組成部分之一。簡而言之簡而言之, 編譯程序編譯程序就是一種語言翻譯程序。就是一種語言翻譯程序。所謂翻所謂翻譯程序，是指這樣一個程序，它能將高級程序設計語譯程序，是指這樣一個程序，它能將高級程序設計語言程序翻譯成邏輯等價的低級語言言程序翻譯成邏輯等價的低級語言( (匯編語言匯編語言, ,機器語機器語言言) ) 程序。程序。編譯程序一般由詞法分析程序、語法分析編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼

2、生成程序、目標代碼程序、語義分析程序、中間代碼生成程序、目標代碼生成程序、代碼優化程序、表格管理程序和出錯處理生成程序、代碼優化程序、表格管理程序和出錯處理程序等成分構成。程序等成分構成。 一個編譯軟件，實際涉及三種語言：源語言、一個編譯軟件，實際涉及三種語言：源語言、目標語言、實現語言。目標語言、實現語言。 源語言：源語言：Source Language 目標語言：目標語言：Target or Object Language 實現語言：實現語言：Implementation L 常常使用常常使用T型圖來表示的一個編譯器涉及的三個型圖來表示的一個編譯器涉及的三個語言之間的關系。語言之間的關系。

3、二、請解釋編譯程序的前端和后端的概念，試問前端二、請解釋編譯程序的前端和后端的概念，試問前端通常包括那些階段，后端包括那些階段？通常包括那些階段，后端包括那些階段？ 編譯程序的前端只依賴于源語言，由幾乎獨立于編譯程序的前端只依賴于源語言，由幾乎獨立于目標機器的階段或階段的一部分組成。編譯程序的前目標機器的階段或階段的一部分組成。編譯程序的前端通常包括詞法分析程序、語法分析程序、語義分析端通常包括詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序及相關的表格管理程序和出程序、中間代碼生成程序及相關的表格管理程序和出錯處理程序。編譯程序的后端是指編譯器中依賴于目錯處理程序。編譯程序的后端是

4、指編譯器中依賴于目標機器的部分標機器的部分,它們一般獨立于源語言，而與中間代它們一般獨立于源語言，而與中間代碼有關。通常包括目標代碼生成程序、代碼優化程序碼有關。通常包括目標代碼生成程序、代碼優化程序以及相關的表格管理程序和出錯處理程序。以及相關的表格管理程序和出錯處理程序。三、三、語言的語法描述語言的語法描述 語言的語法描述方法有其三，用自然語言描述語言的語法描述方法有其三，用自然語言描述語言的語法，用語法圖描述語言的語法和用巴科斯語言的語法，用語法圖描述語言的語法和用巴科斯-瑙爾范式及擴充的巴科斯瑙爾范式及擴充的巴科斯-瑙爾范式瑙爾范式 (EBNF)兩種兩種形式給出語言的語法描述。形式給出

5、語言的語法描述。 用語法圖描述語言的語法與用語法圖描述語言的語法與EBNF描述相比較：描述相比較： 語法圖描述：語法圖描述： 直觀，易讀，易寫。直觀，易讀，易寫。 EBNF表示：形式化強，易機器識別。表示：形式化強，易機器識別。四、四、闡明語法的一個工具是文法，這是形式語言理闡明語法的一個工具是文法，這是形式語言理論的基本概念之一。當我們表述一種語言時，無非論的基本概念之一。當我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對于含句子，則只需列出句子的有窮集就行了，但對于含有無窮句子的語言來講

6、，存在著如何給出它的有窮有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。事實上，使用文法作為工具，不僅為表示的問題。事實上，使用文法作為工具，不僅為了嚴格地定義句子的結構，也是為了用適當條數的了嚴格地定義句子的結構，也是為了用適當條數的規則把語言的全部句子描述出來，是以有窮的集合規則把語言的全部句子描述出來，是以有窮的集合刻劃無窮的集合的工具。刻劃無窮的集合的工具。 在形式上語言是符號串的集合。在形式上語言是符號串的集合。符號串是由字符號串是由字母表中的符號所組成的任何有窮序列。母表中的符號所組成的任何有窮序列。符號串的運符號串的運算和符號串集合的運算。和、算和符號串集合的運算。和、乘

7、積、乘積、方冪與閉包。方冪與閉包。五、請寫出五、請寫出Chomcky關于文法的定義。關于文法的定義。 Chomcky文法的定義：文法文法的定義：文法G定義為四元組定義為四元組,記記為為: G=(VN,VT,P,S)其中：其中：VN 非空有限的非終結符號集非空有限的非終結符號集 VT 非空有限的終結符號集非空有限的終結符號集 P 產生式集產生式集 S 開始符號開始符號/識別符號識別符號 S VN 六、例：已知文法：六、例：已知文法： EX|E+X XY|X*Y Y（E）|i 請判定該文法是那類文法？請判定該文法是那類文法？ 答：根據答：根據 Chomcky文法的定義，該文法是文法的定義，該文法是

8、2類文類文法，即上下文無關文法。法，即上下文無關文法。七、七、*請說明有關句型、句子、句柄概念？請說明有關句型、句子、句柄概念？ 答：設答：設GS是一文法，如果符號串是一文法，如果符號串x是從文法的是從文法的識別符號推導出來的，則稱符號串識別符號推導出來的，則稱符號串x是文法是文法GS的句的句型。若符號串型。若符號串x還滿足僅由終結符號組成的條件，則還滿足僅由終結符號組成的條件，則稱稱x為為GS的句子。一個句型的最左直接短語稱為該的句子。一個句型的最左直接短語稱為該句型的句柄。句型的句柄。八、請說明有關規范句型的概念？八、請說明有關規范句型的概念？ 答：最右推導，即推導的每一步都是替換當前答：

9、最右推導，即推導的每一步都是替換當前句型最右邊的非終結符，被稱為規范推導，由規范句型最右邊的非終結符，被稱為規范推導，由規范推導得到的句型稱為規范句型。推導得到的句型稱為規范句型。九、簡單說明詞法分析程序的主要任務。九、簡單說明詞法分析程序的主要任務。 答：詞法分析程序是編譯程序的一個構成成分，答：詞法分析程序是編譯程序的一個構成成分，它的主要任務是掃描源程序，按構詞規則識別單詞，它的主要任務是掃描源程序，按構詞規則識別單詞，并報告發現的詞法錯誤。并報告發現的詞法錯誤。十、程序設計語言的單詞符號一般可分成下列十、程序設計語言的單詞符號一般可分成下列5種：種： 保留字，也稱關鍵字。保留字，也稱關

10、鍵字。 標識符，用來表示各種名字，如常量名、變標識符，用來表示各種名字，如常量名、變量名和過程名等。量名和過程名等。 常數，各種類型的常數，如常數，各種類型的常數，如25，3.1415，TRUE和和“ABC”等。等。 運算符，如運算符，如+，*，=等。等。 界符，如逗點，分號，括號等。界符，如逗點，分號，括號等。十一、程序設計語言的單詞可用正規文法描述。正十一、程序設計語言的單詞可用正規文法描述。正規文法是右線性文法規文法是右線性文法,文法文法G=(VN,VT,P,S), P中的每中的每一條規則形為一條規則形為AaB或或Aa,其中其中A,BVN ,aVT 。正規文法所描述的是正規文法所描述的是

11、VT上的正規集（正規文法描述上的正規集（正規文法描述的語言的句子的集合）。正規式也稱正則表達式，的語言的句子的集合）。正規式也稱正則表達式，也是表示正規集的數學工具。正規式說明單詞的模也是表示正規集的數學工具。正規式說明單詞的模式，也就是說明單詞組成的形式規則，正規集則是式，也就是說明單詞組成的形式規則，正規集則是滿足這些規則的單詞的集合。滿足這些規則的單詞的集合。十二、十二、*確定的有窮自動機也稱有限自動機，它是作確定的有窮自動機也稱有限自動機，它是作為一種識別裝置，它能準確地識別正規集，即識別為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合。具正規文法所

12、定義的語言和正規式所表示的集合。具體而言，一個確定的有窮自動機可以用一個五元組體而言，一個確定的有窮自動機可以用一個五元組表示，即表示，即M=(K,f, S,Z)。K是一個有窮狀態集，是一個有窮狀態集，是一個有窮字母表，是一個有窮字母表，f是轉換函數，是轉換函數，S是初態，是初態，Z是一是一個終態集。個終態集。 十三、確定的有窮自動機十三、確定的有窮自動機DFA和不確定的有窮自動機和不確定的有窮自動機NFA 的概念，對每個的概念，對每個NFA N一定存在一個一定存在一個DFA M，使得使得L(M)=L(N)。對每個。對每個NFA N存在著與之等價的存在著與之等價的DFA M。與某一。與某一NF

13、A等價的等價的DFA不唯一。不唯一。 -閉包和閉包和子集法算法將子集法算法將NFA轉換成接受同樣的語言的轉換成接受同樣的語言的DFA。十四、語法分析是編譯程序的核心部分。語法分析的十四、語法分析是編譯程序的核心部分。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給作用是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子定文法的正確句子(程序程序)，目前語法分析常用的方法，目前語法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）有自頂向下（自上而下）分析和自底向上（自下而上）分析兩大類。分析兩大類。 十五、自頂向下分析法也稱面向目標的分析方法，十五、自頂向下分析法也稱

14、面向目標的分析方法，也就是從文法的開始符號出發企圖推導出與輸入的也就是從文法的開始符號出發企圖推導出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯。自頂向下分析句子，則必能推出，反之必然出錯。自頂向下分析法又可分為確定的和不確定的兩種，確定的分析方法又可分為確定的和不確定的兩種，確定的分析方法需對文法有一定的限制，但由于實現方法簡單、法需對文法有一定的限制，但由于實現方法簡單、直觀，便于手工構造或自動生成語法分析器，因而直觀，便于手工構造或自動生成語法分析器，因而仍是目前常用的方法之一。不確定的方法即帶回溯仍是目前

15、常用的方法之一。不確定的方法即帶回溯的分析方法，這種方法實際上是一種窮舉的試探方的分析方法，這種方法實際上是一種窮舉的試探方法，因此效率低，代價高，因而極少使用。法，因此效率低，代價高，因而極少使用。在確定在確定的自頂向下語法分析中用的是最左推導。的自頂向下語法分析中用的是最左推導。 十六、請說明有關預測符號集的概念？十六、請說明有關預測符號集的概念？ 答：產生式答：產生式A預測符號集表示：在確定的自預測符號集表示：在確定的自上而下的語法分析過程中，當需要替換的非終結符是上而下的語法分析過程中，當需要替換的非終結符是A時，而當前需要匹配的終結符屬于產生式時，而當前需要匹配的終結符屬于產生式A預

16、測預測符號集中的符號，則能夠采用該產生式進行推導。當符號集中的符號，則能夠采用該產生式進行推導。當不能推出不能推出時，產生式時，產生式A預測符號集是預測符號集是的首符號的首符號集；當集；當能推出能推出時，產生式時，產生式A預測符號集是預測符號集是的首的首符號集與符號集與A的后跟符號集的并集，但是不包括的后跟符號集的并集，但是不包括。十七、十七、LL(1)文法：文法： LL(1)文法的含義是：第一個文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二表明自頂向下分析是從左向右掃描輸入串，第二個個L表明分析過程中將用最左推導，表明分析過程中將用最左推導，1表明只需向表明只需向右看一個符

17、號便可決定選擇哪個產生式或規則進右看一個符號便可決定選擇哪個產生式或規則進行推導。行推導。LL（1）方法是）方法是LL（K）方法的特例。）方法的特例。一個上下文無關文法是一個上下文無關文法是LL(1)文法的充分必要條件文法的充分必要條件是：對每個非終結符是：對每個非終結符A的兩個不同產生式，的兩個不同產生式，A, A,滿足滿足SELECT(A)SELECT(A)= 其中其中，不同時能不同時能 十八、預測分析方法是自頂向下分析的方法，一個預十八、預測分析方法是自頂向下分析的方法，一個預測分析器是由三個部分組成。測分析器是由三個部分組成。 預測分析程序預測分析程序(總控程序總控程序) 先進后出棧先

18、進后出棧(stack) 預測分析表：預測分析表以終結符號和預測分析表：預測分析表以終結符號和“#”號作為列標志，以非終結符號作為行標志，對每個號作為列標志，以非終結符號作為行標志，對每個終結符號或終結符號或“#”號用號用a表示，若表示，若aSELECT(A),則把則把A放入放入MA,a中中,把所有無定義的把所有無定義的MA,a標標上出錯標記。這就構成了預測分析表。上出錯標記。這就構成了預測分析表。 要求學員能夠對一個給定的文法判斷是否是要求學員能夠對一個給定的文法判斷是否是LL(1)文法；能構造預測分析表；能用預測分析方文法；能構造預測分析表；能用預測分析方法判斷給定的輸入符號串是否是該文法的

19、句子。法判斷給定的輸入符號串是否是該文法的句子。 （基本要求）（基本要求） 十九、某些含有左遞歸和左公共因子的文法在通過十九、某些含有左遞歸和左公共因子的文法在通過等價變換把它們消除以后可能變為等價變換把它們消除以后可能變為LL(1)文法，但需文法，但需要用要用LL(1)文法的定義判別。文法的定義判別。 （基本要求）（基本要求） 二十、自底向上分析法，也稱移進二十、自底向上分析法，也稱移進-歸約分析法，或歸約分析法，或自下而上分析。自底向上分析是自頂向下分析的逆自下而上分析。自底向上分析是自頂向下分析的逆過程過程,它是從待分析的句子出發逆向使用產生式逐步它是從待分析的句子出發逆向使用產生式逐步

20、歸約的過程。從語法分析樹的角度講，就是從語法歸約的過程。從語法分析樹的角度講，就是從語法樹的葉結點（句子）出發自下而上逐層構造語法樹，樹的葉結點（句子）出發自下而上逐層構造語法樹，每一層對應歸約過程中的一個句型。每一層對應歸約過程中的一個句型。 常用的自底向上語法分析方法有優先分析方法和常用的自底向上語法分析方法有優先分析方法和LR方法。優先分析方法又分為簡單優先方法和算符方法。優先分析方法又分為簡單優先方法和算符優先方法；優先方法；LR方法也有多種。方法也有多種。二十一、簡單優先分析法的基本思想是：通過優先關二十一、簡單優先分析法的基本思想是：通過優先關系的定義，確定了在系的定義，確定了在V

21、TVVN N中任何二個符號之間的優中任何二個符號之間的優先關系；（兩個符號之間最多只有一種關系成立），先關系；（兩個符號之間最多只有一種關系成立），對于當前的句型，通過從右至左的掃描，利用優先關對于當前的句型，通過從右至左的掃描，利用優先關系，先找到句柄的尾符號，然后找到句柄的頭符號，系，先找到句柄的尾符號，然后找到句柄的頭符號，從而找到了當前句型中應該歸約的句柄。通過歸約，從而找到了當前句型中應該歸約的句柄。通過歸約，構造一層語法樹；如此反復，直到歸約到文法的開始構造一層語法樹；如此反復，直到歸約到文法的開始符號。符號。二十二、算符優先分析的基本思想是只規定算符二十二、算符優先分析的基本思想

22、是只規定算符(廣廣義為終結符義為終結符)之間的優先關系，也就是只考慮終結符之間的優先關系，也就是只考慮終結符之間的優先關系，不考慮非終結符之間的優先關系。之間的優先關系，不考慮非終結符之間的優先關系。它是根據算符（終結符）之間的優先關系確定句型它是根據算符（終結符）之間的優先關系確定句型中歸約子串的方法。它采用的不是規范歸約，因此中歸約子串的方法。它采用的不是規范歸約，因此它的歸約子串并不是規范歸約意義上的句柄，為了它的歸約子串并不是規范歸約意義上的句柄，為了和規范歸約區分開來稱之為最左素短語，也就是說，和規范歸約區分開來稱之為最左素短語，也就是說，在算符優先分析法每步自底向上歸約時，識別和歸

23、在算符優先分析法每步自底向上歸約時，識別和歸約的是當前的最左素短語。約的是當前的最左素短語。二十三、二十三、LR分析法的分析過程是一種規范歸約過分析法的分析過程是一種規范歸約過程，規范歸約是規范推導的逆過程。規范推導是最程，規范歸約是規范推導的逆過程。規范推導是最右推導，規范歸約是其逆過程，則是最左歸約。右推導，規范歸約是其逆過程，則是最左歸約。 LR分析法的可歸約串是當前句型的句柄，即最左分析法的可歸約串是當前句型的句柄，即最左直接短語。直接短語。 對于大多數用無二義性上下文無關文法描述的對于大多數用無二義性上下文無關文法描述的語言都可以用相應的語言都可以用相應的LR分析器進行識別，而且這分

24、析器進行識別，而且這種方法還種方法還具有分析速度快，能準確、及時地指出出具有分析速度快，能準確、及時地指出出錯位置錯位置。二十四、一個二十四、一個LR分析器由分析器由3個部分組成：個部分組成：(1) 總控程序，也可以稱為驅動程序。對所有的總控程序，也可以稱為驅動程序。對所有的LR分析器總控程序都是相同的。分析器總控程序都是相同的。(2) 分析表或分析函數分析表或分析函數,分析表又可分為動作表分析表又可分為動作表(ACTION)和狀態轉換和狀態轉換(GOTO)表兩個部分，它們都表兩個部分，它們都可用二維數組表示。可用二維數組表示。(3) 分析棧，包括文法符號棧和相應的狀態棧，分析棧，包括文法符號

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

26、前綴稱之為活前綴。 可歸前綴：活前綴與句柄有可歸前綴：活前綴與句柄有3種關系，：活前綴種關系，：活前綴不含句柄的任何符號；：活前綴含有句柄的部分不含句柄的任何符號；：活前綴含有句柄的部分符號；：活前綴包含句柄的全部符號。包含句柄符號；：活前綴包含句柄的全部符號。包含句柄的全部符號的活前綴稱之為可歸前綴。的全部符號的活前綴稱之為可歸前綴。 LR(0)項目：在文法項目：在文法G中每個產生式的右部適當中每個產生式的右部適當位置添加一個圓點構成項目。項目分為位置添加一個圓點構成項目。項目分為4種：移進種：移進項目、待約項目、歸約項目、接受項目。項目、待約項目、歸約項目、接受項目。二十六、把拓廣文法的第

27、一個項目二十六、把拓廣文法的第一個項目SS作為初作為初態集的核，通過求核的閉包和轉換函數，求出態集的核，通過求核的閉包和轉換函數，求出LR(0)項目集規范族，再由轉換函數建立狀態之間的連接項目集規范族，再由轉換函數建立狀態之間的連接關系得到識別活前綴的關系得到識別活前綴的DFA；由識別活前綴的；由識別活前綴的DFA構造構造LR（0）分析表；設計總控程序，利用分析表）分析表；設計總控程序，利用分析表和分析棧對服從和分析棧對服從 LR（0）文法的語言進行語法分析。）文法的語言進行語法分析。 （基本要求）（基本要求） LR(0)項目集規范族的方法是通過定義和構造項目集規范族的方法是通過定義和構造拓廣

28、文法的項目拓廣文法的項目I的閉包（的閉包（closure（I），和轉換），和轉換函數（函數（Go（I，X），從而直接構造出識別文法活），從而直接構造出識別文法活前綴的前綴的DFA。要求學生能夠根據文法，采用。要求學生能夠根據文法，采用LR(0)項目集規范族的方法，直接構造出項目集規范族的方法，直接構造出LR(0)分析表。分析表。 LR(0)文法的限制是一個文法的文法的限制是一個文法的LR(0)項目集規項目集規范族中不存在移進范族中不存在移進-歸約沖突和歸約歸約沖突和歸約-歸約沖突。歸約沖突。二十七、二十七、簡單說明語法制導翻譯的概念？簡單說明語法制導翻譯的概念？答：答：一句話解釋：語法分析控制

29、引導下的語義翻譯。語義翻一句話解釋：語法分析控制引導下的語義翻譯。語義翻譯即是把源程序的語義，用另一種語言正確的表示出來。譯即是把源程序的語義，用另一種語言正確的表示出來。具具體步驟是：體步驟是：1、根據描述源程序的語法的文法，、根據描述源程序的語法的文法，對對源程序源程序進行進行語法分析，語法分析，構造一棵與源程序匹配的語法樹；構造一棵與源程序匹配的語法樹；2、按照語法分析的順序，執行、按照語法分析的順序，執行相應相應產生式后面的語義子程序產生式后面的語義子程序，得到翻譯結果，得到翻譯結果，完成源程序的完成源程序的語法制導翻譯。語法制導翻譯。二十八、語法分析與語義翻譯有什么關系呢？二十八、語

30、法分析與語義翻譯有什么關系呢？ 它們之間的聯系就在語法樹。語法分析就是通過采用自它們之間的聯系就在語法樹。語法分析就是通過采用自上而下的方法，或者采用自底向上的方法構造一棵與輸入符上而下的方法，或者采用自底向上的方法構造一棵與輸入符號串匹配的語法樹。從而分析判斷源程序在形式上是否存在號串匹配的語法樹。從而分析判斷源程序在形式上是否存在語法錯誤，是否服從程序設計語言的語法規則。而語義與語語法錯誤，是否服從程序設計語言的語法規則。而語義與語法樹有關。我們在討論二義性文法時，就是用語法樹說明的。法樹有關。我們在討論二義性文法時，就是用語法樹說明的。二義性文法的定義如下：如果對于某文法的一個句子存在兩

31、二義性文法的定義如下：如果對于某文法的一個句子存在兩棵不同的語法樹，則該句子是二義性的。而該文法是二義性棵不同的語法樹，則該句子是二義性的。而該文法是二義性文法。文法。二十九、描述語義的工具什么？描述語義的工具是屬性文法。二十九、描述語義的工具什么？描述語義的工具是屬性文法。屬性文法建立了每個文法符號的屬性。屬性又分為繼承屬性和屬性文法建立了每個文法符號的屬性。屬性又分為繼承屬性和綜合屬性。它們的區分，不在屬性本身，而在于屬性的表示方綜合屬性。它們的區分，不在屬性本身，而在于屬性的表示方式。一個文法符號的屬性可以用其它文法符號的屬性表示。簡式。一個文法符號的屬性可以用其它文法符號的屬性表示。簡

32、單說：如果這種表示與繼承有關則稱之為繼承屬性；而如果表單說：如果這種表示與繼承有關則稱之為繼承屬性；而如果表示與繼承無關的則稱之為綜合屬性。一個產生式中各個文法符示與繼承無關的則稱之為綜合屬性。一個產生式中各個文法符號屬性之間的關系實際上表達了該產生式的語義。號屬性之間的關系實際上表達了該產生式的語義。三十、編譯中的語義處理是指兩個功能：第一，審查每個語法三十、編譯中的語義處理是指兩個功能：第一，審查每個語法結構的靜態語義，即驗證語法結構合法的程序是否真正有意義。結構的靜態語義，即驗證語法結構合法的程序是否真正有意義。有時把這個工作稱為靜態語義分析或靜態審查。第二，如果靜有時把這個工作稱為靜態

33、語義分析或靜態審查。第二，如果靜態語義正確，語義處理則要執行真正的翻譯，即，或者將源程態語義正確，語義處理則要執行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標代碼。語義處理又稱為語義動作，它是依靠執行序翻譯成目標代碼。語義處理又稱為語義動作，它是依靠執行語義子程序完成的。語義子程序完成的。三十一、靜態語義分析通常包括：三十一、靜態語義分析通常包括： 類型檢查。類型檢查。 控制流檢查。控制流檢查。 一致性檢查。一致性檢查。 相關名字檢查。相關名字檢查。 名字的作用域分析名字的作用域分析 。在語法

34、分析過程中，隨著分析的。在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯的辦法稱作語法語義規則描述的語義動作）進行翻譯的辦法稱作語法制導翻譯。制導翻譯。三十二、編譯程序所使用的中間代碼有多種形式。常三十二、編譯程序所使用的中間代碼有多種形式。常見的有逆波蘭記號、三元式、四元式和樹形表示。見的有逆波蘭記號、三元式、四元式和樹形表示。三十三、符號表的作用：三十三、符號表的作用：收集保存符號屬性收集保存符號屬性 上下文語義的合法性檢查的依據上下文語義的合法性檢查的依據 作為目標代碼生成階段地址分配

35、的依據。作為目標代碼生成階段地址分配的依據。三十四、代碼優化：某些編譯程序在中間代碼或目三十四、代碼優化：某些編譯程序在中間代碼或目標代碼生成之后要對生成的代碼進行優化。所謂優標代碼生成之后要對生成的代碼進行優化。所謂優化，實質上是對代碼進行等價變換，使得變換后的化，實質上是對代碼進行等價變換，使得變換后的代碼運行結果與變換前代碼運行結果相同，而運行代碼運行結果與變換前代碼運行結果相同，而運行速度加大或占用存儲空間少，或兩者都有。編譯過速度加大或占用存儲空間少，或兩者都有。編譯過程中可進行的優化可按階段劃分：優化可在編譯的程中可進行的優化可按階段劃分：優化可在編譯的不同階段進行，分為中間代碼一

36、級和目標代碼一級不同階段進行，分為中間代碼一級和目標代碼一級的優化。可按優化涉及的程序范圍劃分：對同一階的優化。可按優化涉及的程序范圍劃分：對同一階段，分為局部優化段，分為局部優化,循環優化和全局優化。最常用的循環優化和全局優化。最常用的代碼優化技術有刪除多余運算，循環不變代碼外提，代碼優化技術有刪除多余運算，循環不變代碼外提，強度削弱，變換循環控制條件，合并已知量與復寫強度削弱，變換循環控制條件，合并已知量與復寫傳播，以及刪除無用賦值等等。傳播，以及刪除無用賦值等等。 三十五、代碼生成器是把某種高級程序設計語言編寫三十五、代碼生成器是把某種高級程序設計語言編寫的程序經過語法、語義分析，或再經

37、過優化后的中間的程序經過語法、語義分析，或再經過優化后的中間代碼作為輸入，將其轉換成特定機器的機器語言或匯代碼作為輸入，將其轉換成特定機器的機器語言或匯編語言作為輸出，這樣的轉換程序稱為代碼生成器。編語言作為輸出，這樣的轉換程序稱為代碼生成器。 代碼生成器的設計要著重考慮目標代碼的質量問代碼生成器的設計要著重考慮目標代碼的質量問題。衡量目標代碼的質量主要從占用空間和執行效率題。衡量目標代碼的質量主要從占用空間和執行效率兩個方面綜合考慮。提高目標代碼的運行效率兩個方面綜合考慮。提高目標代碼的運行效率,需要討需要討論在一個基本塊內如何充分利用寄存器和根據寄存器論在一個基本塊內如何充分利用寄存器和根

38、據寄存器分配的原則給出寄存器分配的一般算法。分配的原則給出寄存器分配的一般算法。 一個高級程序設計語言編譯程序的代碼生成部分一個高級程序設計語言編譯程序的代碼生成部分在編譯中起著關鍵性的作用，而它又與計算機硬件的在編譯中起著關鍵性的作用，而它又與計算機硬件的結構乃致細節緊密相關，這導致了代碼生成的可移植結構乃致細節緊密相關，這導致了代碼生成的可移植性及自動生成算法的研究，無論在理論上還是在實踐性及自動生成算法的研究，無論在理論上還是在實踐上都相當困難。上都相當困難。 （二）（二） 應用題應用題1、文法、文法G（S）的產生式為：）的產生式為：SaAS,ASbA,AaA,Ab,Sa,請寫出該文法請

39、寫出該文法的非終結符號集、終結符號集及文法的開始符號，的非終結符號集、終結符號集及文法的開始符號，根據文法畫出句型根據文法畫出句型aSbSbaAa的語法樹，并且指出的語法樹，并且指出該句型的短語、直接短語和句柄？該句型的短語、直接短語和句柄？答：該文法的非終結符號集是答：該文法的非終結符號集是S,A、終結符號集是終結符號集是a,b及及文法的開始符號是文法的開始符號是S 句型句型aSbSbaAa的語法樹為：的語法樹為： 該句型的短語為：該句型的短語為：aA,SbaA, SbSbaA, aSbSbaAa,a直接短語為：直接短語為：aA, a 句柄為：句柄為：aA2、正規式為：、正規式為：b(ab)

40、*|bb)ba，請根據所列正規式，請根據所列正規式，畫出對應的畫出對應的NFA的狀態轉換圖，并且將的狀態轉換圖，并且將NFA確定化，確定化，畫出對應的畫出對應的DFA的狀態轉換圖。的狀態轉換圖。答：（答：（1）正規式為：正規式為：b(ab)*|bb)ba 對應的對應的NFA的的狀態轉換圖如下：狀態轉換圖如下：（2）利用轉換矩陣將以上）利用轉換矩陣將以上NFA確定化，轉換矩陣如確定化，轉換矩陣如下：下： （3）將狀態重新編號，）將狀態重新編號，NFA確定化后，生成確定化后，生成DFA狀狀態轉換矩陣如下：態轉換矩陣如下： （4）DFA狀態轉換圖如下：狀態轉換圖如下： 3、請根據文法、請根據文法G寫出所有產生式的預測符號集，并寫出所有產生式的預測符號集，并且判定該文法是否是且判定該文法是否是LL(1)文法，如