编译6语法制导翻译技术和中间代码生成解析

1、编译原理编译原理(第三版第三版) 陈火旺等编著22022-4-19 主主 要要 内内 容容 属性文法。属性文法。 语法制导翻译法的思想语法制导翻译法的思想 常见中间代码：逆波兰表示、四元式表示常见中间代码：逆波兰表示、四元式表示和三地址代码、三元式和树形表示和三地址代码、三元式和树形表示 各种不同语法结构的语法制导翻译技术各种不同语法结构的语法制导翻译技术语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成32022-4-196.1 概述概述一、语义分析的任务一、语义分析的任务1.审查每一个语法结构的静态语义，即验证语法正确的结构是否有意义。如：赋值语句：x=x+y,左边变量类型与右边

2、变量类型是否一致。2.在语义正确的基础上生成一种中间代码或目标代码。42022-4-19二、语义分析的范围二、语义分析的范围1.确定类型：确定标识符所关联的数据类型。2.类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。3.识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义，并作相应的语义处理（生成中间代码或目标代码）4.控制流检查：控制流语句必须转移到合法的地方。如：C中，break语句规定跳出最内层的循环或switch语句.52022-4-195.一致性检查：在很多场合要求对象只能被说明一次(避免重复定义)。6.相关名字检

3、查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。62022-4-19三、语义描述工具和语义分析方法三、语义描述工具和语义分析方法1.语义描述工具 目前流行：用属性文法属性文法作为描述语义的工具。2.语义分析方法根据描述属性文法的语义规则的方式不同，语义分析方法分为：语法制导定义方法翻译方案72022-4-196.2 属属 性性 文文 法法一、属性一、属性属性常用来描述事物或人的特征。如：人的姓名，性别等，商品的颜色、重量、单位等。n属性属性：在编译中，对文法的每一个符号，引进一些属性，用这些属性描述文法符号相关的信息，如：类型、

4、值或存储位置等。如：AX ，在语法推导或归约时，有时结合X的类型，位置，值，考虑语法分析的正确性，即语法分析中有语义检查。如:X的属性：Xtype，Xplace，Xval分别表示X的类型，位置，值等语义。82022-4-19n属性值：可以在语法分析过程中计算和传递。n属性的加工过程就是语义的处理过程。二、属性文法二、属性文法1.语义规则语义规则在对文法符号属性处理过程中，必须遵守一定义的规则语义规则。为文法的每一产生式定义一组属性的计算规则，称为语义规则语义规则。2.属性文法属性文法形式定义：一个属性文法是一个三元组A，A=(G,V,F)其中：G为一个上下文无关文法； V 表示属性的有穷集合；

5、 F表示属性的断言或谓词的有穷集。92022-4-19n在属性文法中：每个属性与文法中某个符号相关联，用“符号属性”表示。如：Xtype, Xint, Xbool等。每个断言与文法的某产生式相关联。 断言就是产生式上定义的一组语义规则。例：一个简单表达式方法：EN1+N2 | N1orN2Nnum|true|false102022-4-19n根据程序语言中有关类型的检验原则，可以得到关于类型检验的属性文法：1.EN1+N2 N1.type=int and N2.type=int2.EN1orN2 N1.type=bool and N2.type=bool3.Nnum N.type=int4.N

6、true N.type=bool5.Nfalse N.type=bool112022-4-19n属性分类：综合属性 继承属性综合属性：从语法分析角度看，如果一个结点的某一属性，其值由子结点的属性的值来计算，称该属性为综合属性。继承属性：在语法分析树中，结点的某个属性值由该结点的兄弟结点和（或）父结点的属性值来计算，此结点的属性称为继承属性。继承属性用于“自上而下”传递信息、 综合属性用于“自下而上”传递信息。122022-4-19n注意：注意：终结符号只有综合属性，他由词法分析器提供。非终结符号既有综合属性，也可有继承属性。文法识别符号（开始符号）的所有继承属性作为属性计算前的初始值。根据处理

