編譯原理課件：第六章 類(lèi) 型 檢 查

編譯原理Compilers–Principles,TechniquesandTools第六章類(lèi)型檢查

本章內(nèi)容靜態(tài)檢查中最典型的部分—類(lèi)型檢查設(shè)計(jì)語(yǔ)法制導(dǎo)的類(lèi)型檢查器忽略其它的靜態(tài)檢查：控制流檢查、唯一性檢查、關(guān)聯(lián)名字檢查語(yǔ)法分析器類(lèi)型檢查器中間代碼生成器語(yǔ)法樹(shù)語(yǔ)法樹(shù)中間表示記號(hào)流簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——聲明語(yǔ)句D

D;DD

id

:T {addtype(id.entry,T.type)}

addtype：把類(lèi)型信息填入符號(hào)表簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——聲明語(yǔ)句D

D;DD

id

:T {addtype(id.entry,T.type)}T

boolean {T.type=boolean}T

integer

{T.type=integer}T

T1

{T.type=pointer(T1.type)}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——聲明語(yǔ)句D

D;DD

id

:T {addtype(id.entry,T.type)}T

boolean {T.type=boolean}T

integer

{T.type=integer}T

T1

{T.type=pointer(T1.type)}T

array

[num]ofT1

{T.type=array(num.val,T1.type)}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——聲明語(yǔ)句D

D;DD

id

:T {addtype(id.entry,T.type)}T

boolean {T.type=boolean}T

integer

{T.type=integer}T

T1

{T.type=pointer(T1.type)}T

array

[num]ofT1

{T.type=array(num.val,T1.type)}T

T1

‘’T2

{T.type=T1.typeT2.type}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——表達(dá)式E

truth

{E.type=boolean}E

num

{E.type=integer}E

id

{E.type=lookup(id.entry)}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——表達(dá)式E

truth

{E.type=boolean}E

num

{E.type=integer}E

id

{E.type=lookup(id.entry)}E

E1

modE2

{E.type=ifE1.type==integerand

E2.type==integertheninteger

elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——表達(dá)式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——表達(dá)式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}E

E1{E.type=ifE1.type==pointer(t)thent elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——表達(dá)式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}E

E1{E.type=ifE1.type==pointer(t)thent elsetype_error}E

