編譯原理概念期末總結復習

翻譯程序:把一種語言程序轉換成另一種語言程序，且在功能上是相同的這樣的程序。編譯程序：把高級語言轉換成低級語言，且在功能上是相同的這樣的程序。

解釋程序：邊解釋邊執(zhí)行源程序的程序。區(qū)別：編譯程序有中間代碼，而解釋程序沒有。編譯過程的五個階段：

1、詞法分析任務：對構成源程序的字符串進行掃描和分解，識別出一個個單詞。

2、語法分析任務：在詞法分析的基礎上，根據(jù)語言規(guī)則，把單詞符號串分解成各類語法

單位。

3、語義分析和中間代碼產(chǎn)生任務：對語法分析所識別出的各類語法范疇，分析其含義，

并進行初步翻譯。

4、優(yōu)化任務：對前段產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為高效

的目標代碼。

5、目標代碼生成任務：把中間代碼變換成特定機器上的低級語言代碼。

編譯程序的七個部分詞法分析器，語法分析器、語義分析與中間代碼產(chǎn)生器、優(yōu)化器、目標代碼生成器、表格管理和出錯處理。

編譯程序生成的五個辦法：機器語言、高級語言、移植、自編譯方式和使用工具自動生成。詞法規(guī)則：指單詞符號的形成規(guī)則。（也就是正規(guī)式）

語法規(guī)則：規(guī)定了如何從單詞符號形成更大的結構。就是語法單位的形成規(guī)則�？兆郑翰话�含任何符號的序列。閉包：

中所有的符號組成的集合。

上下文無關文法是指：所定義的語法范疇是完全獨立于這種范疇可能出現(xiàn)的環(huán)境的文法。上下文無關文法的四個組成部分：一組終結符號、一組非終結符號、一個開始符號和一組產(chǎn)生式。

終結符號也就是不可再分的基本符號。

非終結符號是用來代表語法范疇，表示一定符號串的集合。開始符號是語言中我們最感興趣的語法范疇。產(chǎn)生式是定義語法范疇的書寫規(guī)則。

句子：文法中從開始符號推導的終結符號串。句型：從開始符號推導的符號串。語言：文法中所有句子的集合。

程序語言的單詞符號分為五種：關鍵字、標識符、常數(shù)、運算符和界符。二元式表示：（種類，屬性）

正規(guī)式的運算符有三種：或，連接和閉包。優(yōu)先順序是：閉包，連接，或。

DFA怎么識別字：若存在一條從初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有弧的標記符連接成的字是a，則稱a可為DFA所識別。

DFA怎么識別空字：若DFA的初態(tài)結點同時又是終態(tài)結點，則空字可為DFA所識別。NFA怎么識別字：若存在一條從某一初態(tài)結點到終態(tài)結點的通路，且這條通路上所有弧的標記字依序連接成的字等于a，則稱a可為NFA識別。

NFA怎么識別空字：若M的某些結點即是初態(tài)又是終態(tài)結點，或者存在一條從某個初態(tài)結點到某個終態(tài)結點的空通路，那么，空字可為M所識別。語言的語法結構是用上下文無關文法描述的。

語法分析分為兩類：自上而下分析法，自下而上分析法。

自上而下分析法面臨的問題：1.文法的左遞歸問題。2.回溯3.成功可能是暫時的，產(chǎn)生虛假匹配。4.難于知道輸入串中出錯的確切位置。5.效率低，代價高。為什么消除左遞歸？因為含有左遞歸的文法將自上而下分析的過程陷入無限循環(huán)。為什么消除回溯？因為回溯統(tǒng)一做一大堆無效的工作。

自下而上分析法：從輸入串開始，逐步進行歸約，知道歸約到文法的開始符號。短語：符號串推導過程中某非終結符推導的部分。

直接短語：符號串推導過程中某非終結符一步推導的部分。句柄：一個句型的最左直接短語。最左歸約是最有推導的逆過程。

中間語言形式：后綴式，三元式，四元式，間接三元式。中間語言的好處：1.便于進行與機器無關的代碼優(yōu)化工作。2.使編譯程序改變目標機更容易。3.使編譯程序的結構在邏輯上更為簡單，以中間語言為界面，編譯前端和后端的借口更清晰。

擴展閱讀：編譯原理概念整理

翻譯程序：能夠把某種語言轉換成另一種語言，而后者與前者在邏輯上是等價的。

編譯過程：詞法、語法、語義分析與中間代碼、優(yōu)化、目標代碼生成

詞法分析：輸入源程序，對構成源程序關鍵字、標識符、常數(shù)、運算符、界符含有左遞歸的文法將使自上而下的分析過程陷入無限循環(huán)。

LL(1)分析條件:當一個文法不含左遞歸，并且滿足每個非終結符的所有候選首符集兩兩不相交的條件

