语义分析与中间代码生成

语义分析与中间代码生成2024/5/32第6章

语义分析与中间代码生成6.1中间代码的形式6.2声明语句的翻译6.3赋值语句的翻译6.4类型检查6.5控制结构的翻译6.6回填6.7switch语句的翻译6.8过程调用和返回语句的翻译6.9输入输出语句的翻译6.10本章小结第2页,共126页，2024年2月25日，星期天2024/5/336.1中间代码的形式中间代码的作用过渡：经过语义分析被译成中间代码序列中间代码的形式中间语言的语句中间代码的优点形式简单、语义明确、独立于目标语言便于编译系统的实现、移植、代码优化常用的中间代码语法树(6.3.5节)逆波兰表示、三地址码(三元式和四元式)、DAG图表示第3页,共126页，2024年2月25日，星期天2024/5/346.1.1逆波兰表示中缀表达式的计算顺序不是运算符出现的自然顺序，而是根据运算符间的优先关系来确定的，因此，从中缀表达式直接生成目标代码一般比较麻烦。波兰逻辑学家J.Lukasiewicz于1929年提出了后缀表示法，其优点为：表达式的运算顺序就是运算符出现的顺序，它不需要使用括号来指示运算顺序。第4页,共126页，2024年2月25日，星期天2024/5/356.1.1逆波兰表示例6.1下面给出的是一些表达式的中缀、前缀和后缀表示。 中缀表示 前缀表示 后缀表示 a+b +ab ab+ a*(b+c) *a+bc abc+* (a+b)*(c+d) *+ab+cd ab+cd+* a:=a*b+c*d :=a+*ab*cd abc*bd*+:=第5页,共126页，2024年2月25日，星期天2024/5/366.1.2三地址码所谓三地址码，是指这种代码的每条指令最多只能包含三个地址，即两个操作数地址和一个结果地址。如x+y*z三地址码为：t1:=y*zt2:=x+t1三地址码中地址的形式：名字、常量、编译器生成的临时变量。第6页,共126页，2024年2月25日，星期天2024/5/376.1.2三地址码例6.2赋值语句a:=(-b)*(c+d)-(c+d)的三地址码如图6.1所示t1:=minusbt2:=c+dt3:=t1*t2t4:=c+dt5:=t3-t4a:=t5图6.1a:=(-b)*(c+d)-(c+d)的三地址码第7页,共126页，2024年2月25日，星期天2024/5/386.1.2三地址码1．形如x:=yopz的赋值指令；2．形如x:=opy的赋值指令；3．形如x:=y的复制指令；4．无条件跳转指令gotoL；5．形如ifxgotoL(或iffalsexgotoL)的条件跳转指令；6．形如ifxrelopygotoL的条件跳转指令；6.过程调用和返回使用如下的指令来实现：

paramx用来指明参数；

callp,n和y=callp,n用来表示过程调用和函数调用；

returny表示过程返回；8．形如x:=y[i]和x[i]:=y的变址复制指令；9．形如x:=&y、x:=*y和*x:=y的地址和指针赋值指令。第8页,共126页，2024年2月25日，星期天2024/5/39四元式

四元式是一种比较常用的中间代码形式，它由四个域组成，分别称为op、arg1、arg2和result。op是一个一元或二元运算符，arg1和arg2分别是op的两个运算对象，它们可以是变量、常量或编译器生成的临时变量，运算结果则放入result中。图6.2(a)图6.1中三地址码的四元式表示第9页,共126页，2024年2月25日，星期天2024/5/310三元式