E1(E2){E.type=ifE2.type==sand

E1.type==s

tthent

elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——語(yǔ)句S

id:=E{if

(id.type==E.type&&E.type

{boolean,integer})S.type=void;

elseS.type=type_error;}

簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——語(yǔ)句S

id:=E{if

(id.type==E.type&&E.type

{boolean,integer})S.type=void;

elseS.type=type_error;}

S

ifEthenS1{S.type=ifE.type==boolean thenS1.type elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——語(yǔ)句S

whileEdoS1

{S.type=ifE.type==booleanthenS1.type

elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——語(yǔ)句S

whileEdoS1

{S.type=ifE.type==booleanthenS1.type

elsetype_error}S

S1;S2

{S.type=ifS1.type==voidand S2.type==voidthenvoid

elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型檢查——程序P

D;S

{P.type=ifS.type==voidthenvoid elsetype_error}簡(jiǎn)單類(lèi)型檢查器的說(shuō)明類(lèi)型轉(zhuǎn)換E

E1opE2{E.type= ifE1.type==integerandE2.type==integer theninteger elseifE1.type==integerandE2.type==real thenreal elseifE1.type==realandE2.type==integer thenreal

elseifE1.type==realandE2.type==real thenreal elsetype_error}第七章中間代碼生成本章內(nèi)容介紹幾種常用的中間表示：后綴表示、圖形表示和三地址代碼用語(yǔ)法制導(dǎo)定義和翻譯方案來(lái)說(shuō)明源語(yǔ)言的各種構(gòu)造怎樣被翻譯成中間形式分析器靜態(tài)檢查器中間代碼生成器中間代碼記號(hào)流代碼生成器7.1

中間語(yǔ)言7.1.1后綴表示

EE

opE|uopE|(E)|id|num表達(dá)式E的后綴表示可以如下歸納定義：

表達(dá)式E 后綴式E

id

id

num num

E1opE2 E1E2

op uopE Euop

(E) E7.1

中間語(yǔ)言后綴表示不需要括號(hào) (8

5)+2的后綴表示是852+

后綴表示的最大優(yōu)點(diǎn)是便于計(jì)算機(jī)處理表達(dá)式 計(jì)算棧 輸入串

852+

8 52+ 85 2+ 3 2+ 32 +

57.1

中間語(yǔ)言7.1.2

圖形表示語(yǔ)法樹(shù)是一種圖形化的中間表示有向無(wú)環(huán)圖也是一種中間表示assigna++bcduminus(b)DAGassigna++bcdcduminus(a)語(yǔ)法樹(shù)

a=(b+cd)+cd的圖形表示7.1

中間語(yǔ)言構(gòu)造賦值語(yǔ)句語(yǔ)法樹(shù)的語(yǔ)法制導(dǎo)定義

產(chǎn)

生

式

語(yǔ)

義

規(guī)

則Sid=E

S.nptr=mkNode(‘a(chǎn)ssign’,mkLeaf(id,id.entry),E.nptr)E

E1+E2

E.nptr=mkNode(‘+’,E1.nptr,E2.nptr)E

E1E2E.nptr=mkNode(‘’,E1.nptr,E2.nptr)E

E1E.nptr=mkUNode(‘uminus’,E1.nptr)E(E1)E.nptr=E1.nptr

FidE.nptr=mkLeaf(id,id.entry)7.1

中間語(yǔ)言7.1.3三地址代碼一般形式：x=yopz例表達(dá)式x+y

z翻譯成的三地址語(yǔ)句序列是 t1=y

z

t2=x+t1

7.1

中間語(yǔ)言三地址代碼是語(yǔ)法樹(shù)或DAG的一種線性表示例 a=(b+cd)+cd 語(yǔ)法樹(shù)的代碼 t1=b

t2=c

d

t3=t1+t2

t4=c

d

t5=t3+t4

a=t5assigna++bcdcduminus7.1

中間語(yǔ)言三地址代碼是語(yǔ)法樹(shù)或DAG的一種線性表示例 a=(b+cd)+cd 語(yǔ)法樹(shù)的代碼 DAG的代碼 t1=b t1=b

t2=c

d t2=c

d

t3=t1+t2 t3=t1+t2

t4=c

d t4=t3+t2

t5=t3+t4 a=t4

a=t5assigna++bcduminus7.1

中間語(yǔ)言本書(shū)常用的三地址語(yǔ)句賦值語(yǔ)句x=yopz， x=opy， x=y無(wú)條件轉(zhuǎn)移gotoL條件轉(zhuǎn)移ifxrelop

ygotoL過(guò)程調(diào)用paramx

和callp,n過(guò)程返回

returny索引賦值x=y[i]和x[i]=y地址和指針賦值x=&y，x=y和x=y7.2

聲明語(yǔ)句本節(jié)介紹為局部名字建立符號(hào)表?xiàng)l目為它分配存儲(chǔ)單元符號(hào)表中包含名字的類(lèi)型和分配給它的存儲(chǔ)單元的相對(duì)地址等信息7.2

聲明語(yǔ)句7.2.1

過(guò)程中的聲明7.2

聲明語(yǔ)句計(jì)算被聲明名字的類(lèi)型和相對(duì)地址P {offset=0} D;SD

D;D

Did:T {enter(id.lexeme,T.type,offset); offset=offset+T.width}Tinteger {T.type=integer;T.width=4}Treal{T.type=real;T.width=8}Tarray[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}7.2

聲明語(yǔ)句計(jì)算被聲明名字的類(lèi)型和相對(duì)地址P {offset=0} D;SD

D;D

Did:T {enter(id.lexeme,T.type,offset); offset=offset+T.width}Tinteger {T.type=integer;T.width=4}Treal{T.type=real;T.width=8}Tarray[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}7.2

聲明語(yǔ)句7.2.2作用域信息的保存所討論語(yǔ)言的文法

P

D;S DD;D|id:T|

procid;D;S

sortvara:…;x:…;

readarrayvari:…;

exchange

quicksortvark,v:…;

partition

vari,j:…;7.2

聲明語(yǔ)句exchangereadarrayxa表頭空sortquicksort指向readarraypartitionvk表頭quicksortreadarrayi表頭exchange表頭指向exchangepartition

sort

readarray

exchange

quicksort

partition符號(hào)表實(shí)例

7.2

聲明語(yǔ)句符號(hào)表的特點(diǎn)各過(guò)程有各自的符號(hào)表符號(hào)表之間有雙向鏈構(gòu)造符號(hào)表時(shí)需要符號(hào)表?xiàng)?gòu)造符號(hào)表需要活動(dòng)記錄棧語(yǔ)義動(dòng)作用到的函數(shù)mkTable(previous)enter(table,name,type,offset)

addWidth(table,width)enterProc(table,name,newtable)sortvara:…;x:…;

readarrayvari:…;

exchange

quicksortvark,v:…;

partition

vari,j:…;7.2

聲明語(yǔ)句P

MD;S

{addWidth(top(tblptr),top(offset));

pop(tblptr);pop(offset)}M

{t=mkTable(nil); push(t,tblprt);push(0,offset)}D

D1;D2Dprocid;ND1;S{t=top(tblptr); addWidth(t,top(offset));pop(tblptr);pop(offset); enterProc(top(tblptr),id.lexeme,t)}Did:T{enter(top(tblptr),id.lexeme,T.type,top(offset)); top(offset)=top(offset)+T.width}N

{t=mkTable(top(tblptr)); push(t,tblptr);push(0,offset)}7.2

聲明語(yǔ)句P

MD;S

{addWidth(top(tblptr),top(offset));

pop(tblptr);pop(offset)}M

{t=mkTable(nil); push(t,tblprt);push(0,offset)}D

D1;D2Dprocid;ND1;S{t=top(tblptr); addWidth(t,top(offset));pop(tblptr);pop(offset); enterProc(top(tblptr),id.lexeme,t)}Did:T{enter(top(tblptr),id.lexeme,T.type,top(offset)); top(offset)=top(offset)+T.width}N

{t=mkTable(top(tblptr)); push(t,tblptr);push(0,offset)}7.2

聲明語(yǔ)句P

MD;S

{addWidth(top(tblptr),top(offset));

pop(tblptr);pop(offset)}M

{t=mkTable(nil); push(t,tblprt);push(0,offset)}D

D1;D2Dprocid;ND1;S{t=top(tblptr); addWidth(t,top(offset));pop(tblptr);pop(offset); enterProc(top(tblptr),id.lexeme,t)}Did:T{enter(top(tblptr),id.lexeme,T.type,top(offset)); top(offset)=top(offset)+T.width}N

{t=mkTable(top(tblptr)); push(t,tblptr);push(0,offset)}7.3

賦值語(yǔ)句7.3.1符號(hào)表中的名字Sid:=E {p=lookup(id.lexeme); ifp!=

nilthen emit(p,‘=’,E.place) elseerror}E

E1+E2

{E.place=newTemp();

emit(E.place,‘=’,E1.place,‘+’,E2.place)}7.3

賦值語(yǔ)句7.3.1符號(hào)表中的名字E

E1{E.place=newTemp(); emit(E.place,‘=’,‘uminus’,E1.place)}E(E1){E.place=E1.place}Eid{p=lookup(id.lexeme); ifp!=

nilthenE.place=pelseerror}第八章代碼生成本章內(nèi)容一個(gè)簡(jiǎn)單的代碼生成算法涉及存儲(chǔ)管理，指令選擇，寄存器分配和計(jì)算次序選擇等基本問(wèn)題前端代碼優(yōu)化器中間代碼源程序代碼生成器中間代碼目標(biāo)程序8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題8.1.1

目標(biāo)程序絕對(duì)機(jī)器語(yǔ)言程序目標(biāo)程序?qū)⒀b入到內(nèi)存的固定地方可重定位目標(biāo)模塊代碼中含重定位信息，以適應(yīng)重定位要求8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題8.1.1

