編譯詞匯解釋

1、. 編譯程序(Compiler)編譯程序是一種翻譯程序，它將不能被計(jì)算機(jī)識(shí)別的某種高級(jí)語(yǔ)言翻譯成計(jì)算機(jī)能夠識(shí)別的低級(jí)語(yǔ)言。 一般編譯程序分成五個(gè)邏輯模塊：詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成、中間代碼優(yōu)化、目標(biāo) 代碼生成。.解釋程序(Intepretter)解釋程序是一種翻譯程序，它將不能被計(jì)算機(jī)識(shí)別的某種高級(jí)語(yǔ)言翻譯成計(jì)算機(jī)能夠識(shí)別的低級(jí)語(yǔ)言。它是逐個(gè)語(yǔ)句翻譯的，邊翻譯邊執(zhí)行，不生成目標(biāo)代碼。. 源語(yǔ)言(Source language 和源程序(Source program)被編譯程序翻譯的程序稱為源程序，書(shū)寫(xiě)該程序的語(yǔ)言稱為源語(yǔ)言。.目標(biāo)語(yǔ)言( Object language or

2、Target language) 和目標(biāo)程序( Object program or Target program )編譯程序翻譯源程序而得到的結(jié)果程序稱為目標(biāo)程序，書(shū)寫(xiě)該程序的語(yǔ)言稱為目標(biāo)語(yǔ)言. 詞法分析(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 a

3、nalysis或Parsing)和語(yǔ)法分析程序(Parser)語(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é)本是正確的.語(yǔ)義分析將審查類型并報(bào)告錯(cuò)誤：不能在表達(dá)式中使用一個(gè)數(shù)組變量，賦值語(yǔ)句的右端和左端的類

4、型不 匹配.中間代碼生成 (Intermediate Code Generation )在進(jìn)行了語(yǔ)法分析和語(yǔ)義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種 內(nèi)部表示形式叫做中間語(yǔ)言或中間表示或中間代碼。.中間代碼優(yōu)化(Intermediate Code Optimization )所謂代碼優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相 同，而運(yùn)行速度加大或占用存儲(chǔ)空間少，或兩者都有。.目標(biāo)代碼生成(Object Code Generation )將優(yōu)化后的中間代碼轉(zhuǎn)化成等價(jià)的目標(biāo)代碼。目標(biāo)代碼主要有機(jī)器語(yǔ)言和匯編語(yǔ)言。. Lex一個(gè)詞法分

5、析程序的自動(dòng)生成工具。它輸入描述構(gòu)詞規(guī)則的一系列正規(guī)式，然后構(gòu)建有窮自動(dòng)機(jī)和這個(gè)有窮自動(dòng)機(jī)的一個(gè)驅(qū)動(dòng)程序，進(jìn)而生成一個(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是Yet another compiler compiler的縮寫(xiě).文法(Grammars )文法是用于描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。文法G定義為四元組(耳,6 ,產(chǎn)，S)。其中心 為非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；/為終結(jié)符號(hào)集； P為產(chǎn)生式(也稱規(guī)則)的集合；產(chǎn)生式(規(guī)則

6、)是 形如Q T 或a :=b的(a , b)有序?qū)ζ渲幸?(% U % )|且至少含有一個(gè)非終結(jié)符，而 f丘(/ U 6)1。/，41和F是非空有窮集。S稱作識(shí)別符號(hào)或開(kāi)始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條 規(guī)則中作為左部出現(xiàn)。一個(gè)文法的例子：G=(/=A, R, % =0,1 , F=A?0R , A?01,R?A1, = =A).文法分類(A hierarchy of Grammars )著名語(yǔ)言學(xué)家Noam Chomsky定義了四類文法和四種形式語(yǔ)言類，文法的四種類型分別是0型、1型、2型和3型。幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。. 0 型文法(短語(yǔ)結(jié)構(gòu)文法)(phrase

7、structure grammars)設(shè)g=(%, p, S)，如果它的每個(gè)產(chǎn)生式aTS是這樣一種結(jié)構(gòu)aE ()1 且至少含有一個(gè)非終結(jié)符，而e(%u/)l則g是一個(gè)0型文法。0型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言。.1 型文法(上下文有關(guān)文法)(context-sensitive grammars)設(shè)g=(/ M , F, S)為一文法，若?中的每一個(gè)產(chǎn)生式aTE均滿足。，僅僅ST 除外，則文法G是1型或上下文有關(guān)的。1型文法產(chǎn)生的語(yǔ)言稱為1型語(yǔ)言，也稱作上下文有關(guān)語(yǔ)言。.2型文法(上下文無(wú)關(guān)文法)(context-free grammars)設(shè)g=(%, 4, P, S),若p中的每一個(gè)產(chǎn)生式儀滿

8、足：口是一非終結(jié)符，Jw(7u丁)1則此文法稱為2型的或上下文無(wú)關(guān)的。2型文法產(chǎn)生的語(yǔ)言稱為 2型語(yǔ)言，也稱作上下文無(wú)關(guān)語(yǔ)言。.3 型文法(正規(guī)文法) (regular grammars)：設(shè)G=( % , 4 , P , ),若P中的每一個(gè)產(chǎn)生式的形式都是 aB或a ,其中A和B都是非終結(jié)符，a是終結(jié)符，則 G是3型文法或正規(guī)文法。3型文法產(chǎn)生的語(yǔ)言稱為 3型語(yǔ)言，也稱作正規(guī)語(yǔ)言。.句型(Sententialform)設(shè)G S是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即有S= x,則稱x是文法G S的句型。.句子 S Sentences)*設(shè)G S是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出

