編譯原理詞匯表答疑庫

第1頁共22頁編譯原理詞匯表答疑庫

1．詞法分析（Lexicalanalysis或Scanning）和詞法分析程序（Lexicalanalyzer或Scanner）

詞法分析階段是編譯過程的第一個階段。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，即對構(gòu)成源程序的字符流進行掃描然后根據(jù)構(gòu)詞規(guī)則識別單詞(也稱單詞符號或符號)。詞法分析程序?qū)崿F(xiàn)這個任務(wù)。詞法分析程序可以使用lex等工具自動生成。

2．語法分析（Syntaxanalysis或Parsing）和語法分析程序（Parser）

語法分析是編譯過程的一個邏輯階段。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達式”等等.語法分析程序判斷源程序在結(jié)構(gòu)上是否正確.源程序的結(jié)構(gòu)由上下文無關(guān)文法描述.

3．語義分析（Syntaxanalysis）

語義分析是編譯過程的一個邏輯階段.語義分析的任務(wù)是對結(jié)構(gòu)上正確的源程序進行上下文有關(guān)性質(zhì)的審查,進行類型審查.例如一個C程序片斷:

intarr[2],b;

b=arr*10;

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

語義分析將審查類型并報告錯誤:不能在表達式中使用一個數(shù)組變量,賦值語句的右端和左端的類型不匹配.

4.Lex

一個詞法分析程序的自動生成工具。它輸入描述構(gòu)詞規(guī)則的一系列正規(guī)式,然后構(gòu)建有窮自動機和這個有窮自動機的一個驅(qū)動程序,進而生成一個詞法分析程序.

5.Yacc

一個語法分析程序的自動生成工具。它接受語言的文法,構(gòu)造一個LALR(1)分析程序.因為它采用語法制導(dǎo)翻譯的思想,還可以接受用C語言描述的語義動作,從而構(gòu)造一個編譯程序.

Yacc是Yetanothercompilercompiler的縮寫.

6．源語言（Sourcelanguage）和源程序（Sourceprogram）

被編譯程序翻譯的程序稱為源程序,書寫該程序的語言稱為源語言.

7．目標(biāo)語言（ObjectlanguageorTargetlanguage）和目標(biāo)程序（ObjectprogramorTargetprogram）

編譯程序翻譯源程序而得到的結(jié)果程序稱為目標(biāo)程序,書寫該程序的語言稱為目標(biāo)語言.

8．中間語言（中間表示）（Intermediatelanguage(representation)）

在進行了語法分析和語義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語言或中間表示或中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)復(fù)雜性介于源程序語言和機器語言之間，容易將它翻譯成目標(biāo)代碼。另外，還可以在中間代碼一級進行與機器無關(guān)的優(yōu)化。

9．文法（Grammars）

文法是用于描述語言的語法結(jié)構(gòu)的形式規(guī)則。文法G定義為四元組(，，，)。其中為非終結(jié)符號(或語法實體，或變量)集；為終結(jié)符號集；為產(chǎn)生式(也稱規(guī)則)的集合；產(chǎn)生式(規(guī)則)是形如或a::=b的(a,b)有序?qū)?其中(∪)且至少含有一個非終結(jié)符，而(∪)。，和是非空有窮集。稱作識別符號或開始符號，它是一個非終結(jié)符，至少要在一條規(guī)則中作為左部出現(xiàn)。

一個文法的例子:G=(={A，R},={0,1}，={A?0R，A?01,R?A1},=A)

10．文法分類（AhierarchyofGrammars）

著名語言學(xué)家NoamChomsky定義了四類文法和四種形式語言類，文法的四種類型分別是0型、1型、2型和3型。幾類文法的差別在于對產(chǎn)生式施加不同的限制，分別是：

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

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

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

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

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

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

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

設(shè)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ī)語言。

11．句型（Sententialform），句子（Sentence）和語言（Language）

