1、編譯程序(bin y chn x)編譯程序(bin y chn x)是一種翻譯程序，它將高級(jí)語(yǔ)言所寫的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或匯編語(yǔ)言的目標(biāo)程序。詞法(cf)分析（Lexical analysis或Scanning）和詞法分析程序（Lexical analyzer或Scanner）詞法分析階段是編譯過(guò)程的第一個(gè)階段。這個(gè)階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，即對(duì)構(gòu)成源程序的字符流進(jìn)行掃描然后根據(jù)構(gòu)詞規(guī)則識(shí)別單詞(也稱單詞符號(hào)或符號(hào))。詞法分析程序?qū)崿F(xiàn)這個(gè)任務(wù)。詞法分析程序可以使用lex等工具自動(dòng)生成。 語(yǔ)法分析（Syntax analysis或Parsing）和語(yǔ)法分析程序（P

2、arser） 語(yǔ)法分析是編譯過(guò)程的一個(gè)邏輯階段。語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語(yǔ)法短語(yǔ)，如“程序”，“語(yǔ)句”，“表達(dá)式”等等.語(yǔ)法分析程序判斷源程序在結(jié)構(gòu)上是否正確.源程序的結(jié)構(gòu)由上下文無(wú)關(guān)文法描述.語(yǔ)義分析（Syntax analysis）及中間代碼生成語(yǔ)義分析是編譯過(guò)程的一個(gè)邏輯階段. 語(yǔ)義分析的任務(wù)是對(duì)結(jié)構(gòu)上正確的源程序進(jìn)行上下文有關(guān)性質(zhì)的審查, 進(jìn)行類型審查.例如一個(gè)C程序片斷:int arr2,b;b = arr * 10; 源程序的結(jié)構(gòu)是正確的. 語(yǔ)義分析將審查類型并報(bào)告錯(cuò)誤:不能在表達(dá)式中使用一個(gè)數(shù)組變量,賦值語(yǔ)句的右端和左端的類型不匹配.語(yǔ)義分析時(shí)，根據(jù)

3、語(yǔ)句的含義，可對(duì)它進(jìn)行翻譯，用另一種語(yǔ)言形式（比源語(yǔ)言更接近于目標(biāo)語(yǔ)言的一種中間代碼或直接用目標(biāo)語(yǔ)言）來(lái)描述這種語(yǔ)義。代碼優(yōu)化代碼優(yōu)化的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得更為高效的，即省時(shí)間和空間的代碼。目標(biāo)代碼生成目標(biāo)代碼的生成的任務(wù)是將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。遍前端（Frontend）和后端（Back end）有時(shí)，常常把編譯的過(guò)程分為前端(front end)和后端(back end)，前端由那樣一些階段組成：這些階段的工作主要依賴于源語(yǔ)言而與目標(biāo)機(jī)無(wú)關(guān)。通常這些階段包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成，某

4、些優(yōu)化工作也可在前端做，也包括與前端每個(gè)階段相關(guān)的出錯(cuò)處理工作和符號(hào)表管理工作。 后端工作指那些依賴于目標(biāo)機(jī)而一般不依賴源語(yǔ)言，只與中間代碼有關(guān)的那些階段，即目標(biāo)代碼生成，以及相關(guān)出錯(cuò)處理和符號(hào)表操作。編譯程序和解釋程序Lex一個(gè)詞法分析程序的自動(dòng)生成(shn chn)工具。它輸入描述構(gòu)詞規(guī)則的一系列正規(guī)式,然后構(gòu)建(u jin)有窮自動(dòng)機(jī)和這個(gè)有窮自動(dòng)機(jī)的一個(gè)驅(qū)動(dòng)程序,進(jìn)而(jn r)生成一個(gè)詞法分析程序.Yacc 一個(gè)語(yǔ)法分析程序的自動(dòng)生成工具。它接受語(yǔ)言的文法,構(gòu)造一個(gè)LALR(1)分析程序.因?yàn)樗捎谜Z(yǔ)法制導(dǎo)翻譯的思想,還可以接受用C語(yǔ)言描述的語(yǔ)義動(dòng)作,從而構(gòu)造一個(gè)編譯程序. Yacc