9、來(lái)的，即有S= x,若x僅由終結(jié)符號(hào)組成，* *即S=x, x G/了，則稱x為G S的句子。.語(yǔ)言(Language)* *文法G所產(chǎn)生的語(yǔ)言定義為集合 x | S=x,其中S為文法識(shí)別符號(hào)，且 xG廠了 ?？捎肔(G)或L(GS)表示該集合。.推導(dǎo)(Derive) +推導(dǎo)的概念：分別定義V*中的符號(hào)之間的關(guān)系直接推導(dǎo)=、長(zhǎng)度為n (n 1)的推導(dǎo)=和長(zhǎng)度為n(n 0)的推導(dǎo)二:(1)如2T0是文法g=(4, 4, F, S)的規(guī)則(或說(shuō)是p中的一個(gè)產(chǎn)生式)，了和是v*中的任意符號(hào),若有符號(hào)串 v , w滿足：v=7 ct A, w= y B 8則說(shuō)v (應(yīng)用規(guī)則)直接產(chǎn)生w,或說(shuō)，w是v的

10、直接推導(dǎo)，或說(shuō)，w直接歸約到v,記做vn w。(2)如果存在直接推導(dǎo)的序列：v wc)n wi 二 w2 二 wn= w, ( n0)則稱v推導(dǎo)出(產(chǎn)生)w (推導(dǎo)長(zhǎng)度為n),或稱w歸約到v。記作v二Wo+ *(3)若有v = w,或v=w,則記作.。. 語(yǔ)法樹(shù)(Parse tree)語(yǔ)法樹(shù)(推導(dǎo)樹(shù))的概念：給定文法G=(%,丁，P , ),對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))。這棵樹(shù)滿足下列4個(gè)條件：每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是 V的一個(gè)符號(hào)。根的標(biāo)記是So若一個(gè)結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記 A ,則A肯定在 心中。如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n

11、1，像，nk,其標(biāo)記分別為 A1, A2, , Ak那么A-A1A2,，Ak一定是P中的一個(gè)產(chǎn)生式。.二義文法( Ambiguous grammer)如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的?；蛘哒f(shuō)，若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左 (最右)推導(dǎo)，則這個(gè)文法是二義的。.短語(yǔ)(phrase ) +令g是一文法，s是文法的開(kāi)始符號(hào)，a/8是文法g的一個(gè)句型。如果有：Sn山15且工臺(tái) 則稱0是句型汽8相對(duì)與非終結(jié)符a的短語(yǔ)。特別，如有二0則稱0是句型 陽(yáng)5 相對(duì)于規(guī)則的直接短語(yǔ)(也稱簡(jiǎn)單短語(yǔ))。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。.句柄(sentence h

12、andle) +令G是一文法，S是文法的開(kāi)始符號(hào)， 邸6是文法g的一個(gè)句型。如果有：Sn出18且心則 稱是句型相對(duì)與非終結(jié)符a的短語(yǔ)。特別，如有 心0則稱B是句型 邸6 相對(duì)于規(guī)則 人 的直接短語(yǔ)(也稱簡(jiǎn)單短語(yǔ))。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。.正規(guī)式 (regular expression) 和它所表示的正規(guī)集 (regular set)設(shè)字母表為，輔助字母表E = 4, E, I, ., *,(,)。. E和中都是上的正規(guī)式，它們所表示的正規(guī)集分別為 E和9 ；.任彳aG , a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為a；.假定4和%都是上的正規(guī)式,它們所表示的正規(guī)集分別為!_(1)