設(shè)G［S］是一文法，如果符號串x是從識別符號推導(dǎo)出來的，即有Sx，則稱x是文法G［S］的句型。若x僅由終結(jié)符號組成，即Sx，x∈，則稱x為G［S］的句子。

文法G所產(chǎn)生的語言定義為集合｛x｜Sx，其中S為文法識別符號，且x∈｝?？捎肔(G)或L(G[S])表示該集合。

12.推導(dǎo)（Derive）和語法樹（Parsetree）

推導(dǎo)的概念：分別定義V*中的符號之間的關(guān)系直接推導(dǎo)、長度為n（n1）的推導(dǎo)和長度為n（n0）的推導(dǎo)：

（1）如是文法G=(，，，)的規(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)的序列：

vw0w1w2…wnw，（n>0）

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

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

語法樹（推導(dǎo)樹）的概念：給定文法G=(，，，)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹滿足下列4個條件：

①每個結(jié)點都有一個標(biāo)記，此標(biāo)記是V的一個符號。

②根的標(biāo)記是S。

③若一個結(jié)點n至少有一個它自己除外的子孫，并且有標(biāo)記A，則A肯定在中。

④如果結(jié)點n的直接子孫，從左到右的次序是結(jié)點n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么AA1A2，…，Ak一定是P中的一個產(chǎn)生式。

13．二義文法（Ambiguousgrammer）

如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則說這個文法是二義的?；蛘哒f，若一個文法中存在某個句子，它有兩個不同的最左(最右)推導(dǎo)，則這個文法是二義的。

14．短語，句柄(phrase,sentencehandle)

令G是一文法，S是文法的開始符號，是文法G的一個句型。如果有：且則稱是句型相對與非終結(jié)符A的短語。特別，如有則稱是句型相對于規(guī)則的直接短語(也稱簡單短語)。一個句型的最左直接短語稱為該句型的句柄。

15．正規(guī)式（regularexpression）和它所表示的正規(guī)集（regularset）

設(shè)字母表為,輔助字母表=｛,，｜，.，*,(,)｝。

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

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

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

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

16．確定的有窮狀態(tài)自動機DFA(deterministicfiniteautomaton)和不確定的有窮狀態(tài)自動機NFA(nondeterministicfiniteautomaton）

我們這里是把DFA和NFA作為正規(guī)集的識別工具而介紹的。

DFA定義如下：

一個確定的有窮自動機(DFA)M是一個五元組：M=(K,，f，S，Z)其中

1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；

2.是一個有窮字母表，它的每個元素稱為一個輸入字符,所以也稱為輸入符號字母表:

3.f是轉(zhuǎn)換函數(shù)，是在K×K上的映像，即，如f(,a)=(∈K,∈K)就意味著，當(dāng)前狀態(tài)為，輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài)，我們把稱作的一個后繼狀態(tài);

4.S∈K是唯一的一個初態(tài)；

5.ZK，是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。

NFA定義如下;

一個不確定的有窮自動機(NFA)M是一個五元組，M=(K,，f，S，Z)其中

1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；

2.是一個有窮字母表，它的每個元素稱為一個輸入字符；

3.f是一個從K×到K的子集的映像.

4.SK，是一個非空初態(tài)集;

5.ZK，是一個終態(tài)集。

DFA和NFA的等價定理：對于每個NFAM，存在一個DFAM’，使得L（M）＝L（M’），即M和M’是等價的。

17．最小狀態(tài)DFA(reducedDFAorminimumDFA)

我們說一個確定的有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的，這種DFA也叫做最小狀態(tài)DFA。一個DFA可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個與之等價的最小狀態(tài)DFA。

18．FIRST集

設(shè)G=(，，，)是上下文無關(guān)文法FIRST()=｛a｜，a∈，,∈｝若，則規(guī)定∈FIRST()。

19．FOLLOW集

設(shè)G=(，，，)是上下文無關(guān)文法，A∈，Ｓ是開始符號

