編譯原理概念名詞解釋

1、編譯過程的六個階段：詞法分析，語法分析，語義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成解釋程序：把某種語言的源程序轉(zhuǎn)換成等價的另一種語言程序一一目標(biāo)語言程序，然后再執(zhí)行目標(biāo)程序。解釋方式是 接受某高級語言的一個語句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí) 行結(jié)果，然后再接受下一句。編譯程序：就是指這樣一種程序，通過它能夠?qū)⒂酶呒壵Z言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價的低級 語言形式的目標(biāo)程序(機(jī)器語言程序或匯編語言程序)。解釋程序和編譯程序的 根本區(qū)別：是否生成目標(biāo)代碼句子的二義性(這里的二義性是指語法結(jié)構(gòu)上的。)：文法GS的一個句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在

2、兩棵不同的語法樹，則稱這個句子是二義性的。文法的二義性：一個文法如果包含二義性的句子，則這個文法是二義文法，否則是無二義文法。LL(1)的含義：(LL(1)文法是無二義的；LL(1)文法不含左遞歸)第1個L:從左到右掃描輸入串第2個L:生成的是最左推導(dǎo)1 :向右看1個輸入符號便可決定選擇哪個產(chǎn)生式某些非LL(1)文法到LL(1)文法的等價變換：1.提取公因子2.消除左遞歸文法符號的屬性：單詞的含義，即與文法符號相關(guān)的一些信息。如，類型、值、存儲地址等。一個屬性文法(attribute grammar)是一個三元組 A=(G, V, F)G :上下文無關(guān)文法。V :屬性的有窮集。每個屬性與文法的

3、一個終結(jié)符或非終結(jié)符相連。屬性與變量一樣，可以進(jìn)行計(jì)算和傳 遞。F :關(guān)于屬性的斷言或謂詞(一組屬性的計(jì)算規(guī)則)的有窮集。斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián)，只引用該 產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。綜合屬性：若產(chǎn)生式左部的單非終結(jié)符A的屬性值由右部各非終結(jié)符的屬性值決定，則A的屬性稱為綜合屬繼承屬性：若產(chǎn)生式右部符號 B的屬性值是根據(jù)左部非終結(jié)符的屬性值或者右部其它符號的屬性值決定的則B的屬性為繼承屬性。(1) 非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性。(2) 終結(jié)符只有綜合屬性，沒有繼承屬性，它們由詞法程序提供。在計(jì)算時：綜合屬性沿屬性語法樹向上傳遞；繼承

4、屬性沿屬性語法樹向下傳遞。語法制導(dǎo)翻譯：是指在語法分析過程中，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動作。語法制導(dǎo)翻譯實(shí)現(xiàn)：對單詞符號串進(jìn)行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷 語法樹并在語法樹的各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計(jì)算。中間代碼(中間語言)1、是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式。2、一般，快速編譯程序直接生成目標(biāo)代碼。3、 為了使編譯程序結(jié)構(gòu)在邏輯上更為簡單明確，常采用中間代碼，這樣可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié) 置于代碼生成階段仔細(xì)處理，并且可以在中間代碼一級進(jìn)行優(yōu)化工作，使得代碼優(yōu)化比較容易實(shí)現(xiàn)。何謂中間代碼：源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)

5、構(gòu)，易于代碼的機(jī)械生成。為何要轉(zhuǎn)換成中間代碼：(1)邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言。(2)便于移植，便于修改，便于進(jìn)行與機(jī)器無關(guān)的優(yōu)化。中間代碼的幾種形式：逆波蘭記號，三元式和樹形表示，四元式符號表的一般形式：一張符號表的的組成包括兩項(xiàng)，即名字欄和信息欄。信息欄包含許多子欄和標(biāo)志位，用來記錄相應(yīng)名字和種種不同屬性，名字欄也稱主欄。主欄的內(nèi)容稱為關(guān)鍵字(key word)。符號表的功能：(1)收集符號屬性(2)上下文語義的合法性檢查的依據(jù) ：檢查標(biāo)識符屬性在上下文中的一 致性和合法性。(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)符號的主要屬性及作用:1.符號名2.符號的類型4.符號的作

6、用域及可視性（整型、實(shí)型、字符串型等）3.符號的存儲類別（公共、私有）（全局、局部）5.符號變量的存儲分配信息（靜態(tài)存儲區(qū)、動態(tài)存儲區(qū)）存儲分配方案策略：靜態(tài)存儲分配；動態(tài)存儲分配：棧式、 堆式。靜態(tài)存儲分配1、基本策略在編譯時就安排好目標(biāo)程序運(yùn)行時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項(xiàng)的單元地址。2、適用的分配對象：子程序的目標(biāo)代碼段；全局?jǐn)?shù)據(jù)目標(biāo)（全局變量）3、靜態(tài)存儲分配的要求：不允許遞歸調(diào)用，不含有可變數(shù)組。FORTRAN程序是段結(jié)構(gòu)，不允許遞歸，數(shù)據(jù)名大小、性質(zhì)固定。是典型的靜態(tài)分配動態(tài)存儲分配1、如果一個程序設(shè)計(jì)語言允許遞歸過程、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用

7、動態(tài)存儲管理技術(shù)。2、兩種動態(tài)存儲分配方式： 棧式，堆式棧式動態(tài)存儲分配分配策略：將整個程序的數(shù)據(jù)空間設(shè)計(jì)為一個棧。【例】在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個過程時，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程 工作結(jié)束時就釋放這部分空間 。過程所需的數(shù)據(jù)空間包括兩部分一部分是生存期在本過程這次活動中的數(shù)據(jù)對象。如局部變量、參數(shù)單元、臨時變量等；另一部分則是用以管理過程活動的記錄信息（連接數(shù)據(jù)）?；顒佑涗洠ˋR）一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū)（塊）叫做一個活動記錄構(gòu)成1、臨時工作單元；2、局部變量；3、機(jī)器狀態(tài)信息；4、存取鏈；5、控制鏈；6、實(shí)參；7、返回地址什么是代碼優(yōu)化所謂優(yōu)化，就是對代碼進(jìn)行等價變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn) 行速度加快或占用存儲空間減少。優(yōu)化原則：等價原則：經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時間較短，占用的存儲空間較小。 合算原則：以盡可能低的代價取得較好的優(yōu)化效果。常見的優(yōu)化技術(shù)（