7.1

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

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

E2

op，其中E1

和E2

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

中間語(yǔ)言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

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

7.1

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

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

4)+2的后綴表示是84

2+

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

中間語(yǔ)言7.1.2

圖表示法圖表示法包括DAG與抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)

assigna++

bcdcduminus(a)語(yǔ)法樹(shù)

a:=(

b+c

d)+c

d抽象語(yǔ)法樹(shù)7.1

中間語(yǔ)言7.1.2

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

assigna++

bcdcduminusassigna++

bcduminus(a)語(yǔ)法樹(shù)(b)DAG

a:=(

b+c

d)+c

d的圖形表示7.1

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

生

式

語(yǔ)

義

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

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

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

z

t2:=x+t1

演示Table7_3

7.1

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

b+c

d)+c

d

語(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:=t57.1

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

y

gotoL過(guò)程調(diào)用param

x

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

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

y和

x:=y四元式、三元式、間接三元式三地址語(yǔ)句可看成中間代碼的一種抽象形式。編譯程序中，三地址代碼語(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

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

說(shuō)明語(yǔ)句7.2.1

過(guò)程中的聲明7.2

說(shuō)明語(yǔ)句演示Figure7.6計(jì)算被聲明名字的類(lèi)型和相對(duì)地址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

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

DS D

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

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

說(shuō)明語(yǔ)句處理嵌套過(guò)程中的說(shuō)明語(yǔ)句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

說(shuō)明語(yǔ)句exchangereadarrayxa表頭空sortquicksort指向readarraypartitionvk表頭quicksortreadarraryi表頭exchange表頭指向exchangepartition7.2

說(shuō)明語(yǔ)句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

賦值語(yǔ)句7.3.1簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句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

賦值語(yǔ)句7.3.1簡(jiǎn)單算術(shù)表達(dá)式及賦值語(yǔ)句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

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

base+(i

low)

w7.3

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

base+(i

low)

w

重寫(xiě)成

i

w+(base

low

w)7.3

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

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

賦值語(yǔ)句二維數(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

賦值語(yǔ)句二維數(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

賦值語(yǔ)句二維數(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

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

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

n2+i2

)

n3

+i3)…)

nk

+

ik)

w

+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+

lowk

)

w7.3

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

L

id[Elist]|id

Elist

Elist,E|E改成

L

Elist]|id

Elist

Elist,E|id[E7.3

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

L:=EE

E+EE

(E)E

LL

Elist

]L

idElist

Elist,EElist

id[E7.3

賦值語(yǔ)句L

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

賦值語(yǔ)句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

賦值語(yǔ)句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

賦值語(yǔ)句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

賦值語(yǔ)句E

L{ifL.offset=nullthen/

L是簡(jiǎn)單變量

/

E.place:=L.place

elsebeginE.place:=newtemp;

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

賦值語(yǔ)句E

L{ifL.offset=nullthen/

L是簡(jiǎn)單變量

/

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

賦值語(yǔ)句E

L{ifL.offset=nullthen/

L是簡(jiǎn)單變量

/

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

賦值語(yǔ)句E

L{ifL.offset=nullthen/

L是簡(jiǎn)單變量

/

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是簡(jiǎn)單變量

/

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

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

7.3

賦值語(yǔ)句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]的注釋分析樹(shù)7.3

賦值語(yǔ)句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]的注釋分析樹(shù)t1:=y

20t1:=t1+z

7.3

賦值語(yǔ)句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]的注釋分析樹(shù)t1:=y

20t1:=t1+z

t2:=A

84t3:=4

t1

7.3

賦值語(yǔ)句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]的注釋分析樹(shù)t1:=y

20t1:=t1+z

t2:=A

84t3:=4

t1

t4:=t2[t3]7.3

賦值語(yǔ)句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]的注釋分析樹(shù)t1:=y

20t1:=t1+z

t2:=A

84t3:=4

t1

t4:=t2[t3]x:=t4

7.3

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

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

jt2:=inttorealt1

t3:=yreal+t2

x:=t37.3

賦值語(yǔ)句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á)式有兩個(gè)基本目的計(jì)算邏輯值在控制流語(yǔ)句中用作條件表達(dá)式7.4