FOLLOW(A)=｛a｜且a∈，a∈FIRST()，，｝

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

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

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

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

20．SELECT集

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

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

21．左遞歸文法（Leftrecursivegrammar）

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

a)A→A

A∈，∈

b)A→B

B→Ａ

A,B∈，、∈

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

22．LL（1）文法

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

A→，A→，滿足

SELECT（A→）SELECT（A→）＝

其中、不同時能。

LL（1）文法的含義是：第一個L表明自頂向下分析是從左向右掃描輸入串，第二個L表明分析過程中將用最左推導(dǎo)，1表明只需向右看一個符號便可決定如何推導(dǎo)即選擇哪個產(chǎn)生式（規(guī)則）進行推導(dǎo)，類似也可以有LL（K）文法，也就是需向前查看K個符號才可確定選用哪個產(chǎn)生式。通常采用K＝1，個別情況采用K＝2。

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

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

24．移進－歸約分析（shift－reduceanalysis）

自底向上分析方法，也稱移進－歸約分析法，它的實現(xiàn)思想是對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個后進先出棧中，邊移入邊分析，一旦棧頂符號串形成某個句型的句柄時，（該句柄對應(yīng)某產(chǎn)生式的右部），就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號串，這稱為一步歸約。重復(fù)這一過程直到歸約棧中只剩文法的開始符號時則為分析成功，也就確認輸入串是文法的句子。

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

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

26．最左素短語（Mostleftprimephrase）

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

27．LR分析

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

28．屬性文法（Attributegrammar）

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

29．語法制導(dǎo)翻譯（Syntax-directedtranslation）

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

30．?dāng)?shù)組內(nèi)情向量（arraydopevector）

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

31．符號表（symboltable）

在編譯程序中符號表用來存放源程序中出現(xiàn)的有關(guān)標(biāo)識符的屬性信息，這些信息集中反映了標(biāo)識符的語義特征屬性,為進行上下文語義審查和進一步的翻譯使用。

32．靜態(tài)存儲分配（Staticstorageallocation）

如果在編譯時能確定目標(biāo)程序運行中所需的全部數(shù)據(jù)空間的大小，編譯時安排好目標(biāo)程序運行時的全部數(shù)據(jù)空間，確定每個數(shù)據(jù)對象的存儲位置，稱這種分配策略為靜態(tài)存儲分配。

33．動態(tài)存儲分配（Dynamicstorageallocation）

如果一個程序設(shè)計語言允許遞歸過程、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用動態(tài)存儲管理技術(shù)。因為對于這種程序在編譯時無法知道它在運行時需要多大的存儲空間，它所需要的數(shù)據(jù)空間的大小需待程序運行時動態(tài)地確定。有兩種動態(tài)存儲分配方式：棧式（stack）和堆式（heap）。

34．過程的活動記錄AR(ActivationRecord)

過程的活動記錄是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的信息，

一般有如下信息：

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

2．局部變量，一個過程的局部變量。

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

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

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

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

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

35．Display表

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

36．活前綴(viableprefixes)

若是文法G中的一個規(guī)范推導(dǎo)。

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

37．代碼優(yōu)化（CodeOptimization）

所謂代碼優(yōu)化，實質(zhì)上是對代碼進行等價變換，使得變換后的代碼運行結(jié)果與變換前代碼運行結(jié)果相同，而運行速度加大或占用存儲空間少，或兩者都有。

38．基本塊（Basicblock）和DAG

所謂基本塊，是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句。執(zhí)行時只能從其入口語句進入，從其出口語句退出。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無環(huán)路有向圖，簡稱ＤＡＧ?；緣K的DAG表示可用于代碼優(yōu)化。

39．控制流程圖（流圖）（Controlflowgraph）

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

40．循環(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é)點，有一有向邊引到它，或者它就是程序流圖的首結(jié)點。

41．必經(jīng)結(jié)點（dominators）和必經(jīng)結(jié)點集（dominatorsset）

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