为了节省临时变量的开销，有时也可以使用只有三个域的三元式来表示三地址码。三元式的三个域分别称为op，arg1和arg2，op，arg1和arg2的含义与四元式类似，区别只是arg1和arg2可以是某个三元式的编号(图6.2(b)中用圆括号括起来的数字)，表示用该三元式的运算结果作为运算对象。图6.2(b)图6.1中三地址码的三元式表示第10页,共126页，2024年2月25日，星期天2024/5/311生成三地址码的语法制导定义第11页,共126页，2024年2月25日，星期天2024/5/3126.1.3图表示类似于表达式的抽象语法树一样，在dag(directedacyclicgraph)中，每个节点对应一个运算符，代表表达式的一个子表达式，其子节点则与该运算符的运算对象相对应，叶节点对应的是变量或者常量，可以看成是原子运算。利用dag可以很容易地消除公共子表达式例6.3表达式a+a*(b-c)-(b-c)/d的dag如图6.5所示。图6.5a+a*(b-c)-(b-c)/d的dag图第12页,共126页，2024年2月25日，星期天2024/5/313生成dag的语法制导定义产生式语义规则⑴

E→E1+TE.node:=mknode('+',E1.node,T.node)⑵

E→E1-TE.node:=mknode('-',E1.node,T.node)⑶

E→TE.node:=T.node⑷

T→T1*FT.node:=mknode('*',T1.node,F.node)⑸

T→T1/FT.node:=mknode('/',T1.node,F.node)⑹

T→FT.node:=F.node⑺

F→(E)F.node:=E.node⑻

F→idF.node:=mkleaf(id,id.entry)⑼

F→numF.node:=mkleaf(num,num.val)第13页,共126页，2024年2月25日，星期天2024/5/3146.2声明语句的翻译声明语句的作用为程序中用到的变量或常量名指定类型类型的作用类型检查：类型检查的任务是验证程序运行时的行为是否遵守语言的类型的规定，也就是是否符合该语言关于类型的相关规则。辅助翻译：编译器从名字的类型可以确定该名字在运行时所需要的存储空间。在计算数组引用的地址、加入显式的类型转换、选择正确版本的算术运算符以及其它一些翻译工作时同样需要用到类型信息。编译的任务在符号表中记录被说明对象的属性(种别、类型、相对地址、作用域……等)，为执行做准备第14页,共126页，2024年2月25日，星期天2024/5/3156.2.1类型表达式类型可以具有一定的层次结构，因此用类型表达式来表示。类型表达式的定义如下：1．基本类型是类型表达式。 典型的基本类型包括boolean、char、integer、real及void等。2．类型名是类型表达式。3．将类型构造符array应用于数字和类型表达式所形成的表达式是类型表达式。 如果T是类型表达式，那么array(I,T)就是元素类型为T、下标集为I的数组类型表达式。4．如果T1和T2是类型表达式，则其笛卡尔乘积T1×T2也是类型表达式。第15页,共126页，2024年2月25日，星期天2024/5/3166.2.1类型表达式5．类型构造符record作用于由域名和域类型所形成的表达式也是类型表达式。记录record是一种带有命名域的数据结构，可以用来构成类型表达式。例如，下面是一段Pascal程序段：typerow=recordaddress:integer;lexeme:array[1..15]ofcharend;vartable:array[1..10]ofrow;该程序段声明了表示下列类型表达式的类型名row：record(integer×array(1..15,char))第16页,共126页，2024年2月25日，星期天2024/5/3176.2.1类型表达式6．如果T是类型表达式，那么pointer(T)也是类型表达式，表示“指向类型为T的对象的指针”。函数的类型可以用类型表达式D→R来表示。考虑如下的Pascal声明：functionf(a,b:char):↑integer；其定义域类型为char×char，值域类型为pointer(integer)。所以函数f的类型可以表示为如下的类型表达式：char×char→pointer(integer)7.类型表达式可以包含其值为类型表达式的变量。第17页,共126页，2024年2月25日，星期天2024/5/3186.2.2类型等价许多类型检查的规则都具有如下的形式：if两个类型表达式等价then返回一种特定类型else返回type_error。如果用图来表示类型表达式，当且仅当下列条件之一成立时，称两个类型T1和T2是结构等价的：T1和T2是相同的基本类型；T1和T2是将同一类型构造符应用于结构等价的类型上形成的；T1是表示T2的类型名。如果将类型名看作只代表它们自己的话，则上述条件中的前两个将导致类型表达式的名字等价两个类型表达式名字等价当且仅当它们完全相同第18页,共126页，2024年2月25日，星期天2024/5/3196.2.3声明语句的文法P→progid(input,output)D;SD→D;D|List:T|procidD;SList→List1,id|idT→integer|real|arrayCofT1|

