編譯原理詞匯表

編譯程序編譯程序是一種翻譯程序，它將高級(jí)語言所寫的源程序翻譯成等價(jià)的機(jī)器語言或匯編語言的目標(biāo)程序。詞法分析（Lexicalanalysis或Scanning）和詞法分析程序（Lexicalanalyzer或Scanner）詞法分析階段是編譯過程的第一個(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)生成。

語法分析（Syntaxanalysis或Parsing）和語法分析程序（Parser）語法分析是編譯過程的一個(gè)邏輯階段。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等.語法分析程序判斷源程序在結(jié)構(gòu)上是否正確.源程序的結(jié)構(gòu)由上下文無關(guān)文法描述.語義分析（Syntaxanalysis）及中間代碼生成語義分析是編譯過程的一個(gè)邏輯階段.語義分析的任務(wù)是對(duì)結(jié)構(gòu)上正確的源程序進(jìn)行上下文有關(guān)性質(zhì)的審查,進(jìn)行類型審查.例如一個(gè)C程序片斷:

intarr[2],b;

b=arr*10;

源程序的結(jié)構(gòu)是正確的.

語義分析將審查類型并報(bào)告錯(cuò)誤:不能在表達(dá)式中使用一個(gè)數(shù)組變量,賦值語句的右端和左端的類型不匹配.語義分析時(shí)，根據(jù)語句的含義，可對(duì)它進(jìn)行翻譯，用另一種語言形式（比源語言更接近于目標(biāo)語言的一種中間代碼或直接用目標(biāo)語言）來描述這種語義。代碼優(yōu)化代碼優(yōu)化的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得更為高效的，即省時(shí)間和空間的代碼。目標(biāo)代碼生成目標(biāo)代碼的生成的任務(wù)是將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。遍前端及后端編譯程序和解釋程序Lex一個(gè)詞法分析程序的自動(dòng)生成工具。它輸入描述構(gòu)詞規(guī)則的一系列正規(guī)式,然后構(gòu)建有窮自動(dòng)機(jī)和這個(gè)有窮自動(dòng)機(jī)的一個(gè)驅(qū)動(dòng)程序,進(jìn)而生成一個(gè)詞法分析程序.Yacc一個(gè)語法分析程序的自動(dòng)生成工具。它接受語言的文法,構(gòu)造一個(gè)LALR(1)分析程序.因?yàn)樗捎谜Z法制導(dǎo)翻譯的思想,還可以接受用C語言描述的語義動(dòng)作,從而構(gòu)造一個(gè)編譯程序.

Yacc是Yetanothercompilercompiler的縮寫.源語言（Sourcelanguage）和源程序（Sourceprogram）被編譯程序翻譯的程序稱為源程序,書寫該程序的語言稱為源語言.目標(biāo)語言（ObjectlanguageorTargetlanguage）和目標(biāo)程序（ObjectprogramorTargetprogram）編譯程序翻譯源程序而得到的結(jié)果程序稱為目標(biāo)程序,書寫該程序的語言稱為目標(biāo)語言.中間語言（中間表示）（Intermediatelanguage(representation)）在進(jìn)行了語法分析和語義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)復(fù)雜性介于源程序語言和機(jī)器語言之間，容易將它翻譯成目標(biāo)代碼。另外，還可以在中間代碼一級(jí)進(jìn)行與機(jī)器無關(guān)的優(yōu)化。常見的中間代碼形式有：逆波蘭式、三元式、四元式和三地址代碼。文法（Grammars）文法是用于描述語言的語法結(jié)構(gòu)的形式規(guī)則。文法G定義為四元組(VN，VT，P，S)。其中VN為非終結(jié)符號(hào)(或語法實(shí)體，或變量)集；VT為終結(jié)符號(hào)集；P為產(chǎn)生式(也稱規(guī)則)的集合；產(chǎn)生式(規(guī)則)是形如α→β或a::=b的(a,b)有序?qū)?其中α∈(VN∪VT)*且至少含有一個(gè)非終結(jié)符，而β∈(VN∪VT)*。VN，VT和P是非空有窮集。S稱作識(shí)別符號(hào)或開始符號(hào)，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。一個(gè)文法的例子:G=(VN={A，R},P={0,1}，P={A→0R，A→01,R→A1},S=A)文法分類（AhierarchyofGrammars）著名語言學(xué)家NoamChomsky定義了四類文法和四種形式語言類，文法的四種類型分別是0型、1型、2型和3型。幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制，分別是：

