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

编译原理第五章语法制导翻译第1页，共96页，2023年，2月20日，星期四第五章语法制导翻译本章内容§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现§5.2中间语言一、简介二、逆波兰表示三、三元式四、树形表示五、四元式§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句的翻译二、布尔表达式的翻译三、控制语句翻译第2页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述

一、语法制导翻译定义1、问题的引入一个程序成功地通过词法分析和语法分析，只能说明它是一个合适程序，但是对程序内部的逻辑含义并未加以考虑，从整个编译程序来看,词法分析和语法分析仅仅是编译程序一部分,编译程序最终的目的是将源程序翻译成可供计算机直接执行的目标程序。某些编译程序是直接生成机器语言或汇编语言形式的目标代码，而有些则并非如此。语法制导翻译方法先将源程序单词序列翻译成中间语言，然后再将中间语言翻译成目标程序。第3页，共96页，2023年，2月20日，星期四§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值相加就是最终结果。这就是语法制导翻译的基本思想，在语法分析同时进行语义分析。第4页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述二、语法制导翻译原理1、语法制导翻译的原理语法制导翻译的原理就是先为每个文法规确定相应的语义，即编写出相应语义处理子程序，整个分析是以语法分析为主导。在自顶向下语法分析时，若某一个规则右部与输入串相匹配时，或者，在自底向上语法分析时，当一个规则被用于进行归约时，此时该规则对应的语义子程序就进入工作，完成既定翻译任务，产生与语义相应的中间代码或目标代码。第5页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作语义动作：给每个文法符号X赋以各种不同的语义值这里的语义值不一定指具体数值，可以是“类型”、“种属”、“地址”或“代码”等，我们用记号X·TYPE、X·CAT或X·VAL来表示这些值。如果某规则的右部有同一符号若干个出现，那么我们就用上角标来区别这些符号第6页，共96页，2023年，2月20日，星期四§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加在一起来决定的，规则中终结符号“+”按语义规则被解释成通常“加”的意思。各规则的语义动作可以对表达式计算，也可以生成中间代码，甚至还可以来产生目标指令。第7页，共96页，2023年，2月20日，星期四§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之间任一个数.这样，按照它们的语义动作，我们在分析每个句子的同时一步一步地算出每个句子的值.第8页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：

设有文法E∷=E+EE∷=digit如果采用自底向上归约过程。首先考虑底层最左E的结点，这个结点对应于规则E∷=1和语义动作E·VAL:=1。这样，在底层最左的E处值1与语义值E·VAL相关。E+EE+EE123输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：第9页，共96页，2023年，2月20日，星期四§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相关。如下图所示第10页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：

设有文法E∷=E+EE∷=digit输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：E+E•VAL=6EE•VAL=3EE•VAL=3+EE•VAL=1EE•VAL=2123以这种方法继续下去，我们就推出如图所示整个语法树每个结点的语义值。第11页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述三、语法制导翻译实现2、语义动作上面原则上讨论了语法制导翻译的原理，下面通过一个自底向上LR分析看如何实现语法制导翻译。例如有规则：

(1)X∷=…{动作1}(2)Y∷=…{动作2}(3)A∷=XY{动作3}当使用规则(1)、(2)归约时，{动作1}和{动作2}的工作结果有关信息(作为X和Y的语义值)应暂时保存下来，以便以后用规则(3)在归约时(动作3)可引用这些值。第12页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述三、语法制导翻译实现2、语义动作现在对LR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈，为了清晰起见，我们把这个分析栈每一项分三部分组成：状态STATE、文法符号SYM和语义值VAL。SmY•VALYSm-1X•VALXS0－#………TOPSTATEVALSYM第13页，共96页，2023年，2月20日，星期四§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。假定语义动作是紧接在归约之后执行的。第14页，共96页，2023年，2月20日，星期四§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第15页，共96页，2023年，2月20日，星期四§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：根据上述程序段，若输入2*3+2，就有如图所示的语法制导翻译的分析树。S’EEEEE+*223E•VAL=8E•VAL=6E•VAL=4E•VAL=2E•VAL=3LEXVAL=2LEXVAL=3LEXVAL=2第16页，共96页，2023年，2月20日，星期四§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第17页，共96页，2023年，2月20日，星期四第五章语法制导翻译本章内容§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现§5.2中间语言一、简介二、逆波兰表示三、三元式四、树形表示五、四元式§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句的翻译二、布尔表达式的翻译三、控制语句翻译第18页，共96页，2023年，2月20日，星期四§5.2中间语言一、简介1、什么是中间语言就是和源程序等价的一种编码形式，其复杂性介于源程序和机器语言中间。源程序前端中间代码代码优化器中间代码代码生成器目标程序符号表第19页，共96页，2023年，2月20日，星期四§5.2中间语言一、简介2、为什么要引入中间语言（1）为了使编译程序结构上逻辑简单明确（2）为了便于目标代码优化工作（3）便于目标代码生成第20页，共96页，2023年，2月20日，星期四§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，第21页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（1）波兰表示的概念举例：表达式中缀表示和后缀表示中缀表示后缀表示a+b*ca*(b+c/d)a*b+(c-d)/ca+b=3∨d∧c(a+b)*(c-d)a<ba∨b<cabc*+abcd/+*ab*cd-c/+ab+3=dc∧∨ab+cd-*ab<abc<∨第22页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（1）波兰表示的概念说明以后将主要讨论逆波兰表示，即后缀表示,

