第六章中間代碼生成趙建華南京大學(xué)計算機(jī)系第六章中間代碼生成趙建華本章內(nèi)容中間代碼表示抽象語法樹三地址代碼：x=yopz靜態(tài)類型檢查類型檢查（typechecking）語法分析之后的抽象語法(syntax)檢查，比如break的位置，goto的目標(biāo)….中間代碼生成本章內(nèi)容中間代碼表示編譯器前端的邏輯結(jié)構(gòu)編譯器前端的邏輯結(jié)構(gòu)三地址代碼（1）每條指令右側(cè)最多有一個運(yùn)算符一般情況可以寫成x

=

yopz允許的運(yùn)算分量：名字：源程序中的名字作為三地址代碼的地址常量：源程序中出現(xiàn)或生成的常量編譯器生成的臨時變量三地址代碼（1）每條指令右側(cè)最多有一個運(yùn)算符三地址代碼（2）指令集合（1）運(yùn)算/賦值指令：x=yopz x

=

opy復(fù)制指令：x=y無條件轉(zhuǎn)移指令：gotoL條件轉(zhuǎn)移指令：ifxgotoL ifFalsexgotoL條件轉(zhuǎn)移指令：ifxrelopygotoL三地址代碼（2）指令集合（1）三地址代碼（3）指令集合（2）過程調(diào)用/返回：paramx1 //設(shè)置參數(shù)paramx2…paramxncallp,n //調(diào)用子過程p，n為參數(shù)個數(shù)帶下標(biāo)的復(fù)制指令：x=y[i]

x[i]=y注意：i表示離開數(shù)組位置第i個字節(jié)，而不是數(shù)組的第i個元素地址/指針賦值指令：x=&y x=*y *x=y三地址代碼（3）指令集合（2）例子語句doi=i+1;while(a[i]<v)；例子語句三地址指令的四元式表示方法在實(shí)現(xiàn)時，可以使用四元式/三元式/間接三元式來表示三地址指令四元式：可以實(shí)現(xiàn)為紀(jì)錄（或結(jié)構(gòu)）格式（字段）： op arg1 arg2 resultop:運(yùn)算符的內(nèi)部編碼arg1,arg2,result是地址x=y+z +yzx單目運(yùn)算符不使用arg2param運(yùn)算不使用arg2和result條件轉(zhuǎn)移/非條件轉(zhuǎn)移將目標(biāo)標(biāo)號放在result字段三地址指令的四元式表示方法在實(shí)現(xiàn)時，可以使用四元式/三元式/四元式的例子賦值語句：a=b*-c+b*-c四元式的例子賦值語句：a=b*-c+b*-c三元式表示三元式（triple） op arg1 arg2使用三元式的位置來引用三元式的運(yùn)算結(jié)果x[i]=y需要拆分為兩個三元式求x[i]的地址，然后再賦值x=yopz需要拆分為（這里？是編號）(?) op y z = x ?問題：在優(yōu)化時經(jīng)常需要移動/刪除/添加三元式，導(dǎo)致三元式的移動。三元式表示三元式（triple） op arg1 arg2三元式的例子a=b*-c+b*-c三元式的例子a=b*-c+b*-c間接三元式包含了一個指向三元式的指針的列表我們可以對這個列表進(jìn)行操作，完成優(yōu)化功能；操作時不需要修改三元式中的參數(shù)。間接三元式包含了一個指向三元式的指針的列表靜態(tài)單賦值（SSA）SSA中的所有賦值都是針對不同名的變量對于同一個變量在不同路徑中定值的情況，可以使用φ函數(shù)來合并不同的定值if(flag)x=-1;elsex=1; y=x*aif(flag)x1=-1;elsex2=1;

x3=φ(x1,x2)；y=x3*a靜態(tài)單賦值（SSA）SSA中的所有賦值都是針對不同名的變量類型和聲明類型檢查(TypeChecking)利用一組規(guī)則來檢查運(yùn)算分量的類型和運(yùn)算符的預(yù)期類型是否匹配。類型信息的用途查錯、確定名字需要的內(nèi)存空間、計算數(shù)組元素的地址、類型轉(zhuǎn)換、選擇正確的運(yùn)算符本節(jié)的內(nèi)容確定名字的類型，變量的存儲空間布局（相對地址）類型和聲明類型檢查(TypeChecking)類型表達(dá)式類型表達(dá)式（type

expression）：表示類型的結(jié)構(gòu)基本類型類名類型構(gòu)造算子作用于類型array[數(shù)字，類型表達(dá)式]record[字段/類型對的列表]（可以用符號表表示）函數(shù)類型構(gòu)造算子：參數(shù)類型結(jié)果類型笛卡爾積：sXt可以包含取值為類型表達(dá)式的變量類型表達(dá)式類型表達(dá)式（typeexpression）：表示類型表達(dá)式的例子類型例子元素個數(shù)為3X4的二維數(shù)組數(shù)組的元素的記錄類型該記錄類型中包含兩個字段:

