語義分析和中間代碼生成課件

7.1

中間語言7.1.1后綴式表達(dá)式E的后綴式可以如下遞歸定義如果E是變量或常數(shù)，那么E的后綴式就是E本身。7.1

中間語言7.1.1后綴表示表達(dá)式E的后綴表示可以如下遞歸定義如果E是變量或常數(shù)，那么E的后綴表示就是E本身。如果E是形式為E1opE2的表達(dá)式，那么E的后綴式是E1

E2

op，其中E1

和E2

分別是E1和E2的后綴式。7.1

中間語言7.1.1后綴式表達(dá)式E的后綴式可以如下遞歸定義如果E是變量或常數(shù)，那么E的后綴式就是E本身。如果E是形式為E1opE2的表達(dá)式，那么E的后綴式是E1

E2

op，其中E1

和E2

分別是E1和E2的后綴式。如果E是形式為(E1)的表達(dá)式，那么E1的后綴表示也是E的后綴式。

7.1

中間語言后綴式表示法是波蘭邏輯學(xué)家盧卡西維奇（Lukasiewicz）發(fā)明的一種表示表達(dá)式的方法因此又稱逆波蘭表示法。這種表示法是把運(yùn)算量（操作數(shù)）寫在前面把算符寫在后面（后綴）。

7.1

中間語言把表達(dá)式翻譯為后綴式的語義規(guī)則描述 產(chǎn)生式語義規(guī)則E→E1opE2E.code:＝E1.code||E2.code||opE→（E1）E．code:=E1.codeE→idE．code:＝id7.1

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

4)+2的后綴表示是84

2+

后綴式的最大優(yōu)點(diǎn)是便于計(jì)算機(jī)處理表達(dá)式后綴式很容易拓廣到含一元算符的表達(dá)式后綴式也可以拓廣到其它語言成分演示Table7_17.1

中間語言7.1.2

圖表示法圖表示法包括DAG與抽象語法樹抽象語法樹

assigna++

bcdcduminus(a)語法樹

a:=(

b+c

d)+c

d抽象語法樹7.1

中間語言7.1.2

圖表示法有向無環(huán)圖也是一種中間表示

assigna++

bcdcduminusassigna++

bcduminus(a)語法樹(b)DAG

a:=(

b+c

d)+c

d的圖形表示7.1

中間語言構(gòu)造賦值語句抽象語法樹的屬性文法 演示Table7_2產(chǎn)

生

式

語

義

規(guī)

則S

id:=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

E1

E2E.nptr:=mknode(‘

’,E1.nptr,E2.nptr)E

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

(E1)E.nptr:=E1.nptr

E

idE.nptr:=mkleaf

(id,id.entry)7.1

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

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

z

t2:=x+t1

演示Table7_3

7.1

中間語言三地址代碼是語法樹或DAG的一種線性表示 a:=(

b+c

d)+c

d

語法樹的代碼 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:=t57.1

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

y

gotoL過程調(diào)用param

x

和callp,n過程返回

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

y和

x:=y四元式、三元式、間接三元式三地址語句可看成中間代碼的一種抽象形式。編譯程序中，三地址代碼語句的具體實(shí)現(xiàn)可以用記錄表示，記錄中包含表示運(yùn)算符和操作數(shù)的域。通常有三種表示方法：四元式、三元式、間接三元式。a:＝b*－c＋b*－c四元式三元式

oparg1arg2resultoparg1arg2(0)uminuscT1(0)uminusc*bT1T2(1)*b(0)

(2)uminus

cT3(2)uminus

c(3)*bT3T4(3)*b(2)

(4)+T2T4T5(4)+(1)(3)(5):=T5a

(5)assigna(4)X：=(A+B)*C;Y:=D↑(A+B);

間接三元式oparg1arg2(1)+AB

(2)*

(1)C(3):=X(2)

(4)↑D(1)(5):=Y(4)間接代碼（1）（2）（3）（1）（4）（5）7.2

說明語句為局部名字建立符號表?xiàng)l目為它分配存儲單元符號表中包含名字的類型和分配給它的存儲單元的相對地址等信息7.2

說明語句7.2.1

過程中的聲明7.2

說明語句演示Figure7.6計(jì)算被聲明名字的類型和相對地址P

D{offset:=0}D

D;D

D

