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

1、編譯原理概念期末總結(jié)復(fù)習(xí) 編譯原理概念期末總結(jié)復(fù)習(xí) 翻譯程序:把一種語言程序轉(zhuǎn)換成另一種語言程序，且在功能上是相同的這樣的程序。編譯程序：把高級語言轉(zhuǎn)換成低級語言，且在功能上是相同的這樣的程序。 解釋程序：邊解釋邊執(zhí)行源程序的程序。區(qū)別：編譯程序有中間代碼，而解釋程序沒有。編譯過程的五個階段： 1、詞法分析任務(wù)：對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個單詞。 2、語法分析任務(wù)：在詞法分析的基礎(chǔ)上，依據(jù)語言規(guī)則，把單詞符號串分解成各類語法 單位。 3、語義分析和中間代碼產(chǎn)生任務(wù)：對語法分析所識別出的各類語法范疇，分析其含義， 并進行初步翻譯。 4、優(yōu)化任務(wù)：對前段產(chǎn)生的中間代碼進行加工變

2、幻，以期在最后階段能產(chǎn)生出更為高效 的目標代碼。 5、目標代碼生成任務(wù)：把中間代碼變幻成特定機器上的低級語言代碼。 編譯程序的七個部分詞法分析器，語法分析器、語義分析與中間代碼產(chǎn)生器、優(yōu)化器、目標代碼生成器、表格管理和出錯處理。 編譯程序生成的五個辦法：機器語言、高級語言、移植、自編譯方式和使用工具自動生成。詞法規(guī)則：指單詞符號的形成規(guī)則。也就是正規(guī)式 語法規(guī)則：規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)。就是語法單位的形成規(guī)則?？兆郑翰话魏畏柕男蛄?。閉包： 中所有的符號組成的集合。 上下文無關(guān)文法是指：所定義的語法范疇是完全獨立于這種范疇可能出現(xiàn)的環(huán)境的文法。上下文無關(guān)文法的四個組成部分：一組

3、終結(jié)符號、一組非終結(jié)符號、一個開始符號和一組產(chǎn)生式。 終結(jié)符號也就是不可再分的基本符號。 非終結(jié)符號是用來代表語法范疇，表示一定符號串的集合。開始符號是語言中我們最感興趣的語法范疇。產(chǎn)生式是定義語法范疇的書寫規(guī)則。 句子：文法中從開始符號推導(dǎo)的終結(jié)符號串。句型：從開始符號推導(dǎo)的符號串。語言：文法中所有句子的集合。 程序語言的單詞符號分為五種：關(guān)鍵字、標識符、常數(shù)、運算符和界符。二元式表示：種類，屬性 正規(guī)式的運算符有三種：或，連接和閉包。優(yōu)先順序是：閉包，連接，或。 dfa怎么識別字：假設(shè)存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記符連接成的字是a，則稱a可為dfa所識別。

4、 dfa怎么識別空字：假設(shè)dfa的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字可為dfa所識別。nfa怎么識別字：假設(shè)存在一條從某一初態(tài)結(jié)點到終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連接成的字等于a，則稱a可為nfa識別。 nfa怎么識別空字：假設(shè)m的某些結(jié)點即是初態(tài)又是終態(tài)結(jié)點，或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的空通路，那么，空字可為m所識別。語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。 語法分析分為兩類：自上而下分析法，自下而上分析法。 自上而下分析法面臨的問題：1.文法的左遞歸問題。2.回溯3.成功可能是暫時的，產(chǎn)生虛假匹配。4.難于知道輸入串中出錯確實切位置。5.效率低，代價高。為什么消

5、除左遞歸？因為含有左遞歸的文法將自上而下分析的過程陷入無限循環(huán)。為什么消除回溯？因為回溯統(tǒng)一做一大堆無效的工作。 自下而上分析法：從輸入串開始，逐步進行歸約，知道歸約到文法的開始符號。短語：符號串推導(dǎo)過程中某非終結(jié)符推導(dǎo)的部分。 直接短語：符號串推導(dǎo)過程中某非終結(jié)符一步推導(dǎo)的部分。句柄：一個句型的最左直接短語。最左歸約是最有推導(dǎo)的逆過程。 中間語言形式：后綴式，三元式，四元式，間接三元式。中間語言的好處：1.便于進行與機器無關(guān)的代碼優(yōu)化工作。2.使編譯程序改變目標機更容易。3.使編譯程序的結(jié)構(gòu)在邏輯上更為簡單，以中間語言為界面，編譯前端和后端的借口更清楚。 擴大閱讀：編譯原理概念整理 翻譯程序

6、：能夠把某種語言轉(zhuǎn)換成另一種語言，而后者與前者在邏輯上是等價的。 編譯過程：詞法、語法、語義分析與中間代碼、優(yōu)化、目標代碼生成 詞法分析：輸入源程序，對構(gòu)成源程序關(guān)鍵字、標識符、常數(shù)、運算符、界符含有左遞歸的文法將使自上而下的分析過程陷入無限循環(huán)。 ll(1)分析條件:當一個文法不含左遞歸，并且滿足每個非終結(jié)符的所有候選首符集兩兩不相交的條件 ee1orme2:backpatch(e1.f,m.quad); e.t=merge(e1.t,e2.t)e.f=e2.f ee1andme2:backpatch(e1.t,m.quad) e.t=e2.t e.f=merge(e1.f,e2.f) 的字

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

8、生成。后端不依賴于源語言而僅僅依賴于中間語言。詞法規(guī)則是指單詞符號的形成規(guī)則。語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(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ī)則。 二義性：如果一個文法存

