第6章 语法制导翻译和语义分析.ppt

编译原理,第6章 语法制导翻译和语义分析,安庆师范学院计算机与信息学院,本章目标,定义相关概念：属性、属性文法、S——属性文法和L——属性文法 解释基于属性文法的语法制导翻译技术的基本思想 介绍常见的中间代码的描述方法 介绍不同语法结构的语法制导翻译技术,教学内容,教学内容,6.1 属性文法与语法制导翻译,1、 属性及属性文法,（1）文法的属性 属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征 随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号X，该X可以是终结符或非终结符根据语义处理的需要，在用产生式A→αXβ进行归约或推导时，应能准确而恰当地表达文法符号X在归约或推导时的不同特征 例如，判断变量X的类型是否匹配，要用X的数据类型来描述；判断变量X是否存在，要用X的存储位置来描述；而对X的运算，则要用X的值来描述；因此，语义分析阶段引入X的属性，如X.type、X.place、X.val等来分别描述变量X的类型、存储位置以及值等不同的特征1、 属性及属性文法,（2）属性文法 属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了属性的文法，它将文法符号的语义以“属性”的形式附加到各个文法的符号上(如上述与变量X相关联的属性X.type、X.place和X.val等)，再根据产生式所包含的含义，给出每个文法符号属性的求值规则，从而形成一种带有语义属性的上下文无关文法，即属性文法。

属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作 属性文法=上下文无关文法+属性+语义规则,2、 综合属性与继承属性,（1）属性分类 属性文法中的属性可分为继承属性与综合属性两类 继承属性 用于“自上而下”地传递信息 综合属性 用于“自下而上”地传递信息 （2）语义规则 属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程对于文法的每一个产生式都配备了一组属性的计算规则，称为语义规则2、 综合属性与继承属性,（3）语义规则的表示 在一个属性文法中，对应于每个产生式A→α 都有一套与之相关联的语义规则，每条规则形式为 其中f是一个函数，而且或者 ①b是A的一个综合属性，并且c1,c2,…,ck是α中文法符号的属性；或者 ②b是α中某个文法符号的一个继承属性 并且c1,c2,….,ck是A或α中任何文法符号的属性 在上述两种情况下，我们都说属性b依赖于属性c1,c2,…,ck2、 综合属性与继承属性,（3）语义规则的表示 【注意】 ①终结符号只有综合属性，由词法分析器提供 ②非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

③对出现在产生式右边的继承属性和产生式左边的综合属性都必须提供一个计算规则 ④属性计算规则中只能使用相应产生式的文法符号的属性，这有利于在产生式范围内“封装”属性的依赖性然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供3、 S—属性文法与L—属性文法,（1）S—属性文法 仅仅使用综合属性的属性文法，称为S—属性文法 （2）L—属性文法 一个属性文法称为L—属性文法，如果对于每个产生式A→x1x2,…xn，其每个语义规则中的每个属性或者是综合属性，或者是xj(1≤j≤n)的一个继承属性且这个继承属性仅依赖于： ①产生式中xj的左边符号x1,x2,…xj-1的属性； ②A的继承属性 L—属性文法的最大特点是产生式右部符号的继承属性不依赖于该符号右边符号的任何属性3、 S—属性文法与L—属性文法,【注意】 ①S—属性文法一定是L-属性文法 ②S—属性文法适合于一遍扫描的自下而上分析 ③L—属性文法可用于一遍扫描的自上而下分析,4、 基于属性文法的语法制导翻译,（1）语法制导翻译 所谓语法制导翻译就是指为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。

语法制导翻译法的基本思想是对文法中的每个产生式都附加上一个语义动作（或语义子程序），在执行语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式对应的语义动作（或语义子程序）这些语义动作不仅指明了该产生式所产生符号串的意义，而且还根据这种意义规定了对应的加工动作（如查填各类表格、更新变量的值、提示出错信息、生成中间代码等），从而完成预定的翻译工作4、 基于属性文法的语法制导翻译,（2）举例 【例6.1】描述简单算术表达式求值的属性文法val：综合属性，表示E、T、F的值,lexval：综合属性，由词法分析器提供,print：打印由E产生的表达式值,4、 基于属性文法的语法制导翻译,.lexval=3,.lexval=5,.lexval=4,.val=3,.val=3,.val=5,.val=15,.val=15,.val=4,.val=4,.val=19,计算表达式3*5+4的值,print(19),4、 基于属性文法的语法制导翻译,【例6.2】描述说明语句中变量类型信息的属性文法type：综合属性，其值由说明中的关键字确定,in：继承属性，,addtype：把每个标识的类型信息登记到符号表中相关项（id.entry）中,4、 基于属性文法的语法制导翻译,int id1,id2,.type=int,.in=int,.in=int,addtype(id1.entry,int),addtype(id2.entry,int),,,,,,6.2 语义分析和中间代码的产生,1、 语义分析的任务,语义分析与处理的主要任务： （1）审查每个语法结构的静态语义，即验证语法结构合法的源程序是否真正有意义。

