語(yǔ)義分析和中間代碼生成講義

語(yǔ)義分析和中間代碼生成講義第7章

語(yǔ)義分析與中間代碼生成7.1中間代碼的形式7.2聲明語(yǔ)句的翻譯7.3賦值語(yǔ)句的翻譯7.4類型檢查7.5控制結(jié)構(gòu)的翻譯7.6回填7.7switch語(yǔ)句的翻譯7.8過(guò)程調(diào)用和返回語(yǔ)句的翻譯7.9輸入輸出語(yǔ)句的翻譯7.10本章小結(jié)2023/3/1927.1中間代碼的形式中間代碼的作用過(guò)渡：經(jīng)過(guò)語(yǔ)義分析被譯成中間代碼序列中間代碼的形式中間語(yǔ)言的語(yǔ)句中間代碼的優(yōu)點(diǎn)形式簡(jiǎn)單、語(yǔ)義明確、獨(dú)立于目標(biāo)語(yǔ)言便于編譯系統(tǒng)的實(shí)現(xiàn)、移植、代碼優(yōu)化常用的中間代碼語(yǔ)法樹(shù)節(jié))逆波蘭表示、三地址碼(三元式和四元式)、DAG圖表示2023/3/1937.1.1逆波蘭表示中綴表達(dá)式的計(jì)算順序不是運(yùn)算符出現(xiàn)的自然順序，而是根據(jù)運(yùn)算符間的優(yōu)先關(guān)系來(lái)確定的，因此，從中綴表達(dá)式直接生成目標(biāo)代碼一般比較麻煩。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了后綴表示法，其優(yōu)點(diǎn)為：表達(dá)式的運(yùn)算順序就是運(yùn)算符出現(xiàn)的順序，它不需要使用括號(hào)來(lái)指示運(yùn)算順序。2023/3/1947.1.1逆波蘭表示例7.1下面給出的是一些表達(dá)式的中綴、前綴和后綴表示。 中綴表示 前綴表示 后綴表示 a+b +ab ab+ a*(b+c) *a+bc abc+* (a+b)*(c+d) *+ab+cd ab+cd+* a:=a*b+c*d :=a+*ab*cd abc*bd*+:=2023/3/1957.1.2三地址碼所謂三地址碼，是指這種代碼的每條指令最多只能包含三個(gè)地址，即兩個(gè)操作數(shù)地址和一個(gè)結(jié)果地址。如x+y*z三地址碼為：t1:=y*zt2:=x+t1三地址碼中地址的形式：名字、常量、編譯器生成的臨時(shí)變量。2023/3/1967.1.2三地址碼例7.2賦值語(yǔ)句a:=(-b)*(c+d)-(c+d)的三地址碼如圖7.1所示t1:=minusbt2:=c+dt3:=t1*t2t4:=c+dt5:=t3-t4a:=t5圖7.1a:=(-b)*(c+d)-(c+d)的三地址碼2023/3/1977.1.2三地址碼1．形如x:=yopz的賦值指令；2．形如x:=opy的賦值指令；3．形如x:=y的復(fù)制指令；4．無(wú)條件跳轉(zhuǎn)指令gotoL；5．形如ifxgotoL(或iffalsexgotoL)的條件跳轉(zhuǎn)指令；6．形如ifxrelopygotoL的條件跳轉(zhuǎn)指令；7．過(guò)程調(diào)用和返回使用如下的指令來(lái)實(shí)現(xiàn)：

paramx用來(lái)指明參數(shù)；

callp,n和y=callp,n用來(lái)表示過(guò)程調(diào)用和函數(shù)調(diào)用；

returny表示過(guò)程返回；8．形如x:=y[i]和x[i]:=y的變址復(fù)制指令；9．形如x:=&y、x:=*y和*x:=y的地址和指針賦值指令。2023/3/198四元式

四元式是一種比較常用的中間代碼形式，它由四個(gè)域組成，分別稱為op、arg1、arg2和result。op是一個(gè)一元或二元運(yùn)算符，arg1和arg2分別是op的兩個(gè)運(yùn)算對(duì)象，它們可以是變量、常量或編譯器生成的臨時(shí)變量，運(yùn)算結(jié)果則放入result中。圖7.2(a)圖7.1中三地址碼的四元式表示2023/3/199三元式