42．回邊（backedge）

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

43．T型圖（Tdiagram）

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

44．自展（bootstrap）

自展的思想是先用目標(biāo)機的匯編語言或機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集作為書寫語言，實現(xiàn)源語言的編譯程序，如果把這個過程根據(jù)情況分成若干步，像滾雪球一樣直到生成預(yù)計源語言的編譯程序為止，我們把這樣的實現(xiàn)方式稱為自展技術(shù)。

45．Token

具有集合意義的字符序列.是詞法分析的輸出.Token一般分為標(biāo)識符,常數(shù)(常量),關(guān)鍵字,運算符及界符.

46．交叉編譯（Crosscompile）

所謂交叉編譯是指把一個源語言在一個機器(稱為宿主機)上編譯產(chǎn)生另一個機器(稱為目標(biāo)機)的匯編語言或機器語言。

47.前端（Front－end）和后端（Backend）

有時，常常把編譯的過程分為前端(frontend)和后端(backend)，前端由那樣一些階段組成：這些階段的工作主要依賴于源語言而與目標(biāo)機無關(guān)。通常這些階段包括詞法分析、語法分析、語義分析和中間代碼生成，某些優(yōu)化工作也可在前端做，也包括與前端每個階段相關(guān)的出錯處理工作和符號表管理工作。后端工作指那些依賴于目標(biāo)機而一般不依賴源語言，只與中間代碼有關(guān)的那些階段，即目標(biāo)代碼生成，以及相關(guān)出錯處理和符號表操作。

48．LR(0)項目和LR(0)項目集規(guī)范族(LR(0)itemsandcanonicalcollectionofsetsofLR(0)items)

文法G的產(chǎn)生式的右部適當(dāng)位置添加有一個圓點則稱為一個LR(0)項目。構(gòu)成識別一個文法活前綴的DFA項目集(狀態(tài))的全體稱為這個文法的LR(0)項目集規(guī)范族。

49．四元式(quadruples)

四元式是一種中間代碼的形式,是一個有四個域的紀錄結(jié)構(gòu):四個域分別稱為op,arg1,arg2和result即操作符,運算對象1,運算對象2和運算結(jié)果.一個例子:(+,a,b,c)

50．傳值（Call－by－value）和傳地址（Call－by－reference）

是調(diào)用過程向被調(diào)用過程參數(shù)傳遞的兩種方法.

傳值也稱值調(diào)用，即將實參計算處它的值，然后把它傳給被調(diào)過程。具體如下：

①形式參數(shù)當(dāng)作過程的局部變量處理，即在被調(diào)過程的活動記錄中開辟了形參的存儲空間，這些存儲位置即是我們所說的實參或形式單元。

②調(diào)用過程計算實參的值，并將它們的右值（r－value）放在為形式單元開辟的空間中。

③被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。

傳值或值調(diào)用的重要特點是對形式參數(shù)的任何運算不影響調(diào)用過程的活動記錄中實參的值。

當(dāng)參數(shù)通過引用傳遞時，也稱作傳地址，或引用調(diào)用。調(diào)用過程傳給被調(diào)過程的是指針，指向?qū)崊⒋鎯ξ恢玫闹羔槨?/p>

①如實參是一個名字或是具有左值的表達式，則左值本身傳遞過去。

1、證明對任一左線性文法G，若α∈L（G）則α的第一個符號必定是α的句柄。

2、分別給出與圖1的FA等價的正規(guī)文法G和正規(guī)式r。

3、給出與如下文法G(S)等價的LL(1)文法G'(S)。

4、下列算符文法G[S]是二義的，其定義一般程序設(shè)計語言的if語句和其他（非if）語句，按照else與最近的then匹配（或者說then和else之間的語句是"匹配"的）的原則，給出一個與G[S]等價的OPG文法G'[S]。

5、使用圖2的LR分析表分析d;;a是不是如下文法G[S]的句子，按照LR分析算法給出分析步驟。