9、在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。ll(1)的含義:第一個l表示從左到右掃最左規(guī)約=規(guī)范規(guī)約：a描輸入串，第二個l表示最左推導(dǎo)，1最右推導(dǎo)=規(guī)范推導(dǎo)：b 表示分析時每一步只需向前查看一個符號 自上而下分析的問題:文法含有左遞歸時，分析過程會陷入無限循環(huán)回溯浪費分析時間某一非終結(jié)符用某一候選式匹配成功時，可能是暫時的分析不成功時，難以找到出錯位置 自下而上分析的問題:怎樣判斷棧頂?shù)亩陶Z:每棵子樹對應(yīng)一個短語 符號串的可歸約性，以及如何歸約。直接短語:只有兩層的子樹對應(yīng)的短語一個句型的最左直接短語稱為該句型句柄:最左直接短語的句柄。 ete在形式語言中最右推導(dǎo)常被稱為規(guī)范pro

10、ceduree推導(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ǔ)上，為每個文end法符號終結(jié)符或非終結(jié)符配備假設(shè)干相關(guān)的“值稱為屬性 f(e)|iproceduref 語義規(guī)則：文法每個產(chǎn)生式都配備了一ifsym=ithenadvance組屬性的計算規(guī)則。 elseifsym=(then 語法治導(dǎo)翻譯：由源程

11、序的語法結(jié)構(gòu)所begin advancee 驅(qū)動的處理辦法。 ifsym=)thenadvance輸入串-語法樹-依賴圖-語elseerror義規(guī)則計算次序 end靜態(tài)檢查和中間代碼產(chǎn)生的地位：elseerror-語法分析器-靜態(tài)檢查器-中間代碼產(chǎn)生器-優(yōu)化器- 屬性文法:關(guān)于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，在上下文無關(guān)文法的基礎(chǔ)上，為每個符號都配備了假設(shè)干相關(guān)屬性。中間語言形式：后綴式，三地址代碼包括三元式，四元式、間接三元式，dag圖表示 后綴式表示法逆法蘭表示法：把運算量操作數(shù)寫在前面，把算符寫在后面后綴 四元式:(oparg1arg2result)三元式:(oparg1ar

12、g2) 翻譯程序：能夠把某種語言轉(zhuǎn)換成另一種語言，而后者與前者在邏輯上是等價的。 編譯過程：詞法、語法、語義分析與中間代碼、優(yōu)化、目標代碼生成 詞法分析：輸入源程序，對構(gòu)成源程序二義的。 關(guān)鍵字、標識符、常數(shù)、運算符、界符含有左遞歸的文法將使自上而下的分析過程陷入無限循環(huán)。 ll(1)分析條件:當一個文法不含左遞歸，并且滿足每個非終結(jié)符的所有候選首符集兩兩不相交的條件 三元式:(oparg1arg2) ee1orme2:backpatch(e1.f,m.quad); e.t=merge(e1.t,e2.t)e.f=e2.f ee1andme2:backpatch(e1.t,m.quad) e.

13、t=e2.t e.f=merge(e.f,e.f) 的字符串進行掃描和分解，識別出一個個單詞。 語法分析：在詞法分析的基礎(chǔ)上，依據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位。 語義分析與中間代碼產(chǎn)生：對語義分析所識別出的各類語法范疇，分析其含義并進行初步翻譯產(chǎn)生中間代碼；優(yōu)化：優(yōu)化的任務(wù)在于對前段產(chǎn)生的中間代碼進行加工變幻，以期在最后階段能產(chǎn)生出更為高效省時間和空間)的目標代碼。 目標代碼生成：把中間代碼或經(jīng)優(yōu)化處理之后變幻成特定存儲器上的低級語言代碼。 編譯程序結(jié)構(gòu)：表格管理、出錯處理編譯前端：由與源語言有關(guān)但與目標語言無關(guān)的那些部分組成，包括詞法分析、語義分析、語義分析與中間代碼產(chǎn)生。

14、 后端：編譯程序中與目標語言有關(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é)符號，一個開始符號以及一組產(chǎn)生式。 開始符號：是一個特別的非終結(jié)符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子 產(chǎn)生式

15、：是定義語法范疇的一種書寫規(guī)則。 二義性：如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是 12ll(1)的含義:第一個l表示從左到右掃最左規(guī)約=規(guī)范規(guī)約：a描輸入串，第二個l表示最左推導(dǎo)，1最右推導(dǎo)=規(guī)范推導(dǎo)：b 表示分析時每一步只需向前查看一個符號 自上而下分析的問題:文法含有左遞歸時，分析過程會陷入無限循環(huán)回溯浪費分析時間某一非終結(jié)符用某一候選式匹配成功時，可能是暫時的分析不成功時，難以找到出錯位置 自下而上分析的問題:怎樣判斷棧頂?shù)亩陶Z:每棵子樹對應(yīng)一個短語 符號串的可歸約性，以及如何歸約。直接短語:只有兩層的子樹對應(yīng)的短語一個句型的最左直接短語稱為該句型句柄:最左直接短語

16、的句柄。 ete在形式語言中最右推導(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ǔ)上，為每個文end法符號終結(jié)符或非終結(jié)符配備假設(shè)干相關(guān)的“值稱為屬性 f(e)|iproceduref 語義規(guī)則：文法每個產(chǎn)生式都配備了一ifsym=ithenadvance組屬性的計算規(guī)則。 elseifsym=(then 語法治導(dǎo)翻譯：由源程序的語法結(jié)構(gòu)所begin advancee 驅(qū)動的處理辦法。 ifsym=)thenadvance輸入串-語法樹-依賴圖-語elseerror義規(guī)則計算次序 end靜態(tài)檢查和中間代碼產(chǎn)生的地位：elseerror -語法分析器-靜態(tài)