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