目標(biāo)程序絕對(duì)機(jī)器語(yǔ)言程序目標(biāo)程序?qū)⒀b入到內(nèi)存的固定地方可重定位目標(biāo)模塊代碼中含重定位信息，以適應(yīng)重定位要求允許程序模塊分別編譯調(diào)用其它先前編譯好的程序模塊8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題8.1.1

目標(biāo)程序絕對(duì)機(jī)器語(yǔ)言程序可重定位目標(biāo)模塊代碼中含重定位信息，以適應(yīng)重定位要求允許程序模塊分別編譯調(diào)用其它先前編譯好的程序模塊匯編語(yǔ)言程序免去編譯器重復(fù)匯編器的工作從教學(xué)角度，增加可讀性8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題8.1.2

指令的選擇目標(biāo)機(jī)器指令系統(tǒng)的性質(zhì)決定了指令選擇的難易程度，指令系統(tǒng)的統(tǒng)一性和完備性是重要的因素指令的速度和機(jī)器特點(diǎn)是另一些重要的因素8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題若不考慮目標(biāo)程序的效率，指令的選擇是直截了當(dāng)?shù)睦?三地址語(yǔ)句x=y+z(x，y和z都靜態(tài)分配)

MOV y, R0 /

把y裝入寄存器R0/ ADD z, R0 /