為了節(jié)省臨時(shí)變量的開(kāi)銷，有時(shí)也可以使用只有三個(gè)域的三元式來(lái)表示三地址碼。三元式的三個(gè)域分別稱為op，arg1和arg2，op，arg1和arg2的含義與四元式類似，區(qū)別只是arg1和arg2可以是某個(gè)三元式的編號(hào)(圖7.2(b)中用圓括號(hào)括起來(lái)的數(shù)字)，表示用該三元式的運(yùn)算結(jié)果作為運(yùn)算對(duì)象。圖7.2(b)圖7.1中三地址碼的三元式表示2023/3/1910生成三地址碼的語(yǔ)法制導(dǎo)定義2023/3/19117.1.3圖表示類似于表達(dá)式的抽象語(yǔ)法樹(shù)一樣，在dag(directedacyclicgraph)中，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)運(yùn)算符，代表表達(dá)式的一個(gè)子表達(dá)式，其子節(jié)點(diǎn)則與該運(yùn)算符的運(yùn)算對(duì)象相對(duì)應(yīng)，葉節(jié)點(diǎn)對(duì)應(yīng)的是變量或者常量，可以看成是原子運(yùn)算。利用dag可以很容易地消除公共子表達(dá)式例7.3表達(dá)式a+a*(b-c)-(b-c)/d的dag如圖7.5所示。圖7.5a+a*(b-c)-(b-c)/d的dag圖2023/3/1912生成dag的語(yǔ)法制導(dǎo)定義產(chǎn)生式語(yǔ)義規(guī)則⑴

E→E1+TE.node:=mknode('+',E1.node,T.node)⑵

E→E1-TE.node:=mknode('-',E1.node,T.node)⑶

E→TE.node:=T.node⑷

T→T1*FT.node:=mknode('*',T1.node,F.node)⑸

T→T1/FT.node:=mknode('/',T1.node,F.node)⑹

T→FT.node:=F.node⑺F→(E)F.node:=E.node⑻F→idF.node:=mkleaf(id,id.entry)⑼F→numF.node:=mkleaf(num,num.val)2023/3/19137.2聲明語(yǔ)句的翻譯聲明語(yǔ)句的作用為程序中用到的變量或常量名指定類型類型的作用類型檢查：類型檢查的任務(wù)是驗(yàn)證程序運(yùn)行時(shí)的行為是否遵守語(yǔ)言的類型的規(guī)定，也就是是否符合該語(yǔ)言關(guān)于類型的相關(guān)規(guī)則。輔助翻譯：編譯器從名字的類型可以確定該名字在運(yùn)行時(shí)所需要的存儲(chǔ)空間。在計(jì)算數(shù)組引用的地址、加入顯式的類型轉(zhuǎn)換、選擇正確版本的算術(shù)運(yùn)算符以及其它一些翻譯工作時(shí)同樣需要用到類型信息。編譯的任務(wù)在符號(hào)表中記錄被說(shuō)明對(duì)象的屬性(種別、類型、相對(duì)地址、作用域……等)，為執(zhí)行做準(zhǔn)備2023/3/19147.2.1類型表達(dá)式類型可以具有一定的層次結(jié)構(gòu)，因此用類型表達(dá)式來(lái)表示。類型表達(dá)式的定義如下：1．基本類型是類型表達(dá)式。 典型的基本類型包括boolean、char、integer、real及void等。2．類型名是類型表達(dá)式。3．將類型構(gòu)造符array應(yīng)用于數(shù)字和類型表達(dá)式所形成的表達(dá)式是類型表達(dá)式。 如果T是類型表達(dá)式，那么array(I,T)就是元素類型為T、下標(biāo)集為I的數(shù)組類型表達(dá)式。4．如果T1和T2是類型表達(dá)式，則其笛卡爾乘積T1×T2也是類型表達(dá)式。2023/3/19157.2.1類型表達(dá)式5．類型構(gòu)造符record作用于由域名和域類型所形成的表達(dá)式也是類型表達(dá)式。記錄record是一種帶有命名域的數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)構(gòu)成類型表達(dá)式。例如，下面是一段Pascal程序段：typerow=recordaddress:integer;lexeme:array[1..15]ofcharend;vartable:array[1..10]ofrow;該程序段聲明了表示下列類型表達(dá)式的類型名row：record((address×integer)×(lexeme×array(1..15,char)))2023/3/19167.2.1類型表達(dá)式6．如果T是類型表達(dá)式，那么pointer(T)也是類型表達(dá)式，表示“指向類型為T的對(duì)象的指針”。函數(shù)的類型可以用類型表達(dá)式D→R來(lái)表示?？紤]如下的Pascal聲明：functionf(a,b:char):↑integer；其定義域類型為char×char，值域類型為pointer(integer)。所以函數(shù)f的類型可以表示為如下的類型表達(dá)式：char×char→pointer(integer)7．類型表達(dá)式可以包含其值為類型表達(dá)式的變量。2023/3/19177.2.2類型等價(jià)許多類型檢查的規(guī)則都具有如下的形式：if兩個(gè)類型表達(dá)式等價(jià)then返回一種特定類型else返回type_error。如果用圖來(lái)表示類型表達(dá)式，當(dāng)且僅當(dāng)下列條件之一成立時(shí)，稱兩個(gè)類型T1和T2是結(jié)構(gòu)等價(jià)的：T1和T2是相同的基本類型；T1和T2是將同一類型構(gòu)造符應(yīng)用于結(jié)構(gòu)等價(jià)的類型上形成的；T1是表示T2的類型名。如果將類型名看作只代表它們自己的話，則上述條件中的前兩個(gè)將導(dǎo)致類型表達(dá)式的名字等價(jià)兩個(gè)類型表達(dá)式名字等價(jià)當(dāng)且僅當(dāng)它們完全相同2023/3/19187.2.3聲明語(yǔ)句的文法P→progid(input,output)D;SD→D;D|List:T|procidD;SList→List1,id|idT→integer|real|arrayCofT1|T1|recordDC→[num]C|ε