5、 是 Yet another compiler compiler的縮寫.源語(yǔ)言（Source language）和源程序（Source program）被編譯程序翻譯的程序稱為源程序,書寫該程序的語(yǔ)言稱為源語(yǔ)言.目標(biāo)語(yǔ)言（Object language or Target language）和目標(biāo)程序（Object program or Target program） 編譯程序翻譯源程序而得到的結(jié)果程序稱為目標(biāo)程序, 書寫該程序的語(yǔ)言稱為目標(biāo)語(yǔ)言.中間語(yǔ)言（中間表示）（Intermediate language(representation)） 在進(jìn)行了語(yǔ)法分析和語(yǔ)義分析階段的工作之后，有的編

6、譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語(yǔ)言或中間表示或中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)復(fù)雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言之間，容易將它翻譯成目標(biāo)代碼。另外，還可以在中間代碼一級(jí)進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化。常見的中間代碼形式有：逆波蘭式、三元式、四元式、樹形表示和三地址代碼。文法（Grammars） 文法是用于描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。文法G定義為四元組(VN，V T，P，S)。其中VN為非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；V T為終結(jié)符號(hào)集；P為產(chǎn)生式(也稱規(guī)則)的集合；產(chǎn)生式(規(guī)則)是形如或 a :=b 的(a , b)有序?qū)?其中(

7、VNV T)*且至少含有一個(gè)非終結(jié)符，而(VNV T)*。VN，V T和P是非空有窮集。S稱作識(shí)別符號(hào)或開始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。 一個(gè)文法的例子: G=( VN =A，R, P =0,1 ，P =A0R，A01,RA1, S =A) 文法(wnf)分類（A hierarchy of Grammars） 著名(zhmng)語(yǔ)言學(xué)家Noam Chomsky定義了四類文法和四種(s zhn)形式語(yǔ)言類，文法的四種類型分別是0型、1型、2型和3型。幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制，分別是： 0型文法(短語(yǔ)結(jié)構(gòu)文法)(phrase structure gram

8、mars)： 設(shè)G=(VN，V T，P，S)，如果它的每個(gè)產(chǎn)生式是這樣一種結(jié)構(gòu)(VNV T)*且至少含有一個(gè)非終結(jié)符，而(VNV T)*，則G是一個(gè)0型文法。 1型文法（上下文有關(guān)文法）(context-sensitive grammars)： 設(shè)G=(VN，V T，P，S)為一文法|，若P中的每一個(gè)產(chǎn)生式均滿足|，僅僅S除外，則文法G是1型或上下文有關(guān)的。 2型文法（上下文無(wú)關(guān)文法）(context-free grammars)： 設(shè)G=(VN，V T，P，S)，若P中的每一個(gè)產(chǎn)生式滿足：是一非終結(jié)符，(VNV T)*則此文法稱為2型的或上下文無(wú)關(guān)的。 3型文法（正規(guī)文法）(regular

9、grammars)： 設(shè)G=(VN，V T，P，S)，若P中的每一個(gè)產(chǎn)生式的形式都是AaB或Aa，其中A和B都是非終結(jié)符，a是終結(jié)符，則G是3型文法或正規(guī)文法。 0型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言。 1型文法產(chǎn)生的語(yǔ)言稱為1型語(yǔ)言，也稱作上下文有關(guān)語(yǔ)言。 2型文法產(chǎn)生的語(yǔ)言稱為2型語(yǔ)言，也稱作上下文無(wú)關(guān)語(yǔ)言。 3型文法產(chǎn)生的語(yǔ)言稱為3型語(yǔ)言，也稱作正規(guī)語(yǔ)言。 句型（Sententialform），句子（Sentence）和語(yǔ)言（Language）設(shè)GS是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即有Sx，則稱x是文法GS的句型。若x僅由終結(jié)符號(hào)組成，即Sx，xV T*，則稱x為GS的句子。 文法