x和y,其類型分別是float和integer類型表達(dá)式array[3,array[4,record[(x,float),(y,float)]]類型表達(dá)式的例子類型例子類型等價不同的語言有不同的類型等價的定義結(jié)構(gòu)等價或者它們是相同的基本類型或者是相同的構(gòu)造算子作用于結(jié)構(gòu)等價的類型而得到的。或者一個類型是另一個類型表達(dá)式的名字名等價類型名僅僅代表其自身類型等價不同的語言有不同的類型等價的定義聲明文法DTid;D|εTBC|record‘{’D‘}’Cint|floatCε|[num]C含義：D生成一系列聲明；T生成不同的類型；B生成基本類型int/float；C表示分量，生成[num]序列；注意record中包含了各個字段的聲明。字段聲明和變量聲明的文法一致。聲明文法局部變量的存儲布局變量的類型可以確定變量需要的內(nèi)存即類型的寬度可變大小的數(shù)據(jù)結(jié)構(gòu)只需要考慮指針函數(shù)的局部變量總是分配在連續(xù)的區(qū)間；因此給每個變量分配一個相對于這個區(qū)間開始處的相對地址變量的類型信息保存在符號表中；局部變量的存儲布局變量的類型可以確定變量需要的內(nèi)存計算T的類型和寬度的SDT綜合屬性：type,width全局變量t和w用于將類型和寬度信息從B傳遞到Cε相當(dāng)于C的繼承屬性，因?yàn)榭偸峭ㄟ^拷貝來傳遞，所以在SDT中只賦值一次。也可以把t和w替換為C.t和C.w計算T的類型和寬度的SDT綜合屬性：type,widthSDT運(yùn)行的例子輸入：int[2][3]SDT運(yùn)行的例子輸入：int[2][3]作用域和符號表在具有語句塊概念的編程語言中，標(biāo)識符x在最內(nèi)層的x聲明的作用域中。每個作用域?qū)?yīng)于一個符號表；多個符號表形成樹狀結(jié)構(gòu)。在語義分析時，通過棧來存放當(dāng)前符號表及其祖先。作用域和符號表在具有語句塊概念的編程語言中，標(biāo)識符x在最內(nèi)層聲明序列的SDT（1）在處理一個過程/函數(shù)時，局部變量應(yīng)該放到單獨(dú)的符號表中去；這些變量的內(nèi)存布局獨(dú)立相對地址從0開始；假設(shè)變量的放置和聲明的順序相同；SDT的處理方法變量offset記錄當(dāng)前可用的相對地址；每“分配”一個變量，offset的值增加相應(yīng)的值top.put(id.lexeme,T.type,offset)在當(dāng)前符號表(位于棧頂)中創(chuàng)建符號表條目，記錄標(biāo)識符的類型，偏移量聲明序列的SDT（1）在處理一個過程/函數(shù)時，局部變量應(yīng)該放聲明序列的SDT（2）我們可以把offset看作D的繼承屬性D.offset表示D中第一個變量的相對地址P{D.offset=0}DDTid;{D1.offset=D.offset+T.width;}D1聲明序列的SDT（2）我們可以把offset看作D的繼承屬性記錄字段的處理Trecord‘{‘D‘}’為每個記錄創(chuàng)建單獨(dú)的符號表首先創(chuàng)建一個新的符號表，壓到棧頂；然后處理對應(yīng)于字段聲明的D，字段都被加入到新符號表中；最后根據(jù)棧頂?shù)姆柋順?gòu)造出record類型表達(dá)式；符號表出棧記錄字段的處理Trecord‘{‘D‘}’表達(dá)式代碼的SDD將表達(dá)式翻譯成三地址指令序列表達(dá)式的SDD屬性code表示代碼addr表示存放表達(dá)式結(jié)果的地址（臨時變量）newTemp()可以生成一個臨時變量gen(…)生成一個指令表達(dá)式代碼的SDD將表達(dá)式翻譯成三地址指令序列增量式翻譯方案主屬性code滿足增量式翻譯的條件。注意：top.get(…)從棧頂符號表開始，逐個向下尋找id的信息。這里的gen發(fā)出相應(yīng)的代碼增量式翻譯方案主屬性code滿足增量式翻譯的條件。數(shù)組元素的尋址假設(shè)數(shù)組元素被存放在連續(xù)的存儲空間中。元素從0到n-1編號，第i個元素的地址為base+i*wK維數(shù)組的尋址：假設(shè)數(shù)組按行存放，即首先存放A[0][i2]…[ik]，然后存放A[1][i2]…[ik]，…A[i1][i2]…[ik]的地址base+i1*w1+i2*w2+…+ik*wk或者base+((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w其中：base、w、i、n的值可以從符號表中找到。數(shù)組元素的尋址假設(shè)數(shù)組元素被存放在連續(xù)的存儲空間中。新的文法產(chǎn)生式數(shù)組元素L：LL[E]|id[E]以數(shù)組元素為左部的賦值：SL=E;數(shù)組元素作為表達(dá)式中的因子：ELL的代碼計算偏移量，將結(jié)果存放于L.addr所指的臨時變量中綜合屬性array記錄了相應(yīng)數(shù)組的信息：元素類型，基地址，…新的文法產(chǎn)生式數(shù)組元素L：LL[E]|id[E]數(shù)組元素作為因子L的代碼只計算了偏移量；數(shù)組元素的存放地址應(yīng)該根據(jù)偏移量進(jìn)一步計算，即L的數(shù)組基址加上偏移量使用三地址指令x=a[i]數(shù)組元素作為因子L的代碼只計算了偏移量；數(shù)組元素作為賦值左部使用三地址指令a[i]=x數(shù)組元素作為賦值左部使用三地址指令a[i]=x例子表達(dá)式：c+a[i][j]例子表達(dá)式：c+a[i][j]類型檢查和轉(zhuǎn)換類型系統(tǒng)：給每一個組成部分賦予一個類型表達(dá)式通過一組邏輯規(guī)則來表示這些類型表達(dá)式必須滿足的條件可發(fā)現(xiàn)錯誤、提高代碼效率、確定臨時變量的大小、…類型檢查和轉(zhuǎn)換類型系統(tǒng)：類型系統(tǒng)的分類類型綜合根據(jù)子表達(dá)式的類型構(gòu)造出表達(dá)式的類型if

f的類型為st且x的類型為sthen

f(x)的類型為t類型推導(dǎo)根據(jù)語言結(jié)構(gòu)的使用方式來確定該結(jié)構(gòu)的類型：iff(x)是一個表達(dá)式then對于某些類型α,β；f的類型為αβ且x的類型為α類型系統(tǒng)的分類類型綜合類型轉(zhuǎn)換假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)該是浮點(diǎn)數(shù)x和i使用不同的二進(jìn)制表示方式浮點(diǎn)*和整數(shù)*使用不同的指令t1=(float)it2=xfmult1類型轉(zhuǎn)換比較簡單時的SDD：EE1+E2{if(E1.type=integerandE2.type=integer)E.type=integer;elseif

(E1.type=floatandE2.type=integer)E.type=float;}}這個規(guī)則沒有考慮生成類型轉(zhuǎn)換代碼類型轉(zhuǎn)換假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)類型的widening和narrowingJava的類型轉(zhuǎn)換規(guī)則編譯器自動完成的轉(zhuǎn)換為隱式轉(zhuǎn)換，程序員用代碼指定的轉(zhuǎn)換為顯式轉(zhuǎn)換。類型的widening和narrowingJava的類型轉(zhuǎn)換處理類型轉(zhuǎn)換的SDT函數(shù)Max求的是兩個參數(shù)在拓寬層次結(jié)構(gòu)中的最小公共祖先Widen函數(shù)已經(jīng)生成了必要的類型轉(zhuǎn)換代碼處理類型轉(zhuǎn)換的SDT函數(shù)Max求的是兩個參數(shù)在拓寬層次結(jié)構(gòu)中函數(shù)/運(yùn)算符的重載通過查看參數(shù)來解決函數(shù)重載問題Ef(E1)

