1、 “賦值句”、“分程序”、“過程”等，它們都是現(xiàn)今程序語言常見的語法范疇。我們也可以說，一個非終結符代表一個一定的語法概念。因此，一個非終結符是一個類（或集合）記號，而不是一個個體記號。例如，“算術表達式”這個非終結符乃代表一定算術式組成的類。因而，也可以說，每個非終結符號表示一定符號串的集合（由終結符號和非終結符號組成的符號串）。開始符號是一個特殊的非終結符號，它代表所定義的語言中我們最終感興趣的語法范疇，這個語法范疇通常稱為“句子”。但在程序語言中，我們最終感興趣的是“程序”這個語法范疇，而其它的語法范疇都只不過是構造“程序”的一塊塊磚石。1語.法2分析樹與二義性前面我們提到過可以用一張圖

2、表示一個句型的推導，這種表示稱為語法分析樹，或簡稱為語法樹。語法樹有助于理解一個句子語法結構的層次。語法樹通常表示成一棵倒立的樹，根在上，枝葉在下。語法樹的根結由開始符號所標記。隨著推導的展開，當某個非終結符被它的某個候選式所替換時，這個非終結符的相應結就產(chǎn)生出下一代新結，候選式中自左至右的每個符號對應一個新結，并用這些符號標記其相應的新結。每個新結和其父結間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結自左至右排列起來就是一個句型。就產(chǎn)生出下一代新結，候選式中自左至右的每個符號對應一個新結，并用這些符號標記其相應的新結。每個新結和其父結間都有一條連線。在一棵語法樹生

3、長過程中的任何時刻，所有那些沒有后代的端末結自左至右排列起來就是一個句型。例如，對于文法，關于的推導例如，對于文法，關于的推導.的2語）法樹如圖2.所2示。圖2.語2法樹這就是說，一棵語法樹表示了一個句型種種可能的（但未必是所有的）不同推導過程，包括最左（最右）推導。這樣的一棵語法樹是這些不同推導過程的共性抽象，是它們的代表。如果我們堅持使用最左（最右）推導，那么，一棵語法樹就完全等價于一個最左（最右）推導，這種等價性包括樹的步步成長和推導的步步展開之間的完全一致性。但是，一個句型是否只對應唯一的一棵語法樹呢?也就是，它是否只有唯一的一個最左（最右）推導呢?不盡然。1形.式3語言鳥瞰前面喬姆斯

4、基把文法分成四種類型，即0型，1型，2型，和3型。0型強于1型，1型強于2型，2型強于3型。這幾類文法的差別在于對產(chǎn)生式施加不同的限制。0型文法：也稱短語文法，其能力相當于圖靈機。任何0型語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。1型文法：也稱上下文有關文法，對非終結符進行替換時務必聯(lián)系上下文，并且一般不允許替換成空串。2型文法：也稱上下文無關文法3型文法：也稱右線性文法，這類文法等價于正規(guī)式，所以也稱正規(guī)文法。只有下面兩種形式的產(chǎn)生式：-a或-a。若則稱文法和是等價的例如：下列兩個文法是等價的因為定義：對文法進行變換，使變換后的文法滿足某種要求并于原文法等價，這種變換成為文

5、法的等價變換。定義：設文法，構造文法U其中，aagU顯然，稱為文法的增廣文法。例：fa經(jīng)等價變換后可得到增廣文法aaa定義：若文法中有產(chǎn)生式a邠|邠則稱該文發(fā)含有左因子G。其中G,P，PPgU)例：文法aa提取左因子該文法變?yōu)椋篏Sa:iESt|SaSaEab定義：若文法中存在推導：。則稱該文法含有左遞歸。若存在產(chǎn)生式a則稱該文法含有直接左遞歸。若存在產(chǎn)生式a,pY,G則稱該文法含有間接左遞歸。其中gapyUN直接左遞歸的消除方法：假設非終結符存在產(chǎn)生式ap刪除左遞歸產(chǎn)生式a引入新的非終結符消除文法中的左遞歸，得：pa間接左遞歸的消除方法：將間接左遞歸轉化為直接左遞歸；消除直接左遞歸；化簡文法

6、，刪除含有從起始符號無法到達的非終結符的產(chǎn)生式最后，作為描述程序語言的上下文無關文法，我們對它有幾點限制。()文法中不含任何下面形式的產(chǎn)生式：-因為這種產(chǎn)生式除了產(chǎn)生二義性外沒有任何用處。()每個非終結符必須有用處。這一方面意味著，必須存在含的句型；也就是，從開始符號出發(fā)，存在推導另一方面意味著，必須存在終結符串使得;也就是，對于不存在永不終結的回路。我們以后所討論的文法均假定滿足上述兩條件。授課題目(教學章、節(jié)或主題)：第三章語法分析自上而下分析課時安排12授課時間第4周第3-6節(jié)第6周第1-6節(jié)第7周第1-2節(jié)教學目的、要求（分掌握、熟悉、了解三個層次）：了解確定的自頂向下分析思想熟悉某些

7、非（）文法到（）文法的等價變換掌握（）文法的判別、確定的自頂向下分析方法教學重點和難點：語法分析器的功能、確定的自頂向下分析思想、（）文法的判別、某些非（）文法到（）文法的等價變換、不確定的自頂向下分析思想、確定的自頂向下分析方法授課類型（請打J）:理論課回討論課口實驗課回練習課回其他口教學方式（請打）:講授團討論口示教口指導0其他口教學資源（請打J）:多媒體回模型口實物口掛圖口音像口其他口討論、思考題、作業(yè)：P81：1,2,4教學內(nèi)容第三章語法分析自上而下分析語1法分析器的功能語法分析器：是這樣的一個程序，它將按文法的產(chǎn)生式，識別輸入符號串是否為一個句子。輸入串是指由單詞符號（文法的終結符）

8、組成的有限序列。語法分析的方法：可大致分為兩類，一類是自下而上分析法，另一類是自上而下分析法。所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號。自上而下分析過程恰好與此相反，它從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式，尋找“匹配”于輸入串的推導。自2上而下分析面臨的問題本節(jié)主要是通過例子使我們認識到，作自上而下分析所遇到的主要困難是語法的左遞歸性使分析陷入無限循環(huán)；回溯的不確定性，要求我們將已經(jīng)完成工作推倒重來，為解決這些問題我們要消除左遞歸和消除回溯。分析法自上而下分析方法不允許文法含有任何左遞歸。為構造不帶回溯的自上而下分析算法，首先要消除文法的左遞歸性，并找