10、G所產(chǎn)生的語(yǔ)言定義為集合xSx，其中S為文法識(shí)別符號(hào)，且xV T*。可用L(G) 或L(GS)表示該集合。 推導(dǎo)（Derive）和語(yǔ)法樹（Parse tree） 推導(dǎo)的概念：分別(fnbi)定義V*中的符號(hào)(fho)之間的關(guān)系直接(zhji)推導(dǎo)、長(zhǎng)度為n（n1）的推導(dǎo)和長(zhǎng)度為n（n0）的推導(dǎo)： （1）如是文法G=(VN，V T，P，S)的規(guī)則（或說(shuō)是P中的一個(gè)產(chǎn)生式），和是V*中的任意符號(hào)，若有符號(hào)串v，w滿足： v，w則說(shuō)v（應(yīng)用規(guī)則）直接產(chǎn)生w，或說(shuō)，w是v的直接推導(dǎo)，或說(shuō)，w直接歸約到v，記做vw。 （2）如果存在直接推導(dǎo)的序列： vw0 w1 w2 wnw，（n0） 則稱v推導(dǎo)出（產(chǎn)

11、生）w（推導(dǎo)長(zhǎng)度為n），或稱w歸約到v。記作vw。 （3）若有vw，或vw，則記作。 語(yǔ)法樹（推導(dǎo)樹）的概念：給定文法G=(VN，V T，P，S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹（推導(dǎo)樹）。這棵樹滿足下列4個(gè)條件： 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)。 根的標(biāo)記是S。 若一個(gè)結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則A肯定在VN中。 如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1，n2， ，nk，其標(biāo)記分別為A1，A2，Ak，那么AA1A2，Ak一定是P中的一個(gè)產(chǎn)生式。 二義文法（Ambiguous grammer）如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則說(shuō)這

12、個(gè)文法是二義的。或者說(shuō)，若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左(最右)推導(dǎo)，則這個(gè)文法是二義的。 短語(yǔ)，句柄 (phrase , sentence handle)令G是一文法，S是文法的開始符號(hào)，是文法G的一個(gè)句型。如果有：且則稱是句型相對(duì)與非終結(jié)符 A的短語(yǔ)。特別，如有則稱是句型相對(duì)于規(guī)則A的直接短語(yǔ) (也稱簡(jiǎn)單短語(yǔ))。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。 正規(guī)式（regular expression）和它所表示的正規(guī)集（regular set）設(shè)字母表為,輔助字母表 =,，.，*,(,)。1. 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和； 2.任何a，a是上的一個(gè)正規(guī)式，它所表

13、示的正規(guī)集為a； 3.假定1和2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(1)和L(2)，那么，(1)，12，12和2*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(1)，L(1)L(2)，L(1)L(2)和(L(1) *。4.僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。 確定(qudng)的有窮狀態(tài)自動(dòng)機(jī)DFA(deterministic finite automaton)和不確定(qudng)的有窮狀態(tài)自動(dòng)機(jī)NFA(nondeterministic finite automaton)我們(w men)這里是把DFA和NFA作為正規(guī)集的識(shí)別工

14、具而介紹的。DFA定義如下：一個(gè)確定的有窮自動(dòng)機(jī)(DFA)M是一個(gè)五元組：M=(K, ，f，S，Z)其中 1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符,所以也稱為輸入符號(hào)字母表;3.f是轉(zhuǎn)換函數(shù)，是在KK上的映像，即，如f(ki,a)= kj( kiK, kjK)就意味著，當(dāng)前狀態(tài)為ki，輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài);4.SK是唯一的一個(gè)初態(tài)；5.ZK，是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。NFA定義如下;一個(gè)不確定的有窮自動(dòng)機(jī)(NFA)M是一個(gè)五元組，M=(K, ，f，S，Z)其中 1.K是

15、一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符； 3. f是一個(gè)從K*到K的子集的映像.4. SK，是一個(gè)非空初態(tài)集;5. ZK，是一個(gè)終態(tài)集。 DFA和NFA的等價(jià)定理：對(duì)于每個(gè)NFA M，存在一個(gè)DFA M，使得L（M）L（M），即M和M是等價(jià)的。 最小狀態(tài)DFA(reduced DFA or minimum DFA) 我們說(shuō)一個(gè)確定的有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是說(shuō)，它沒(méi)有多余狀態(tài)并且它的狀態(tài)中沒(méi)有兩個(gè)是互相等價(jià)的，這種DFA也叫做最小狀態(tài)DFA。一個(gè)DFA可以通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)與之等價(jià)的最小狀態(tài)DFA。 24FIRST集設(shè)