6、圖3中的程序，過程調(diào)用序列為Sort→quiksort→partition→exchange若目標(biāo)代碼運行時的環(huán)境采用棧式存儲管理方案，描述此時exchange的AR的display表內(nèi)容。

7、通?？墒褂靡豢梅Q作DOMtree的樹表示程序流圖中結(jié)點間的dominate關(guān)系。首結(jié)點是根，每個結(jié)點n只是它的子孫結(jié)點的必經(jīng)結(jié)點，且每個結(jié)點只有一個父結(jié)點，這個父結(jié)點就是從首結(jié)點到n的任何路徑上的、除它自身外的最后一個必經(jīng)結(jié)點。

8、在PL/0語言編譯程序代碼生成的實現(xiàn)中，當(dāng)語法分析到過程體的開始語句時，應(yīng)當(dāng)在目標(biāo)代碼CODE()和名字表TABLE()的相應(yīng)位置（已經(jīng)拉鏈過）回填過程的入口地址，是否只在CODE()中回填就可以？

9、PL/0語言編譯程序的實現(xiàn)中，如何保證標(biāo)識符的作用域？

10、L/0語言編譯程序的實現(xiàn)使用了遞歸子程序法，從PL/0語言也允許過程遞歸調(diào)用從它的實現(xiàn)中可看出，遞歸子程序法對每個過程可能存在直接或間接遞歸調(diào)用，所以對某個過程在退出之前可能又被調(diào)用，因此調(diào)用前的某些信息需要保留，通常在入口時需保留某些信息，出口時需恢復(fù)。由于遞歸過程是遵循先進后出規(guī)律，所以通常開辟先進后出棧來處理。但是，PL/0語言編譯程序的實現(xiàn)是用PASCAL語言編寫的，它是如何實現(xiàn)在過程入口時保留某些信息，出口時恢復(fù)某些信息的？

11、如果用FORTRAN語言編寫PL/0語言的編譯程序會與用PASCAL語言編寫一樣嗎？

12、為什么若Ａ→αB是一個產(chǎn)生式,或A→αBβ是一個產(chǎn)生式，而βT*ε(即ε∈FIRST(β)），則把FOLLOW（A）加至FOLLOW（B）中？

13、為什么算符優(yōu)先分析有可能把不是所給文法的句子也正確歸約，而發(fā)現(xiàn)不了錯誤？

14、在LR分析的項目集中，若含有形如S′→S·項目（S′→S·稱接受項目），則該項目集對應(yīng)的的狀態(tài)稱接受狀態(tài)。為什么在接受狀態(tài)中不可能有移進-接受沖突，而可能有接受-歸約沖突？

15、為什么LALR(1)的狀態(tài)個數(shù)與SLR(1)的相同，它們歸約時都是向前看一個輸入符號，但是LALR(1)比SLR(1)對文法的要求要低？發(fā)現(xiàn)錯誤的時間要早？

16、在LR的一個項目集中可能存在移進項目、歸約項目、待約項目和接受項目4種，所以可能會出現(xiàn)移進-歸約、歸約-歸約或歸約-接受沖突，但為什么與待約項目無關(guān)？

17、用自展方式在PC機上實現(xiàn)C語言的編譯程序，首先把C劃分成真包含的子集C1和C2，然后分3步實現(xiàn)。但是對步驟2和步驟3的雙層結(jié)合T型圖看不明白。

18、給出下述NFAM的五元組表示，并將其確定化。

19、構(gòu)造一個不具有ε-轉(zhuǎn)移的NFAM'，使得L(M')=L(M).

20、對目標(biāo)代碼運行時的存儲空間采用基于過程活動記錄的棧式分配方案，舉例說明象PASCAL這樣的語言如何實現(xiàn)對非局部變量的訪問。

21、文法G[R]:R→R+R|R·R|R*|(R)|a|b|ε