9、出克服回溯的充分必要條件。3左.遞1歸的消除假定關于非終結符的規(guī)則為ap其中，每個都不以開頭，那么我們可以把的規(guī)則改寫成如下的非直接左遞歸形式：a為空字這種形式和原來的形式是等價的，也就是說，從推出的符號串是相同的。3消.除2回溯、提左因子我們首先來看一下在不得回溯的情況下對于文法有什么要求。前面已經(jīng)說過，欲實行自上而下的分析，文法不得含左遞歸。令是一個不含左遞歸的文法，對的所有的非終結符號的每個候選定義它的終結首符集為：特別是，若,則規(guī)定）換句話說是的所有可能推導的開頭終結符或可能的。如果非終結符的所有候選首符集兩兩不相交，即的任何兩個不同的候選和BE么，當要求匹配輸入串時，就能根據(jù)它所面臨

10、的第一個輸入符號，準確地指派某個候選前去執(zhí)行任務。這個候選就是那個終結首符集含的“如何把一個文法改造成任何終結首符集的所有候選首符集兩兩不相交呢？其辦法是提取公共左因子。例如，假定關于的規(guī)則是(其中每個不以開頭)那TOC o 1-5 h z(其中每個不以開頭)那么，可以把這些規(guī)則改寫成：分析條件假定是文法的開始符號，對于任何非終結符我們定義：特別是，若,則規(guī)定也就是說，是所有句型中出現(xiàn)在緊接之后的終結符或者。判斷某給定文法是否為文法其條件為：(1)文法不含左遞歸。()對于文法中每個非終結符的各個產(chǎn)生式的候選首符集兩兩不相交。即，若aaa則：()對文法中每一個終結符，若它存在某個候選首符集包含,

11、則FIRST(A)FLLOW(A)=一個文法若滿足以上條件，則稱該文法為文法遞4歸下降分析程序構造在不含左遞歸和每個非終結符的所有候選終結首符集都兩兩不相交的條件下，可能(僅是可能)構造一個不帶回溯的自上而下分析程序.文法如下：當一個文法滿足條件時，我們就可以為它構造一個不帶回溯的自上而下分析程序，這個分析程序是由一組遞歸過程組成的，每個過程對應文法的一個非終結符。這樣的一個分析程序稱為遞歸下降分析器。預5測分析程序用高級語言的遞歸過程描述遞歸下降分析器只有當具有實現(xiàn)這種過程的編譯系統(tǒng)剛才有實際意義。實現(xiàn)分析的另一種有效方法是使用一張分析表和一個棧進行聯(lián)合控制。我們現(xiàn)在要介紹的預測分析程序就是

12、屬于這種類型的分析器5預.測1分析程序工作過程預測分析程序的總控程序在任何時候都是按棧頂符號和當前的輸入符號行事的。5預.測2分析表的構造為了構造預測分析表，我們需要先構造與文法有關的集合和FOLLOW.消除左遞歸和提取左因子將有助于獲得無多重定義的分析表。可以證明，一個文法的預測分析表不含多重定義入口，當且僅當該文法為的。分析中的錯誤處理我們以預測分析為例。在預測分析過程中，出現(xiàn)了下列兩種情況，則說明遇到了語法錯誤。（1棧）頂?shù)慕K結符與當前的輸入符號不匹配。非終結符處于棧頂，面臨的輸入符號為，但分析表中的，為空。發(fā)現(xiàn)錯誤后，要盡快地從錯誤中恢復過來，使分析能繼續(xù)進行下去?；镜淖龇ň褪翘^輸

13、入串中的一些符號直至遇到“同步符號”為止。這種做法的效果有賴于同步符號集的選擇。我們可以從以下幾個方面考慮同步符號集的選擇。把中的所有符號放人非終結符的同步符號集。如果我們跳讀一些輸入符號直到出現(xiàn)中的符號，把從棧中彈出，這樣就可能使分析繼續(xù)下去。對于非終結符來說，只用作為它的同步符號集是不夠的。例如，如果分號作為語句的結束符語言中就是這樣的，那么作為語句開頭的關鍵字就可能不在產(chǎn)生表達式的非終結符的集中。這樣，在一個賦值語句后少一個分號就可能導致作為下一語句開頭的關鍵字被跳過。如果把中的符號加入非終結符的同步符號集，那么，當中的一個符號在輸入中出現(xiàn)時，可以根據(jù)恢復語法分析。（4如）果一個非終結符

14、產(chǎn)生空串，那么，推導6的產(chǎn)生式可以作為缺省的情況，這樣做可以推遲某些錯誤檢查，但不能導致放棄一個錯誤。這種方法減少在錯誤恢復期間必須考慮的非終結符數(shù)。（5如）果不能匹配棧頂?shù)慕K結符號，一種簡單的想法是彈出棧頂?shù)倪@個終結符號，并發(fā)出一條信息，說明已經(jīng)插入這個終結符，繼續(xù)進行語法分析。結果，這種方法使一個單詞符號的同步符號集包含所有其它單詞符號。授課題目（教學章、節(jié)或主題）：課時安排16第三章語法分析自下而上分析授課時間第7周第3-4節(jié)第8周第1-4節(jié)第9周第1-4節(jié)第10周第1-4節(jié)第11周第1-2節(jié)教學目的、要求（分掌握、熟悉、了解三個層次）：熟悉自下而上分析思想了解算符優(yōu)先分析法掌握分析法教

15、學重點和難點：自下而上分析思想、算符優(yōu)先分析法、分析法授課類型（請打J）:理論課回討論課口實驗課回練習課回其他口教學方式（請打）:講授團討論口不教口指導回其他口教學資源（請打J）:多媒體團模型口實物口掛圖口音像口其他口討論、思考題、作業(yè)：P133：1,2,3,5教學內(nèi)容第三章語法分析程序-自-下而上分析所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根結。5.自1下而上分析基本問題我們首先討論自下而上分析法的基本思想和基本概念3.1歸.約1“移進-歸-約-”：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進到棧

16、里，當棧頂形成某個產(chǎn)生式的一個候選式時，即把棧頂?shù)倪@一部分替換（歸約為）該產(chǎn)生式的左部符號。我們可用句柄來刻畫移進歸約過程的“可歸約串?！?.1規(guī).范2歸約簡述規(guī)范規(guī)約是關于a的一個最右推導的逆過程。因此，規(guī)范規(guī)約也稱最左規(guī)約。最右推導常被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型。如果文法是無二義的，那么規(guī)范推導的逆過程必是規(guī)范規(guī)約。句柄：令是一個文法，是文法的開始符號，假定ag是文法的一個句型，如果有aG且+B則稱B是句型。於相對于非終結符的短語。特別是，如果有B則稱B是句型aBG相對于規(guī)則的直接短語。一個句型的最左直接短語稱為該句型的句柄。1符.號3棧的使用與語法樹的表示在形式語言中