0型文法(短語結(jié)構(gòu)文法)(phrasestructuregrammars)：

設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu)α∈(VN∪VT)*且至少含有一個(gè)非終結(jié)符，而β∈(VN∪VT)*，則G是一個(gè)0型文法。

1型文法（上下文有關(guān)文法）(context-sensitivegrammars)：

設(shè)G=(VN，VT，P，S)為一文法|α|，若P中的每一個(gè)產(chǎn)生式α→β均滿足|β|≥|α|，僅僅S→ε除外，則文法G是1型或上下文有關(guān)的。

2型文法（上下文無關(guān)文法）(context-freegrammars)：

設(shè)G=(VN，VT，P，S)，若P中的每一個(gè)產(chǎn)生式α→β滿足：α是一非終結(jié)符，β∈(VN∪VT)*則此文法稱為2型的或上下文無關(guān)的。

3型文法（正規(guī)文法）(regulargrammars)：

設(shè)G=(VN，VT，P，S)，若P中的每一個(gè)產(chǎn)生式的形式都是A→aB或A→a，其中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è)G［S］是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來的，即有Sx，則稱x是文法G［S］的句型。若x僅由終結(jié)符號(hào)組成，即Sx，x∈VT*，則稱x為G［S］的句子。

文法G所產(chǎn)生的語言定義為集合｛x｜Sx，其中S為文法識(shí)別符號(hào)，且x∈VT*｝。可用L(G)或L(G[S])表示該集合。

推導(dǎo)（Derive）和語法樹（Parsetree）推導(dǎo)的概念：分別定義V*中的符號(hào)之間的關(guān)系直接推導(dǎo)、長度為n（n≥1）的推導(dǎo)和長度為n（n≥0）的推導(dǎo)：

（1）如α→β是文法G=(VN，VT，P，S)的規(guī)則（或說是P中的一個(gè)產(chǎn)生式），γ和δ是V*中的任意符號(hào)，若有符號(hào)串v，w滿足：

v＝γαδ，w＝γβδ

則說v（應(yīng)用規(guī)則α→β）直接產(chǎn)生w，或說，w是v的直接推導(dǎo)，或說，w直接歸約到v，記做vw。

（2）如果存在直接推導(dǎo)的序列：

vw0w1w2…wnw，（n>0）

則稱v推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長度為n），或稱w歸約到v。記作vw。

（3）若有vw，或v＝w，則記作。

語法樹（推導(dǎo)樹）的概念：給定文法G=(VN，VT，P，S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(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，那么A→A1A2，…，Ak一定是P中的一個(gè)產(chǎn)生式。

二義文法（Ambiguousgrammer）如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則說這個(gè)文法是二義的?；蛘哒f，若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左(最右)推導(dǎo)，則這個(gè)文法是二義的。短語，句柄(phrase,sentencehandle)令G是一文法，S是文法的開始符號(hào)，αβδ是文法G的一個(gè)句型。如果有：且則稱β是句型αβδ相對(duì)與非終結(jié)符A的短語。特別，如有則稱β是句型αβδ相對(duì)于規(guī)則A→β的直接短語(也稱簡單短語)。一個(gè)句型的最左直接短語稱為該句型的句柄。正規(guī)式（regularexpression）和它所表示的正規(guī)集（regularset）設(shè)字母表為Σ,輔助字母表Σ’=｛Φ,ε，｜，.，*,(,)｝。

1.ε和Φ都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Φ；

2.任何a∈Σ，a是Σ上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；

3.假定е1和е2都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(е1)和L(е2)，那么，(е1)，е1｜е2，е1·е2和е2*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(е1)，L(е1)∪L(е2)，L(е1)L(е2)和(L(е1))*。

4.僅由有限次使用上述三步驟而定義的表達(dá)式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。

確定的有窮狀態(tài)自動(dòng)機(jī)DFA(deterministicfiniteautomaton)和不確定的有窮狀態(tài)自動(dòng)機(jī)NFA(nondeterministicfiniteautomaton）我們這里是把DFA和NFA作為正規(guī)集的識(shí)別工具而介紹的。

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ù)，是在K×Σ→K上的映像，即，如f(ki,a)=kj(ki∈K,kj∈K)就意味著，當(dāng)前狀態(tài)為ki，輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài);

4.S∈K是唯一的一個(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是一個(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è)NFAM，存在一個(gè)DFAM’，使得L（M）＝L（M’），即M和M’是等價(jià)的。

最小狀態(tài)DFA(reducedDFAorminimumDFA)我們說一個(gè)確定的有窮自動(dòng)機(jī)是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的，這種DFA也叫做最小狀態(tài)DFA。一個(gè)DFA可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)與之等價(jià)的最小狀態(tài)DFA。24．FIRST集設(shè)G=(VN，VT，P，S)是上下文無關(guān)文法FIRST(α)=｛a｜，a∈VT，α,β∈V*｝若，則規(guī)定∈FIRST(α)。

25．FOLLOW集設(shè)G=(VN，VT，P，S)是上下文無關(guān)文法，A∈VN，Ｓ是開始符號(hào)

FOLLOW(A)=｛a｜且a∈VT，a∈FIRST(β)，μ∈VT*，β∈V+｝

若，且，則#∈FOLLOW(A)。

也可定義為：FOLLOW(A)={a|…Aa…,a∈VT}

若有…A，則規(guī)定#∈FOLLOW(A)

這里我們用‘?！鳛檩斎氪慕Y(jié)束符，或稱為句子括號(hào)，如：＃輸入串＃。

26．SELECT集給定上下文無關(guān)文法的產(chǎn)生式A→α

A∈VN，α∈V*，若，則SELECT(A→α)=FIRST(α)如果，則SELECT(A→α)=FIRST(α)∪FOLLOW(A)。

27．左遞歸文法（Leftrecursivegrammar）

一個(gè)文法含有下列形式的產(chǎn)生式時(shí)。

a)A→Aβ