（1）證明文法G[R]生成字母表Σ={a,b}上的所有正規(guī)表達式(用+代替"|"，連接符·沒有省略)

（2）證明此文法是二義的

22、找出下列流圖中的回邊和回邊組成的循環(huán)。編譯中利用流圖完成什么工作？

1、證明對任一左線性文法G，若α∈L（G）則α的第一個符號必定是α的句柄.

證明：

設(shè)G=({S1,S21,……,Sn},{a1,a2,……,am},S0,P)

其中P形為：Si→Sjak或Si→ak,i∈{0,1,2,……,n},k∈{0,1,2,……,m}

設(shè)＝a1al+1……al+n，則的推導(dǎo)樹一定為如下結(jié)構(gòu)：

顯然a1是a1al+1……al+n的句柄。

top↑

2、分別給出與圖1的FA等價的正規(guī)文法G和正規(guī)式r。

解：

正規(guī)文法S→0A|1B

A→1S|1

B→0S|0

正規(guī)式S→(01|10)(01|10)*

top↑

3、給出與如下文法G(S)等價的LL(1)文法G'(S)。

G(s):S→aSb|P

P→bPc|bQc

Q→Qa|a

解：

將G(s)中的左遞歸規(guī)則和會有左公因子的規(guī)則進行改造，得

G'(S)：S→aSb|P

P→bP'

P'→Pc|Qc

Q→aQ'

Q'→aQ'|

驗證LL（1）文法條件：FIRSTFOLLOWSa,bbPbc,bP'b,ac,bQacQ'a,εcG'滿足LL（1）條件。

top↑

4、下列算符文法G[S]是二義的，其定義一般程序設(shè)計語言的if語句和其他（非if）語句，按照else與最近的then匹配（或者說then和else之間的語句是"匹配"的）的原則，給出一個與G[S]等價的OPG文法G'[S]。

G[S]：S→C|a

C→tS|tSeS

解：

G'[S]：S→M|U

M→tMeM|a

U→tS|tMeS

top↑

5、使用圖2的LR分析表分析d;;a是不是如下文法G[S]的句子，按照LR分析算法給出分析步驟

G[S]:（1）S→d;B

（2）B→B;a

（3）B→a

（4）B→ε

解：步驟狀態(tài)棧符號棧余留輸入串下步動作0）0#D；；a#移進S21）02#d；；a#移進S32）023#d；；a#歸約r4（B→ε）3）0234#d；B；a#移進S64）02346#d；Ba#移進S75）023467#d；B；a#歸約r2（B→B;a）6）0234#d；B#歸約r1（S→d;B）7）01#S#acctop↑

6、圖3中的程序，過程調(diào)用序列為Sort→quiksort→partition→exchange若目標(biāo)代碼運行時的環(huán)境采用棧式存儲管理方案，描述此時exchange的AR的display表內(nèi)容。

解：

運行棧的布局：

運行時display表d：d[1]t3d[0]0top↑

7、通?？墒褂靡豢梅Q作DOMtree的樹表示程序流圖中結(jié)點間的dominate關(guān)系。首結(jié)點是根，每個結(jié)點n只是它的子孫結(jié)點的必經(jīng)結(jié)點，且每個結(jié)點只有一個父結(jié)點，這個父結(jié)點就是從首結(jié)點到n的任何路徑上的、除它自身外的最后一個必經(jīng)結(jié)點。

7.1給出圖4流圖的DOMtree；7..2找出流圖中所有回邊及回邊組成的循環(huán)。

解：

7.1D(1)={1}

D(2)={1,2}

D(3)={1,2,3}

D(4)={1,2,4}

D(5)={1,2,4,5}

D(6)={1,2,3,6}

D(7)={1,2,7}

D(8)={1,2,7,8}

Domtree:

7.2回邊：5→4

7→2

循環(huán)：{4,5}

{2,3,4,5,6,7}

G[S]:S→d;B(2)B→B;a(3)B→a(4)B→εActionGotod;a#SB0S211Acc2S3