{

if

f.typeset={siti|1<=i<=k}andE1.type=sk

then

E.type=tk

}函數(shù)/運(yùn)算符的重載通過查看參數(shù)來解決函數(shù)重載問題控制流的翻譯布爾表達(dá)式可以用于改變控制流/計算邏輯值。文法BB‖B|B&&B|!B|(B)|ErelE|true|false語義B1‖B2中B1為真時，不計算B2，整個表達(dá)式為真。因此，當(dāng)B1為真時應(yīng)該跳過B2的代碼。B1&&B2中B1為假時，不計算B2，整個表達(dá)式為假短路代碼通過跳轉(zhuǎn)指令實(shí)現(xiàn)控制流的處理邏輯運(yùn)算符本身不在代碼中出現(xiàn)；控制流的翻譯布爾表達(dá)式可以用于改變控制流/計算邏輯值。短路代碼的例子語句：if(x<100||x>200&&x!=y)x=0;代碼

if x<100 gotoL2

ifFalse x>200 gotoL1

ifFalse x!=y gotoL1L2:x=0L1:接下來的代碼注：當(dāng)x<100為真時，直接執(zhí)行x=0；所以執(zhí)行x>200時，x<100必然為假同理：計算x!=y時，x<100為假，而x>200為真短路代碼的例子語句：注：控制流語句的翻譯文法：B表示布爾表達(dá)式，S代表語句Sif(B)S1Sif(B)S1

elseS2Swhile(B)S1代碼的布局見右圖繼承屬性B.true：B為真的跳轉(zhuǎn)目標(biāo)B.false：B為假的跳轉(zhuǎn)目標(biāo)S.next：S執(zhí)行完畢時的跳轉(zhuǎn)目標(biāo)控制流語句的翻譯文法：B表示布爾表達(dá)式，S代表語句語法制導(dǎo)的定義（1）語法制導(dǎo)的定義（1）語法制導(dǎo)的定義（2）增量式生成代碼：Swhile( {begin=newlabel();B.true=newlabel;B.false=S.next;gen(begin‘:’)}

B)