7、不同的要求，属性和断言可以多种形式出现，如：语义规则或者程序段等。132022-4-19【例6.1】简单表达式求值的属性文法。 产生式语义规则1.LEprint(E.val)2.EE1+TE.val=E1.val+T.val3.ETE.val=T.val4.TT1*FE.val=T1.val*F.val5.TFT.val=F.val6.F(E)F.val=E.val7.FdigitF.val= digit.lexval142022-4-19【例6.2】描述说明语句中简单变量类型信息的属性文法产生式产生式语义规则语义规则1.DTLL.in=T.type2.TintT.type =integer3

8、.TrealT.type =real 4.LL1，id L1.in=L.inaddtype(id.entry,L.in)5.Lidaddtype(id.entry,L.in)152022-4-19文法定义了一种说明语句，该说明语句的形式是由关键字int或real开头，后跟一个标识符表，每一个标识符间用逗号隔开：real id1，id2，idn 或 int id1，id2，idn属性文法中，非终结符T有综合属性type，其值由关键字int和real决定。n语义规则L.in=T.type将L的属性值置为该说明语句指定的类型。 L.in将被沿着语法树传递到下边的结点使用，与L产生式相联的规则里使用了

9、它。如：句子int id1，id2语法树： D T L L int , id2 id1 162022-4-19一、基本思想对文法中的每个产生式都附加上一个语义动作或语义子程序，伴随着语法分析，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作（包括：查填表格，改变变量的求值，打印信息和生成中间代码等），从而完成预定的翻译工作。即在语法翻译过程中伴随部分语义的检查工作。6.3 语法制导翻译概述语法制导翻译概述172022-4-19n语法制导翻译方法：自底向上的语法制导翻译方法自顶向下的语法制导翻译方法二、语法制导翻译的步骤1、为所给文法每个产生式设计相应的语义规则。例：为一个简单表达

