第六章 属性文法和语法制导翻译..pptVIP

第六章 属性文法和语法制导翻译 6.1 属性文法 ●属性文法 ●语义规则的一般形式 ●规定 ●语义规则所描述的工作 ● S-属性文法 （1）先画语法树，再画带注释的语法树 下面用例子来说明继承属性的使用和计算过程 属性文法如下： 例如：分析输入串 real a, b, c 的语义。 6.2 基于属性文法的处理方法 依赖图 例如 ●文法是良定义的 例6.5 画出 real id1, id2, id3 的依赖图，并进行语义翻译。 树遍历的属性计算方法 例6.6 分析输入串xyz的含义 （见P143 表6.3 ) 一遍扫描的处理方法 思考题1 对下面文法，写出将输入串转换成十进制整数的属性文法。 （1）先画1011语法树，再画带注释的语法树 思考题2 对下面文法，写出将输入串转换成十进制数的属性文法。 抽象语法树 例1 S?if B then S1 else S2 ● 语法制导翻译过程既可以基于语法树，也可以基于抽象语法树。 三个标准函数： a-4+b 对应的抽象语法树 例6.8 写一个属性文法，能建立表达式的抽象语法树 6.3 S-属性文法的自下而上计算 ● S-属性文法的翻译器可借助LR分析器来实现。 例6.10 写出输入串3*5+4n的翻译过程。 例6.10 （续） 例6.9 写一个属性文法，能由LR分析器计算出表达式的综合属性值。 6.4 L-属性文法和自上而下翻译 非L-属性文法的例子 （见P150） 例如 写一个翻译模式，将中缀表达式翻译成相应的后缀表达式。 分析一下输入串9-5+2： 属性文法： 翻译模式： ● 注意：在设计翻译模式时，必须保证当执行某个语义动作时，它引用的属性必须是有定义的。 建立翻译模式要满足的条件 下面翻译模式不合理： 改造如下： 结论 若一个属性文法是L-属性文法，则可建立满足三条件的翻译模式。 自上而下翻译 例如: 写出消除左递归后的翻译模式 （1）先画语法树，考虑自下而上的翻译过程 消除左递归后的文法: 消除左递归后的翻译模式 消除左递归后的翻译模式的一般方法 如何推出的？ 例6.11 写出消除左递归后的翻译模式 递归下降翻译器的设计 设计方法 例6.12 写出图6.17的递归下降翻译器 例6.12 写出图6.17的递归下降翻译器 思考题2 对文法：S?(L) | a L?L,S | S 解答2 对文法：S?(L) | a L?L,S | S 6.5 自下而上计算继承属性 例如：9-5+2： 例如：9-5+2： 分析栈中的继承属性 例如 ( P159 ) int p , q , r ; 模拟继承属性的计算 ● 通过加入标记非终结符可解决此问题 ● 标记非终结符也可模拟不是复写规则的语义规则 ● 下面给出一种带继承属性的自下而上的分析和翻译方法 用综合属性代替继承属性 修改后的属性文法 E T R 9 ‘9’ - T M R 5 ‘5’ ? ‘-’ + T N R 2 ‘2’ ? ‘+’ ? 后缀：9 5 – 2 + 转换后带注释的语法树 在自下而上分析器中，考虑产生式：A?XY … X.s X … … top … X.s X Y.s Y ntop 若Y的继承属性是通过复写规则Y.i=X.s定义的，则在需要Y.i值的地方就使用X.s的值 int T p.entry p top int T add L ntop q.entry q int T L , int T add L ntop top 从上节得知，只有根据文法预知属性值在栈中的位置，才能有效的在分析栈中