编译7语义分析及中间代码产生1

编译原理(第三版)

陈火旺等编著（2015年9月-10月）主讲：朱世松计算机学院22023/2/3概述一、语义分析的任务审查每一个语法结构的静态语义，即验证语法正确的结构是否有意义。 如：赋值语句：x=x+y,左边变量类型与右边变量类型是否一致。在语义正确的基础上生成一种中间代码或目标代码。32023/2/3二、语义分析的范围1.确定类型：确定标识符所关联的数据类型。2.类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。3.识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义，并作相应的语义处理（生成中间代码或目标代码）42023/2/34.控制流检查：控制流语句必须转移到合法的地方。如：C中，break语句规定跳出最内层的循环或switch语句.5.一致性检查：在很多场合要求对象只能被说明一次(避免重复定义)。6.相关名字检查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。52023/2/3三、语义描述工具和语义分析方法语义描述工具目前流行：用属性文法作为描述语义的工具。语义分析方法 根据描述属性文法的语义规则的方式不同，语义分析方法分为：语法制导定义方法翻译方案62023/2/31中间语言中间语言：它介于源程序到目标语言程序中间程序的语言中间语言程序：用中间语言表示的程序。作用：用于编译程序，将源程序翻译成等价的中间语言程序，再将中间语言程序转化成目标程序（即将语义分析和目标代码生成分开处理）源程序 中间语言程序 目标程序中间语言是表示语法制导翻译的结果。等价变换转化7.1中间语言72023/2/3好处：中间语言与机器无关，使采用中间语言进行翻译的编译程序系统易于移植。易于优化翻译后的代码。使编译程序的结构在逻辑上更简单明确。2中间语言的表示常见：逆波兰表示 四元式表示和三地址代码、三元式 图表示：DAG和树形表示82023/2/37.1.1逆波兰表示由波兰逻辑学家J.Lukasiewicz(卢卡西维兹)首先提出用来表示表达式的方法，后来推广到表示程序设计语言中的其它语法成分。表达式的逆波兰表示表达式的表示：中缀表示： 运算符居中，运算对象在左右两边:a+b波兰表示：前缀表示：运算符在前，运算对象在后：+ab后缀表示：运算对象在前，运算符在后：ab+…(逆波兰表示)92023/2/3例：逆波兰表示的例子102023/2/3(1)表达式逆波兰表示的定义：设E是一般表达式，则：

一般表达式

逆波兰表达式若E为变量或常量 E（E） E的逆波兰式E(1)opE(2)(二目运算) E(1)的逆波兰式E(2)的逆波兰式opopE(单目运算) E的逆波兰式op112023/2/3把表达式翻译成后缀式的语义规则描述产生式E→E(1)opE(2)E→(E(1))E→id

语义动作E.code:=E(1).code||E(2).code||opE.code:=E(1).codeE.code:=idE.code表示E后缀形式op表示任意二元操作符“||”表示后缀形式的连接。122023/2/3(2)逆波兰表示的特点a.标识符(运算对象)出现的顺序（从左到右）和原有顺序相同。b.运算符是按实际计算顺序（从左到右）出现的。c.运算符紧跟在运算对象的后面出现，并且没有括号。132023/2/3(3)好处：易于对表达式的计算处理对于一般表达式的计算，系统需要用两个工作栈分别处理运算对象和运算符。对于逆波兰表示的表达式计算处理只用一个工作栈。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。142023/2/3例：逆波兰式ab+c*的计算处理过程遇运算对象a,b入栈扫描ab+c*栈遇二目运算符+c*取出a,b，运算结果T入栈取出c,T作运算，设结果T1遇运算符*c*遇运算对象c入栈152023/2/32.形成逆波兰表示 怎样将一般表达式转换成逆波兰表示？

基本思想:从左到右扫描表达式，每遇到：

1o

表达式中的运算对象则往左去。

2o

表达式中的运算符，则与运算符栈顶元素比较优先数：162023/2/3逆波兰表示表达式运算对象运算符进栈出栈运算符栈

