編譯原理基本概念(共13頁)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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