編譯原理概念整理

1、精品文檔翻譯程序：能夠把某種語言轉(zhuǎn)換成另一 種語言，而后者與前者在邏輯上是等價 的。編譯過程：詞法、語法、語義分析與中 間代碼、優(yōu)化、目標代碼生成 詞法分析：輸入源程序，對構(gòu)成源程序 的字符串進行掃描和分解，識別出一個 個單詞。語法分析：在詞法分析的基礎(chǔ)上，根據(jù) 語言的語法規(guī)則，把單詞符號串分解成 各類語法單位。語義分析與中間代碼產(chǎn)生：對語義分析所識別出的各類語法范疇，分析其含義 并進行初步翻譯（產(chǎn)生中間代碼）； 優(yōu)化：優(yōu)化的任務在于對前段產(chǎn)生的中 間代碼進行加工變換，以期在最后階段 能產(chǎn)生出更為高效（省時間和空間）的目 標代碼。目標代碼生成： 把中間代碼（或經(jīng)優(yōu)化 處理之后）變換成特定存儲器

2、上的低級 語言代碼。編譯程序結(jié)構(gòu)：表格管理、出錯處理 編譯前端：由與源語言有關(guān)但與目標語 言無關(guān)的那些部分組成，包括詞法分 析、語義分析、語義分析與中間代碼產(chǎn) 生。后端：編譯程序中與目標語言有關(guān)那些 部分，優(yōu)化與目標代碼生成。后端不依 賴于源語言而僅僅依賴于中間語言。 詞法規(guī)則是指單詞符號的形成規(guī)則。 語言的語法規(guī)則規(guī)定了如何從單詞符 號形成更大的結(jié)構(gòu)（語法單位）。 所謂一個語言的語義是指這樣的一組 規(guī)則，使用它可以定義一個程序的意 義，這些規(guī)則稱為語義規(guī)則。文法是描述語言的語法結(jié)構(gòu)的 形式規(guī)則 上下文無關(guān)文法：是這樣一種文法，它 所定義的語法范疇是完全獨立于這種 范疇可能出現(xiàn)的環(huán)境。上下文無

3、關(guān)文法組成：一組終結(jié)符號一 組非終結(jié)符號，一個開始符號以及一組 產(chǎn)生式。開始符號：是一個特殊的非終結(jié)符號， 它代表所定義的語言中我們最終感興 趣的語法范疇，這個語法范疇通常稱為“句子”產(chǎn)生式：是定義語法范疇的一種書寫規(guī) 則。二義性：如果一個文法存在某個句子對 應兩棵不同的語法樹，則稱這個文法是 二義的。關(guān)鍵字、標識符、常數(shù)、運算符、界符 含有左遞歸的文法將使自上而下的分 析過程陷入無限循環(huán)。LL（1）分析條件：當一個文法不含左遞 歸，并且滿足每個非終結(jié)符的所有候選 首符集兩兩不相交的條件LL（1）的含義：第一個L表示從左到右掃 描輸入串，第二個 L表示最左推導，1 表示分析時每一步只需向前查看

4、一個 符號自上而下分析的問題：文法含有左遞歸時，分析過程會陷入無限循環(huán)回溯 浪費分析時間某一非終結(jié)符用某一 候選式匹配成功時，可能是暫時的分 析不成功時，難以找到出錯位置 自下而上分析的問題：怎樣判斷棧頂?shù)姆柎目蓺w約性，以及如何歸約。 一個句型的最左直接短語稱為該句型 的句柄。在形式語言中最右推導常被稱為規(guī)范推導，由規(guī)范推導所得的句型稱為規(guī)范 句型，如果文法無二義的，那么規(guī)范推 導（最右推導）的逆過程必是規(guī)范歸約（最左歸約）屬性分為兩類：綜合屬性，繼承屬性， 綜合屬性用于“自下而上”傳遞信息， 繼承屬性用于“自上而下”傳遞信息。 在上下文無關(guān)文法的基礎(chǔ)上，為每個文 法符號（終結(jié)符或非終結(jié)符

5、）配備若干 相關(guān)的“值”（稱為屬性） 語義規(guī)則：文法每個產(chǎn)生式都配備了一 組屬性的計算規(guī)則。語法制導翻譯：由源程序的語法結(jié)構(gòu)所 驅(qū)動的處理辦法。輸入串-語法樹 依賴圖語義規(guī)則計算次序靜態(tài)檢查和中間代碼產(chǎn)生的地位：-語法分析器-靜態(tài)檢查器 中間代碼產(chǎn)生器優(yōu)化器 屬性文法：對于文法的每個產(chǎn)生式都配 備了一組屬性的計算規(guī)則，在上下文無關(guān)文法的基礎(chǔ)上，為每個符號都配備了若干相關(guān)屬性。中間語言形式：后綴式，三地址代碼（包 括三元式，四元式、間接三元式），DAG 圖表示后綴式表示法（逆法蘭表示法）：把運 算量（操作數(shù)）寫在前面，把算符寫在 后面（后綴）四元式：（OP Arg1 Arg2 Result）三元

6、式：（OP Arg1 Arg2）E t Ei or M E2: backpatch（Ei.F,M.quad）;E.T=merge（Ei.T,E2.T）E.F=E2.FE t E1 a nd M E2: backpatch（E 1.T,M.quad） E.T=E2.TE.F=merge（E1.F,E2.F）最左規(guī)約=規(guī)范規(guī)約：A最右推導=規(guī)范推導：B a|b-Jbb短語：每棵子樹對應一個短語直接短語：只有兩層的子樹對應的短語 句柄:最左直接短語Et TEProcedure EBegi nT;E EndEt +TE? |Procedure E If sym= + the nBeginAdva ne