D——程序說(shuō)明部分的抽象S——程序體部分的抽象T——類型的抽象，需要表示成類型表達(dá)式C——數(shù)組下標(biāo)的抽象2023/3/1919語(yǔ)義屬性、輔助過(guò)程與全局變量的設(shè)置文法變量T(類型)的語(yǔ)義屬性type：類型(表達(dá)式)width：類型所占用的字節(jié)數(shù)輔助子程序enter：將變量的類型和地址填入符號(hào)表中array：數(shù)組類型處理子程序全局變量offset：已分配空間字節(jié)數(shù)，用于計(jì)算相對(duì)地址2023/3/19207.2.4過(guò)程內(nèi)聲明語(yǔ)句的翻譯P→{offset:=0}DD→D;DD→id:T{enter(,T.type,offset);offset:=offset+T.width}T→integer{T.type:=integer;T.width:=4}T→real{T.type:=real;T.width:=8}T→array[num]ofT1

{T.type:=array(num.val,T1.type);T.width:=num.val*T1.width}T→↑T1{T.type:=pointer(T1.type);T.width:=4}P→MDM→{offset:=0}2023/3/1921例x:real;i:integer的翻譯enter(x,real,0)offset=0offset=8T.type=realT.width=8offset=12T.type=integerT.width=4enter(i,integer,8)D→id:T{enter(,T.type,offset);offset:=offset+T.width}2023/3/1922例x:real;i:integer的翻譯P{offset:=0}D{offset:=0}D;D{offset:=0}x:T{enter(x,T.type,offset);offset:=offset+T.width};D{offset:=0}x:real{T.type:=real;T.width:=8}{enter(x,T.type,offset);offset:=offset+T.width};Dx:real{(x,real,0);offset:=8};Dx:real{(x,real,0);offset:=8};i:T{enter(,T.type,offset);offset:=offset+T.width}x:real{(x,real,0);offset:=8};i:integer{T.type:=integer;T.width:=4}{enter(i,T.type,offset);offset:=offset+T.width}x:real{(x,real,0)};i:integer{(i,integer,8);offset:=12}2023/3/19237.2.5嵌套過(guò)程中聲明語(yǔ)句的翻譯所討論語(yǔ)言的文法

Pprogid(input,output)D;S

DD;D|id:T|procidD;S

語(yǔ)義動(dòng)作用到的函數(shù)mktable(previous)：創(chuàng)建一個(gè)新的符號(hào)表；enter(table,name,type,offset)addwidth(table,width)：符號(hào)表的大??；enterproc(table,name,newtable)

在table指向的符號(hào)表中為name建立一個(gè)新表項(xiàng)；2023/3/1924Pprogid(input,output)MD;S{addwidth(top(tblptr),top(offset));pop(tblptr);pop(offset)}M

{t:=mktable(nil); push(t,tblptr);push(0,offset)}DD1;D2Dprocid;ND1;S{t:=top(tblptr);addwidth(t,top(offset));pop(tblptr);pop(offset); enterproc(top(tblptr),,t)}Did:T{enter(top(tblptr),,T.type,top(offset)); top(offset)：=top（offset）+T.width}N

{t:=mktable(top(tblptr)); push(t,tblptr);push(0,offset)}7.2.5嵌套過(guò)程中聲明語(yǔ)句的翻譯2023/3/1925programsort(input,output); vara:array[0..10]ofinteger;x:integer;procedurereadarray; vari:integer;begin…a…end；

procedureexchange(i,j:integer); beginx:=a[i];a[i]:=a[j];a[j]:=x;end；

procedurequicksort(m,n:integer); vark,v:integer; functionpartition(y,z:integer):integer; vari,j:integer; begin…a… …v……exchange(i,j)…end; begin…end；

