編譯原理課件：第六章 類 型 檢 查

編譯原理Compilers–Principles,TechniquesandTools第六章類型檢查

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

D;DD

id

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

addtype：把類型信息填入符號表簡單類型檢查器的說明類型檢查——聲明語句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)}簡單類型檢查器的說明類型檢查——聲明語句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)}簡單類型檢查器的說明類型檢查——聲明語句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}簡單類型檢查器的說明類型檢查——表達(dá)式E

truth

{E.type=boolean}E

num

{E.type=integer}E

id

{E.type=lookup(id.entry)}簡單類型檢查器的說明類型檢查——表達(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}簡單類型檢查器的說明類型檢查——表達(dá)式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}簡單類型檢查器的說明類型檢查——表達(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}簡單類型檢查器的說明類型檢查——表達(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}簡單類型檢查器的說明類型檢查——語句S

id:=E{if

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

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

elseS.type=type_error;}

簡單類型檢查器的說明類型檢查——語句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}簡單類型檢查器的說明類型檢查——語句S

whileEdoS1

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

elsetype_error}簡單類型檢查器的說明類型檢查——語句S

whileEdoS1

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

elsetype_error}S

S1;S2

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

elsetype_error}簡單類型檢查器的說明類型檢查——程序P

D;S

{P.type=ifS.type==voidthenvoid elsetype_error}簡單類型檢查器的說明類型轉(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)容介紹幾種常用的中間表示：后綴表示、圖形表示和三地址代碼用語法制導(dǎo)定義和翻譯方案來說明源語言的各種構(gòu)造怎樣被翻譯成中間形式分析器靜態(tài)檢查器中間代碼生成器中間代碼記號流代碼生成器7.1

中間語言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

中間語言后綴表示不需要括號 (8

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

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

852+

8 52+ 85 2+ 3 2+ 32 +

57.1

中間語言7.1.2

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

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

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

產(chǎn)

生

式

語

義

規(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

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

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

z

t2=x+t1

7.1

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

t2=c

d

t3=t1+t2

t4=c

d

t5=t3+t4

a=t5assigna++bcdcduminus7.1

中間語言三地址代碼是語法樹或DAG的一種線性表示例 a=(b+cd)+cd 語法樹的代碼 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

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

ygotoL過程調(diào)用paramx

和callp,n過程返回

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

聲明語句本節(jié)介紹為局部名字建立符號表條目為它分配存儲單元符號表中包含名字的類型和分配給它的存儲單元的相對地址等信息7.2

聲明語句7.2.1

過程中的聲明7.2

聲明語句計算被聲明名字的類型和相對地址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

聲明語句計算被聲明名字的類型和相對地址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

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

P

D;S DD;D|id:T|

procid;D;S

sortvara:…;x:…;

readarrayvari:…;

exchange

quicksortvark,v:…;

partition

vari,j:…;7.2

聲明語句exchangereadarrayxa表頭空sortquicksort指向readarraypartitionvk表頭quicksortreadarrayi表頭exchange表頭指向exchangepartition

sort

readarray

exchange

quicksort

partition符號表實例

7.2

聲明語句符號表的特點各過程有各自的符號表符號表之間有雙向鏈構(gòu)造符號表時需要符號表棧構(gòu)造符號表需要活動記錄棧語義動作用到的函數(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

聲明語句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

聲明語句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

聲明語句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

賦值語句7.3.1符號表中的名字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

賦值語句7.3.1符號表中的名字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)容一個簡單的代碼生成算法涉及存儲管理，指令選擇，寄存器分配和計算次序選擇等基本問題前端代碼優(yōu)化器中間代碼源程序代碼生成器中間代碼目標(biāo)程序8.1

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

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

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

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

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

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

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

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

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

MOV y, R0 /

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

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

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

8.1

代碼生成器的設(shè)計中的問題語句序列

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

代碼生成器的設(shè)計中的問題語句序列

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è)計中的問題語句序列

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è)計中的問題8.1.3寄存器分配 運(yùn)算對象處于寄存器和處于內(nèi)存相比，指令要短一些，執(zhí)行也快一些寄存器分配

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

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

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

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

目標(biāo)機(jī)器地址模式和它們的匯編語言形式及附加代價模式 形式 地址 附加代價絕對地址 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ī)器例 指令實例

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指令的代價指令代價簡化為 1+指令的源和目的地址模式的附加代價8.2

目標(biāo)機(jī)器地址模式和它們的匯編語言形式及附加代價模式 形式 地址 附加代價絕對地址 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指令的代價指令代價簡化為 1+指令的源和目的地址模式的附加代價 指令 代價

MOVR0，R1 1

MOVR5，M 2

ADD#1，R3 2

SUB4(R0),12(R1) 38.3

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

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

其三地址代碼見右邊

(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ù)的語句序列，控 制流從它的開始進(jì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

基本塊和流圖(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一個簡單的代碼生成器為單個塊生成代碼依次考慮三地址指令進(jìn)行寄存器組織和管理（最大限度地利用）執(zhí)行一個運(yùn)算時，部分或全部分量在寄存器中寄存器存放單個組塊內(nèi)的臨時變量寄存器可以存放全局值運(yùn)行時刻的存儲管理一個簡單的代碼生成器為單個塊生成代碼每個寄存器都有寄存器描述符跟蹤哪些變量的當(dāng)前值存放在此寄存器每個變量都有地址描述符跟蹤哪些位置上可找到該變量的當(dāng)前值。位置可以指一個寄存器、一個內(nèi)存地址、一個棧中的位置t=a-b

LDR1,aLDR2,bSUBR2,R1,R2abcdR1R2R3abcdtuvata,R1bcdR2一個簡單的代碼生成器代碼生成算法getReg(I)：為每個與三地址指令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的處理類似生成指令“ADDRx,Ry,Rz”一個簡單的代碼生成器代碼生成算法管理寄存器和地址描述符LDR,x修改R的寄存器描述符，使之只包含x把R加入到x的地址描述符中從任何不同于x的變量的地址描述符中刪除R一個簡單的代碼生成器代碼生成算法管理寄存器和地址描述符ADDRx,Ry,Rz改變Rx的寄存器描述符，使之只包含x改變x的地址描述符，使之只包含Rx從任何不同于x的變量的地址描述符中刪除Rx一個簡單的代碼生成器代碼生成算法t=a-b

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

LDR1,aLDR2,bSUBR2,R1,R2abcdR1R2R3abcdtuvata,R1bcdR