編譯原理概念期末總結(jié)復(fù)習(xí)

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

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

1、詞法分析任務(wù)：對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個(gè)個(gè)單詞。

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

單位。

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

并進(jìn)行初步翻譯。

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

的目標(biāo)代碼。

5、目標(biāo)代碼生成任務(wù)：把中間代碼變換成特定機(jī)器上的低級語言代碼。

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

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

語法規(guī)則：規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)。就是語法單位的形成規(guī)則。空字：不包含任何符號的序列。閉包：

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

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

終結(jié)符號也就是不可再分的基本符號。

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

句子：文法中從開始符號推導(dǎo)的終結(jié)符號串。句型：從開始符號推導(dǎo)的符號串。語言：文法中所有句子的集合。

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

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

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

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

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

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

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

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

直接短語：符號串推導(dǎo)過程中某非終結(jié)符一步推導(dǎo)的部分。句柄：一個(gè)句型的最左直接短語。最左歸約是最有推導(dǎo)的逆過程。

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

擴(kuò)展閱讀：編譯原理概念整理

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

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

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

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

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ìn)行掃描和分解，識別出一個(gè)個(gè)單詞。

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

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

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

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

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

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

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

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

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

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

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

表示分析時(shí)每一步只需向前查看一個(gè)符號

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

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

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

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

（最左歸約)

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

Begin

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

F→(E)|iProcedureF

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

Elseifsym=’(’then

語法制導(dǎo)翻譯：由源程序的語法結(jié)構(gòu)所Begin

AdvanceE

驅(qū)動的處理辦法。

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

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

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

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

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

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

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

詞法分析：輸入源程序，對構(gòu)成源程序二義的。

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

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

三元式:(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ìn)行掃描和分解，識別出一個(gè)個(gè)單詞。

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

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

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

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

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

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

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

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

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

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

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

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

表示分析時(shí)每一步只需向前查看一個(gè)符號

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

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

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

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

（最左歸約)

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

Begin

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

F→(E)|iProcedureF

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

Elseifsym=’(’then

語法制導(dǎo)翻譯：由源程序的語法結(jié)構(gòu)所Begin

AdvanceE

驅(qū)動的處理辦法。

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

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

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

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

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

四元式:(OPArg1Arg2Result)

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

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

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

• 上一篇：汽車維修技術(shù)經(jīng)驗(yàn)總結(jié)
• 下一篇：汽車維修技術(shù)經(jīng)驗(yàn)總結(jié)