id:T {enter(id.name,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}7.2

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

DS D

D;D|id:T|procid;D;S語義動作用到的函數(shù)mktable(previous)enter(table,name,type,offset)

addwidth(table,width)enterproc(table,name,newtable)7.2

說明語句處理嵌套過程中的說明語句P

MD

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

pop(tblptr);pop(offset)}M

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

D1;D2D

procid;ND1;S{t:=top(tblptr);

addwidth(t,top(offset));pop(tblptr);pop(offset);

enterproc(top(tblptr),id.name,t)}D

id:T{enter(top(tblptr),id.name,T.type,top(offset)); top(offset):=top(offset)+T.width}N

{t:=mktable(top(tblptr)); push(t,tblptr);push(0,offset)}

（1）

programsort(input,output)（2）

vara:array[0..10]ofinteger;（3）

x:integer;（4）

procedurereadarray（5）

vari:integer;（6）

begin…a…end{readarray}（7）

procedureexchange(i,j:integer);（8）

begin（9）

x:=a[i];a[i]:=a[j];a[j]:=x（10）

end{exchange};（11）

procedurequicksort(m,n;integer);（12）

vark,v:integer;（13）

functionpartition(y,z:integer):integer;（14）

vari,j:integer;（15）

begin…a…（16）

…v…（17）

…exchange(i,j);…（18）

end{partition};（19）

begin…end{quicksort};（20）

begin…end{sort}.7.2

說明語句exchangereadarrayxa表頭空sortquicksort指向readarraypartitionvk表頭quicksortreadarraryi表頭exchange表頭指向exchangepartition7.2

說明語句7.2.3

記錄的域名T

recordDendT

recordL

Dend {T.type:=record(top(tblptr)); T.width:=top(offset); pop(tblptr);pop(offset)}L

{t:=mktable(nil); push(t,tblprt);push(0,offset)}7.3

賦值語句7.3.1簡單算術(shù)表達(dá)式及賦值語句S

id:=E {p:=lookup(id.name); 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簡單算術(shù)表達(dá)式及賦值語句E

E1{E.place:=newtemp; emit(E.place,‘:=’,‘uminus’,E1.place)}E

(E1){E.place:=E1.place}E

id{p:=lookup(id.name); ifp

nilthenE.place:=pelseerror}7.3

賦值語句7.3.2數(shù)組元素的地址計(jì)算一維數(shù)組A的第i個元素的地址計(jì)算

base+(i

low)

w7.3

賦值語句7.3.3數(shù)組元素的地址計(jì)算一維數(shù)組A的第i個元素的地址計(jì)算

base+(i

low)

w

重寫成

i

w+(base

low

w)7.3

賦值語句二維數(shù)組列為主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]7.3

賦值語句二維數(shù)組列為主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]行為主

A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,3]

7.3

賦值語句二維數(shù)組列為主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]行為主

A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,3]

base+((i1

low1)

n2+(i2

low2))

w

（其中n2=high2

low2+1）7.3

賦值語句二維數(shù)組列為主

A[1,1],A[2,1],A[1,2],A[2,2],A[1,3],A[2,3]行為主

A[1,1],A[1,2],A[1,3],A[2,1],A[2,2],A[2,3]

base+((i1

low1)

n2+(i2

low2))

w

（其中n2=high2

low2+1）

((i1

n2)+i2)

w+

(base

((low1

n2)+low2)

w)7.3

賦值語句多維數(shù)組A[i1,i2,...,ik

]的地址表達(dá)式((…((i1

n2+i2

)

n3

+i3)…)

nk

+

ik)

w

+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+

lowk

)

w7.3

賦值語句7.3.4數(shù)組元素地址計(jì)算的翻譯方案下標(biāo)變量訪問的產(chǎn)生式

L

id[Elist]|id

Elist

Elist,E|E改成

L

Elist]|id

Elist

Elist,E|id[E7.3

賦值語句所有產(chǎn)生式S

L:=EE

E+EE

(E)E

LL

Elist

]L

idElist

Elist,EElist