begin…end；例一個(gè)帶有嵌套的pascal程序(圖7.11)2023/3/1926表頭空sortoffsettblptrtoptop02023/3/1927表頭空sortoffsettblptrtoptop40aarray02023/3/1928xinteger40aarray0表頭空sortoffsettblptrtoptop442023/3/1929表頭空sortreadarrary表頭offsettblptrtoptop440aarray0xinteger402023/3/1930表頭空sortreadarrary表頭offsettblptrtoptop444aarray0xinteger40iinteger02023/3/1931表頭空sortreadarrary表頭4offsettblptrtoptop44aarray0xinteger40iinteger0readarray指向readarray2023/3/1932表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭toptop02023/3/1933表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange2023/3/1934表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort02023/3/1935表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort4kinteger02023/3/1936表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger42023/3/1937表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition02023/3/1938表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition4iinteger02023/3/1939表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition8iinteger0jinteger42023/3/1940表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭8partitioniinteger0jinteger4partition2023/3/1941表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭8quicksortkinteger0vinteger4表頭8partitioniinteger0jinteger4partitionquicksort2023/3/1942表頭44空sortreadarrary表頭4offsettblptraarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭8quicksortkinteger0vinteger4表頭8partitioniinteger0jinteger4partitionquicksort2023/3/19437.2.6記錄的翻譯空間分配設(shè)置首地址和各元素的相對(duì)地址大于所需的空間(對(duì)齊)例：structNode{floatx,y;structnode*next;}node;0482023/3/19447.2.6記錄的翻譯符號(hào)表及有關(guān)表格處理為每個(gè)記錄類型單獨(dú)構(gòu)造一張符號(hào)表將域名id的信息(名字、類型、字節(jié)數(shù))填入到該記錄的符號(hào)表中所有域都處理完后，offset將保存記錄中所有數(shù)據(jù)對(duì)象的寬度總和T.type通過(guò)將類型構(gòu)造器record應(yīng)用于指向該記錄符號(hào)表的指針獲得2023/3/19457.2.6記錄的翻譯TrecordDendTrecordLDend {T.type:=record(top(tblptr)); T.width:=top(offset); pop(tblptr);pop(offset)}L

{t:=mktable(nil); push(t,tblprt);push(0,offset)}2023/3/19467.3賦值語(yǔ)句的翻譯翻譯的需求充分了解各種語(yǔ)言現(xiàn)象的語(yǔ)義包括：控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、單詞充分了解它們的實(shí)現(xiàn)方法目標(biāo)語(yǔ)言的語(yǔ)義了解中間代碼的語(yǔ)義了解運(yùn)行環(huán)境2023/3/1947輔助子程序與語(yǔ)義屬性設(shè)置輔助子程序gencode(code)，emit(code)：產(chǎn)生一條中間代碼newtemp：產(chǎn)生新的臨時(shí)變量lookup：檢查符號(hào)表中是否出現(xiàn)某名字語(yǔ)義屬性設(shè)置中間代碼序列：code地址：addr下一條四元式序號(hào)：nextquad2023/3/19487.3.1簡(jiǎn)單賦值語(yǔ)句的翻譯Sid:=E {p:=lookup(); ifpnilthen gencode(p,‘:=’,E.addr) elseerror}EE1+E2 {E.addr:=newtemp; emit(E.addr,‘:=’,E1.addr,‘+’,E2.addr)}E

E1{E.addr:=newtemp; emit(E.addr,‘:=’,‘uminus’,E1.addr)}E(E1){E.addr:=E1.addr}Eid{p:=lookup(); ifpnilthenE.addr:=pelseerror}2023/3/1949臨時(shí)名字的重用大量臨時(shí)變量的使用對(duì)優(yōu)化有利大量臨時(shí)變量會(huì)增加符號(hào)表管理的負(fù)擔(dān)也會(huì)增加運(yùn)行時(shí)臨時(shí)數(shù)據(jù)占的空間EE1+E2的動(dòng)作產(chǎn)生的代碼的一般形式為 計(jì)算E1到t1

計(jì)算E2到t2 t3:=t1+t2 (())((()())())臨時(shí)變量的生存期像配對(duì)括號(hào)那樣嵌套或并列2023/3/1950基于臨時(shí)變量生存期特征的三地址代碼x:=ab+cdef語(yǔ)句計(jì)數(shù)器c的值0$0:=ab1$1:=cd2$0:=$0+$11$1:=ef2$0:=$0$11x:=$00引入一個(gè)計(jì)數(shù)器c，它的初值為0。每當(dāng)臨時(shí)變量?jī)H作為運(yùn)算對(duì)象使用時(shí)，c減去1；每當(dāng)要求產(chǎn)生新的臨時(shí)名字時(shí)，使用$c并把c增加1。2023/3/19517.3.2數(shù)組元素的尋址數(shù)組元素引用的翻譯完成上下界檢查生成完成相對(duì)地址計(jì)算的代碼目標(biāo)x:=y[i]和y[i]:=xy為數(shù)組地址的固定部分——相當(dāng)于第1個(gè)元素的地址，i是相對(duì)地址，不是數(shù)組下標(biāo)數(shù)組說(shuō)明的翻譯符號(hào)表及有關(guān)表格(內(nèi)情向量)的處理維數(shù)、下標(biāo)上界、下標(biāo)下界、類型等首地址、需用空間計(jì)算按行存放、按列存放——影響具體元素地址的計(jì)算2023/3/1952數(shù)組元素地址計(jì)算——行優(yōu)先一維數(shù)組A[low1:up1](nk=upk-lowk+1)addr(A[i])=base+(i-low1)*w =(base-low1*w)+i*w=c+i*w二維數(shù)組A[low1:up1,low2:up2]；A[i1,i2]addr(A[i1,i2])=base+((i1-low1)*n2+(i2-low2))*w =base+(i1-low1)*n2*w+(i2-low2)*w =base-low1*n2*w-low2*w+i1*n2*w+i2*w =base-(low1*n2-low2)*w+(i1*n2+i2)*w =c+(i1*n2+i2)*wA[1,1],A[1,2],A[1,3]A[2,1],A[2,2],A[2,3]2023/3/1953數(shù)組元素地址計(jì)算的翻譯方案設(shè)計(jì)下標(biāo)變量訪問(wèn)的產(chǎn)生式

