語義分析與中間代碼生成

語義分析與中間代碼生成第1頁，課件共126頁，創(chuàng)作于2023年2月2023/7/202第6章

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

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

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

returny表示過程返回；8．形如x:=y[i]和x[i]:=y的變址復(fù)制指令；9．形如x:=&y、x:=*y和*x:=y的地址和指針賦值指令。第8頁，課件共126頁，創(chuàng)作于2023年2月2023/7/209四元式

四元式是一種比較常用的中間代碼形式，它由四個(gè)域組成，分別稱為op、arg1、arg2和result。op是一個(gè)一元或二元運(yùn)算符，arg1和arg2分別是op的兩個(gè)運(yùn)算對象，它們可以是變量、常量或編譯器生成的臨時(shí)變量，運(yùn)算結(jié)果則放入result中。圖6.2(a)圖6.1中三地址碼的四元式表示第9頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2010三元式

為了節(jié)省臨時(shí)變量的開銷，有時(shí)也可以使用只有三個(gè)域的三元式來表示三地址碼。三元式的三個(gè)域分別稱為op，arg1和arg2，op，arg1和arg2的含義與四元式類似，區(qū)別只是arg1和arg2可以是某個(gè)三元式的編號(圖6.2(b)中用圓括號括起來的數(shù)字)，表示用該三元式的運(yùn)算結(jié)果作為運(yùn)算對象。圖6.2(b)圖6.1中三地址碼的三元式表示第10頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2011生成三地址碼的語法制導(dǎo)定義第11頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20126.1.3圖表示類似于表達(dá)式的抽象語法樹一樣，在dag(directedacyclicgraph)中，每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)運(yùn)算符，代表表達(dá)式的一個(gè)子表達(dá)式，其子節(jié)點(diǎn)則與該運(yùn)算符的運(yùn)算對象相對應(yīng)，葉節(jié)點(diǎn)對應(yīng)的是變量或者常量，可以看成是原子運(yùn)算。利用dag可以很容易地消除公共子表達(dá)式例6.3表達(dá)式a+a*(b-c)-(b-c)/d的dag如圖6.5所示。圖6.5a+a*(b-c)-(b-c)/d的dag圖第12頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2013生成dag的語法制導(dǎo)定義產(chǎn)生式語義規(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)第13頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20146.2聲明語句的翻譯聲明語句的作用為程序中用到的變量或常量名指定類型類型的作用類型檢查：類型檢查的任務(wù)是驗(yàn)證程序運(yùn)行時(shí)的行為是否遵守語言的類型的規(guī)定，也就是是否符合該語言關(guān)于類型的相關(guān)規(guī)則。輔助翻譯：編譯器從名字的類型可以確定該名字在運(yùn)行時(shí)所需要的存儲(chǔ)空間。在計(jì)算數(shù)組引用的地址、加入顯式的類型轉(zhuǎn)換、選擇正確版本的算術(shù)運(yùn)算符以及其它一些翻譯工作時(shí)同樣需要用到類型信息。編譯的任務(wù)在符號表中記錄被說明對象的屬性(種別、類型、相對地址、作用域……等)，為執(zhí)行做準(zhǔn)備第14頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20156.2.1類型表達(dá)式類型可以具有一定的層次結(jié)構(gòu)，因此用類型表達(dá)式來表示。類型表達(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á)式。第15頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20166.2.1類型表達(dá)式5．類型構(gòu)造符record作用于由域名和域類型所形成的表達(dá)式也是類型表達(dá)式。記錄record是一種帶有命名域的數(shù)據(jù)結(jié)構(gòu)，可以用來構(gòu)成類型表達(dá)式。例如，下面是一段Pascal程序段：typerow=recordaddress:integer;lexeme:array[1..15]ofcharend;vartable:array[1..10]ofrow;該程序段聲明了表示下列類型表達(dá)式的類型名row：record(integer×array(1..15,char))第16頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20176.2.1類型表達(dá)式6．如果T是類型表達(dá)式，那么pointer(T)也是類型表達(dá)式，表示“指向類型為T的對象的指針”。函數(shù)的類型可以用類型表達(dá)式D→R來表示?？紤]如下的Pascal聲明：functionf(a,b:char):↑integer；其定義域類型為char×char，值域類型為pointer(integer)。所以函數(shù)f的類型可以表示為如下的類型表達(dá)式：char×char→pointer(integer)7.類型表達(dá)式可以包含其值為類型表達(dá)式的變量。第17頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20186.2.2類型等價(jià)許多類型檢查的規(guī)則都具有如下的形式：if兩個(gè)類型表達(dá)式等價(jià)then返回一種特定類型else返回type_error。如果用圖來表示類型表達(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)它們完全相同第18頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20196.2.3聲明語句的文法P→progid(input,output)D;SD→D;D|List:T|procidD;SList→List1,id|idT→integer|real|arrayCofT1|T1|recordDC→[num]C|ε

