语义分析和中间代码生成课件

7.1

中间语言7.1.1后缀式表达式E的后缀式可以如下递归定义如果E是变量或常数，那么E的后缀式就是E本身。7.1

中间语言7.1.1后缀表示表达式E的后缀表示可以如下递归定义如果E是变量或常数，那么E的后缀表示就是E本身。如果E是形式为E1opE2的表达式，那么E的后缀式是E1

E2

op，其中E1

和E2

分别是E1和E2的后缀式。7.1

中间语言7.1.1后缀式表达式E的后缀式可以如下递归定义如果E是变量或常数，那么E的后缀式就是E本身。如果E是形式为E1opE2的表达式，那么E的后缀式是E1

E2

op，其中E1

和E2

分别是E1和E2的后缀式。如果E是形式为(E1)的表达式，那么E1的后缀表示也是E的后缀式。

7.1

中间语言后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法因此又称逆波兰表示法。这种表示法是把运算量（操作数）写在前面把算符写在后面（后缀）。

7.1

中间语言把表达式翻译为后缀式的语义规则描述 产生式语义规则E→E1opE2E.code:＝E1.code||E2.code||opE→（E1）E．code:=E1.codeE→idE．code:＝id7.1

中间语言后缀式不需要括号 (8

4)+2的后缀表示是84

2+

后缀式的最大优点是便于计算机处理表达式后缀式很容易拓广到含一元算符的表达式后缀式也可以拓广到其它语言成分演示Table7_17.1

中间语言7.1.2

图表示法图表示法包括DAG与抽象语法树抽象语法树

assigna++

bcdcduminus(a)语法树

a:=(

b+c

d)+c

d抽象语法树7.1

中间语言7.1.2

图表示法有向无环图也是一种中间表示

assigna++

bcdcduminusassigna++

bcduminus(a)语法树(b)DAG

a:=(

b+c

d)+c

d的图形表示7.1

中间语言构造赋值语句抽象语法树的属性文法 演示Table7_2产

生

式

语

义

规

则S

id:=E

S.nptr:=mknode(‘assign’,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表达式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无条件转移gotoL条件转移ifxrelop

y

gotoL过程调用param

x

和callp,n过程返回

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

y和

x:=y四元式、三元式、间接三元式三地址语句可看成中间代码的一种抽象形式。编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。通常有三种表示方法：四元式、三元式、间接三元式。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

说明语句为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息7.2

说明语句7.2.1

过程中的声明7.2

说明语句演示Figure7.6计算被声明名字的类型和相对地址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语义动作用到的函数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简单算术表达式及赋值语句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简单算术表达式及赋值语句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数组元素的地址计算一维数组A的第i个元素的地址计算

base+(i

low)

w7.3

赋值语句7.3.3数组元素的地址计算一维数组A的第i个元素的地址计算

base+(i

low)

w

重写成

i

w+(base

low

w)7.3

赋值语句二维数组列为主

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

赋值语句二维数组列为主

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

赋值语句二维数组列为主

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

赋值语句二维数组列为主

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

赋值语句多维数组A[i1,i2,...,ik

]的地址表达式((…((i1

n2+i2

)

n3

+i3)…)

nk

+

ik)

w

+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+

lowk

)

w7.3

赋值语句7.3.4数组元素地址计算的翻译方案下标变量访问的产生式

L

id[Elist]|id

Elist

Elist,E|E改成

L

Elist]|id

Elist

Elist,E|id[E7.3

赋值语句所有产生式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类型转换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

布尔表达式的翻译布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式7.4

布尔表达式的翻译布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式布尔表达式的完全计算布尔表达式的“短路”计算E1orE2定义成ifE1thentrueelseE2E1andE2定义成

ifE1thenE2elsefalse7.4

布尔表达式的翻译7.4.1布尔表达式的翻译E

E

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

布尔表达式的翻译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

布尔表达式的翻译表达式演示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

作为控制条件的布尔表达式的翻译一遍扫描产生布尔表达式中间代码的问题：生成某些转移语句时，还不知道转移到哪里。解决方法：不确定跳转目标；建立一个链表，记录跳转指令的标号。目标确定后，再根据这个链表，把所有相关指令填完整。E.truelist:布尔表达式E生成的四元式中需回填真出口的四元式标号；E.falselist:布尔表达式E生成的四元式中需回填假出口的四元式标号；7.4

布尔表达式的翻译nextquadmakelist(i)merge(p1,p2)backpatch(p,t)7.4

布尔表达式的翻译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使用回填技术一遍扫描翻译控制语句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,-,-,-)}使用回填技术一遍扫描翻译控制语句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开关语句的翻译switchE begin caseV1:S1 caseV2:S2 ... caseVn-1:Sn–1 default:Sn

