《編譯原理》第6章-類型檢查課件

語義分析類型檢查驗證程序中執(zhí)行的每個操作是否遵守語言的類型系統(tǒng)的過程，編譯程序必須報告不符合類型系統(tǒng)的信息。控制流檢查控制流語句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的這樣的語句，則就報錯。一致性檢查在很多場合要求對象只能被定義一次。例如Pascal語言規(guī)定同一標識符在一個分程序中只能被說明一次，同一case語句的標號不能相同，枚舉類型的元素不能重復出現(xiàn)等等。相關名字檢查有時，同一名字必須出現(xiàn)兩次或多次。例如，Ada語言程序中，循環(huán)或程序塊可以有一個名字，出現(xiàn)在這些結構的開頭和結尾，編譯程序必須檢查這兩個地方用的名字是相同的。名字的作用域分析第六章類型檢查本章內(nèi)容靜態(tài)檢查中最典型的部分—類型檢查： 類型系統(tǒng)、類型檢查、多態(tài)函數(shù)、重載。忽略其它的靜態(tài)檢查：控制流檢查、唯一性檢查、相關名字檢查。每個程序設計語言都有自己的類型機制，包括類型說明和使用。

類型分析是編譯器語義分析的重要組成部分

。編譯器首先根據(jù)類型說明，確定每一個變量和常量的類型

，計算其使用存儲空間的大小，從而建立其到存儲空間的映射。進而，編譯器要確定每個語言結構的類型，以完成下面的主要任務：

（1）判定重載算符（函數(shù)）在程序中代表的是哪一個運算；（2）進行類型轉(zhuǎn)換；（3）對語言結構進行類型檢查。6類型分析

6.1.1類型表達式定義

語言結構的類型由類型表達式表示，類型表達式依賴于程序語言的類型體制。類型表達式或者是簡單類型表達式，或者是構造符作用在類型表達式上得到的類型表達式。類型表達式的定義如下：

（1）類型名和基本類型是類型表達式。integer、char、real、boolean是基本類型，所以它們是類型表達式。另外，void表示“無類型”，type_error表示“出錯類型”，它們也是類型表達式。6.1類型表達式

（2）類型構造符作用于類型表達式的結果仍然是類型表達式。類型構造符包括：

（a）數(shù)組構造符ARRAY：若T是類型表達式，則ARRAY（I,T）是類型表達式。

（b）笛卡兒乘積：若T1、T2是類型表達式，則T1T2是類型表達式，且是左結合的。

（c）記錄類型構造符RECORD：若有標識符N1、N2……、Nn與類型表達式T1、T2、…、Tn，則RECORD（（N1

T1）（N2

T2）

…

（Nn

Tn））是一個類型表達式，它表示一個記錄類型。6.1類型表達式

（d）指針類型構造符POINTER：若T是類型表達式，則POINTER（T）是類型表達式，它表示一個指針類型。

（e）函數(shù)類型構造符→：若D1、D2、…、Dn和R是類型表達式，則D1D2

……Dn→R是類型表達式，其中優(yōu)先于→，它表示從定義域類型D1

D2

…

Dn到值域類型R的映射。

（3）類型表達式中可出現(xiàn)類型變量，變量是類型表達式。6.1類型表達式

設有Pascal程序片段：

TYPEstype=RECORD

name:ARRAY[1..8]OFchar;

score:integer

END;

VAR

table:ARRAY[1..50]OFstype;

p:↑stype;

則stype代表的類型表達式

RECORD((nameARRAY(1..8,char))

(scoreinteger))

和table綁定的類型表達式ARRAY(1..50,stype)

和p綁定的類型表達式

POINTER(stype)例

例1

設有下面的函數(shù)定義

FUNCTIONf(P1:T1;P2:T2;…，Pn:Tn):T;

BEGIN……END;

和f綁定的類型表達式T1T2

…

Tn→T

例2

在函數(shù)式語言中可如下定義恒等函數(shù)

funf(x)=x

x可以是任何類型的語言結構。因此x可以是任何類型。f的類型表達式為

為類型變量，其值是任何類型表達式。例

1.樹:內(nèi)部結點是類型構造符，葉結點是基本類型，類型名或類型變量。例如，

FUNCTIONf(a,b:char):integer:………charcharpointer(integer)pointerintegercharchar類型表達式的表達方法2.位串(對類型表達式作某些限制)

例如，考慮由POINTER、→和ARRAY作為構造符的類型表達式。pointer(t)表示指向類型為t的指針，freturns(t)表示若干變元的函數(shù),其中t為函數(shù)返回對象的類型,而函數(shù)變元的類型則存放在其它地方。ARRAY(t)表示元素類型為t的數(shù)組，而數(shù)組元素的個數(shù)保存在其它地方。這樣，構造符都成為一元算符，它們作用于基本類型形成的類型表達式有非常統(tǒng)一的結構。類型表達式的表達方法類型構造符編碼

pointer01array10freturns11

基本類型編碼