D——程序說明部分的抽象S——程序體部分的抽象T——類型的抽象，需要表示成類型表達(dá)式C——數(shù)組下標(biāo)的抽象第19頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2020語義屬性、輔助過程與全局變量的設(shè)置文法變量T(類型)的語義屬性type：類型(表達(dá)式)width：類型所占用的字節(jié)數(shù)輔助子程序enter：將變量的類型和地址填入符號表中array：數(shù)組類型處理子程序全局變量offset：已分配空間字節(jié)數(shù)，用于計(jì)算相對地址第20頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20216.2.4過程內(nèi)聲明語句的翻譯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

}第21頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2022例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}第22頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2023例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}第23頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20246.2.5嵌套過程中聲明語句的翻譯所討論語言的文法

Pprogid(input,output)D;S

DD;D|id:T|procidD;S

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

在table指向的符號表中為name建立一個(gè)新表項(xiàng)；第24頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2025Pprogid(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)}6.2.5嵌套過程中聲明語句的翻譯第25頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2026programsort(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程序(圖6.11)第26頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2027表頭空sortoffsettblptrtoptop0第27頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2028表頭空sortoffsettblptrtoptop40aarray0第28頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2029xinteger40aarray0表頭空sortoffsettblptrtoptop44第29頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2030表頭空sortreadarrary表頭offsettblptrtoptop440aarray0xinteger40第30頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2031表頭空sortreadarrary表頭offsettblptrtoptop444aarray0xinteger40iinteger0第31頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2032表頭空sortreadarrary表頭4offsettblptrtoptop44aarray0xinteger40iinteger0readarray指向readarray第32頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2033表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭toptop0第33頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2034表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange第34頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2035表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort0第35頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2036表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort4kinteger0第36頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2037表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4第37頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2038表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition0第38頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2039表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition4iinteger0第39頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2040表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition8iinteger0jinteger4第40頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2041表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭8partitioniinteger0jinteger4partition第41頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2042表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭8quicksortkinteger0vinteger4表頭8partitioniinteger0jinteger4partitionquicksort第42頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2043表頭44空sortreadarrary表頭4offsettblptraarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭8quicksortkinteger0vinteger4表頭8partitioniinteger0jinteger4partitionquicksort第43頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20446.2.6記錄的翻譯空間分配設(shè)置首地址和各元素的相對地址大于所需的空間(對齊)例：structNode{floatx,y;structnode*next;}node;048第44頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20456.2.6記錄的翻譯符號表及有關(guān)表格處理為每個(gè)記錄類型單獨(dú)構(gòu)造一張符號表將域名id的信息(名字、類型、字節(jié)數(shù))填入到該記錄的符號表中所有域都處理完后，offset將保存記錄中所有數(shù)據(jù)對象的寬度總和T.type通過將類型構(gòu)造器record應(yīng)用于指向該記錄符號表的指針獲得第45頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20466.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)}第46頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20476.3賦值語句的翻譯翻譯的需求充分了解各種語言現(xiàn)象的語義包括：控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、單詞充分了解它們的實(shí)現(xiàn)方法目標(biāo)語言的語義了解中間代碼的語義了解運(yùn)行環(huán)境第47頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2048輔助子程序與語義屬性設(shè)置輔助子程序gencode(code)，emit(code)：產(chǎn)生一條中間代碼newtemp：產(chǎn)生新的臨時(shí)變量lookup：檢查符號表中是否出現(xiàn)某名字語義屬性設(shè)置中間代碼序列：code地址：addr下一條四元式序號：nextquad第48頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20496.3.1簡單賦值語句的翻譯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}第49頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2050臨時(shí)名字的重用大量臨時(shí)變量的使用對優(yōu)化有利大量臨時(shí)變量會(huì)增加符號表管理的負(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í)變量的生存期像配對括號那樣嵌套或并列第50頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2051基于臨時(shí)變量生存期特征的三地址代碼x:=ab+cdef語句計(jì)數(shù)器c的值0

$0:=ab1

$1:=cd2

$0:=$0+$11

$1:=ef2