13、和L(與)，那么，(青),4 |電, 4片和外也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(4), lM)UL(1 ), L(4)L(B )和化(4 )1 o.僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是Y上的正規(guī)集。.確定的有窮狀態(tài)自動(dòng)機(jī)DFA(deterministic finite automaton)我們這里是把DFA和NFA作為正規(guī)集的識(shí)別工具而介紹的。DFA定義如下：一個(gè)確定的有窮自動(dòng)機(jī)(DFA)M是一個(gè)五元組：M=(K, , f, S, Z)其中. K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；. E是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符，

14、所以也稱為輸入符號(hào)字母表：.f是轉(zhuǎn)換函數(shù)，是在 KX二K 上的映像，即，如f也,a)=/ 內(nèi) K,*/ GK)就意味著，當(dāng)前狀態(tài)為上輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài) 勺 我們把上J稱作尢的一個(gè)后繼狀態(tài)；. SC K是唯一的一個(gè)初態(tài)；. ZQK,是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。29,不確定的有窮狀態(tài)自動(dòng)機(jī)NFA(nondeterministic finite automaton )NFA定義如下；一個(gè)不確定的有窮自動(dòng)機(jī)(NFA)M是一個(gè)五元組，M=(K, , f, S, Z)其中. K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；. 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；. f是

15、一個(gè)從KX E,到K的子集的映像. SQK,是一個(gè)非空初態(tài)集；. Z U K ,是一個(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 oToken具有集合意義的字符序列。是詞法分析的輸出.Token 一般分為標(biāo)識(shí)符，常數(shù)(常

16、量),關(guān)鍵字，運(yùn)算符及界符。FIRST 集*設(shè) G=( %, P , )是上下文無(wú)關(guān)文法FIRST( a )= a | =, a,也,0 W* 若療= ,則規(guī)定 e FIRST( 口)。FOLLOW 集設(shè)G=4 , VT , P , S )是上下文無(wú)關(guān)文法，ACN，S是開(kāi)始符號(hào)*FOLLOW(A)= a |且 aG % , a FIRST( ), .展左口* 若Sn, 且 ； ,則 #G FOLLOW(A) o*也可定義為：FOLLOW(A)=a| = - Aa- ,a fj t若有a ,則規(guī)定#e follow(A)這里我們用，#?作為輸入串的結(jié)束符，或稱為句子括號(hào)，如：#輸入串#。SELE

17、CT 集給定上下文無(wú)關(guān)文法的產(chǎn)生式 2 口 AW% ,口,若氏* ,則SELECT件 口 )= FIRST(也)*如果 g ， 則 SELECT件 Q )=FIRST( Q ) U FOLLOW(A)。左遞歸文法( Left recursive grammar)一個(gè)文法含有下列形式的產(chǎn)生式時(shí)。a)A B AC / G 廠b)2B 二EK A cA,B e %, 口、 e+在a)中也可稱為含有左遞歸的規(guī)則或稱直接左遞歸，在 b)中為 Q A稱文法中含有左遞歸或間接 左遞歸，文法中只要含有 a)或含有b)或二者皆有均認(rèn)為文法是左遞歸的。LL (1)文法滿足如下條件的上下文無(wú)關(guān)文法稱為L(zhǎng)L (1)文