把z加到R0上/ MOV R0, x /

把R0存入x中/逐條語(yǔ)句地產(chǎn)生代碼，常常得到低質(zhì)量的代碼

8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題語(yǔ)句序列

a=b+c d=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0ADD e, R0 MOV R0, d 8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題語(yǔ)句序列

a=b+c d=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 －－多余的指令A(yù)DD e, R0 MOV R0, d 8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題語(yǔ)句序列

a=b+c d=a+e的代碼如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 －－多余的指令A(yù)DD e, R0 －－若a不再使用，MOV R0, d －－第三條指令也多余8.1

代碼生成器的設(shè)計(jì)中的問(wèn)題8.1.3寄存器分配 運(yùn)算對(duì)象處于寄存器和處于內(nèi)存相比，指令要短一些，執(zhí)行也快一些寄存器分配

選擇駐留在寄存器中的一組變量寄存器指派

挑選變量要駐留的具體寄存器8.2

目標(biāo)機(jī)器8.2.1目標(biāo)機(jī)器的指令系統(tǒng)選擇可作為幾種微機(jī)代表的寄存器機(jī)器四個(gè)字節(jié)組成一個(gè)字，有n個(gè)通用寄存器R0,R1,…,Rn-1二地址指令：

op源，目的 MOV {源傳到目的} ADD {源加到目的} SUB {目的減去源}8.2

目標(biāo)機(jī)器地址模式和它們的匯編語(yǔ)言形式及附加代價(jià)模式 形式 地址 附加代價(jià)絕對(duì)地址 M M 1寄存器 R R 0變址 c(R) c+contents(R) 1間接寄存器R contents(R) 0間接變址

c(R) contents(c+contents(R))1直接量 #c c 1

8.2

目標(biāo)機(jī)器例 指令實(shí)例

MOV R0, M

MOV 4(R0), M 4(R0)的值：contents(4+contents(R0)) MOV 4(R0), M 4(R0)的值：contents(contents(4+contents(R0)))

MOV #1, R08.2

目標(biāo)機(jī)器8.2.2指令的代價(jià)指令代價(jià)簡(jiǎn)化為 1+指令的源和目的地址模式的附加代價(jià)8.2

目標(biāo)機(jī)器地址模式和它們的匯編語(yǔ)言形式及附加代價(jià)模式 形式 地址 附加代價(jià)絕對(duì)地址 M M 1寄存器 R R 0變址 c(R) c+contents(R) 1間接寄存器R contents(R) 0間接變址

c(R) contents(c+contents(R))1直接量 #c c 1

8.2

目標(biāo)機(jī)器8.2.2指令的代價(jià)指令代價(jià)簡(jiǎn)化為 1+指令的源和目的地址模式的附加代價(jià) 指令 代價(jià)

MOVR0，R1 1

MOVR5，M 2

ADD#1，R3 2

SUB4(R0),12(R1) 38.3