$0:=$0$11

x:=$00引入一個(gè)計(jì)數(shù)器c，它的初值為0。每當(dāng)臨時(shí)變量僅作為運(yùn)算對象使用時(shí)，c減去1；每當(dāng)要求產(chǎn)生新的臨時(shí)名字時(shí)，使用$c并把c增加1。第51頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20526.3.2數(shù)組元素的尋址數(shù)組元素引用的翻譯完成上下界檢查生成完成相對地址計(jì)算的代碼目標(biāo)x:=y[i]和y[i]:=xy為數(shù)組地址的固定部分——相當(dāng)于第1個(gè)元素的地址，i是相對地址，不是數(shù)組下標(biāo)數(shù)組說明的翻譯符號表及有關(guān)表格(內(nèi)情向量)的處理維數(shù)、下標(biāo)上界、下標(biāo)下界、類型等首地址、需用空間計(jì)算按行存放、按列存放——影響具體元素地址的計(jì)算第52頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2053數(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]第53頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2054數(shù)組元素地址計(jì)算的翻譯方案設(shè)計(jì)下標(biāo)變量訪問的產(chǎn)生式

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

LElist]|id ElistElist,E|id[E第54頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2055數(shù)組元素地址計(jì)算的翻譯方案設(shè)計(jì)

LElist]|idElistElist,E|id[E目的使我們在整個(gè)下標(biāo)表達(dá)式列表Elist的翻譯過程中隨時(shí)都能知道符號表中相應(yīng)于數(shù)組名id的表項(xiàng)，從而能夠了解登記在符號表中的有關(guān)數(shù)組id的全部信息。于是我們就可以為非終結(jié)符Elist引進(jìn)一個(gè)綜合屬性Elist.array，用來記錄指向符號表中相應(yīng)數(shù)組名字表項(xiàng)的指針。第55頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2056數(shù)組元素地址計(jì)算的翻譯方案設(shè)計(jì)屬性Elist.array，用來記錄指向符號表中相應(yīng)數(shù)組名字表項(xiàng)的指針。Elist.ndim，用來記錄Elist中下標(biāo)表達(dá)式的個(gè)數(shù)，即數(shù)組的維數(shù)。Elist.addr，用來臨時(shí)存放Elist的下標(biāo)表達(dá)式計(jì)算出來的值。函數(shù)limit(array,j)，返回nj第56頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20576.3.3帶有數(shù)組引用的賦值語句的翻譯SLeft:=EEE+EE(E)ELeftLeftElist]LeftidElistElist,EElistid[E第57頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2058賦值語句的翻譯模式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)*w第58頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2059賦值語句的翻譯模式ELeft

{ifLeft.offset=nullthen/Left是簡單變量/ 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是簡單變量/ 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)第59頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2060例：設(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]的注釋分析樹第60頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2061例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]的注釋分析樹t1:=y20t1:=t1+z第61頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2062例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]的注釋分析樹t1:=y20t1:=t1+zt2:=baseA84t3:=4t1

第62頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2063例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]的注釋分析樹t1:=y20t1:=t1+zt4:=t2[t3]t2:=baseA84t3:=4t1

第63頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2064例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]的注釋分析樹t1:=y20t1:=t1+zt4:=t2[t3]x:=t4

t2:=baseA84t3:=4t1

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

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

第66頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20676.4.2類型轉(zhuǎn)換x:=y+ij（x和y的類型是real，i和j的類型是integer）中間代碼t1:=iintjt2:=inttorealt1

t3:=yreal+t2

