編譯原理總復習2016

1、 1 1 題型及分值題型及分值 2 2 教材各章知識點概覽教材各章知識點概覽 3 3 計算題題型計算題題型一、判斷題 （15=5）二、填空題 （110=10）三、選擇題 （25=10）四、簡答題 （本題共35分）:其中包括兩個名詞解釋。五、計算題 （10+15+15=40） 返回編譯程序概論編譯程序概論 1文法和語言文法和語言 2詞法分析與有限自動機詞法分析與有限自動機 3自上而下語法分析方法自上而下語法分析方法 4自下而上語法分析方法自下而上語法分析方法 5語法制導翻譯和語義分析語法制導翻譯和語義分析 6符號表符號表 7代碼優(yōu)化代碼優(yōu)化 8（1）基本概念，（2）編譯過程的五個階段，各階段的任

2、務及其依循的規(guī)則、描述工具分別是什么？除了這個5個階段之外，還應該有哪兩個重要內容？五個邏輯階段：詞法分析、語法分析、語義分析和中間代碼產生、代碼優(yōu)化和目標代碼生成。除了這五個階段之外，編譯程序的每個階段都涉及到表格管理和錯誤處理這兩個重要內容。（3）編譯錯誤的種類從編譯程序的角度來看，源程序中的錯誤主要分為：語法錯誤 和 語義錯誤兩類錯誤。（4）高級程序設計語言翻譯的兩種方式以及它們的區(qū)別高級程序設計語言的翻譯主要有兩種方式：編譯方式 和 解釋方式。區(qū)別：是否生成目標代碼。（1）基本概念、（2）對文法G，能夠給出給定句型或句子的最左推導及最右推導序列，并畫出其對應的語法分析樹。（3）能夠計算

3、某文法的語言。（4）理解文法的二義性，能夠說明一個文法是二義的。（5）形式語言分類(chomsky,1956)u0型 普通（短語）文法 u1型 上下文有關文法u2型 上下文無關文法u3型 線性（正規(guī)、正則）文法3型2型1型0型（1）基本概念、（2）詞法分析器的任務及其輸出形式任務：自左至右逐個字符地對源程序進行掃描，按語言的構詞規(guī)則識別出一個個單詞，把作為字符串的源程序改造為單詞符號串的中間程序。輸出形式：二元式 （ 單詞種別， 單詞符號的屬性值）（3）單詞符號的種類關鍵字、標識符、常數(shù)、運算符、界符（4）正規(guī)文法、正規(guī)式、有限自動機之間的相互等價性定理（5）正規(guī)式 NFA DFA 最小化DF

4、A（1）語法分析的方法根據(jù)語法分析樹建立方向的不同，將語法分析分成兩類：自上而下語法分析方法和自下而上語法分析方法。（2）自上而下分析的基本思想窮舉試探法（3）自上而下分析面臨的兩個最主要的問題左遞歸、回溯（4）自上而下分析的基本方法 LL（1）分析法、遞歸下降分析器（5）左遞歸（直接、間接）和回溯的消除u 直接左遞歸的消除u 間接左遞歸的消除排序代入及消除左遞歸化簡12m12nPP|P|P|12n12mPP |P |PPP |P |P | （5）左遞歸（直接、間接）和回溯的消除u 回溯的消除：提左公因子12n12mA | | | | |12m12nAA | | |A | | （6）LL(1)