{gen(B.true‘:’);S1.next=begin;}S1{gen(‘goto’begin);}語法制導(dǎo)的定義（2）增量式生成代碼：布爾表達(dá)式的控制流翻譯生成的代碼執(zhí)行時跳轉(zhuǎn)到兩個標(biāo)號之一。表達(dá)式的值為真時，跳轉(zhuǎn)到B.true表達(dá)式的值為假時，跳轉(zhuǎn)到B.falseB.true和B.false是兩個繼承屬性，根據(jù)B所在的上下文指向不同的位置如果B是if語句的條件表達(dá)式，分別指向then分支和else分支；如果沒有else分支，則指向if語句的下一條指令如果B是while語句的條件表達(dá)式，分別指向循環(huán)體的開頭和循環(huán)出口處；布爾表達(dá)式的控制流翻譯生成的代碼執(zhí)行時跳轉(zhuǎn)到兩個標(biāo)號之一。布爾表達(dá)式的代碼的SDD（1）布爾表達(dá)式的代碼的SDD（1）布爾表達(dá)式的代碼的SDD（2）布爾表達(dá)式的代碼的SDD（2）布爾表達(dá)式代碼的例子if(x<100||x>200&&x!=y)x=0;的代碼布爾表達(dá)式代碼的例子if(x<100||x>200布爾值和跳轉(zhuǎn)代碼程序中出現(xiàn)布爾表達(dá)式的目的可能就是求出它的值。比如x=a<b；處理方法：首先建立表達(dá)式的語法樹，然后根據(jù)表達(dá)式的不同角色來處理。文法：Sid=E;|if(E)S|while(E)S|SSEE‖E|E&&E|ErelE

|

…根據(jù)E的語法樹結(jié)點(diǎn)所在的位置：Swhile(E)S1中的E，生成跳轉(zhuǎn)代碼對于Sid=E，生成計算右值的代碼布爾值和跳轉(zhuǎn)代碼程序中出現(xiàn)布爾表達(dá)式的目的可能就是求出它的值回填（1）為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某些跳轉(zhuǎn)指令應(yīng)該跳轉(zhuǎn)到哪里例如：if

(B)S按照短路代碼的翻譯方法，B的代碼中有一些跳轉(zhuǎn)指令在B為假時執(zhí)行，這些跳轉(zhuǎn)指令的目標(biāo)應(yīng)該跳過S對應(yīng)的代碼。生成這些指令時，S的代碼尚未生成，因此目標(biāo)不確定通過語句的繼承屬性next來傳遞。需要第二趟處理。如何一趟處理完畢呢？回填（1）為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某回填（2）基本思想：記錄B的代碼中跳轉(zhuǎn)指令gotoS.next，if…gotoS.next的位置，但是不生成跳轉(zhuǎn)目標(biāo)。這些位置被記錄到B的綜合屬性B.falseList中；當(dāng)S.next的值已知時（即S的代碼生成完畢時），把B.nextList中的所有指令的目標(biāo)都填上這個值。回填技術(shù)：生成跳轉(zhuǎn)指令時暫時不指定跳轉(zhuǎn)目標(biāo)標(biāo)號，而是使用列表記錄這些不完整的指令；等知道正確的目標(biāo)時再填寫目標(biāo)標(biāo)號；每個列表中的指令都指向同一個目標(biāo)回填（2）基本思想：布爾表達(dá)式的回填翻譯（1）布爾表達(dá)式用于語句的控制流時，它總是在取值true時和取值false時分別跳轉(zhuǎn)到某個位置引入兩個綜合屬性truelist:包含跳轉(zhuǎn)指令（位置）的列表，這些指令在取值true時執(zhí)行falselist：包含跳轉(zhuǎn)指令（位置）的列表，這些指令在取值false時執(zhí)行輔助函數(shù)Makelist(i)Merge(p1,p2)Backpatch(p,i)布爾表達(dá)式的回填翻譯（1）布爾表達(dá)式用于語句的控制流時，它總布爾表達(dá)式的回填翻譯（2）布爾表達(dá)式的回填翻譯（2）回填和非回填方法的比較（1）B {B1.true=B.true,B1.false=newlabel();} B1|| {label(B1.false);B2.true=B.true;B2.false=B.false;} B2true/false屬性的賦值，在回填方案中對應(yīng)為相應(yīng)的list的賦值或者merge；原來生成label的地方，在回填方案中使用M來記錄相應(yīng)的代碼位置。M.inst的需要對英語相應(yīng)label的標(biāo)號；原方案生成的指令goto

B1.false，現(xiàn)在生成了gotoM.inst回填和非回填方法的比較（1）B {B1.true=B.回填和非回填方法的比較（2）回填時生成指令坯，然后加入相應(yīng)的list原來跳轉(zhuǎn)到B.true的指令，現(xiàn)在被加入到B.truelist中。回填和非回填方法的比較（2）回填時生成指令坯，然后加入相應(yīng)的布爾表達(dá)式的回填例子x<100||x>200&&x!=y布爾表達(dá)式的回填例子x<100||x>200&&x!控制轉(zhuǎn)移語句的回填S if(B)S | if(B)SelseS | while(B)S|{L}|A L LS|S語句的綜合屬性：nextlistnextlist中的跳轉(zhuǎn)指令的目標(biāo)應(yīng)該是S執(zhí)行完畢之后緊接著執(zhí)行的下一條指令的位置。考慮S是while語句、if語句的子語句時，分別應(yīng)該跳轉(zhuǎn)到哪里？控制轉(zhuǎn)移語句的回填S if(B)S | if控制轉(zhuǎn)移語句的回填（2）M的作用就是用M.instr記錄下一個指令的位置規(guī)則1中記錄了then分支的代碼起始位置；規(guī)則2中，分別記錄了then分支和else分支的起始位置；N的作用是生成goto指令坯，N.nextlist只包含這個指令的位置控制轉(zhuǎn)移語句的回填（2）M的作用就是用M.instr記錄下一控制轉(zhuǎn)移語句的回填(3)控制轉(zhuǎn)移語句的回填(3)Break、Continue的處理雖然break、continue在語法上是一個獨(dú)立的句子，但是它的代碼和外圍語句相關(guān)。方法：(break語句)跟蹤外圍語句S，生成一個跳轉(zhuǎn)指令坯將這個指令坯的位置加入到S的nextlist中。跟蹤的方法在符號表中設(shè)置break條目，令其指向外圍語句在符號表中設(shè)置指向S的nextlist的指針，然后把這個指令坯的位置直接加入到nextlist中。Break、Continue的處理雖然break、conti第六章中間代碼生成趙建華南京大學(xué)計算機(jī)系第六章中間代碼生成趙建華本章內(nèi)容中間代碼表示抽象語法樹三地址代碼：x=yopz靜態(tài)類型檢查類型檢查（typechecking）語法分析之后的抽象語法(syntax)檢查，比如break的位置，goto的目標(biāo)….中間代碼生成本章內(nèi)容中間代碼表示編譯器前端的邏輯結(jié)構(gòu)編譯器前端的邏輯結(jié)構(gòu)三地址代碼（1）每條指令右側(cè)最多有一個運(yùn)算符一般情況可以寫成x

=

yopz允許的運(yùn)算分量：名字：源程序中的名字作為三地址代碼的地址常量：源程序中出現(xiàn)或生成的常量編譯器生成的臨時變量三地址代碼（1）每條指令右側(cè)最多有一個運(yùn)算符三地址代碼（2）指令集合（1）運(yùn)算/賦值指令：x=yopz x

=

opy復(fù)制指令：x=y無條件轉(zhuǎn)移指令：gotoL條件轉(zhuǎn)移指令：ifxgotoL ifFalsexgotoL條件轉(zhuǎn)移指令：ifxrelopygotoL三地址代碼（2）指令集合（1）三地址代碼（3）指令集合（2）過程調(diào)用/返回：paramx1 //設(shè)置參數(shù)paramx2…paramxncallp,n //調(diào)用子過程p，n為參數(shù)個數(shù)帶下標(biāo)的復(fù)制指令：x=y[i]

x[i]=y注意：i表示離開數(shù)組位置第i個字節(jié)，而不是數(shù)組的第i個元素地址/指針賦值指令：x=&y x=*y *x=y三地址代碼（3）指令集合（2）例子語句doi=i+1;while(a[i]<v)；例子語句三地址指令的四元式表示方法在實(shí)現(xiàn)時，可以使用四元式/三元式/間接三元式來表示三地址指令四元式：可以實(shí)現(xiàn)為紀(jì)錄（或結(jié)構(gòu)）格式（字段）： op arg1 arg2 resultop:運(yùn)算符的內(nèi)部編碼arg1,arg2,result是地址x=y+z +yzx單目運(yùn)算符不使用arg2param運(yùn)算不使用arg2和result條件轉(zhuǎn)移/非條件轉(zhuǎn)移將目標(biāo)標(biāo)號放在result字段三地址指令的四元式表示方法在實(shí)現(xiàn)時，可以使用四元式/三元式/四元式的例子賦值語句：a=b*-c+b*-c四元式的例子賦值語句：a=b*-c+b*-c三元式表示三元式（triple） op arg1 arg2使用三元式的位置來引用三元式的運(yùn)算結(jié)果x[i]=y需要拆分為兩個三元式求x[i]的地址，然后再賦值x=yopz需要拆分為（這里？是編號）(?) op y z = x ?問題：在優(yōu)化時經(jīng)常需要移動/刪除/添加三元式，導(dǎo)致三元式的移動。三元式表示三元式（triple） op arg1 arg2三元式的例子a=b*-c+b*-c三元式的例子a=b*-c+b*-c間接三元式包含了一個指向三元式的指針的列表我們可以對這個列表進(jìn)行操作，完成優(yōu)化功能；操作時不需要修改三元式中的參數(shù)。間接三元式包含了一個指向三元式的指針的列表靜態(tài)單賦值（SSA）SSA中的所有賦值都是針對不同名的變量對于同一個變量在不同路徑中定值的情況，可以使用φ函數(shù)來合并不同的定值if(flag)x=-1;elsex=1; y=x*aif(flag)x1=-1;elsex2=1;

x3=φ(x1,x2)；y=x3*a靜態(tài)單賦值（SSA）SSA中的所有賦值都是針對不同名的變量類型和聲明類型檢查(TypeChecking)利用一組規(guī)則來檢查運(yùn)算分量的類型和運(yùn)算符的預(yù)期類型是否匹配。類型信息的用途查錯、確定名字需要的內(nèi)存空間、計算數(shù)組元素的地址、類型轉(zhuǎn)換、選擇正確的運(yùn)算符本節(jié)的內(nèi)容確定名字的類型，變量的存儲空間布局（相對地址）類型和聲明類型檢查(TypeChecking)類型表達(dá)式類型表達(dá)式（type

expression）：表示類型的結(jié)構(gòu)基本類型類名類型構(gòu)造算子作用于類型array[數(shù)字，類型表達(dá)式]record[字段/類型對的列表]（可以用符號表表示）函數(shù)類型構(gòu)造算子：參數(shù)類型結(jié)果類型笛卡爾積：sXt可以包含取值為類型表達(dá)式的變量類型表達(dá)式類型表達(dá)式（typeexpression）：表示類型表達(dá)式的例子類型例子元素個數(shù)為3X4的二維數(shù)組數(shù)組的元素的記錄類型該記錄類型中包含兩個字段:

x和y,其類型分別是float和integer類型表達(dá)式array[3,array[4,record[(x,float),(y,float)]]類型表達(dá)式的例子類型例子類型等價不同的語言有不同的類型等價的定義結(jié)構(gòu)等價或者它們是相同的基本類型或者是相同的構(gòu)造算子作用于結(jié)構(gòu)等價的類型而得到的。或者一個類型是另一個類型表達(dá)式的名字名等價類型名僅僅代表其自身類型等價不同的語言有不同的類型等價的定義聲明文法DTid;D|εTBC|record‘{’D‘}’Cint|floatCε|[num]C含義：D生成一系列聲明；T生成不同的類型；B生成基本類型int/float；C表示分量，生成[num]序列；注意record中包含了各個字段的聲明。字段聲明和變量聲明的文法一致。聲明文法局部變量的存儲布局變量的類型可以確定變量需要的內(nèi)存即類型的寬度可變大小的數(shù)據(jù)結(jié)構(gòu)只需要考慮指針函數(shù)的局部變量總是分配在連續(xù)的區(qū)間；因此給每個變量分配一個相對于這個區(qū)間開始處的相對地址變量的類型信息保存在符號表中；局部變量的存儲布局變量的類型可以確定變量需要的內(nèi)存計算T的類型和寬度的SDT綜合屬性：type,width全局變量t和w用于將類型和寬度信息從B傳遞到Cε相當(dāng)于C的繼承屬性，因?yàn)榭偸峭ㄟ^拷貝來傳遞，所以在SDT中只賦值一次。也可以把t和w替換為C.t和C.w計算T的類型和寬度的SDT綜合屬性：type,widthSDT運(yùn)行的例子輸入：int[2][3]SDT運(yùn)行的例子輸入：int[2][3]作用域和符號表在具有語句塊概念的編程語言中，標(biāo)識符x在最內(nèi)層的x聲明的作用域中。每個作用域?qū)?yīng)于一個符號表；多個符號表形成樹狀結(jié)構(gòu)。在語義分析時，通過棧來存放當(dāng)前符號表及其祖先。作用域和符號表在具有語句塊概念的編程語言中，標(biāo)識符x在最內(nèi)層聲明序列的SDT（1）在處理一個過程/函數(shù)時，局部變量應(yīng)該放到單獨(dú)的符號表中去；這些變量的內(nèi)存布局獨(dú)立相對地址從0開始；假設(shè)變量的放置和聲明的順序相同；SDT的處理方法變量offset記錄當(dāng)前可用的相對地址；每“分配”一個變量，offset的值增加相應(yīng)的值top.put(id.lexeme,T.type,offset)在當(dāng)前符號表(位于棧頂)中創(chuàng)建符號表條目，記錄標(biāo)識符的類型，偏移量聲明序列的SDT（1）在處理一個過程/函數(shù)時，局部變量應(yīng)該放聲明序列的SDT（2）我們可以把offset看作D的繼承屬性D.offset表示D中第一個變量的相對地址P{D.offset=0}DDTid;{D1.offset=D.offset+T.width;}D1聲明序列的SDT（2）我們可以把offset看作D的繼承屬性記錄字段的處理Trecord‘{‘D‘}’為每個記錄創(chuàng)建單獨(dú)的符號表首先創(chuàng)建一個新的符號表，壓到棧頂；然后處理對應(yīng)于字段聲明的D，字段都被加入到新符號表中；最后根據(jù)棧頂?shù)姆柋順?gòu)造出record類型表達(dá)式；符號表出棧記錄字段的處理Trecord‘{‘D‘}’表達(dá)式代碼的SDD將表達(dá)式翻譯成三地址指令序列表達(dá)式的SDD屬性code表示代碼addr表示存放表達(dá)式結(jié)果的地址（臨時變量）newTemp()可以生成一個臨時變量gen(…)生成一個指令表達(dá)式代碼的SDD將表達(dá)式翻譯成三地址指令序列增量式翻譯方案主屬性code滿足增量式翻譯的條件。注意：top.get(…)從棧頂符號表開始，逐個向下尋找id的信息。這里的gen發(fā)出相應(yīng)的代碼增量式翻譯方案主屬性code滿足增量式翻譯的條件。數(shù)組元素的尋址假設(shè)數(shù)組元素被存放在連續(xù)的存儲空間中。元素從0到n-1編號，第i個元素的地址為base+i*wK維數(shù)組的尋址：假設(shè)數(shù)組按行存放，即首先存放A[0][i2]…[ik]，然后存放A[1][i2]…[ik]，…A[i1][i2]…[ik]的地址base+i1*w1+i2*w2+…+ik*wk或者base+((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w其中：base、w、i、n的值可以從符號表中找到。數(shù)組元素的尋址假設(shè)數(shù)組元素被存放在連續(xù)的存儲空間中。新的文法產(chǎn)生式數(shù)組元素L：LL[E]|id[E]以數(shù)組元素為左部的賦值：SL=E;數(shù)組元素作為表達(dá)式中的因子：ELL的代碼計算偏移量，將結(jié)果存放于L.addr所指的臨時變量中綜合屬性array記錄了相應(yīng)數(shù)組的信息：元素類型，基地址，…新的文法產(chǎn)生式數(shù)組元素L：LL[E]|id[E]數(shù)組元素作為因子L的代碼只計算了偏移量；數(shù)組元素的存放地址應(yīng)該根據(jù)偏移量進(jìn)一步計算，即L的數(shù)組基址加上偏移量使用三地址指令x=a[i]數(shù)組元素作為因子L的代碼只計算了偏移量；數(shù)組元素作為賦值左部使用三地址指令a[i]=x數(shù)組元素作為賦值左部使用三地址指令a[i]=x例子表達(dá)式：c+a[i][j]例子表達(dá)式：c+a[i][j]類型檢查和轉(zhuǎn)換類型系統(tǒng)：給每一個組成部分賦予一個類型表達(dá)式通過一組邏輯規(guī)則來表示這些類型表達(dá)式必須滿足的條件可發(fā)現(xiàn)錯誤、提高代碼效率、確定臨時變量的大小、…類型檢查和轉(zhuǎn)換類型系統(tǒng)：類型系統(tǒng)的分類類型綜合根據(jù)子表達(dá)式的類型構(gòu)造出表達(dá)式的類型if

f的類型為st且x的類型為sthen

f(x)的類型為t類型推導(dǎo)根據(jù)語言結(jié)構(gòu)的使用方式來確定該結(jié)構(gòu)的類型：iff(x)是一個表達(dá)式then對于某些類型α,β；f的類型為αβ且x的類型為α類型系統(tǒng)的分類類型綜合類型轉(zhuǎn)換假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)該是浮點(diǎn)數(shù)x和i使用不同的二進(jìn)制表示方式浮點(diǎn)*和整數(shù)*使用不同的指令t1=(float)it2=xfmult1類型轉(zhuǎn)換比較簡單時的SDD：EE1+E2{if(E1.type=integerandE2.type=integer)E.type=integer;elseif

(E1.type=floatandE2.type=integer)E.type=float;}}這個規(guī)則沒有考慮生成類型轉(zhuǎn)換代碼類型轉(zhuǎn)換假設(shè)在表達(dá)式x*i中，x為浮點(diǎn)數(shù)、i為整數(shù)，則結(jié)果應(yīng)類型的widening和narrowingJava的類型轉(zhuǎn)換規(guī)則編譯器自動完成的轉(zhuǎn)換為隱式轉(zhuǎn)換，程序員用代碼指定的轉(zhuǎn)換為顯式轉(zhuǎn)換。類型的widening和narrowingJava的類型轉(zhuǎn)換處理類型轉(zhuǎn)換的SDT函數(shù)Max求的是兩個參數(shù)在拓寬層次結(jié)構(gòu)中的最小公共祖先Widen函數(shù)已經(jīng)生成了必要的類型轉(zhuǎn)換代碼處理類型轉(zhuǎn)換的SDT函數(shù)Max求的是兩個參數(shù)在拓寬層次結(jié)構(gòu)中函數(shù)/運(yùn)算符的重載通過查看參數(shù)來解決函數(shù)重載問題Ef(E1)