x:=t3第67頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20686.4.2類型轉(zhuǎn)換EE1+E2的語義子程序{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...}第68頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20696.5控制結(jié)構(gòu)的翻譯高級語言的控制結(jié)構(gòu)順序結(jié)構(gòu)begin語句;…；語句end分支結(jié)構(gòu)if_then_else、if_then switch、case循環(huán)結(jié)構(gòu)while_do、do_whilefor、repeat_untilgoto語句三地址碼goton (j,_,_,n)ifxrelopygoton (jrelop,x,y,n)第69頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20706.5.1布爾表達(dá)式的翻譯基本文法BB1orB2|B1andB2|notB1|(B1)|E1relopE2|true|false處理方式數(shù)值表示法(與算術(shù)表達(dá)式的處理類似)真：B.addr=1假：B.addr=0真假出口表示法(作為其他語句的條件改變控制流程，隱含著程序中的位置)真出口：B.true假出口：B.false第70頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20716.5.1布爾表達(dá)式的翻譯aorbandnotct1:=notct2:=bandt1t3:=aort2a<b100:ifa<bgoto103101:t:=0102:goto104103:t:=1104第71頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2072用數(shù)值表示布爾值的翻譯nextquad是下一條三地址碼指令的序號，每生成一條三地址碼指令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)}第72頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2073用數(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')}第73頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2074例6.8對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:goto100 113:t5:=t1ort4第74頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20756.5.2常見控制結(jié)構(gòu)的翻譯文法S→ifBthenS1S→ifBthenS1elseS2S→whileBdoS1S→beginSlistendSlist→Slist;S|SB是控制結(jié)構(gòu)中的布爾表達(dá)式函數(shù)newlabel返回一個(gè)新的語句標(biāo)號屬性B.true和B.false分別用于保存B為真和假時(shí)控制流要轉(zhuǎn)向的語句標(biāo)號第75頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20766.5.2常見控制結(jié)構(gòu)的翻譯翻譯S時(shí)允許控制從S.code中跳轉(zhuǎn)到緊接在S.code之后的那條三地址碼指令，但在某些情況下，緊跟S.code的指令是跳轉(zhuǎn)到某個(gè)標(biāo)號L的跳轉(zhuǎn)指令，用繼承屬性S.next可以避免從S.code中跳轉(zhuǎn)到一條跳轉(zhuǎn)指令這樣的連續(xù)跳轉(zhuǎn)。S.next的值是一個(gè)語句標(biāo)號，它是S的代碼執(zhí)行后應(yīng)執(zhí)行的第一個(gè)三地址碼指令的標(biāo)號。while語句中用S.begin保存語句的開始位置

第76頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20776.5.2常見控制結(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圖6.25if-then、if-then-else和while-do語句的目標(biāo)代碼結(jié)構(gòu)第77頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20786.5.2常見控制結(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-then第78頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20796.5.2常見控制結(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-else第79頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20806.5.2常見控制結(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-do第80頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20816.5.2常見控制結(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;S2第81頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20826.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的開始B2的真假出口分別與B的真假出口相同第82頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2083簡單布爾表達(dá)式的翻譯示例

——例6.9a<borc<dande<f

ifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalse第83頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20846.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}第84頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20856.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)}第85頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2086例6.10：翻譯下列語句whilea<bdo

B1ifc<dthen

B2S1

x:=y+zelseS2

x:=y-zS3第86頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2087生成的三地址代碼序列L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:t1:=y+zx:=t1

gotoL1L4:t2:=y-zx:=t2gotoL1Lnext:B1.codeB2.codeS1.codeS2.codeS3.codewhilea<bdo

ifc<dthen

x:=y+zelsex:=y-z第87頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20886.5.4混合模式的布爾表達(dá)式翻譯EE1relopE2│E1+E2│E1andE2│idE1+E2、id產(chǎn)生算術(shù)結(jié)果E1relopE2、E1andE2產(chǎn)生布爾值E1andE2：E1和E2必須都是布爾型的引入語義屬性E.type:arith或者boolE.true,E.falseE.addr第88頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20896.5.4混合模式的布爾表達(dá)式翻譯EE1relopE2{E.code:=E1.code||E2.code||gencode(‘if’E1.addrrelopE2.addr‘goto‘E.true)||

gencode('goto'E.false)}第89頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20906.5.4混合模式的布爾表達(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+1)||gencode(E2.false':'E.addr':='E1.addr)elseif…….}第90頁，課件共126頁，創(chuàng)作于2023年2月2023/7/2091混合模式布爾表達(dá)式的翻譯示例

——例如：4+a>b-candd

t1=4+at2=b-cift1>t2gotoL1gotoLfalseL1:ifdgotoLtruegotoLfalse第91頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20926.6回填兩遍掃描從給定的輸入構(gòu)造出一棵語法樹；對語法樹按深度優(yōu)先進(jìn)行遍歷,在遍歷過程中執(zhí)行語法制導(dǎo)定義中給出的翻譯動(dòng)作

效率較低第92頁，課件共126頁，創(chuàng)作于2023年2月2023/7/20936.6回填一遍掃描問題：生成跳轉(zhuǎn)語句時(shí)可能不知道要轉(zhuǎn)向指令的標(biāo)號先產(chǎn)生暫時(shí)沒有填寫目標(biāo)標(biāo)號的轉(zhuǎn)移指令 對于每一條這樣的指令作適當(dāng)?shù)挠涗?，建一個(gè)鏈表