圖書專題-博客園

第六章中間代碼生成在編譯器的分析-綜合模型中，前端對源程序進行分析并產(chǎn)生中間表示，后端在此基礎(chǔ)上生成目標(biāo)代碼。在理想情況下，和源語言相關(guān)的細節(jié)在前端分析中處理，而關(guān)于目標(biāo)機器的細節(jié)則在后端處理。基于一個適當(dāng)定義的中間表示形式，可以把針對源語言i的前端和針對目標(biāo)機器j的后端組合起來，構(gòu)造得到源語言i在目標(biāo)機器j上的一個編譯器。這種創(chuàng)建編譯器組合的方法可以節(jié)約大量的工作量：只要寫出m種前端和n種后端處理程序，就可以得到m×n種編譯程序。本章的內(nèi)容處理中間代碼表示、靜態(tài)類型檢查和中間代碼生成。為簡單起見，我們假設(shè)一個編譯程序的前端處理按照圖6.1所示方式進行組織，順序地進行語法分析、靜態(tài)檢查和中間代碼生成。有時候這幾個過程也可以組合起來，在語法分析中一并完成。我們將使用第二章和第五章中的語法制導(dǎo)定義來描述類型檢查和翻譯過程。大部分的翻譯方案可以基于第五章中給出的自頂向下或自底向上的技術(shù)來實現(xiàn)。所有的方案都可以通過生成并遍歷抽象語法樹來實現(xiàn)。Parser 語法分析器Parser 語法分析器StaticChecker靜態(tài)檢查程序Intermediatecodegenerator中間代碼生成器intermediatecode 中間代碼codegenerator 代碼生成器frontend 前端backend后端圖6.1：一個編譯器前端的邏輯結(jié)構(gòu)靜態(tài)檢查包括類型檢查，保證運算符被作用于兼容的運算分量。靜態(tài)檢查還包括在語法分析之后進行的所有語法檢查。例如，靜態(tài)檢查保證了C語言中的一條break指令必然位于一個while/for/switch語句之內(nèi)。如果不存在這樣的語句，靜態(tài)檢查將報告一個錯誤。本章介紹的方法可以用于多種中間表示，包括抽象語法樹和三地址代碼。這兩種中間表示方法都在本書的2.8節(jié)中介紹過。名為“三地址代碼”的原因是這些指令的一般形式x=yopz具有三個地址：兩個運算分量y和z，一個結(jié)果變量x。在將給定源語言的一個程序翻譯成特定的目標(biāo)機器代碼的過程中，一個編譯器可能構(gòu)造出一系列的中間表示，如圖6.2所示。高層的表示接近于源語言，而低層的表示接近于目標(biāo)機器。語法樹是高層的表示，它刻畫了源程序的自然的層次性結(jié)構(gòu)，并且很適合進行諸如靜態(tài)類型檢查這樣的處理。SourceProgram源程序SourceProgram源程序HighLevelIntermediateRepresentation高層中間表示形式LowLevelIntermediateRepresentation低層中間表示形式TargetCode 目標(biāo)代碼圖6.2：編譯器可能使用一系列的中間表示低層的表示形式適合進行機器相關(guān)的處理任務(wù)，比如寄存器分配、指令選擇等。通過選擇不同的運算符，三地址代碼既可以是高層的表示方式，也可以是低層的表示方式。從6.2.3節(jié)將可以看出，對表達式而言，語法樹和三地址代碼只是在表面上有所不同。對于循環(huán)語句，語法樹表示了語句的各個組成部分，而三地址代碼包含了標(biāo)號和跳轉(zhuǎn)指令，用來表示目標(biāo)語言的控制流。不同的編譯程序?qū)χ虚g表示的選擇和設(shè)計各有不同。中間表示可以是一種真正的語言，也可以是編譯器的各個處理階段共享的多個內(nèi)部數(shù)據(jù)結(jié)構(gòu)。C語言是一種程序設(shè)計語言。它具有很好的靈活性和通用性，可以很方便地把C程序編譯成高效的機器代碼，并且有很多C的編譯器可用，因此C語言也常常被用作中間表示。早期的C++編譯器的前端生成C代碼，而把C編譯器作為其后端。6.1語法樹的變體語法樹中各個結(jié)點代表了源程序的構(gòu)造；一個結(jié)點的所有子結(jié)點反映了該結(jié)點對應(yīng)構(gòu)造的有意義的組成成分。為表達式構(gòu)建的無環(huán)有向圖（Directedacyclicgraph,以后簡稱DAG）指出了表達式中的公共子表達式（多次出現(xiàn)的子表達式）。在本節(jié)我們將看到，可以用構(gòu)造語法樹的技術(shù)去構(gòu)造DAG圖。6.1.1表達式的有向無環(huán)圖和表達式的語法樹類似，一個DAG圖的葉子結(jié)點對應(yīng)于原子運算分量，而內(nèi)部結(jié)點對應(yīng)于運算符。與語法樹不同的是，如果DAG圖中的一個結(jié)點N表示一個公共子表達式，則N可能有多個父結(jié)點。在語法樹中，公共子表達式每出現(xiàn)一次，代表該公共子表達式的子樹就會被復(fù)制一次。因此，DAG不僅更簡潔地表示了表達式，而且可以為最終生成表達式的高效代碼提供重要的信息。例子6.1：圖6.3給出了下面的表達式的DAG圖a+a*(b-c)+(b-c)*d葉子結(jié)點a在表達式中出現(xiàn)了兩次，因此a有兩個父結(jié)點。值得注意的是，結(jié)點“-”代表公共子表達式b-c的兩次出現(xiàn)。該結(jié)點同樣有兩個父結(jié)點，表明該子表達式在子表達式a*(b-c)和(b-c)*d中兩次被使用。盡管b和c在整個表達式中出現(xiàn)了兩次，它們對應(yīng)的結(jié)點都只有一個父結(jié)點，因為對它們的使用都出現(xiàn)在同樣的公共子表達式b-c中?！鯃D圖6.3：表達式a+a*(b-c)+(b-c)*d的DAG圖圖6.4：生成語法樹或DAG圖的語法制導(dǎo)定義圖6.4：生成語法樹或DAG圖的語法制導(dǎo)定義圖6.4給出的SDD（語法制導(dǎo)定義）既可以用來構(gòu)造語法樹，也可以用來構(gòu)造DAG圖。它在例5.11中曾被用于構(gòu)造語法樹。在那時，函數(shù)lead和node每次被調(diào)用都會構(gòu)造出一個新結(jié)點。要構(gòu)造得到DAG圖，這些函數(shù)就要在每次構(gòu)造新結(jié)點之前首先檢查是否已存在這樣的結(jié)點。如果存在一個已被創(chuàng)建的結(jié)點，它們就返回這個結(jié)點。例如，在構(gòu)造一個新結(jié)點Node(op,left,right)之前，我們首先檢查是否已存在一個結(jié)點，該結(jié)點的標(biāo)號為op，且其兩個子結(jié)點為left和right。如果存在，Node函數(shù)返回這個已存在的結(jié)點；否則它創(chuàng)建一個新結(jié)點。例子6.2:圖6.5給出了構(gòu)造圖6.3中所示DAG圖的各個步驟。如上所述，函數(shù)node和leaf盡可能地返回已存在的結(jié)點。我們假設(shè)entry-a指向符號表中a的位置，其它標(biāo)識符也類似。圖圖6.5：圖6.3所示DAG圖的構(gòu)造過程。當(dāng)在第2步上再次調(diào)用Leaf(id,entry-a)時，函數(shù)返回的是之前已生成的結(jié)點，因此p2=p1。類似地，第8步和第9步上返回的結(jié)點分別和第3步及第4步中返回的結(jié)果相同（即p8=p3，p9=p4）。同樣，第10步中返回的結(jié)點必然和第5步中返回的相同，即p10=p5?！?.1.2構(gòu)造DAG的值編碼方法語法樹或DAG圖中的結(jié)點通常被存放在一個記錄數(shù)組中，如圖6.6所示。數(shù)組的每一行表示一個記錄，也就是一個結(jié)點。在每個記錄中，第一個域是一個運算符代碼，也是該結(jié)點的標(biāo)號。在圖6.6(b)中，各個葉子結(jié)點還有一個附加的域，存放了標(biāo)識符的字面值（在這里，它是一個指向符號表的指針或一個常量）。而內(nèi)部結(jié)點則有兩個附加的域，分別指明其左右子結(jié)點。圖圖6.6：i=i+10的DAG圖的結(jié)點在數(shù)組中的表示在這個數(shù)組中，我們只需要給出一個結(jié)點對應(yīng)的記錄在此數(shù)組中的整數(shù)序號就可以引用該結(jié)點。在歷史上，這個序號被稱為相應(yīng)結(jié)點或該結(jié)點所表示的表達式的值編碼。例如，在圖6.6中，標(biāo)號為“+”的結(jié)點的值編碼為3,其左右子結(jié)點的值編碼分別為1和2。在實踐中，我們可以用記錄指針或?qū)ο笠脕泶嬲麛?shù)下標(biāo)，但是我們?nèi)匀话岩粋€結(jié)點的引用稱為該結(jié)點的“值編碼”。如果使用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，值編碼可以幫助我們高效地構(gòu)造出表達式的DAG圖。下一個算法將給出構(gòu)造的方法。假定結(jié)點按照如圖6.6所示的方式存放在一個數(shù)組中，每個結(jié)點通過值編碼引用。令每個內(nèi)部結(jié)點用一個三元組表示<op,l,r>。其中op是標(biāo)號，l是其左子結(jié)點對應(yīng)的值編碼，r是右子結(jié)點對應(yīng)的值編碼。假設(shè)單目運算符對應(yīng)的結(jié)點中r=0。算法6.3:構(gòu)造DAG圖的值編碼方法。輸入：標(biāo)號op、結(jié)點l和結(jié)點r。輸出：數(shù)組中具有三元組<op,l,r>形式的結(jié)點的值編碼。方法：在數(shù)組中搜索標(biāo)號為op、左子結(jié)點為l且右子結(jié)點為r的結(jié)點M。如果存在，則返回M結(jié)點的數(shù)值號。若不存在，則在數(shù)組中添加一個結(jié)點N，其標(biāo)號為op，左右子結(jié)點分別為l和r；返回新建結(jié)點對應(yīng)的值編碼?！蹼m然算法6.3可以產(chǎn)生我們期待的輸出結(jié)果，但是每次定位一個結(jié)點時都要搜索整個數(shù)組。這個開銷是很大的，當(dāng)數(shù)組中存放了整個程序的所有表達式時尤其如此。更高效的途徑是使用哈希表，將結(jié)點放入若干“桶”中，每個桶通常只包含少量結(jié)點。哈希表是能夠高效支持詞典功能的少數(shù)幾個數(shù)據(jù)結(jié)構(gòu)之一見Aho,A.V.,J.E.Hopcroft和J.D.Ullman,DatastructuresandAlgorithms,Addison-Wesley出版社,1983。其中有一個關(guān)于支持詞典功能的數(shù)據(jù)結(jié)構(gòu)的討論。。詞典是一種抽象的數(shù)據(jù)類型，它可以插入或刪除一個集合中的元素，可以確定一個給定元素當(dāng)前是否在集合中。類似于見Aho,A.V.,J.E.Hopcroft和J.D.Ullman,DatastructuresandAlgorithms,Addison-Wesley出版社,1983。其中有一個關(guān)于支持詞典功能的數(shù)據(jù)結(jié)構(gòu)的討論。要給DAG圖中的結(jié)點構(gòu)造哈希表，首先需要建立哈希函數(shù)h。這個函數(shù)為形如<op,l,r>的三元組計算“桶”的索引，把三元組在各個桶之間進行分配，使得每個“桶”中的元組數(shù)量都不大可能超過平均數(shù)很多。通過對op、l、r的計算，可以確定地得到桶索引h（op,l,r）。因而我們可以多次重復(fù)這個計算過程，總是得到結(jié)點<op,l,r>的相同的桶索引。桶可以通過鏈表來實現(xiàn)，如圖6.7所示。一個由哈希值索引的數(shù)組保存桶的頭。每個頭指向列表中的第一個單元。所有其哈希值指向這個桶的結(jié)點都存放在這個桶的鏈表中，鏈表的各個單元記錄了這些結(jié)點的值編碼。就是說，在以數(shù)組的第h(op,l,r)個元素為頭的鏈表中可以找到結(jié)點<op,l,r>。ArrayofbucketheadersindexedbyhashvalueArrayofbucketheadersindexedbyhashvalue以Hash值為索引的桶頭的數(shù)組Listelementsrepresentingnodes表示結(jié)點的元素鏈表圖6.7：用于搜索桶的數(shù)據(jù)結(jié)構(gòu)因此，給定一個輸入結(jié)點(op,l,r)，我們首先計算桶索引h(op,l,r)，然后在該桶的鏈表單元中搜索這個結(jié)點。通常情況下有足夠多的桶，因此鏈表中不會有很多單元。然而，我們可能必須查看一個桶中的所有單元，并且對于每一個單元中的值編碼v，我們必須檢查輸入結(jié)點的三元組<op,l,r>是否和單元列表中值編碼為v的結(jié)點相匹配。如果我們找到了匹配的結(jié)點，就返回v。如果我們沒有找到，我們知道任何其它桶中都不會有這樣的結(jié)點。我們就創(chuàng)建一個新的單元，添加到“桶”索引為h(op,l,r)的單元鏈表中，并返回新建結(jié)點對應(yīng)的值編碼。6.1.36.1節(jié)的練習(xí)練習(xí)6.1.1:為下面的表達式構(gòu)造DAG圖((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))練習(xí)6.1.2:為下列表達式構(gòu)造DAG圖，且指出它們的每個子表達式的值編碼。假定＋是左結(jié)合的。a+b+(a+b)a+b+a+ba+a+(a+a+a+(a+a+a+a))6.2三地址代碼在三地址代碼中，一條指令的右部最多允許有一個運算符；也就是說，不允許組合的算術(shù)表達式。因此象x+y*z這樣的源語言表達式需要被翻譯成如下的三地址指令序列。t1=y*z，t2=x+t1。其中t1和t2是編譯器產(chǎn)生的臨時名字。因為三地址代碼拆分了多運算符算術(shù)表達式以及控制流語句的嵌套結(jié)構(gòu)，它很適合于目標(biāo)代碼的生成和優(yōu)化。具體的過程將在第8、9章中詳細介紹。因為用名字來表示程序計算得到的中間結(jié)果，三地址代碼可以方便地進行重組。例6.4：三地址代碼是一棵語法樹或一個DAG圖的線性表示形式。三地址代碼中的名字對應(yīng)于圖中的內(nèi)部結(jié)點。圖6.8中再次給出了圖6.3中的DAG圖，以及該圖對應(yīng)的三地址代碼序列?！鮀AGDAG三地址代碼圖6.8：一個DAG圖及其對應(yīng)的三地址代碼6.2.1地址和指令三地址代碼基于兩個基本概念：地址和指令。按照面向?qū)ο蟮恼f法，這兩個概念對應(yīng)于兩個類，而各種類型的地址和指令對應(yīng)于某個適當(dāng)?shù)淖宇悺Ａ硪环N方法是用記錄的方式來實現(xiàn)三地址代碼，記錄中的域被用來保存地址。6.2.2節(jié)將簡要介紹被稱為四元式和三元式的記錄表示方式。地址可以具有如下形式之一：名字。為方便起見，我們允許源程序中的名字出現(xiàn)在三地址代碼中。在實現(xiàn)中，源程序名字被替換為指向符號表條目的指針。關(guān)于該名字的所有信息均存放在該條目中。常量地址。在實踐中，一個編譯器往往要處理很多不同類型的常量和變量。6.5.2節(jié)將考慮表達式中的類型轉(zhuǎn)換問題。編譯器生成的臨時變量。在每次需要臨時變量時產(chǎn)生一個新名字是必要的，在優(yōu)化編譯器中尤其如此。當(dāng)為變量分配寄存器的時候，我們可以盡可能地合并這些臨時變量。下面我們介紹本書的其余部分常用的幾種三地址指令。改變控制流的指令將使用符號化標(biāo)號。每個符號化標(biāo)號表示了指令序列中的一條三地址指令的位置。通過一次單獨的掃描，或者通過回填技術(shù)就可以把符號化標(biāo)號替換為實際的指令位置?；靥罴夹g(shù)將在6.7節(jié)中討論。下面給出幾種常見的三地址指令形式：形如x=yopz的賦值指令，其中op是一個雙目算術(shù)或邏輯運算符。x、y、z是地址。形如x=opy的賦值指令，其中op是單目運算符?；镜膯文窟\算符包括單目減、邏輯非、移位操作和轉(zhuǎn)換操作。將整數(shù)轉(zhuǎn)換成浮點數(shù)的操作就是轉(zhuǎn)換操作的一個例子。形如x=y的復(fù)制指令，它把y的值賦給x。無條件轉(zhuǎn)移指令gotoL，下一步要執(zhí)行的指令是帶有標(biāo)號L的三地址指令。形如ifxgotoL或ifFalsexgotoL的條件轉(zhuǎn)移指令。分別當(dāng)x為真或為假時，這兩個指令的下一步將執(zhí)行帶有標(biāo)號L的指令。否則下一步將照常執(zhí)行序列中的后一條指令。形如ifxrelopygotoL的條件轉(zhuǎn)移指令。它對x和y應(yīng)用一個關(guān)系運算符（<,==,>=等等）。如果x和y之間滿足relop關(guān)系，那么下一步將執(zhí)行帶有標(biāo)號L的指令。否則將執(zhí)行指令序列中跟在這個指令之后的指令。過程調(diào)用和返回通過下列指令來實現(xiàn)：paramx進行參數(shù)傳遞，callp,n和y=callp,n分別進行過程調(diào)用和函數(shù)調(diào)用；returny是返回指令，其中y表示被返回值，它是可選的。這些指令的常見用法見下面的三地址指令序列paramx1paramx2…paramxncallp,n它是為過程調(diào)用p(x1,x2,…xn)所生成代碼的一部分。“callp,n”中的n是實在參數(shù)的個數(shù)。這個n并不是冗余的，因為存在嵌套調(diào)用的情況。就是說，前面的一些param指令可能是p返回之后才執(zhí)行的某個函數(shù)調(diào)用的參數(shù)，而p的返回值又成為這個后續(xù)函數(shù)調(diào)用的參數(shù)。過程調(diào)用的實現(xiàn)將在6.9節(jié)中概要描述。帶下標(biāo)的復(fù)制指令x=y[i]和x[i]=y。x=y[i]指令將把距離位置y處i個內(nèi)存單元的位置中存放的值賦給x。指令x[i]=y將距離位置x處i個內(nèi)存單元的位置中的內(nèi)容設(shè)置為y的值。形如x=&y、x=*y或*x=y的地址及指針賦值指令。指令x=&y將x的右值設(shè)置為y的地址（左值）2.8.3曾經(jīng)提出，l-/r-vlaue分別表示賦值左/右部。。這個y通常是一個名字，也可能是一個臨時變量。它表示一個諸如A[i][j]這樣、具有左值的表達式。x是一個指針名字或臨時變量。在指令x=*y中，假定y是一個指針，或是一個其右值表示內(nèi)存位置的臨時變量。這個指令使得x的右值等于存儲在這個地址中的值。最后，指令*x=y則把y的右值賦給由x指向的目標(biāo)的2.8.3曾經(jīng)提出，l-/r-vlaue分別表示賦值左/右部。例子6.5：考慮語句doi=i+1;while(a[i]<v);圖6.9給出了這個語句的兩種可能的翻譯。在圖6.9的翻譯中，第一條指令上附加了一個符號化標(biāo)號L。（b）中的翻譯顯示了每條指令的位置號，我們在圖中任意地選擇100作為開始位置。在兩種翻譯中，最后一條指令都是目標(biāo)為第一條指令的條件轉(zhuǎn)移指令。乘法運算i*8適用于每個元素占8個存儲單元的數(shù)組?！?a)符號標(biāo)號（b）位置標(biāo)號(a)符號標(biāo)號（b）位置標(biāo)號圖6.9：給三地址指令指定標(biāo)號的兩種方法選擇使用哪些運算符是中間表示形式設(shè)計的一個重要問題。顯然，這個運算符集合需要能夠?qū)崿F(xiàn)源語言中的所有操作。接近目標(biāo)指令的運算符可以使在目標(biāo)機器上實現(xiàn)中間表示形式更加容易。然而，如果前端必須為某些源語言操作生成很長的指令序列，那么優(yōu)化和代碼生成器就需要花費更多的時間去重新發(fā)現(xiàn)程序的結(jié)構(gòu)，然后才能為這些結(jié)構(gòu)生成高質(zhì)量的目標(biāo)代碼。6.2.2四元式表示上述對三地址指令的描述詳細說明了各類指令的組成部分，但是并沒有描述這些指令在某個數(shù)據(jù)結(jié)構(gòu)中的表示方法。在編譯器中，這些指令可以被描述為對象，或者是帶有運算符域和運算分量域的記錄。四元式、三元式和間接三元式是三種這樣的描述方式。一個四元式有四個域，我們分別稱之為op、arg1、arg2、result。域op包含了一個運算符的內(nèi)部編碼。舉例來說，三地址指令x=y+z相應(yīng)的四元式中，op域中存放+，arg1中為y，arg2中為z，result中為x。下面是這個規(guī)則的一些特例。形如x=minusy的單目運算符指令和賦值指令x=y不使用arg2。特別注意象x=y這樣的賦值語句，op是=；而對大部分其它操作而言，賦值操作是隱含表示的。象param這樣的運算既不使用arg2，也不使用result域。條件或非條件轉(zhuǎn)移指令將目標(biāo)標(biāo)號放入result域。例子6.6：賦值語句a=b*-c+b*-c的三地址代碼如圖6.10(a)所示。這里我們使用特殊的minus運算符來表示“-c”中的單目減運算符“-”，以區(qū)別于“b-c”中的雙目減運算符“-”。請注意單目減的三地址指令中只有兩個地址。復(fù)制指令a=t5也是如此。圖6.10(b)描述了實現(xiàn)（a）中三地址代碼的四元式序列?！酰╝）三地址代碼（b）四元式（a）三地址代碼（b）四元式圖6.10：三地址代碼及其四元式表示為了提高可讀性，我們在圖6.10(b)中直接用實際標(biāo)識符，比如象a、b、c，來描述arg1、arg2以及result域，而沒有使用指向相應(yīng)符號表條目的指針。臨時名字可以像程序聲明中的變量一樣被加入到符號表中，也可以實現(xiàn)為Temp類的實例對象。這個Temp類有自己的例程。6.2.3三元式表示一個三元式只有三個域，我們分別稱之為op,arg1和arg2。請注意，圖6.10(b)中的四元式的result域主要被用于臨時變量名。使用三元式時，我們將用運算xopy的位置來表示它的結(jié)果，而不是用一個明確的臨時名字表示。例如，在三元式表示中將直接用位置（0），而不是象圖6.10(b)中那樣用臨時名字t1來表示對相應(yīng)運算結(jié)果的引用。帶有括號的數(shù)字表示指向相應(yīng)三元式結(jié)構(gòu)的指針。在6.1.2節(jié)中，指針或位置信息被稱之為值編碼。三元式基本上和算法6.3中的結(jié)點范型等價。因此，表達式的DAG圖表示和三元式表示是等價的。當(dāng)然這種等價關(guān)系僅對表達式成立，語法樹的變體和三地址代碼分別以完全不同的方式來表示控制流。例子6.7：圖6.11中給出的語法樹和三元式表示對應(yīng)于圖6.10中的三地址代碼及四元式序列。在圖6.11(b)給出的三元式表示中，復(fù)制指令a=t5按照下列方式被表示為一個三元組：在域arg1是a，而在域arg2中是三元式位置的值編碼（4）?！跸髕[i]=y這樣的三元操作在三元式結(jié)構(gòu)中需要兩個條目；例如，我們可以把把x和i置于一個三元式，并把y置于另一個三元式。類似的，我們可以把x=y[i]看成是兩條指令t=y[i]和x=t，從而用三元式實現(xiàn)這個語句。其中的t是編譯器生成的臨時變量。請注意，實際上t是不會出現(xiàn)在三元式中的，因為在三元式結(jié)構(gòu)中是通過相應(yīng)三元式結(jié)構(gòu)的位置來引用臨時值的。為什么我們需要復(fù)制指令？為什么我們需要復(fù)制指令？如圖6.10(a)所示，一個簡單的翻譯表達式的算法往往會為賦值運算產(chǎn)生復(fù)制指令。在該圖中，我們將t5復(fù)制給a，而不是直接將t2+t4賦給a。通常，每個子表達式都會有一個它自己的臨時變量來存放運算結(jié)果。而只有當(dāng)處理賦值運算符=時，我們才知道將把整個表達式的結(jié)果賦到哪里。一個代碼優(yōu)化過程將會發(fā)現(xiàn)t5可以被替換為a。這個優(yōu)化過程可能使用6.1.1節(jié)中描述的DAG圖作為中間表示形式。（a）語法樹（b）三元式（a）語法樹（b）三元式圖6.11：a+a*(b-c)+(b-c)*d的表示在優(yōu)化型編譯器中，由于指令的位置常常會發(fā)生變化，四元式相對于三元式的優(yōu)勢就體現(xiàn)出來了。使用四元式時，如果我們移動了一個計算臨時變量t的指令，那些使用t的指令不需要作任何改變。而使用三元式時，對于操作結(jié)果的引用是通過位置號完成的，因此如果改變一條指令的位置，則引用該指令的結(jié)果的所有指令都需要做出修改。使用下面考慮的間接三元式時就不會發(fā)生這個問題。間接三元式包含了一個指向三元式的指針的列表，而不是列出三元式序列本身。例如，我們可以使用數(shù)組instruction按照適當(dāng)?shù)捻樞蛄谐鲋赶蛉降闹羔?。這樣，圖6.1.1(b)中的三元式序列就可以表示成為圖6.12中的形式。使用間接三元式表示方法時，優(yōu)化型編譯器可以通過對指針數(shù)組的重新排序來移動指令的位置。在用Java實現(xiàn)時，一個指令對象的數(shù)組和間接三元式表示類似，因為java將數(shù)組元素作為對象引用來處理。圖圖6.12：三地址代碼的間接三元式表示6.2.4靜態(tài)單賦值形式靜態(tài)單賦值形式（SSA）是另一種中間表示形式，它支持某些類型的代碼優(yōu)化。SSA和三地址代碼的區(qū)別主要在兩個方面。首先，SSA中的所有賦值都是針對具有不同名字的變量的，這也是術(shù)語靜態(tài)單賦值的由來。圖6.13給出了分別以三地址代碼形式和靜態(tài)單賦值形式表示的中間程序?？梢钥闯?，SSA表示中對變量p和q的每次定值都以不同的下標(biāo)加以區(qū)分。（a）（a）三地址代碼（b）靜態(tài)單賦值表示圖6.13：三地址代碼形式和SSA形式的中間程序在一個程序中，同一個變量可能在不同的控制流路徑中被定值。例如，下列源程序if(flag)x=-1;elsex=1;y=x*a;中，x在兩個不同的控制流路徑中被定值。如果我們對條件語句的真分支和假分支中的x使用不同的變量名進行定值，那么我們應(yīng)該在賦值運算y=x*a中使用哪個名字？這也是SSA的第二個特別之處。SSA使用一種被稱為φ-函數(shù)的記號規(guī)則將x的兩處定值合并起來：if(flag)x1=-1;elsex2=1;x3=φ(x1,x2)如果控制流經(jīng)過這個條件語句的真分支，φ(x1,x2)的值為x1，否則如果經(jīng)過假分支，φ-函數(shù)取x2值。也就是說，根據(jù)到達包含φ-函數(shù)的賦值語句的不同控制流路徑，φ-函數(shù)返回不同的參數(shù)。6.2.56.2節(jié)的練習(xí)練習(xí)6.2.1:將算術(shù)表達式a+-(b+c)翻譯成：語法樹四元式序列三元式序列間接三元式序列練習(xí)6.2.2:對下列賦值語句重復(fù)練習(xí)6.2.1。a=b[i]+c[j]a[i]=b*c–b*dx=f(y+1)+2x=*p+&y！練習(xí)6.2.3:說明如何對一個三地址代碼序列進行轉(zhuǎn)換，使得每個被定值的變量都有獨一無二的變量名。6.3類型和聲明可以把類型的應(yīng)用劃分為類型檢查和翻譯：類型檢查。類型檢查利用一組邏輯規(guī)則來推理一個程序在運行時刻的行為。更明確地講，類型檢查保證運算分量的類型和運算符的預(yù)期類型相匹配。例如，java要求&&運算符的兩個運算分量必須是boolean型；如果滿足這個條件，結(jié)果也具有boolean類型。翻譯時的應(yīng)用。根據(jù)一個名字的類型，編譯器可以確定這個名字在運行時刻需要多少存儲空間。類型信息還會在其它很多地方被用到，包括計算一個數(shù)組引用所指示的地址，插入顯式的類型轉(zhuǎn)換，選擇正確版本的算術(shù)運算符，等等。在這一節(jié)中，我們將考慮在某個過程或類中申明的變量的類型及存儲空間布局問題。一個過程調(diào)用或?qū)ο蟮膶嶋H存儲空間是在運行時刻，當(dāng)該過程被調(diào)用或該對象被創(chuàng)建時，進行分配的。然而，當(dāng)我們在編譯時刻檢查局部聲明時，我們可以進行相對地址的布局，一個名字或某個數(shù)據(jù)結(jié)構(gòu)分量的相對地址是指它相對于某個數(shù)據(jù)區(qū)域開始位置的偏移量。6.3.1類型表達式類型自身也有結(jié)構(gòu)，我們使用類型表達式來表示這種結(jié)構(gòu)：類型表達式可能是基本類型，也可能通過把被稱為類型構(gòu)造算子的運算符作用于類型表達式而構(gòu)造得到?；绢愋偷募虾皖愋蜆?gòu)造算子根據(jù)被檢查的具體語言而定。例子6.8：數(shù)組類型int[2][3]表示“由兩個數(shù)組組成的數(shù)組，其中的每個數(shù)組各包含3個整數(shù)”。它的類型表達式可以寫成array(2,array(3,integer))。該類型可以用如圖6.14中的樹來描述。Array運算符有兩個參數(shù)：一個數(shù)字和一個類型?！鯃D圖6.14：int[2][3]的類型表達式我們將使用如下的類型表達式的定義：一個基本類型是一個類型表達式。一種語言的基本類型通常包括：boolean，char，integer，float和void。最后一個類型表示“沒有值”。一個類名是一個類型表達式。將類型構(gòu)造算子array作用于一個數(shù)字和一個類型表達式可以構(gòu)造得到一個類型表達式。一個記錄是包含有名域的數(shù)據(jù)結(jié)構(gòu)。將record類型構(gòu)造符應(yīng)用于域名和相應(yīng)的類型可以構(gòu)造得到一個類型表達式。在6.3.6節(jié)中，記錄類型的實現(xiàn)方法是把構(gòu)造算子record應(yīng)用于包含了各個域?qū)?yīng)條目的符號表。使用類型構(gòu)造算子可以構(gòu)造得到函數(shù)類型的類型表達式。我們把“從類型s到類型t的函數(shù)”寫成st。在6.5節(jié)中討論類型檢查時，函數(shù)類型表達式是有用的。如果s和t是類型表達式，則其卡氏積s×t也是類型表達式。引入卡氏積主要是為了定義的完整性。它可以被用于描述類型的列表或元組（例如，帶參數(shù)的函數(shù)類型）。我們假定×具有左結(jié)合性，并且其優(yōu)先級高于。類型表達式可以包含取值為類型表達式的變量。在6.5.4節(jié)中將用到編譯器產(chǎn)生的類型變量。圖是表示類型表達式的一種比較方便的方法?？梢孕薷?.1.2節(jié)中給出的值編碼方法，用來構(gòu)造一個類型表達式的DAG圖。圖的內(nèi)部結(jié)點表示類型構(gòu)造算子，而葉子結(jié)點是基本類型、類型名或類型變量。6.1.4給出了一棵樹的實例類型名代表類型表達式，因此可能形成隱式的環(huán)；見上面的類型名代表類型表達式，因此可能形成隱式的環(huán)；見上面的“類型名和遞歸類型”方框。如果到達類型名的邊被重定向到該名字對應(yīng)的類型表達式，那么得到的圖中就可能因為遞歸類型的存在而出現(xiàn)環(huán)。類型名和遞歸類型類型名和遞歸類型在C++和Java中，類一旦被定義，其名字就可以被用來表示類型名。例如，下列程序片段中的Node類。PublicclassNode{…}…publicNoden;類型名還可被用來定義遞歸類型，在象鏈表這樣的數(shù)據(jù)結(jié)構(gòu)中必須要用到遞歸類型。一個列表元素的偽代碼如下classCell{intinfo;Cellnext;…}它定義了一個遞歸類型Cell。這個類包括一個info域和另一個Cell類型的域next。在C中可以通過記錄和指針來定義類似的遞歸類型。本章介紹的技術(shù)也適用于遞歸類型。6.3.2類型等價兩個類型表達式什么時候等價呢？很多類型檢查規(guī)則具有這樣的形式，“如果兩個類型表達式等價，那么返回某種類型，否則出錯”。當(dāng)對一些類型表達式命名，并且這些名字在之后的其它類型表達式中使用時就可能會產(chǎn)生歧義。關(guān)鍵問題在于一個類型表達式中的名字是代表它自身呢，還是被看作另一個類型表達式的一種縮寫形式。當(dāng)用圖來表示類型表達式的時候，兩種類型之間結(jié)構(gòu)等價當(dāng)且僅當(dāng)下面的某個條件為真：它們是相同的基本類型它們是將相同的類型構(gòu)造算子應(yīng)用于結(jié)構(gòu)等價的類型而構(gòu)造得到。一個類型是另一個類型表達式的名字。如果類型名僅僅代表它自身，那么上述定義中的前兩個條件定義了類型表達式的名等價關(guān)系。如果我們使用算法6.3，那么名等價的類型表達式將被賦予相同的值編碼。結(jié)構(gòu)等價關(guān)系可以使用6.5.5節(jié)中給出的合一算法進行檢驗。6.3.3聲明我們在研究類型及其聲明時將使用一個經(jīng)過簡化的文法，在這個文法中一次只聲明一個名字。一次聲明多個名字的情況可以象例子5.10中討論的那樣進行處理。我們使用的文法如下：D→Tid;D|εT→BC|record‘{’D‘}’B→int|floatC→ε|[num]C上述處理基本類型和數(shù)組類型的文法可以用來演示5.3.2節(jié)中描述的繼承屬性。本節(jié)的不同之處在于我們不僅考慮類型本身，還考慮各個類型的存儲布局。非終結(jié)符號D生成一系列聲明。非終結(jié)符T生成基本類型、數(shù)組類型或記錄類型。非終結(jié)符B生成基本類型int和float之一。非終結(jié)符C，表示“分量”，產(chǎn)生零個或多個整數(shù)，每個整數(shù)用方括號括起。一個數(shù)組類型包含一個由B指定的基本類型，后面跟一個由非終結(jié)符C指定的數(shù)組分量。一個記錄類型（T的第二個產(chǎn)生式）由各個記錄域的聲明序列構(gòu)成，并由花括號括起。6.3.4局部變量名的存儲布局從變量類型我們可以知道該變量在運行時刻需要的內(nèi)存數(shù)量。在編譯時刻，我們可以使用這些數(shù)量為每個名字分配一個相對地址。一個名字的的類型和相對地址信息被保存在符號表的相應(yīng)條目中。對于象字符串?dāng)?shù)據(jù)（strings）這樣的變長數(shù)據(jù)，以及象動態(tài)數(shù)組這樣的只有在運行時刻才能夠確定其大小的數(shù)據(jù)，處理的方法是為指向這些數(shù)據(jù)的指針保留一個已知的固定大小的存儲區(qū)域。運行時刻的存儲管理問題將在第7章中討論。地址對齊地址對齊數(shù)據(jù)對象的存儲布局受到目標(biāo)機器的尋址約束的影響。比如，將整數(shù)相加的指令往往希望整數(shù)能夠?qū)R，也就是說，希望它們被放在內(nèi)存中的某些特定位置上，比如地址能夠被4整除的位置上。雖然一個10個字符的數(shù)組只需要足以存放10個字符的字節(jié)空間，編譯器常常會給它分配12個字節(jié)——即下一個4的倍數(shù)——這樣會有2個字節(jié)沒有使用。因為對齊的要求而分配的無用空間被稱為“補白”。當(dāng)空間比較寶貴時，編譯器需要對數(shù)據(jù)進行壓縮，使得不存在“補白”空間；此時可能需要在運行時刻執(zhí)行額外的指令把被壓縮的數(shù)據(jù)重新定位，以便使得這些數(shù)據(jù)看上去仍然是對齊的，可以進行相關(guān)操作。假設(shè)存儲區(qū)域是連續(xù)的字節(jié)塊，其中字節(jié)是可尋址的最小內(nèi)存單位。一個字節(jié)通常有8個二進制位，若干字節(jié)組成一個機器字。多字節(jié)數(shù)據(jù)對象往往被存儲在一段連續(xù)的字節(jié)中，并以初始字節(jié)的地址作為該數(shù)據(jù)對象的地址。類型的寬度是指該類型的一個對象所需存儲單元的數(shù)量。一個基本類型，比如字符型、整型和浮點型，需要整數(shù)多個的字節(jié)。為方便訪問，為數(shù)組和類這樣的復(fù)合類型數(shù)據(jù)分配的內(nèi)存是一個連續(xù)的存儲字節(jié)塊在C或C++中，如果讓所有的指針具有相同的寬度，指針的存儲分配就變得比較簡單。其原因是我們可能需要在知道它所指對象的類型之前就為它分配存儲空間。在C或C++中，如果讓所有的指針具有相同的寬度，指針的存儲分配就變得比較簡單。其原因是我們可能需要在知道它所指對象的類型之前就為它分配存儲空間。圖6.15中給出的翻譯方案（SDT）計算了基本類型和數(shù)組類型以及它們的寬度。記錄類型將在6.3.6節(jié)中討論。這個SDT對每個非終結(jié)符使用綜合屬性type和width。它還使用了兩個變量t和w，變量的用途是將類型和寬度信息從語法分析樹中的B結(jié)點傳遞到對應(yīng)于產(chǎn)生式C→ε的結(jié)點。在語法制導(dǎo)定義中，t和w將是C的繼承屬性。T-產(chǎn)生式的產(chǎn)生式體包含一個非終結(jié)符號B、一個動作和一個非終結(jié)符號C，其中C顯示在下一行上。B和C之間的動作是將t設(shè)置為B.type，并將w設(shè)置為B.width。如果B→int,則B.type被設(shè)置為integer，B.width被設(shè)置為4，即一個整型數(shù)的寬度。類似的，如果B→float，則B.type和B.width分別被設(shè)置為float和8，即一個浮點數(shù)的寬度。C的產(chǎn)生式?jīng)Q定了T生成的是一個基本類型還是一個數(shù)組類型。如果是C→ε，則t變成C.type，且w變成C.width。否則C就描述了一個數(shù)組分量。C→[num]C1的動作將類型構(gòu)造算子array應(yīng)用于運算分量num.value和C1.type，構(gòu)造得到C.type。例如，應(yīng)用算子array的結(jié)果可能是圖6.14所示的樹形結(jié)構(gòu)。圖圖6.15：確定類型及其寬度數(shù)組的寬度是將數(shù)組元素的個數(shù)乘以單個數(shù)組元素的寬度而得到的。如果連續(xù)存放的整數(shù)的地址之間的差距為4，那么對一個整數(shù)數(shù)組的地址計算將包含乘4運算。這樣的乘法運算為優(yōu)化提供了機會，因此讓前端程序的輸出將這樣的操作明確描述出來有助于優(yōu)化。在這一章中，我們將忽略其它與機器相關(guān)特性，比如數(shù)據(jù)對象的地址必須和機器字的邊界對齊。例6.9：類型int[2][3]的語法分析樹用圖6.16中的虛線描述。圖中的實線描述了type和width是如何從B結(jié)點開始，通過變量t和w，沿著多個C組成的鏈下傳，然后又作為綜合屬性type和width沿此鏈返回的。在訪問包含C結(jié)點的子樹之前，變量t和w被賦予B.type和B.width的值。變量t和w的值在C→ε對應(yīng)的結(jié)點上被使用，并開始沿著多個C結(jié)點組成的鏈向上的對綜合屬性求值。□圖6.16：圖6.16：數(shù)組類型的語法制導(dǎo)翻譯6.3.5聲明的序列象C和Java這樣的語言允許單個過程中的所有聲明分成一個組進行處理。這些聲明可能分布在一個java過程中。但是仍然能夠在分析該過程時處理它們。因此，我們可以使用一個變量，比如offset，來跟蹤下一個可用的相對地址。圖6.7中的翻譯方案處理形如Tid的聲明的序列，其中的T如圖6.15所示產(chǎn)生一個類型。在考慮第一個聲明之前，offset被設(shè)置為0。每處理一個變量x時，x被加入符號表，它的相對地址被設(shè)置為offset的當(dāng)前值。隨后，x的類型的寬度被加到offset上。圖6.17圖6.17：計算被聲明變量的相對地址產(chǎn)生式D→Tid;D1中的語義動作首先執(zhí)行top.put(id.lexeme,T.type,offset)，創(chuàng)建一個符號表條目。這里的top指向當(dāng)前的符號表。例程top.put為id.lexeme創(chuàng)建一個符號表條目，該條目的數(shù)據(jù)區(qū)中存放了類型T.type和相對地址offset。如果我們把第一個產(chǎn)生式寫在同一行中，P→{offset=0;}D（6.1）圖6.17中對offset的初始化處理就變得更容易理解。生成ε的非終結(jié)符被稱為標(biāo)記非終結(jié)符。這些終結(jié)符號的目的是使得所有的語義動作都出現(xiàn)在產(chǎn)生式右部的尾端；具體方法見5.5.4節(jié)。使用標(biāo)記非終結(jié)符M，（6.1）可以被改寫為：P→MDM→ε{offset=0;}6.3.6記錄和類中的域圖6.17中對聲明的翻譯方案還可以被用于處理記錄和類中的域。要把記錄類型加入到圖6.15中的文法中，只需要加上下面的產(chǎn)生式：T→record‘{’D‘}’這個記錄類型中的域由D生成的聲明序列描述。圖6.17中的方法可以被用來確定這些域的類型和相對地址，當(dāng)然我們還需要小心地處理下面兩件事：一個記錄中各個域的名字必須是互不相同的；就是說，在由D生成的聲明中同一個名字最多出現(xiàn)一次。域名的偏移量，或者說相對地址，是相對與該記錄的數(shù)據(jù)區(qū)域而言的。例6.10：在一個記錄中域中把名字x用作域名并不會和記錄外對該名字的其它使用沖突。因此下列聲明中對x的三次使用是不同的，互相之間并不沖突。floatx;record{floatx;floaty;}p;recode{inttag;floatx;floaty;}q;這些聲明之后的一個賦值語句x=p.x+q.x;把變量x的值設(shè)置為記錄p和q中x域的值的和。請注意，p中x的相對地址和q中x的相對地址是不同的?！鯙榉奖闫鹨?，記錄類型將使用一個專用的符號表，對它們的各個域的類型和相對地址進行編碼。記錄類型形如record(t)，其中record是類型構(gòu)造算子，t是一個符號表對象，它保存了有關(guān)該記錄類型的各個域的信息。圖6.18中的翻譯方案包含一條產(chǎn)生式，該產(chǎn)生式將被加入到圖6.15中關(guān)于T的產(chǎn)生式中。這個產(chǎn)生式有兩個語義動作。嵌在D之前的動作首先保存top指向的已有符號表。然后將top指向新的符號表。該動作還保存了當(dāng)前offset值，并將offset重置為0。D生成的聲明所給出的類型和相對地址將被保存到新的符號表中。D之后的語義動作使用top創(chuàng)建了一個記錄類型，然后恢復(fù)早先保存好的符號表和偏移值。圖6.18圖6.18：處理記錄類型中的域名為了使翻譯方案更加具體，圖6.18中的動作給出了某個特定實現(xiàn)的偽代碼。令Env類實現(xiàn)了符號表的管理。對Env.push(top)的調(diào)用將top所指的當(dāng)前符號表壓入一個棧中。然后變量top被設(shè)置為指向一個新的符號表。類似的，offset被推入名為Stack的棧中，offset變量被重置為0。在D中的聲明被翻譯方案處理之后，符號表top保存了這個記錄中所有域的類型和相對地址。而且offset還給出了存放所有域所需的存儲空間。第二個動作將T.type設(shè)為record(top)，并將T.width設(shè)為offset。然后，變量top和offset將被恢復(fù)為原先被壓入棧中的值，完成這個記錄類型的翻譯過程。有關(guān)記錄類型存儲方式的討論還可以被推廣到類，因為我們無需為類中的例程保留存儲空間。見練習(xí)6.3.2。6.3.76.3節(jié)的練習(xí)練習(xí)6.3.1：確定下列聲明序列中各個標(biāo)識符的類型和相對地址。floatx;record{floatx;floaty;}p;record{inttag;floatx;floaty;}q;！練習(xí)6.3.2：將圖6.18對域名的處理方法擴展到類和單繼承的類層次結(jié)構(gòu)。給出類Env的一個實現(xiàn)。該實現(xiàn)允許符號表鏈，使得子類可以重定義一個域名，也可以直接引用某個超類中的域名。給出一個翻譯方案，該方案能夠為類中的域分配連續(xù)的存儲區(qū)域，這些域中包含繼承而來的域。繼承而來的域必須保持在對超類進行存儲分配時獲得的相對地址。6.4表達式的翻譯本章余下的部分將介紹在翻譯表達式和語句時出現(xiàn)的關(guān)鍵問題。在本節(jié)中，我們首先考慮從表達式到三地址代碼的翻譯。一個帶有多個運算符的表達式，比如a+b*c，將被翻譯成為每條指令只包含一個運算符的指令序列。一個數(shù)組引用A[i][j]將被擴展成一個計算該引用的地址的三地址指令序列。我們將在6.5節(jié)中考慮表達式的類型檢查，并在6.6節(jié)中介紹如何使用布爾表達式來處理程序的控制流。6.4.1表達式中的運算圖6.19中的語法制導(dǎo)定義使用S的屬性code以及表達式E的屬性addr和code，為一個賦值語句S生成三地址代碼。屬性S.code和E.code分別表示S和E對應(yīng)的三地址代碼。屬性E.addr則表示被用于存放E的值的地址?；仡?.2.1節(jié)，一個地址可以是變量名字、常量或編譯器產(chǎn)生的臨時量。PRODUCTION 產(chǎn)生式PRODUCTION 產(chǎn)生式SEMANTICRULES 語義規(guī)則圖6.19表達式的三地址代碼考慮圖6.19中語法制導(dǎo)定義的最后一個產(chǎn)生式E→id。若表達式只是單個的標(biāo)識符，比如說x，那么x本身就保存了這個表達式的值。這個產(chǎn)生式對應(yīng)的語義規(guī)則把E.addr定義位為指向該id的實例對應(yīng)的符號表條目的指針。令top表示當(dāng)前的符號表。當(dāng)函數(shù)top.get被做用于id的這個實例的字符串表示id.lexeme時，它返回對應(yīng)的符號表條目。E.code被設(shè)置為空串。當(dāng)規(guī)則為E→(E1)時，對E的翻譯等同于對子表達式E1的翻譯。因此，E.addr等于E1.addr，E.code等于E1.code。圖6.19中運算符+和單目-是典型語言中的運算符的代表。E→E1+E2的語義規(guī)則生成了根據(jù)E1和E2的值計算E的值的代碼。計算得到的值被存放在新生成的臨時變量中。如果E1的值計算后被放入E1.addr，E2的值被放到E2.addr中，那么E1+E2就可以被翻譯為t=E1.addr+E2.addr，其中t是一個臨時變量。E.addr被設(shè)為t。連續(xù)執(zhí)行newTemp()會產(chǎn)生一系列互不相同的臨時變量t1，t2….。為方便起見，我們使用記號gen（x‘=’y‘+’z）來表示三地址指令x=y+z。當(dāng)被傳遞給gen時，變量x、y、z的位置上出現(xiàn)的表達式將首先被求值，而象‘=’這樣的引號內(nèi)的字符串則按照字面直接生成在語法制導(dǎo)定義中，gen構(gòu)造出一條指令并返回它。在翻譯方案中，gen構(gòu)造出一條指令，并增量地將它添加到指令流中去。。其它的三地址指令的生成方法類似，也是將gen作用于在語法制導(dǎo)定義中，gen構(gòu)造出一條指令并返回它。在翻譯方案中，gen構(gòu)造出一條指令，并增量地將它添加到指令流中去。當(dāng)我們翻譯產(chǎn)生式E→E1+E2時，圖6.19中的語義規(guī)則首先將E1.code和E2.code聯(lián)接起來，然后再加上一條將E1和E2的值相加的指令，從而生成E.code。新增加的這條指令將求和的結(jié)果放入一個為E生成的臨時變量中，用E.addr表示。產(chǎn)生式E→-E1的翻譯類似。這個規(guī)則首先為E創(chuàng)建一個新的臨時變量，并生成一條指令來執(zhí)行單目-操作。最終，產(chǎn)生式S→id=E;所生成的指令將表達式E的值賦給標(biāo)識符id。和規(guī)則Eid中一樣，這個產(chǎn)生式的語義規(guī)則使用函數(shù)top.get來確定id所代表的標(biāo)識符的地址。S.code包含的代碼首先計算E的值并將其保存到由E.addr指定的地址中，然后再將這個值賦給這個id實例的地址top.get(id.lexeme)。例子6.11：圖6.19中的語法制導(dǎo)定義將賦值語句a=b+-c;翻譯成如下的三地址代碼序列t1=minusct2=b+t1a=t2□6.4.2增量翻譯code屬性可能是很長的字符串，因此就像5.5.2中討論的那樣，它們通常是用增量的方式生成的。因此，我們不會象圖6.19中那樣構(gòu)造E.code，我們可以設(shè)法象圖6.20中那樣只生成新的三地址代碼。在這個增量方式中，gen不僅要構(gòu)造出一個新的三地址指令，還要將它添加到至今為止已生成的三地址指令序列之后。指令序列可能暫時放在內(nèi)存中進一步處理，也可能增量地輸出。圖6.20中的翻譯方案和圖6.19中的語法制導(dǎo)定義產(chǎn)生相同的代碼。采用增量方式時不需再用到code屬性，因為對gen的連續(xù)調(diào)用將生成一個指令序列。例如，圖6.20中對應(yīng)于E→E1+E2的語義規(guī)則直接調(diào)用gen產(chǎn)生一條加法指令；在此之前，翻譯方案已經(jīng)生成了計算E1的值并放入E1.addr、計算E2并放入E2.addr的指令序列。圖6.20的方法同樣可以被用來構(gòu)造語法樹，對應(yīng)于E→E1+E2的語義規(guī)則使用構(gòu)造算子生成新的結(jié)點。規(guī)則如下：E→E1+E2{E.addr=newNode(‘+’,E1.addr,E2.addr);}這里，屬性addr表示的是一個結(jié)點的地址，而不是某個變量或常量。圖6.20增量生成表達式的三地址圖6.20增量生成表達式的三地址代碼6.4.3數(shù)組元素的尋址將數(shù)組元素存儲在一塊連續(xù)的存儲空間里就可以快速地訪問它們。在C和Java中，一個具有n個元素的數(shù)組中的元素是按照0，1，…，n-1編號的。假設(shè)每個數(shù)組元素的寬度是w，那么數(shù)組A的第i個元素的開始地址為base+i×w (6.2)其中base是分配給數(shù)組A的內(nèi)存塊的相對地址。就是說，base是A[0]的相對地址。公式（6.2）可以被泛化到2維或多維數(shù)組上。對于2維數(shù)組，我們在C和Java中用A[i1][i2]來表示第i1行的第i2個元素。假設(shè)一行的寬度是w1，同一行中每個元素的寬度是w2。A[i1][i2]的相對地址可以使用下面的公式計算base+i1×w1+i2×w2 (6.3)對于k維數(shù)組，相應(yīng)的公式為base+i1×w1+i2×w2+…..+ik×wk (6.4)其中，wj(1≤j≤k)是對公式（6.3）中的w1和w2的泛化。另一種計算數(shù)組引用的相對地址的方法是根據(jù)第j維上的數(shù)組元素的個數(shù)nj和該數(shù)組的每個元素的寬度w=wk進行計算。在二維數(shù)組中（即k=2，w=w2），A[i1][i2]的地址為base+(i1×n2+i1)×w (6.5)對于k維數(shù)組，下列公式計算得到的地址和公式6.4所得地址相同：base+((..(i1×n2+i2)×n3+i3)…)×nk+ik)×w (6.6)在更一般的情況下，數(shù)組元素下標(biāo)并不一定是從0開始的。在一個一維數(shù)組中，數(shù)組元素的編號方式如下：low,low+1….high，而base是A[low]的相對地址。計算A[i]的地址的公式(6.2)變成了：base+(i-low)×w (6.7)公式（6.2）和（6.7）都可以改寫成i*w+c的形式，其中的子表達式c=base-low*w可以在編譯時刻預(yù)先計算得到。請注意當(dāng)low為0時c=base。我們假定c被存放在A對應(yīng)的符號表條目中，因此只要簡單地把i*w加到c上就可以計算得到A[i]的相對地址。編譯時刻的預(yù)先計算同樣可以被用于多維數(shù)組元素的地址計算；見練習(xí)6.4.5。然而，有一種情況下我們不能使用編譯時刻預(yù)先計算的技術(shù)：當(dāng)數(shù)組大小是動態(tài)的時候。如果我們在編譯時刻無法知道low和high（或者它們在多維數(shù)組情況下的泛化）的值，我們就無法提前計算出象c這樣的常量。因此在程序運行時，象（6.7）這樣的公式就需要按照公式所寫進行求值。上面的地址計算是基于數(shù)組的按行存放方式的。C和Java語言都使用這種數(shù)據(jù)布局方式。一個二維數(shù)組通常有兩種存儲方式，即按行存放（一行行地存儲）和按列存放（一列列地存放）。圖6.21顯示了一個2×3的數(shù)組A的兩種存儲布局方式，（a）中是按行存放方式，（b）中是按列存放方式。Fortran系列語言使用按列存放方式。Firstrow第一行 Secondrow 第二行Firstrow第一行 Secondrow 第二行Firstcolumn第一列 Secondcolumn 第二列 Thirdcolumn第三列(a)按行存放 (b)按列存放圖6.21：二維數(shù)組的存儲布局我們可以把按行存放策略和按列存放策略泛化到多維數(shù)組中。按行存放方式的泛化形式按照如下的方式來存儲元素：當(dāng)我們掃描一塊存儲區(qū)域時，就象汽車?yán)锍瘫碇械臄?shù)字一樣，最右邊的下標(biāo)變化最為頻繁。而按列存放方式則被泛化為相反的布局方式，最左邊的下標(biāo)變化最頻繁。6.4.4數(shù)組引用的翻譯為數(shù)組引用生成代碼時要解決的主要問題是將6.4.3節(jié)中給出的相對地址計算公式和數(shù)組引用的語法規(guī)則關(guān)聯(lián)起來。令非終結(jié)符L生成一個數(shù)組名字再加上一個下標(biāo)表達式的序列：L→L[E]|id[E]與C和Java中一樣，我們假定數(shù)組元素的最低端編號是0。我們使用公式6.4，基于寬度來計算相對地址，而不是象公式（6.6）中那樣使用元素的數(shù)量。圖6.22的翻譯方案為帶有數(shù)組引用的表達式生成三地址代碼。它包括了圖6.20中給出的產(chǎn)生式和語義動作，同時還包括了涉及到非終結(jié)符L的產(chǎn)生式。圖6.22處理數(shù)組引用的語義動作圖6.22處理數(shù)組引用的語義動作非終結(jié)符L有三個綜合屬性：L.addr指示一個臨時變量。這個臨時變量將被用于累加公式(6.4)中的ij*wj項，計算得到數(shù)組引用的偏移量。L.array是一個指向數(shù)組名字的符號表條目的指針。在分析了所有的下標(biāo)表達式之后，該數(shù)組的基地址，也就是L.array.base，被用于確定一個數(shù)組引用的實際左值。L.type是L生成的子數(shù)組的類型。對于任何類型t，我們假定其寬度由t.width給出。我們把類型而不是寬度作為屬性，是因為無論如何類型檢查總是需要這個類型信息。對于任何數(shù)組類型t，假設(shè)t.elem給出了其數(shù)組元素的類型。產(chǎn)生式S→id=E;代表了一個對非數(shù)組變量的賦值語句，它按照通常的方法進行處理。S→L=E的語義規(guī)則產(chǎn)生了一個帶下標(biāo)的復(fù)制指令，它將表達式E的值存放到數(shù)組引用L所指的內(nèi)存位置?；仡櫼幌?，屬性L.array給出了數(shù)組的符號表條目。數(shù)組的基地址——即0號元素的地址——由L.array.base給出。屬性L.addr表示了一個臨時變量，它保存了L生成的數(shù)組引用的偏移量。因此這個數(shù)組引用的位置是L.array.base[L.addr]。這個指令將地址E.addr中的右值放入L的內(nèi)存位置中。產(chǎn)生式E→E1+E2和E→id和以前相同。新的產(chǎn)生式E→L的語義動作生成的代碼將L所指位置上的值復(fù)制到一個新的臨時變量中。和前面對產(chǎn)生式S→L=E的討論中一樣，L所指的地址就是L.array.base[L.addr]；其中屬性L.array仍然給出了數(shù)組名，L.array.base給出了數(shù)組的基地址。屬性L.addr表示保存偏移量的臨時變量。數(shù)組引用的代碼將存放在由基地址和偏移量給出的位置中的右值放入E.addr所指的臨時變量中。例子6.12：令a表示一個2×3的整數(shù)數(shù)組，c、i、j都是整數(shù)。那么a的類型就是aray(2,array(3,integer))。假定一個整數(shù)的寬度為4，那么a的類型的寬度就是24。a[i]的類型是array(3,integer)，寬度w1為12。a[i][j]的類型是整型。圖6.23給出了表達式c+a[i][j]的標(biāo)注分析樹。該表達式被翻譯成圖6.24中給出的三地址代碼序列。這里我們?nèi)匀皇褂妹總€標(biāo)識符的名字來表示它們的符號表條目?！?.4.56.4節(jié)的練習(xí)練習(xí)6.4.1：向圖6.19的翻譯方案中加入對應(yīng)于下列產(chǎn)生式的規(guī)則：E→E1*E2。E→+E1(單目加)。練習(xí)6.4.2：使用圖6.20中的增量式翻譯方案，重復(fù)練習(xí)6.4.1。圖6.23：圖6.23：c+a[i][j]的標(biāo)注分析樹圖6.24：表達式c+a[i][j]的的三地址代碼圖6.24：表達式c+a[i][j]的的三地址代碼練習(xí)6.4.3：使用圖6.22所示的翻譯方案來翻譯下列賦值語句：x=a[i]+b[j]x=a[i][j]+b[i][j]!c)x=a[b[i][j]][c[k]]!練習(xí)6.4.4：修正圖6.22中的翻譯方案，使之適合Fortran風(fēng)格的數(shù)組引用，也就是說，n維數(shù)組的引用為id[E1,E2,…,En]。練習(xí)6.4.5：將公式（6.7）推廣到多維數(shù)組上，并指出哪些值可以被存放到符號表中并用來計算偏移量?？紤]下列的情況：一個二維數(shù)組A，按行存放。第一維的下標(biāo)從l1到h1，第二維的下標(biāo)從l2到h2。單個數(shù)組元素的寬度為w。和(a)相同，但是采用按列存放方式。！c)一個k維的數(shù)組A，按行存放，元素寬度為w，第j維的下標(biāo)從lj到hj。！d)和(c)相同，但是采用按列存放方式。符號化表示的類型寬度符號化表示的類型寬度中間代碼應(yīng)該相對獨立于目標(biāo)機器，這樣當(dāng)代碼生成器被替換為另一臺機器的生成器時，優(yōu)化程序不需要很大的改變。然而，正如我們剛剛描述的類型寬度計算方法中顯示的，關(guān)于基本類型的信息被融合到了這個翻譯方案中。例如，例子6.12中假定每個整數(shù)數(shù)組的元素占4個字節(jié)。一些中間代碼，如Pascal的p-code，讓代碼生成器來填寫數(shù)組元素的大小，因此這個中間代碼獨立于機器的字長。只要用一個符號常量來代替翻譯方案中的（作為整數(shù)類型寬度的）4，我們就可以在我們的翻譯方案中同樣做到這一點。練習(xí)6.4.6：一個整數(shù)數(shù)組A[i,j]的下標(biāo)i的范圍從1到10，下標(biāo)j的范圍從1到20。每個整數(shù)占4個字節(jié)。假設(shè)數(shù)組A從0字節(jié)開始存放，請給出下列元素的位置：a)A[4,5]b)A[10,8]c)A[3,17]練習(xí)6.4.7：假定A是按列存放的，重復(fù)練習(xí)6.4.6。練習(xí)6.4.8：一個實數(shù)型數(shù)組A[i,j,k]的下標(biāo)i的范圍從1到4，j的范圍從0到4，且k的范圍從5到10。每個實數(shù)占8個字節(jié)。假設(shè)數(shù)組A從0字節(jié)開始存放。計算下列元素的位置。a)A[3,4,5]b)A[1,2,7]c)A[4,3,9]練習(xí)6.4.9：假定A是按列存放的，重復(fù)練習(xí)6.4.8。6.5類型檢查為了進行類型檢查，編譯器需要給源程序的每一個組成成分賦予一個類型表達式。然后，編譯器需要確定這些類型表達式是否滿足一組邏輯規(guī)則。這些規(guī)則被稱為源語言的類型系統(tǒng)。類型檢查具有發(fā)現(xiàn)程序中的錯誤的功能。原則上，如果目標(biāo)代碼在保存元素值的同時保存了元素類型的信息，任何檢查都可以動態(tài)地進行。一個健全的類型系統(tǒng)可以消除對動態(tài)類型檢查的需要，因為它可以幫助我們靜態(tài)地確定這些錯誤不會在程序運行的時候發(fā)生。如果編譯器可以保證它接受的程序在運行時刻不會發(fā)生類型錯誤，那么該語言的這個實現(xiàn)就被稱為強類型的。除了用于編譯，類型檢查的思想還被用來提高系統(tǒng)的安全性，使得人們安全地導(dǎo)入和執(zhí)行軟件模塊。Java程序被編譯成為機器無關(guān)的字節(jié)碼。在字節(jié)碼中包含了有關(guān)字節(jié)碼中的操作的詳細類型信息。導(dǎo)入的代碼在被允許執(zhí)行之前首先要進行類型檢查，以防止因疏忽造成的錯誤和惡意攻擊。6.5.1類型檢查規(guī)則類型檢查有兩種形式：綜合和推導(dǎo)。類型綜合根據(jù)子表達式的類型構(gòu)造出表達式的類型。它要求名字先聲明再使用。表達式E1+E2的類型是根據(jù)E1和E2的類型定義的。一個典型的類型綜合規(guī)則具有如下形式：iff的類型為s→t且x的類型為s,then表達式f(x)的類型為t. (6.8)這里，f和x表示表達式，而s→t表示從s到t的函數(shù)。這個針對單參數(shù)函數(shù)的規(guī)則可以推廣到帶有多個參數(shù)的函數(shù)。稍作修改，規(guī)則（6.8）就可以被用于E1+E2，我們只需要把它看作一個函數(shù)應(yīng)用add(E1,E2)就可以了即使我們在確定類型時需要某些上下文信息，我們?nèi)詫⑹褂眉词刮覀冊诖_定類型時需要某些上下文信息，我們?nèi)詫⑹褂谩熬C合”這個術(shù)語。使用重載函數(shù)時，多個函數(shù)可能被賦予同一個名字。在某些語言中，我們還需要考慮E1+E2的上下文才能確定其類型規(guī)則。類型推導(dǎo)根據(jù)一個語言結(jié)構(gòu)的使用方式來推導(dǎo)該結(jié)構(gòu)類型。預(yù)先看一下6.5.4節(jié)中的例子，令null是一個測試列表是否為空的函數(shù)。那么根據(jù)這個函數(shù)的使用null(x)，我們可以指出x必須是一個列表類型。列表x中的元素類型是未知的，我們所知道的全部信息是：x是一個列表類型，其元素類型當(dāng)前未知。代表類型表達式的變量使得我們可以考慮未知類型。我們可以用希臘字母α、β等等作為類型表達式中的變量。一個典型的類型推導(dǎo)具有下面的形式：iff(x)是一個表達式,then對某些α和β,f的類型為α→β且x的類型為α (6.9)在類似ML這樣的語言中需要進行類型推導(dǎo)。ML語言會檢查類型，但是不需要對名字進行聲明。在本節(jié)中，我們考慮表達式的類型檢查。檢查語句的規(guī)則和檢查表達式類型的規(guī)則類似。例如，我們可以把條件語句“if(E)S;”看作是對E和S應(yīng)用if函數(shù)。令特殊類型void表示沒有值的類型。那么if函數(shù)將被應(yīng)用在一個布爾型和一個void型的對象上；此函數(shù)的結(jié)果類型是void類型。6.5.2類型轉(zhuǎn)換考慮類似于x+i的表達式，其中x類型是浮點數(shù)而i是整型。因為整數(shù)和浮點數(shù)在計算機中有不同的表示形式，而且使用不同的機器指令來操作整數(shù)和浮點數(shù)。編譯器需要把+的某個運算分量進行轉(zhuǎn)換，以保證在進行加法運算時兩個運算分量具有相同的類型。假定在必要的時候可以使用一個單目運算符（float）將整數(shù)轉(zhuǎn)換成浮點數(shù)。例如，整數(shù)2在表示式2*3.14的代碼中被轉(zhuǎn)換成浮點數(shù)：t1=(float)2t2=t1*3.14我們可以擴展這樣例子，考慮運算符的整型版本和浮點型版本；比如int*表示作用于整型運算分量的運算符，而float*表示作用于浮點型運算分量的運算符。我們將擴展6.4.2節(jié)中的用于表達式翻譯的翻譯方案，以說明如何進行類型綜合。我們引入另一個屬性E.type，該屬性的取值可以是integer或float。和E→E1+E2關(guān)聯(lián)的規(guī)則可用如下的偽代碼給出：if(E1.type=integerandE2.type=integer)E.type=integer;elseif(E1.type=floatandE2.type=integer)……隨著需要轉(zhuǎn)換的類型的增多，需要處理的不同情況急劇增多。因此在處理大量的類型時，精心組織用于類型轉(zhuǎn)換的語義動作就變得非常重要。不同語言具有不同的類型轉(zhuǎn)換規(guī)則。圖6.25中的Java的轉(zhuǎn)換規(guī)則區(qū)分了拓寬轉(zhuǎn)換和窄化轉(zhuǎn)換。拓寬轉(zhuǎn)換可以保持原有的信息，而窄化轉(zhuǎn)換則可能丟失信息。拓寬規(guī)則通過圖6.25（a）中的層次結(jié)構(gòu)給出：在該層次結(jié)構(gòu)中位于較低層的類型可以被拓寬為較上層的類型。因此，char類型可以被拓寬為int型和float型，但是不可以被拓寬為short類型。窄化轉(zhuǎn)換的規(guī)則表示為圖6.25(b)中的圖：如果存在一條從s到t的路徑，則可以將s窄化為t?？梢钥闯?，char、short、byte之間可以兩兩相互轉(zhuǎn)換。如果類型轉(zhuǎn)換由編譯器自動完成，那么這樣的轉(zhuǎn)換就被稱為隱式轉(zhuǎn)換。隱式轉(zhuǎn)換又稱為coercion類型轉(zhuǎn)換。在很多語言中coercion轉(zhuǎn)換僅僅限于拓寬轉(zhuǎn)換。如果程序員必須寫出某些代碼來引發(fā)類型轉(zhuǎn)換操作，這個轉(zhuǎn)換就稱為顯式的。顯式轉(zhuǎn)換也被稱為cast轉(zhuǎn)換。（a）拓寬類型轉(zhuǎn)換（b）窄化類型轉(zhuǎn)換（a）拓寬類型轉(zhuǎn)換（b）窄化類型轉(zhuǎn)換圖6.25：Java中簡單類型的轉(zhuǎn)換檢查E→E1+E2的語義動作使用了兩個函數(shù):max(t1,t2)接受t1和t2兩個類型參數(shù)，并返回拓寬層次結(jié)構(gòu)中這兩個類型的最大者（或者最小上界）如果t1或t2之一沒有出現(xiàn)在這個層次結(jié)構(gòu)中，比如有個類型是數(shù)組類型或指針類型，那么該函數(shù)返回一個錯誤信息。如果需要將地址a中類型為t的值轉(zhuǎn)換成w類型的值，函數(shù)widen(a,t,w)將生成類型轉(zhuǎn)換的代碼。如果t和w是相同的類型，該函數(shù)返回a本身。否則，它會生成一條指令來完成轉(zhuǎn)換工作并將轉(zhuǎn)換結(jié)果放置到臨時變量t中。這個臨時變量作為結(jié)果返回。函數(shù)widen的偽代碼如圖6.26所示，這里假設(shè)只有integer和float兩種類型。圖6.26：widen函數(shù)的偽代碼圖6.26：widen函數(shù)的偽代碼圖6.27中E→E1+E2的語義動作演示了如何把類型轉(zhuǎn)換加入到在圖6.20所示的表達式翻譯的翻譯方案中。在這個語義動作中，如果E1的類型不需要被轉(zhuǎn)換成E的類型時，臨時變量a1就是E1.addr。如果需要進行這樣的轉(zhuǎn)換，a1就是widen函數(shù)返回的一個新的臨時變量。類似地，a2可能是E2.addr，也可能是一個新臨時變量，用于存放轉(zhuǎn)換后的E2的值。如果兩個變量都是整型或者都是浮點型，就不需要進行任何轉(zhuǎn)換。然而我們會發(fā)現(xiàn)，總的來說將兩個不同類型的值相加的唯一方法是把它們都轉(zhuǎn)換成為第三種類型。圖6.27：表達式求值中引入類型轉(zhuǎn)換圖6.27：表達式求值中引入類型轉(zhuǎn)換6.5.3函數(shù)和運算符的重載依據(jù)它所在的不同上下文，被重載的符號會有不同的含義。如果能夠為一個名字的每次出現(xiàn)確定其唯一的含義，該名字的重載就得到了解決。在本節(jié)中，我們僅考慮那些只需要查看函數(shù)參數(shù)就能解決的函數(shù)重載。Java中的重載即是如此。例子6.13：根據(jù)其運算分量的類型，Java中的+運算符既可以表示字符的連接運算，也可以表示加法運算。用戶自定義的函數(shù)同樣可以重載，例如voiderr(){…}voiderr(Strings){…}請注意，我們可以根據(jù)函數(shù)err的參數(shù)來確定選擇這個函數(shù)的哪一個版本?！跻韵率轻槍χ剌d函數(shù)的類型綜合規(guī)則：iff可能的類型為si→ti,（1≤i≤n），其中如果i≠j，si≠sjandx的類型為sk,對某個1≤k≤n(6.10)then表達式f(x)的類型為tk6.1.2節(jié)中的值編碼方法同樣可以被用于類型表達式，根據(jù)參數(shù)類型高效地解決重載問題。在表示類型表達式的一個DAG圖上，我們給每個結(jié)點賦予一個被稱為值編碼的整數(shù)值。使用算法6.3，我們可以構(gòu)造出每個結(jié)點的范型，該范型由該結(jié)點的標(biāo)號及其從左到右的子結(jié)點的值編碼組成。一個函數(shù)的范型由其函數(shù)名和它的參數(shù)的類型組成。根據(jù)函數(shù)的參數(shù)類型解決重載的問題就等價于基于范型解決重載的問題。僅僅通過查看一個函數(shù)的參數(shù)類型并不一定能夠解決重載問題。在Ada中，一個子表達式會有一組可能的類型，而不是只有一個確定的類型。它所在的上下文必須提供足夠的信息來縮小可選范圍，最終得到唯一的可選類型（見練習(xí)6.5.2）。6.5.4類型推導(dǎo)和多態(tài)函數(shù)類型推導(dǎo)常被用于象ML這樣的語言中。ML是一個強類型語言，但是它不要求名字在被使用前首先進行聲明。類型推導(dǎo)保證了名字使用的一致性。術(shù)語“多態(tài)”指的是任何可以在不同的參數(shù)類型上運行的代碼片段。在本節(jié)中，我們考慮參數(shù)多態(tài)，這種多態(tài)通過參數(shù)和類型變量來刻劃。我們使用圖6.28中的ML程序作為一個貫穿本節(jié)的例子。該程序定義了一個函數(shù)length。函數(shù)length的類型可以描述為：“對于任何類型α，length函數(shù)將元素類型為α的列表映射為整型”。圖6.28：計算一個列表長度的ML程序圖6.28：計算一個列表長度的ML程序例子6.14：在圖6.28中，關(guān)鍵字fun引出了一個函數(shù)定義；被定義的函數(shù)可以是遞歸的。這個程序片段定義了帶有單個參數(shù)x的函數(shù)length。這個函數(shù)的函數(shù)體包含了一個條件表達式。預(yù)定義的函數(shù)null測試一個列表是否為空。預(yù)定義函數(shù)tl（tail的縮寫）移除列表中的第一個元素，然后返回列表的余下部分。函數(shù)length確定一個列表x的長度，或者說x中元素的個數(shù)。列表中的所有元素必須具有相同的類型。不管列表元素是什么類型，length函數(shù)都可以被用來求出這個列表的長度。在下面的表達式中，length被應(yīng)用到兩種不同類型的列表中（列表元素用“[”和“]”括起）：length([“sun”,“mon”,“tue”])+length([10,9,8,7])(6.11) 字符串列表的長度為3，整數(shù)列表的長度為4，因此表達式（6.11）的值為7?！跏褂梅枺ㄗx作“對于任意類型”）以及類型構(gòu)造算子list，length的類型可以寫作：α.list(α)→integer(6.12)符號是全稱量詞，它所作用于的類型變量被稱為受限的。受限變量可以被任意地重命名，但是需要把這個變量的所有出現(xiàn)一起同樣地重命名。因此，類型表達式β.list(β)→integer和（6.12）等價。其中帶有符號的類型表達式被稱為“多態(tài)類型”。在多態(tài)函數(shù)的各次應(yīng)用中，函數(shù)的受限的類型變量可以表示不同的類型。在類型檢查中，每次使用多態(tài)類型時，我們將受限變量替換為新的變量，并去掉相應(yīng)的全稱量詞。下一個例子對length類型進行了非正式的推導(dǎo)，推導(dǎo)過程中隱式地使用了公式（6.9）中的推導(dǎo)規(guī)則。這里再重復(fù)一遍：iff(x)是一個表達式,then對某些α和β,f的類型為α→β且x的類型為α (6.9)例6.15：圖6.29中的抽象語法樹表示圖6.28中對length的定義。這棵樹的根的標(biāo)號為fun。它表示函數(shù)定義。其它的非葉子結(jié)點可以看作是函