Lid[Elist]|id ElistElist,E|E為了使數(shù)組各維的長(zhǎng)度n在我們將下標(biāo)表達(dá)式合并到Elist時(shí)是可用的，需將產(chǎn)生式改寫為：

LElist]|id ElistElist,E|id[E2023/3/1954數(shù)組元素地址計(jì)算的翻譯方案設(shè)計(jì)LElist]|idElistElist,E|id[E目的使我們?cè)谡麄€(gè)下標(biāo)表達(dá)式列表Elist的翻譯過(guò)程中隨時(shí)都能知道符號(hào)表中相應(yīng)于數(shù)組名id的表項(xiàng)，從而能夠了解登記在符號(hào)表中的有關(guān)數(shù)組id的全部信息。于是我們就可以為非終結(jié)符Elist引進(jìn)一個(gè)綜合屬性Elist.array，用來(lái)記錄指向符號(hào)表中相應(yīng)數(shù)組名字表項(xiàng)的指針。2023/3/1955數(shù)組元素地址計(jì)算的翻譯方案設(shè)計(jì)屬性Elist.array，用來(lái)記錄指向符號(hào)表中相應(yīng)數(shù)組名字表項(xiàng)的指針。Elist.ndim，用來(lái)記錄Elist中下標(biāo)表達(dá)式的個(gè)數(shù)，即數(shù)組的維數(shù)。Elist.addr，用來(lái)臨時(shí)存放Elist的下標(biāo)表達(dá)式計(jì)算出來(lái)的值。函數(shù)limit(array,j)，返回nj2023/3/19567.3.3帶有數(shù)組引用的賦值語(yǔ)句的翻譯SLeft:=EEE+EE(E)ELeftLeftElist]LeftidElistElist,EElistid[E2023/3/1957賦值語(yǔ)句的翻譯模式Leftid{Left.addr:=id.addr;Left.offset:=null}Elistid[E{Elist.addr:=E.addr;Elist.ndim:=1; Elist.array:=id.addr}ElistElist1,E{t:=newtemp;m:=Elist1.ndim+1;gencode(t,‘:=’,Elist1.addr,‘’,limit(Elist1.array,m));gencode(t,‘:=’,t,‘+’,E.addr);Elist.array:=Elist1.array;Elist.addr:=t;Elist.ndim:=m}LeftElist] {Left.addr:=newtemp;Left.offset:=newtemp;gencode(Left.addr,‘:=’,base(Elist.array),‘’,invariant(Elist.array));gencode(Left.offset,‘:=’,Elist.addr,‘’,w)}i1*n2(i1*n2)+i2((i1*n2)+i2)*wbase-(low1*n2-low2)*w2023/3/1958賦值語(yǔ)句的翻譯模式ELeft{ifLeft.offset=nullthen/Left是簡(jiǎn)單變量/ E.addr:=Left.addr elsebeginE.addr:=newtemp; gencode(E.addr,‘:=’,Left.addr,‘[’,Left.offset,‘]’)end}EE1+E2{E.addr:=newtemp; gencode(E.addr,‘:=’,E1.place,‘+’,E2.addr)}E(E1){E.addr:=E1.addr}SLeft:=E{ifLeft.offset=nullthen/Left是簡(jiǎn)單變量/ gencode(Left.addr,‘:=’,E.addr) else gencode(Left.addr,‘[’,Left.offset,‘]’,‘:=’,E.addr)}((i1*n2)+i2)*w+(base-(low1*n2-low2)*w)((i1*n2)+i2)*w+(base-(low1*n2-low2)*w)2023/3/1959例：設(shè)A是一個(gè)10×20的整型數(shù)組

——w=4

S:=Left.place:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹(shù)2023/3/1960例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹(shù)t1:=y20t1:=t1+z2023/3/1961例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]yx:=A[y,z]的注釋分析樹(shù)t1:=y20t1:=t1+zt2:=baseA84t3:=4t1

2023/3/1962例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹(shù)t1:=y20t1:=t1+zt4:=t2[t3]t2:=baseA84t3:=4t1

2023/3/1963例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]yx:=A[y,z]的注釋分析樹(shù)t1:=y20t1:=t1+zt4:=t2[t3]x:=t4

t2:=baseA84t3:=4t1

