編譯原理教案-資料下載頁

　　

【正文】 驗課254。 練習(xí)課254。 其他□教學(xué)方式（請打√）：講授254。 討論□ 示教□ 指導(dǎo)254。 其他□教學(xué)資源（請打√）：多媒體254。 模型□ 實物□ 掛圖□ 音像□ 其他□討論、思考題、作業(yè)：P217：1，4，7，9教學(xué)內(nèi)容第四章 語法制導(dǎo)翻譯和中間代碼產(chǎn)生 屬性文法和語法制導(dǎo)翻譯屬性文法是在上下文無關(guān)文法的基礎(chǔ)上為每個文法符號（終結(jié)符或非終結(jié)符）配備若干個相關(guān)的“值”（稱為屬性）。這些屬性代表與文法符號相關(guān)的信息，例如它的類型、值、代碼序列 、符號表內(nèi)容等等。屬性和變量一樣，可以進行計算和傳遞。 屬性一般分為兩類：綜合屬性和繼承屬性。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。屬性加工的過程即是語義處理的過程，對于文法的每一個產(chǎn)生式都配備了一組屬性的計算規(guī)則，則稱為語義規(guī)則。 在一個屬性文法中，對應(yīng)于每個產(chǎn)生式Aa174。都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條語義規(guī)則的形式為： b:=f(c1,c2,…,ck) 這里f是一個函數(shù)，而且或者 （1）b是A的一個綜合屬性并且c1,c2,…,ck是產(chǎn)生式右邊文法符號的屬性； 或者 （2）b是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且c1,c2,…，ck是A或 產(chǎn)生式右邊任何文法符號的屬性 在這兩種情況下，我們都說屬性b依賴于屬性c1,c2，…,ck.： 在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。因此，通常使用自底向上的方法在每一個結(jié)點處使用語義規(guī)則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。 35＋4n ： 在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性確定。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。 如果在一棵語法樹中一個結(jié)點的屬性b依賴于屬性c，那么這個結(jié)點處計算b的屬性規(guī)則必須在確定c的語義規(guī)則之后使用。在一顆語法樹中的結(jié)點的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以用稱作依賴圖的一個有向圖來描述。 在為一棵語法樹構(gòu)造依賴圖以前，我們?yōu)槊恳粋€包含過程調(diào)用的語義規(guī)則引入一個虛綜合屬性b，這樣把每一個語義規(guī)則都寫成 b:= f(c1,c2, …ck) 的形式。依賴圖中為每一個屬性設(shè)置一個結(jié)點，如果屬性b依賴屬性c，則從屬性c的結(jié)點有一條有向邊連到屬性b的結(jié)點。這里要掌握依賴圖的畫法。 例如，屬性 :=f( , ) 對應(yīng)于產(chǎn)生式 A174。XY的語義規(guī)則,。 如果在語法樹中應(yīng)用這個產(chǎn)生式，,。，. 如果與產(chǎn)生式A174。XY對應(yīng)的語義規(guī)則還有： :=g(,) 那么，圖中還應(yīng)有兩條有向邊，,. S—屬性文法的自下而上計算 這一節(jié)我們考慮這樣一類屬性文法：S—屬性文法，它只含有綜合屬性。相應(yīng)屬性文法的翻譯器很容易建立。 下面我們討論分析棧中的綜合屬性。 在自底向上的分析法中。我們使用一個棧來存放已經(jīng)分析過的子樹的信息?，F(xiàn)在我們可以在分析棧中使用一個附域來存放綜合屬性值。State val… …X Y Z … … L—屬性文法和自頂向下翻譯 一個屬性文法稱為L—屬性文法：如果對于每個產(chǎn)生式A174。X1X2…Xn其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj(1=j=n)的一個繼承屬性且這個繼承屬性僅依賴于： （1）產(chǎn)生式Xj的左邊符號X1,X2,…Xj1的屬性 （2）A的繼承屬性。L—屬性文法允許通過一次遍歷就計算出所有屬性值。 中間語言 我們將介紹其他幾種常見的中間語言形式：后綴式（逆波蘭式）三地址代碼（四元式，三元式，間接三元式），DAG圖表示。 后綴式后綴式表示法是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達式的方法，因此又稱逆波蘭表示法。表達式E的后綴形式可以如下定義：(1) 如果E是一個變量或常量，則E的后綴式是E自身。 (2) 如果E是E1opE2形式的表達式，這里op是任何二元操作符，則E的后綴式為E1’E2’op，這里E1’和E2’分別為El和E2的后綴式。這種表示法用不著使用括號。根據(jù)運算量和算符出現(xiàn)的先后位置，以及每個算符的目數(shù)，就完全決定了一個表達式的分解。例如 abc+* 所代表的表達式是 a*(b+c)。只要我們知道每個算符的目數(shù)，對于后綴式，不論從哪一端進行掃描，都能對它正確進行唯一分解。把一般表達式翻譯為后綴式是很容易的。 圖表示法 這里的圖表示法包括DAG（無循環(huán)有向圖）與抽象語法樹。 三地址代碼三地址代碼可以看成是抽象語法樹或DAG的一種線性表示。之所以稱為三地址代碼是因為每條語句通常包含三個地址，兩個用來表示操作數(shù)，一個用來存放結(jié)果。對于后面給出的三地址代碼中，用戶定義的名字在實際實現(xiàn)時將由指向符號表中的相應(yīng)名字入口的指針?biāo)?。三地址語句類似于匯編語言代碼。語句可以帶有符號標(biāo)號，而且存在各種控制流語句。符號標(biāo)號代表存放中間代碼的數(shù)組中三地址代碼語句的下標(biāo)。 說明語句 當(dāng)我們考查一個過程或分程序的一系列說明語句時，便可為局部于該過程的名字分配存儲空間。對每個局部名字，我們都將在符號表中建立相應(yīng)的表項，并填入有關(guān)的信息如類型、在存儲器中的相對地址等。相對地址是指對靜態(tài)數(shù)據(jù)區(qū)基址或活動記錄中局部數(shù)據(jù)區(qū)基址的一個偏移量。有關(guān)活動記錄我們將在第九章詳細(xì)介紹。當(dāng)產(chǎn)生中間代碼地址時，對目標(biāo)機一些情況做到心中有數(shù)是有好處的。例如，假定在一個以字節(jié)編址的目標(biāo)機上，整數(shù)必須存放在4的倍數(shù)的地址單元，那么，計算地址時就應(yīng)以4的倍數(shù)增加。 過程中的說明語句 在C、Pascal及FORTRAN等語言的語法中，允許在一個過程中的所有說明語句作為一個組來處理，把它們安排在一個數(shù)據(jù)區(qū)中。從而我們需要一個全程變量如offset來跟蹤下一個可用的相對地址的位置。在關(guān)于說明語句的翻譯模式中，非終結(jié)符號P產(chǎn)生一系列形如id：T的說明語句。在處理第一條說明語句之前，先置offset為0，以后每次遇到一個新的名字，便將該名字填入符號表中并置相對地址為當(dāng)前offset之值，然后使offset加上該名字所表示的數(shù)據(jù)對象的域?qū)挕＿^程enter(name，type，offset)用來把名字name填入到符號表中，并給出此名字的類型type及在過程數(shù)據(jù)區(qū)中的相對地址offset。非終結(jié)符號T有兩個綜合屬性T．type和 T．width，分別表示名字的類型和名字的域?qū)?即該類型名字所占用的存儲單元個數(shù))。假定整數(shù)類型域?qū)挒?；實數(shù)域?qū)挒?；一個數(shù)組的域?qū)捒梢酝ㄟ^把數(shù)組元素數(shù)目與一個元素的域?qū)捪喑双@得；每個指針類型的域?qū)捈俣橐?增加。 保留作用域信息 過程readarray，exchange和quicksord的符號表有指針指向其外圍過程的符號表。另一過程partition是在quicksort中被說明，因此它的符號表有指針指向quicksort的符號表。在下面的語義規(guī)則中用到如下操作： (1)mktable(previous)創(chuàng)建一張新符號表，并返回指向新表的一個指針。參數(shù)previous 指向一張先前創(chuàng)建的符號表，譬如剛好包含嵌入過程的外圍過程符號表。指針previous 之值放在新符號表表頭，表頭中還可存放一些其它信息如過程嵌套深度等。我們也可以按過程被說明的順序?qū)^程編號，并把這一編號填入表頭。(2)enter(table，name，type，offset)在指針table指示的符號表中為名字建立一個新項，并把類型type、相對地址offset填入到該項中。(3)addwidth(table，width)在指針table指示的符號表表頭中記錄下該表中所有名字占用的總寬度。(4)enterproc(table，name，newtable)在指針table指示的符號表中為名字為name的過程建立一個新項。參數(shù)newtable指向過程name的符號表。 記錄中的域名 當(dāng)遇到保留字record時，與標(biāo)記非終結(jié)符號I相應(yīng)的語義動作為記錄中的各域名創(chuàng)建一張新的記錄符號表。把指向該表的指針壓入棧tblptr中，并把相對地址0壓入棧offset中。產(chǎn)生式D174。id：T的語義動作是將域名id的有關(guān)信息填入此記錄的符號表中。當(dāng)記錄的所有域名都被檢查過之后，在offset的棧頂將存放著記錄之內(nèi)的所有數(shù)據(jù)對象的總域?qū)?。文法中end之后的語義動作是將offset的棧頂?shù)目傆驅(qū)捵鳛榫C合屬性T．width的值。類型T．type通過對指向本記錄符號表的指針施用類型構(gòu)造符record而得到。、類型及域?qū)挼?。有關(guān)類型構(gòu)造符和類型表達式概念將在4．7節(jié)介紹。 在本節(jié)中賦值語句中的表達式的類型可以是整型、實型、數(shù)組和記錄。作為翻譯賦值語句為三地址代碼的一個部分，我們將討論如何在符號表中查找名字及如何存取數(shù)組和記錄的元素。課本P179給出了把簡單算術(shù)表達式及賦值語句翻譯為三地址代碼的翻譯模式。該翻譯模式中說明了如何查找符號表的入口。過程lookup()檢查是否在符號表中存在此名字的入口。如果有，則返回一個指向該表項的指針，否則，返回nil表示沒找到。在相關(guān)的語義動作中，調(diào)用過程emit將生成的三地址語句發(fā)送到輸出文件中，我們可以重新解釋lookup操作，若采用最近嵌套作用域規(guī)則查找非局部名字，如Pascal語言中的那樣，此時前面的翻譯模式仍是可用的。 數(shù)組元素的引用現(xiàn)在討論包括數(shù)組元素的表達式和賦值語句的翻譯問題。若數(shù)組A的元素存放在一片連續(xù)單元里，則可以較容易的訪問數(shù)組的每個元素。假定數(shù)組的每個元素的寬度為w，則一維數(shù)組A[i] 這個元素的起始地址為： base + (i – low)*w （）其中l(wèi)ow為數(shù)組下標(biāo)的下界， 并且base是分配給數(shù)組的相對地址，即base為A的第一個元素A[low]的相對地址。： i*w + (base – low*w)其中：i*w 是隨數(shù)組下標(biāo)變量而變化的部分 （base – low*w）是在數(shù)組中不變化的常數(shù)記為C對于多維數(shù)組中二維的情況尤其應(yīng)注意：若二維數(shù)組A按行存放，則可用如下公式計算A[i1,i2]的相對地址： base + (( i1 – low1)*n2 + i1 – low2) *w其中，lowlow2分別為ii2的下界；n2是i2可取值得個數(shù)。即若high2為i2的上界，則n2=high2 – low2 +1.假定i1,i2是編譯時唯一尚未知道的值，我們可以重寫上述表達式為： ( (i1*n2) + i2) *w +( base –（ (low1 *n2) + low2) *w）后一項子表達式( base – （(low1 *n2) + low2) *w ）的值是可以在編譯時確定的,為常數(shù)。前一子項隨i1, i2 而改變是一個變數(shù)。特別是當(dāng)low=1， 時有：V=(i1*n2+i2)*w C= base –(n2+1)*w應(yīng)該牢記。要生成數(shù)組的引用代碼，其主要問題是把常數(shù)C和變數(shù)V 的計算與數(shù)組引用的文法聯(lián)系起來。 id 出現(xiàn)的地方也允許下面產(chǎn)生式中的L出現(xiàn)，則可把數(shù)組元素引用加入到賦值語句中。 L→id [ Elist ]| id Elist→Elist, E | E 為語句處理上的方便改寫為： L→Elist ] | id Elist →Elist, E | id [ E即把數(shù)組的名字id與最左下標(biāo)表達式E 相聯(lián)系，而不是在形成L時與Elist相聯(lián)系。其目的是使我們在整個下標(biāo)表達式串Elist的翻譯過程中隨時都知道符號表中相應(yīng)于數(shù)組名字id的全部信息。對于非終結(jié)符號Elist引進綜合屬性arry，用來紀(jì)錄指向符號表中相應(yīng)數(shù)組名字表項的指針。，即維數(shù)。函數(shù)Limit(arry, j) 返回nj ，即由arry所指示的數(shù)組的第j 維的長度。最后，用來臨時存放由Elist中的下標(biāo)表達式計算出來的值。一個Elist可以產(chǎn)生一個k 維數(shù)組引用A[i1,i2,…ik]的前m維下標(biāo)，并將生成計算下面式子的三地址代碼。 （ …( ( i1*n2 +i2)n3)…)nm + im利用如下的遞歸公式進行計算： e1 = i1, em = em1* nm + im于是 當(dāng)m=k時將ek乘以元素的寬度w便可計算出（）的第一個子項。描述L的左值（基地值），而offset為null，表示這個左只是一個簡單名字而非數(shù)組的引用。 記錄中域的作用 編譯器必須將記錄中的域的類型和相對地址保持下來。一般說來，把這些信息保存在相應(yīng)的域名的符號表表項之中。這樣做的好處是可以把用在符號表中查找名字的程序同樣用來查找域名。在此意義下，利用上一節(jié)圖4．9中的語義動作可為每一個記錄類型建立一張單獨的符號表。如果t是一個指向某個記錄類型的指針，把類型構(gòu)造符record 施于該指針，返回所形成的類型record(t)作為屬性T．type的值。p 是一個指向某個記錄的指針，這個記錄有一個類型為算術(shù)型的域名info。如果類型像圖4．8和圖4．9一樣構(gòu)造，則p173。的類型可以由類型表達式pointer(record(t))給出。于是p的類型是record(t)，t可由此先取出來。也就是說域名info將可以在t所指向的符號表中查找。 布爾表達式的翻譯在程序設(shè)計語言中，布爾表達式有兩個基本作用： 一個使用作計算邏輯值；另一個是用作控制流語句如ifthen、ifthenelse