16、G=(VN，V T，P，S)是上下文無(wú)關(guān)(wgun)文法 FIRST()=a，aV T，, V *若，則規(guī)定(gudng)FIRST()。 25FOLLOW集設(shè)G=(VN，V T，P，S)是上下文無(wú)關(guān)(wgun)文法，AVN，是開始符號(hào)FOLLOW(A)=a且aV T，aFIRST()，V T*，V + 若，且，則#FOLLOW(A)。也可定義為：FOLLOW(A)=a|Aa,aV T 若有A，則規(guī)定#FOLLOW(A) 這里我們用作為輸入串的結(jié)束符，或稱為句子括號(hào)，如：輸入串。 26SELECT集給定上下文無(wú)關(guān)文法的產(chǎn)生式A AVN，V *，若，則SELECT(A)= FIRST() 如果，

17、則SELECT(A)=FIRST()FOLLOW(A)。 27左遞歸文法（Left recursive grammar） 一個(gè)文法含有下列形式的產(chǎn)生式時(shí)。 a)AA AVN，V * b)ABB A,BVN，、V * 在a)中也可稱為含有左遞歸的規(guī)則或稱直接左遞歸，在b)中為A稱文法中含有左遞歸或間接左遞歸，文法中只要含有a)或含有b)或二者皆有均認(rèn)為文法是左遞歸的。 28LL（1）文法 滿足如下條件的上下文無(wú)關(guān)文法稱為L(zhǎng)L（1）文法：對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式， A，A，滿足 SELECT（A）SELECT（A）其中、不同時(shí)能。 LL（1）文法的含義是：第一個(gè)L表明自頂向下分析是從左向右

18、掃描輸入串，第二個(gè)L表明分析過(guò)程中將用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)即選擇哪個(gè)產(chǎn)生式（規(guī)則）進(jìn)行推導(dǎo)，類似也可以有LL（K）文法，也就是需向前查看K個(gè)符號(hào)才可確定選用哪個(gè)產(chǎn)生式。通常采用K1，個(gè)別情況采用K2。 29遞歸子程序法（Recursive-descent） 遞歸子程序法是LL（1）文法的分析程序的一種實(shí)現(xiàn)方法。它對(duì)應(yīng)文法中每個(gè)非終結(jié)符編寫(binxi)一個(gè)遞歸過(guò)程，這種分析程序由這一系列遞歸過(guò)程的相互調(diào)用來(lái)完成語(yǔ)法分析工作。 30移進(jìn)歸約分析(fnx)（shiftreduce analysis） 自底向上分析方法，也稱移進(jìn)歸約分析法，它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左

19、向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號(hào)串形成(xngchng)某個(gè)句型的句柄時(shí)，（該句柄對(duì)應(yīng)某產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為一步歸約。重復(fù)這一過(guò)程直到歸約棧中只剩文法的開始符號(hào)時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。 31算符文法，算符優(yōu)先文法(Operator Grammar，Operator Precedence Grammar) 設(shè)有文法G，若G中沒(méi)有形如UVW的規(guī)則，其中V和W為非終結(jié)符，則稱G是一個(gè)算符文法(Operator Grammar)，即OG文法。設(shè)有一不含產(chǎn)生式的算法文法G，如果對(duì)任意兩個(gè)

20、終結(jié)符對(duì)a，b之間至多只有、和三種關(guān)系的一種成立，則稱G是一個(gè)算符優(yōu)先文法(Operator Precedence Grammar)，即OPG文法。 32最左素短語(yǔ)（Most left prime phrase） 設(shè)有文法GS，其句型的素短語(yǔ)是一個(gè)短語(yǔ) ，它至少包含一個(gè)終結(jié)符，并除自身外不包含其它素短語(yǔ)，句型的最左邊的素短語(yǔ)稱最左素短語(yǔ)。 33LR分析(fnx) 是一種(y zhn)自底向上的語(yǔ)法分析技術(shù),通常(tngchng)稱為L(zhǎng)R(K).L是說(shuō)從左至右掃描輸入串,R是說(shuō)分析過(guò)程所形成的推導(dǎo)是最右推導(dǎo),K是指在做分析決策時(shí)向前察看K個(gè)輸入符號(hào).LR分析可用于一大類上下文無(wú)關(guān)文法,是一種最常

