属性文法ppt课件.ppt

第六讲属性文法和语法制导翻译 属性文法基于属性文法的处理属性的计算S属性文法的自下而上计算L属性文法的自上而下计算 1 1 属性文法 属性文法是在上下文无关文法的基础上为每个文法符号 终结符或非终结符 配备若干个相关的 值 称为属性 这些属性代表与文法符号相关的信息 例如它的类型 值 代码序列 符号表内容等等 属性和变量一样 可以进行计算和传递 属性一般分为两类 综合属性 用于 自下而上 传递信息 继承属性 用于 自上而下 传递信息 属性加工的过程即是语义处理的过程 对于文法的每一个产生式都配备了一组属性的计算规则 称为语义规则 2 属性的类型 综合属性 在语法树中 一个结点的综合属性的值由其子结点的属性值确定 通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 仅仅使用综合属性的属性文法称S 属性文法 继承属性 在语法树中 一个结点的继承属性由此结点的父结点和 或兄弟结点的某些属性确定 可用继承属性来表示程序语言结构中的上下文依赖关系 3 注意 1 终结符只有综合属性 由词法分析器提供 2 非终结符既可以有综合属性也可以有继承属性 文法开始符号的所有继承属性作为属性计算前的初始值 出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则 一般地 属性计算规则中只能使用相应产生式的文法符号的属性 这有利于产生式范围内 封装 属性的依赖性 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算 它们由其它产生式的属性规则计算或由属性计算器的参数提供 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 语义规则 描述属性计算 静态语义检查 符号表操作 代码生成等 语义规则可能产生副作用 如产生代码 也可能不是变元的严格函数 即函数中还有其它没有列出的自变量如变量地址等 比如说某个规则可能给出可用的下一个数据单元的地址 这样的语义规则通常写成过程调用或过程段 6 下表是一个台式计算器程序的属性文法 该计算器读入一个算术表达式 计算并打印它的值 每个输入行以n作为结束 在这些语义规则中 一个整数综合属性val把每个非终结符E T F联系起来 记号digit具有综合属性lexval 其值由词法分析器提供 7 句子3 5 4n的带注释的语法树 这是个带综合属性文法的例子 下面再来看一个继承属性的例子 8 变量声明语句中 通过继承属性把类型信息传递给每个标识符 问题 给出句子reala b c的带注释的语法树 9 10 2 基于属性文法的处理方法 对单词符号串进行语法分析 构造语法分析树 然后根据需要遍历语法树 并在语法树的各结点处按语义规则进行计算 输入串 语法树 依赖图 按次序计算语义规则这种由源程序的语法结构所驱动的处理办法就是语法制导翻译 语义规则的计算可能产生代码 在符号表中存放信息 给出错误信息或执行任何其它动作 对输入串的翻译 根据语义规则进行计算得出结果 11 依赖图 语法树中结点属性之间的相互依赖关系用依赖图描述为每一个包含过程调用的语义规则引入一个虚综合属性b 这样把每一个语义规则都写成b f c1 c2 ck 的形式 依赖图是一个有向图 为每一个属性设置一个结点 如果属性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 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 使得边必须是从序列中前面的结点指向后面的结点 也就是说 如果mi mj是mi到mj的一条边 那么在序列中mi必须出现在mj之前 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 属性文法说明的翻译是很精确的 基础文法用于构造输入符号串的语法分析树 在此基础之上可以建立依赖图 按照图的某一种拓扑排序 就可以根据语义规则进行翻译 16 树遍历的属性计算方法 以某种次序遍历语法树 直至计算出所有的属性 最常用的遍历方法是深度优先 从左到右的遍历方法 这种方法最简单 适应面最广 算法略 缺点 必须在语法树建立之后才能使用效率不高 对每个非终结符号 多次重复计算所有能够计算的继承属性最后计算所有能够计算的综合属性 17 一遍扫描的处理方法 在语法分析的同时计算属性值 因而无需构造实际的语法树 语法制导翻译法就是为文法中每个产生式配上一组语义规则 并且 在语法分析的同时执行这些语义规则 计算语义规则 完成有关语义分析和代码生成动作的时机 自上而下分析中一个产生式匹配输入串成功时 自下而上分析中一个产生式被用于进行归约时 18 抽象语法树 在语法分析期间完成翻译工作可大幅提高编译的时空效率 但也存在一些问题 适合于语法分析的文法可能并不反映语言成分的自然层次结构 特定的语法分析方法也可能限制了语法分析树的节点考察顺序因此 现代编译器通用的做法是 通过语法分析构造语法树 再对语法树进行遍历完成属性的计算 也就是使用中间表示 IntermediateRepresentation 把翻译从语法分析中分离出来 这样做可以使编译器更好地模块化 也方便了移植和优化 19 为每个运算分量或运算符号都建立一个结点来为子表达式建立子树 运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根 抽象语法树中的每一个结点可以由包含几个域的记录来实现 在一个运算符号对应的结点中 一个域标识运算符号 其它域包含指向运算分量的结点的指针 通常 运算符号叫做这个结点的标号 进行翻译时 抽象语法树中的结点可能会用附加域来存放结点的属性值 或指向属性的指针 表达式3 5 4的抽象语法树 抽象语法树 AST 语法分析树的压缩形式 叶子结点 终结符的综合属性 文法开始符号的继承属性 以下以表达式为例 说明如何构造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分析法中 我们使用一个栈来存放已经分析过的子树的信息 现在可以在分析栈中使用一个附加的域来存放综合属性值 如果一个属性文法是S 属性文法 那么在计算每个语义规则时 分析栈中栈顶处正好就是计算语义规则时需要用到的其它属性值 31 假设图中的栈是由一对数组state和val来实现的 每一个state元素都是一个指向LR 1 分析表的指针 或索引 注意 文法符号隐含在state中而不需要存储在栈中 然而 如果像前面LR分析时的那样把文法符号存入栈中时 那么当第i个state对应的符号为A时 val i 中就存放语法树中与结点A对应的属性值 设当前栈顶由指针top指示 我们假设综合属性是刚好在每次归约前计算的 假设语义规则A a f X x Y 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 边分析边翻译的方式能否用于继承属性 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动 那么就有可能在分析的同时完成属性计算 33 4 L 属性文法和自顶向下翻译 L 属性文法 如果对于每个产生式A X1X2 Xn的每个语义规则中 每个属性或者是综合属性 或者是Xj 1 j n 的一个继承属性且这个继承属性仅依赖于 1 产生式Xj的左边符号X1 X2 Xj 1的属性 2 A的继承属性 L 属性文法也就是 左属性 文法 计算每一个继承属性时不能引用右边符号的属性 继承属性和综合属性 由此定义可知 S属性文法一定是L属性文法 34 翻译模式 属性文法可以看成是关于语言翻译的高级规范说明 其中隐去实现细节 使用户从明确说明翻译顺序的工作中解脱出来 下面我们讨论一种适合语法制导翻译的另一种描述形式 称为翻译模式 翻译模式给出了使用语义规则进行计算的次序 这样就可以把某些实现细节表示出来 在翻译模式中 和文法符号相关的属性和语义规则 这里我们也称语义动作 用花括号 括起来 插入到产生式右部的合适位置上 这样翻译模式给出了使用语义规则进行计算的顺序 35 对继承属性出现位置的限制 为了计算出继承属性 翻译模式必须满足三个条件 1 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来 2 一个动作不能引用这个动作右边符号的综合属性 3 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算 计算这种属性的动作通常可放在产生式右端的末尾 36 不满足条件的例子 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 经过转换的翻译模式 使用了R的继承属性i和综合属性s 考虑产生算术表达式的文法 它的翻译模式如何 考虑语义动作 40 求值翻译模式 使用属性val来保存计算结果E T R i T val R E val R s R T R1 i R i T val R1 R s R1 s R R s R i T E T val E val T num T val num val 41 构造语法树的翻译模式 使用属性p来保存语法子树的根结点指针E T R i T p R E p R s R T R1 i mknod R i T p R1 R s R1 s R R s R i T E T p E p T num T p mkleaf num num val 42 递归下降翻译器的构造 思想 对递归下降的语法分析器进行扩展 在适当的位置加入语义子程序 使之能够实现翻译模式 方法 为每个非终结符A构造一个函数 A的继承属性对应该函数的形式参数 其返回值为A的综合属性 函数体内 对出现在A的产生式右部的每个文法符号的每个属性都设置一个局部变量 控制流程依然由递归下降分析方法确定 43 在每个产生式对应的程序代码中 按照从左到右的次序 对于终结符 非终结符及其语义动作分别作以下工作 对于带有综合属性x的终结符X 把x的值存入为X x设置的变量中 然后产生一个匹配X的调用 并继续输入 对于每个非终结符B 产生一个右部带有函数调用的赋值语句c B b1 b2 bn 其中b1 b2 bn是为B的继承属性设置的变量 c是为B的综合属性设置的变量 对于语义动作 把动作的代码抄进语法分析器中 并把对属性的引用改为对相应变量的引用 思考 实现上述算术表达式文法的翻译模式 产生语法树 44 预测翻译器的设计 示例把预测分析器的构造方法推广到翻译方案的实现产生式R TR 的分析过程procedureR beginiflookahead thenbeginmatch T Rendelsebegin 什么也不做 endend 45 functionR i syntax tree node syntax tree node varnptr i1 s1 s syntax tree node addoplexeme char beginiflookahead thenbegin 产生式R TR addoplexeme lexval match nptr T i1 mknode addoplexme i nptr s1 R i1 s s1endelses i 产生式R returnsend R i sT nptr addoplexeme 46 5 自下而上计算继承属性 自下而上地计算L 属性 可以基于所有LL 1 文法和许多LR 1 的L 属性文法 从翻译模式中去掉嵌入在产生式中间的动作分析栈中的继承属性复写规则 能够预知属性值在栈中的存放位置模拟继承属性的计算不能预知属性值在栈中的存放位置时 通过模拟非终结符 修改翻译模式归结为2中的情形用综合属性代替继承属性改变基础文法以避免继承属性详见参考书 47 习题一 下列文法由开始符号S产生一个二进制数 令综合属性val给出该数的值 S L L LL LB BB 0 1试设计求S val的属性文法 其中 已知B的综合属性c 给出由B产生的二进位的结果值 48 方法1 使用L val L len属性 S L S val L val S L1 L2 S val L1 val L2 val 2L2 len L B L val B c L len 1 L L1B L val 2 L1 val B c L len L1 len 1 B 0 B c 0 B 1 B c 1 49 方法2 使用L lval L w属性 S L S val L lval S L1 L2 S val L1 lval L2 lval L2 w L B L lval B c L w 2 L L1B L lval 2 L1 lval B c L w 2 L1 w B 0 B c 0 B 1 B c 1 50 为下面文法写一个语法制导的定义 用S的综合属性val给出下面文法中S产生的二进制数的值 例如 输入101 101时 S val 5 625 不得修改文法 但属性使用没有限制S L R LL LB BR BR BB 0 1 习题二 51 S L RS val L val R valS LS val L valL L1BL val L1 val 2 B valL BL val B valR BR1R val R1 val 2 B val 2R BR val B val 2B 0B val 0B 1B val 1 52 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义 例如 因为 和 是左结合 a b c d 可以重写成a b c d先把表达式的括号都去掉 然后在必要的地方再加括号去掉表达式中的冗余括号 保留必要的括号 习题三 53 第一种方法S Eprint E code E E1 TifT op plusthenE code E1 code T code elseE code E1 code T code E op plusE TE code T code E op T op 54 T T1 Fif F op plus or F op times thenifT1 op plusthenT code T1 code F code elseT code T1 code F code elseifT1 op plusthenT code T1 code F codeelseT code T1 code F code T op ti