boolean0000char0001integer0010real0011

類型表達式編碼

char0000000001freturns(char)0000110001pointer(freturns(char))0001110001array(pointer(freturns(char)))1001110001根據(jù)語言的類型體制和類型表達式的表示方法，分結構等價和名字等價。

結構等價

兩個類型表達式結構等價，當且僅當它們完全相同。圖6-6是測試兩個類型表達式結構等價的算法，假設類型構造符僅有數(shù)組、笛卡兒積、指針和函數(shù)，這個算法遞歸地比較兩個類型表達式的結構。

FUNCTIONeq(s,t):boolean;

BEGIN

IFs和t是相同的基本類型

THEN

return(true)

6.1.2類型表達式的等價ELSEIF(s=ARRAY(s1,s2))and(t=ARRAY(t1,t2))THEN

return(eq(s1,t1)andeq(s2,t2))

ELSEIF(s=s1s2)and(t=t1t2)THENreturn(eq(s1,t1)and(eq(s2,t2))

ELSEIF(s=POINTER(s1))and(t=POINTER(t1))THENreturn(eq(s1,t1))

ELSEIF(s=s1→s2)and(t=t1→t2)THEN

return(eq(s1,t1)andeq(s2,t2))

ELSEreturn(false)

END

類型可以命名。例如，

TYPELink=↑cell;

VARnext:Link;(6－2）

Last:Link;

P:↑cell;

q,r:↑cell;

所謂名字等價，是指兩個等價類型有同一個名字，也就是說，兩個不同的類型名表示不同的類型。在結構等價中，把類型表達式中的所有名字用它們所代表的類型表達式替換后，兩個類型表達式等價即是結構等價。

類型表達式中的名字

例6.2下面給出和聲明（6-2）中的5個變量相聯(lián)系的類型表達式。

變量類型表達式

next

Link

last

Link

p

Pointer(cell)

q

Pointer(cell)

r

Pointer(cell)

在名字等價下，變量next和last有同樣的類型;next和p的類型不相同。在結構等價下，所有五個變量都有同樣的類型。不同的語言中，通過聲明將變量標識符和類型相聯(lián)系的規(guī)則是不同的，在解釋這些規(guī)則時，結構等價和名字等價是兩個有用的概念。

例6.3

在一些Pascal的實現(xiàn)中，用隱含的類型名和每個聲明的變量標識符相聯(lián)系，如果說明中出現(xiàn)沒有名字的類型表達式，就建立一個隱含的類型名。

如（6－2）中的聲明是如下處理的：

TYPEVAR

Link=↑cell;next:link;

np=↑cell;

last:link;

nqr=↑cell;

p:np;

q

:nqr;

r:nqr;

典型的實現(xiàn)是構造一張類型圖，每當遇到類型構造符和基本類型，就建立一個新結點，但要記住類型名所命名的類型表達式。在這種方法中，如果兩個類型表達式用類型圖中同樣的結點表示，那么，它們等價。link=pointerpointerpointercellnextlastpqr圖6-7鏈表和樹結構經(jīng)常是遞歸定義的。它們的結點通常定義成一個記錄，記錄中含有指向同類型記錄的指針。設鏈表中的結點含有一個整型信息和一個指向下一個結點的指針，實現(xiàn)鏈表的類型定義：

TYPElink=node;node=RECORDinfo:integer;next:linkEND;類型表示中的環(huán)用圖表示類型表達式node=recordinfointegernextpointernodenode=recordnextinfointegerpointera.無環(huán)b.有環(huán)

C語言對除記錄（結構）以外的所有類型使用結構等價，而記錄類型用的是名字等價，以避免類型圖中的環(huán)。cell=record::infopointernextintegercell6.2.1變量標識符和類型表達式的綁定程序說明部分建立計算環(huán)境,其中說明了每個變量標識符以及與之綁定的類型。語法(6－3)是一個簡單的程序語言語法，該程序由一系列聲明D和隨后的一個表達式E組成，假設數(shù)組的下標從1開始。

文法G[P]，產(chǎn)生式如下：

(6－3)

P→D；E

D→D；D|id:T

T→char|integer|ARRAY[num]OFT|↑T

E→num|id|EMODE|E[E]|E↑6.2類型分析

語義分析程序首先處理類型說明，建立類型表達式，然后處理變量說明，建立變量和類型表達式的綁定。具體實現(xiàn)是把變量標識符的類型信息記錄在其符號表的表項中，過程addtype（id.entry,T.type）完成這個任務，其翻譯模式由圖6－4給出

P→D；E

D→D；D

D→id:T

{addtype（id.enery，T.TYPE）}

T→char

{T.type:=char}

T→integer

{T.type:=integer}

T→↑T1

{T.type:=POINTER(T1.type)}

T→ARRAY[num]OFT1

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

圖6-4建立變量標識符和類型屬性綁定的翻譯模式

6.2.2類型檢查類型檢查可以分為動態(tài)和靜態(tài)兩種。動態(tài)檢查在運行時刻完成。功效很低。但是如果語言允許動態(tài)確定類型，動態(tài)檢查是必須的。靜態(tài)檢查在編譯時刻完成。靜態(tài)檢查是高效的。如果一個語言能夠保證經(jīng)過靜態(tài)檢查之后，程序沒有運行時刻的類型錯誤，則稱為強類型的。類型檢查的內(nèi)容包括：表達式語句函數(shù)

檢查運算對象之間的類型是否滿足相容條件,函數(shù)lookup（e）取符號表中保存在條目e中的類型。

E→num

{E.type:=integer}

E→id

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

E→E1MODE2

{E.type:=IF(E1.type=integer)AND(E2.type=integer)

THENintegerELSEtype_error}

E→E1[E2]

{E.type:=IF(E2.type=integer)AND(E1.type=ARRAY(s,t))

THENtELSEtype_error}

E→E1↑

{E.type:=IFE1.type=POINTER(t)

THENtELSEtype_error}

表達式的類型檢查的翻譯模式

表達式的類型檢查

語句的類型檢查主要包括：賦值語句類型的相容性，控制表達式的結果類型檢查。指派給語句的類型是基本類型void，如果在語句中發(fā)現(xiàn)類型錯誤，指派給語句的類型是type_error。

語句的類型檢查

S→id:=E{S.type:=IFid.type=E.type

THENvoidELSEtype_error}

S→IFETHENS1

{S.type:=IFE.type=boolean

THENS1.typeELSEtype_error}

S→WHILEEDOS1{S.type:=IFE.type=boolean

THENS1.typeELSEtype_error}

S→S1;S2{S.type:=IF(S1.type=void)AND(S2.type=void)

THENvoid

ELSEtype_error}

圖6－5檢查語句類型的翻譯模式

對說明部分的分析，應該能知道被引用函數(shù)的類型。翻譯模式為：

T→T1‘→’T2{T.type:=T1.type→T2.type}

函數(shù)引用可看成一個表達式作用于另一個表達式，它的類型檢查是：

E→E1(E2){E.type:=IF(E2.type=s)AND(E1.type=s→t)

THENtELSEtype_error}

把單個參數(shù)推廣到多個參數(shù),類型為T1、T2、…、Tn的n個變元可以看成類型為T1T2

…Tn的一個變元。函數(shù)引用的類型檢查

6.2.2類型轉(zhuǎn)換

一般的程序設計語言中都規(guī)定了某些類型之間的轉(zhuǎn)換關系：比如說整數(shù)量可以被當作實數(shù)量參與運算，并且不需要程序員顯式說明。不同類型的常數(shù)在計算機中有不同的表示。當一個值需要轉(zhuǎn)換成為其它類型使用的時候，需要使用某些代碼進行轉(zhuǎn)換。因此，編譯程序要識別需要進行類型轉(zhuǎn)換的地方，并相應地生成代碼。程序設計語言的設計者需要考慮什么情況下需要和可以進行轉(zhuǎn)換。

考慮表達式x+i，其中x是實型，i是整形,它的后綴式可能是

xiinttorealreal+

語言的定義會指出必須要做的類型轉(zhuǎn)換。例如，當整數(shù)賦給實型變量時，應該把賦值號右邊對象轉(zhuǎn)換成左邊對象的類型。

例6.6

考慮把算術運算符op作用于常數(shù)和標識符形成的表達式，假設運算對象有整型和實型兩個類型

，函數(shù)lookup(e)返回符號表中保存在e條目中的類型。

6.2.2類型轉(zhuǎn)換

E→num{E.type:=integer}

E→num.num{E.type:=real}

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

E→E1opE2{E.type:=IF(E1.type=integer)AND(E2.type=integer)

THENintegerELSE

IF(E1.type=integer)AND(E2.type=real)

THENrealELSE

IF(E1.type=real)AND(E2.type=integer)

THENreal

ELSE

IF(E1.type=real)AND(E2.type=real)

THENreal

ELSEtype_error}

圖6－9需要強制類型轉(zhuǎn)換的類型檢查

運算符（函數(shù)）的重載多態(tài)函數(shù)重載運算符（overloadingoperator）根據(jù)上下文可以執(zhí)行不同的運算。＋是重載符號，在A＋B中，當A和B為整數(shù)、實數(shù)、復數(shù)或者矩陣時，運算符執(zhí)行不同類型的運算。當出現(xiàn)重載運算符時，要確定它所表示的唯一的意義，稱為運算符識別。檢查運算符的操作數(shù)。多態(tài)函數(shù)能實現(xiàn)對數(shù)據(jù)結構進行操作的算法，不管數(shù)據(jù)結構的元素類型是什么。多態(tài)函數(shù)的特點每次被調(diào)用時，傳遞過來的參數(shù)可以具有不同類型。

6.1假如有下面的Pascal說明

TYPE

atype=ARRAY[0..9,-10..10]OFinteger;

cell=RECORD

a,b:integer

END;

pcell=↑cell