7、e T;E EndFt (E)|iProcedure FIf sym= i then advaneeElse if sym= ( thenBeginAdvanee EIf sym= ) then advanee Else errorEndElse error精品文檔精品文檔翻譯程序：能夠把某種語言轉(zhuǎn)換成另一 種語言，而后者與前者在邏輯上是等價 的。編譯過程：詞法、語法、語義分析與中 間代碼、優(yōu)化、目標代碼生成詞法分析：輸入源程序，對構(gòu)成源程序 的字符串進行掃描和分解，識別出一個 個單詞。語法分析：在詞法分析的基礎(chǔ)上，根據(jù) 語言的語法規(guī)則，把單詞符號串分解成 各類語法單位。語義分析與中間代碼產(chǎn)生

8、：對語義分析所識別出的各類語法范疇，分析其含義 并進行初步翻譯（產(chǎn)生中間代碼）； 優(yōu)化：優(yōu)化的任務在于對前段產(chǎn)生的中 間代碼進行加工變換，以期在最后階段 能產(chǎn)生出更為高效（省時間和空間）的目 標代碼。目標代碼生成： 把中間代碼（或經(jīng)優(yōu)化 處理之后）變換成特定存儲器上的低級 語言代碼。編譯程序結(jié)構(gòu)：表格管理、出錯處理 編譯前端：由與源語言有關(guān)但與目標語 言無關(guān)的那些部分組成，包括詞法分 析、語義分析、語義分析與中間代碼產(chǎn) 生。后端：編譯程序中與目標語言有關(guān)那些 部分，優(yōu)化與目標代碼生成。后端不依 賴于源語言而僅僅依賴于中間語言。詞法規(guī)則是指單詞符號的形成規(guī)則。語言的語法規(guī)則規(guī)定了如何從單詞符 號

9、形成更大的結(jié)構(gòu)（語法單位）。所謂一個語言的語義是指這樣的一組 規(guī)則，使用它可以定義一個程序的意 義，這些規(guī)則稱為語義規(guī)則。文法是描述語言的語法結(jié)構(gòu)的 形式規(guī)則 上下文無關(guān)文法：是這樣一種文法，它 所定義的語法范疇是完全獨立于這種 范疇可能出現(xiàn)的環(huán)境。上下文無關(guān)文法組成：一組終結(jié)符號一 組非終結(jié)符號，一個開始符號以及一組 產(chǎn)生式。開始符號：是一個特殊的非終結(jié)符號， 它代表所定義的語言中我們最終感興 趣的語法范疇，這個語法范疇通常稱為“句子”產(chǎn)生式：是定義語法范疇的一種書寫規(guī) 則。二義性：如果一個文法存在某個句子對 應兩棵不同的語法樹，則稱這個文法是 二義的。關(guān)鍵字、標識符、常數(shù)、運算符、界符 含

10、有左遞歸的文法將使自上而下的分 析過程陷入無限循環(huán)。LL（1）分析條件：當一個文法不含左遞 歸，并且滿足每個非終結(jié)符的所有候選 首符集兩兩不相交的條件LL（1）的含義：第一個L表示從左到右掃 描輸入串，第二個 L表示最左推導，1 表示分析時每一步只需向前查看一個 符號自上而下分析的問題 ：文法含有左遞 歸時，分析過程會陷入無限循環(huán)回溯 浪費分析時間某一非終結(jié)符用某一 候選式匹配成功時，可能是暫時的分 析不成功時，難以找到出錯位置 自下而上分析的問題 ：怎樣判斷棧頂?shù)?符號串的可歸約性，以及如何歸約。 一個句型的最左直接短語稱為該句型 的句柄。在形式語言中最右推導常被稱為規(guī)范推導，由規(guī)范推導所得

11、的句型稱為規(guī)范 句型，如果文法無二義的，那么規(guī)范推 導（最右推導）的逆過程必是規(guī)范歸約（最左歸約）屬性分為兩類：綜合屬性，繼承屬性， 綜合屬性用于“自下而上”傳遞信息， 繼承屬性用于“自上而下”傳遞信息。 在上下文無關(guān)文法的基礎(chǔ)上，為每個文 法符號（終結(jié)符或非終結(jié)符）配備若干 相關(guān)的“值”（稱為屬性）語義規(guī)則：文法每個產(chǎn)生式都配備了一 組屬性的計算規(guī)則。語法制導翻譯：由源程序的語法結(jié)構(gòu)所 驅(qū)動的處理辦法。輸入串-語法樹依賴圖語義規(guī)則計算次序靜態(tài)檢查和中間代碼產(chǎn)生的地位：-語法分析器-靜態(tài)檢查器中 間代碼產(chǎn)生器優(yōu)化器屬性文法：對于文法的每個產(chǎn)生式都配 備了一組屬性的計算規(guī)則，在上下文無 關(guān)文法的

12、基礎(chǔ)上，為每個符號都配備了 若干相關(guān)屬性。中間語言形式：后綴式，三地址代碼（包 括三元式，四元式、間接三元式），DAG 圖表示后綴式表示法（逆法蘭表示法）：把運 算量（操作數(shù)）寫在前面，把算符寫在 后面（后綴）四元式：（OP Arg1 Arg2 Result） 三元式：（OP Arg1 Arg2）E t Ei or M E2： backpatch（Ei.F,M.quad）;E.T=merge（Ei.T,E2.T）E.F=E2.FE t E1 a nd M E2: backpatch（E 1.T,M.quad） E.T=E2.T E.F=merge（E1.F,E2.F）最左規(guī)約=規(guī)范規(guī)約：Ab短語：每棵子樹對應一個短語直接短語：只有兩層的子樹對應的短語 句柄:最左直接短語Et TEProcedu