id[E7.3

賦值語句L

id{L.place:=id.place;L.offset:=null}7.3

賦值語句L

id{L.place:=id.place;L.offset:=null}Elist

id[E{Elist.place:=E.place;Elist.ndim:=1;

Elist.array:=id.place}7.3

賦值語句L

id{L.place:=id.place;L.offset:=null}Elist

id[E{Elist.place:=E.place;Elist.ndim:=1;

Elist.array:=id.place}Elist

Elist1,E{t:=newtemp;m:=Elist1.ndim+1;

emit(t,‘:=’,Elist1.place,‘

’,limit(Elist1.array,m));

emit(t,‘:=’,t,‘+’,E.place);

Elist.array:=Elist1.array;

Elist.place:=t;Elist.ndim:=m}7.3

賦值語句L

id{L.place:=id.place;L.offset:=null}Elist

id[E{Elist.place:=E.place;Elist.ndim:=1;

Elist.array:=id.place}Elist

Elist1,E{t:=newtemp;m:=Elist1.ndim+1;

emit(t,‘:=’,Elist1.place,‘

’,limit(Elist1.array,m));

emit(t,‘:=’,t,‘+’,E.place);

Elist.array:=Elist1.array;

Elist.place:=t;Elist.ndim:=m}L

Elist

] {L.place:=newtemp;emit(L.place,‘:=’,base(Elist.array),‘

’,C);/*C=invariant(Elist.array)*/L.offset:=newtemp;emit(L.offset,‘:=’,Elist.place,‘

’,w)}7.3

賦值語句E

L{ifL.offset=nullthen/

L是簡單變量

/

E.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place,‘:=’,L.place,‘[’,L.offset,‘]’)end}7.3

賦值語句E

L{ifL.offset=nullthen/

L是簡單變量

/

E.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place,‘:=’,L.place,‘[’,L.offset,‘]’)end}E

E1+E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place,‘+’,E2.place)}7.3

賦值語句E

L{ifL.offset=nullthen/

L是簡單變量

/

E.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place,‘:=’,L.place,‘[’,L.offset,‘]’)end}E

E1+E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place,‘+’,E2.place)}E

(E1){E.place:=E1.place}

7.3

賦值語句E

L{ifL.offset=nullthen/

L是簡單變量

/

E.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place,‘:=’,L.place,‘[’,L.offset,‘]’)end}E

E1+E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place,‘+’,E2.place)}E

(E1){E.place:=E1.place}S

L:=E {ifL.offset=nullthen/

L是簡單變量

/

emit(L.place,‘:=’,E.place) else

emit(L.place,‘[’,L.offset,‘]’,‘:=’, E.place)}

7.3

賦值語句S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹7.3

賦值語句S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹t1:=y

20t1:=t1+z

7.3

賦值語句S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹t1:=y

20t1:=t1+z

t2:=A

84t3:=4

t1

7.3

賦值語句S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹t1:=y

20t1:=t1+z

t2:=A

84t3:=4

t1

t4:=t2[t3]7.3

賦值語句S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]y

x:=A[y,z]的注釋分析樹t1:=y

20t1:=t1+z

t2:=A

84t3:=4

t1

t4:=t2[t3]x:=t4

7.3

賦值語句7.3.5類型轉(zhuǎn)換x:=y+i

j（x和y的類型是real，i和j的類型是integer）中間代碼t1:=iint

jt2:=inttorealt1

t3:=yreal+t2

x:=t37.3

賦值語句E

E1+E2E.place:=newtempifE1.type=integerandE2.type=integerthenbegin

emit(E.place,‘:=’,E1.place,‘int+’,E2.place);

E.type=integerendelseifE1.type=integerandE2.type=realthenbegin u:=newtemp; emit(u,‘:=’,‘inttoreal’,E1.place); emit(E.place,‘:=’,u,

‘real+’,E2.place); E.type:=realend...7.4

布爾表達(dá)式的翻譯布爾表達(dá)式有兩個基本目的計(jì)算邏輯值在控制流語句中用作條件表達(dá)式7.4

布爾表達(dá)式的翻譯布爾表達(dá)式有兩個基本目的計(jì)算邏輯值在控制流語句中用作條件表達(dá)式布爾表達(dá)式的完全計(jì)算布爾表達(dá)式的“短路”計(jì)算E1orE2定義成ifE1thentrueelseE2E1andE2定義成

ifE1thenE2elsefalse7.4

布爾表達(dá)式的翻譯7.4.1布爾表達(dá)式的翻譯E

E

orE|EandE|notE|(E) |idrelopid|true|falsea<b的翻譯100:ifa<bgoto103101:t:=0102:goto104103:t:=1104:7.4