因前缀表示并不常用，所以有时也将后缀表示笼统地统称为波兰表示.从上表中可以看出：(1)在中缀表示和后缀表示中，运算对象按相同次序出现。(2)在后缀表示中，运算符是按实际计算顺序从左到右排列，

且每一运算符总是跟在它的运算对象之后。第23页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（2）逆波兰(后缀)表示的优点1）后缀表示是无括号表示法，简明，且确切规定了计算顺序。2）运算处理极其简单方便，只要从左到右扫描后缀表达式各个符号,就能进行对表达式处理一般步骤是从左到右扫描后缀表达式各个符号，每碰到运算对象时就把它推进栈，每碰到一个K元运算符时，就取出栈顶的K个运算对象进行相应的运算，并且用运算结果去替换栈顶的K个运算对象，然后再继续扫描表达式中余留符号,如此等等，直到整个表达式计算完毕为止。当上述过程结束后，整个表达式之值将留于栈顶。3)十分方便容易生成目标指令第24页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示下面通过求后缀表达式ab+c*的值，来说明用后缀表式对表达式处理的过程，设a，b和c分别为1，3和5，为了求13+5*的值，其计算过程如下：1)把1推进栈。2)把3推进栈。3)将栈顶两个元素1和3相加，使它们退出栈，把结果4存入栈。4)把5推进栈。5)将栈顶两个元素4和5相乘，使它们退出栈，将结果20存入栈。结束时栈顶的值(这里是20)是整个表达式值。第25页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成对逆波兰(后缀)表示的形成，荷兰学者W.DEJKSTRA给出形象的解释。波兰表示运算对象表达式运算符进栈运算符栈退栈比栈顶高进栈，比栈顶低或相同的退栈第26页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：A运算对象A移进对象栈#+B*C#①第27页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：A＋>#，＋向下进运算符栈＋#B*C#②第28页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：AB运算对象B移进对象栈＋#*C#③第29页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：AB*>+，*向下进运算符栈*＋#C#④第30页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：ABC运算对象C移进对象栈*＋##⑤第31页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：ABC*#<*，*退栈往左＋##⑥第32页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示1、表达式的逆波兰表示（3）逆波兰(后缀)表示的形成图解形式来说明A+B*C形成的过程：ABC*＋#<＋，＋退栈往左##⑦第33页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示2、逆波兰表示的扩充只要遵守在运算对象后直接紧跟运算符这条规则，就可以简单地把这种后缀式扩充到比通常表达式更大范围，即扩充到程序语言的其它语法成分。第34页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示2、逆波兰表示的扩充（1）赋值语句

〈左部〉:=〈表达式〉

把赋值号“:=”看成是一个赋值运算符，它的后缀式为

〈左部〉〈表达式的后缀式〉：=

例如：x:=5x:=a*b-c/d

的后缀式分别为

x5:=xab*cd/-:=第35页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示2、逆波兰表示的扩充（1）赋值语句赋值语句的后缀式的处理方法和后缀式表达式处理方法类似。不同的是栈中保存的是左部变量的地址，而不是其值，在赋值运算处理结束后，不产生任何中间计算结果，因而也不存在保存中间计算结果的问题，而是把存放在运算栈中栈顶两项〈左部〉和〈表达式〉的值这两个量退掉。第36页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示2、逆波兰表示的扩充（1）条件语句

ifEthenS1elseS２对于用后缀式来表示条件语句，我们假定后缀式中各符号存放在一个一维数组POST［1··n］之中，每一个数组元素存放一个运算对象或运算符。同时约定如下几个符号：①JUMP表示无条件转；②JLT表示小于转；③JEZ表示零转。后缀式PJUMP表示无条件转移到下标P所指那个元素POST［p］(即从该符号开始继续执行)。

后缀式ePJEZ表示当后缀表达式e的值为零时，则转移至POST[P]。后缀式e1e2PJLT表示当后缀表达式e1小于后缀表达式e2时，

