new《编译原理》第五章.ppt

编 译 原 理 Compiler Principles,蒋 凌云 南京邮电大学.计算机学院,第五章 语法制导翻译及中间代码生成,教材：编译技术原理及其实现方法王汝传 编著,第五章 语法制导翻译及中间代码生成,本章内容,5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现 5.2 中间语言 一、引言 二、逆波兰表示 三、三元式 四、树形表示 五、四元式,第五章 语法制导翻译及中间代码生成,本章内容,5.3 自底向上语法制导翻译 一、简单算术表达式和赋值语句的翻译 二、布尔表达式的翻译 三、控制语句翻译 * 四、数组元素的翻译 五、过程语句的翻译 六、说明语句的翻译 5.4 自顶向下语法制导翻译 一、递归下降的语法制导翻译 二、LL(1)语法制导翻译 5.5 属性文法与属性翻译 一、属性文法与L属性文法 二、属性翻译,第五章 语法制导翻译及中间代码生成,本节内容,5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现 5.2 中间语言 一、引言 二、逆波兰表示 三、三元式 四、树形表示 五、四元式,5.1 语法制导翻译概述,本节内容,一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,第五章 语法制导翻译及中间代码生成,5.1 语法制导翻译概述 在前面我们已经讨论了词法分析和语法分析，一个程序成功地通过词法分析和语法分析，只能说明它是一个合法程序，但是对程序内部的逻辑含义并未加以考虑，从整个编译程序来看，词法分析和语法分析仅仅是编译程序的一部分，编译程序最终的目的是将源程序翻译成可供计算机直接执行的目标程序。 在某些编译程序中，是直接生成机器语言或汇编语言形式的目标代码；有些编译程序是把源程序翻译为某种形式中间语言代码，然后 再把中间语言代码翻译为目标代码。 下面就来介绍一种语法制导翻译方法，这种方法先将源程序单词序列翻译成中间语言，然后再将中间语言翻译成目标程序。那么，什么叫语法制导翻译呢？,第五章 语法制导翻译及中间代码 5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,第五章 语法制导翻译及中间代码 5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,5.1 语法制导翻译概述 一、语法制导翻译定义 语法制导翻译就是以语法分析为主导的语义处理。在自顶向下语法分析 过程中嵌入语义动作，即调用对应的语义子程序。 例如在前面语法分析时分析a+b*c表达式，其分析语法树如下：,E,+,E,E,*,E,E,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，最后再将左右两个E值相加就是最终结果，这就是语法制导翻译的基本思想，在语法分析同时进行语义分析。,第五章 语法制导翻译及中间代码 5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,第五章 语法制导翻译及中间代码 5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,5.1 语法制导翻译概述 二、语法制导翻译原理 语法制导翻译的原理就是先为每个文法规定相应的语义，即编写出相应语义处理子程序，整个分析是以语法分析为主导。在自顶向下语法分析时，若某一个规则右部与输入串相匹配时，或者，在自底向上语法分析时，当一个规则被用于归约时，此时该规则对应的语义子程序就进入工作，完成既定翻译任务，产生与语义相应的中间代码或目标代码。 语义动作：给每个文法符号X赋以各种不同的语义值 这里的语义值不一定指具体数值，可以是“类型”、“种属”、“地址”或“代码”等，我们用记号XTYPE、XCAT或XVAL来表示这些值。如果某规则的右部有若干个同一符号出现，那么我们就用上角标来区别这些符号。例如，假定有如下规则和语义动作 ：,例如，假定有如下规则和语义动作 ： E=E(1)+E(2) EVAL:=E(1)VAL+E(2)VAL 语义动作写在规则之后的花括号里，这里语义动作是表明与规则左部 文法符号E相关的语义值EVAL，它是通过把规则右部文法符号的语义 值E(1)VAL和E(2)VAL加在一起来决定的，规则中终结符号“+”按语义 规则被解释成通常“加”的意思 。各规则的语义动作可以对表达式计算，也可以生成中间代码，甚至还可以来产生目标指令。 例5.1 设有文法 E=E+E E=digit 这里digit代表0和9之间任一数字，如果我们的目的仅是为了求值，则 语义动作如下 (1) E=E(1)+E()EVAL:=E(1)VAL+E(2)VAL (2) E=digit EVAL:=digit 假定语义动作中的“+”代表是整型加算术运算。 规则(1)的语义动作为: E的语义值EVAL等于E(1) 和E(2)的语义值E(1) VAL和E(2)VAL之和. 规则(2)的语义动作为: E的语义值为09之间任一个数. 这样，按照它们的语义动作，我们在分析每个句子的同时一步一步地算出 每个句子的值 。,例如，假定有输入串1+2+3，我们通过语法树的分析来看如何进行语法 制导翻译，来求出该句子最后值。 输入串1+2+3的语法树如下图所示：,下面我们采用自底向上归约过程。首先考虑底层最左E的结点，这个 结点对应于规则E=1和语义动作EVAL：=1。这样，底层最左的E的 值1与语义值EVAL相关。类似地，值2与该结点的右兄弟的语义值EVAL 相关。如下图所示：,E,+,E,E,+,E,E,1,2,3,在图所示子树中，子树根处EVAL的语义值是3，这可用语义动作 EVAL:=E(1)VAL+E(2)VAL算出。使用这个语义动作时，以底部最左的E的 EVAL的值来代替E(1)VAL ，而以右边E的EVAL的值代替E(2)VAL 。 以这种方法继续下去，我们就推出如下图所示整个语法树每个结点的语义值。,E,+,E,E VAL=1,E,1,2,E VAL=2,E,+,E VAL=6,E,E VAL=3,E,E VAL=3,+,E,E VAL=1,E,E VAL=2,1,2,3,第五章 语法制导翻译及中间代码 5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,第五章 语法制导翻译及中间代码 5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现,5.1 语法制导翻译概述 三、语法制导翻译实现 上面我们从原则上讨论了语法制导翻译的原理，下面我们通 过一个自底向上LR分析看如何实现语法制导翻译。例如： 有规则： (1)X= 动作1 (2)Y= 动作2 (3)A=XY 动作3 当使用规则(1)、(2)归约时，动作1和动作2 工作结果的有关信息(作为X和Y的语义值)应暂时保存下来，以便以后用规则(3)在归约时(动作3)可引用这些值。 现在对LR分析器的分析栈加以扩充，为了在语法分析过程中平行地进行语义处理，使得每个文法符号之后都跟着它的语义值，因此，设置一个语义信息栈，为了清晰起见，我们把这个分析栈每一项分三部分组成：状态STATE、文法符号SYM和语义值VAL。这样，分析栈如下图所示。,TOP,STATE,VAL,SYM,TOP(100),归约前,TOP(99),归约后,YVAL,TOP(99),求值后,AVAL:=YVAL和XVAL的处理结果,我们假定先归约后执行语义子程序，所以当X，Y归约为A时，此时栈顶 指针下退。 例如：开始TOP指100 VALTOP：=Y.VAL（100） VALTOP-1：=X.VAL（99） 若归约后，此时TOP指99，所以 VALTOP：=X.VAL（99） VALTOP+1：=Y.VAL（100） 若求值后，此时TOP指99，所以 VALTOP：=A.VAL（99）,例5.2 考虑下面文法及其语义描述： 规 则 语义动作 (0)S=E print EVAL (1)E=E(1)+E(2) EVAL:=E(1)VAL+E(2)VAL (2)E=E(1)*E(2) EVAL:=E(1)VAL*E(2)VAL (3)E=(E(1) EVAL=E(1)VAL (4)E=i EVAL:=LEXVAL 其中： 语义动作中的+、*代表整型加、乘算术运算，而且词法分析 程序将送来每个i的整型内部值LEXVAL。 假定语义动作是紧接在归约之后执行的。上面所列的语义动作 就相当于下面所列的程序段：,规 则 程序段 (0)S=E print VALTOP (1)E=E(1)+E(2) VALTOP：=VALTOP+VALTOP+2 (2)E=E(1)*E(2) VALTOP：=VALTOP*VALTOP+2 (3)E=(E(1) VALTOP:=VALTOP+1 (4)E=i VALTOP:=LEXVAL,由于有一个“+“号，所以为TOP+2,由于有一个“(“号，所以为TOP+1,由于有一个”*”号，所以为TOP+2,根据上述程序段，若输入2*3+2，就有如下图所示的语法制导翻译的分析树。,S,E,E,E,E,E,+,*,2,2,3,E VAL=8,E VAL=6,E VAL=2,E VAL=2,E VAL=3,LEXVAL=2,LEXVAL=3,LEXVAL=2,对2*3+2利用P136.表4.23进行分析和翻译(实为计算值)该输入串过程如下表所示。当状态1面临#时对应的分析动作为acc(接受)，此时， 相应的语义动作为print VALTOP，即输出语义程序的计值结果：8。,第五章 语法制导翻译及中间代码生成,本节内容,5.1 语法制导翻译概述 一、语法制导翻译定义 二、语法制导翻译原理 三、语法制导翻译实现 5.2 中间语言 一、引言 二、逆波兰表示 三、三元式 四、树形表示 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 一、引言 1. 什么是中间语言 就是和源程序等价的一种编码形式，其复杂性介于源程序 和机器语言中间。,源程序,前端,中间代码,代码 优化器,中间代码,代码 生成器,目标程序,符号表,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 一、引言 2. 为什么要引入中间语言 (1) 为了使编译程序结构上逻辑简单明确 (2) 为了便于目标代码优化工作 (3) 便于目标代码生成,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 二、逆波兰表示 1. 表达式逆波兰表示 （1）波兰表示的概念 对于一个算术表达式A+B或逻辑表达式AB，根据运算符和运算 对象的位置关系，可分为三种等价表示形式： 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，,例如表达式中缀表示和后缀表示如下表所示(p155表5.2）,说明： 以后我们主要讨论逆波兰表示，即后缀表示，因前缀表示并不常用，所以有时也将后缀表示笼统地统称为波兰表示。 从上表中可以看出： (1)在中缀表示和后缀表示中，运算对象按相同次序出现。 (2)在后缀表示中，运算符是按实际计算顺序从左到右排列，且每一运算符总是跟在它的运算对象之后。,(2)逆波兰(后缀)表示的优点 1）后缀表示是一种无括号表示法，不但简明，而且又确切规 定了计算顺序。 2）运算处理极其简单方便，只要从左到右扫描后缀表达式 各个符号，就能进行对表达式的处理 一般步骤是从左到右扫描后缀表达式各个符号，每碰到运算对象时就把它推进栈，每碰到一个K元运算符时，就取出栈顶的K个运算对象进行相应的运算，并且用运算结果去替换栈顶的K个运算对象，然后再继续扫描表达式中余留符号，如此等等，直到整个表达式计算完毕为止。 当上述过程结束后，整个表达式之值将留于栈顶。 3) 便于生成目标指令,(3) 逆波兰(后缀)表示的形成 为了说明逆波兰(后缀)表示的形成，荷兰学者 W.DEJKSTRA给出下面形象的解释。,比栈顶高进栈，比栈顶低或相同的退栈,下面用图解形式来说明A+B*C形成的过程。,A,运算对象A移进对象栈,#,+B*C#,下面用图解形式来说明A+B*C形成的过程。,A,#，向下进运算符栈,#,B*C#,下面用图解形式来说明A+B*C形成的过程。,AB,运算对象B移进对象栈,#,*C#,下面用图解形式来说明A+B*C形成的过程。,AB,*+，*向下进运算符栈,*#,C#,下面用图解形式来说明A+B*C形成的过程。,ABC,运算对象C移进对象栈,*#,#,下面用图解形式来说明A+B*C形成的过程。,ABC*,#*，*退栈往左,#,#,下面用图解形式来说明A+B*C形成的过程。,ABC*,#，退栈往左,#,#,最后生成A+B*C的后缀式ABC*,(4)用后缀表式对表达式处理的过程 下面通过求后缀表达式ab+c*的值，来说明用后缀表式对表达式处理的 过程 设a，b和c分别为1，3和5，为了求1 3+5*的值，其计算过程如下： 1)把1推进栈。 2)把3推进栈。 3)将栈顶两个元素1和3相加，使它们退出栈，然后把 结果4存入栈。 4)把5推进栈。 5)将栈顶两个元素4和5相乘，使它们退出栈，然后将 结果20存入栈。 结束时栈顶的值(这里是20)是整个表达式值。,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 二、逆波兰表示 2.逆波兰表示的扩充 只要遵守在运算对象后直接紧跟运算符这条规则，我们就可以 简单地把这种后缀式扩充到比通常表达式更大范围，即扩充到程序 语言的其它语法成分。 （1）赋值语句 左部:=表达式 把赋值号“:=”看成是一个赋值运算符，它的后缀式为 左部表达式的后缀式：= 例如：x:=5 x:=a*b-c/d 的后缀式分别为 x5:= xab*cd/-:=,赋值语句的后缀式的处理方法和后缀式表达式处理方法类似。所不同的 是栈中保存的是左部变量的地址，而不是其值，在赋值运算处理结束后， 不产生任何中间计算结果，因而也不存在保存中间计算结果的问题，而是 把存放在运算栈中栈顶两项左部和表达式的值这两个量退掉。,（2）条件语句 if E then S1 else S 对于用后缀式来表示条件语句，我们假定后缀式中各符号存放在一个 一维数组POST1n之中，每一个数组元素存放一个运算对象或运算符。 同时我们约定如下几个符号： JUMP表示无条件转； JLT表示小于转； JEZ表示零转。 后缀式P JUMP表示无条件转移到下标P所指那个元素POSTp (即从该符号开始继续执行)。 后缀式e P JEZ表示当后缀表达式e的值为零时，则转移至POSTP。 后缀式e1e2 P JLT表示当后缀表达式e1小于后缀表达式e2时，则转移至POSTP,于是，对于形如 if e then S1 else S2 的条件语句可按后缀式写成ep1JEZ S1p2JUMP S2 我们约定e0时,该条件语句的值是S1,否则等于S2 。 对于后缀式条件语句中:e 、 S1和S2 分别是e、 S1和S2的后缀式。 此外, p1表示S2 在数组POST的起始位置, p2表示S2 之后那个符号 位置。 上述后缀式条件语句的意思是,若e=0时,则转至POSTp1对S2 进行计算,否则计算S1,然后转到POSTp2的位置。 e p1 JEZ S1 p2 JUMP S2 （ p1和p2 等处理S2后再反填）,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 二、逆波兰表示 3. 语法制导翻译生成后缀式 下面我们讨论语法制导翻译生成后缀式的过程。我们以例4.15 文法GE为例，说明如何按语法制导翻译方法把一个中缀形式的 简单算术表达式翻译成为后缀式。,后缀式的语义动作 规则 语义动作 (1) E=E(1)+T ECODE:=E(1).CODET.CODE+ (2) E=T ECODE:=TCODE (3) T=T(1)*F TCODE:=T(1)CODEFCODE* (4) T=F TCODE:=FCODE (5) F=(E) FCODE:=ECODE (6) F=i FCODE:=i 几点说明: E.CODE,T.CODE,F.CODE表示构成后缀式的符号串 符号“”表示两个串的“捻接”运算，即并置运算 。显然, E(1).CODET.CODE+ 是E.CODE,因为符号在后,其它类似.,下面将上述语义动作具体化成语义子程序:,自底向上分析要归约时先调用相应子程序生成后缀式 假定后缀式存放在数组POST中 假设要归约的句柄为 E(1)+T(在语法分析栈中)，则首先要求调用相应于E(1)+T的语义子程序，此时 E(1)和T已调用过相应的语义子程序，因此，它们的后缀式已被生成，对应于 E(1)+T的语义子程序所要完成的工作是把已生成的两后缀式捻接起来，然后再 添上符号“+”。 如果我们设置一个数组存放后缀式，那么语义动作就可以不涉及 捻接运算。令这个数组为POST，p为下标，初值为1。 如下图：,POST(P),对于上述文法GE的语义动作，可以改写为如下相应的 语义子程序： (1) E=E(1)+T POSTp:=+;p:=p+1 (2) E=T (3) T=T(1)*F POSTp:=*;p:=p+1 (4) T=F (5) F=(E) (6) F=i POSTp:=i;p:=p+1,最后，我们以表达式a+b*c为例按照P118.表4.15文法GELR分析表 给出语法制导翻译产生后缀式过程， 其中SUBK表示第K个规则相对应的语义子程序。分析过程如下表：,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 三、三元式表示 1.三元式 (1) 定义 三元式的一般形式为 (i) (OP, ARG1, ARG2) 其中：(i)为三元式的编号，不同三元式不能有相同的编号 OP是运算符部分 ARG1和ARG2是运算对象部分，它们或者指向符号表登记项指示 器(对于运算对象是常数或标识符的情况)，或者是一个指向三元式 序列(或三元式表)中某一个三元式位置的指示器(对于运算对象是中 间结果的情况)。 如：A+B*C对应的三元式表示为： (1) (*，B，C) (2) (+，A，(1),注：运算符OP通常用一个整数码表示，它除了标识运算符的种属 之外，还附带地表示其它一些语义特性。例如若OP表示一个加法 运算符，则相应的整数码除了标识加法运算本身外，还兼有表示 数据类型(如整型、实型等)、运算方式(定点、浮点)和运算精度等 信息，且不同语义属性使用不同的运算符代码。,对于一目运算符OP，ARG1和ARG2只需其一。我们可以随意规定选用一个，例如，规定用ARG1。至于多目运算符可以用若干个相继三元式表示。 如：赋值语句 x:=-b*(c+d) 用三元式来表示，则可写成 (1) ( - ,b, ) (2) (+, c, d) (3)(*,(1),(2) (4)(:=,x,(3) 其中，三元式(3)就引用三元式(1)和(2)的结果作为它的两个运算对象,三元式出现先后顺序和表达式各部分计算顺序相一致！,(2) 三元式的生成 同样可以用语法制导翻译来产生三元式： 下面给出文法GE的语义动作来描述这种翻译的算法： (1)E=E(1)+T EVAL:=TRIP(+,E(1)VAL,TVAL) (2)E=T EVAL:=TVAL (3)T=T(1)*F TVAL:=TRIP(*,T(1)VAL,FVAL) (4)T=F TVAL:=FVAL (5)F=(E) FVAL:=EVAL (6)F=i FVAL:=ENTRY(i) 其中语义值EVAL、TVAL和FVAL，是一个指示器，或指向有关符号 表某一项，或指向三元式表自身某一项，TRIP(OP，ARG1，ARG2)是 一个语义子程序，回送新产生的三元式存放在三元式表位置。 ENTRY(i)是一个语义子程序，通过ENTRY查i在符号表中位置，即 对应地址，若查不到，认为有错误。,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 三、三元式表示 2. 间接三元式 为了便于代码优化，常常采用间接三元式。这由两张表组成： （1）三元式表，用来存放各三元式本身； （2）执行表(间接码表)，它按执行三元式顺序，依次列出相应各 三元式在三元式表中位置 。,例如，对于如下赋值语句 x:=a*b+c+a*b 若按三元式表示，可写成,按间接三元式表示，则可写成 执行表 三元式表 (1) (1) (*,a,b) (2) (2) (+,(1),c) (1) (3) (+,(2),(1) (3) (4) (:=,x,(3) (4),(1) (*,a,b) (2) (+,(1),c) (3) (*,a,b) (4) (+,(2),(3) (5) (:=,x,(4) 其中，三元式(1)和(3)完全一样， 但是不能将(3)省去。,间接三元式的优点： （1）便于代码优化 在进行代码优化时，常常要从中间代码删去一些运算，或者 把某些运算移到另外位置上，若采用一般三元式，则由于三元式 之间引用太多，很难做到这一点 。 （2）节省空间 由于在间接三元式执行表中已经依次列出每次要执行的那个 三元式，所以，若有若干个相同三元式，则仅须在三元式表中 保存其中之一。如上面赋值语句右部表达式中有两个a*b子表达式， 而三元式表中只出现一次(*, a, b) 。,对于间接三元式表示，语义子程序应增添产生执行表的动作。 在填写三元式表时，应首先看一下此三元式是否在其中， 如已在其中，则无需填入。,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 四、树形表示 1. 表示方法 我们可以用树形数据结构来表示一个表达式或语句 。 在树表示中，叶子结点表示运算对象，即常量或变量，其它结点 表示运算符，如表达式 a+b, a-b, -a 的树表示分别定义为：,+,a,b,a,b,a,双目运算对应二叉树，多目运算对应多叉树，单目运算对应单叉树 。 如表达式a*b-(c+d)/(e-f)的二叉树如下图：,后序遍历上述二叉树便得到该表达式的逆波兰表示为 ab*cd+ef-/-,*,/,a,b,+,c,d,e,f,表达式的三元式可以看作是树的直接表示，图5.7所对应的三元式为 (1) (*,a,b) (2) (+,c,d) (3) (-,e,f) (4) (/,(2),(3) (5) (-,(1),(4) 显然，每一个三元式对应一棵子树，子树的根便是三元式的运算符， 三元式的运算对象是子树两个分枝 。,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 四、树形表示 2. 树表示生成 对文GE翻译成树形表示语义动作描述如下： (1)E=E(1)+T EVAL:=NODE(+,E(1)VAL,TVAL) (2)E=T EVAL:=TVAL (3)T=T(1)*F TVAL:=NODE(*,T(1)VAL,FVAL) (4)T=F TVAL:=FVAL (5)F=(E) FVAL:=EVAL (6)F=i FVAL:=LEAF(i) 其中：语义值EVAL、TVAL和FVAL是一个指示器，指向树一个结点。 NODE (OP，LEFT，RIGHT)是一个函数子程序， OP是一个二元运算符，LEFT，RIGHT为指示器，每调用 此函数一次,就建立一个新结点，其标记为OP， LEFT和RIGHT分别指向左右子树根结点指针，从NODE回送 的值是一个指示器，指向这棵新树的根。 LEAF(i)是建立一个末端结点(叶结点),第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,第五章 语法制导翻译及中间代码生成,5.2 中间语言 一、引言 1.什么是中间语言 2.为什么要引入中间语言 二、逆波兰表示 1.表达式逆波兰表示 2.逆波兰表示的扩充 3.语法制导翻译生成后缀式 三、三元式 1.三元式 2.间接三元式 四、树形表示 1. 表示方法 2. 树表示生成 五、四元式,5.2 中间语言 五、四元式表示 四元式是一种用得比较多的一种中间语言代码形式，四元式 一般形式是 (OP，ARG1，ARG2，RESULT) 其中：OP是运算符，其含义与三元式中OP类似； ARG1和ARG2是运算对象， RESULT是运算结果,例如：赋值语句 a:=-b*(c+d) 用四元式表示，则可写成 (1) ( - , b,T1) (2) (+,c,d,T2) (3) (*,T1,T2,T3) (4) (:=,T3, ,a),四元式之间联系是通过临时变量实现 的，调整四元式之间相对位置并不 意味着一定要改变一系列指示器值。 因此，对中间代码进行优化处理时， 四元式比三元式方便得多。 下面主要讨论如何用四元式表示 各种语句，并产生四元式语义子程序。,第五章 语法制导翻译及中间代码生成,本节内容,5.3 自底向上语法制导翻译 一、简单算术表达式和赋值语句的翻译 二、布尔表达式的翻译 三、控制语句翻译 四、数组元素的翻译 五、过程语句的翻译 六、说明语句的翻译 5.4 自顶向下语法制导翻译 一、递归下降的语法制导翻译 二、LL(1)语法制导翻译 5.5 属性文法与属性翻译 一、属性文法与L属性文法 二、属性翻译,第五章 语法制导翻译及中间代码生成 5.3 自底向上语法制导翻译,一、简单算术表达式和赋 值语句的翻译 1. 翻译成四元式 2. 类型检查与类型转换 二、布尔表达式的翻译 1. 概述 2.布尔表达式的翻译方法 3.翻译成四元式的实现 三、控制语句翻译 1.语句标号和goto语句的翻译 2.条件语句的翻译 3.布尔表达式的翻译方法 4.while循环语句翻译 5.for循环语句的翻译,四、数组元素的翻译 1. 下标变量地址的计算 2.数组元素的翻译 五、过程语句的翻译 1.参数传递方式 2.过程语句的翻译 六、说明语句的翻译 1.变量说明的翻译 2.数组说明的翻译 3.过程说明的翻译,第五章 语法制导翻译及中间代码生成 5.3 自底向上语法制导翻译,一、简单算术表达式和赋 值语句的翻译 1. 翻译成四元式 2. 类型检查与类型转换 二、布尔表达式的翻译 1. 概述 2.布尔表达式的翻译方法 3.翻译成四元式的实现 三、控制语句翻译 1.语句标号和goto语句的翻译 2.条件语句的翻译 3.布尔表达式的翻译方法 4.while循环语句翻译 5.for循环语句的翻译,四、数组元素的翻译 1. 下标变量地址的计算 2.数组元素的翻译 五、过程语句的翻译 1.参数传递方式 2.过程语句的翻译 六、说明语句的翻译 1.变量说明的翻译 2.数组说明的翻译 3.过程说明的翻译,第五章 语法制导翻译及中间代码生成 5.3 自底向上语法制导翻译,一、简单算术表达式和赋 值语句的翻译 1. 翻译成四元式 2. 类型检查与类型转换 二、布尔表达式的翻译 1. 概述 2.布尔表达式的翻译方法 3.翻译成四元式的实现 三、控制语句翻译 1.语句标号和goto语句的翻译 2.条件语句的翻译 3.布尔表达式的翻译方法 4.while循环语句翻译 5.for循环语句的翻译,四、数组元素的翻译 1. 下标变量地址的计算 2.数组元素的翻译 五、过程语句的翻译 1.参数传递方式 2.过程语句的翻译 六、说明语句的翻译 1.变量说明的翻译 2.数组说明的翻译 3.过程说明的翻译,5.3 自底向上语法制导翻译 一、简单算术表达式和赋值语句的翻译 1. 翻译成四元式 我们首先讨论仅含有简单变量的表达式和赋值语句到四元式的翻译，对于复杂的表达式和赋值语句的翻译将在以后讨论 。 为简便起见，假定赋值语句中所含的全部变量是同一类型整型变量，此外在翻译过程中也不作语义检查。 (1) 赋值语句的文法 1) A=V:=E 5)T=F 2) E=E (1)+T 6)F=(E) 3) E=T 7)F=i 4) T=T(1)*F 8)V=i 为了实现到四元式的翻译，需要引进一系列语义变量和语义子程序。,(2)语义变量和语义子程序 NEWTEMP是一个函数，每次调用时，都定义一个新临时变量，回送 一个代表新临时变量名的整数码作为函数值。为直观起见，我们将 NEWTEMP产生的临时变量依次记为T，等等。 ENTRY(i)是一个函数过程 ，查找符号名i在表中的入口地址。 XPLACE是和非终结符X相联系的语义变量，表示存放X值的变量名在 符号表的入口或整数码(若此变量是一个临时变量)。 如： F=i FPLACE:=ENTRY(i) 表示存放F值变量名i在符号表 中的入口地址。即从变量F.PLACE值可知i在符号表中的位置。 GEN (OP，ARG1，ARG2，RESULT)是一个语义过程，该过程把四元式 (OP，ARG1，ARG2，RESULT)填入四元式表中。,因此，上面定义文法GA语义子程序的描述如下：,(3)语义子程序的描述 (1) A=V:=E GEN(:=,EPLACE, ,VPLACE) (2)E=E(1)+T EPLACE:=NEWTEMP; GEN(+,E(1)PLACE,TPLACE,EPLACE) (3) E=T EPLACE:=TPLACE (4) T=T(1)*F TPLACE:=NEWTEMP; GEN(*,T(1)PLACE,FPLACE,TPLACE) (5) T=F TPLACE:=FPLACE (6) F=(E) FPLACE:=EPLACE (7) F=i FPLACE:=ENTRY(i) (8) V=i VPLACE:=ENTRY(i),在进行自底向上语法制导翻译时，还需一张LR分析表，上述文法GA 是一个SLR(1)文法，其分析表如下：,（4）文法GASLR(1)分析表,（5）对x:=a+b*c语法制导翻译产生四元式过程（以赋值语句x:=a+b*c为例）,分析表几点说明： 在分析表中Vx,Ea,Tb,Fc之类记号，表示与非终结符V,E,T,F相关联 的VPLACE,E.PLACE,T.PLACE,F.PLACE中存放着ENTRY(x), ENTRY(a), ENTRY(b), ENTRY(c) 符号指针，指向符号表。 在四元式中，如（*，b,c,T1)，*实际上是某种整数编码，反映 运算符本身及其信息特征，如类型等。 b, c实际上也是指示器，指示符号表入口；T1是临时变量，实际上 也是整数码. 下面我们根据上面分析表叙述对x:=a+b*c语法制导翻译产生四元式过程,第五章 语法制导翻译及中间代码生成 5.3 自底向上语法制导翻译,一、简单算术表达式和赋 值语句的翻译 1. 翻译成四元式 2. 类型检查与类型转换 二、布尔表达式的翻译 1. 概述 2.布尔表达式的翻译方法 3.翻译成四元式的实现 三、控制语句翻译 1.语句标号和goto语句的翻译 2.条件语句的翻译 3.布尔表达式的翻译方法 4.while循环语句翻译 5.for循环语句的翻译,四、数组元素的翻译 1. 下标变量地址的计算 2.数组元素的翻译 五、过程语句的翻译 1.参数传递方式 2.过程语句的翻译 六、说明语句的翻译 1.变量说明的翻译 2.数组说明的翻译 3.过程说明的翻译,5.3 自底向上语法制导翻译 一、简单算术表达式和赋值语句的翻译 2. 类型检查与类型转换 (1)目的 1) 类型检查是编译程序语义检查不可缺少的一部分。 类型检查就是对访问数据的操作和被访问数据的类型进行检查 检查操作的合法性和数据类型的相容性。例如，在PASCAL语言中， 若算术运算符的操作数为布尔量，或者赋给实型变量值是个指针， 则编译程序报告“类型不相容”的诊断信息。 2)允许类型混合，但在处理时要统一，所以必须进行类型转换。 例如，加法运算“+”允许运算对象是整型数或实型数,如果一个 运算对象是实型，另一个运算对象是整型，其运算结果的类型是实 型，由于实型数和整型数的内部表示不相同，因此为了使整型数能 参加实型数运算，必须事先将整型数转换成实型数。,(2)类型检查 类型检查可在生成中间代码时进行，也可在生成目标代码时进行，但最好是在生成中间代码时进行，因为语法和语义检查最好尽早进行，这样能尽早避免徒劳的工作。 在上面对简单算术表达式和赋值语句翻译到四元式的讨论中，我们假定各个变量是同一类型整型变量，并且规定在四元式的op代码中，本身就会有类型信息。所以，在上例各语义子程序中，我们并未考虑有关类型方面语义处理。,（3）类型转换方法 为了简单起见，我们仅考虑整型和实型的情况。 这种混合运算中，给每个非终结符的语义值增添类型信息X.MODE XMODE的值或为r(实型)或为int(整型)。 原来X的信息除X.PLACE， 还有X.MODE。 对表达式的每一规则的语义子程序进行修改，增加关于类型 信息的语义规则 。 必要时应产生对运算量进行类型转换的四元式 ， (itr,A,T) 把整型变量A转换成实型变量，结果存在T中。,此外，在书写语义子程序时，为阅读上的直观性，我们用+i,*i等 表示整型运算符，用+r,*r等表示实型运算符。 现以规则E=E(1)OP E(2)为例，给出语义子程序的具体描述如下：,现以规则E=E(1)OP E(2)为例，给出语义子程序的具体描述如下： T:=NEWTEMP; IF E(1)MODE=int AND E(2)MODE=int THEN BEGIN GEN(opi,E(1)PLACE,E(2)PLACE,T); EMODE:=int END ELSE IF E(1)MODE=r AND E(2)MODE=r THEN BEGIN GEN (opr,E(1)PLACE,E(2)PLACE,T); EMODE:=r END ELSE IF E(1)MODE=int/*and E(2)MODE=r*/THEN BEGIN U:=NEWTEMP; GEN (itr, E(1)PLACE,-,U); GEN (opr,U,E(2)PLACE,T); EMODE:=r END ELSE / * E(1) MODE=r and E(2)MODE=int * / BEGIN U:=NEWTEMP; GEN (itr, E(2)PLACE,-,U); GEN (opr,E(1)PLACE,U,T); EMODE:=r END; EPLACE:=T;,这样,对于输入串为 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),第五章 语法制导翻译及中间代码生成 5.3 自底向上语法制导翻译,一、简单算术表达式和赋 值语句的翻译 1. 翻译成四元式 2. 类型检查与类型转换 二、布尔表达式的翻译 1.