《编译原理5语法制导翻译技术和中间代码生成new.》由会员分享，可在线阅读，更多相关《编译原理5语法制导翻译技术和中间代码生成new.（37页珍藏版）》请在金锄头文库上搜索。
1、第5章 语法制导翻译技术和中间代码生成 5.1概述 对语法分析后的语法单位进行语义分析，首先编译程序审查每 个语法结构的静态语义，如果静态语义正确，再生成中间代码 ，也有的编译程序不生成中间代码，而直接生成目标代码。 目前较为常见的是用属性文法作为描述程序设计语言语义的工 具，采用语法制导翻译法完成对语法成分的翻译工作。 5.2属性文法 属性：一般用来描述客观存在的事物或人的特性。 一个属性文法是在上下文无关文法的基础上，允许每个文法符 号X（终结符或非终结符)根据处理的需要，定义与X相关联的 属性，以及对属性的处理规则（我们称为语义规则)。 属性通常分为两类：综合属性和继承属性。简单地说，综
2、合属 性用于自下向上传递信息，而继承属性用于自上向下传递信息 。 在一个属性文法中，对应于每一个产生式A都有一个与之 相关联的语义规则(可包括属性的计算，静态语义检查，符号 表操作，代码生成等)，每条规则的形式为： b=f(c1,c2,ck) 这里f是一个函数，而且或者 1)b是A的一个综合属性，并且c1,c2,ck是产生式右边文法符 号的属性；或者 2)b是产生式右边文法符号的一个继承属性并且c1,c2,ck是A 或产生式右边任何文法符号的属性。 在两种情况下，我们都说属性b依赖于属性c1,c2,ck 特别强调的是： 1)终结符只有综合属性，他们由词法分析器提供； 2)非终结符既可以有综合属
3、性也可以有继承属性，文法开始符 号的所有继承属性作为属性计算前的初始值。 一般来说，对于出现在产生式右边的继承属性和出现在产生式 左边的综合属性都必须提供一个计算规则，属性计算规则中只 能使用相应产生式中的文法符号的属性，然而出现在产生式左 边的继承属性和出现在产生式右边的综合属性不由所给产生式 的属性计算规则进行计算，他们由其他产生式的属性规则计算 或由属性计算器的参数提供。 属性文法形式定义为一个四元组AG=(G,A,R,B),G是一个已经化 简的上下文无关文法，A是属性的有限集合，R是语义规则的有 限集，B是描述使R有效的条件的有限集合；且同时满足： 1)每个属性与某个文法符号X相关联，
4、用“文法符号属性”表示这 种关联，从而保证了G中任意两个不同的文法符号X和Y，属性 集合A(X)和A(Y)不相交。 2)在G的任意一个语法树中，对文法符号X的每一次出现，可用 于计算X的每个属性X.a(X.aA(X)之值的规则至多有一条（每 个产生式中的任一文法符号的属性计算规则只能是唯一的) 例：对于一个简单表达式的文法： EN(1)+N(2)| N(1) or N(2) N num|true|false 遵照以上关联与程序设计语言中有关类型的检验原则可以得到关 于类型检验的属性文法： 1.EN(1)+N(2) 2.EN(1)orN(2) 3.N num 4.N true 5.N false
5、 N(1)type=int and N(2)type=int N(1)type=bool and N(2)bool=bool Ntype=int Ntype=bool Ntype=bool 例：简单算术表达式求 值的属性文法 1.S E 2.E E(1)+T 3. E T 4. T T(1)*F 5. T F 6.F (E) 7.F digit print(E.val) E .val =E(1) .val +T .val E .val =T .val T .val =T(1) .val *F .val T .val =F .val F .val =E .val F .val =digit.le
6、xval 例：说明语句中简单变量类型信息的属性文法 1.D TL 2.T int 3.Treal 4.L L(1),i 5.L i L.in=T.type T.type=integer T.type=real L(1).in= L.in addtype(i.entry,L.in) addtype(i.entry,L.in) 5.3语法制导翻译概述 语法制导翻译法的基本思想：对文法中的每个产生式都附加 上一个语义动作或语义子程序，在执行语法分析的过程中， 每当使用一条产生式进行推导或归约时，就执行相应的产生 式的语义动作。 这些语义动作不仅指明了该产生式所产生的符号串的意义， 而且还根据这种意义
7、规定了对应的加工动作，从而完成预定 的翻译工作。 语法制导翻译法就是在语法分析过程中随着分析的逐步发展 ，根据相应文法的每一规则所对应的语义子程序进行翻译的 方法。具体分为自底向上语法制导翻译和自顶向下语法制导 翻译两种。 下面以LR语法制导翻译为例，讨论如何具体实现语法制导翻译 ： 1.为文法的每个规则设计相应的语义子程序。 例：一个简单算术表达式计值的文法 E E+E|E*E|(E)|digit 1. E E(1)+E(2) 2. E E(1)*E(2) 3. E (E(1) 4. E digit E.val =E(1) .val +E(2) .val E.val =E(1) .val *
8、E(2) .val E.val =E(1) .val E.val =digit .lexval 2.为上述文法构造LR分析表 状态ACTIONGOTO +digit*()$E 0S3S21 1S4S5acc6 2S3S2 3r4r4r4r4 4S3S27 5S3S28 6S4S5S9 7r1S5r1r1 8r2S6r2r2r2 9r3r3r3r3 3.将原先的语法分析栈扩充，以便存放文法符号对应的语义值 。 分析栈中可以存放三类信息：分析状态，文法符号及其语义值 SKXKXK.val . S1X1X1 .val S0X0X0. val 状态栈文法符号栈语义值栈 4.根据语义分析栈的工作过程，设
9、计总控程序，使其在完成语 法分析工作的同时，也能完成语义分析动作，即在用某一个产 生式进行归约的同时，调用相应的语义子程序完成所用产生式 相应的语义动作，并将每次工作后的语义值保存在扩充后的语 义值栈中。 步骤状态栈语义栈符号栈输入符号分析 动作 10-$7+8*5$S3 203-$7+8*5 $r4 301-7$E+8*5 $s4 4014-7-$E+8*5 $s3 50143-7-$E+8*5 $r4 60147-7-8$E+E*5 $s5 701475-7-8-$ E+E*5$s3 801475 3 -7-8-$ E+E*5$r4 901475 8 -7-8-5$E+E*E$r2 100
10、147-7-40$ E+E$r1 1101-47$E$acc 5.4 中间语言 编译器各阶段的完整输出，均可以被认为是源程序的某种中间 表示。 本节讨论的是中间代码生成器输出的中间表示，称之为中间代 码。 中间代码实际上应起一个编译器前端与后端分水岭的作用。 要求中间代码具有如下特性，以便于编译器的开发移植和代码 的优化： 1便于语法制导翻译； 2既与机器指令的结构相近，又与具体机器无关。 中间语言几种最常用的形式： 逆波兰表示、四元式表示、三元式表示、树、三地址代码表 示。 四个跳转符号的约定： 1)LJ：表示转向某标号处； 2)TJ：表示按条件真转 3)FJ：表示按条件假转 4)RJ；表示
11、无条件转 4.5.1 逆波兰表示 一、简单表达式的逆波兰式表示 1)简单表达式的表示法 （1)中缀表示法：是把双目运算符放在两个运算分量的中间的表达 式表示方法。例：(a+b)c （2)前缀表示法：把运算符放在其运算分量的前面。前缀表示法又 称为波兰表示法。例：+abc （3)后缀表示法：把运算符放在其运算分量的后面。后缀表示法又 称为逆波兰表示法。例：ab+c 三种表达式的共同特点： 1、运算符的个数不变； 2、运算分量的次序和个数保持不变； 对逆波兰表达式分析：从左到右检查表达式中的诸符号；遇到运 算分量则保存；遇到运算符时，则取其前面紧靠的两个或一个分 量进行相应的运算处理，保存其结果，
12、继续向右检查表达中的符 号，直至表达式处理完毕。 a*(-b+c) a+b*(c+d/e) -a+b*(-c+d) a+b*c+d 设E是一般表达式，其逆波兰式定义如下： 一般表达式 逆波兰式 E(常数、变量) E (E) E的逆波兰式 E(1) op E(2)(二元运算) E(1) 的逆波兰式E(2)的逆波兰式 op op E(一元运算) E的逆波兰式op 2)逆波兰式表示法的优点 l无括号，形式简单 l运算符的顺序与运算的次序完全相同。 二、语句的逆波兰式表示法 逆波兰式是一种后缀表示法，即运算符在运算对象的后面。 把这种方法推广到程序设计语言的其它一些语法成分。 主要包括四种情况： 1、
13、赋值语句， 2、转向语句， 3、条件语句， 4、循环语句。 1)赋值语句的逆波兰表示： 赋值语句的语法规则：左部:=表达式 逆波兰式： 左部表达式 := 例：赋值语句 x:=5 逆波兰式：x5:=； x:=a*b-c/d 逆波兰式：xab*cd/-:= 2)转向语句的逆波兰式表示 转向语句：goto标号 逆波兰表示为：标号LJ 3)条件语句的逆波兰表示 无条件转移RJ表示为单目后缀运算符：序号RJ，表示 无条件转到序号处执行。 例：10 RJ：表示无条件地转到逆波兰式中序号为10的单词处 （符号处)执行。 条件转移TJ和FJ均可表示为双目后缀运算符： 布尔表达式逆波兰式序号TJ： 表示当布尔表
14、达式为真，则转到序号处 布尔表达式逆波兰式序号FJ： 表示当布尔表达式为假，则转到序号处 条件语句： if 布尔表达式then 语句1else 语句2的逆波兰式： 布尔表达式逆波兰式 序号1FJ 语句1的逆波兰式 序号2RJ 语句2的逆波兰式 序号1为语句2的逆波兰式的第一个符号的序号 序号2为语句2的逆波兰式后面的第一个符号的序号，实 际上对应着条件语句逆波兰式后面的逆波兰表示式的第一个符号 的序号。 如果采用TJ的方式则为： 布尔表达式逆波兰式序号1TJ语句2的逆波兰式 序号2RJ语句1的逆波兰式 序号1为语句1的逆波兰式的第一个符号； 序号2为条件语 句逆波兰式后的第一个符号的序号。 例
15、如：有条件语句 if ab then x:=a+b else x:=a-b 逆波兰表示式： a b 13 FJ x a b + := 18 RJ x a b - := 序号： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1a b i+j then begin k:=k-1; goto 10 end else k:=i*i j * j ; i:=0 ; j:=0 End 4 )循环语句的逆波兰表示 对于所有循环语句，我们都可以把它改造为条件语句和转向语 句的组合。 例：for i:=a to b do S:=S+i 可以改写为： i:=a; 10: if i=b then begin S:=S+i; i:=i+1; goto 10 end 作一个100次的循环： i:=1; 10: if i=100 then be