2023/3/19647.4類型檢查類型檢查具有發(fā)現(xiàn)程序錯(cuò)誤的能力，為了進(jìn)行類型檢查，編譯程序需要為源程序的每個(gè)語(yǔ)法成分賦予一個(gè)類型表達(dá)式，名字的類型表達(dá)式保存在符號(hào)表中，其他語(yǔ)法成分(如表達(dá)式E或語(yǔ)句S)的類型表達(dá)式則作為文法符號(hào)的屬性保存在語(yǔ)義棧中。類型檢查的任務(wù)就是確定這些類型表達(dá)式是否符合一定的規(guī)則，這些規(guī)則的集合通常稱為源程序的類型系統(tǒng)2023/3/19657.4.1類型檢查的規(guī)則類型綜合從子表達(dá)式的類型確定表達(dá)式的類型要求名字在引用之前必須先進(jìn)行聲明iff的類型為s→tandx的類型為sthen表達(dá)式f(x)的類型為t

類型推斷根據(jù)語(yǔ)言結(jié)構(gòu)的使用方式來(lái)確定其類型經(jīng)常被用于從函數(shù)體推斷函數(shù)類型iff(x)是一個(gè)表達(dá)式then對(duì)某兩個(gè)類型變量α和β，f具有類型→βandx具有類型

2023/3/19667.4.2類型轉(zhuǎn)換x:=y+ij（x和y的類型是real，i和j的類型是integer）中間代碼t1:=iintjt2:=inttorealt1

t3:=yreal+t2

