编译7语义分析和中间代码产生1(zss).ppt

编译原理编译原理(第三版第三版)陈火旺等编著（2012201220122012年年年年9 9 9 9月月月月-12-12-12-12月）月）月）月）主讲：朱世松主讲：朱世松计算机学院计算机学院4/20/20231概述概述一、语义分析的任务一、语义分析的任务1.审查每一个语法结构的静态语义，即验证语法正确的结构是否有意义。如：赋值语句：x=x+y,左边变量类型与右边变量类型是否一致。2.在语义正确的基础上生成一种中间代码或目标代码。4/20/20232二、语义分析的范围二、语义分析的范围1.确定类型：确定标识符所关联的数据类型。2.类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。3.识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义，并作相应的语义处理（生成中间代码或目标代码）4.控制流检查：控制流语句必须转移到合法的地方。如：C中，break语句规定跳出最内层的循环或switch语句.4/20/202335.一致性检查：在很多场合要求对象只能被说明一次(避免重复定义)。6.相关名字检查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。4/20/20234三、语义描述工具和语义分析方法三、语义描述工具和语义分析方法1.语义描述工具 目前流行：用属性文法属性文法作为描述语义的工具。2.语义分析方法根据描述属性文法的语义规则的方式不同，语义分析方法分为：语法制导定义方法翻译方案4/20/202351 中间语言n中间语言：它介于源程序到目标语言程序中间程序的语言n中间语言程序：用中间语言表示的程序。n作用：用于编译程序，将源程序翻译成等价的中间语言程序，再将中间语言程序转化成目标程序（即将语义分析和目标代码生成分开处理）n源程序 中间语言程序目标程序n中间语言是表示语法制导翻译的结果。等价变换转化7.1 7.1 中中 间间 语语 言言4/20/20236好处：n中间语言与机器无关，使采用中间语言进行翻译的编译程序系统易于移植。n易于优化翻译后的代码。n使编译程序的结构在逻辑上更简单明确。2 中间语言的表示常见：逆波兰表示 四元式表示和三地址代码、三元式 图表示：DAG和树形表示4/20/202377.1.1 逆波兰表示逆波兰表示 由波兰逻辑学家J.Lukasiewicz(卢卡西维兹)首先提出用来表示表达式的方法，后来推广到表示程序设计语言中的其它语法成分。1.表达式的逆波兰表示表达式的逆波兰表示2.表达式的表示：n中缀表示：运算符居中，运算对象在左右两边:a+bn波兰表示：前缀表示：运算符在前，运算对象在后：+ab后缀表示：运算对象在前，运算符在后：ab+(逆波兰表示)4/20/20238n例：逆波兰表示的例子中缀表示(一般表示)逆波兰表示a+b*cabc*+a*(b+c/d)abcd/+*a*b+cab*c+a*b+(c-d)/eab*cd-e/+4/20/20239(1)表达式逆波兰表示的定义：设E是一般表达式，则：一般表达式一般表达式逆波兰表达式逆波兰表达式n若E为变量或常量En（E）E的逆波兰式nE(1)opE(2)(二目运算)E(1)的逆波兰式 E(2)的逆波兰式 opnopE(单目运算)E的逆波兰式 op4/20/202310把表达式翻译成后缀式的语义规则描述把表达式翻译成后缀式的语义规则描述 产生式产生式EE(1)op E(2)E(E(1)Eid语义动作语义动作E.code:=E(1).code|E(2).code|opE.code:=E(1).codeE.code:=idE.code表示表示E后缀形式后缀形式op表示任意二元操作符表示任意二元操作符“|”表示后缀形式的连接表示后缀形式的连接。4/20/202311 (2)逆波兰表示的特点a.标识符(运算对象)出现的顺序（从左到右）和原有顺序相同。b.运算符是按实际计算顺序（从左到右）出现的。c.运算符紧跟在运算对象的后面出现，并且没有括号。4/20/202312(3)好处：易于对表达式的计算处理n对于一般表达式的计算，系统需要用两个工作栈分别处理运算对象和运算符。n对于逆波兰表示的表达式计算处理只用一个工作栈。一一般般的的计计算算过过程程是是：自自左左至至右右扫扫描描后后缀缀式式，每每碰碰到到运运算算量量就就把把它它推推进进栈栈。每每碰碰到到k目目运运算算符符就就把把它它作作用用于于栈栈顶顶的的k个个项项，并并用用运运算算结结果果代代替替这这k个项个项。4/20/202313例：逆波兰式ab+c*的计算处理过程遇运算对象a,b入栈扫描ab+c*ba栈遇二目运算符+c*取出a,b，运算结果T入栈TcT取出c,T作运算，设结果T1T1遇运算符*c*遇运算对象c入栈4/20/2023142.形成逆波兰表示怎样将一般表达式转换成逆波兰表示？基本思想基本思想:从左到右扫描表达式，每遇到：1o 表达式中的运算对象则往左去。2o 表达式中的运算符，则与运算符栈顶元素比较优先数：4/20/202315逆波兰表示表达式运算对象运算符进栈出栈运算符栈 如果运算符栈顶元素的优先数大于或等于表达式中当前的运算符优先数，则栈顶元素退栈向左去。然后当前运算符继续与栈顶的新元素比较优先数。直到栈顶元素的优先数小于表达式中当前运算符为止。此时，才将表达式中当前运算符进栈。4/20/202316例：画出形成表达式a*(b+c/d)的逆波兰表示过程a*(b+c/d)#步骤a(b+c/d)#*#步骤ab+c/d)#(*#步骤ab+c/d)#(*#步骤abc/d)#+(*#步骤abc/d)#+(*#步骤4/20/202317abcd)#/+(*#步骤abcd)#/+(*#步骤/+(*#abcd/)#步骤+(*#abcd/+)#步骤*#abcd/+*#步骤4/20/202318形成逆波兰表示的过程，实质上是表达式的翻译过程。（算法不难写出）例：a/b/c+d=ab/c/d+(a+b)*(c-d/e)=ab+cde/-*4/20/202319n数组数组POST存放后缀式：存放后缀式：k为下标，初值为为下标，初值为1n上述语义动作可实现为：上述语义动作可实现为：产生式产生式程序段程序段EE(1)op E(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1n例：输入串例：输入串a+b+c的分析和翻译的分析和翻译POST：1 2 3 4 5EE(1)op E(2)E.code:=E(1).code|E(2).code|opE(E(1)E.code:=E(1).codeEidE.code:=idab+c+4/20/2023207.1.2 图表示法图表示法n图表示法图表示法DAG抽象语法树抽象语法树 4/20/2023217.1.2 图表示法图表示法n无循环有向图无循环有向图(Directed Acyclic Graph，简称简称DAG)对表达式中的每个子表达式，对表达式中的每个子表达式，DAG中都有一个中都有一个结点结点一个一个内部结点内部结点代表一个代表一个操作符操作符，它的孩子代表，它的孩子代表操作数操作数在一个在一个DAG中代表公共子表达式的结点具有多中代表公共子表达式的结点具有多个父结点个父结点4/20/202322 a:=b*(-c)+b*(-c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc4/20/202323抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象语法树抽象语法树*buminusc4/20/202324DAG对应的代码：对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树抽象语法树对应的代码：对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T54/20/202325 产生赋值语句抽象语法树的属性文法产生赋值语句抽象语法树的属性文法 产产 生生 式式语义规则语义规则Sid:=ES.nptr:=mknode(assign,mkleaf(id,id.place),E.nptr)EE1+E2E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(*,E1.nptr,E2.nptr)E-E1 E.nptr:=mknode(uminus,E1.nptr)E(E1)E.nptr:=E1.nptrEid E.nptr:=mkleaf(id,id.place)4/20/2023267.1.3 三地址代码三地址代码 n三地址代码三地址代码x:=y op z n三地址代码可以看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的一种线性表示的一种线性表示 4/20/202327 a:=b*(-c)+b*(-c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc4/20/202328 T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5对于抽象语法树的代码对于抽象语法树的代码对于对于DAG的代码的代码4/20/202329三地址语句的种类三地址语句的种类 nx:=y op z nx:=op y nx:=y ngoto L nif x relop y goto L或或if a goto Lnparam x和和call p,n，以及返回语句，以及返回语句return ynx:=yi及及xi:=y的索引赋值的索引赋值nx:=&y,x:=*y和和*x:=y的地址和指针赋值的地址和指针赋值4/20/202330n生成三地址代码时，临时变量的名字对应生成三地址代码时，临时变量的名字对应抽象语法树的内部结点抽象语法树的内部结点nid:=E对表达式对表达式E求值并置于变量求值并置于变量T中值中值id.place:=T4/20/202331从赋值语句生成三地址代码的从赋值语句生成三地址代码的S-属性文法属性文法n非终结符号非终结符号S有综合属性有综合属性S.code，它代表赋，它代表赋值语句值语句S的三地址代码。的三地址代码。n非终结符号非终结符号E有如下两个属性：有如下两个属性：E.place表示存放表示存放E值的名字。值的名字。E.code表示对表示对E求值的三地址语句序列。求值的三地址语句序列。函函数数newtemp的的功功能能是是，每每次次调调用用它它时时，将将返返回一个不同临时变量名字回一个不同临时变量名字,如如T1,T2,。4/20/202332为赋值语句生成三地址代码的为赋值语句生成三地址代码的S-属性文法定义属性文法定义 产生式产生式语义规则语义规则Sid:=ES.code:=E.code|gen(id.place:=E.place)EE1+E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place+E2.place)EE1*E2E.place:=newtemp;E.code:=E1.code|E2.code|gen(E.place:=E1.place*E2.place)E-E1E.place:=newtemp;E.code:=E1.code|gen(E.place:=uminus E1.place)E(E1)E.place:=E1.place;E.code:=E1.codeEid E.place:=id.place;E.code=4/20/202333三地址语句三地址语句n四元式四元式一个带有四个域的记录结构，这四个域分别一个带有四个域的记录结构，这四个域分别称为称为op,arg1,arg2及及resultoparg1arg2result(0)uminuscT1(1)*bT1T2(2)uminuscT3(3)*bT3T4(4)+T2T4T5(5):=T5a 4/20/202334三地址语句三地址语句n三元式三元式 通过计算临时变量值的语句的位置来引用这通过计算临时变量值的语句的位置来引用这个临时变量个临时变量三个域：三个域：op、arg1和和arg2oparg1arg2(0)uminusc(1)*b(0)(2)uminusc(3)*b(2)(4)+(1)(3)(5)assigna(4)4/20/202335三地址语句三地址语句nxi:=y op arg1 arg2(0)=x i (1)ynx:=yiop arg1 arg2(0)=y i(1)assign x (0)4/20/202336三地址语句三地址语句n间接三元式间接三元式 为为了了便便于于优优化化，用用 三三元元式式表表+间间接接码码表表 表表示示中间代码中间代码间间接接码码表表:一一张张指指示示器器表表，按按运运算算的的先先后后次次序列出有关三元式在三元式表中的位置。序列出有关三元式在三元式表中的位置。优点优点:方便优化，节省空间方便优化，节省空间4/20/202337n例如，语句例如，语句X:=(A+B)*C;Y:=D(A+B)的间接三元式表示如下表所示。的间接三元式表示如下表所示。4/20/202338例：a=A+(-B)*C 的三元式：(1)(,B,-)(2)(*,(1),C)(3)(+,A,(2)4/20/202339