编译原理课件：第六章 类 型 检 查

编译原理Compilers–Principles,TechniquesandTools第六章类型检查

本章内容静态检查中最典型的部分—类型检查设计语法制导的类型检查器忽略其它的静态检查：控制流检查、唯一性检查、关联名字检查语法分析器类型检查器中间代码生成器语法树语法树中间表示记号流简单类型检查器的说明类型检查——声明语句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}简单类型检查器的说明类型检查——表达式E

truth

{E.type=boolean}E

num

{E.type=integer}E

id

{E.type=lookup(id.entry)}简单类型检查器的说明类型检查——表达式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}简单类型检查器的说明类型检查——表达式E

E1[E2]{E.type=ifE2.type==integerand E1.type==array(s,t)thent elsetype_error}简单类型检查器的说明类型检查——表达式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==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}简单类型检查器的说明类型转换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.1

中间语言7.1.1后缀表示

EE

opE|uopE|(E)|id|num表达式E的后缀表示可以如下归纳定义：

表达式E 后缀式E

id

id

num num

E1opE2 E1E2

op uopE Euop

(E) E7.1

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

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

后缀表示的最大优点是便于计算机处理表达式 计算栈 输入串

852+

8 52+ 85 2+ 3 2+ 32 +

57.1

中间语言7.1.2

图形表示语法树是一种图形化的中间表示有向无环图也是一种中间表示assigna++bcduminus(b)DAGassigna++bcdcduminus(a)语法树

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

中间语言构造赋值语句语法树的语法制导定义

产

生

式

语

义

规

则Sid=E

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

ygotoL过程调用paramx

和callp,n过程返回

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

声明语句本节介绍为局部名字建立符号表条目为它分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息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

声明语句符号表的特点各过程有各自的符号表符号表之间有双向链构造符号表时需要符号表栈构造符号表需要活动记录栈语义动作用到的函数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}第八章代码生成本章内容一个简单的代码生成算法涉及存储管理，指令选择，寄存器分配和计算次序选择等基本问题前端代码优化器中间代码源程序代码生成器中间代码目标程序8.1

代码生成器的设计中的问题8.1.1

目标程序绝对机器语言程序目标程序将装入到内存的固定地方可重定位目标模块代码中含重定位信息，以适应重定位要求8.1

代码生成器的设计中的问题8.1.1

目标程序绝对机器语言程序目标程序将装入到内存的固定地方可重定位目标模块代码中含重定位信息，以适应重定位要求允许程序模块分别编译调用其它先前编译好的程序模块8.1

代码生成器的设计中的问题8.1.1

目标程序绝对机器语言程序可重定位目标模块代码中含重定位信息，以适应重定位要求允许程序模块分别编译调用其它先前编译好的程序模块汇编语言程序免去编译器重复汇编器的工作从教学角度，增加可读性8.1

代码生成器的设计中的问题8.1.2

指令的选择目标机器指令系统的性质决定了指令选择的难易程度，指令系统的统一性和完备性是重要的因素指令的速度和机器特点是另一些重要的因素8.1

代码生成器的设计中的问题若不考虑目标程序的效率，指令的选择是直截了当的例 三地址语句x=y+z(x，y和z都静态分配)

MOV y, R0 /

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

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

把R0存入x中/逐条语句地产生代码，常常得到低质量的代码

8.1

代码生成器的设计中的问题语句序列

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

代码生成器的设计中的问题语句序列

a=b+c d=a+e的代码如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 －－多余的指令ADD e, R0 MOV R0, d 8.1

代码生成器的设计中的问题语句序列

a=b+c d=a+e的代码如下MOV b, R0ADD c, R0MOV R0, aMOV a, R0 －－多余的指令ADD e, R0 －－若a不再使用，MOV R0, d －－第三条指令也多余8.1

代码生成器的设计中的问题8.1.3寄存器分配 运算对象处于寄存器和处于内存相比，指令要短一些，执行也快一些寄存器分配

选择驻留在寄存器中的一组变量寄存器指派

挑选变量要驻留的具体寄存器8.2

目标机器8.2.1目标机器的指令系统选择可作为几种微机代表的寄存器机器四个字节组成一个字，有n个通用寄存器R0,R1,…,Rn-1二地址指令：

op源，目的 MOV {源传到目的} ADD {源加到目的} SUB {目的减去源}8.2

目标机器地址模式和它们的汇编语言形式及附加代价模式 形式 地址 附加代价绝对地址 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

目标机器例 指令实例

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

目标机器8.2.2指令的代价指令代价简化为 1+指令的源和目的地址模式的附加代价8.2

目标机器地址模式和它们的汇编语言形式及附加代价模式 形式 地址 附加代价绝对地址 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

目标机器8.2.2指令的代价指令代价简化为 1+指令的源和目的地址模式的附加代价 指令 代价

MOVR0，R1 1

MOVR5，M 2

ADD#1，R3 2

SUB4(R0),12(R1) 38.3

基本块和流图怎样为三地址语句序列生成目标代码？

先给出本节用例 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基本块基本块连续的语句序列，控 制流从它的开始进入， 并从它的末尾离开流图再用有向边表示基本块 之间的控制流信息，就 能得到程序的流图(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一个简单的代码生成器为单个块生成代码依次考虑三地址指令进行寄存器组织和管理（最大限度地利用）执行一个运算时，部分或全部分量在寄存器中寄存器存放单个组块内的临时变量寄存器可以存放全局值运行时刻的存储管理一个简单的代码生成器为单个块生成代码每个寄存器都有寄存器描述符跟踪哪些变量的当前值存放在此寄存器每个变量都有地址描述符跟踪哪些位置上可找到该变量的当前值。位置可以指一个寄存器、一个内存地址、一个栈中的位置t=a-b

LDR1,aLDR2,bSUBR2,R1,R2abcdR1R2R3abcdtuvata,R1bcdR2一个简单的代码生成器代码生成算法getReg(I)：为每个与三地址指令I有关的内存位置选择寄存器运算的机器指令：x=y+zgetReg(x=y+z)为x、y、z选择寄存器，记为Rx、Ry、Rz如果y不在Ry的寄存器描述符中，则生成指令“LDRy,y’”，其中y’是存放y的内存位置之一(y’可以根据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