A∈VN，β∈V*

b)A→Bβ

B→Ａα

A,B∈VN，α、β∈V*

在a)中也可稱為含有左遞歸的規(guī)則或稱直接左遞歸，在b)中為AＡ…稱文法中含有左遞歸或間接左遞歸，文法中只要含有a)或含有b)或二者皆有均認(rèn)為文法是左遞歸的。

28．LL（1）文法

滿足如下條件的上下文無關(guān)文法稱為LL（1）文法：對(duì)每個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，

A→α，A→β，滿足

SELECT（A→α）SELECT（A→β）＝Φ

其中α、β不同時(shí)能。

LL（1）文法的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過程中將用最左推導(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。

29．遞歸子程序法（Recursive-descent）

遞歸子程序法是LL（1）文法的分析程序的一種實(shí)現(xiàn)方法。它對(duì)應(yīng)文法中每個(gè)非終結(jié)符編寫一個(gè)遞歸過程，這種分析程序由這一系列遞歸過程的相互調(diào)用來完成語法分析工作。

30．移進(jìn)－歸約分析（shift－reduceanalysis）

自底向上分析方法，也稱移進(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ù)這一過程直到歸約棧中只剩文法的開始符號(hào)時(shí)則為分析成功，也就確認(rèn)輸入串是文法的句子。

31．算符優(yōu)先文法(OperatorPrecedenceGrammar)

設(shè)有一不含產(chǎn)生式的算法文法G，如果對(duì)任意兩個(gè)終結(jié)符對(duì)a，b之間至多只有＜·、·＞和三種關(guān)系的一種成立，則稱G是一個(gè)算符優(yōu)先文法(OperatorPrecedenceGrammar)，即OPG文法。

32．最左素短語（Mostleftprimephrase）

設(shè)有文法G［S］，其句型的素短語是一個(gè)短語，它至少包含一個(gè)終結(jié)符，并除自身外不包含其它素短語，句型的最左邊的素短語稱最左素短語。

33．LR分析

是一種自底向上的語法分析技術(shù),通常稱為LR(K).L是說從左至右掃描輸入串,R是說分析過程所形成的推導(dǎo)是最右推導(dǎo),K是指在做分析決策時(shí)向前察看K個(gè)輸入符號(hào).LR分析可用于一大類上下文無關(guān)文法,是一種最常用的無回朔的移進(jìn)歸約分析,

34．屬性文法（Attributegrammar）

形式上講，一個(gè)屬性文法是一個(gè)三元組，Ａ＝（Ｇ，Ｖ，Ｆ），一個(gè)上下文無關(guān)文法Ｇ；一個(gè)屬性的有窮集Ｖ和關(guān)于屬性的斷言或謂詞的有窮集Ｆ。每個(gè)屬性與文法的某個(gè)非終結(jié)符或終結(jié)符相聯(lián)。每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。如果對(duì)Ｇ中的某一輸入串而言（句子），Ａ中的所有斷言對(duì)該輸入串的語法樹結(jié)點(diǎn)的屬性全為真，則該串也是Ａ語言中的句子。編譯程序的靜態(tài)語義審查工作就是驗(yàn)證關(guān)于所編譯的程序的斷言是否全部為真。屬性分為兩類：綜合屬性和繼承屬性。35．語法制導(dǎo)翻譯（Syntax-directedtranslation）

在語法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序（或語義規(guī)則描述的語義動(dòng)作）進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。

36．?dāng)?shù)組內(nèi)情向量（arraydopevector）一般編譯程序?qū)?shù)組說明的處理是把數(shù)組的有關(guān)信息匯集在一個(gè)叫做“內(nèi)情向量”或“信息向量”的表格中，以便以后計(jì)算數(shù)組元素的地址時(shí)引用這些信息。每個(gè)數(shù)組有一個(gè)內(nèi)情向量。其中的信息包括，數(shù)組的類型，維數(shù)，各維的上、下界，以及數(shù)組的首地址。編譯程序處理數(shù)組說明的主要工作是把內(nèi)情向量登錄在符號(hào)表中，這些屬性信息是確定存儲(chǔ)分配時(shí)數(shù)組所占空間的大小和數(shù)組元素位置的依據(jù)。