18、法：對(duì)每個(gè)非終結(jié)符 A的兩個(gè)不同產(chǎn)生式，2 Q , 2 1 ,滿足SELECT (2口)A SELECT (2 0)=力其中。、/不同時(shí)能=。LL (1)文法的含義是：第一個(gè) L表明自頂向下分析是從左向右掃描輸入串，第二個(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)生式。通常采用 K=1,個(gè)別情況采用K=2.遞歸下降法(Recursive-descent遞歸下降法是LL (1)文法的分析程序的一種實(shí)現(xiàn)方法。它對(duì)應(yīng)文法中每個(gè)非終結(jié)符編寫(xiě)一個(gè)遞歸過(guò) 程，這種分

19、析程序由這一系列遞歸過(guò)程的相互調(diào)用來(lái)完成語(yǔ)法分析工作。.移進(jìn)一歸約分析(shift reduce analysis)自底向上分析方法，也稱移進(jìn)-歸約分析法，它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將 輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄時(shí)，(該句柄對(duì) 應(yīng)某產(chǎn)生式的右部)，就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這稱為一步歸約。重復(fù) 這一過(guò)程直到歸約棧中只剩文法的開(kāi)始符號(hào)時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。.算法優(yōu)先文法(Operator Precedence Grammar)設(shè)有一不含E產(chǎn)生式的算法文法 G,如果對(duì)任意兩個(gè)終結(jié)

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

21、 (LR(0) items )文法G的產(chǎn)生式的右部適當(dāng)位置添加有一個(gè)圓點(diǎn)則稱為一個(gè)LR(0)項(xiàng)目。. LR(0)項(xiàng)目集規(guī)范族( canonical collection of sets of LR(0) items)構(gòu)成識(shí)別一個(gè)文法活前綴的 DFA項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的 LR(0)項(xiàng)目集規(guī)范族。.活前綴(viable prefixes) *若S號(hào)郎0中是文法G中的一個(gè)規(guī)范推導(dǎo)。如果符號(hào)串7是口0的前綴,則稱是g的一個(gè)活前綴。也就是說(shuō)y是規(guī)范句型e/h的前綴,但它的右端不超過(guò)該句型句柄的末端。這里S為對(duì)原文法G加了產(chǎn)生式S TS , S為原文法G的開(kāi)始符號(hào)，S為拓廣后文法G的開(kāi)始符號(hào)

22、。.屬性文法(Attribute grammar )形式上講，一個(gè)屬性文法是一個(gè)三元組，A= (G, V, F), 一個(gè)上下文無(wú)關(guān)文法G; 一個(gè)屬性的 有窮集V和關(guān)于屬性的斷言或謂詞的有窮集F。每個(gè)屬性與文法的某個(gè)非終結(jié)符或終結(jié)符相聯(lián)。每個(gè)斷言 與文法的某產(chǎn)生式相聯(lián)。如果對(duì)G中的某一輸入串而言(句子)，A中的所有斷言對(duì)該輸入串的語(yǔ)法樹(shù)結(jié) 點(diǎn)的屬性全為真，則該串也是A語(yǔ)言中的句子。編譯程序的靜態(tài)語(yǔ)義審查工作就是驗(yàn)證關(guān)于所編譯的程序 的斷言是否全部為真。.語(yǔ)法制導(dǎo)翻譯(Syntax-directed translation)在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序(或

23、語(yǔ)義規(guī)則描述的 語(yǔ)義動(dòng)作)進(jìn)行翻譯的辦法稱作語(yǔ)法制導(dǎo)翻譯。.中間語(yǔ)言(中間表示) ( Intermediate language(representation)在進(jìn)行了語(yǔ)法分析和語(yǔ)義分析階段的工作之后，有的編譯程序?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)化。.數(shù)組內(nèi)情向量(array dope vector)一般編譯程序?qū)?shù)組說(shuō)明的處理是把數(shù)組的有關(guān)信息匯集在一個(gè)叫做內(nèi)情向量”或 信息向

24、量”的表格中，以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息。每個(gè)數(shù)組有一個(gè)內(nèi)情向量。其中的信息包括，數(shù)組的 類型，維數(shù)，各維的上、下界，以及數(shù)組的首地址。編譯程序處理數(shù)組說(shuō)明的主要工作是把內(nèi)情向量登錄 在符號(hào)表中，這些屬性信息是確定存儲(chǔ)分配時(shí)數(shù)組所占空間的大小和數(shù)組元素位置的依據(jù)。.符號(hào)表(symbol table)在編譯程序中符號(hào)表用來(lái)存放源程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的 語(yǔ)義特征屬性，為進(jìn)行上下文語(yǔ)義審查和進(jìn)一步的翻譯使用。.靜態(tài)存儲(chǔ)分配(Static storage allocation)如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)