5、的含義LL(1)中的第一個L表示從左至右掃描輸入串，第二個L表示最左推導，1表示分析時每一步只需向前查看一個符號。（7）LL(1)分析器的組成部分輸入緩沖區(qū)、分析棧、分析表、總控程序（8）LL(1)分析的四種動作成功、匹配、推導、報錯（9）LL(1)文法的判定條件文法不含左遞歸。文法中每一個非終結符A的各個產生式的候選首符集兩兩不相交。即，若則 對文法中的每個非終結符A，若它存在某個候選首符集包含，則如果一個文法G滿足以上條件，則稱該文法G為。n21|Aj)(i)FIRST()FIRST(jiFOLLOW(A)FIRST(A)（10）LL(1)分析方法假設要用非終結符A進行匹配，面臨的輸入符號

6、為a，關于A的所有產生式為則LL(1)分析算法如下：若 ，則指派 去執(zhí)行匹配任務。若a不屬于任何一個候選首符集，則v若屬于某個 且 ，則讓A與自動匹配；v否則，a的出現(xiàn)是一種語法錯誤。根據(jù)LL(1)文法的條件，每一步這樣的工作都是確信無疑的。n21|A)FIRST(aii)FIRST(iFOLLOW(A)a（11）FIRST集和FOLLOW集的構造（12）預測分析表的構造（1）基本概念、（2）自下而上分析的基本思想及其核心基本思想：移進-歸約核心問題：可歸約串的界定（3）自下而上分析的基本方法u算符優(yōu)先分析法：以最左素短語作為可歸約串，非規(guī)范歸約uLR分析法：以句柄作為可歸約串，規(guī)范歸約（4）

7、給定一個文法的句型，找出其短語、直接短語、句柄、素短語和最左素短語方法：首先畫出句型的語法分析樹，然后根據(jù)語法樹尋找。u每棵子樹的葉子結點自左至右排列構成一個相對于子樹根的短語。u每棵簡單子樹（只有父子兩代）的葉子結點自左至右排列構成一個直接短語。u最左簡單子樹的葉子結點自左至右排列構成一個句柄。u將所有短語中至少含一個終結符的短語，按長度從小到大排列，長度最短的認定為素短語，然后考察其余長度較大的，若不包含更小的素短語，則也為素短語。位于句型中最左邊的素短語即為最左素短語。（5）算符文法與算符優(yōu)先文法算符文法：任意產生式右部不含兩個連續(xù)的非終結符，（.QR.）算符優(yōu)先文法：算符文法中任意兩個

8、終結符之間至多只含“”、“”、“=”三種關系之一。算符優(yōu)先關系是有序的，但不滿足對稱性和傳遞性，即對于文法G的終結符a、b和c：如果aa；如果存在a=b和b=c，不一定有b=a或a=c；如果存在ab和bc，也不能得出ac。（6）FIRSTVT集與LASTVT集的計算FIRSTVT：若有產生式Pa或 PQa，則aFIRSTVT(P)；：若aFIRSTVT(Q)且有產生式 PQ，則aFIRSTVT(P) ；：反復使用以上兩條規(guī)則，直到FIRSTVT(P)不再增大為止。LASTVT：若有產生式Pa或 PaQ，則aLASTVT(P)；：若aLASTVT(Q)且有產生式 PQ，則aLASTVT(P) ；

9、：反復使用以上兩條規(guī)則，直到LASTVT(P)不再增大為止。()|,TNFIRSTVTPaPaPQ aaVQV或()|,TNLASTVTPaPaPaQ aVQV或（7）算符優(yōu)先關系表的構造：對形如Pab或PaQb的產生式，有a=b；：對形如PaR的產生式，若有bFIRSTVT(R)，則ab；：對于語句括號#，有#=#，且若aFIRSTVT(S)和bLASTVT(S)，則有#。（8）算符優(yōu)先分析算法最左素短語的尋找依據(jù)：（9）算符優(yōu)先分析算法算符優(yōu)先分析的特點：u算符優(yōu)先分析一般并不等價于規(guī)范歸約u無法使用單非產生式(如：TF)進行歸約。u算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產生式。

10、u可能將本來不是句子的輸入串誤認為是句子。（10）LR分析器的基本思想及其組成部分基本思想：記住歷史、展望未來、定奪現(xiàn)在組成部分：輸入緩沖區(qū)、分析棧（狀態(tài)、符號）、分析表（動作、轉換）、總控程序（11）四類LR分析表LR分析表是LR分析器的核心，主要有以下幾種分析表：LR(0)表、 SLR(1)表（即簡單LR表）、LR(1)表（即規(guī)范LR表）、LALR表（即向前LR表）。其中，L代表自左至右掃描輸入串，R代表構建最右推導的逆過程，1代表分析時每一步至多向前查看一個符號，S代表簡單的。（12）LR分析器的四種動作移進、歸約、接受、報錯（13）LR分析器的兩種沖突移進歸約 沖突 和 歸約歸約 沖突

11、（14）四類不同的項目項目類型項目類型形形 式式說說 明明歸約項目A這類項目表示句柄恰好包含在棧頂中，即當前棧中符號正好為可歸前綴，應按A進行歸約。接受項目SS是文法唯一的開始符號。這類項目實際是特殊的歸約項目，即按S進行歸約，可直接歸約到文法開始符號，表示分析成功。移進項目AaaVT，這類項目表示當前棧中符號串為不完全包含句柄的活前綴，為構成可歸前綴，需將a移進分析棧。待約項目ABBVN，這類項目表示當前棧中符號串為不完全包含句柄的活前綴，為構成可歸前綴，應先把當前輸入字符串中的相應內容先歸約到B。（15）四類LR分析表的構造拓廣文法構造LR(0)（LR(0)和SLR分析表）或LR(1)（L

12、R(1)和LALR分析表）項目集規(guī)范簇構造相應分析表（16）LR文法的特點uLR文法肯定是無二義的，一個二義文法決不會是LR文法。uLR分析法比預測分析法更加一般化。uLR(0)文法一定是SLR文法，SLR文法和LALR文法一定是LR(1)文法。（1）基本概念 、（2）屬性分類綜合屬性：用于“自下而上”地傳遞信息。繼承屬性：用于“自上而下”地傳遞信息。終結符號只有綜合屬性，由詞法分析器提供。非終結符既可有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。（3）語義規(guī)則的表示（4）常見的中間代碼的幾種形式后綴式（逆波蘭表示式）圖表示法u抽象語法樹uDAG圖三地址代碼u四元

13、式u三元式u間接三元式（5）后綴式（逆波蘭式）的表示把運算量（操作數(shù)）寫在前面，把運算符寫在后面（后綴）的一種表達式表示方法。其歸納定義如下：如果E是一個變量或常數(shù)，則E的后綴式是E自身。如果E是E1 op E2 形式的表達式，op是二元操作符，則E的后綴式為E1E2op，其中E1，E2分別是E1和E2的后綴式。若E是（E1）形式的表達式，則E的后綴式就是E1的后綴式。（6）將以下語句翻譯為四元式序列表達式（算術及布爾）賦值語句IF語句WHILE語句（7）參數(shù)傳遞的幾種方式傳地址、 傳值、傳名、得結果（1）符號表的基本組成、基本操作組成：一張符號表的每一項入口包含：名字欄和信息欄 操作：查表、填表、訪表、更新、刪除（2）內情向量的基本表項在編譯過程中，碰到數(shù)組的說明時，通常將數(shù)組的有關信息記錄在一個內情向量表中，這些信息包括：維數(shù)、首地址、各維界差、各維上界、各維下界、數(shù)組元素類型、地址不變量。（1）基本概念（2）代碼優(yōu)化遵循的原則 等價原則、有效原則、合算原則（3）優(yōu)化分類根據(jù)優(yōu)化對象所涉及的程序范圍劃分為：局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。 （4）常見的優(yōu)化的幾種方法刪除公共子表達式、復寫傳播