T1|recordDC→[num]C|ε

D——程序说明部分的抽象S——程序体部分的抽象T——类型的抽象，需要表示成类型表达式C——数组下标的抽象第19页,共126页，2024年2月25日，星期天2024/5/320语义属性、辅助过程与全局变量的设置文法变量T(类型)的语义属性type：类型(表达式)width：类型所占用的字节数辅助子程序enter：将变量的类型和地址填入符号表中array：数组类型处理子程序全局变量offset：已分配空间字节数，用于计算相对地址第20页,共126页，2024年2月25日，星期天2024/5/3216.2.4过程内声明语句的翻译P→{offset:=0}

DD→D;DD→id:T{enter(,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}P→MDM→

{offset:=0

}第21页,共126页，2024年2月25日，星期天2024/5/322例x:real;i:integer的翻译enter(x,real,0)offset=0offset=8T.type=realT.width=8offset=12T.type=integerT.width=4enter(i,integer,8)D→id:T

{enter(,T.type,offset);offset:=offset+T.width}第22页,共126页，2024年2月25日，星期天2024/5/323例x:real;i:integer的翻译P

{offset:=0}D{offset:=0}D;D{offset:=0}x:T{enter(x,T.type,offset);

offset:=offset+T.width};D{offset:=0}x:real{T.type:=real;T.width:=8}

{enter(x,T.type,offset);offset:=offset+T.width};Dx:real{(x,real,0);offset:=8};Dx:real{(x,real,0);offset:=8};i:T

{enter(,T.type,offset);offset:=offset+T.width}x:real{(x,real,0);offset:=8};i:integer{T.type:=integer;T.width:=4}{enter(i,T.type,offset);offset:=offset+T.width}x:real{(x,real,0)};i:integer{(i,integer,8);offset:=12}第23页,共126页，2024年2月25日，星期天2024/5/3246.2.5嵌套过程中声明语句的翻译所讨论语言的文法

P

progid(input,output)D;S

D

D;D|id:T|procidD;S

语义动作用到的函数mktable(previous)：创建一个新的符号表；enter(table,name,type,offset)addwidth(table,width)：符号表的大小；enterproc(table,name,newtable)

在table指向的符号表中为name建立一个新表项；第24页,共126页，2024年2月25日，星期天2024/5/325P

progid(input,output)MD;S{addwidth(top(tblptr),top(offset));pop(tblptr);pop(offset)}M

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

D1;D2D

procid;ND1;S{t:=top(tblptr);addwidth(t,top(offset));pop(tblptr);pop(offset); enterproc(top(tblptr),,t)}D

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

{t:=mktable(top(tblptr)); push(t,tblptr);push(0,offset)}6.2.5嵌套过程中声明语句的翻译第25页,共126页，2024年2月25日，星期天2024/5/326programsort(input,output); vara:array[0..10]ofinteger;x:integer;procedurereadarray; vari:integer;begin…a…end；

procedureexchange(i,j:integer); beginx:=a[i];a[i]:=a[j];a[j]:=x;end；

procedurequicksort(m,n:integer); vark,v:integer; functionpartition(y,z:integer):integer; vari,j:integer; begin…a… …v……exchange(i,j)…end; begin…end；

begin…end；例一个带有嵌套的pascal程序(图6.11)第26页,共126页，2024年2月25日，星期天2024/5/327表头空sortoffsettblptrtoptop0第27页,共126页，2024年2月25日，星期天2024/5/328表头空sortoffsettblptrtoptop40aarray0第28页,共126页，2024年2月25日，星期天2024/5/329xinteger40aarray0表头空sortoffsettblptrtoptop44第29页,共126页，2024年2月25日，星期天2024/5/330表头空sortreadarrary表头offsettblptrtoptop440aarray0xinteger40第30页,共126页，2024年2月25日，星期天2024/5/331表头空sortreadarrary表头offsettblptrtoptop444aarray0xinteger40iinteger0第31页,共126页，2024年2月25日，星期天2024/5/332表头空sortreadarrary表头4offsettblptrtoptop44aarray0xinteger40iinteger0readarray指向readarray第32页,共126页，2024年2月25日，星期天2024/5/333表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头toptop0第33页,共126页，2024年2月25日，星期天2024/5/334表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange第34页,共126页，2024年2月25日，星期天2024/5/335表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort0第35页,共126页，2024年2月25日，星期天2024/5/336表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort4kinteger0第36页,共126页，2024年2月25日，星期天2024/5/337表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort8kinteger0vinteger4第37页,共126页，2024年2月25日，星期天2024/5/338表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort8kinteger0vinteger4表头partition0第38页,共126页，2024年2月25日，星期天2024/5/339表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort8kinteger0vinteger4表头partition4iinteger0第39页,共126页，2024年2月25日，星期天2024/5/340表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort8kinteger0vinteger4表头partition8iinteger0jinteger4第40页,共126页，2024年2月25日，星期天2024/5/341表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头quicksort8kinteger0vinteger4表头8partitioniinteger0jinteger4partition第41页,共126页，2024年2月25日，星期天2024/5/342表头空sortreadarrary表头4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头8quicksortkinteger0vinteger4表头8partitioniinteger0jinteger4partitionquicksort第42页,共126页，2024年2月25日，星期天2024/5/343表头44空sortreadarrary表头4offsettblptraarray0xinteger40iinteger0readarray指向readarrayexchange表头0toptopexchange指向exchange表头8quicksortkinteger0vinteger4表头8partitioniinteger0jinteger4partitionquicksort第43页,共126页，2024年2月25日，星期天2024/5/3446.2.6记录的翻译空间分配设置首地址和各元素的相对地址大于所需的空间(对齐)例：structNode{floatx,y;structnode*next;}node;048第44页,共126页，2024年2月25日，星期天2024/5/3456.2.6记录的翻译符号表及有关表格处理为每个记录类型单独构造一张符号表将域名id的信息(名字、类型、字节数)填入到该记录的符号表中所有域都处理完后，offset将保存记录中所有数据对象的宽度总和T.type通过将类型构造器record应用于指向该记录符号表的指针获得第45页,共126页，2024年2月25日，星期天2024/5/3466.2.6记录的翻译T

recordDendT

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

{t:=mktable(nil); push(t,tblprt);push(0,offset)}第46页,共126页，2024年2月25日，星期天2024/5/3476.3赋值语句的翻译翻译的需求充分了解各种语言现象的语义包括：控制结构、数据结构、单词充分了解它们的实现方法目标语言的语义了解中间代码的语义了解运行环境第47页,共126页，2024年2月25日，星期天2024/5/348辅助子程序与语义属性设置辅助子程序gencode(code)，emit(code)：产生一条中间代码newtemp：产生新的临时变量lookup：检查符号表中是否出现某名字语义属性设置中间代码序列：code地址：addr下一条四元式序号：nextquad第48页,共126页，2024年2月25日，星期天2024/5/3496.3.1简单赋值语句的翻译S

id:=E {p:=lookup(); ifp

nilthen gencode(p,‘:=’,E.addr) elseerror}E

E1+E2

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

E1

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

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

id{p:=lookup(); ifp

nilthenE.addr:=pelseerror}第49页,共126页，2024年2月25日，星期天2024/5/350临时名字的重用大量临时变量的使用对优化有利大量临时变量会增加符号表管理的负担也会增加运行时临时数据占的空间E

E1+E2的动作产生的代码的一般形式为 计算E1到t1

计算E2到t2 t3:=t1+t2 (())((()())())临时变量的生存期像配对括号那样嵌套或并列第50页,共126页，2024年2月25日，星期天2024/5/351基于临时变量生存期特征的三地址代码x:=a

b+c

d

e

f语句计数器c的值0

$0:=a

b1

$1:=c

d2

$0:=$0+$11

$1:=e

f2

$0:=$0

$11

x:=$00引入一个计数器c，它的初值为0。每当临时变量仅作为运算对象使用时，c减去1；每当要求产生新的临时名字时，使用$c并把c增加1。第51页,共126页，2024年2月25日，星期天2024/5/3526.3.2数组元素的寻址数组元素引用的翻译完成上下界检查生成完成相对地址计算的代码目标x:=y[i]和y[i]:=xy为数组地址的固定部分——相当于第1个元素的地址，i是相对地址，不是数组下标数组说明的翻译符号表及有关表格(内情向量)的处理维数、下标上界、下标下界、类型等首地址、需用空间计算按行存放、按列存放——影响具体元素地址的计算第52页,共126页，2024年2月25日，星期天2024/5/353数组元素地址计算——行优先一维数组A[low1:up1](nk=upk-lowk+1)addr(A[i])=base+(i-low1)*w =(base-low1*w)+i*w=c+i*w二维数组A[low1:up1,low2:up2]；A[i1,i2]addr(A[i1,i2])=base+((i1-low1)*n2+(i2-low2))*w =base+(i1-low1)*n2*w+(i2-low2)*w =base-low1*n2*w-low2*w+i1*n2*w+i2*w =base-(low1*n2-low2)*w+(i1*n2+i2)*w =c+(i1*n2+i2)*wA[1,1],A[1,2],A[1,3]A[2,1],A[2,2],A[2,3]第53页,共126页，2024年2月25日，星期天2024/5/354数组元素地址计算的翻译方案设计下标变量访问的产生式

L

id[Elist]|id Elist

Elist,E|E为了使数组各维的长度n在我们将下标表达式合并到Elist时是可用的，需将产生式改写为：

L

Elist]|id Elist