17、，最右推導常被稱為規(guī)范推導。由規(guī)范推導所得的句型稱為規(guī)范句型。如果文法是無二義的，那么，規(guī)范推導最右推導的逆過程必是規(guī)范歸約（最左歸約）。請注意句柄的“最左”特征，這一點對于移進歸約來說是重要的。因為，句柄的“最左性”和符號棧的棧頂兩者是相關的。對于規(guī)范句型來說，句柄的后面不會出現(xiàn)非終結符號即，句柄的后面只能出現(xiàn)終結符）基于這一點，我們可用句柄來刻畫移進歸約過程的“可歸約串”。因此，規(guī)范歸約的實質(zhì)是，在移進過程中，當發(fā)現(xiàn)棧頂呈現(xiàn)句柄時就用相應產(chǎn)生式的左部符號進行替換。算2符優(yōu)先分析法現(xiàn)在，我們來討論一種簡單直觀、廣為使用的自下而上分析法，叫做算符優(yōu)先分析法。這種方法特別有利于表達式分析，宜于手

18、工實現(xiàn)。算符優(yōu)先分析過程是自下而上的歸約過程，但這種歸約未必是嚴格的最左歸約。也就是說，算符優(yōu)先分析法不是一種規(guī)范歸約法。所謂算符優(yōu)先分析就是定義算符之間（確切地說，終結符之間）的某種優(yōu)先關系，借助于這種優(yōu)先關系尋找“可歸約串”和進行歸約。我們用下面方法表示任何兩個可能相繼出現(xiàn)的終結符和它們之間可能插有一個非終結符）的優(yōu)先關系。這種關系有三種：的優(yōu)先性低于二的優(yōu)先性等于的優(yōu)先性高于注意，這三個關系不同于數(shù)學中的；二和。例如，,并不一定意味著a2算.符1優(yōu)先分析文法及其優(yōu)先表構造一個文法，如果它的任何產(chǎn)生式的右部都不含兩個相繼（并列）的非終結符，即不含如下形式的產(chǎn)生式右部：則我們稱該文法為算符文

19、法。在后面的定義中，a代表任意終結符；、代表任意非終結符；代表有終結符和非終結符組成的任意序列，包括空字。假定是一個不含產(chǎn)生式的算符文法。對于任何一對終結符、，我們說:（）=當且僅當文法中含有形如或的產(chǎn)生式當且僅當中含有形如的產(chǎn)生式，而或當且僅當中含有形如的產(chǎn)生式，而或如果一個文法中的任何終結符對（）至多只滿足下述三關系之一：則稱是一個算符優(yōu)先文法。應掌握算符優(yōu)先表的構造方法。通過檢查的每個產(chǎn)生式的每個候選式，可以找出滿足的終結符對。為了找出所有滿足關系和的終結符對，我們需要對的每個非終結符構TOC o 1-5 h z造兩個集合和或而或而有了這兩個集合后，就可以通過檢查每個產(chǎn)生式的候選式確定滿

20、足關系和的所有終結符對。例如：假定有個產(chǎn)生式的一個候選式為那末，對任何我們有。類似地，假定有產(chǎn)生式的一個候選式為那末，對任何我們有我們首先討論構造集合的算法。按定義，我們可用下面兩條規(guī)則來構造集合若有產(chǎn)生式或貝I若,且有產(chǎn)生式，則同樣我們可以構造的算法。在我們有了每個非終結符的和之后我們就能夠造文法的優(yōu)先表。其算法如下：每一條產(chǎn)生式FORi:=1TOn-1DOBEGIN和均為終結符置且和都為終結符，而為非終結符，則置為終結符而為非終結符中的每個為非終結符而為終結符中的每個置至此我們完成了從文法構造優(yōu)先表的算法。3.2算.符2優(yōu)先分析算法在正確的情況下，算法工作完畢時，符號棧應呈現(xiàn)：。注意，在上

21、述算法中，我們并沒有指出應把所找到的最左素短語歸約到哪一個非終結符號。是指那樣一個產(chǎn)生式的左部符號，此產(chǎn)生式的右部和+為構成如下一一對應關系：自左至右，終結符對終結符，非終結符對非終結符，而且對應的終結符相同。由于非終結符對歸約沒有影響，因此，非終結符根本可以不進符號棧。在算符優(yōu)先歸約過程中，我們無法用那些右部僅含一個非終符的產(chǎn)生式（稱為單非產(chǎn)生式，如進行歸約。3.2優(yōu).先3函數(shù)如果優(yōu)先函數(shù)存在，那么，從優(yōu)先表構造優(yōu)先函數(shù)的一個簡單方法是：對于每個終結符包括令其對應兩個符號和，畫一張以所有符號和為結點的方向圖，如果，那么，就從畫一箭弧至；如果，就畫一條從到的箭弧。（2對）每個結點都賦予一個數(shù)，

22、此數(shù)等于從該結點出發(fā)所能到達結點（包括出發(fā)結點自身在內(nèi)的個數(shù)。賦給的數(shù)作為，賦給的數(shù)作為。檢查所構造出來的函數(shù)和，看它們同原來的關系表是否有矛盾。如果沒有矛盾，則和就是所要的優(yōu)先函數(shù)。如果有矛盾，那么，就不存在優(yōu)先函數(shù)?，F(xiàn)在必須證明：若，則二；若，則；若，則在實際實現(xiàn)算符優(yōu)先分析算法時，一般不用上述這樣的優(yōu)先表，而是用兩個優(yōu)先函數(shù)和相對應，函數(shù)稱為人棧優(yōu)先函數(shù)，稱為比較優(yōu)先函數(shù)。使用優(yōu)先函數(shù)有兩方面的優(yōu)點：便于作較運算，并且節(jié)省存儲空間，因為優(yōu)先關系表占用的存儲量比較大。其缺點是，原先不存在優(yōu)先關系的兩個終結符，由于與自然數(shù)相對應，變成可比較的了。因而，可能會掩蓋輸入串的某些錯誤。但是，我們可

23、以通過檢查棧頂符號和輸入符號的具體內(nèi)容來發(fā)現(xiàn)那些原先不可比較的情形。3.2算.符4優(yōu)先分析中的出錯處理使用算符優(yōu)先分析法時，可在兩種情況下，發(fā)現(xiàn)語法錯誤：（1若）在棧頂終結符號與下一輸人符號之間不存在任何優(yōu)先關系；（2若）找到某一“句柄”（此處“句柄”指素短語），但不存在任一產(chǎn)生式，其右部為此“句柄?！贬槍ι鲜銮闆r，處理錯誤的子程序也可分成幾類。分析法分析器的核心部分是一張分析表。這張分析表包括兩部分，一是“動作”表，另一是“狀態(tài)轉換”表。它們都是二維數(shù)組。，規(guī)定了當狀態(tài)面臨輸入符號時應采取什么動作。，規(guī)定了狀態(tài)面對文法符號終結符或非終結符時下一狀態(tài)是什么。顯然，定義了一個以文法符號為字母表的