基本塊和流圖怎樣為三地址語(yǔ)句序列生成目標(biāo)代碼？

先給出本節(jié)用例 prod=0; i=1; do{ prod=prod+a[i]b[i]; i=i+1; }while(i<=20);

其三地址代碼見(jiàn)右邊

(1)prod=0(2)i=1(3)t1=4i(4)t2=a[t1](5)t3=4i(6)t4=b[t3](7)t5=t2t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)ifi<=20goto(3)8.3

基本塊和流圖8.3.1基本塊基本塊連續(xù)的語(yǔ)句序列，控 制流從它的開(kāi)始進(jìn)入， 并從它的末尾離開(kāi)流圖再用有向邊表示基本塊 之間的控制流信息，就 能得到程序的流圖(1)prod=0(2)i=1(3)t1=4i(4)t2=a[t1](5)t3=4i(6)t4=b[t3](7)t5=t2t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)ifi<=20goto(3)

8.3

基本塊和流圖(1) prod=0(2) i=1(3) t1=4i(4) t2=a[t1](5) t3=4i(6) t4=b[t3](7) t5=t2t4

(8) t6=prod+t5(9) prod=t6(10) t7=i+1(11) i=t7(12) ifi<=20goto(3)(1)prod=0(2)i=1(3)t1=4i(4)t2=a[t1](5)t3=4i(6)t4=b[t3](7)t5=t2t4(8)t6=prod+t5(9)prod=t6(10)t7=i+1(11)i=t7(12)ifi<=20goto(3)B1B2一個(gè)簡(jiǎn)單的代碼生成器為單個(gè)塊生成代碼依次考慮三地址指令進(jìn)行寄存器組織和管理（最大限度地利用）執(zhí)行一個(gè)運(yùn)算時(shí)，部分或全部分量在寄存器中寄存器存放單個(gè)組塊內(nèi)的臨時(shí)變量寄存器可以存放全局值運(yùn)行時(shí)刻的存儲(chǔ)管理一個(gè)簡(jiǎn)單的代碼生成器為單個(gè)塊生成代碼每個(gè)寄存器都有寄存器描述符跟蹤哪些變量的當(dāng)前值存放在此寄存器每個(gè)變量都有地址描述符跟蹤哪些位置上可找到該變量的當(dāng)前值。位置可以指一個(gè)寄存器、一個(gè)內(nèi)存地址、一個(gè)棧中的位置t=a-b

LDR1,aLDR2,bSUBR2,R1,R2abcdR1R2R3abcdtuvata,R1bcdR2一個(gè)簡(jiǎn)單的代碼生成器代碼生成算法getReg(I)：為每個(gè)與三地址指令I(lǐng)有關(guān)的內(nèi)存位置選擇寄存器運(yùn)算的機(jī)器指令：x=y+zgetReg(x=y+z)為x、y、z選擇寄存器，記為Rx、Ry、Rz如果y不在Ry的寄存器描述符中，則生成指令“LDRy,y’”，其中y’是存放y的內(nèi)存位置之一(y’可以根據(jù)y的地址描述符得到)。z的處理跟y的處理類(lèi)似生成指令“ADDRx,Ry,Rz”一個(gè)簡(jiǎn)單的代碼生成器代碼生成算法管理寄存器和地址描述符LDR,x修改R的寄存器描述符，使之只包含x把R加入到x的地址描述符中從任何不同于x的變量的地址描述符中刪除R一個(gè)簡(jiǎn)單的代碼生成器代碼生成算法管理寄存器和地址描述符ADDRx,Ry,Rz改變Rx的寄存器描述符，使之只包含x改變x的地址描述符，使之只包含Rx從任何不同于x的變量的地址描述符中刪除Rx一個(gè)簡(jiǎn)單的代碼生成器代碼生成算法t=a-b

LDR1,aLDR2,bSUBR2,R1,R2abcdR1R2R3abcdtuvata,R1bcdR2t=a-bu=a-cv=t+ua=dd=v+u一個(gè)簡(jiǎn)單的代碼生成器代碼生成算法t=a-b

LDR1,aLDR2,bSUBR2,R1,R2abcdR1R2R3abcdtuvata,R1bcdR