37．符號(hào)表（symboltable）在編譯程序中符號(hào)表用來存放源程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語義特征屬性,為進(jìn)行上下文語義審查和進(jìn)一步的翻譯使用。編譯程序處理標(biāo)識(shí)符時(shí)主要涉及兩部分內(nèi)容，其一是標(biāo)識(shí)符本身，其二是標(biāo)識(shí)符相關(guān)的信息。符號(hào)表上有三種操作：填入、查找和更新。符號(hào)表的查找方法有順序查找、二分查找和散列（雜湊）查找法。38．運(yùn)行時(shí)的環(huán)境及存儲(chǔ)空間所謂運(yùn)行時(shí)的環(huán)境是指目標(biāo)計(jì)算機(jī)的寄存器和存儲(chǔ)器的結(jié)構(gòu)，以及用來管理存儲(chǔ)器并保存執(zhí)行過程所需要的信息。存儲(chǔ)空間包括用戶定義的各種類型的數(shù)據(jù)對(duì)象所需要的存儲(chǔ)空間、調(diào)用過程所需要的連接單元和組織輸入/輸出所需要的緩沖區(qū)及保留中間接過和傳遞參數(shù)所需要的臨時(shí)單元。存儲(chǔ)空間通常被劃分為：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)。39．靜態(tài)存儲(chǔ)分配（Staticstorageallocation）如果在編譯時(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ǔ)分配（Dynamicstorageallocation）如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。因?yàn)閷?duì)于這種程序在編譯時(shí)無法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。有兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式（stack）和堆式（heap）。41．過程的活動(dòng)記錄AR(ActivationRecord)過程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過程的一次執(zhí)行所需要的信息，

一般有如下信息：

1．臨時(shí)工作單元，比如計(jì)算表達(dá)式過程中需存放中間結(jié)果用的臨時(shí)值單元。

2．局部變量，一個(gè)過程的局部變量。

3．保存機(jī)器狀態(tài)，容納該過程執(zhí)行前關(guān)于機(jī)器狀態(tài)的信息，諸如程序計(jì)數(shù)器、寄存器的值，這些值都需要在控制從該過程返回時(shí)給予恢復(fù)。

4．存取鏈，用以存取非局部變量，這些變量存放于其它過程活動(dòng)記錄中。并不是所有語言需要該信息。

5．控制鏈，指向調(diào)用該過程的那個(gè)過程的活動(dòng)記錄，這也不是所有語言都需要的。

6．實(shí)參，也稱形式單元，由調(diào)用過程向該被調(diào)過程提供實(shí)參的值（或地址）。當(dāng)然在實(shí)際編譯程序中，也常常使用機(jī)器寄存器傳遞實(shí)參。

7．返回地址，保存該被調(diào)過程返回后的地址。

42．Display表為能存取非局部變量而紀(jì)錄外包過程的活動(dòng)記錄地址的數(shù)組。即每進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display。這里所提到的“嵌套層次”，是指過程定義的層數(shù)，始終假定主程序的層數(shù)為0，因此主程序稱為0層過程。如某過程p是在層次為i的過程q內(nèi)定義的，并且q是包圍p的直接外層，那么p的過程層數(shù)為i+1。display是一個(gè)指針數(shù)組d，也可看做是一個(gè)小棧，自頂向下每個(gè)單元依次存放著現(xiàn)行層，直接外層，……直至最外層（0層，主程序?qū)樱┑让恳粚舆^程的最新活動(dòng)記錄的地址。