布爾表達(dá)式的翻譯E

E1orE2

{E.place:=newtemp;

emit(E.place,‘:=’,E1.place,‘or’E2.place)}E

id1relopid2

{E.place:=newtemp;emit(‘if’,id1.place,relop.op,id2.place,‘goto’,nextstat+3);emit(E.place,‘:=’,‘0’);emit(‘goto’,nextstat+2);emit(E.place,‘:=’,‘1’)}7.4

布爾表達(dá)式的翻譯表達(dá)式演示Figure7_13

a<borc<dande<f的代碼是： 100ifa<bgoto103107T2:=1 101T1:=0

108ife<f

goto111102goto104109T3:=0 103T1:=1

110goto112104ifc<d

goto107111T3:=1 105T2:=0112T4:=T2and

T3106goto108113T5:=T1or

T47.4

作為控制條件的布爾表達(dá)式的翻譯一遍掃描產(chǎn)生布爾表達(dá)式中間代碼的問題：生成某些轉(zhuǎn)移語句時，還不知道轉(zhuǎn)移到哪里。解決方法：不確定跳轉(zhuǎn)目標(biāo)；建立一個鏈表，記錄跳轉(zhuǎn)指令的標(biāo)號。目標(biāo)確定后，再根據(jù)這個鏈表，把所有相關(guān)指令填完整。E.truelist:布爾表達(dá)式E生成的四元式中需回填真出口的四元式標(biāo)號；E.falselist:布爾表達(dá)式E生成的四元式中需回填假出口的四元式標(biāo)號；7.4

布爾表達(dá)式的翻譯nextquadmakelist(i)merge(p1,p2)backpatch(p,t)7.4

布爾表達(dá)式的翻譯E

E1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist;}E

id1

relopid2E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop,id1.place,id2.place,0);emit(j,-,-,0);}演示7.5控制語句的翻譯7.5.1控制流語句的翻譯S

ifEthenS1 |ifEthenS1

elseS2 |whileEdoS1 |S1;S2

7.5控制語句的翻譯E.codeS1.codeE.true:...跳向E.true跳向E.false(a)if-thenE.codeS1.codeE.true:...跳向E.true跳向E.falseE.false:goto

S.nextS2.code(b)if-then-elseE.codeS1.codeE.true:...跳向E.true跳向E.falsegoto

S.beginS.begin:(c)while-doS1.codeS2.codeS1.next:...(d)S1;S27.5控制語句的翻譯S

ifEthenS1{E.true:=newlabel;

E.false:=S.next;

S1.next:=S.next;

S.code:=E.code||gen(E.true,‘:’)||S1.code}E.codeS1.codeE.true:...跳向E.true跳向E.false(a)if-then7.5控制語句的翻譯S

ifEthenS1elseS2{E.true:=newlabel;

E.false:=newlabel;

S1.next:=S.next;

S2.next:=S.next;

S.code:= E.code||gen(E.true,‘:’)||S1.code||

gen(‘goto’,S.next)||gen(E.false,‘:’)||

S2.code}E.codeS1.codeE.true:...跳向E.true跳向E.falseE.false:goto

S.nextS2.code(b)if-then-else7.5控制語句的翻譯S

whileEdoS1

{S.begin:=newlabel;

E.true:=newlabel;

E.false:=S.next;

S1.next:=S.begin;

S.code:=gen(S.begin,‘:’)||E.code||

gen(E.true,‘:’)||S1.code||gen(‘goto’,S.begin)}E.codeS1.codeE.true:...跳向E.true跳向E.falsegoto

S.beginS.begin:(c)while-do7.5控制語句的翻譯S

S1;S2{S1.next:=newlabel;S2.next:=S.next;

S.code:=S1.code||gen(S1.next,‘:’)||S2.code}S1.codeS2.codeS1.next:...(d)S1;S2使用回填技術(shù)一遍掃描翻譯控制語句S→ifEthenM1S1NelseM2S2{backpatch(E.truelist,M1.quad);

backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist);N→ε{N.nextlist:=makelist(nextquad);emit(j,-,-,-)}使用回填技術(shù)一遍掃描翻譯控制語句M→ε{M.quad:=nextquad;}S→ifEthenMS1{backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist);}S→whileM1EdoM2S1M3{backpatch(S1.nextlist,M1.quad);

backpatch(E.turelist,M2.quad);

backpatch(E.falselist,M3.quad+1);S.nextlist:=E.falselist;emit(j,-,-,M1.quad)}演示Table7_8P195的翻譯模式能回填P196的第二個四元式么？7.5控制語句的翻譯7.5.3開關(guān)語句的翻譯switchE begin caseV1:S1 caseV2:S2 ... caseVn-1:Sn–1 default:Sn