25、程序運(yùn)行時(shí)的全 部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置，稱這種分配策略為靜態(tài)存儲(chǔ)分配。.動(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ì)于這種程序在編譯時(shí)無(wú)法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù) 據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。有兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式(stack)和堆式(heapp.過(guò)程的活動(dòng)記錄 AR(Activation Record)過(guò)程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過(guò)程的一次執(zhí)行所需要的信息，一般有如下信息：.臨時(shí)工作單元，

26、比如計(jì)算表達(dá)式過(guò)程中需存放中間結(jié)果用的臨時(shí)值單元。.局部變量，一個(gè)過(guò)程的局部變量。.保存機(jī)器狀態(tài)，容納該過(guò)程執(zhí)行前關(guān)于機(jī)器狀態(tài)的信息，諸如程序計(jì)數(shù)器、寄存器的值，這些值都需要在控制從該過(guò)程返回時(shí)給予恢復(fù)。.存取鏈，用以存取非局部變量，這些變量存放于其它過(guò)程活動(dòng)記錄中。并不是所有語(yǔ)言需要該信 息。.控制鏈，指向調(diào)用該過(guò)程的那個(gè)過(guò)程的活動(dòng)記錄，這也不是所有語(yǔ)言都需要的。.實(shí)參，也稱形式單元，由調(diào)用過(guò)程向該被調(diào)過(guò)程提供實(shí)參的值（或地址）。當(dāng)然在實(shí)際編譯程序 中，也常常使用機(jī)器寄存器傳遞實(shí)參。.返回地址，保存該被調(diào)過(guò)程返回后的地址。. Display 表為能存取非局部變量而紀(jì)錄外包過(guò)程的活動(dòng)記錄地址的

27、數(shù)組。即每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表displayo這里所提到的 嵌套層次”，是指過(guò)程定義的層數(shù)，始終假定主程序的層數(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)記錄的地址。.基本塊（Basic block）所謂基本塊，是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。執(zhí)行時(shí)只 能從其人口語(yǔ)句進(jìn)入，從其出口語(yǔ)句退出。

28、.無(wú)循環(huán)有向圖 DAG （ Directed Acyclic Graph ）如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。基本塊的DAG表示可用于代碼優(yōu)化。.控制流程圖（流圖）（ Control flow graph ）一個(gè)控制流程圖就是具有唯一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開(kāi)始到控制流程圖中任何結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。我們可以把一個(gè)控制流程圖表示成一個(gè)三元組G= （N, E,用。），其中，N代表圖中所有結(jié)點(diǎn)集，E代表圖中所有有向邊集，力。代表首結(jié)點(diǎn)?？刂屏鞒虉D簡(jiǎn)稱為流圖。.循環(huán)（Loop）在程序流圖中，稱具有下列性質(zhì)的結(jié)點(diǎn)序列為一個(gè)循環(huán)：.它們是強(qiáng)連通的。也即

29、，其中任意兩個(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)，有一有向邊引到它，或者它就是 程序流圖的首結(jié)點(diǎn)。.必經(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

30、n。流圖中結(jié)點(diǎn)n的所有必經(jīng)結(jié)點(diǎn)的集合， 稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集， 記為D (n)。.回邊(back edge)假設(shè)a-b是流圖中的一條有向邊，如果 b DOM a,則稱a-b是流圖中的一條回邊。. T 型圖(T diagram )一個(gè)編譯程序涉及到三個(gè)方面的語(yǔ)言，即源語(yǔ)言、目標(biāo)語(yǔ)言和編譯程序的書(shū)寫(xiě)語(yǔ)言。為了描述方便通 常用T型圖來(lái)表示一個(gè)編譯程序所涉及到的這三個(gè)方面的語(yǔ)言。T型圖的左上角表示源語(yǔ)言，右上角表示目標(biāo)語(yǔ)言，底部表示書(shū)寫(xiě)語(yǔ)言 (實(shí)現(xiàn)語(yǔ)言)。.自展(bootstrap)自展的思想是先用目標(biāo)機(jī)的匯編語(yǔ)言或機(jī)器語(yǔ)言書(shū)寫(xiě)源語(yǔ)言的一個(gè)子集的編譯程序，然后再用這個(gè)子 集作為書(shū)寫(xiě)語(yǔ)言，實(shí)現(xiàn)源語(yǔ)言的編譯程序，如果把這個(gè)過(guò)程根據(jù)情況分成若干步，像滾雪球一樣直到生成 預(yù)計(jì)源語(yǔ)言的編譯程序?yàn)橹梗覀儼堰@樣的實(shí)現(xiàn)方式稱為自展技術(shù)。.交叉編譯(Cross compile)所謂交叉編譯是指把一個(gè)源語(yǔ)言在一個(gè)機(jī)器(稱為宿主機(jī))上編譯產(chǎn)生另一個(gè)機(jī)器(稱為目標(biāo)機(jī))的匯編語(yǔ)言或機(jī)器語(yǔ)言。.前端(Front-end)有時(shí)，常常把編譯的過(guò)程分為前端 (front end)和后端(back end),前端由那樣一些階段組成：這些階段的工作主要依賴于源語(yǔ)言而與目標(biāo)機(jī)無(wú)關(guān)。通常這些階段包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生 成，某些優(yōu)化工作也可在前端做，也包括與前端每個(gè)階段相