{

if

f.typeset={siti|1<=i<=k}andE1.type=sk

then

E.type=tk

}函數(shù)/運(yùn)算符的重載通過查看參數(shù)來解決函數(shù)重載問題控制流的翻譯布爾表達(dá)式可以用于改變控制流/計算邏輯值。文法BB‖B|B&&B|!B|(B)|ErelE|true|false語義B1‖B2中B1為真時，不計算B2，整個表達(dá)式為真。因此，當(dāng)B1為真時應(yīng)該跳過B2的代碼。B1&&B2中B1為假時，不計算B2，整個表達(dá)式為假短路代碼通過跳轉(zhuǎn)指令實(shí)現(xiàn)控制流的處理邏輯運(yùn)算符本身不在代碼中出現(xiàn)；控制流的翻譯布爾表達(dá)式可以用于改變控制流/計算邏輯值。短路代碼的例子語句：if(x<100||x>200&&x!=y)x=0;代碼

if x<100 gotoL2

ifFalse x>200 gotoL1

ifFalse x!=y gotoL1L2:x=0L1:接下來的代碼注：當(dāng)x<100為真時，直接執(zhí)行x=0；所以執(zhí)行x>200時，x<100必然為假同理：計算x!=y時，x<100為假，而x>200為真短路代碼的例子語句：注：控制流語句的翻譯文法：B表示布爾表達(dá)式，S代表語句Sif(B)S1Sif(B)S1