有时把这个工作称为静态语义分析或静态语义审查 （2）若静态语义正确，则要执行语义翻译，即用另一种语言形式（比源语言更接近于目标语言的一种中间代码或直接用目标代码）来描述这种语义2、 常见的中间代码形式,（1）中间代码 源程序的一种内部表达，不依赖于目标机的结构，易于机械生成目标代码的中间表示，称为中间代码 （2）为什么要此阶段 使用中间代码主要有以下几点好处： ①使逻辑结构清楚 ②有利于不同目标机上实现同一种语言 ③有利于进行与机器无关的优化 ④这些内部形式也能用于解释,2、 常见的中间代码形式,（3）常见的中间代码形式 ①后缀式（逆波兰表示式） ②图表示法 抽象语法树 DAG图 ③三地址代码 四元式 三元式 间接三元式,2、 常见的中间代码形式,（4）后缀式（逆波兰式） ①定义 后缀式表示法（逆波兰表示法），由波兰逻辑学家卢卡西维奇（Lukasiewicz）发明，它把运算量（操作数）写在前面，把运算符写在后面（后缀）的一种表达式表示方法其归纳定义如下： 如果E是一个变量或常数，则E的后缀式是E自身 如果E是E1 op E2 形式的表达式，op是二元操作符，则E的后缀式为E1´E2´op，其中E1´，E2´分别是E1和E2的后缀式。

若E是（E1）形式的表达式，则E的后缀式就是E1的后缀式2、 常见的中间代码形式,（4）后缀式（逆波兰式） ②举例,2、 常见的中间代码形式,（4）后缀式（逆波兰式） ③后缀式的计算机处理 后缀式的最大优点是易于计算机处理，其处理过程如下： 利用一个栈，从左至右扫描逆波兰式，若当前符号是运算对象则进栈，若当前符号是运算符（假定该运算符号是k元运算符），则将栈顶k个元素依次弹出，同时进行k元运算，并将运算结果进栈，表达式处理完毕时，最后的结果留在栈顶2、 常见的中间代码形式,（5）图表示法 ①抽象语法树 在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符抽象语法树不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的层次结构 例如，表达式x=a-b*c的语法树和抽象语法树如下图所示：,S→V=E V→x E→E-E|E*E|a|b|c,2、 常见的中间代码形式,（5）图表示法 ②DAG图（Directed Acyclic Graph，有向无环图） 对表达式的每个子表达式，DAG都有一个结点，一个内部结点代表一个操作符，它的孩子代表操作数，在一个DAG中代表公共子表达式的结点具有多个父结点。

而在抽象语法树中公共子表达式被表示为重复的子树 例如，表达式a+a*(b-c)+(b-c)*d的DAG图和抽象语法树如下图所示：,2、 常见的中间代码形式,（6）三地址代码 三地址代码可以看成是抽象语法树或ＤＡＧ的一种线性表示 ①三地址代码的形式 三地址代码语句的一般形式为 x=y op z 其中，x、y和z为名字、常量或编译时产生的临时变量，op为运算符三地址代码的每条语句通常包含三个地址，两个用来存放运算对象，一个用来存放运算结果 实际中用户定义的名字由指向符号表中该名字项的指针所取代由于三地址语句只含一个运算符，因此多个运算符组成的表达式需用三地址语句序列来表示2、 常见的中间代码形式,（6）三地址代码 例如，表达式x+y*z的三地址代码为： t1=y*z t2= x+t1 ②三地址语句的种类 三地址语句类似于汇编代码，它可以有符号标号和各种控制流语句常用的三地址语句有以下几种： x=y op z，其中op为二目算术或逻辑运算符 x=op y，其中op为一目运算符，如一目减uminus、逻辑否定not、移位运算符、将定点数转换成浮点数的类型转换符2、 常见的中间代码形式,（6）三地址代码 赋值语句：x=y 无条件转移语句：goto L 条件转移语句：if x relop y goto L ，if a goto L 过程调用语句param X和call P,n及过程返回语句return y 变址赋值语句：x=y[i]，x[i]=y 地址和指针赋值语句：x=&y，x=*y，*x=y,2、 常见的中间代码形式,（6）三地址代码 ③三地址代码的具体实现 编译程序中，三地址代码的具体实现通常有三种表示方法：四元式、三元式 和 间接三元式。

四元式 四元式是具有四个域的记录结构，即 (op，arg1，arg2，result) 其中，op为运算符，arg1、arg2及result为指针，它们可指向有关名字在符号表中的登记项或临时变量（也可为空）2、 常见的中间代码形式,（6）三地址代码 常用的三地址语句与相应四元式对应如下：,relop为：、=、、=、!=、==,2、 常见的中间代码形式,（6）三地址代码 例如，赋值语句a=b*(c+d)的四元式代码为： ① (+,c,d,t1) ② (*,b,t1,t2) ③ (:=,t2,_,a) 约定：一个运算量的算符使用arg1 此外，若op是一个算术或逻辑运算符，则result为新引进的临时变量，用来存放运算结果可见，四元式出现的顺序与表达式计值的顺序一致，四元式之间的联系通过临时变量实现2、 常见的中间代码形式,（6）三地址代码 三元式 三元式是具有三个域的记录结构，即 (op，arg1，arg2) 其中，op为运算符，arg1、arg2既可指向有关名字在符号表中的登记项或临时变量，也可指向三元式表中的某个三元式 例如，表达式a=(b+c)*(b+c)的三元式代码为： ① (+,b,c) ② (+,b,c) ③ (*,①,②) ④ (:=,a,③) 由上例可知，三元式出现的先后顺序和表达式各部分的计值顺序一致。

2、 常见的中间代码形式,（6）三地址代码 间接三元式 在三元式代码表的基础上另设一张表，该表按运算的次序列出相应三元式在三元式表中的位置，这张表称为间接码表 三元式表只记录不同的三元式，间接码表表示由这些语句组成的运算次序 例如，表达式a=(b+c)*(b+c)的三元式表和间接码表为： 三。