21、用的無(wú)回朔的移進(jìn)歸約分析, 一個(gè)LR分析器由分析棧、分析表和總控程序3個(gè)部分組成。LR分析器總控程序根據(jù)LR分析表，執(zhí)行4種可能的動(dòng)作：移進(jìn)、規(guī)約、接受（acc）和報(bào)錯(cuò)。34屬性文法（Attribute grammar） 形式上講，一個(gè)屬性文法是一個(gè)三元組，（，），一個(gè)上下文無(wú)關(guān)文法；一個(gè)屬性的有窮集和關(guān)于屬性的斷言或謂詞的有窮集。每個(gè)屬性與文法的某個(gè)非終結(jié)符或終結(jié)符相聯(lián)。每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。如果對(duì)中的某一輸入串而言（句子），中的所有斷言對(duì)該輸入串的語(yǔ)法樹結(jié)點(diǎn)的屬性全為真，則該串也是語(yǔ)言中的句子。編譯程序的靜態(tài)語(yǔ)義審查工作就是驗(yàn)證關(guān)于所編譯的程序的斷言是否全部為真。屬性分為兩類：綜合

22、屬性和繼承屬性。35語(yǔ)法制導(dǎo)翻譯（Syntax-directed translation） 在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（或語(yǔ)義規(guī)則描述的語(yǔ)義動(dòng)作）進(jìn)行翻譯的辦法稱作語(yǔ)法制導(dǎo)翻譯。 36數(shù)組內(nèi)情向量（array dope vector） 一般編譯程序?qū)?shù)組說(shuō)明的處理是把數(shù)組的有關(guān)信息匯集在一個(gè)叫做“內(nèi)情向量”或“信息向量”的表格中，以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息。每個(gè)數(shù)組有一個(gè)內(nèi)情向量。其中的信息包括，數(shù)組的類型，維數(shù)，各維的上、下界，以及數(shù)組的首地址。編譯程序處理數(shù)組說(shuō)明的主要工作是把內(nèi)情向量登錄在符號(hào)表中，這些屬性信息是確定存儲(chǔ)分配時(shí)數(shù)組

23、所占空間的大小和數(shù)組元素位置的依據(jù)。 37符號(hào)表（symbol table）在編譯程序中符號(hào)表用來(lái)存放源程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語(yǔ)義特征屬性,為進(jìn)行上下文語(yǔ)義審查和進(jìn)一步的翻譯使用。 編譯程序處理標(biāo)識(shí)符時(shí)主要涉及兩部分內(nèi)容，其一是標(biāo)識(shí)符本身，其二是標(biāo)識(shí)符相關(guān)的信息。符號(hào)表上有三種操作：填入、查找和更新。符號(hào)表的查找方法有順序查找、二分查找和散列（雜湊）查找法。38運(yùn)行(ynxng)時(shí)的環(huán)境及存儲(chǔ)空間所謂運(yùn)行時(shí)的環(huán)境(hunjng)是指目標(biāo)計(jì)算機(jī)的寄存器和存儲(chǔ)器的結(jié)構(gòu)，以及用來(lái)管理存儲(chǔ)器并保存執(zhí)行過(guò)程所需要的信息。存儲(chǔ)空間包括用戶定義的各種類型的數(shù)據(jù)對(duì)象所需要

24、的存儲(chǔ)空間、調(diào)用過(guò)程所需要的連接單元和組織輸入/輸出所需要的緩沖區(qū)及保留中間接過(guò)和傳遞參數(shù)所需要的臨時(shí)(ln sh)單元。存儲(chǔ)空間通常被劃分為：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)。39靜態(tài)存儲(chǔ)分配（Static storage allocation）如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置，稱這種分配策略為靜態(tài)存儲(chǔ)分配。40動(dòng)態(tài)存儲(chǔ)分配（Dynamic storage allocation）如果一個(gè)程序設(shè)計(jì)語(yǔ)言允許遞歸過(guò)程、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。因?yàn)閷?duì)于這種程序在