3r4S5r444S6r15r5r56S7

7r2r2圖2（1）Programsort(input,output)；（2）vara：array[0..10]ofinteger；（3）x：integer；（4）Procedurereadarray；（5）Vari：integer；/*注釋語句1*/（6）begin…a…end{readarray}；（7）Procedureexchange（i,j:integer）；（8）begin（9）x：=a[i];a[i]:=a[j];a[j]:=x（10）end{exchange}；（11）Procedurequicksort(m,n:integer)；（12）vark,v:integer；（13）functionpartition(y,z:integer)：integer；/*注釋語句2*/（14）vari,j：integer；:integer；（15）begin…a…（16）…v…（17）…exchange(i,j);…（18）end{partition}；（19）begin…end{quicksort}；（20）begin…end{sort}．圖3

圖4

top↑

8、在PL/0語言編譯程序代碼生成的實現(xiàn)中，當(dāng)語法分析到過程體的開始語句時，應(yīng)當(dāng)在目標(biāo)代碼CODE()和名字表TABLE()的相應(yīng)位置（已經(jīng)拉鏈過）回填過程的入口地址，是否只在CODE()中回填就可以？

答：從目標(biāo)代碼CODE()執(zhí)行的正確性來說沒有問題，但在TABLE()中也回填過程的入口地址，對以后出現(xiàn)調(diào)用該過程語句時可直接從TABLE()中找到過程的入口地址，可少執(zhí)行一條跳轉(zhuǎn)指令。

top↑

9、PL/0語言編譯程序的實現(xiàn)中，如何保證標(biāo)識符的作用域？

答：PL/0語言對標(biāo)識符的作用域同PASCAL，內(nèi)層可引用包圍它的外層定義的標(biāo)識符（如：變量名，過程名，常量名），實現(xiàn)時tx是BLOCK的實際值參，當(dāng)遞歸進入分程序BLOCK時當(dāng)時的tx為實際值參，退出BLOCK時tx恢復(fù)到調(diào)用前的值。從下面的示意圖（1）中可看出內(nèi)層可引用包圍它的外層定義的標(biāo)識符，反之則不行。

Table表的下標(biāo)指針tx說明：

top↑

10、PL/0語言編譯程序的實現(xiàn)使用了遞歸子程序法，從PL/0語言也允許過程遞歸調(diào)用從它的實現(xiàn)中可看出，遞歸子程序法對每個過程可能存在直接或間接遞歸調(diào)用，所以對某個過程在退出之前可能又被調(diào)用，因此調(diào)用前的某些信息需要保留，通常在入口時需保留某些信息，出口時需恢復(fù)。由于遞歸過程是遵循先進后出規(guī)律，所以通常開辟先進后出棧來處理。但是，PL/0語言編譯程序的實現(xiàn)是用PASCAL語言編寫的，它是如何實現(xiàn)在過程入口時保留某些信息，出口時恢復(fù)某些信息的？

答：因為PASCAL語言本身允許過程遞歸調(diào)用，所以用PASCAL語言編寫遞歸子程序時，對過程入口時保留某些信息，出口時恢復(fù)某些信息的工作由PASCAL語言的編譯程序自動完成。就象用PL/0語言編寫一個含有過程遞歸調(diào)用的程序時，在這個程序中不必再處理信息的保留和恢復(fù)。

top↑

11、如果用FORTRAN語言編寫PL/0語言的編譯程序會與用PASCAL語言編寫一樣嗎？

答：不一樣，因為FORTRAN語言不允許遞歸調(diào)用，它的編譯程序沒有對遞歸調(diào)用時某些信息保留和恢復(fù)進行處理，所以，若用FORTRAN語言采用遞歸子程序法編寫PL/0語言的編譯程序時，則必須要對過程入口和出口時的某些信息進行保留和恢復(fù)處理。

top↑

