编译原理-第五章 语法制导翻译

编译原理CompilerPrinciples徐小龙[e-mail]南京邮电大学.计算机学院第五章语法制导翻译comPilingrunningProgramming教材：《编译技术原理及其实现方法》王汝传编著第五章语法制导翻译本章内容§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现§5.2中间语言一、简介二、逆波兰表示三、三元式四、树形表示五、四元式§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句的翻译二、布尔表达式的翻译三、控制语句翻译§5.1语法制导翻译概述一、语法制导翻译定义1、问题的引入一个程序成功地通过词法分析和语法分析，只能说明它是一个合适程序，但是对程序内部的逻辑含义并未加以考虑，从整个编译程序来看,词法分析和语法分析仅仅是编译程序一部分,编译程序最终的目的是将源程序翻译成可供计算机直接执行的目标程序。某些编译程序是直接生成机器语言或汇编语言形式的目标代码，而有些则并非如此。语法制导翻译方法先将源程序单词序列翻译成中间语言，然后再将中间语言翻译成目标程序。§5.1语法制导翻译概述一、语法制导翻译定义2、定义语法制导翻译就是以语法分析为主导的语义处理。在语法分析过程中嵌入语义动作，即调用对应的语义子程序。E+EE*EEabc例如在前面语法分析时分析a+b*c表达式。语法分析是将a归约E，再将b归约E，将c归约为E，然后再将E*E归约成E，再将E+E归约成E，所以a+b*c是一个合法的句子。如果考虑语义，在归约过程中加上语义动作，先将a归约为E，将a值赋给E后，b归约成E，同时将b值赋给E，在将c值赋给E，然后再将b*c（E*E）给右E，再将a给E，最后再将两个E值相加就是最终结果。这就是语法制导翻译的基本思想，在语法分析同时进行语义分析。§5.1语法制导翻译概述二、语法制导翻译原理1、语法制导翻译的原理语法制导翻译的原理就是先为每个文法规确定相应的语义，即编写出相应语义处理子程序，整个分析是以语法分析为主导。在自顶向下语法分析时，若某一个规则右部与输入串相匹配时，或者，在自底向上语法分析时，当一个规则被用于进行归约时，此时该规则对应的语义子程序就进入工作，完成既定翻译任务，产生与语义相应的中间代码或目标代码。§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作语义动作：给每个文法符号X赋以各种不同的语义值这里的语义值不一定指具体数值，可以是“类型”、“种属”、“地址”或“代码”等，我们用记号X·TYPE、X·CAT或X·VAL来表示这些值。如果某规则的右部有同一符号若干个出现，那么我们就用上角标来区别这些符号§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：假定有如下规则和语义动作：E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}语义动作写在规则之后的花括号里，这里语义动作是表明与规则左部文法符号E相关的语义值E·VAL，它是通过把规则右部文法符号的语义值E(1)·VAL和E(2)·VAL加在一起来决定的，规则中终结符号“+”按语义规则被解释成通常“加”的意思。各规则的语义动作可以对表达式计算，也可以生成中间代码，甚至还可以来产生目标指令。§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digitdigit代表0和9之间任一数字，如果仅是为了求值，则语义动作：(1)E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=digit{E·VAL:=digit}假定语义动作中的“+”代表是整型加算术运算。规则(1)的语义动作为:E的语义值E·VAL等于E(1)和E(2)的语义值E(1)·VAL和E(2)·VAL之“和.规则(2)的语义动作为:E的语义值为0～9之间任一个数.这样，按照它们的语义动作，我们在分析每个句子的同时一步一步地算出每个句子的值.§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digit如果采用自底向上归约过程。首先考虑底层最左E的结点，这个结点对应于规则E∷=1和语义动作E·VAL:=1。这样，在底层最左的E处值1与语义值E·VAL相关。E+EE+EE123输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digit输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：在图所示子树中，子树根处E·VAL的语义值是3，这可用语义动作E·VAL:=E(1)·VAL+E(2)·VAL算出。使用这个语义动作时，以底部最左的E的E·VAL的值来代替E(1)·VAL，而以右边E的E·VAL的值代替E(2)·VAL。E+EE•VAL=1E12E•VAL=2类似地，值2与该结点的右兄弟的语义值E·VAL相关。如下图所示§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digit输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：E+E•VAL=6EE•VAL=3EE•VAL=3+EE•VAL=1EE•VAL=2123以这种方法继续下去，我们就推出如图所示整个语法树每个结点的语义值。§5.1语法制导翻译概述三、语法制导翻译实现2、语义动作上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上LR分析看如何实现语法制导翻译。例如有规则：(1)X∷=…{动作1}(2)Y∷=…{动作2}(3)A∷=XY{动作3}当使用规则(1)、(2)归约时，{动作1}和{动作2}的工作结果有关信息(作为X和Y的语义值)应暂时保存下来，以便以后用规则(3)在归约时(动作3)可引用这些值。§5.1语法制导翻译概述三、语法制导翻译实现2、语义动作现在对LR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈，为了清晰起见，我们把这个分析栈每一项分三部分组成：状态STATE、文法符号SYM和语义值VAL。SmY•VALYSm-1X•VALXS0－#………TOPSTATEVALSYM§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：考虑下面文法及其语义描述：规则(0)S’∷=E{printE·VAL}(1)E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=E(1)*E(2){E·VAL:=E(1)·VAL*E(2)·VAL}(3)E∷=(E(1)){E·VAL=E(1)·VAL}(4)E∷=i{E·VAL:=LEXVAL}其中：语义动作中的+、*代表整型加、乘算术运算，而且词法分析程序将送来每个i的整型内部值LEXVAL。假定语义动作是紧接在归约之后执行的。§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：上面所列的语义动作就相当于下面所列的程序段：规则(0)S’∷=E{printVAL［TOP］}(1)E∷=E(1)+E(2){VAL[TOP]：=VAL[TOP]+VAL[TOP+2]}(2)E∷=E(1)*E(2){VAL[TOP]：=VAL[TOP]*VAL[TOP+2]}(3)E∷=(E(1)){VAL［TOP］:=VAL［TOP+1］}(4)E∷=i{VAL［TOP］:=LEXVAL}由于有一个“+“号，所以为TOP+2由于有一个“（“号，所以为TOP+1由于有一个“*“号，所以为TOP+2§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：根据上述程序段，若输入2*3+2，就有如图所示的语法制导翻译的分析树。S’EEEEE+*223E•VAL=8E•VAL=6E•VAL=4E•VAL=2E•VAL=3LEXVAL=2LEXVAL=3LEXVAL=2§5.1语法制导翻译概述对2*3+2进行分析和翻译(实为计算值)该输入串过程如下表所示。当状态1面临#时对应的分析动作为acc(接受)，此时，相应的语义动作为printVAL[TOP]，即输出语义程序的计值结果：8。步骤状态栈语义值栈符号栈输入串归约规则及动作10－＃2*3+2＃S3203－－＃2*3+2＃r4301－2＃E*3+2＃GOTO[0,E]=1,S54015－2－＃E*3+2＃S350153－2－－＃E*3+2＃r460158－2－3＃E*E+2＃GOTO[5,E]=8,r2701－（6）＃E+2＃GOTO[0,E]=1,S48014－（6）－＃E+2＃S390143－（6）－－＃E+2＃r4100147－（6）－2＃E+E＃GOTO[4,E]=7,r11101－（8）＃E＃acc第五章语法制导翻译本章内容§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现§5.2中间语言一、简介二、逆波兰表示三、三元式四、树形表示五、四元式§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句的翻译二、布尔表达式的翻译三、控制语句翻译§5.2中间语言一、简介1、什么是中间语言就是和源程序等价的一种编码形式，其复杂性介于源程序和机器语言中间。源程序前端中间代码代码优化器中间代码代码生成器目标程序符号表§5.2中间语言一、简介2、为什么要引入中间语言（1）为了使编译程序结构上逻辑简单明确（2）为了便于目标代码优化工作（3）便于目标代码生成§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（1）波兰表示的概念对于一个算术表达式A+B或逻辑表达式A≥B，根据运算符和运算对象的位置关系，可分为三种等价表示形式：1)中缀表示法运算符在运算对象中间，如：A+B，A≥B，a+b*(c+d*(e-f))等.2)后缀表示法将运算符放在运算对象后面，通常将后缀表示称为逆波兰表示.如：A+B表示为AB+，A≥B表示为AB≥，a+b*c表示为abc*+对于逆波兰表示非常适合机械处理，只要从左到右按运算顺序计算3)前缀表示法即将运算符放在运算对象前面。如:+AB，≥AB，§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（1）波兰表示的概念举例：表达式中缀表示和后缀表示中缀表示后缀表示a+b*ca*(b+c/d)a*b+(c-d)/ca+b=3∨d∧c(a+b)*(c-d)aba∨bcabc*+abcd/+*ab*cd-c/+ab+3=dc∧∨ab+cd-*ababc∨§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（1）波兰表示的概念说明以后将主要讨论逆波兰表示，即后缀表示,因前缀表示并不常用，所以有时也将后缀表示笼统地统称为波兰表示.(1)(2)在后缀表示中，运算符是按实际计算顺序从左到右排列，且每一运算符总是跟在它的运算对象之后。§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（2）逆波兰(后缀)表示的优点1）后缀表示是无括号表示法，简明，且确切规定了计算顺序。2）运算处理极其简单方便，只要从左到右扫描后缀表达式各个符号,就能进行对表达式处理一般步骤是从左到右扫描后缀表达式各个符号，每碰到运算对象时就把它推进栈，每碰到一个K元运算符时，就取出栈顶的K个运算对象进行相应的运算，并且用运算结果去替换栈顶的K个运算对象，然后再继续扫描表达式中余留符号,如此等等，直到整个表达式计算完毕为止。当上述过程结束后，整个表达式之值将留于栈顶。3)十分方便容易生成目标指令§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示下面通过求后缀表达式ab+c*的值，来说明用后缀表式对表达式处理的过程，设a，b和c分别为1，3和5，为了求13+5*的值，其计算1)把12)把33)将栈顶两个元素1和3相加，使它们退出栈，把结果4存入栈。4)把55)将栈顶两个元素4和5相乘，使它们退出栈，将结果20存入栈。结束时栈顶的值(这里是20)是整个表达式值。§5.2中间语言二、逆波兰表示1、表达式的逆波