25、編譯時(shí)無(wú)法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。有兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式（stack）和堆式（heap）。41四元式(quadruples) 四元式是一種中間代碼的形式,是一個(gè)有四個(gè)域的紀(jì)錄結(jié)構(gòu): 四個(gè)域分別稱為 op,arg1,arg2 和 result 即操作符,運(yùn)算對(duì)象1, 運(yùn)算對(duì)象2 和運(yùn)算結(jié)果.一個(gè)例子:( + ,a, b, c) 42Display表 為能存取非局部變量而紀(jì)錄外包過(guò)程的活動(dòng)記錄地址的數(shù)組。即每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display。這里所提到的“嵌套層次”，是指過(guò)程定義的層數(shù)，始

26、終假定主程序的層數(shù)為0，因此主程序稱為0層過(guò)程。如某過(guò)程p是在層次為i的過(guò)程q內(nèi)定義的，并且q是包圍p的直接外層，那么p的過(guò)程層數(shù)為i+1。display是一個(gè)指針數(shù)組d，也可看做是一個(gè)小棧，自頂向下每個(gè)單元依次存放著現(xiàn)行層，直接外層，直至最外層（0層，主程序?qū)樱┑让恳粚舆^(guò)程的最新活動(dòng)記錄的地址。 43活前綴(viable prefixes) 和拓廣文法若是文法(wnf)G中的一個(gè)規(guī)范(gufn)推導(dǎo)。如果(rgu)符號(hào)串是的前綴，則稱是G的一個(gè)活前綴。也就是說(shuō)是規(guī)范句型的前綴，但它的右端不超過(guò)該句型句柄的末端。這里S為對(duì)原文法G加了產(chǎn)生式S，S為原文法G的開始符號(hào)，S為拓廣后文法G的開始符號(hào)

27、。 44LR(0)項(xiàng)目和LR(0)項(xiàng)目集規(guī)范族(LR(0)items and canonical collection of sets of LR(0) items)文法G的產(chǎn)生式的右部適當(dāng)位置添加有一個(gè)圓點(diǎn)則稱為一個(gè)LR(0)項(xiàng)目。根據(jù)小圓點(diǎn)的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符，將一個(gè)文法的全部LR(0)項(xiàng)目分為四類：歸約項(xiàng)目、移進(jìn)項(xiàng)目、待約項(xiàng)目和接受項(xiàng)目。根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把項(xiàng)目分為以下幾種：移進(jìn)項(xiàng)目，形如 A a，其中，(VNV T)*待約項(xiàng)目，形如 A B，其中，(VNV T)*歸約項(xiàng)目，形如 A ，其中(VNV T)*接受項(xiàng)目，形如 S S 構(gòu)成識(shí)別一個(gè)文法

28、活前綴的DFA項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。45同心集所謂同心的LR(1)項(xiàng)目集是指在兩個(gè)LR(1)項(xiàng)目集中，除搜索符不同之外，核心部分是相同的。46代碼優(yōu)化（Code Optimization）所謂代碼優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲(chǔ)空間少，或兩者都有。 代碼優(yōu)化通常分為兩大類：與機(jī)器相關(guān)的優(yōu)化和與機(jī)器無(wú)關(guān)的優(yōu)化。與機(jī)器無(wú)關(guān)的優(yōu)化，常見的優(yōu)化技術(shù)：刪除公共子表達(dá)式（刪除多余運(yùn)算）、代碼外提、強(qiáng)度削弱、變換循環(huán)控制條件（刪除歸納變量）、合并已知量、復(fù)寫傳播和刪除無(wú)用賦值。依據(jù)優(yōu)化所涉及的范圍

