《属性文法ppt课件.ppt》由会员分享，可在线阅读，更多相关《属性文法ppt课件.ppt（62页珍藏版）》请在金锄头文库上搜索。
1、第六讲属性文法和语法制导翻译 属性文法基于属性文法的处理属性的计算S属性文法的自下而上计算L属性文法的自上而下计算 1 1 属性文法 属性文法是在上下文无关文法的基础上为每个文法符号 终结符或非终结符 配备若干个相关的 值 称为属性 这些属性代表与文法符号相关的信息 例如它的类型 值 代码序列 符号表内容等等 属性和变量一样 可以进行计算和传递 属性一般分为两类 综合属性 用于 自下而上 传递信息 继承属性 用于 自上而下 传递信息 属性加工的过程即是语义处理的过程 对于文法的每一个产生式都配备了一组属性的计算规则 称为语义规则 2 属性的类型 综合属性 在语法树中 一个结点的综合属性的值由其
2、子结点的属性值确定 通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 仅仅使用综合属性的属性文法称S 属性文法 继承属性 在语法树中 一个结点的继承属性由此结点的父结点和 或兄弟结点的某些属性确定 可用继承属性来表示程序语言结构中的上下文依赖关系 3 注意 1 终结符只有综合属性 由词法分析器提供 2 非终结符既可以有综合属性也可以有继承属性 文法开始符号的所有继承属性作为属性计算前的初始值 出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则 一般地 属性计算规则中只能使用相应产生式的文法符号的属性 这有利于产生式范围内 封装 属性的依赖性 出现在产生
3、式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算 它们由其它产生式的属性规则计算或由属性计算器的参数提供 4 在一个属性文法中 对应于每个产生式A 都有一套与之相关联的语义规则 每条语义规则的形式为 b f c1 c2 ck 其中f是一个函数 并且满足下面两种情况之一 1 b是A的一个综合属性并且c1 c2 ck是产生式右边文法符号的属性 2 b是产生式右边某个文法符号的一个继承属性并且c1 c2 ck是A或产生式右边任何文法符号的属性 对这两种情况都称为属性b依赖于属性c1 c2 ck 5 语义规则 描述属性计算 静态语义检查 符号表操作 代码生成等 语义规
4、则可能产生副作用 如产生代码 也可能不是变元的严格函数 即函数中还有其它没有列出的自变量如变量地址等 比如说某个规则可能给出可用的下一个数据单元的地址 这样的语义规则通常写成过程调用或过程段 6 下表是一个台式计算器程序的属性文法 该计算器读入一个算术表达式 计算并打印它的值 每个输入行以n作为结束 在这些语义规则中 一个整数综合属性val把每个非终结符E T F联系起来 记号digit具有综合属性lexval 其值由词法分析器提供 7 句子3 5 4n的带注释的语法树 这是个带综合属性文法的例子 下面再来看一个继承属性的例子 8 变量声明语句中 通过继承属性把类型信息传递给每个标识符 问题
5、给出句子reala b c的带注释的语法树 9 10 2 基于属性文法的处理方法 对单词符号串进行语法分析 构造语法分析树 然后根据需要遍历语法树 并在语法树的各结点处按语义规则进行计算 输入串 语法树 依赖图 按次序计算语义规则这种由源程序的语法结构所驱动的处理办法就是语法制导翻译 语义规则的计算可能产生代码 在符号表中存放信息 给出错误信息或执行任何其它动作 对输入串的翻译 根据语义规则进行计算得出结果 11 依赖图 语法树中结点属性之间的相互依赖关系用依赖图描述为每一个包含过程调用的语义规则引入一个虚综合属性b 这样把每一个语义规则都写成b f c1 c2 ck 的形式 依赖图是一个有向
6、图 为每一个属性设置一个结点 如果属性b依赖属性c 则从属性c的结点有一条有向边连到属性b的结点 12 依赖图的画法 例 属性A a f X x Y y 对应于产生式A XY的语义规则 在依赖图中有三个相关结点 A a X x Y y 由于A a依赖于X x Y y 所以有两条有向边从X x到A a 从Y y连到A a 如果与产生式A XY对应的语义规则还有 X i g A a Y y 图中再增加两条有向边 从A a连到X i 从Y y连到X i 因为X i依赖于A a和Y y 13 例 依赖图 当下面的产生式应用于语法树时 我们就像下图所示的那样把有向边加到依赖图中 产生式语义规则E E1
7、E2E val E1 val E2 val 14 例 依赖图 因为产生式D TL的语义规则L in T type 从代表T type的结点4有一条边连到代表L in的结点5 因为产生式L L1 id有语义规则L1 in L in 可知L1 in依赖于L in 所以有两条向下的边分别进入结点7和9 每一个与L产生式有关的语义规则addtype id entry L in 都产生一个虚属性 结点6 8和10都是为这些虚属性构造的 15 良定义文法和属性的计算次序 定义 属性之间不存在循环依赖关系的属性文法 一个有向非循环图的拓扑序是图中结点的任何顺序m1 m2 mk 使得边必须是从序列中前面的结点
8、指向后面的结点 也就是说 如果mi mj是mi到mj的一条边 那么在序列中mi必须出现在mj之前 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 属性文法说明的翻译是很精确的 基础文法用于构造输入符号串的语法分析树 在此基础之上可以建立依赖图 按照图的某一种拓扑排序 就可以根据语义规则进行翻译 16 树遍历的属性计算方法 以某种次序遍历语法树 直至计算出所有的属性 最常用的遍历方法是深度优先 从左到右的遍历方法 这种方法最简单 适应面最广 算法略 缺点 必须在语法树建立之后才能使用效率不高 对每个非终结符号 多次重复计算所有能够计算的继承属性最后计算所有能够计算的综合属
9、性 17 一遍扫描的处理方法 在语法分析的同时计算属性值 因而无需构造实际的语法树 语法制导翻译法就是为文法中每个产生式配上一组语义规则 并且 在语法分析的同时执行这些语义规则 计算语义规则 完成有关语义分析和代码生成动作的时机 自上而下分析中一个产生式匹配输入串成功时 自下而上分析中一个产生式被用于进行归约时 18 抽象语法树 在语法分析期间完成翻译工作可大幅提高编译的时空效率 但也存在一些问题 适合于语法分析的文法可能并不反映语言成分的自然层次结构 特定的语法分析方法也可能限制了语法分析树的节点考察顺序因此 现代编译器通用的做法是 通过语法分析构造语法树 再对语法树进行遍历完成属性的计算
10、也就是使用中间表示 IntermediateRepresentation 把翻译从语法分析中分离出来 这样做可以使编译器更好地模块化 也方便了移植和优化 19 为每个运算分量或运算符号都建立一个结点来为子表达式建立子树 运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根 抽象语法树中的每一个结点可以由包含几个域的记录来实现 在一个运算符号对应的结点中 一个域标识运算符号 其它域包含指向运算分量的结点的指针 通常 运算符号叫做这个结点的标号 进行翻译时 抽象语法树中的结点可能会用附加域来存放结点的属性值 或指向属性的指针 表达式3 5 4的抽象语法树 抽象语法树 A
11、ST 语法分析树的压缩形式 叶子结点 终结符的综合属性 文法开始符号的继承属性 以下以表达式为例 说明如何构造AST 20 综合属性nptr表示函数调用返回的指针 21 a 5 b的语法树的构造 22 a 5 b的语法树的构造 23 a 5 b的语法树的构造 24 a 5 b的语法树的构造 25 a 5 b的语法树的构造 26 a 5 b的语法树的构造 27 a 5 b的语法树的构造 28 a 5 b的语法树的构造 29 a 5 b的语法树的构造 30 3 S 属性文法的自下而上计算 S 属性文法 只含有综合属性的属性文法 在自底向上的分析法如LR分析法中 我们使用一个栈来存放已经分析过的子树
12、的信息 现在可以在分析栈中使用一个附加的域来存放综合属性值 如果一个属性文法是S 属性文法 那么在计算每个语义规则时 分析栈中栈顶处正好就是计算语义规则时需要用到的其它属性值 31 假设图中的栈是由一对数组state和val来实现的 每一个state元素都是一个指向LR 1 分析表的指针 或索引 注意 文法符号隐含在state中而不需要存储在栈中 然而 如果像前面LR分析时的那样把文法符号存入栈中时 那么当第i个state对应的符号为A时 val i 中就存放语法树中与结点A对应的属性值 设当前栈顶由指针top指示 我们假设综合属性是刚好在每次归约前计算的 假设语义规则A a f X x Y
13、y Z z 是对应于产生式A XYZ的 在把XYZ归约成A以前 属性Z z的值放在val top 中 Y y的值放在val top 1 中 X x的值放在val top 2 中 如果一个符号没有综合属性 那么数组val中相应的元素就不定义 归约后 top值减2 A的状态存放在state top 中 也就是X的位置 综合属性A a的值存放在val top 中 Stateval XX xYY yZ 栈顶 Z z val X xY y栈顶 Z z 简化为 32 边分析边翻译的方式能否用于继承属性 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左
14、向右流动 那么就有可能在分析的同时完成属性计算 33 4 L 属性文法和自顶向下翻译 L 属性文法 如果对于每个产生式A X1X2 Xn的每个语义规则中 每个属性或者是综合属性 或者是Xj 1 j n 的一个继承属性且这个继承属性仅依赖于 1 产生式Xj的左边符号X1 X2 Xj 1的属性 2 A的继承属性 L 属性文法也就是 左属性 文法 计算每一个继承属性时不能引用右边符号的属性 继承属性和综合属性 由此定义可知 S属性文法一定是L属性文法 34 翻译模式 属性文法可以看成是关于语言翻译的高级规范说明 其中隐去实现细节 使用户从明确说明翻译顺序的工作中解脱出来 下面我们讨论一种适合语法制导
15、翻译的另一种描述形式 称为翻译模式 翻译模式给出了使用语义规则进行计算的次序 这样就可以把某些实现细节表示出来 在翻译模式中 和文法符号相关的属性和语义规则 这里我们也称语义动作 用花括号 括起来 插入到产生式右部的合适位置上 这样翻译模式给出了使用语义规则进行计算的顺序 35 对继承属性出现位置的限制 为了计算出继承属性 翻译模式必须满足三个条件 1 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 2 一个动作不能引用这个动作右边符号的综合属性 3 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算 计算这种属性的动作通常可放在产生式右端的末尾 36 不满
16、足条件的例子 S A1A2 A1 in 1 A2 in 2 A a print A in 应该改为 S A1 in 1 A1 A2 in 2 A2A a print A in 通常写成 S A1 in 1 A1 A2 in 2 A2A a print A in 37 自顶向下翻译 在第四讲我们知道 为了构造不带回溯的自顶向下语法分析 必须消除文法中的左递归 现在我们把前面消除左递归的方法加以扩充 当消除一个翻译模式的基本语法的左递归时同时考虑属性 这种方法适合带综合属性的翻译模式 这样许多文法可以使用自顶向下分析来实现 38 消除左递归 推广转换左递规翻译模式的方法 以便进行自顶向下分析 假设我们有下面的翻译模式 A A1Y A a g A1 a Y y A X A a f X x 其每个文法符号都有一个综合属性 用小写字母表示 g和f是任意函数 利用第四章消除左递归的算法 可将其转换成下面文法 A XRR YR 39 翻译模式变为 A X R i f X x R A a R s R Y R1 i g R i Y y R1 R s R1 s R R s R i 经过转换的翻译模式 使用