43．活前綴(viableprefixes)和拓廣文法若是文法G中的一個(gè)規(guī)范推導(dǎo)。

如果符號(hào)串γ是αβ的前綴，則稱γ是G的一個(gè)活前綴。也就是說γ是規(guī)范句型αβω的前綴，但它的右端不超過該句型句柄的末端。這里S為對(duì)原文法G加了產(chǎn)生式S′→Ｓ，S為原文法G的開始符號(hào)，S′為拓廣后文法G′的開始符號(hào)。

44．LR(0)項(xiàng)目和LR(0)項(xiàng)目集規(guī)范族(LR(0)itemsandcanonicalcollectionofsetsofLR(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)目。構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族。45．同心集所謂同心的LR(1)項(xiàng)目集是指在兩個(gè)LR(1)項(xiàng)目集中，除搜索符不同之外，核心部分是相同的。46．代碼優(yōu)化（CodeOptimization）所謂代碼優(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ī)器無關(guān)的優(yōu)化。與機(jī)器無關(guān)的優(yōu)化，常見的優(yōu)化技術(shù)：刪除公共子表達(dá)式（刪除多余運(yùn)算）、代碼外提、強(qiáng)度削弱、變換循環(huán)控制條件（刪除歸納變量）、合并已知量、復(fù)寫傳播和刪除無用賦值。47．基本塊（Basicblock）和DAG所謂基本塊，是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口語句和一個(gè)出口語句。執(zhí)行時(shí)只能從其入口語句進(jìn)入，從其出口語句退出。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無環(huán)路有向圖，簡稱ＤＡＧ?；緣K的DAG表示可用于代碼優(yōu)化。在一個(gè)基本塊內(nèi)，可以執(zhí)行三種優(yōu)化：刪除多余運(yùn)算、、合并已知量、刪除無用賦值。48．控制流程圖（流圖）（Controlflowgraph）

一個(gè)控制流程圖就是具有唯一首結(jié)點(diǎn)的有向圖。所謂首結(jié)點(diǎn)，就是從它開始到控制流程圖中任何結(jié)點(diǎn)都有一條通路的結(jié)點(diǎn)。我們可以把一個(gè)控制流程圖表示成一個(gè)三元組Ｇ＝（Ｎ，Ｅ，），其中，Ｎ代表圖中所有結(jié)點(diǎn)集，Ｅ代表圖中所有有向邊集，代表首結(jié)點(diǎn)?？刂屏鞒虉D簡稱為流圖。

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)過循環(huán)的入口結(jié)點(diǎn)。

所謂入口結(jié)點(diǎn)，是指序列中具有下述性質(zhì)的結(jié)點(diǎn)：從序列外某結(jié)點(diǎn)，有一有向邊引到它，或者它就是程序流圖的首結(jié)點(diǎn)。

50．必經(jīng)結(jié)點(diǎn)（dominators）和必經(jīng)結(jié)點(diǎn)集（dominatorsset）

在程序流圖中，對(duì)任意兩個(gè)結(jié)點(diǎn)m和n，如果從流圖的首結(jié)點(diǎn)出發(fā)，到達(dá)n的任一通路都要經(jīng)過m，則稱m是n的必經(jīng)結(jié)點(diǎn)，記為mDOMn。流圖中結(jié)點(diǎn)ｎ的所有必經(jīng)結(jié)點(diǎn)的集合，稱為結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集，記為D（n）。

51．回邊（backedge）

假設(shè)a→b是流圖中的一條有向邊，如果bDOMa，則稱a→b是流圖中的一條回邊。

52．T型圖（Tdiagram）

一個(gè)編譯程序涉及到三個(gè)方面的語言，即源語言、目標(biāo)語言和編譯程序的書寫語言。為了描述方便通常用T型圖來表示一個(gè)編譯程序所涉及到的這三個(gè)方面的語言。T型圖的左上角表示源語言，右上角表示目標(biāo)語言，底部表示書寫語言(實(shí)現(xiàn)語言)。

53．自展（bootstrap）

自展的思想是先用目標(biāo)機(jī)的匯編語言或機(jī)器語言書寫源語言的一個(gè)