24、A每一項，所規(guī)定的動作不外是下述四種可能之一。移進把，的下一狀態(tài)那，和輸入符號推進棧，下一輸入符號變成現(xiàn)行輸入符號。歸約指用某一產(chǎn)生式進行歸約。假若的長度為，歸約的動作是，去除棧頂?shù)膫€項，使狀態(tài)-變成棧頂狀態(tài)，然后把-,的下一狀態(tài)二-,和文法符號推進棧。歸約動作不改變現(xiàn)行輸入符號。執(zhí)行歸約動作意味著-+已呈現(xiàn)于棧頂而且是一個相對于的句柄。（3接的受宣布分析成功，停止分析器的工作。（4報的錯發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序。分析器的總控程序本身的工作是非常簡單的。它的任何一步只需按棧頂狀態(tài)和現(xiàn)行輸入符號執(zhí)行，所規(guī)定的動作。不管什么分析表，總控程序都是一樣地工作。一個分析器的工作過程可看成是棧

25、里的狀態(tài)序列、已歸約串和輸入串所構成的三元式的變化過程。棧的每一項內(nèi)容包括狀態(tài)和文法符號兩部分。，為分輸入帶析開始前預先放在棧里的初始狀態(tài)和句子括號。棧頂狀態(tài)為，符號串一個分析器實質(zhì)上是一個帶先進后出存儲器（棧）的確定有限狀態(tài)自動機。我們將把“歷史”和“展望”材料綜合地抽象成某些“狀態(tài)”（）項目集族和（）分析表的構造字的前綴是指字的任意首部。所謂活前綴是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。之所以稱為活前綴，是因為在右邊添一些終結符之后，就可以使它成為一個規(guī)范句型。文法的每一個產(chǎn)生式右部添加一個圓點就稱為的一個項目。構成識別一個文法活前綴的的項目集（狀態(tài)）的全體稱為這個文法的項

26、目集規(guī)范族為了使接受狀態(tài)易于識別，我們總是把文法進行拓廣。假定文法是一個以為開始符號的文法，我們構造一個它包含了整個，但它引進了一個不出現(xiàn)在中的非終結符，并加進了一個新產(chǎn)生式，而這個是的開始符號。那么，我們稱是的拓廣文法。這樣，便會產(chǎn)生一個僅含項目的狀態(tài)，這就是唯一的接受態(tài)。假定一個文法的拓廣文法的話前綴識別自動機中的每個狀態(tài)（項目集）不存在下述情況：（1）既含移進項目又含規(guī)約項目；（2）或者含有多個規(guī)約項目，則稱是一個文法。由于假定文法規(guī)范族的每一個項目集不含沖突項目，因此，按上述方法構造的分析表的每一個入口都是唯一的（即不含多重定義）。我們稱如此構造的分析表是一張表）使用表的分析器叫做一個

27、分析器。分析表的構造是的一種改進，它在歸約時除了考慮歷史情況之外還考慮了一點現(xiàn)實。上面所說的文法是一類非常簡單的文法。這種文法的話前綴識別自動機的每一個狀態(tài)（項目集）都不含沖突性的項目。如果項目集中某個項目存在有沖突的項目集，可以根據(jù)讀頭下符號的不同來消除沖突。一般而言，對于任何形如項目集，若則可以根據(jù)當前讀頭下符號來則可以根據(jù)當前讀頭下符號來消除沖突。即在構造分析表的算法中做一些改變：）若當前輸入符做移進；）若當前輸入符，按產(chǎn)生式歸約；）若當前輸入符，按產(chǎn)生式歸約；）其他，報錯。規(guī)范分析表的構造）其他，報錯。規(guī)范分析表的構造在構造分析表的方法中，若項目集中含有，那么在狀態(tài)時，只要面臨輸入符號

28、，就確定采用產(chǎn)生式進行歸約。但是，在某種情況下，當狀態(tài)呈現(xiàn)于棧頂時，棧里的符號串所構成的活前綴未必允許把歸約為。因為可能沒有一個規(guī)范句型含有前綴a因此此時用產(chǎn)生式進行歸約未必有效。對策：給每個項目添加展望信息，即：添加句柄之后可能跟的終結符，因為這些終結符確實是規(guī)范句型中跟在句柄之后的。這就是的方法。分析表的構造現(xiàn)在來討論構造分析表的方法。這本質(zhì)上是一種折衷方法。分析表比規(guī)范分析表要小得多，能力也差一點，但它卻能對付一些所不能對付的情形。對于同一個文法，分析表和分析表永遠具有相同數(shù)目的狀態(tài)。對于一類語言來說，一般要用幾百個狀態(tài)，但若用規(guī)范分析表，同一類語言，卻要用幾千個狀態(tài)。因此，用或要經(jīng)濟得

29、多。3.3二.義6文法的應用任何二義文法決不是一個文法，因而也不是或文法。這是一條定理。但是，某些二義文法是非常有用的。本節(jié)將討論如何使用分析法的基本思想，憑借一些其它的條件，來分析二義文法所定義的語言。例如，若用下面的文法來描述含有、的算術表達式：采用附加條件之后，發(fā)生沖突的表元素就只留下了一種操作；在上面的規(guī)則中，我們是認為“*”的優(yōu)先級大于“+”，若現(xiàn)在規(guī)則發(fā)生變化，認為“+”的優(yōu)先級大于“*”，那么對它的實現(xiàn)根本不需修改文法，只要處理沖突時改變一下就行。用這種方法改變算符的優(yōu)先級是非常方便的。分析中的出錯處理在分析過程中，當我們處在這樣一種狀態(tài)下，即輸入符號既不能移入棧頂，棧內(nèi)元素又不

30、能歸約時，就意味著發(fā)現(xiàn)語法錯誤。發(fā)現(xiàn)錯誤后，便進入相應的出錯處理子程序。3.語4法分析器的自動生成工具YACC是一個編譯程序的編譯程序，借助它可以構造編譯程序。輸入用戶提供的語言的語法描述規(guī)格說明，基于語法分析的原理，自動構造一個該語言的語法分析器，同時，它還能根據(jù)規(guī)格說明中給出的語義子程序建立規(guī)定的翻譯。授課題目（教學章、節(jié)或主題）：第四章語法制導翻譯和中間代碼產(chǎn)生課時安排8授課時間第11周第3、4節(jié)第12周第1-4節(jié)第13周第1、2節(jié)教學目的、要求（分掌握、熟悉、了解三個層次）：理解屬性文法的定義，語法制導翻譯方法熟悉中間代碼的形式掌握中間代碼形式變換掌握簡單賦值語句的翻譯、布爾表達式的翻