则转移至POST[P]第37页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示2、逆波兰表示的扩充（1）条件语句举例：对于形如ifethenS1elseS２的条件语句可按后缀式写成e’p1JEZS1’p2JUMPS2’我们约定e≠0时,该条件语句的值是S1,否则等于S2

。对于后缀式条件语句中:e’、S1’和S2’

分别是e、S1和S2的后缀式。此外,p1表示S2’

在数组POST的起始位置,p2表示S2’

之后那个符号位置。上述后缀式条件语句的意思是,若e′=0时,则转至POST[p1］对S2’

进行计算,否则计算S1′,然后转到POST［p1］的位置。第38页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示3、语法制导翻译生成后缀式例4.15文法G［E］如何按语法制导翻译方法把一个中缀形式的简单算术表达式翻译成为后缀式？

规则语义动作(1)E∷=E(1)+T{E·CODE:=E(1).CODE‖T.CODE‖+}(2)E∷=T{E·CODE:=T·CODE}(3)T∷=T(1)*F{T·CODE:=T(1)CODE‖F·CODE‖*}(4)T∷=F{T·CODE:=F·CODE}(5)F∷=(E){F·CODE:=E·CODE}(6)F∷=i{F·CODE:=i}几点说明:E.CODE,T.CODE,F.CODE表示构成后缀式的符号串符号“‖”表示两个串的“捻接”运算，即并置运算

.显然,E(1).CODE‖T.CODE‖+是E.CODE,因为符号在后,其它类似.第39页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示3、语法制导翻译生成后缀式如果我们设置一个数组存放后缀式，那么语义动作就可以不涉及捻接运算。令这个数组为POST，p为下标，初值为1。相应的语义子程序：

(1)E∷=E(1)+T{POST[p]:=‘+’;p:=p+1}(2)E∷=T{}(3)T∷=T(1)*F{POST[p]:=‘*’;p:=p+1}(4)T∷=F{}(5)F∷=(E){}(6)F∷=i{POST[p]:=i;p:=p+1}…E(1).CODET.CODE+POST(P)第40页，共96页，2023年，2月20日，星期四§5.2中间语言二、逆波兰表示3、语法制导翻译生成后缀式以表达式a+b*c为例按照P118.表4.15文法G［E］LR分析表给出语法制导翻译产生后缀式过程，其中SUBK表示第K个规则相对应的语义子程序。第41页，共96页，2023年，2月20日，星期四步骤状态栈符号栈输入串归约规则调用子程序后缀式10＃a+b*c#205＃a+b*c#F::=iSUB6a303＃F+b*c#T::=FSUB4a402＃T+b*c#E(1)::=TSUB2a501＃E(1)+b*c#a6016＃E(1)+b*c#a70165＃E(1)+b*c#F::=iSUB6ab80163＃E(1)+F*c#T(1)::=FSUB4ab90169＃E(1)+T(1)

*c#ab1001697＃E(1)+T(1)*c#ab11016975＃E(1)+T*c#F::=iSUB6abc12016970＃E(1)+T(1)*F#T::=T(1)*FSUB3abc*130169＃E(1)+T#E::=E(1)+TSUB1abc*+1401＃E#abc*+第42页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式1、三元式定义三元式的一般形式为(i)(OP,ARG1,ARG2)其中：(i)为三元式的编号，不同三元式不能有相同的编号

OP是运算符部分

ARG1和ARG2是运算对象部分，它们或者指向符号表登记项指示器(对于运算对象是常数或标识符的情况)，或者是一个指向三元式序列(或三元式表)中某一个三元式位置的指示器(对于运算对象是中间结果的情况)。

如：A+B*C对应的三元式表示为：（1）（*，B，C）（2）（+，A，（1））第43页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式1、三元式定义说明：运算符OP通常用一个整数码表示，它除了标识运算符的种属之外，还附带地表示其它一些语义特性。若OP表示一个加法运算符，则相应的整数码除了标识加法运算本身外，还兼有表示数据类型(如整型、实型等)、运算方式(定点、浮点)和运算精度等信息，且不同语义属性使用不同的运算符代码。

第44页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式1、三元式定义说明：对于一目运算符OP，ARG1和ARG2只需其一。我们可以随意规定选用一个，例如，规定用ARG1。至于多目运算符可以用若干个相继三元式表示如：赋值语句x:=-b*(c+d)用三元式来表示，则可写成(1)(-,b,)(2)(+,c,d)(3)(*,(1),(2))(4)(:=,x,(3))三元式(3)就引用三元式(1)和(2)的结果作为它的两个运算对象

三元式出现先后顺序和表达式各部分计算顺序相一致！第45页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式2、三元式的生成同样可以用语法制导翻译来产生三元式：(1)E∷=E(1)+T{E·VAL:=TRIP(+,E(1)·VAL,T·VAL)}(2)E∷=T{E·VAL:=T·VAL}(3)T∷=T(1)*F{T·VAL:=TRIP(*,T(1)·VAL,F·VAL)}(4)T∷=F{T·VAL:=F·VAL}(5)F∷=(E){F·VAL:=E·VAL}(6)F∷=i{F·VAL:=ENTRY(i)}其中语义值E·VAL、T·VAL和F·VAL，是一个指示器，或指向有关符号表某一项，或指向三元式表自身某一项TRTP(OP，ARG1，ARG2)是一个语义子程序，回送新产生的三元式存放在三元式表位置。ENTRY(i)是一个语义子程序，通过ENTRY查i在符号表中位置，即对应地址，若查不到，认为有错误。第46页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式3、间接三元式为了便于代码优化，常常采用间接三元式。这由两张表组成：（1）三元式表，用来存放各三元式本身；（2）执行表(间接码表)，它按执行三元式顺序，依次列出相应各三元式在三元式表中位置。第47页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式3、间接三元式例如，对于如下赋值语句x:=a*b+c+a*b若按三元式表示，可写成(1)(*,a,b)(2)(+,(1),c)(3)(*,a,b)(4)(+,(2),(3))(5)(:=,x,(4))其中，三元式(1)和(3)完全一样，但是不能将(3)省去。按间接三元式表示，则可写成执行表三元式表(1)(1)(*,a,b)(2)(2)(+,(1),c)(1)(3)(+,(2),(1))(3)(4)(:=,x,(3))(4)第48页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式3、间接三元式间接三元式的优点：（1）便于代码优化在进行代码优化时，常常要从中间代码删去一些运算，或者把某些运算移到另外位置上，若采用一般三元式，则由于三元式之间引用太多，很难做到这一点。（2）节省空间由于在间接三元式执行表中已经依次列出每次要执行的那个三元式，所以，若有若干个相同三元式，则仅须在三元式表中保存其中之一。如上面赋值语句右部表达式中有两个a*b子表达式，而三元式表中只出现一次(*,a,b)。第49页，共96页，2023年，2月20日，星期四§5.2中间语言三、三元式3、间接三元式补充说明：对于间接三元式表示，语义子程序应增添产生执行表的动作。在填写三元式表时，应首先看一下此三元式是否在其中，如已在其中，则无需填入。第50页，共96页，2023年，2月20日，星期四§5.2中间语言四、树形表示1、表示方法我们可以用树形数据结构来表示一个表达式或语句。在树表示中，叶子结点表示运算对象，即常量或变量，其它结点表示运算符，如表达式

a+b,a-b,-a的树表示分别定义为：+ab－ab－a第51页，共96页，2023年，2月20日，星期四§5.2中间语言四、树形表示1、表示方法双目运算对应二叉树，多目运算对应多叉树，单目运算对应单叉树。如表达式a*b-(c+d)/(e-f)的二叉树如下图：后序遍历上述二叉树便得到该表达式的逆波兰表示为ab*cd+ef-/-－*/ab+－cdef第52页，共96页，2023年，2月20日，星期四§5.2中间语言四、树形表示2、树表示生成对文G[E]翻译成树形表示语义动作描述如下：(1)E∷=E(1)+T{E·VAL:=NODE(+,E(1)·VAL,T·VAL)}(2)E∷=T{E·VAL:=T·VAL}(3)T∷=T(1)*F{T·VAL:=NODE(*,T(1)·VAL,F·VAL)}(4)T∷=F{T·VAL:=F·VAL}(5)F∷=(E){F·VAL:=E·VAL}(6)F∷=i{F·VAL:=LEAF(i)}其中：语义值E·VAL、T·VAL和F·VAL是一个指示器，指向树一个结点。

NODE(OP，LEFT，RIGHT)是一个函数子程序，

OP是一个二元运算符，LEFT，RIGHT为指示器，每调用此函数一次,就建立一个新结点，其标记为OP，

LEFT和RIGHT分别指向左右子树根结点指针，从NODE回送的值是一个指示器，指向这棵新树的根。

LEAF(i)是建立一个末端结点(叶结点)第53页，共96页，2023年，2月20日，星期四§5.2中间语言五、四元式表示1、定义四元式是一种用得比较多的一种中间语言代码形式，四元式一般形式：

(OP，ARG1，ARG2，RESULT)其中：OP是运算符，其含义与三元式中OP类似；

ARG1和ARG2是运算对象，

RESULT是运算结果第54页，共96页，2023年，2月20日，星期四§5.2中间语言五、四元式表示2、示例赋值语句a:=-b*(c+d)用四元式表示，则可写成：(1)(-,b,,T1)(2)(+,c,d,T2)(3)(*,T1,T2,T3)(4)(:=,T3,,a)

四元式之间联系是通过临时变量实现的，调整四元式之间相对位置并不意味着一定要改变一系列指示器值。因此，对中间代码进行优化处理时，四元式比三元式方便得多。第55页，共96页，2023年，2月20日，星期四第五章语法制导翻译本章内容§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现§5.2中间语言一、简介二、逆波兰表示三、三元式四、树形表示五、四元式§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句的翻译二、布尔表达式的翻译三、控制语句翻译第56页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译1、翻译成四元式（1）赋值语句的文法

1)A∷=V:=E5)T∷=F2)E∷=E(1)+T6)F∷=(E)3)E∷=T7)F∷=i4)T∷=T(1)*F8)V∷=i