x:=t32023/3/19677.4.2類型轉(zhuǎn)換EE1+E2的語(yǔ)義子程序{E.addr:=newtempifE1.type=integerandE2.type=integerthenbegin gencode(E.addr,‘:=’,E1.addr,‘int+’,E2.addr); E.type=integerendelseifE1.type=integerandE2.type=realthenbegin u:=newtemp; gencode(u,‘:=’,‘inttoreal’,E1.addr); gencode(E.addr,‘:=’,u,‘real+’,E2.addr); E.type:=realend...}2023/3/19687.5控制結(jié)構(gòu)的翻譯高級(jí)語(yǔ)言的控制結(jié)構(gòu)順序結(jié)構(gòu)begin語(yǔ)句;…；語(yǔ)句end分支結(jié)構(gòu)if_then_else、if_then switch、case循環(huán)結(jié)構(gòu)while_do、do_whilefor、repeat_untilgoto語(yǔ)句三地址碼goton (j,_,_,n)ifxrelopygoton (jrelop,x,y,n)2023/3/19697.5.1布爾表達(dá)式的翻譯基本文法BB1orB2|B1andB2|notB1|(B1)|E1relopE2|true|false處理方式數(shù)值表示法(與算術(shù)表達(dá)式的處理類似)真：B.addr=1假：B.addr=0真假出口表示法(作為其他語(yǔ)句的條件改變控制流程，隱含著程序中的位置)真出口：B.true假出口：B.false2023/3/19707.5.1布爾表達(dá)式的翻譯aorbandnotct1:=notct2:=bandt1t3:=aort2a<b100:ifa<bgoto103101:t:=0102:goto104103:t:=11042023/3/1971用數(shù)值表示布爾值的翻譯nextquad是下一條三地址碼指令的序號(hào)，每生成一條三地址碼指令gencode便會(huì)將nextquad加1BB1orB2{B.addr:=newtemp;gencode(B.addr':='B1.addr‘or'B2.addr)}BB1andB2{B.addr:=newtemp;gencode(B.addr':='B1.addr‘a(chǎn)nd'B2.addr)}BnotB1{B.addr:=newtemp; gencode(B.addr':=''not'B1.addr)}2023/3/1972用數(shù)值表示布爾值的翻譯B(B1){B.addr:=B1.addr}BE1relopE2{B.addr:=newtemp;gencode('if‘E1.addrrelop.opE2.addr'goto'nextquad+3); gencode(B.addr':=''0');gencode('goto'nextquad+2); gencode(B.addr':=''1')}Btrue{B.addr:=newtemp;gencode(B.addr':=''1')}Bfalse{B.addr:=newtemp;gencode(B.addr':=''0')}2023/3/1973例7.8對(duì)a<borc<dande<f的翻譯100:ifa<bgoto103 107:t2:=1101:t1:=0 108:ife<fgoto111102:goto104 109:t3:=0103:t1:=1 110:goto112104:ifc<dgoto107 111:t3:=1105:t2:=0 112:t4:=t2andt3106:goto108 113:t5:=t1ort42023/3/19747.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯文法S→ifBthenS1S→ifBthenS1elseS2S→whileBdoS1S→beginSlistendSlist→Slist;S|SB是控制結(jié)構(gòu)中的布爾表達(dá)式函數(shù)newlabel返回一個(gè)新的語(yǔ)句標(biāo)號(hào)屬性B.true和B.false分別用于保存B為真和假時(shí)控制流要轉(zhuǎn)向的語(yǔ)句標(biāo)號(hào)2023/3/19757.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯翻譯S時(shí)允許控制從S.code中跳轉(zhuǎn)到緊接在S.code之后的那條三地址碼指令，但在某些情況下，緊跟S.code的指令是跳轉(zhuǎn)到某個(gè)標(biāo)號(hào)L的跳轉(zhuǎn)指令，用繼承屬性S.next可以避免從S.code中跳轉(zhuǎn)到一條跳轉(zhuǎn)指令這樣的連續(xù)跳轉(zhuǎn)。S.next的值是一個(gè)語(yǔ)句標(biāo)號(hào)，它是S的代碼執(zhí)行后應(yīng)執(zhí)行的第一個(gè)三地址碼指令的標(biāo)號(hào)。while語(yǔ)句中用S.begin保存語(yǔ)句的開(kāi)始位置

2023/3/19767.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯B.codeS1.codeB.true:...指向B.true指向B.false(a)if-thenB.codeS1.codeB.true:...指向B.true指向B.falseB.false:gotoS.nextS2.code(b)if-then-elseB.codeS1.codeB.true:...指向B.true指向B.falsegotoS.beginS.begin:(c)while-doS1.codeS2.codeS1.next:...(d)S1;S2圖7.25if-then、if-then-else和while-do語(yǔ)句的目標(biāo)代碼結(jié)構(gòu)2023/3/19777.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯SifBthenS1{B.true:=newlabel;B.false:=S.next;S1.next:=S.next;S.code:=B.code||gencode(B.true,‘:’)||S1.code}B.codeS1.codeB.true:...指向B.true指向B.false(a)if-then2023/3/19787.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯SifBthenS1elseS2{B.true:=newlabel;B.false:=newlabel;S1.next:=S.next;S2.next:=S.next;S.code:=B.code||gencode(B.true,‘:’)||S1.code||gencode(‘goto’,S.next)||gen(B.false,‘:’)||S2.code}B.codeS1.codeB.true:...指向B.true指向B.falseB.false:gotoS.nextS2.code(b)if-then-else2023/3/19797.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯SwhileBdoS1

{S.begin:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gencode(S.begin,‘:’)||B.code||gencode(B.true,‘:’)||S1.code||gencode(‘goto’,S.begin)}B.codeS1.codeB.true:...指向B.true指向B.falsegotoS.beginS.begin:(c)while-do2023/3/19807.5.2常見(jiàn)控制結(jié)構(gòu)的翻譯SS1;S2{S1.next:=newlabel;S2.next:=S.next;S.code:=S1.code||gencode(S1.next,‘:’)||S2.code}S1.codeS2.codeS1.next:...(d)S1;S22023/3/19817.5.3布爾表達(dá)式的控制流翻譯屬性(繼承屬性)B.true，B為真時(shí)控制到達(dá)的位置；B.false，B為假時(shí)控制到達(dá)的位置。a<bifa<bgotoB.truegotoB.falseB→B1orB2如果B1為真，則立即可知B為真，即B1.true與B.true相同；如果B1為假，則必須計(jì)算B2的值，令B1.false為B2的開(kāi)始B2的真假出口分別與B的真假出口相同2023/3/1982簡(jiǎn)單布爾表達(dá)式的翻譯示例

——例7.9a<borc<dande<fifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalse2023/3/19837.5.3布爾表達(dá)式的控制流翻譯BB1orB2{B1.true:=B.true;B1.false:=newlabel; B2.true=B.true;B2.false:=B.false;B.code:=B1.code||gencode(B1.false’:’)||B2.code}BB1andB2{B1.true:=newlabel;B1.false:=B.false;B2.true=B.true;B2.false:=B.false;B.code:=B1.code||gencode(B1.true’:’)||B2.code}BnotB1{B1.true:=B.false;B1.false:=B.true；

B.code:=B1.code}2023/3/19847.5.3布爾表達(dá)式的控制流翻譯B(B1){B1.true:=B.

true;B1.false:=B.false；

B.code:=B1.code}BE1relopE2{B.code:=gencode(‘if’E1.addrrelopE2.addr‘goto’B.true)；

||gencode('goto'B.false)}Btrue{B.code:=gencode('goto'B.true)}Bfalse{B.code:=gencode('goto'B.false)}2023/3/1985例7.10：翻譯下列語(yǔ)句whilea<bdo B1ifc<dthen B2S1x:=y+zelseS2x:=y-zS32023/3/1986生成的三地址代碼序列L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:t1:=y+zx:=t1

gotoL1L4:t2:=y-zx:=t2gotoL1Lnext:B1.codeB2.codeS1.codeS2.codeS3.codewhilea<bdoifc<dthenx:=y+zelsex:=y-z2023/3/19877.5.4混合模式的布爾表達(dá)式翻譯EE1relopE2│E1+E2│E1andE2│idE1+E2、id產(chǎn)生算術(shù)結(jié)果E1relopE2、E1andE2產(chǎn)生布爾值E1andE2：E1和E2必須都是布爾型的引入語(yǔ)義屬性E.type:arith或者boolE.true,E.falseE.addr2023/3/19887.5.4混合模式的布爾表達(dá)式翻譯EE1relopE2{E.code:=E1.code||E2.code||gencode(‘if’E1.addrrelopE2.addr‘goto‘E.true)||

gencode('goto'E.false)}2023/3/1989混合模式的布爾表達(dá)式翻譯EE1+E2{E.type:=arith;ifE1.type=arithandE2.type=ariththenbeginE.addr:=newtemp;E.code:=E1.code||E2.code||gencode(E.addr'='E1.addr'+'E2.addr)endelseifE1.type=arithandE2.type=boolthenbeginE.addr:=newtemp;E2.true:=newlabel;2.false:=newlabel;E.code:=E1.code||E2.code||gencode(E2.true':'E.addr':='E1.addr+1)||gencode('goto'nextstate+2)||gencode(E2.false':'E.addr':='E1.addr)elseif…….}2023/3/1990混合模式布爾表達(dá)式的翻譯示例

——例如：4+a>b-canddt1=4+at2=b-cift1>t2gotoL1gotoLfalseL1:ifdgotoLtruegotoLfalse2023/3/19917.6回填兩遍掃描從給定的輸入構(gòu)造出一棵語(yǔ)法樹(shù)；對(duì)語(yǔ)法樹(shù)按深度優(yōu)先進(jìn)行遍歷,在遍歷過(guò)程中執(zhí)行語(yǔ)法制導(dǎo)定義中給出的翻譯動(dòng)作

效率較低2023/3/19927.6回填一遍掃描問(wèn)題：生成跳轉(zhuǎn)語(yǔ)句時(shí)可能不知道要轉(zhuǎn)向指令的標(biāo)號(hào)先產(chǎn)生暫時(shí)沒(méi)有填寫目標(biāo)標(biāo)號(hào)的轉(zhuǎn)移指令 對(duì)于每一條這樣的指令作適當(dāng)?shù)挠涗?，建一個(gè)鏈表一旦確定了目標(biāo)標(biāo)號(hào),再將它“回填”到相應(yīng)的指令中E.truelistE.falselist2023/3/19937.6回填翻譯模式用到如下三個(gè)函數(shù)：

1．makelist(i)：創(chuàng)建一個(gè)只包含i的新表，i

是四元式數(shù)組的一個(gè)索引(下標(biāo))，或者說(shuō)

i是四元式代碼序列的一個(gè)標(biāo)號(hào)。

2．merge(p1,p2)：合并由指針p1和p2指向的兩個(gè)表并且返回一個(gè)指向合并后的表的指針。

3．backpatch(p，i)：把i作為目標(biāo)標(biāo)號(hào)回填到

p所指向的表中的每一個(gè)轉(zhuǎn)移指令中去。此處的“表”都是為“回填”所拉的鏈2023/3/19947.6.1布爾表達(dá)式的回填式翻譯BB1orMB2{backpatch(B1.falselist,M.quad);B.truelist:=merge(B1.truelist,B2.truelist);B.falselist:=B2.falselist}M

ε{M.quad:=nextquad}B1的代碼B.falselistB1.falselistB2.falselistB2的代碼M.quadB1.truelistB2.truelistB.truelistor2023/3/19957.6.1布爾表達(dá)式的回填式翻譯BB1andMB2{backpatch(B1.truelist,M.quad);B.truelist:=B2.truelist;

B.falselist:=merge(B1.falselist,B2.falselist);}B1的代碼B.truelistB1.truelistB2.truelistB2的代碼M.quadB1.falselistB2.falselistB.falselistand2023/3/19967.6.1布爾表達(dá)式的回填式翻譯BnotB1{B.truelist:=B1.falselist;B.falselist:=B1.truelist;}B(B1){B.truelist:=B1.truelist;B.falselist:=B1.falselist;}2023/3/19977.6.1布爾表達(dá)式的回填式翻譯BE1relopE2{B.truelist:=makelist(nextquad);B.falselist:=makelist(nextquad+1);gencode(‘if’E1.addrrelopE2.addr‘goto-’);gencode(‘goto-’)}2023/3/19987.6.1布爾表達(dá)式的回填式翻譯Btrue{B.truelist:=makelist(nextquad);gencode(‘goto-’)}Bfalse{B.falselist:=makelist(nextquad);gencode(‘goto-’)}2023/3/1999例7.11B.t={100,104}B.f={103,105}M.q:={102}B.t:={100}B.f:={101}<B.t={104}B.f={103,105}B.t={102}B.f={103}B.t={104}B.f={105}圖7.27a<borc<dande<f的注釋分析樹(shù)aborεM.q:={104}andε<cd<ef100:ifa<bgoto–101:goto-102:ifc<dgoto104103:goto–104:ife<fgoto–105:goto-100:ifa<bgoto–101:goto-102:ifc<dgoto–103:goto-104:ife<fgoto–105:goto-100:ifa<bgoto–101:goto102102:ifc<dgoto104103:goto–104:ife<fgoto–105:goto-M.q:={102}M.q:={104}B.t代表B.truelistB.f代表B.falselistM.q代表M.quad2023/3/191007.6.2常見(jiàn)控制結(jié)構(gòu)的回填式翻譯SifBthenMS1 |ifBthenM1S1NelseM2S2 |whileM1BdoM2S1 |S1;MS2

Mε{M.qu