31、譯、控制語句的翻譯教學重點和難點：、中間代碼的形式、簡單賦值語句的翻譯、布爾表達式的翻譯、控制語句的翻譯授課類型（請打J）:理論課回討論課口實驗課回練習課回其他口教學方式（請打）:講授團討論口不教口指導回其他口教學資源（請打J）:多媒體團模型口實物口掛圖口音像口其他口討論、思考題、作業(yè)：P217：1,4,7,9第四章語法制導翻譯和中間代碼產(chǎn)生4.屬1性文法和語法制導翻譯屬性文法是在上下文無關文法的基礎上為每個文法符號（終結符或非終結符）配備若干個相關的“值”（稱為屬性）。這些屬性代表與文法符號相關的信息，例如它的類型、值、代碼序列、符號表內(nèi)容等等。屬性和變量一樣，可以進行計算和傳遞。屬性一般分

32、為兩類：綜合屬性和繼承屬性。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。屬性加工的過程即是語義處理的過程，對于文法的每一個產(chǎn)生式都配備了一組屬性的計算規(guī)則，則稱為語義規(guī)則。在一個屬性文法中對應于每個產(chǎn)生式都有一套與之相關聯(lián)的語義規(guī)則，每條語義規(guī)則的形式為：這里是一個函數(shù)，而且或者（）是的一個綜合屬性并且是產(chǎn)生式右邊文法符號的屬性；或者（）是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且，是或產(chǎn)生式右邊任何文法符號的屬性在這兩種情況下，我們都說屬性依賴于屬性，在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。因此，通常使用自底向上的方法在每一個結點處使用語義

33、規(guī)則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱屬性文法。其值為根的第一個子結點的值在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定。用繼承屬性來表示程序語言結構中的上下文依賴關系很方便。如果在一棵語法樹中一個結點的屬性依賴于屬性，那么這個結點處計算的屬性規(guī)則必須在確定的語義規(guī)則之后使用。在一顆語法樹中的結點的繼承屬性和綜合屬性之間的相互依賴關系可以用稱作依賴圖的一個有向圖來描述。在為一棵語法樹構造依賴圖以前，我們?yōu)槊恳粋€包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性，這樣把每一個語義規(guī)則都寫成的形式。依賴圖中為每一個屬性設置一個結點，如果屬性依賴屬性，則從屬性的結點有一

34、條有向邊連到屬性的結點。這里要掌握依賴圖的畫法。例如，屬性A.a:=f(X.x,Y.y)對應于產(chǎn)生式的語義規(guī)則這條語義規(guī)則確定了依賴于屬性和的綜合屬性.如果在語法樹中應用這個產(chǎn)生式，那么在依賴圖中會有三個結點和。由于依賴，所以有一條有向邊從到由于也依賴于，所以還有一條有向邊從連到如果與產(chǎn)生式對應的語義規(guī)則還有：X.i:=g(A.a,Y.y)那么，圖中還應有兩條有向邊，一條從連到，另一條從連到因為依賴于和屬性文法的自下而上計算這一節(jié)我們考慮這樣一類屬性文法：屬性文法，它只含有綜合屬性。相應屬性文法的翻譯器很容易建立。下面我們討論分析棧中的綜合屬性。在自底向上的分析法中。我們使用一個棧來存放已經(jīng)分

35、析過的子樹的信息?，F(xiàn)在我們可以在分析棧中使用一個附域來存放綜合屬性值。圖4.表9示的是一個帶有一個屬性值空間的分析棧的例子。屬性文法和自頂向下翻譯一個屬性文法稱為屬性文法：如果對于每個產(chǎn)生式其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是的一個繼承屬性且這個繼承屬性僅依賴于：()產(chǎn)生式的左邊符號的屬性()的繼承屬性。L屬性文法允許通過一次遍歷就計算出所有屬性值。中2間語言我們將介紹其他幾種常見的中間語言形式：后綴式（逆波蘭式）三地址代碼（四元式，三元式，間接三元式），圖表示。2后.綴1式后綴式表示法是波蘭邏輯學家盧卡西維奇發(fā)明的一種表示表達式的方法，因此又稱逆波蘭表示法。表達式的后綴形式可以如

36、下定義：如果是一個變量或常量，則的后綴式是自身。如果是形式的表達式，這里是任何二元操作符，則的后綴式為，這里和分別為和的后綴式。這種表示法用不著使用括號。根據(jù)運算量和算符出現(xiàn)的先后位置，以及每個算符的目數(shù)，就完全決定了一個表達式的分解。例如所代表的表達式是b只要我們知道每個算符的目數(shù)，對于后綴式，不論從哪一端進行掃描，都能對它正確進行唯一分解。把一般表達式翻譯為后綴式是很容易的。2圖.表2示法這里的圖表示法包括（無循環(huán)有向圖）與抽象語法樹。2三.地3址代碼三地址代碼可以看成是抽象語法樹或的一種線性表示。之所以稱為三地址代碼是因為每條語句通常包含三個地址，兩個用來表示操作數(shù)，一個用來存放結果。對

37、于后面給出的三地址代碼中，用戶定義的名字在實際實現(xiàn)時將由指向符號表中的相應名字入口的指針所代替。三地址語句類似于匯編語言代碼。語句可以帶有符號標號，而且存在各種控制流語句。符號標號代表存放中間代碼的數(shù)組中三地址代碼語句的下標。說3明語句當我們考查一個過程或分程序的一系列說明語句時，便可為局部于該過程的名字分配存儲空間。對每個局部名字，我們都將在符號表中建立相應的表項，并填入有關的信息如類型、在存儲器中的相對地址等。相對地址是指對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基址的一個偏移量。有關活動記錄我們將在第九章詳細介紹。當產(chǎn)生中間代碼地址時，對目標機一些情況做到心中有數(shù)是有好處的。例如，假定在一個

38、以字節(jié)編址的目標機上，整數(shù)必須存放在4的倍數(shù)的地址單元，那么，計算地址時就應以4的倍數(shù)增加。3過.程1中的說明語句在、及等語言的語法中，允許在一個過程中的所有說明語句作為一個組來處理，把它們安排在一個數(shù)據(jù)區(qū)中。從而我們需要一個全程變量如來跟蹤下一個可用的相對地址的位置。在關于說明語句的翻譯模式中，非終結符號產(chǎn)生一系列形如：的說明語句。在處理第一條說明語句之前，先置為，以后每次遇到一個新的名字，便將該名字填入符號表中并置相對地址為當前之值，然后使加上該名字所表示的數(shù)據(jù)對象的域?qū)?。過程，用來把名字填入到符號表中，并給出此名字的類型及在過程數(shù)據(jù)區(qū)中的相對地址f非終結符號有兩個綜合屬性.和.，分別表示