如果运算符栈顶元素的优先数大于或等于表达式中当前的运算符优先数，则栈顶元素退栈向左去。然后当前运算符继续与栈顶的新元素比较优先数。直到栈顶元素的优先数小于表达式中当前运算符为止。此时，才将表达式中当前运算符进栈。172023/2/3例：画出形成表达式a*(b+c/d)的逆波兰表示过程a*(b+c/d)##步骤①a(b+c/d)#*#步骤②ab+c/d)#(*#步骤③ab+c/d)#(*#步骤④abc/d)#+(*#步骤⑤abc/d)#+(*#步骤⑥182023/2/3abcd)#/+(*#步骤⑦abcd)#/+(*#步骤⑧/+(*#abcd/)#步骤⑨+(*#abcd/+)#步骤⑩*#abcd/+*#步骤⑾192023/2/3形成逆波兰表示的过程，实质上是表达式的翻译过程。（算法不难写出）例：a/b/c+d=>ab/c/d+(a+b)*(c-d/e)=>ab+cde/-*202023/2/3数组POST存放后缀式：k为下标，初值为1上述语义动作可实现为： 产生式 程序段

E→E(1)opE(2) {POST[k]:=op;k:=k+1} E→(E(1)) {} E→i {POST[k]:=i;k:=k+1}例：输入串a+b+c的分析和翻译

POST：12345E→E(1)opE(2) E.code:=E(1).code||E(2).code||opE→(E(1)) E.code:=E(1).codeE→id E.code:=idab+c+…212023/2/37.1.2图表示法图表示法DAG抽象语法树

222023/2/37.1.2图表示法无循环有向图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点232023/2/3a:=b*(-c)+b*(-c)的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc242023/2/3抽象语法树对应的代码：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象语法树*buminusc252023/2/3DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5262023/2/3

产生赋值语句抽象语法树的属性文法

产生式 语义规则S→id:=E S.nptr:=mknode(‘assign’,

mkleaf(id,id.place),E.nptr)E→E1+E2

E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2

E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E→-E1

E.nptr:=mknode(‘uminus’,E1.nptr)E→(E1) E.nptr:=E1.nptrE→id E.nptr:=mkleaf(id,id.place)272023/2/37.1.3三地址代码三地址代码x:=yopz三地址代码可以看成是抽象语法树或DAG的一种线性表示282023/2/3a:=b*(-c)+b*(-c)的图表示法assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc292023/2/3 T1:=-c T1:=-c T2:=b*T1 T2:=b*T1 T3:=-c T5:=T2+T2 T4:=b*T3 a:=T5 T5:=T2+T4

a:=T5对于抽象语法树的代码 对于DAG的代码302023/2/3三地址语句的种类x:=yopzx:=opyx:=ygotoLifxrelopygotoL或ifagotoLparamx和callp,n,以及返回语句returnyx:=y[i]及x[i]:=y的索引赋值x:=&y,x:=*y和*x:=y的地址和指针赋值312023/2/3生成三地址代码时，临时变量的名字对应抽象语法树的内部结点id:=E对表达式E求值并置于变量T中值id.place:=T322023/2/3从赋值语句生成三地址代码的S-属性文法非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。非终结符号E有如下两个属性：E.place表示存放E值的名字。E.code表示对E求值的三地址语句序列。函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,…。gen(x‘:=’y‘+’z)表示生成三地址代码。332023/2/3为赋值语句生成三地址代码的S-属性文法定义

产生式 语义规则S→id:=E S.code:=E.code||gen(id.place‘:=’E.place)E→E1+E2 E.place:=newtemp; E.code:=E1.code||E2.code|| gen(E.place‘:=’E1.place‘+’E2.place)E→E1*E2 E.place:=newtemp; E.code:=E1.code||E2.code|| gen(E.place‘:=’E1.place‘*’E2.place)E→-E1 E.place:=newtemp; E.code:=E1.code|| gen(E.place‘:=’‘uminus’E1.place)E→(E1) E.place:=E1.place; E.code:=E1.codeE→id E.place:=id.place; E.code=‘’342023/2/3三地址语句四元式一个带有四个域的记录结构，这四个域分别称为op,arg1,arg2及result op arg1 arg2 result(0) uminus c T1(1) * b T1 T2(2) uminus c T3(3) * b T3 T4(4) + T2 T4 T5(5) := T5 a

352023/2/3三地址语句三元式通过计算临时变