为了实现到四元式的翻译，需要引进一系列语义变量和语义子程序。这里讨论仅含有简单变量的表达式和赋值语句到四元式的翻译。为简便起见，假定赋值语句中所含的全部变量是同一类型的整型变量，

在翻译过程中也不作语义检查。第57页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译1、翻译成四元式（2）语义子程序的描述(1)A∷=V:=E{GEN(:=,E·PLACE,,V·PLACE)}(2)E∷=E(1)+T{E·PLACE:=NEWTEMP;GEN(+,E(1)·PLACE,T·PLACE,E·PLACE)}(3)E∷=T{E·PLACE:=T·PLACE}(4)T∷=T(1)*F{T·PLACE:=NEWTEMP;GEN(*,T(1)·PLACE,F·PLACE,T·PLACE)}(5)T∷=F{T·PLACE:=F·PLACE}(6)F∷=(E){F·PLACE:=E·PLACE}(7)F∷=i{F·PLACE:=ENTRY(i)}(8)V∷=i{V·PLACE:=ENTRY(i)}第58页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译1、翻译成四元式（3）语义变量和语义子程序

①

NEWTEMP是一个函数，每次调用时，都定义一个新临时变量，回送一个代表新临时变量名的整数码作为函数值。为直观起见，我们将

NEWTEMP产生的临时变量依次记为T１，Ｔ２…等等。