39、名字的類型和名字的域?qū)挘丛擃愋兔炙加玫拇鎯卧獋€數(shù)）。假定整數(shù)類型域?qū)挒?；實數(shù)域?qū)挒?；一個數(shù)組的域?qū)捒梢酝ㄟ^把數(shù)組元素數(shù)目與一個元素的域?qū)捪喑双@得；每個指針類型的域?qū)捈俣橐?增加。3保.留2作用域信息過程，和的符號表有指針指向其外圍過程的符號表。另一過程是在中被說明，因此它的符號表有指針指向的符號表。在下面的語義規(guī)則中用到如下操作：創(chuàng)建一張新符號表，并返回指向新表的一個指針。參數(shù)指向一張先前創(chuàng)建的符號表，譬如剛好包含嵌入過程的外圍過程符號表。指針之值放在新符號表表頭，表頭中還可存放一些其它信息如過程嵌套深度等。我們也可以按過程被說明的順序?qū)^程編號，并把這一編號填入表頭。，在指針指

40、示的符號表中為名字建立一個新項，并把類型、相對地址填入到該項中。，在指針指示的符號表表頭中記錄下該表中所有名字占用的總寬度。，在指針指示的符號表中為名字為的過程建立一個新項。參數(shù)指向過程的符號表。3記.錄3中的域名當遇到保留字時，與標記非終結符號相應的語義動作為記錄中的各域名創(chuàng)建一張新的記錄符號表。把指向該表的指針壓入棧中，并把相對地址壓入棧中。產(chǎn)生式:的語義動作是將域名的有關信息填入此記錄的符號表中。當記錄的所有域名都被檢查過之后，在的棧頂將存放著記錄之內(nèi)的所有數(shù)據(jù)對象的總域?qū)?。文法中之后的語義動作是將的棧頂?shù)目傆驅(qū)捵鳛榫C合屬性.的值。類型.通過對指向本記錄符號表的指針施用類型構造符而得到。

41、在下一節(jié)該指針將用來從恢復記錄中各域的域名、類型及域?qū)挼?。有關類型構造符和類型表達式概念將在47節(jié)介紹。4.賦4值語句的翻譯在本節(jié)中賦值語句中的表達式的類型可以是整型、實型、數(shù)組和記錄。作為翻譯賦值語句為三地址代碼的一個部分，我們將討論如何在符號表中查找名字及如何存取數(shù)組和記錄的元素。課本給出了把簡單算術表達式及賦值語句翻譯為三地址代碼的翻譯模式。該翻譯模式中說明了如何查找符號表的入口。屬性表示所代表的名字本身。過程檢查是否在符號表中存在此名字的入口。如果有,則返回一個指向該表項的指針，否則，返回表示沒找到。在相關的語義動作中，調(diào)用過程將生成的三地址語句發(fā)送到輸出文件中，我們可以重新解釋操作，

42、若采用最近嵌套作用域規(guī)則查找非局部名字，如語言中的那樣，此時前面的翻譯模式仍是可用的。4.4數(shù).組2元素的引用現(xiàn)在討論包括數(shù)組元素的表達式和賦值語句的翻譯問題。若數(shù)組的元素存放在一片連續(xù)單元里，則可以較容易的訪問數(shù)組的每個元素。假定數(shù)組的每個元素的寬度為，則一維數(shù)組這個元素的起始地址為：法（）其中為數(shù)組下標的下界，并且是分配給數(shù)組的相對地址，即為的第一個元素的相對地址。的第一個元素的相對地址。式可以整理為：其中：是隨數(shù)組下標變量而變化的部分（）是在數(shù)組中不變化的常數(shù)記為對于多維數(shù)組中二維的情況尤其應注意：若二維數(shù)組按行存放，則可用如下公式計算的相對地址：其中，1分別為1的下界；是可取值得個數(shù)。

43、即若為的上界，則假定是編譯時唯一尚未知道的值，我們可以重寫上述表達式為：（）后一項子表達式（）的值是可以在編譯時確定的為常數(shù)。前一子項隨而改變是一個變數(shù)。特別是當，時有：應該牢記。要生成數(shù)組的引用代碼，其主要問題是把常數(shù)和變數(shù)的計算與數(shù)組引用的文法聯(lián)系起來。如果在圖的文法中出現(xiàn)的地方也允許下面產(chǎn)生式中的出現(xiàn)，則可把數(shù)組元素引用加入到賦值語句中。ft為語句處理上的方便改寫為：LtElist|idElisttElist,E|idE即把數(shù)組的名字與最左下標表達式相聯(lián)系，而不是在形成時與相聯(lián)系。其目的是使我們在整個下標表達式串的翻譯過程中隨時都知道符號表中相應于數(shù)組名字的全部信息。對于非終結符號引進綜

44、合屬性，用來紀錄指向符號表中相應數(shù)組名字表項的指針。我們還利用來紀錄中的下表表達式的個數(shù)，即維數(shù)。函數(shù)返回，即由所指示的數(shù)組的第維的長度。最后，表示臨時變量，用來臨時存放由中的下標表達式計算出來的值。一個可以產(chǎn)生一個維數(shù)組引用的前維下標，并將生成計算下面式子的三地址代碼。（利用如下的遞歸公式進行計算：e1=i1,em=em-1*nm+im于是當時將乘以元素的寬度便可計算出（）的第一個子項。描述的左值（基地值）用兩個屬性和如果僅為一個簡單名字，就為指向符號表中相應此名字表項的指針，而為，表示這個左只是一個簡單名字而非數(shù)組的引用。4.4記.錄3中域的作用編譯器必須將記錄中的域的類型和相對地址保持下

45、來。一般說來，把這些信息保存在相應的域名的符號表表項之中。這樣做的好處是可以把用在符號表中查找名字的程序同樣用來查找域名。在此意義下，利用上一節(jié)圖49中的語義動作可為每一個記錄類型建立一張單獨的符號表。如果是一個指向某個記錄類型的指針，把類型構造符施于該指針，返回所形成的類型作為屬性的值。是一個指向某個記錄的指針，這個記錄有一個類型為算術型的域名。如果類型像圖.和圖.一樣構造，則的類型可以由類型表達式給出。于是的類型是，可由此先取出來。也就是說域名將可以在所指向的符號表中查找。4.布5爾表達式的翻譯在程序設計語言中，布爾表達式有兩個基本作用：一個使用作計算邏輯值；另一個是用作控制流語句如n和等