10、式计值的文法：EE+E|E*E|(E)|digit设计简单计算的语义规则如下：1. EE(1)+E(2)Eval=E(1)val + E(2)val 2. EE(1)*E(2)Eval=E(1)val * E(2)val 3. E(E(1)Eval=E(1)val4. EdigitEval=lexdigit为文法产生式写语义规则或语义子程序为文法产生式写语义规则或语义子程序是难点.182022-4-192.采用LR分析方法，则构造LR分析表状态ACTIONGOTO+digit*()#E0S3S211S4S5acc2S3S263r4r4r4r44S3S275S3S286S4S5S97r1S5r1

11、r18r2r2r2r29r3r3r3r3192022-4-193. 将原LR语法分析栈扩充，增加语义值栈。4. 根据语义分析栈的工作过程设计总控程序，使语法分析与语义分析工作同时完成。例例：计算表达式7+8*5的语法树，以及用LR语法制导翻译法得到该表达式的计值过程：SnxnxnvalS1x1S0#x1val状态栈文法符号栈语义值栈202022-4-19步骤状态栈语义栈符号栈输入符号栈主要动作10_#7+8*5#S3203_#7+8*5#r4301_7#E+8*5#S44014_7_#E+8*5#S350143_7_#E+8*5#r460147_7_8#E+E*5#S5701475_7_8#E

12、+E*5#S38014753_7_8_#E+E*5#r49014758_7_8_5#E+E*E#r2100147_7_40#E+E#r11101_47#E#acc 7 + Eval=47 Eval=7 Eval=40 + Eval=8 Eval=5 8 5 注：自底向上语法制导翻译的特点：当栈顶形成句柄执当栈顶形成句柄执行归约时，调用相行归约时，调用相应的语义动作应的语义动作。语法分析与语义分语法分析与语义分析同步操作。析同步操作。*212022-4-191 中间语言n中间语言：它介于源程序到目标语言程序中间程序的语言n中间语言程序：用中间语言表示的程序。n作用：用于编译程序，将源程序翻译成等

13、价的中间语言程序，再将中间语言程序转化成目标程序（即将语义分析和目标代码生成分开处理）n源程序 中间语言程序目标程序n中间语言是表示语法制导翻译的结果。等价变换转化6.4 6.4 中中 间间 语语 言言222022-4-19好处：n中间语言与机器无关，使采用中间语言进行翻译的编译程序系统易于移植。n易于优化翻译后的代码。n使编译程序的结构在逻辑上更简单明确。2 中间语言的表示常见：逆波兰表示 四元式表示和三地址代码 三元式和树形表示232022-4-196.4.1 逆波兰表示逆波兰表示 由波兰逻辑学家J.Lukasiewicz(卢卡西维兹)首先提出用来表示表达式的方法，后来推广到表示程序设计语

14、言中的其它语法成分。1.表达式的逆波兰表示表达式的逆波兰表示表达式的表示：n中缀表示：运算符居中，运算对象在左右两边:a+bn波兰表示：前缀表示：运算符在前，运算对象在后：+ab后缀表示：运算对象在前，运算符在后：ab+(逆波兰表示)242022-4-19n例：逆波兰表示的例子中缀表示(一般表示)逆波兰表示a+b*cabc*+a*(b+c/d)abcd/+*a*b+cab*c+a*b+(c-d)/eab*cd-e/+252022-4-19(1)表达式逆波兰表示的定义： 设E是一般表达式，则： 一般表达式一般表达式逆波兰表达式逆波兰表达式n若E为变量或常量En（E）E的逆波兰式nE(1)opE(

15、2)(二目运算)E(1)的逆波兰式E(2)的逆波兰式opnopE(单目运算)E的逆波兰式op262022-4-19 在编译过程中，生成逆波兰表示的语义规则描述： 产生式 语义规则 EE(1)opE(2) E.code=E(1).code|E(2) .code|op E(E(1) ) E.code=E(1) .code Ei E.code= i 其中：E.code表示E的逆波兰式；|表示逆波兰式的连接。272022-4-19 (2)逆波兰表示的特点a.标识符(运算对象)出现的顺序（从左到右）和原有顺序相同。b. 运算符是按实际计算顺序（从左到右）出现的。c. 运算符紧跟在运算对象的后面出现，并且

16、没有括号。282022-4-19(3) 好处：易于对表达式的计算处理n对于一般表达式的计算，系统需要用两个工作栈分别处理运算对象和运算符。n对于逆波兰表示的表达式计算处理只用一个工作栈。例：逆波兰式ab+c*的计算处理过程遇运算对象a,b入栈扫描ab+c*ba栈遇运算符+取出a,b，运算结果T入栈TcTc*遇运算对象c入栈取出c,T作运算，设结果T1T1遇运算符*292022-4-192. 形成逆波兰表示怎样将一般表达式转换成逆波兰表示？基本思想基本思想:从左到右扫描表达式，每遇到：1o 表达式中的运算对象则往左去。2o 表达式中的运算符，则与运算符栈顶元素比较优先数：302022-4-19逆

17、波兰表示表达式运算对象运算符进栈出栈运算符栈 如果运算符栈顶元素的优先数大于或等于表达式中当前的运算符优先数，则栈顶元素退栈向左去。然后当前运算符继续与栈顶的新元素比较优先数。直到栈顶元素的优先数小于表达式中当前运算符为止。此时，才将表达式中当前运算符进栈。312022-4-19例：画出形成表达式a*(b+c/d)的逆波兰表示过程a*(b+c/d)#步骤a(b+c/d)#*#步骤ab+c/d)#(*#步骤ab+c/d)#(*#步骤abc/d)#+(*#步骤abc/d)#+(*#步骤322022-4-19abcd)#/+(*#步骤abcd)#/+(*#步骤/+(*#abcd/)#步骤+(*#ab

18、cd/+)#步骤 *#abcd/+*#步骤332022-4-19形成逆波兰表示的过程，实质上是表达式的翻译过程。（算法不难写出）例：a/b/c+d = ab/c/d+(a+b)*(c-d/e) = ab+cde/-*342022-4-196.4.2 三元式和树形表示三元式和树形表示1. 三元式一个三元式由三个主要部分和一个序号组成：(i)(op,arg1,arg2)其中：op是运算符，arg1和arg2是运算对象。当op为一目运算符时，只有一个运算对象。(i)表示三元式的序号，三元式的运算结果由每个三元式前序号(i)指示。序号(i)指向三元式所处的表格位置，因此引用一个三元式的计算结果是通过引