②ENTRY(i)是一个函数过程，查找符号名i在表中的入口地址。

③

X·PLACE是和非终结符X相联系的语义变量，表示存放X值的变量名在符号表的入口或整数码(若此变量是一个临时变量)。如：F∷=i{F·PLACE:=ENTRY(i)}表示存放F值变量名i在符号表中的入口地址。即从变量F.PLACE值可知i在符号表中的位置。

④GEN(OP，ARG1，ARG2，RESULT)是一个语义过程，该过程把四元式(OP，ARG1，ARG2，RESULT)填入四元式表中。

第59页，共96页，2023年，2月20日，星期四（4）文法G[A]SLR(1)分析表状态ACTIONGOTOi+*():=#AVETF0S2131acc2r83S44S9S85675S106r3S11r3r37r5r5r5r58S9S812679r7r7r7r710S9S813711S9S81412S10S1513r2S11r2r214r4r4r4r415r6r6r6r6第60页，共96页，2023年，2月20日，星期四（5）对x:=a+b*c语法制导翻译产生四元式过程（以赋值语句x:=a+b*c为例）步骤状态栈符号栈PLACE输入串归约规则调用子程序四元式10＃－X:=a+b*c#SUB8202＃x－Vx:=a+b*c#V::=i303＃V－Vx:=a+b*c#4034＃V:=－Vx-a+b*c#50349＃V:=a－Vx-Fa+b*c#F::=iSUB760347＃V:=F－Vx-Fa+b*c#T::=FSUB570346＃V:=T－Vx-Ta+b*c#E::=TSUB380345＃V:=E－Vx-Ea+b*c#903450＃V:=E+－Vx-Ea-b*c#10034509＃V:=E+b－Vx-Ea-Fb*c#F::=iSUB711034507＃V:=E+F－Vx-Ea-Tb*c#T::=FSUB512034503＃V:=E+T－Vx-Ea-Tb*c#130345031＃V:=E+T*－Vx-Ea-Tb-c#1403450319＃V:=E+T*c－Vx-Ea-Tb-FC#F::=iSUB71503450314＃V:=E+T*F－Vx-Ea-T1#T::=T(1)*FSUB4(*,b,c,T1)16034503＃V:=E+T－Vx-T2#E::=E(1)+TSUB2(+,a,T1,T2)170345＃V:=E－Vx-T2#A::=V:=ESUB1(:=,T2,,x)1801＃A#第61页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译1、翻译成四元式分析表几点说明在分析表中Vx,Ea,Tb,Fc之类记号，表示与非终结符V,E,T,F相关联的V·PLACE,E.PLACE,T.PLACE,F.PLACE中存放着ENTRY(x),ENTRY(a),ENTRY(b),ENTRY(c)符号指针，指向符号表。在四元式中，如（*，b,c,T1)，*实际上是某种整数编码，反映运算符本身及其信息特征，如类型等。b,c实际上也是指示器，指示符号表入口；T1是临时变量，实际上也是整数码.第62页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译2、类型检查与类型转换(1)目的1)类型检查是编译程序语义检查不可缺少的一部分。类型检查就是对访问数据的操作和被访问数据的类型进行检查检查操作的合法性和数据类型的相容性。例如，在PASCAL语言中，若算术运算符的操作数为布尔量，或者赋给实型变量值是个指针，则编译程序报告“类型不相容”的诊断信息。2)允许类型混合，但在处理时要统一，所以必须进行类型转换。例如，加法运算“+”允许运算对象是整型数或实型数,如果一个运算对象是实型，另一个运算对象是整型，其运算结果的类型是实型，由于实型数和整型数的内部表示不相同，因此为了使整型数能参加实型数运算，必须事先将整型数转换成实型数。第63页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译2、类型检查与类型转换（2）类型检查类型检查可在生成中间代码时进行，也可在生成目标代码时进行，但最好是在生成中间代码时进行，因为语法和语义检查最好尽早进行，这样能尽早避免徒劳的工作。在上面对简单算术表达式和赋值语句翻译到四元式的讨论中，我们假定各个变量是同一类型整型变量，并且规定在四元式的op代码中，本身就会有类型信息。所以，在上例各语义子程序中，我们并未考虑有关类型方面语义处理。第64页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译2、类型检查与类型转换（3）类型转换方法为了简单起见，我们仅考虑整型和实型的情况。