end7.5控制語句的翻譯分支數(shù)較少時 t:=E的代碼 |Ln-2:ift

Vn-1gotoLn-1

ift

V1gotoL1 | Sn

-1的代碼

S1的代碼 | gotonext

gotonext |Ln-1:Sn的代碼

L1: ift

V2gotoL2|next: S2的代碼

gotonextL2: ... ...7.5控制語句的翻譯分支較多時，將分支測試的代碼集中在一起，便于生成較好的分支測試代碼。 t:=E的代碼 |Ln: Sn的代碼

gototest

| gotonext L1: S1的代碼 |test:ift=V1gotoL1

gotonext | ift=V2gotoL2

L2: S2的代碼

| ...

gotonext | ift=Vn-1gotoLn-1 ... | gotoLnLn-1: Sn

-1的代碼

|next:

gotonext7.5控制語句的翻譯中間代碼增加一種case語句，便于代碼生成器對它進(jìn)行特別處理test: caseV1 L1 caseV2 L2 ... caseVn-1

Ln-1 caset Ln

next:7.6

過程調(diào)用的處理

過程調(diào)用的翻譯S

callid(Elist){for隊(duì)列queue中的每一項(xiàng)pdoemit（’param’p）；emit（‘call’id.Place）}Elist

Elist,E{將E.Place加入到queeue的隊(duì)尾}Elist

E{初始化queue僅包含E.place}7.6過程調(diào)用過程調(diào)用id(E1,E2,…,En)的中間代碼結(jié)構(gòu)E1.place:=E1的代碼E2.place:=E2的代碼 ...En.place:=En的代碼param

E1.placeparam

E2.place ...param

En.placecallid.place,n7.6過程調(diào)用S

callid(Elist) {為長度為n的隊(duì)列中的每個E.place，

emit(‘param’,E.place); emit(‘call’,id.plase,n)

}Elist

Elist,E

{把E.place放入隊(duì)列末尾}Elist

E

{將隊(duì)列初始化，并讓它僅含E.place}演示7.7

類型檢查靜態(tài)檢查中最典型的部分—類型檢查： 類型系統(tǒng)、類型檢查、多態(tài)函數(shù)、重載。忽略其它的靜態(tài)檢查：控制流檢查、唯一性檢查、關(guān)聯(lián)名字檢查。分析器類型檢查器中間代碼生成器語法樹語法樹中間表示記號流7.7.1類型系統(tǒng)變量的類型 變量在程序執(zhí)行期間的取值范圍類型化語言 變量都被給定類型的語言無類型語言 不限制變量值范圍的語言 一個運(yùn)算可以作用到任意的運(yùn)算對象，其結(jié)果可能是一個有意義的值、一個錯誤、一個異?；蛞粋€未做說明的結(jié)果。類型系統(tǒng)的根本目的是防止程序運(yùn)行時出現(xiàn)執(zhí)行錯誤類型系統(tǒng)的形式化 類型表達(dá)式一些實(shí)際使用的語言是弱類型化語言Pascal語言無標(biāo)志的變體記錄類型函數(shù)型參數(shù)C語言 有很多不安全的并且被廣泛使用的特征，如：指針?biāo)阈g(shù)運(yùn)算強(qiáng)制類型轉(zhuǎn)換參數(shù)個數(shù)可變7.7.1.2

類型化語言的優(yōu)點(diǎn)從工程的觀點(diǎn)看，類型化語言有下面一些優(yōu)點(diǎn)

開發(fā)的實(shí)惠較早發(fā)現(xiàn)錯誤類型信息還具有文檔作用7.7.2

類型檢查器的規(guī)格說明

一個簡單的語言P

D;ED

D;D|id:TT

boolean|integer|array[num]ofT|

T|T‘

’TS

id:=E|ifEthenS|whileEdoS|S;SE

literal|num|id|EmodE|E[E]|

E

7.7.2