end7.5控制语句的翻译分支数较少时 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语句，便于代码生成器对它进行特别处理test: caseV1 L1 caseV2 L2 ... caseVn-1

Ln-1 caset Ln

next:7.6

过程调用的处理

过程调用的翻译S

callid(Elist){for队列queue中的每一项pdoemit（’param’p）；emit（‘call’id.Place）}Elist

Elist,E{将E.Place加入到queeue的队尾}Elist

E{初始化queue仅包含E.place}7.6过程调用过程调用id(E1,E2,…,En)的中间代码结构E1.place:=E1的代码E2.place:=E2的代码 ...En.place:=En的代码param

E1.placeparam

E2.place ...param

En.placecallid.place,n7.6过程调用S

callid(Elist) {为长度为n的队列中的每个E.place，

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

}Elist

Elist,E

{把E.place放入队列末尾}Elist

E

{将队列初始化，并让它仅含E.place}演示7.7

类型检查静态检查中最典型的部分—类型检查： 类型系统、类型检查、多态函数、重载。忽略其它的静态检查：控制流检查、唯一性检查、关联名字检查。分析器类型检查器中间代码生成器语法树语法树中间表示记号流7.7.1类型系统变量的类型 变量在程序执行期间的取值范围类型化语言 变量都被给定类型的语言无类型语言 不限制变量值范围的语言 一个运算可以作用到任意的运算对象，其结果可能是一个有意义的值、一个错误、一个异常或一个未做说明的结果。类型系统的根本目的是防止程序运行时出现执行错误类型系统的形式化 类型表达式一些实际使用的语言是弱类型化语言Pascal语言无标志的变体记录类型函数型参数C语言 有很多不安全的并且被广泛使用的特征，如：指针算术运算强制类型转换参数个数可变7.7.1.2

类型化语言的优点从工程的观点看，类型化语言有下面一些优点

开发的实惠较早发现错误类型信息还具有文档作用7.7.2

类型检查器的规格说明

一个简单的语言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

类型检查器的规格说明类型检查——声明语句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

类型检查器的规格说明类型检查——声明语句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

类型检查器的规格说明类型检查——声明语句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

类型检查器的规格说明类型表达式基本类型 boolean,char,integer,real构造类型数组类型 array(I,T)指针类型 pointer(T)积类型 T1

T2函数 T1

T2类型表达式中还可以出现类型名字和类型变量7.7.2

类型检查器的规格说明表达式的类型检查E

literal

{E.type:=char}E

num

{E.type:=integer}E

id

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

类型检查器的规格说明类型检查——表达式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

类型检查器的规格说明类型检查——表达式E

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

类型检查器的规格说明类型检查——表达式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

类型检查器的规格说明类型检查——表达式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

类型检查器的规格说明语句的类型检查S

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

类型检查器的规格说明类型检查——语句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

类型检查器的规格说明S

whileEdoS1

{S.type:=ifE.type=boolean

thenS1.type

elsetype_error}7.7.2

类型检查器的规格说明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

类型检查器的规格说明程序的类型检查P

D;S

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

类型检查器的规格说明类型转换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函数和运算符的重载重载符号 有多个含义，但在引用点的含义都是唯一的例如 加法算符+可用于不同类型，是不同的函数

在Ada中，()是重载的，A(I)有不同含义7.7.3函数和运算符的重载子表达式的可能类型集合例

Ada语言声明：function“

”(i,

j:integer)returncomplex;function“

”(x,

y:complex)returncomplex;使得算符

重载，可能的类型包括：integer

integer

integerinteger

integer

complexcomplex

complex

complex

7.7.3函数和运算符的重载子表达式的可能类型集合例

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函数和运算符的重载子表达式的可能类型集合例

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是复型

7.7.3函数和运算符的重载以函数作用为例，考虑类型检查 在每个表达式都有唯一的类型时，函数作用的类型检查是：E

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

t

thent

elsetype_error}7.7.3函数和运算符的重载确定表达式可能类型的集合产

生

式

语

义

规

则

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

多态函数7.7.3.1为什么要使用多态函数例：用Pascal语言写不出求表长度的通用程序typelink=

cell; cell=record info:integer; next:link end;7.7.4多态函数functionlength(lptr:link):integer;

varlen:integer; begin

len:=0; whilelptr<>nildobegin

len:=len+1;

lptr:=lptr

.next end; length:=lenend;7.7.4多态函数用ML语言很容易写出求表长度的程序而不必管表元的类型。funlength(lptr)= ifnull(lptr)then0 elsel