布爾表達(dá)式的翻譯布爾表達(dá)式有兩個(gè)基本目的計(jì)算邏輯值在控制流語(yǔ)句中用作條件表達(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á)式中間代碼的問(wèn)題：生成某些轉(zhuǎn)移語(yǔ)句時(shí)，還不知道轉(zhuǎn)移到哪里。解決方法：不確定跳轉(zhuǎn)目標(biāo)；建立一個(gè)鏈表，記錄跳轉(zhuǎn)指令的標(biāo)號(hào)。目標(biāo)確定后，再根據(jù)這個(gè)鏈表，把所有相關(guān)指令填完整。E.truelist:布爾表達(dá)式E生成的四元式中需回填真出口的四元式標(biāo)號(hào)；E.falselist:布爾表達(dá)式E生成的四元式中需回填假出口的四元式標(biāo)號(hà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控制語(yǔ)句的翻譯7.5.1控制流語(yǔ)句的翻譯S

ifEthenS1 |ifEthenS1

elseS2 |whileEdoS1 |S1;S2

7.5控制語(yǔ)句的翻譯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控制語(yǔ)句的翻譯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控制語(yǔ)句的翻譯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控制語(yǔ)句的翻譯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控制語(yǔ)句的翻譯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ù)一遍掃描翻譯控制語(yǔ)句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ù)一遍掃描翻譯控制語(yǔ)句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的第二個(gè)四元式么？7.5控制語(yǔ)句的翻譯7.5.3開(kāi)關(guān)語(yǔ)句的翻譯switchE begin caseV1:S1 caseV2:S2 ... caseVn-1:Sn–1 default:Sn

end7.5控制語(yǔ)句的翻譯分支數(shù)較少時(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控制語(yǔ)句的翻譯分支較多時(shí)，將分支測(cè)試的代碼集中在一起，便于生成較好的分支測(cè)試代碼。 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控制語(yǔ)句的翻譯中間代碼增加一種case語(yǔ)句，便于代碼生成器對(duì)它進(jìn)行特別處理test: caseV1 L1 caseV2 L2 ... caseVn-1

Ln-1 caset Ln

next:7.6

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

過(guò)程調(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過(guò)程調(diào)用過(guò)程調(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過(guò)程調(diào)用S

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

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

}Elist

Elist,E

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

E

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

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

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

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

類(lèi)型檢查器的規(guī)格說(shuō)明

一個(gè)簡(jiǎn)單的語(yǔ)言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

類(lèi)型檢查器的規(guī)格說(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)}7.7.2

類(lèi)型檢查器的規(guī)格說(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)}7.7.2

類(lèi)型檢查器的規(guī)格說(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)}7.7.2

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

T2函數(shù) T1

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

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

literal

{E.type:=char}E

num

{E.type:=integer}E

id

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

類(lèi)型檢查器的規(guī)格說(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}7.7.2

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

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

類(lèi)型檢查器的規(guī)格說(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}7.7.2

類(lèi)型檢查器的規(guī)格說(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}7.7.2

類(lèi)型檢查器的規(guī)格說(shuō)明語(yǔ)句的類(lèi)型檢查S

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

類(lèi)型檢查器的規(guī)格說(shuō)明類(lèi)型檢查——語(yǔ)句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

類(lèi)型檢查器的規(guī)格說(shuō)明S

whileEdoS1

{S.type:=ifE.type=boolean

thenS1.type

elsetype_error}7.7.2

類(lèi)型檢查器的規(guī)格說(shuō)明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

類(lèi)型檢查器的規(guī)格說(shuō)明程序的類(lèi)型檢查P

D;S

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

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

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

Ada語(yǔ)言聲明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重載，可能的類(lèi)型包括：integer

integer

integerinteger

integer

complexcomplex

complex

complex

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

Ada語(yǔ)言聲明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重載，可能的類(lèi)型包括：integer

integer

integer 2

(3

5)

integer

integer

complex complex

complex

complex

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

Ada語(yǔ)言聲明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重載，可能的類(lèi)型包括：integer

integer

integer 2

(3

5)

integer

integer

complex (3

5)

z

complex

complex

complex

z是復(fù)型

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

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

t

thent

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

生

式

語(yǔ)

義

規(guī)

則

E

E

E

.types:=E.types

E

id

E.types:=lookup(id.entry)

E

E1(E2)

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

t屬于E1.types}7.7.4

多態(tài)函數(shù)7.7.3.1為什么要使用多態(tài)函數(shù)例：用Pascal語(yǔ)言寫(xiě)不出求表長(zhǎng)度的通用程序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語(yǔ)言很容易寫(xiě)出求表長(zhǎng)度的程序而不必管表元的類(lèi)型。funlength(lptr)= ifnull(lptr)then0 elsel