29、分為：局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。47基本塊（Basic block）和DAG 所謂基本塊，是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。執(zhí)行時(shí)只能從其入口語(yǔ)句進(jìn)入，從其出口語(yǔ)句退出。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱。基本塊的DAG表示可用于代碼優(yōu)化。 在一個(gè)基本塊內(nèi)，可以執(zhí)行三種優(yōu)化：刪除多余運(yùn)算、合并已知量、刪除無(wú)用賦值。48控制(kngzh)流程圖（流圖）（Control flow graph）一個(gè)控制流程圖就是(jish)具有唯一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開始到控制流程圖中任何結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。 我們(w men)

30、可以把一個(gè)控制流程圖表示成一個(gè)三元組（，），其中，代表圖中所有結(jié)點(diǎn)集，代表圖中所有有向邊集，代表首結(jié)點(diǎn)。控制流程圖簡(jiǎn)稱為流圖。 49循環(huán)（Loop） 在程序流圖中，稱具有下列性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)： 它們是強(qiáng)連通的。也即，其中任意兩個(gè)結(jié)點(diǎn)之間，必有一條通路，而且該通路上各結(jié) 點(diǎn)都屬于該結(jié)點(diǎn)序列。如果序列只包含一個(gè)結(jié)點(diǎn)，則必有一有向邊從該結(jié)點(diǎn)引到其自身。 它們中間有且只有一個(gè)是入口結(jié)點(diǎn)。因此，我們定義的循環(huán)就是程序流圖中具有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖，從循環(huán)外要進(jìn)入循 環(huán)，必須首先經(jīng)過(guò)循環(huán)的入口結(jié)點(diǎn)。所謂入口結(jié)點(diǎn)，是指序列中具有下述性質(zhì)的結(jié)點(diǎn)：從序列外某結(jié)點(diǎn)，有一有向邊引到它，或者它就是程序流圖

31、的首結(jié)點(diǎn)。 50必經(jīng)結(jié)點(diǎn)（dominators）和必經(jīng)結(jié)點(diǎn)集（dominators set）在程序流圖中，對(duì)任意兩個(gè)結(jié)點(diǎn)m和n，如果從流圖的首結(jié)點(diǎn)出發(fā)，到達(dá)n的任一通路都要經(jīng)過(guò)m，則稱m是n的必經(jīng)結(jié)點(diǎn)，記為m DOM n。流圖中結(jié)點(diǎn)的所有必經(jīng)結(jié)點(diǎn)的集合，稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，記為D（n）。51回邊（back edge）假設(shè)ab是流圖中的一條有向邊，如果b DOM a，則稱ab是流圖中的一條回邊。52T型圖（T diagram） 一個(gè)編譯程序涉及到三個(gè)方面的語(yǔ)言，即源語(yǔ)言、目標(biāo)語(yǔ)言和編譯程序的書寫語(yǔ)言。為了描述方便通常用T型圖來(lái)表示一個(gè)編譯程序所涉及到的這三個(gè)方面的語(yǔ)言。T型圖的左上角表示源語(yǔ)言，右上角表示目標(biāo)語(yǔ)言，底部表示書寫語(yǔ)言(實(shí)現(xiàn)語(yǔ)言)。 53自展（bootstrap）自展的思想是先用目標(biāo)機(jī)的匯編語(yǔ)言(yyn)或機(jī)器語(yǔ)言書寫源語(yǔ)言的一個(gè)子集的編譯程序，然后再用這個(gè)子集作為書寫語(yǔ)言，實(shí)現(xiàn)源語(yǔ)言的編譯程序，如果把這個(gè)過(guò)程根據(jù)情況分成若干步，像滾雪球一樣直到生成預(yù)計(jì)源語(yǔ)言的編譯程序?yàn)橹梗覀儼堰@樣的實(shí)現(xiàn)方式稱為自展技術(shù)。 54Token 具有集合意義的字符(z f)序列.是詞法分析(fnx)的輸出. Token 一般分為標(biāo)識(shí)符,常數(shù)(常量),關(guān)鍵字,運(yùn)算符及界符.55交叉編譯（Cross compile） 所謂交叉編譯是指把一個(gè)源語(yǔ)言在一個(gè)機(jī)器(稱為宿主機(jī))上編譯產(chǎn)生