46、之中的條件表達式。布爾表達式是用布爾運算符號（、）作用到布爾變量或關系表達式上而組成的。關系表達式形式如其中和是算術表達式，為關系運算符（豐）。把解釋成把解釋成把解釋成上述這兩種計算法對于不包含布爾函數(shù)調(diào)用的式子是沒有什么差別的。但是，假設一個布爾式中含有布爾函數(shù)調(diào)用，并且這種函數(shù)調(diào)用引起副作用（指對全局量的賦值）。那么，上述兩種計算法未必是等價的。有些程序語言規(guī)定，函數(shù)過程調(diào)用應不影響這個調(diào)用所處環(huán)境的計值?；蛘哒f，函數(shù)過程的工作不許產(chǎn)生副作用。在這種規(guī)定下，我們可任選上述的一種方法。下面我們將分別用這兩種方法來討論如何把布爾表達式翻譯成地址代碼。從表達式各部分的值計算出整個表達式的值。數(shù).

47、值1表示法首先考慮用1表示真，0表示假來實現(xiàn)布爾表達式的翻譯。一個形如的關系表達式可等價的寫成并將它翻譯成如下三地址語句序列：4.5作.為2條件控制的布爾式翻譯出現(xiàn)在條件語句：ifEthenS1elseS2（4.10）中的布爾表達式，它的作用僅在于控制對和的選擇。只要能完成這一使命，的值就無需最終保留在某個臨時單元中。因此，作為轉移條件的布爾式，我們可以賦予它兩種出口。一個是真出口，出向；一個是假出口，出向。于是語句（）可翻譯成如圖所示的形式。圖-語句的代碼結構對布爾表達式進行翻譯的語義規(guī)則的最容易方法是經(jīng)過兩遍掃描。首先，為給定的輸入串構造一棵語法樹；然后，對語法樹進行深度優(yōu)先遍歷，進行語義

48、規(guī)則中規(guī)定的翻譯。通過一遍掃描來產(chǎn)生布爾表達式和控制流語句的代碼的主要問題在于，當生成某些轉移語句時我們可能還不知道該語句將要轉移到的標號究竟是什么。為了解決這個問題，我們可以在生成形式分支的跳轉指令時暫時不確定跳轉目標，而建立一個鏈表，把轉向這個目標的跳轉指令的標號鍵入這個鏈表。一旦目標確定之后再把它填入有關的跳轉指令中。這種技術稱為回填。按照這個思想，我們?yōu)榉墙K結符賦予兩個綜合屬性.和.s它們分別記錄布爾表達式所應的四元式中需回填“真、“假”出口的四元式的標號所構成的鏈表。具體實現(xiàn)時，我們可以借助于需要回填的跳轉四元式的第四區(qū)段來構造這種鏈。4.控6制語句的翻譯4.6控.制1流語句我們考慮

49、文法：f其中布爾表達式。與上一節(jié)一樣，我們先討論對這些語句進行翻譯的一般語義規(guī)則。然后討論如何通過一遍掃描產(chǎn)生上述語句的代碼，給出相應的翻譯模式。關于這三條語句的代碼結構如圖所示。條件語句的語義規(guī)則允許控制從的代碼之內(nèi)轉移到緊接之后的那條三地址指令。但是，有時候此條緊接之后的指令是一條無條件轉移指令，它轉移到標號為的指令。通過使用繼承屬性可以避免上述連續(xù)轉移的發(fā)生，而從之內(nèi)直接轉移到標號為的指令。之值是一個標號，他指出繼的代碼之后時，我們建將被執(zhí)行的第一條三地址指令。在翻譯語句f時，我們建立了一個新的標號，并且用它來標識的代碼的第一條指令，如圖（）所示。表給出了一個屬性文法。在的代碼中將有這樣

50、的轉移指令：若為真則轉移到并且若為假則轉移到因為我們置為圖4.17控制語句的代碼結構在翻譯語句f時，布爾表達式的代碼中有這樣的轉移指令：若為真則轉移到的第一條指令，若為假則轉移到的得一條指令。如圖（）所示。圖（）語句f的結構圖如（）與上邊兩個語句相似，不再重述。使用回填技術通過一遍掃描翻譯控制流語句的翻譯模式應該掌握。標號與語句很多語句都保留了標號和語句作為最基本的程序設計語言成分。一個帶標號的語句形式是：他。當這種語句被處理之后，標號稱為“定義了”的。也就是在符號表中標號的“地址”欄將登記上語句的第一個四元式的地址編號）如果是一個向后轉移的語句，那么，當編譯程序碰到這個語句時，必是已定義了的

51、。通過對查找符號表獲得它的定義地址，編譯程序可立即產(chǎn)生出相應于這個的四元式，一，一，。如果是一個向前轉移的語句，也就是說標號尚未定義，那么，若是第一次出現(xiàn)，則把它填進符號表中并標志上“未定義”由于尚未定義，對我們只能產(chǎn)生一個不完全的四元式，一，一，一，它的轉移目標須待定義時再回填進去。在這種情況下，必須把所有那些以為轉移目標的四元式的地址全都記錄下來，以便定義時就可對這些四元式進行回填。語句的翻譯4.7過程調(diào)用的處理過程是程序設計語言中最常用的一種結構。我們這一節(jié)所討論的過程也包括函數(shù)，實際上函數(shù)可以看作是返回結果值的過程。我們考慮過程調(diào)用文法如下：（）f其傳地址的翻譯模式應掌握。4.8類型檢

52、查授課題目（教學章、節(jié)或主題）：第八章運行時存儲空間組織課時安排6授課時間第13周第3、4節(jié)第14周第1-4節(jié)教學目的、要求（分掌握、熟悉、了解三個層次）：熟悉棧式存儲分配的實現(xiàn)掌握參數(shù)的傳遞教學重點和難點：參數(shù)的傳遞、棧式存儲分配的實現(xiàn)授課類型（請打J）:理論課回討論課口實驗課口練習課回其他口教學方式（請打）:講授團討論口示教口指導團其他口教學資源（請打J）:多媒體回模型口實物口掛圖口音像口其他口討論、思考題、作業(yè)：P268：1,4,9教學內(nèi)容第六章運行時存儲空間組織編譯程序在完成詞法、語法和語義分析后，在生成目標代碼之前，需要把程序的靜態(tài)正文和實現(xiàn)這個程序的運行時的活動聯(lián)系起來，弄清楚將來

53、在代碼運行時刻，源代碼中的各種變量、常量等用戶定義的量是如何存放的，如何去訪問它們。在程序的執(zhí)行過程中，程序中數(shù)據(jù)的存取是通過與之對應的存儲單元來進行的。在程序語言中，程序使用的存儲單元都是由標識符來表示的。它們對應的內(nèi)存地址都是由編譯程序在編譯時或由其生成的目標程序運行時進行分配。所以對于編譯程序來說存儲組織與管理是一個復雜而又十分重要的問題。這一章就是對目標程序運行時的活動和運行環(huán)境進行討論，主要討論存儲組織與管理,包括活動紀錄的建立與管理、存儲器的組織與存儲分配的策略、非局部名稱的訪問等問6.1目標程序運行時的活動6.1.1過程的活動這一節(jié)討論一個過程的靜態(tài)源程序和它的目標程序在運行時的