類型檢查器的規(guī)格說明類型檢查——聲明語句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)}7.7.2

類型檢查器的規(guī)格說明類型檢查——聲明語句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)}7.7.2

類型檢查器的規(guī)格說明類型檢查——聲明語句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)}7.7.2

類型檢查器的規(guī)格說明類型表達(dá)式基本類型 boolean,char,integer,real構(gòu)造類型數(shù)組類型 array(I,T)指針類型 pointer(T)積類型 T1

T2函數(shù) T1

T2類型表達(dá)式中還可以出現(xiàn)類型名字和類型變量7.7.2

類型檢查器的規(guī)格說明表達(dá)式的類型檢查E

literal

{E.type:=char}E

num

{E.type:=integer}E

id

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

類型檢查器的規(guī)格說明類型檢查——表達(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}7.7.2

類型檢查器的規(guī)格說明類型檢查——表達(dá)式E

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

類型檢查器的規(guī)格說明類型檢查——表達(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}7.7.2

類型檢查器的規(guī)格說明類型檢查——表達(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}7.7.2

類型檢查器的規(guī)格說明語句的類型檢查S

id:=E{S.type:=ifid.type=E.type thenvoid elsetype_error}7.7.2

類型檢查器的規(guī)格說明類型檢查——語句S

id:=E{S.type:=ifid.type=E.type thenvoid elsetype_error}S

ifEthenS1{S.type:=ifE.type=boolean

thenS1.type elsetype_error}7.7.2

類型檢查器的規(guī)格說明S

whileEdoS1

{S.type:=ifE.type=boolean

thenS1.type

elsetype_error}7.7.2

類型檢查器的規(guī)格說明S

whileEdoS1

{S.type:=ifE.type=boolean

thenS1.type

elsetype_error}S

S1;S2

{S.type:=ifS1.type=

voidand S2.type=voidthenvoid

elsetype_error}7.7.2

類型檢查器的規(guī)格說明程序的類型檢查P

D;S

{P.type:=ifS.type=voidthenvoid elsetype_error}7.7.2

類型檢查器的規(guī)格說明類型轉(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}7.7.3函數(shù)和運(yùn)算符的重載重載符號 有多個含義，但在引用點(diǎn)的含義都是唯一的例如 加法算符+可用于不同類型，是不同的函數(shù)

在Ada中，()是重載的，A(I)有不同含義7.7.3函數(shù)和運(yùn)算符的重載子表達(dá)式的可能類型集合例

Ada語言聲明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重載，可能的類型包括：integer

integer

integerinteger

integer

complexcomplex

complex

complex

7.7.3函數(shù)和運(yùn)算符的重載子表達(dá)式的可能類型集合例

Ada語言聲明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重載，可能的類型包括：integer

integer

integer 2

(3

5)

integer

integer

complex complex

complex

complex

7.7.3函數(shù)和運(yùn)算符的重載子表達(dá)式的可能類型集合例

Ada語言聲明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重載，可能的類型包括：integer

integer

integer 2

(3

5)

integer

integer

complex (3

5)

z

complex

complex

complex

z是復(fù)型

7.7.3函數(shù)和運(yùn)算符的重載以函數(shù)作用為例，考慮類型檢查 在每個表達(dá)式都有唯一的類型時，函數(shù)作用的類型檢查是：E

E1(E2){E.type:= ifE2.type=sandE1.type=s

t

thent

elsetype_error}7.7.3函數(shù)和運(yùn)算符的重載確定表達(dá)式可能類型的集合產(chǎn)

生

式

語

義

規(guī)

則

E

E

E

.types:=E.types

E

id

E.types:=lookup(id.entry)

E

E1(E2)

E.types:={t|E2.types中存在一個s，使得s

t屬于E1.types}7.7.4

多態(tài)函數(shù)7.7.3.1為什么要使用多態(tài)函數(shù)例：用Pascal語言寫不出求表長度的通用程序typelink=

cell; cell=record info:integer; next:link end;7.7.4多態(tài)函數(shù)functionlength(lptr:link):integer;

varlen:integer; begin

len:=0; whilelptr<>nildobegin

len:=len+1;

lptr:=lptr

.next end; length:=lenend;7.7.4多態(tài)函數(shù)用ML語言很容易寫出求表長度的程序而不必管表元的類型。funlength(lptr)= ifnull(lptr)then0 elsel