编译原理语义1(属性文法和语法制导翻译).pptx

第 9 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第四章 语义分析和中间代码生成,4.1 语义分析概述 4.2 属性文法 4.3 几种常见的中间语言 4.4 表达式及赋值语句的翻译 4.5 控制语句的翻译 4.6 数组元素的翻译 4.7 过程或函数调用语句的翻译 4.8 说明语句的翻译 4.9 递归下降语法制导翻译方法简介,第四章语义分析和中间代码生成 4.1 语义分析概述 4.2 属性文法 4.3 几种常见的中间语言 重点掌握 语法翻译制导思想 逆波兰表示法 三地址代码（四元式、三元式）,本讲目标,4.1 语义分析概述,4.1.1 语义分析的内容 语义分析包括两部分： 1. 静态语义审查（编译阶段） (1)类型检查：检查运算的合法性和运算分量类型的相容性，必要时进行类型转换。 (2)控制流检查：保证控制语句有合法的转向点。 (3)一致性检查：变量重复声明、case语句相同入口等。 2. 生成目标代码或中间代码 生成中间代码的好处： (1) 使得编译结构在逻辑上更为简单明确 (2) 容易实现目标代码的优化,4.1 语义分析概述,4.1.1 如何实现语义分析？ 语义分析不像词法分析和语法分析那样，分别可以用正规文法和上下文无关文法形式化地进行描述 语义分析的描述工具：属性文法 语义分析的实现方式：语法制导翻译 其中，属性文法是语法制导翻译的基础,4.1 语义分析概述,4.1.2 语法制导翻译方法（原理） 语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序。 语义子程序的作用：描述一个产生式所对应的翻译工作。 如：改变变量的值，查、填符号表、发现语义错误、 产生中间代码等。 所以，在语法分析过程中，当每一个产生式获得匹配（对应自顶向下推导）或成功规约（对应于自底向上）时，此产生式相应的语义子程序进入工作，最终完成翻译工作。 那么，语法制导翻译分为自顶向下和自底向上两种。,4.1 语义分析概述,4.1.2 语法制导翻译方法（实例） 假定有一个自底向上的LR分析器，原始功能是规约输入串。如：“#7+9*5#”。现在将它的功能加以扩大，使其在规约输入串的同时调用语义子程序计算输入串的语义。,产生式 语义动作 (0) SE print valTOP (1) EE(1) + E(2) valTOP= valTOP +valTOP+2 (2) EE(1)*E(2) valTOP=valTOP* valTOP+2 (3) E(E(1) valTOP=valTOP+1 (4) Ei valTOP=lexval (注：lexval为i的整型内部值),图4-1 扩充后的LR分析栈,注意语义栈的功能：完成语义动作后，保存语义值,状态栈、符号栈和 语义栈三者同步变化,2. 在用某一规则进行归约，栈顶保存文法符号之后，调用相应语义子程序完成语义动作，将改变的语义值保存在语义栈中,表4.1 表达式“7 + 9*5#”的语义分析和计值过程,产生式 语义动作 (0) SE print valTOP (1) EE(1) + E(2) valTOP= valTOP +valTOP+2 (2) EE(1)*E(2) valTOP=valTOP* valTOP+2 (3) E(E(1) valTOP=valTOP+1 (4) Ei valTOP=lexval (注：lexval为i的整型内部值) 规约时，先对产生式右部的语义值进行综合，其结果作为左部符号的语义值保存在语义栈中。,4.2 属性文法,4.2.1 文法的属性 属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征 对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号:X，该X可以是终结符或非终结符 文法符号X的属性一般包括三种： X.type: X的类型 X.place: X的存储位置 X.val: X的值,4.2.1 文法的属性 文法符号的属性按照语法分析方向（推导还是规约）分为两种：继承属性和综合属性 1. 继承属性：用于“自顶向下”传递信息，继承属性由相应语法树中结点的父结点属性计算得到，即沿语法树向下传递，由根结点到分枝(子)结点，它反映了对上下文依赖的特性。 2. 综合属性：用于“自底向上”传递信息，综合属性由相应语法分析树中结点的分枝结点(即子结点)属性计算得到，其传递方向与继承属性相反，即沿语法分析树向上传递，从分枝结点到根结点。,4.2 属性文法,4.2 属性文法 属性文法是经过扩展了的常规文法，适用于定义语义。即在语言的文法中增加了属性信息： 1. 将文法符号的语义以“属性”的形式附加到各个文法符号上； 2.根据产生式所包含的含义，给出每个文法符号属性的求值规则。 所以，从而形成一种带有语义属性的上下文无关文法，即属性文法。属性有助于更详细地指定文法中的代码生成动作。,4.2 属性文法,例如，简单算术表达式求值的属性文法如下： 产生式 语义规则 (1) SE print(E.val) (2) EE(1)+T E.val = E(1).val+T.val (3) ET E.val = T.val (4) TT(1)*F T.val = T(1).val*F.val (5) TT(1) T.val = T(1).val (6) F(E) F.val = E.val (7) Fi F.val = i.lexval,lexval是词法分析送来的整型内部值,4.2 属性文法（综合属性）,表达式左侧的非终结符语义值来自于右侧语义的计算， 因此称为综合属性,再举一例说明属性文法。一简单变量类型说明的文法GD如下： GD: Dint L | float L LL, id | id,4.2 属性文法（继承属性）,4.2 属性文法（继承属性）,属性L.in被确定后将随语法树的逐步生成而传递到下边的有关结点使用，这种结点属性称为继承属性,int a,b的分析过程,4.3.1 抽象语法树 抽象语法树是一种较为流行的中间语言表示形式。 每一个叶子结点表述运算对象，其它内部结点表示运算符。 抽象语法树由语法树去掉一切不必要的信息得来。,4.3 几种常见的中间语言,图4-4 x = ab*c的语法树 (a) 抽象语法树；(b) 普通语法树图,4.3.1 抽象语法树 问题1：什么是抽象语法？ 由于语法规则中包含的某些符号可能起标点符号作用也可能起注释作用: (1)赋值语句语法规则： S V = e 其中的赋值号“=”仅起标点符号作用，其目的是把V与e分开； (2)条件语句语法规则： Sif(e)S1; else S2 其中的if和else起注释作用，而“；”仅起标点符号作用。 在把语法规则中本质部分抽象出来而将非本质部分去掉后， 便得到抽象语法规则,4.3 几种常见的中间语言,V e,e S1 S2,4.3.1 抽象语法树 问题2：如何将表达式的普通语法树化简为抽象语法树？ 解答：化简过程为： (1)去掉与单非产生式相关的子树，上提终结符结点； (2)如果子树中有运算符结点，上提运算符取代父节点； (3)去掉括号，上提运算符，让其取代父节点。 课堂练习：对于文法GS,构造i*(i+i)的语法树并化简。,4.3 几种常见的中间语言,GE:E E+T | T T T*F | F F (E) | i （3.1）,4.3.2 1.表达式的逆波兰表示法 逆波兰表示法是波兰逻辑学家卢卡西维奇(Lukasiewicz)发明的一种表示表达式的方法，又称后缀表示法。 例如： a+b 表示成 ab+ a*(b+c)表示成 abc+* (a+b)*(a-c)-d 表示成 ab+ac-*d- 优点：1.表达式中无括号 2.运算不需要考虑优先级，扫描一遍即可完成运算 特点：1.标识符出现的顺序和原有顺序相同； 2.运算符是按照实际计算顺序出现的； 3.运算符紧跟在运算对象的后面。,4.3 几种常见的中间语言,思考：逆波兰式如何计算？,4.3.2 2.程序语句的逆波兰表示法 由于控制语句需要跳转，因此定义如下转移操作： (1) BL：转向某标号； (2) BT：条件为真时转移； (3) BF：条件为假时转移； (4) BR：无条件转移。 程序语句的逆波兰表示主要掌握如下几类： (1) 赋值语句； (2) GOTO语句； (3) 条件语句； (4) 循环语句。,4.3 几种常见的中间语言,(1) 赋值语句 “ = ” 的逆波兰表示为 = 例如，赋值语句“x = a + b * c”可按逆波兰式写为 “xabc*+=”。 (2) GOTO语句。转向语句“GOTO”的逆波兰表示为 BL 其中，“BL”为单目后缀运算符，“”则为BL的一个运算分量。 例如，转向语句 GOTO 10，逆波兰表示为“10BL”，意为无条件转向标号为10 的语句处。,4.3 几种常见的中间语言,(3) 条件语句 BR表示无条件转移单目后缀运算符，例如，“BR”表示无条件转移到“”处，这里的顺序号是BR的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号(即第几个单词) BT和BF表示按条件转移的两个双目后缀运算符 例如： BT BF 分别表示当e为真或假时转移到顺序号处。其中，布尔表达式e的逆波兰式和顺序号是两个特殊的运算分量。,4.3 几种常见的中间语言,此逆波兰式也可写在一行上，即： mn13BFki1+=18BRki1 =,例如，条件语句if(mn) k=i+1；else k=i1的逆波兰式表示为(1)(18)为单词编号),实例：条件语句的逆波兰表示,(1) m n ,(4) 13 BF,(6) k i 1 + =,(11) 18 BR,(13) k i 1 =,(18) if语句的后继语句,(4) 循环语句 for循环语句为for(i=m；i=n；i+)S 其中，i为循环控制变量，m为初值，n为终值，S为循环体； 循环语句不能直接用逆波兰表示，因而将其展开为等价的条件语句后再用逆波兰表示 例如： i=m； 10：if(i=n) S； i=i+1； goto 10 ,4.3 几种常见的中间语言,一起来完成逆波兰式翻译,4.3.3 三地址代码 三地址代码语句的一般形式： x = y op z 其中，x、y和z为名字、常量或编译时产生的临时变量； op为运算符，如定点运算符、浮点运算符和逻辑运算符等。 三地址代码的语句中通常包含三个地址，两个用来存放操作数（或操作对象），一个用来存放运算结果。如果一个表达式中有多于三个的操作对象，该表达式可以用若干个三地址代码来表示。 例如，表达式x+y*z的三地址代码为,4.3 几种常见的中间语言,t1 = y*z t2 = x + t1,4.3.3 三地址代码 三地址代码语句的具体实现： 在编译程序中，三地址代码语言的具体实现通常有三种表示方法：四元式、三元式和间接三元式。 (1)四元式 四元式是具有四个域的记录(即结构体)结构，这四个域为 (op, arg1, arg2, result) 其中，op为运算符；arg1、arg2及result为指针，它们可指向有关名字在符号表中的登记项或一临时变量(个别指针也可空缺)。,4.3 几种常见的中间语言,四元式还有一个数字标记，用来记录当前四元式的编号。在跳转时使用。,x=y op z 对应(op, y, z, x) x=y 对应(uminus, y, _, x) x=y 对应(=, y, _, x) par x1 对应(par, x1, _, _ ) call P 对应(call, _, _, P) goto L 对应(j, _, _, L) if x rop y goto L 对应(jrop, x, y, L),常用的三地址语句与相应的四元式对应如下：,4.3 几种常见的中间语言,关于四元式： 约定： (1)凡只需一个运算量的算符一律使用arg1 ; (2)如果op是一个算术或逻辑运算符，则result总是一个新引进的临时变量，它用来存放运算结果。 例如，赋值语句a=b*(c+d)相应的四元式代码为,4.3 几种常见的中间语言, (+, c, d, t1) (*, b, t1, t2) (=, t2, _, a),由上例也可看出，四元式出现的顺序与表达式计值的顺序是一致的，四元式之间的联系是通过临时变量实现的,4.3 几种常见的中间语言,4.3.3 三地址代码 (2)三元式 例如，相应于赋值语句a = (b+c) * (b+c)的三元式代码为： (+, b, c) (+, b, c) (*, , ) (=, a, ) 三元式的顺序号必须有，它有两个作用： 1.代表运算次序； 2.保存三元式运算结果。,4.3 几种常见的中间语言,4.3.3 三地址代码 三元式相对于四元式的优点： (1)三元式无需生成临时变量 (2)三元式占用的存储空间较少 三元式相对于四元式的缺点： 使用三元式不利于代码优化，因为改变一个三元式编号或胜省略一个三元式，需要修改大量的三元式序号和内容。,4.3 几种常见的中间语言,4.3.3 三地址代码 (3)间接三元式 间接三元式的提出是为了优化三元式代码： 作为中间代码，通常不直接使用三元式表示，而是另设一张间接码表，也称执行表。