①这种混合运算中，给每个非终结符的语义值增添类型信息X.MODEX·MODE的值或为r(实型)或为int(整型)。原来X的信息除X.PLACE，还有X.MODE。②对表达式的每一规则的语义子程序进行修改，增加关于类型信息的语义规则。③必要时应产生对运算量进行类型转换的四元式，

(itr,A,,T)

把整型变量A转换成实型变量，结果存在T中。此外，在书写语义子程序时，为阅读上的直观性，我们用+i,*i等表示整型运算符，用+r,*r等表示实型运算符。第65页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句翻译2、类型检查与类型转换这样,对于输入串为

X*2+A*(I+1)其中I为整型量,X、A为实型量,则产生四元式序列(itr,2,-,T1)(*r,X,T１,T２)(+i,I,1,T3)(itr,T3,-,T４)(*r,A,T4,T5)(+r,T2,T5,T6)第66页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译1、概述布尔表达式由布尔运算符∧(与)、∨(或)和﹁(非)等

作用于布尔量或关系表达式构成关系表达式的形式是E1ropE2,其中rop是关系运算符

(如<、<=、=、>、>=及<>)。而E1和E2是算术表达式。第67页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译1、概述(1)布尔表达式的用途在程序设计语言中，布尔表达式有两个基本用途:1）一个是求逻辑值，逻辑值的结果是真或假。

2）另一个用得最多的是在控制语句中用作条件表达式，例如，在if-then、if-then-else和while-do语句里表示控制条件第68页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译1、概述(2)布尔表达式的文法布尔表达式文法G［E］如下:E∷=E∧E|E∨E|﹁E|(E)|i|iropi

说明：1）布尔表达式的文法是一个二义文法例如：该文法的一个句子a∧b∨c

有两棵不同的语法树与之对应，所以该文法是一个二义文法。EEE∨EE∧abcEEE∧aEE∨bc第69页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译1、概述(2)布尔表达式的文法布尔表达式文法G［E］如下:E∷=E∧E|E∨E|﹁E|(E)|i|iropi

说明：2）规定布尔运算符的优先顺序是:﹁、∧、∨。并假定∧和∨为左结合。所有关系运算符优先级相同,且高于任何布尔运算符,低于算术运算符。3）iropi中i可认为是布尔表达式也可视为数值

（1为真true,0为假false)。4）iropi中rop是关系运算符。第70页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译1、概述(3)布尔表达式求值方法

1）把真和假数值化，使布尔表达式计算类似于算术表达式的计算，常用1表示真，0表示假，或者用非零整数表示真。如：1∨（﹁0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1第71页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译1、概述(3)布尔表达式求值方法