elseS2Swhile(B)S1代碼的布局見右圖繼承屬性B.true：B為真的跳轉(zhuǎn)目標(biāo)B.false：B為假的跳轉(zhuǎn)目標(biāo)S.next：S執(zhí)行完畢時的跳轉(zhuǎn)目標(biāo)控制流語句的翻譯文法：B表示布爾表達(dá)式，S代表語句語法制導(dǎo)的定義（1）語法制導(dǎo)的定義（1）語法制導(dǎo)的定義（2）增量式生成代碼：Swhile( {begin=newlabel();B.true=newlabel;B.false=S.next;gen(begin‘:’)}

B)

{gen(B.true‘:’);S1.next=begin;}S1{gen(‘goto’begin);}語法制導(dǎo)的定義（2）增量式生成代碼：布爾表達(dá)式的控制流翻譯生成的代碼執(zhí)行時跳轉(zhuǎn)到兩個標(biāo)號之一。表達(dá)式的值為真時，跳轉(zhuǎn)到B.true表達(dá)式的值為假時，跳轉(zhuǎn)到B.falseB.true和B.false是兩個繼承屬性，根據(jù)B所在的上下文指向不同的位置如果B是if語句的條件表達(dá)式，分別指向then分支和else分支；如果沒有else分支，則指向if語句的下一條指令如果B是while語句的條件表達(dá)式，分別指向循環(huán)體的開頭和循環(huán)出口處；布爾表達(dá)式的控制流翻譯生成的代碼執(zhí)行時跳轉(zhuǎn)到兩個標(biāo)號之一。布爾表達(dá)式的代碼的SDD（1）布爾表達(dá)式的代碼的SDD（1）布爾表達(dá)式的代碼的SDD（2）布爾表達(dá)式的代碼的SDD（2）布爾表達(dá)式代碼的例子if(x<100||x>200&&x!=y)x=0;的代碼布爾表達(dá)式代碼的例子if(x<100||x>200布爾值和跳轉(zhuǎn)代碼程序中出現(xiàn)布爾表達(dá)式的目的可能就是求出它的值。比如x=a<b；處理方法：首先建立表達(dá)式的語法樹，然后根據(jù)表達(dá)式的不同角色來處理。文法：Sid=E;|if(E)S|while(E)S|SSEE‖E|E&&E|ErelE

|

…根據(jù)E的語法樹結(jié)點(diǎn)所在的位置：Swhile(E)S1中的E，生成跳轉(zhuǎn)代碼對于Sid=E，生成計算右值的代碼布爾值和跳轉(zhuǎn)代碼程序中出現(xiàn)布爾表達(dá)式的目的可能就是求出它的值回填（1）為布爾表達(dá)式和控制流語句生成目標(biāo)代碼的關(guān)鍵問題：某些跳轉(zhuǎn)指令應(yīng)該跳轉(zhuǎn)到哪里例如：if

(B)S按照短路代碼的翻譯方法，B的代碼中有一些跳轉(zhuǎn)指令在B為假時執(zhí)行，這些跳轉(zhuǎn)指令的目標(biāo)應(yīng)該跳過S對應(yīng)的代碼。生成這些指令時，S的代碼尚未生成，因此目標(biāo)不確定通過語句的繼承屬性nex