12、為什么若Ａ→αB是一個產(chǎn)生式,或A→αBβ是一個產(chǎn)生式，而βT*ε(即ε∈FIRST(β)），則把FOLLOW（A）加至FOLLOW（B）中？

答：若有S*…Aa…,a∈VT，由A→αB，則可有S*…αBa…,所以a∈FOLLOW（B）。又由因有A→αBβ，則可有S*…αBβa…，再因有β*ε，所以a∈FOLLOW（B），可見FOLLOW（A）∈FOLLOW（B）。

這個問題非常重要，是計算FOLLOW集出錯的主要原因。

top↑

13、為什么算符優(yōu)先分析有可能把不是所給文法的句子也正確歸約，而發(fā)現(xiàn)不了錯誤？

答：因為算符優(yōu)先分析方法只考慮終結(jié)符之間的優(yōu)先關(guān)系，不考慮非終結(jié)符之間的優(yōu)先關(guān)系，在歸約過程中只要找到可歸約串即最左素短語作為句柄就歸約為某一非終結(jié)符，并不考慮歸約到的那個非終結(jié)符名字是什么，因而算符優(yōu)先歸約不是規(guī)范歸約。這樣也就去掉了單非終結(jié)符的歸約，因為若只有一個非終結(jié)符時無法與句型中該非終結(jié)符的左部及右部的串比較優(yōu)先關(guān)系。歸約時只看產(chǎn)生式文法符號的個數(shù)和終結(jié)符相應(yīng)的位置。

例如，下述文法是一個算符優(yōu)先文法，其產(chǎn)生式為：

S→S;D|D

D→D(T)|H

H→a|(S)

T→T+S|S

用算符優(yōu)先分析法對輸入串(a+a)#進行分析時，可以完全正確地進行歸約，然而(a+a)#卻不是該文法能推導(dǎo)出的句子。

top↑

14、在LR分析的項目集中，若含有形如S′→S·項目（S′→S·稱接受項目），則該項目集對應(yīng)的的狀態(tài)稱接受狀態(tài)。為什么在接受狀態(tài)中不可能有移進-接受沖突，而可能有接受-歸約沖突？

答：因為在接受狀態(tài)中，接受項目S′→S·只能遇到'#'號才能接受，而移進的輸入符號不可能有'#'號，只在輸入串結(jié)束時才可能遇到'#'號。但是在接受狀態(tài)中可能存在接受-歸約沖突，因為LR分析是規(guī)范歸約，可能當(dāng)前輸入符為'#'號，但還存在其它的歸約項目，這時就無法確定歸約還是接受，所以出現(xiàn)接受-歸約沖突。

top↑

15、為什么LALR(1)的狀態(tài)個數(shù)與SLR(1)的相同，它們歸約時都是向前看一個輸入符號，但是LALR(1)比SLR(1)對文法的要求要低？發(fā)現(xiàn)錯誤的時間要早？

答：因為向前看一個輸入符號只對歸約項目起作用，SLR(1)方法僅僅用產(chǎn)生式左部非終結(jié)符FOLLOW集的元素作向前查看的符號，而LALR(1)是由LR(1)項目集規(guī)范族合并同心集的方法構(gòu)造的，LR(1)分析向前查看的是搜索符，對搜索符的計算方法比FOLLOW集更確切，搜索符真包含在FOLLOW集中。

top↑

16、在LR的一個項目集中可能存在移進項目、歸約項目、待約項目和接受項目4種，所以可能會出現(xiàn)移進-歸約、歸約-歸約或歸約-接受沖突，但為什么與待約項目無關(guān)？

答：以構(gòu)造文法G′的LR(0)項目集規(guī)范族為例，其步驟如下：

a)置項目S′→·S為初態(tài)集的核，然后對核求閉包，CLOSURE(｛S′→·S｝）得到初態(tài)的項目集。

b)對初態(tài)集或其它所構(gòu)造的項目集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)=CLOSURE(J)求出新狀態(tài)J的項目集