2）采取某种优化措施，有时不需要将一个布尔表达式从头算到尾，而只须计算它的一个子表达式，便能确定整个布尔表达式真和假。例如，对于A∨B，只要计算出A为真，则不管B值如何，A∨B之值一定为真。又如对A∧B，只要计算出A为假，则A∧B必然为假。

对于三种逻辑运算，可作如下等价的解释：

A∨B:ifAthentrueelseBA∧B:ifAthenBelsefalse

﹁A:ifAthenfalseelsetrue

用这种方式实现控制语句的布尔表达式尤其方便。对应上述两种计算方法，其布尔表达式有两种不同的翻译方法第72页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译2、布尔表达式的翻译方法(1)如同翻译算术表达式一样，用于求值例如，布尔表达式﹁a∧(b∨c=d)将被翻译成如下四元式：

1)(﹁,a,-,T1)2)(=,c,d,T2)3)(∨,b,T2,T3)4)(∧,T1,T3,T4)第73页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译2、布尔表达式的翻译方法(1)如同翻译算术表达式一样，用于求值仿照翻译算术表达式的方法，布尔表达式文法G［E］的规则用于求值的语义动作(1)E∷=E(1)∧E(2){E·PLACE:=NEWTEMP;

GEN(∧,E(1)·PLACE,E(2)·PLACE,E·PLACE)}(2)E∷=E(1)∨E(2){E·PLACE:=NEWTEMP;GEN(∨,E(1)·PLACE,E(2).PLACE,E·PLACE)}(3)E∷=﹁E(1){E·PLACE:=NEWTEMP；GEN（﹁

，E(1)·PLACE,,E·PLACE)}(4)E∷=（E(1)）

{E·PLACE:=E(1)·PLACE}(5)E∷=i{E·PLACE:=ENTRY（i）}(6)E∷=iropi{E·PLACE:=NEWTEMP;

GEN(rop,ENTRY(i(1)),ENTRY(i(2)),E.PLACE)}}第74页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译2、布尔表达式的翻译方法(2)作为条件控制的布尔表达式的翻译1)布尔表达式E作为条件控制的代码结构对于条件语句

ifEthenS1elseS2中的布尔表达式E，它的作用就是控制S1和S2的选择，我们赋于E代码两种出口，其一为“真出口”，另一个是“假出口”，它们分别指出当E值为true和false时，控制转向的目标(即某一四元式所在位置或序号)。E的代码S1的代码truefalseS2的代码第75页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译2、布尔表达式的翻译方法(2)作为条件控制的布尔表达式的翻译2)三种形式的四元式作为条件控制的布尔表达式E的翻译归纳起来有三种形式的四元式

(jnz,a1,,p)若a1为真时,则转向第p个四元式。

(jrop,a1,a2，p)若关系a1ropa2成立时,转向第p个四元式。

(j,,,p)无条件转向第p个四元式。除上述两种真转外，可用无条件表示假转第76页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译2、布尔表达式的翻译方法(2)作为条件控制的布尔表达式的翻译例如,对于条件语句

ifa∨b<cthenS1elseS2经翻译后，可得如下四元式序列：(1)(jnz,a,,5)(2)(j,,,3)(3)(j<,b,c,5)(4)(j,,,p+1)(5)(关于S1的四元式序列)(P)(j,,,q)(p+1)(关于S2的四元式序列)(q)

（1）a为真，a∨b<c就为真，转5执行（2）a为假，a∨b<c的值取决于b<c的值，所以转3执行（3）a为假，且b<c，则a∨b<c为真，转5执行（4）a为假，且b<c也是假，则a∨b<c为假，

执行S2语句，即应转p+1执行（p）执行完S1（对应四元式为（5））则应转到条件语句的下一条语句执行，所以无条件跳转到（q）执行。四元式(1)～(4)中显然含有多余的四元式，第77页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（1）回填

在自底向上的语法制导翻译过程中，在产生一个条件或无条件转移四元式时，它所要转移到的那个四元式尚未产生，故无法立即产生一个完全控制转移四元式。例如，对于上例，在产生第一个四元式时，因为语句S1的中间代码尚未产生，故此时只得产生一个空缺转移目标的四元式(jnz,a,,0)，且将此四元式的序号作为语义信息存起来，待开始翻译语句S1时，再将S1的第一个四元式序号(即5)填入这个不完全条件转移四元式中。这种事后再填转移目标叫做回填。第78页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（2）真链T和假链F

在翻译过程中，有时会存在着若干个转移四元式,如例中的1和3两个四元式，它们有同一个转移目标5，但此目标的具体位置在形成四元式时还不知道，此时，我们将这些四元式链接起来，并且用一个指示器指示这条链的链头，以后，便可以从链头开始，沿着这条链逐个为其中各四元式填入转移目标。

