编译原理62基于属性文法的处理方法.ppt

第六章属性文法和语法制导翻译 6 1属性文法6 2基于属性文法的处理方法6 3S 属性文法的自下而上计算6 4L 属性文法和自顶向下翻译6 5自下而上计算继承属性 6 2基于属性文法的处理方法 6 2 1依赖图6 2 2树遍历的属性计算方法6 2 3一遍扫描的处理方法6 2 4抽象语法树 语法制导翻译法 syntax directedtranslation 由源程序的语法结构驱动翻译过程 输入串 语法树 依赖图 语义规则计算次序 图6 3语法制导翻译概观 描述一棵语法树中结点的属性之间的相互依赖关系 也可在语法分析的同时完成语义规则的计算 一遍扫描 语义规则的形式b f c1 c2 ck 可以为每一个包含过程调用的语义规则引入一个虚综合属性b 依赖图中为每一个属性设置一个结点 如果属性b依赖于属性c 则从属性c的结点有一条有向边连到属性b的结点 6 2 1依赖图 b c1 ck for语法树中每一结点ndofor结点n的文法符号的每一个属性ado为a在依赖图中建立一个结点 for语法树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b f c1 c2 ck dofori 1tokdo从ci结点到b结点构造一条有向边 依赖图的构造步骤 val val val 虚线表示语法树 实线表示依赖图 realid1 id2 id3的语法分析树的依赖图 D real T id3 L L L id2 id1 1entry 10 2entry 3entry in9 8 in7 6 in5 4type 图6 5图6 2中语法分析树的依赖图 虚结点 属性的计算次序 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序 例6 5在 图6 5的依赖图中 依赖图的一个拓扑排序可以从低序号到高序号顺序写出 用an来代表依赖图中与序号n的结点有关的属性 a4 real a5 a4 addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7 addtype id1 entry a9 6 2 2树遍历的属性计算方法 以某种次序遍历语法树 直至计算出所有属性 最常用的遍历方法是深度优先 从左到右的遍历方法 如果需要的话 可使用多次遍历 下面算法可对任何无循环的属性文法进行计算 While还有未被计算的属性doVisitNode S S是开始符号 procedureVisitNode N Node beginifN VNthen 假设它的产生式为N X1X2 Xm fori 1tomdoifXi VNthen 即Xi是非终结符 begin计算Xi的所有能够计算的继承属性 VisitNode Xi end 计算N的所有能够计算的综合属性end a 初始状态 b VisitNode S 第一次调用后 c VisitNode S 第二次调用后 d VisitNode S 第三次调用后的最终状态 初值S a 0 输入串xyz的语法树如下 例6 6 S有继承属性a 综合属性bX有继承属性c 综合属性dY有继承属性e 综合属性fZ有继承属性h 综合属性g h 0 g 1 c 1 d 2 e 0 f 0 b 0 6 2 3一遍扫描的处理方法 一遍扫描的处理方法 在语法分析的同时计算属性值 而不是语法分析构造语法树之后进行属性的计算 而且无需构造实际的语法树 如果采用一遍扫描的编译程序模型 语法制导翻译就是为文法中每个产生式配上一组语义规则 并且在语法分析的同时执行这些语义规则 一遍扫描处理方法与两个因素有关语法分析方法属性的计算次序在什么时候计算一个产生式的语义规则在自上而下分析中 当一个产生式匹配输入串成功在自下而上分析中 当一个产生式被用于进行归约时L 属性文法可用于一遍扫描的自上而下分析S 属性文法适合于一遍扫描的自下而上分析 6 2 4抽象语法树 在抽象语法树中 操作符和关键字都不作为叶结点出现 而是把它们作为内部结点 S ifBthenS1elseS2 抽象语法树 语法分析树 语法制导翻译可以基于语法分析树 也可以基于抽象语法树 a b c b c 抽象语法树 语法分析树 如何建立表达式的抽象语法树 抽象语法树中的每一个结点可以由包含几个域的记录来实现的 运算符号 结点标号 运算分量的指针 标识符在符号表中的入口 用一些函数来建立表达式的抽象语法树中的结点 1 mknode op left right 建立一个运算符号结点 标号是op 两个域left和right分别指向左子树和右子树 2 mkleaf id entry 建立一个标识符结点 标号为id 一个域entry指向标识符在符号表中的入口 3 mkleaf num val 建立一个数结点 标号为num 一个域val用于存放数的值 每一个函数都返回一个指向新建立结点的指针 toentryfora toentryforc 图6 7a 4 c的抽象语法树 建立表达式a 4 c的抽象语法树 1 P1 mkleaf id entrya 2 P2 mkleaf num 4 3 P3 mknode P1 P2 4 P4 mkleaf id entryc 5 P5 mknode P3 P4 P1 P2 P3 P4 P5 建立抽象语法树的语义规则 表6 4为表达式建立抽象语法树的属性文法 nptr 函数调用返回的指针 虚线 带注释的语法分析树