編譯原理概念整理(共3頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上翻譯程序：能夠把某種語言轉(zhuǎn)換成另一種語言，而后者與前者在邏輯上是等價的。編譯過程：詞法、語法、語義分析與中間代碼、優(yōu)化、目標代碼生成詞法分析：輸入源程序，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個單詞。語法分析：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位。語義分析與中間代碼產(chǎn)生：對語義分析所識別出的各類語法范疇，分析其含義并進行初步翻譯（產(chǎn)生中間代碼）；優(yōu)化：優(yōu)化的任務(wù)在于對前段產(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)境。上下文無關(guān)文法組成：一組終結(jié)符號一組非終結(jié)符號，一個開

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

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

5、由源程序的語法結(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)三元式:(OP Arg1 Arg2)EE1 or M E2: backpatch(E1.F,M.quad);E.T=m

6、erge(E1.T,E2.T)E.F=E2.FEE1 and M E2: backpatch(E1.T,M.quad)E.T=E2.TE.F=merge(E1.F,E2.F)最左規(guī)約=規(guī)范規(guī)約：A最右推導(dǎo)=規(guī)范推導(dǎo)：B短語:每棵子樹對應(yīng)一個短語直接短語:只有兩層的子樹對應(yīng)的短語句柄:最左直接短語ETEProcedure EBeginT;EEndE+TE|Procedure EIf sym=+ then Begin Advance T;EEndF(E)|iProcedure FIf sym=i then advanceElse if sym=( thenBeginAdvance EIf sym=

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

8、（或經(jīng)優(yōu)化處理之后）變換成特定存儲器上的低級語言代碼。編譯程序結(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)境。上下文

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

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

11、產(chǎn)生式都配備了一組屬性的計算規(guī)則。語法制導(dǎo)翻譯：由源程序的語法結(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)三元式:(OP Arg1 Arg2)EE1 or M E2: backpatch(E1.F,M.quad);E.T=merge(E1.T,E2.T)E.F=E2.FEE1 and M E2: backpatch(E1.T,M.quad)E.T=E2.TE.F=merge(E1.F,E2.F)最左規(guī)約=規(guī)范規(guī)約：A最右推導(dǎo)=規(guī)范推導(dǎo)：B短語:每棵子樹對應(yīng)一個短語直接短語:只有兩層的子樹對應(yīng)的短語句柄:最左直接短語ETEProcedure E