E→E1orME2:backpatch(E1.F,M.quad);

E.T=merge(E1.T,E2.T)E.F=E2.F

E→E1andME2:backpatch(E1.T,M.quad)

E.T=E2.T

E.F=merge(E1.F,E2.F)

的字符串進行掃描和分解，識別出一個個單詞。

語法分析：在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位。

語義分析與中間代碼產(chǎn)生：對語義分析所識別出的各類語法范疇，分析其含義并進行初步翻譯（產(chǎn)生中間代碼）；優(yōu)化：優(yōu)化的任務在于對前段產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為高效（省時間和空間)的目標代碼。

目標代碼生成：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定存儲器上的低級語言代碼。

編譯程序結構：表格管理、出錯處理編譯前端：由與源語言有關但與目標語言無關的那些部分組成，包括詞法分析、語義分析、語義分析與中間代碼產(chǎn)生。

后端：編譯程序中與目標語言有關那些部分，優(yōu)化與目標代碼生成。后端不依賴于源語言而僅僅依賴于中間語言。詞法規(guī)則是指單詞符號的形成規(guī)則。語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結構（語法單位）。

所謂一個語言的語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義，這些規(guī)則稱為語義規(guī)則。文法是描述語言的語法結構的形式規(guī)則

上下文無關文法：是這樣一種文法，它所定義的語法范疇是完全獨立于這種范疇可能出現(xiàn)的環(huán)境。

上下文無關文法組成：一組終結符號一組非終結符號，一個開始符號以及一組產(chǎn)生式。

開始符號：是一個特殊的非終結符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”

產(chǎn)生式：是定義語法范疇的一種書寫規(guī)則。

二義性：如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。LL(1)的含義:第一個L表示從左到右掃最左規(guī)約=規(guī)范規(guī)約：A描輸入串，第二個L表示最左推導，1最右推導=規(guī)范推導：B

表示分析時每一步只需向前查看一個符號

自上而下分析的問題:①文法含有左遞歸時，分析過程會陷入無限循環(huán)②回溯浪費分析時間③某一非終結符用某一候選式匹配成功時，可能是暫時的④分析不成功時，難以找到出錯位置

自下而上分析的問題:怎樣判斷棧頂?shù)亩陶Z:每棵子樹對應一個短語

符號串的可歸約性，以及如何歸約。直接短語:只有兩層的子樹對應的短語一個句型的最左直接短語稱為該句型句柄:最左直接短語的句柄。

E→TE’在形式語言中最右推導常被稱為規(guī)范ProcedureE推導，由規(guī)范推導所得的句型稱為規(guī)范BeginT;E’句型，如果文法無二義的，那么規(guī)范推End導（最右推導）的逆過程必是規(guī)范歸約

（最左歸約)

E’→+TE’|屬性分為兩類：綜合屬性，繼承屬性，ProcedureE’綜合屬性用于“自下而上”傳遞信息，Ifsym=’+’then

Begin

繼承屬性用于“自上而下”傳遞信息。AdvanceT;E’在上下文無關文法的基礎上，為每個文End法符號（終結符或非終結符）配備若干相關的“值”（稱為屬性）

F→(E)|iProcedureF

語義規(guī)則：文法每個產(chǎn)生式都配備了一Ifsym=’i’thenadvance組屬性的計算規(guī)則。

Elseifsym=’(’then

語法制導翻譯：由源程序的語法結構所Begin

AdvanceE

驅動的處理辦法。

Ifsym=’)’thenadvance輸入串-----語法樹-------依賴圖--------語Elseerror義規(guī)則計算次序

End靜態(tài)檢查和中間代碼產(chǎn)生的地位：Elseerror----語法分析器-----靜態(tài)檢查器-------中間代碼產(chǎn)生器-------優(yōu)化器-------

屬性文法:對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，在上下文無關文法的基礎上，為每個符號都配備了若干相關屬性。中間語言形式：后綴式，三地址代碼（包括三元式，四元式、間接三元式），DAG圖表示

后綴式表示法（逆法蘭表示法）：把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）

四元式:(OPArg1Arg2Result)三元式:(OPArg1Arg2)

翻譯程序：能夠把某種語言轉換成另一種語言，而后者與前者在邏輯上是等價的。

編譯過程：詞法、語法、語義分析與中間代碼、優(yōu)化、目標代碼生成

詞法分析：輸入源程序，對構成源程序二義的。

關鍵字、標識符、常數(shù)、運算符、界符含有左遞歸的文法將使自上而下的分析過程陷入無限循環(huán)。

LL(1)分析條件:當一個文法不含左遞歸，并且滿足每個非終結符的所有候選首符集兩兩不相交的條件

三元式:(OPArg1Arg2)

E→E1orME2:backpatch(E1.F,M.quad);