(1)(jnz,a,,5)(2)(j,,,3)(3)(j<,b,c,5)(4)(j,,,p+1)(5)(关于S1的四元式序列)(P)(j,,,q)(p+1)(关于S2的四元式序列)(q)ifa∨b<cthenS1elseS2第79页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（2）真链T和假链F在实际操作时，1）将要填真出口的各四元式链接起来，组成一个链称真链T

，记为TC2）将要填假出口的各四元式链接起来，组成一个链称假链F

，记为FC

首先定义两个语义变量E.TC和E.FC分别指示T链和F链的链头。如下图：(1)(jnz,a,,0)(2)(j,,,3)E·TC→(3)(j<,b,c,1)E·FC→(4)(j,,,0)(5)链中各个四元式RESULT字段为相应结点指针字段，当其不为零时，它是链中后继四元式的序号如（2）中的3，否则，相应四元式是链尾结点，如（1）中的0

第80页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（3）改写布尔表达式文法G[E]为了使用语法制导翻译做回填工作，便于编制相应的语义子程序，我们对上面布尔表达式文法G［E］改写为

E∷=E∧E|E∨Ｅ|﹁E|(E)|i|iropiE∧∷=E∧E∨∷=E∨

当扫描到E∧和E∨并归约到E∧和E∨时就可以及时回填,知道真假出口，如果不是这样改写，当扫描到E∧和E∨时，还不能归约，因此就不能及时回填。第81页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

1）语义变量和语义过程为了构造语义子程序，我们引入下面语义变量和语义过程：①

NXQ是指示器，用来指示所要产生下一个四元式的序号，NXQ的初值为1，每当执行一次GEN之后，NXQ之值增1。如：

100(×，×，×，×)101(×，×，×，×)102(×，×，×，×)

NXQ103②GEN功能同前，每被调用一次，NXQ值增加一,形成一个四元式，送入四元式表。第82页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

1）语义变量和语义过程③BACKPATCH(p,t)是一过程，把四元式序号t填入以p为链头的链中各个四元式第四区段上。过程描述如下：PROCEDUREBACKPATCH(p,t)BEGINQ:=p;WHILEQ<>0DOBEGINq:=四元式Q的第四区段的内容;

把t填进四元式Q的第四区段;Q:=qENDEND将四元式链头序号P送到工作单元Q即将下一个四元式序号保存到q中让Q指向下一个四元式Q<>0表示没到链尾，执行循环体。第83页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

1）语义变量和语义过程③BACKPATCH(p,t)是一过程，把四元式序号t填入以p为链头的链中各个四元式第四区段上。过程描述如下：假定要填入四元式序号t＝31，四元式10，20，30形成一个链，其链头是30，链尾是10，现在执行算法BACKPATCH进行回填01020102030313131第84页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

1）语义变量和语义过程④MERG(p1，p2)是一个函数过程，把以链头分别为p1和p2两条链进行合并，并返回合并以后的链头。过程描述如下：POINTERPROCEDUREMERGE(p1,p2);IFp2=0THENMERG:=p1ELSEBEGINp:=p2;

WHILE四元式p第四区段的内容<>0DOp:=四元式p第四区段的内容;

把p1填进四元式p的第四区段

MERGE:=p2ENDp2=0意味着p2空，所以合并后p1为链头循环目的是找到p2的链尾将p1链头和p2后链尾链在一起，即p1和p2两个链合并返回链头p2，p2链头是合并后链头第85页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

1）语义变量和语义过程④MERG(p1，p2)是一个函数过程，把以链头分别为p1和p2两条链进行合并，并返回合并以后的链头。过程描述如下：假定P1为四元式10，20，30一个链，其链头P1＝30，P2为四元式40，50，60另一个链，其链头P2＝60，现在执行算法MERG，将P1和P2两个链进行合并，使得合并后的链头就是60，即P2的链头0102010203004050405060P1:30P2:60第86页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

1）语义变量和语义过程④MERG(p1，p2)是一个函数过程，把以链头分别为p1和p2两条链进行合并，并返回合并以后的链头。过程描述如下：假定P1为四元式10，20，30一个链，其链头P1＝30，P2为四元式40，50，60另一个链，其链头P2＝60，现在执行算法MERG，将P1和P2两个链进行合并，使得合并后的链头就是60，即P2的链头01020102030304050405060P1:30P2:60第87页，共96页，2023年，2月20日，星期四§5.3自底向上语法制导翻译二、布尔表达式的翻译3、翻译成四元式的实现（4）文法G[E]各规则语义子程序

2）语义子程序