Elist,E|id[E第54页,共126页，2024年2月25日，星期天2024/5/355数组元素地址计算的翻译方案设计

L

Elist]|idElist

Elist,E|id[E目的使我们在整个下标表达式列表Elist的翻译过程中随时都能知道符号表中相应于数组名id的表项，从而能够了解登记在符号表中的有关数组id的全部信息。于是我们就可以为非终结符Elist引进一个综合属性Elist.array，用来记录指向符号表中相应数组名字表项的指针。第55页,共126页，2024年2月25日，星期天2024/5/356数组元素地址计算的翻译方案设计属性Elist.array，用来记录指向符号表中相应数组名字表项的指针。Elist.ndim，用来记录Elist中下标表达式的个数，即数组的维数。Elist.addr，用来临时存放Elist的下标表达式计算出来的值。函数limit(array,j)，返回nj第56页,共126页，2024年2月25日，星期天2024/5/3576.3.3带有数组引用的赋值语句的翻译S

Left:=EE

E+EE

(E)E

LeftLeft

Elist]Left

idElist

Elist,EElist

id[E第57页,共126页，2024年2月25日，星期天2024/5/358赋值语句的翻译模式Left

id{Left.addr:=id.addr;Left.offset:=null}Elist

id[E{Elist.addr:=E.addr;Elist.ndim:=1; Elist.array:=id.addr}Elist

Elist1,E{t:=newtemp;m:=Elist1.ndim+1;gencode(t,‘:=’,Elist1.addr,‘

’,limit(Elist1.array,m));gencode(t,‘:=’,t,‘+’,E.addr);Elist.array:=Elist1.array;Elist.addr:=t;Elist.ndim:=m}Left

Elist] {Left.addr:=newtemp;Left.offset:=newtemp;gencode(Left.addr,‘:=’,base(Elist.array),‘

’,invariant(Elist.array));gencode(Left.offset,‘:=’,Elist.addr,‘

’,w)}i1*n2(i1*n2)+i2((i1*n2)+i2)*wbase-(low1*n2-low2)*w第58页,共126页，2024年2月25日，星期天2024/5/359赋值语句的翻译模式E

Left

{ifLeft.offset=nullthen/

Left是简单变量

/ E.addr:=Left.addr elsebeginE.addr:=newtemp; gencode(E.addr,‘:=’,Left.addr,‘[’,Left.offset,‘]’)end}E

E1+E2

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

(E1)

{E.addr:=E1.addr}S

Left:=E{ifLeft.offset=nullthen/

Left是简单变量

/ gencode(Left.addr,‘:=’,E.addr) else gencode(Left.addr,‘[’,Left.offset,‘]’,‘:=’,E.addr)}((i1*n2)+i2)*w+(base-(low1*n2-low2)*w)((i1*n2)+i2)*w+(base-(low1*n2-low2)*w)第59页,共126页，2024年2月25日，星期天2024/5/360例：设A是一个10×20的整型数组

——w=4

S:=Left.place:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注释分析树第60页,共126页，2024年2月25日，星期天2024/5/361例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注释分析树t1:=y

20t1:=t1+z第61页,共126页，2024年2月25日，星期天2024/5/362例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注释分析树t1:=y

20t1:=t1+zt2:=baseA

84t3:=4

t1

第62页,共126页，2024年2月25日，星期天2024/5/363例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注释分析树t1:=y

20t1:=t1+zt4:=t2[t3]t2:=baseA

84t3:=4

t1

第63页,共126页，2024年2月25日，星期天2024/5/364例S:=Left.addr:=xLeft.offset:=nullxE.addr:=t4Left.addr:=t2Left.offset:=t3Elist.addr:=t1Elist.ndim:=2Elist.array:=A,Elist.addr:=yElist.ndim:=1Elist.array:=AE.addr:=zLeft.addr:=zLeft.offset:=nullE.addr:=yLeft.addr:=yLeft.offset:=nullA[z]y

x:=A[y,z]的注释分析树t1:=y

20t1:=t1+zt4:=t2[t3]x:=t4

t2:=baseA

84t3:=4

t1

第64页,共126页，2024年2月25日，星期天2024/5/3656.4类型检查类型检查具有发现程序错误的能力，为了进行类型检查，编译程序需要为源程序的每个语法成分赋予一个类型表达式，名字的类型表达式保存在符号表中，其他语法成分(如表达式E或语句S)的类型表达式则作为文法符号的属性保存在语义栈中。类型检查的任务就是确定这些类型表达式是否符合一定的规则，这些规则的集合通常称为源程序的类型系统第65页,共126页，2024年2月25日，星期天2024/5/3666.4.1类型检查的规则类型综合从子表达式的类型确定表达式的类型要求名字在引用之前必须先进行声明iff的类型为s→tandx的类型为sthen表达式f(x)的类型为t

类型推断根据语言结构的使用方式来确定其类型经常被用于从函数体推断函数类型iff(x)是一个表达式then对某两个类型变量α和β，f具有类型

→βandx具有类型

第66页,共126页，2024年2月25日，星期天2024/5/3676.4.2类型转换x:=y+i

j（x和y的类型是real，i和j的类型是integer）中间代码t1:=iint

jt2:=inttorealt1

t3:=yreal+t2

x:=t3第67页,共126页，2024年2月25日，星期天2024/5/3686.4.2类型转换E

E1+E2的语义子程序{E.addr:=newtempifE1.type=integerandE2.type=integerthenbegin gencode(E.addr,‘:=’,E1.addr,‘int+’,E2.addr); E.type=integerendelseifE1.type=integerandE2.type=realthenbegin u:=newtemp; gencode(u,‘:=’,‘inttoreal’,E1.addr); gencode(E.addr,‘:=’,u,‘real+’,E2.addr); E.type:=realend...}第68页,共126页，2024年2月25日，星期天2024/5/3696.5控制结构的翻译高级语言的控制结构顺序结构begin语句;…；语句end分支结构if_then_else、if_then switch、case循环结构while_do、do_whilefor、repeat_untilgoto语句三地址码goton (j,_,_,n)ifxrelopygoton (jrelop,x,y,n)第69页,共126页，2024年2月25日，星期天2024/5/3706.5.1布尔表达式的翻译基本文法B

B1orB2|B1andB2|notB1|(B1)|E1relopE2|true|false处理方式数值表示法(与算术表达式的处理类似)真：B.addr=1假：B.addr=0真假出口表示法(作为其他语句的条件改变控制流程，隐含着程序中的位置)真出口：B.true假出口：B.false第70页,共126页，2024年2月25日，星期天2024/5/3716.5.1布尔表达式的翻译aorbandnotct1:=notct2:=bandt1t3:=aort2a<b100:ifa<bgoto103101:t:=0102:goto104103:t:=1104第71页,共126页，2024年2月25日，星期天2024/5/372用数值表示布尔值的翻译nextquad是下一条三地址码指令的序号，每生成一条三地址码指令gencode便会将nextquad加1B

B1orB2{B.addr:=newtemp;gencode(B.addr':='B1.addr‘or'B2.addr)}B

B1andB2{B.addr:=newtemp;gencode(B.addr':='B1.addr‘and'B2.addr)}B

notB1{B.addr:=newtemp; gencode(B.addr':=''not'B1.addr)}第72页,共126页，2024年2月25日，星期天2024/5/373用数值表示布尔值的翻译B

(B1){B.addr:=B1.addr}B

E1relopE2

{B.addr:=newtemp;gencode('if‘E1.addrrelop.opE2.addr'goto'nextquad+3); gencode(B.addr':=''0');gencode('goto'nextquad+2); gencode(B.addr':=''1')}B

true{B.addr:=newtemp;gencode(B.addr':=''1')}B

false{B.addr:=newtemp;gencode(B.addr':=''0')}第73页,共126页，2024年2月25日，星期天2024/5/374例6.8对a<borc<dande<f的翻译100:ifa<bgoto103 107:t2:=1101:t1:=0 108:ife<fgoto111102:goto104 109:t3:=0103:t1:=1 110:goto112104:ifc<dgoto107 111:t3:=1105:t2:=0 112:t4:=t2andt3106:goto100 113:t5:=t1ort4第74页,共126页，2024年2月25日，星期天2024/5/3756.5.2常见控制结构的翻译文法S→ifBthenS1S→ifBthenS1elseS2S→whileBdoS1S→beginSlistendSlist→Slist;S|SB是控制结构中的布尔表达式函数newlabel返回一个新的语句标号属性B.true和B.false分别用于保存B为真和假时控制流要转向的语句标号第75页,共126页，2024年2月25日，星期天2024/5/3766.5.2常见控制结构的翻译翻译S时允许控制从S.code中跳转到紧接在S.code之后的那条三地址码指令，但在某些情况下，紧跟S.code的指令是跳转到某个标号L的跳转指令，用继承属性S.next可以避免从S.code中跳转到一条跳转指令这样的连续跳转。S.next的值是一个语句标号，它是S的代码执行后应执行的第一个三地址码指令的标号。while语句中用S.begin保存语句的开始位置

第76页,共126页，2024年2月25日，星期天2024/5/3776.5.2常见控制结构的翻译B.codeS1.codeB.true:...指向B.true指向B.false(a)if-thenB.codeS1.codeB.true:...指向B.true指向B.falseB.false:gotoS.nextS2.code(b)if-then-elseB.codeS1.codeB.true:...指向B.true指向B.falsegotoS.beginS.begin:(c)while-doS1.codeS2.codeS1.next:...(d)S1;S2图6.25if-then、if-then-else和while-do语句的目标代码结构第77页,共126页，2024年2月25日，星期天2024/5/3786.5.2常见控制结构的翻译S

ifBthenS1{B.true:=newlabel;B.false:=S.next;S1.next:=S.next;S.code:=B.code||gencode(B.true,‘:’)||S1.code}B.codeS1.codeB.true:...指向B.true指向B.false(a)if-then第78页,共126页，2024年2月25日，星期天2024/5/3796.5.2常见控制结构的翻译S

ifBthenS1elseS2{B.true:=newlabel;B.false:=newlabel;S1.next:=S.next;S2.next:=S.next;S.code:=B.code||gencode(B.true,‘:’)||S1.code||gencode(‘goto’,S.next)||gen(B.false,‘:’)||S2.code}B.codeS1.codeB.true:...指向B.true指向B.falseB.false:gotoS.nextS2.code(b)if-then-else第79页,共126页，2024年2月25日，星期天2024/5/3806.5.2常见控制结构的翻译S

whileBdoS1

{S.begin:=newlabel;B.true:=newlabel;B.false:=S.next;S1.next:=S.begin;S.code:=gencode(S.begin,‘:’)||B.code||gencode(B.true,‘:’)||S1.code||gencode(‘goto’,S.begin)}B.codeS1.codeB.true:...指向B.true指向B.falsegotoS.beginS.begin:(c)while-do第80页,共126页，2024年2月25日，星期天2024/5/3816.5.2常见控制结构的翻译S

S1;S2{S1.next:=newlabel;S2.next:=S.next;S.code:=S1.code||gencode(S1.next,‘:’)||S2.code}S1.codeS2.codeS1.next:...(d)S1;S2第81页,共126页，2024年2月25日，星期天2024/5/3826.5.3布尔表达式的控制流翻译属性(继承属性)B.true，B为真时控制到达的位置；B.false，B为假时控制到达的位置。a<bifa<bgotoB.truegotoB.falseB→B1orB2如果B1为真，则立即可知B为真，即B1.true与B.true相同；如果B1为假，则必须计算B2的值，令B1.false为B2的开始B2的真假出口分别与B的真假出口相同第82页,共126页，2024年2月25日，星期天2024/5/383简单布尔表达式的翻译示例

——例6.9a<borc<dande<f

ifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalse第83页,共126页，2024年2月25日，星期天2024/5/3846.5.3布尔表达式的控制流翻译B

B1orB2{B1.true:=B.true;B1.false:=newlabel; B2.true=B.true;B2.false:=B.false;B.code:=B1.code||gencode(B1.false’:’)||B2.code}B

B1andB2{B1.true:=newlabel;B1.false:=B.false;B2.true=B.true;B2.false:=B.false;B.code:=B1.code||gencode(B1.true’:’)||B2.code}B

notB1{B1.true:=B.false;B1.false:=B.true；

B.code:=B1.code}第84页,共126页，2024年2月25日，星期天2024/5/3856.5.3布尔表达式的控制流翻译B

(B1){B1.true:=B.

true;B1.false:=B.false；

B.code:=B1.code}B

E1relopE2

{B.code:=gencode(‘if’E1.addrrelopE2.addr‘goto’B.true)；

||gencode('goto'B.false)}B

true{B.code:=gencode('goto'B.true)}B

false{B.code:=gencode('goto'B.false)}第85页,共126页，2024年2月25日，星期天2024/5/386例6.10：翻译下列语句whilea<bdo

B1ifc<dthen

B2S1

x:=y+zelseS2

x:=y-zS3第86页,共126页，2024年2月25日，星期天2024/5/387生成的三地址代码序列L1:ifa<bgotoL2gotoLnextL2:ifc<dgotoL3gotoL4L3:t1:=y+zx:=t1

gotoL1L4:t2:=y-zx:=t2gotoL1Lnext:B1.codeB2.codeS1.codeS2.codeS3.codewhilea<bdo

ifc<dthen

x:=y+zelsex:=y-z第87页,共126页，2024年2月25日，星期天2024/5/3886.5.4混合模式的布尔表达式翻译E

E1relopE2│E1+E2│E1andE2│idE1+E2、id产生算术结果E1relopE2、E1andE2产生布尔值E1andE2：E1和E2必须都是布尔型的引入语义属性E.type:arith或者boolE.true,E.falseE.addr第88页,共126页，2024年2月25日，星期天2024/5/3896.5.4混合模式的布尔表达式翻译E

E1relopE2{E.code:=E1.code||E2.code||gencode(‘if’E1.addrrelopE2.addr‘goto‘E.true)||

gencode('goto'E.false)}第8