19、用该三元式的序号实现的。三元式出现的先后顺序与表达式的计值顺序一致。352022-4-19例：a=A+(-B)*C 的三元式：(1)(,B,-)(2)(*,(1),C)(3)(+,A,(2)362022-4-192. 间接三元式由于三元式的先后顺序决定了值的顺序，因此在产生三元式形式的中间代码后，对其进行代码的优化时难免涉及到改变三元式的顺序,这就要修改三元式表。为了最少改动三元式表，可以另设一张间接码表来表示有关三元式在三元式表的计值顺序，用这种办法处理的中间代码称为间接三元式。例：表达式x=A+B*Cy=D-B*C372022-4-19其间接三元式表示如下：三元式表间接码表(1)(*,B,

20、C)(1)(2)(+,A,)(1)(2)(3)(=,x,(2)(3)(4)(-,D,(1)(1)(5)(=,y,(4)(4)(5)由于间接码表的作用，编译程序每产生一个三元式时，先查看三元式表中是否存在当前三元式，若存在就不需要重复填写三元式表，如上例中的三元式(1) (*,B,C)在间接码表中出现了两次，但三元式表中实际只有一个三元式。注：间接三元式表示的中间代码有利于中间代码的优化。382022-4-193.树形表示树形表示n树形结构是三元式的另一种表示形式例如：a=-b*c+b*d的树形表示(由三元式的下至上画出) = + a b * * c - d b 392022-4-19v一个表达

21、式中简单变量或常数的树形表示就是它们的本身。v如果表达式e1和e2的树分别为T1和T2,则： e1+e2, e1* e2, -e1 的树分别： + T2 T1 e1+e2 * T2 T1 e1*e2 - T1 -e1 树形表示法很容易表示一个表达式或语句。402022-4-19注注：二目运算对应二叉树三目运算对应三叉树： 如条件语句if u then S1 else S2 可看作三目运算。 其三目运算符定义为:if then else 则树表示： S2 u S1 注：多叉树不便于存储，可以化为二叉树： S1 S2 u new 412022-4-19四、四元式和三地址代码四、四元式和三地址代码四

22、元式是一种比较普遍采用的中间代码形式。n四元式由四个部分组成：(i) (op, arg1, arg2, result)其中：op为运算符;arg1,arg2为运算对象。result存放结果的变量。四元式之间的联系通过变量来联系(而不是三元式中的序号联系)例：a=b*c+b/d 的四元式表示：(1) (*, b, c, t1)(2) (/, b, d, t2)(3) (+, t1, t2, t3)(4) (=, t3, _, a)422022-4-19注：四元式和三元式的主要不同在于：四元式之间的联系通过中间引用的变量名实现，而三元式之间的联系通过三元式序号实现。 这说明要更改一张三元式表比较困难，它需要改变一系列的三元式的序号。四元式表的修改比较方便，调整四元式之间位置，不改变其中的参数。 因此：四元式和三地址代码表示的中间代码便于中间代码的优化。而三元式和树不便于优化。432022-4-19有时将四元式表示成更直观的形式：三地址代码v三地址代码形式：x = a op b (赋值形式)与赋值语句的区别：其右边最多只能有一个运算符。 例：上例的四元式写成三地址代码：(1) t1=b*c(2) t2=b/d (3) t3= t1+ t2(4) a= t3n三地址代码表示的好处：表示中间代码更直观，有利于中间代码的优化