54、活動之間的關系。一個過程的活動指的是該過程的一次執(zhí)行。關于過程一個活動的生存期，指的是從執(zhí)行該構成體第一步操作到最后一步操作之間的操作序列，包括執(zhí)行時調(diào)用其他過程化費的時間。一般來說，術語“生存期”指的是在程序執(zhí)行過程中若干步驟的一個順序序列。一個說明在程序里能起作用的范圍成為該說明的作用域。6.1.2參數(shù)傳遞要掌握在過程調(diào)用時出現(xiàn)的：形式參數(shù)，實在參數(shù)等基本概念。傳地址，傳值，傳名三種參數(shù)傳遞方法。由于傳遞參數(shù)的方法不同，同樣的程序運行的結果可能大不相同。6.2運行時存儲器的劃分6.2.1運行時存儲器的劃分編譯程序為了使它編譯后得到的目標程序能夠運行，要從操作系統(tǒng)中獲得一塊存儲空間。從上一節(jié)

55、的討論我們知道，對這塊提供運行的空間應該進行劃分以便存放其中包括生成的目標代碼、數(shù)據(jù)對象和跟蹤過程活動的控制棧。6.2.2活動紀錄為了管理過程在一次執(zhí)行中所需要的信息，使用一個連續(xù)的存儲塊，我們把這樣的一個連續(xù)存儲塊稱為活動紀錄。當前活動紀錄一般包括如下內(nèi)容：連接數(shù)據(jù)返回地址動態(tài)鏈：指向調(diào)用該過程前的最新活動紀錄地址的指針。運行時，是運行棧上各數(shù)據(jù)區(qū)按動態(tài)建立的次序結成鏈。鏈頭為棧頂起始位置。靜態(tài)鏈：指向靜態(tài)直接外層最新活動紀錄地址的指針，用來訪問非局部數(shù)據(jù)。形式單元：存放相應的實在參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時工作單元（如存放對表達式求值的結果）。不同的編譯程序關于數(shù)據(jù)

56、空間的存儲分配策略可能不同。靜態(tài)分配策略在編譯是對所有對象分配固定的存儲單元。且在運行是保持不變。棧式動態(tài)分配策略在運行時把存儲器作為一個棧進行管理，運行時，每當調(diào)用一個過程，它所需要的存儲空間就動態(tài)的分配于棧頂，一旦退出，它所占空間就予以釋放。堆式動態(tài)存儲策略在運行時把存儲器組織成堆結構，以便用戶關于存儲空間的申請與歸還（回收），凡申請者分給一塊，凡釋放者退回給堆。靜態(tài)存儲分配如果在編譯時就能夠確定一個程序在運行時所需要的存儲空間的大小，則在編譯時就能夠安排好目標程序運行時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項的單元地址。存儲空間的這種分配方法叫做靜態(tài)分配。這一節(jié)要特別注意臨時變量的地址分配方法

57、。盡管在翻譯時大量引進了臨時變量名，但是并不是對每一個名字分配一個不同的存儲單元，那樣做太浪費空間了。一個一般的原則是如果兩個臨時變量的名字作用域不相交，則他們可分配在同一單元中，一個臨時變量名自它第一次被定值（賦值）的地方起直至它最后一次被引用的地方止，這區(qū)間的程序所能到達的全體四元式，構成了它的作用域。對于用來暫存表達式中間結果的臨時變量名而言，只存在一次定值和一次引用，并且在定值和引用之間不存在分叉轉移（無論轉進或轉出）這類臨時變量名作用域的確定是非常簡單的。它們的存儲分配可用一種特別簡易的辦法實現(xiàn)。我們說過，大部分的臨時變量名是用來存放表達式的中間結果。這些臨時變量有一個特點。它們均只

58、被定值一次，被引用一次。它們的作用域如同配對的括號序列所管轄的區(qū)一樣是層次嵌套的。因此我們可以設想用一個棧（先進后出區(qū)）來存放這類臨時變量名的值。也就是說，可以用一個棧來存放表達式記值過程中的中間結果。為簡單起見，我們假定所有臨時變量值只需要一種同一長度棧單元。令為棧的指示器，設它的初值是局部區(qū)中用來存放臨時變量值的區(qū)域首地址。每當發(fā)現(xiàn)一個新的臨時變量名定值時就用的現(xiàn)行值作為的地址。然后把累增。每當引用了某個臨時變量名作為操作數(shù)時（此時的地址必已分配），就把指示器的值遞減。6.4簡單的棧式存儲分配使用棧式存儲分配法意味著把存儲組成一個棧，運行時，每當一個過程（一個新的活動開始）時，就把它的活動

59、紀錄壓入棧（累筑于棧頂），從而形成過程工作時的數(shù)據(jù)區(qū)，一個過程的活動紀錄的體積在編譯是是可靜態(tài)確定的。當該過程結束（過程退出）時，再把它的活動過程彈出棧。這樣在棧頂?shù)臄?shù)據(jù)區(qū)也隨即不復存在。此時運行棧最頂端數(shù)據(jù)取得是兩個指示器和SP總是指向現(xiàn)行過程活動紀錄的起點，用于訪問局部數(shù)據(jù)。始終指向（已占用）棧頂單元。這兩個指示器實際上是固定分配了兩個變址器。當進入一個過程時，指向為此過程創(chuàng)建的活動記錄的頂端，在分配數(shù)組之后，就改指向數(shù)組區(qū)（整個數(shù)據(jù)區(qū)）的頂端。的活動紀錄的活動紀錄有以下四個項目。連接數(shù)據(jù)，有兩個：（）老值，即前一個活動紀錄的地址；（2）返回地址。參數(shù)個數(shù)。形式單元（存放實在參數(shù)的值或地址

60、）。TOP-X幅時工作單元P內(nèi)者向量SF簡單變量舞式單元參蠹個數(shù)篦回地址老9.14匚過程的活硒紀錄過程的局部變量、數(shù)組內(nèi)情向量和臨時工作單元。其結構如圖9.14所示。由圖9.14所示，過程的每一個局部變量或形參在活動紀錄中的位置是確定的，就是說，對它們都分配了存儲單元，其地址是相對于活動紀錄的基地址（的。因此，變量和形參運行實時在棧上的絕對地址是：絕對地址=活動紀錄基地址+相對地址的過程調(diào)用、過程進入、數(shù)組空間分配和過程返回我們說過，過程調(diào)用的四元式序列：現(xiàn)在我們考慮在運行時四元式和是如何執(zhí)行的，或者說，對于和應該生成些什么相應的目標代碼。由于總是指向棧頂，而形式單元和活動紀錄起點之間的距離是