E.T=merge(E1.T,E2.T)E.F=E2.F

E→E1andME2:backpatch(E1.T,M.quad)

E.T=E2.T

E.F=merge(E.F,E.F)

的字符串進行掃描和分解，識別出一個個單詞。

語法分析：在詞法分析的基礎上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位。

語義分析與中間代碼產(chǎn)生：對語義分析所識別出的各類語法范疇，分析其含義并進行初步翻譯（產(chǎn)生中間代碼）；優(yōu)化：優(yōu)化的任務在于對前段產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為高效（省時間和空間)的目標代碼。

目標代碼生成：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定存儲器上的低級語言代碼。

編譯程序結構：表格管理、出錯處理編譯前端：由與源語言有關但與目標語言無關的那些部分組成，包括詞法分析、語義分析、語義分析與中間代碼產(chǎn)生。

后端：編譯程序中與目標語言有關那些部分，優(yōu)化與目標代碼生成。后端不依賴于源語言而僅僅依賴于中間語言。詞法規(guī)則是指單詞符號的形成規(guī)則。語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結構（語法單位）。

所謂一個語言的語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義，這些規(guī)則稱為語義規(guī)則。文法是描述語言的語法結構的形式規(guī)則

上下文無關文法：是這樣一種文法，它所定義的語法范疇是完全獨立于這種范疇可能出現(xiàn)的環(huán)境。

上下文無關文法組成：一組終結符號一組非終結符號，一個開始符號以及一組產(chǎn)生式。

開始符號：是一個特殊的非終結符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”

產(chǎn)生式：是定義語法范疇的一種書寫規(guī)則。

二義性：如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是

12LL(1)的含義:第一個L表示從左到右掃最左規(guī)約=規(guī)范規(guī)約：A描輸入串，第二個L表示最左推導，1最右推導=規(guī)范推導：B

表示分析時每一步只需向前查看一個符號

自上而下分析的問題:①文法含有左遞歸時，分析過程會陷入無限循環(huán)②回溯浪費分析時間③某一非終結符用某一候選式匹配成功時，可能是暫時的④分析不成功時，難以找到出錯位置

自下而上分析的問題:怎樣判斷棧頂?shù)亩陶Z:每棵子樹對應一個短語

符號串的可歸約性，以及如何歸約。直接短語:只有兩層的子樹對應的短語一個句型的最左直接短語稱為該句型句柄:最左直接短語的句柄。

E→TE’在形式語言中最右推導常被稱為規(guī)范ProcedureE推導，由規(guī)范推導所得的句型稱為規(guī)范BeginT;E’句型，如果文法無二義的，那么規(guī)范推End導（最右推導）的逆過程必是規(guī)范歸約

（最左歸約)

E’→+TE’|屬性分為兩類：綜合屬性，繼承屬性，ProcedureE’綜合屬性用于“自下而上”傳遞信息，Ifsym=’+’then

Begin

繼承屬性用于“自上而下”傳遞信息。AdvanceT;E’在上下文無關文法的基礎上，為每個文End法符號（終結符或非終結符）配備若干相關的“值”（稱為屬性）

F→(E)|iProcedureF

語義規(guī)則：文法每個產(chǎn)生式都配備了一Ifsym=’i’thenadvance組屬性的計算規(guī)則。

Elseifsym=’(’then

語法制導翻譯：由源程序的語法結構所Begin

AdvanceE

驅動的處理辦法。

Ifsym=’)’thenadvance輸入串-----語法樹-------依賴圖--------語Elseerror義規(guī)則計算次序

End靜態(tài)檢查和中間代碼產(chǎn)生的地位：Elseerror

----語法分析器-----靜態(tài)檢查器-------中間代碼產(chǎn)生器-------優(yōu)化器-------

屬性文法:對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，在上下文無關文法的基礎上，為每個符號都配備了若干相關屬性。中間語言形式：后綴式，三地址代碼（包括三元式，四元式、間接三元式），DAG圖表示

后綴式表示法（逆法蘭表示法）：把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）

四元式:(OPArg1Arg2Result)

友情提示：本文中關于《編譯原理概念期末總結復習》給出的范例僅供您參考拓展思維使用，編譯原理概念期末總結復習：該篇文章建議您自主創(chuàng)作。

來源：網(wǎng)絡整理 免責聲明：本文僅限學習分享，如產(chǎn)生版權問題，請聯(lián)系我們及時刪除。

《編譯原理概念期末總結復習》由互聯(lián)網(wǎng)用戶整理提供,轉載分享請保留原作者信息,謝謝!
鏈接地址：http://www.hmlawpc.com/gongwen/747463.html

• 上一篇：汽車維修技術經(jīng)驗總結
• 下一篇：汽車維修技術經(jīng)驗總結