五章语法制导的翻译.pptVIP

自底向上实现L属性SDD的例子（3） S1.next被存放在N的栈记录中，它恰巧存放于S1的栈记录之下 S1.next = stack[top-3].L1 构造抽象语法树的SDD 抽象语法树 每个结点代表一个语法结构；对应于一个运算符； 结点的每个子结点代表其子结构；对应于运算分量； 表示这些子结构按照特定方式组成了较大的结构。 可以忽略掉一些标点符号等非本质的东西。 语法树的表示方法 每个结点用一个对象表示 对象有多个域 叶子结点中只存放词法值； 内部结点中存放了op值和参数（通常指向其它结点）； 构造简单表达式的语法树的SDD 属性E.node指向E对应的语法树的根结点； 表达式语法树的构造过程 输入： a-4+c 步骤： p1=new Leaf(id, entry_a) p2=new Leaf(num, 4); p3=new Node(‘-’, p1,p2); p4=new Leaf(id, entry_c); p5=new Node(‘+’, p3,p4); 自顶向下方式处理的L属性定义（1） 在消左递归时，按照规则得到此SDD 自顶向下方式处理的L属性定义（2） 对于这个SDD，各属性值的计算过程实际上和原来S属性定义中的计算过程一致。 继承属性可以把值从一个结构传递到另一个并列的结构；也可把值从父结构传递到子结构。 抽象语法树和分析树不一致时，继承属性很有用。 类型结构 简化的类型表达式的语法 T?B C B?int | float C?[num]C | ε 生成类型表达式的SDD 类型的含义 类型包括两个部分：T?B C 基本类型 B 分量 C 分量形如[3][4] 表示3X4的二维数组 int [3][4] 数组构造算符array array(3,array(4,int))表示抽象的3X4的二维数组 类型表达式的生成过程 输入：int [2][3] 语法制导的翻译方案 语法制导的翻译方案（SDT）是在产生式体中嵌入程序片断（语义动作）的上下文无关文法 SDT的基本实现方法： 建立语法分析树； 将语义动作看作是虚拟的结点； 从左到右、深度优先地遍历分析树，在访问虚拟结点时执行相应动作 用SDT实现两类重要的SDD 基本文法是LR的，SDD是S属性的 基本文法是LL的，SDD是L属性的 例子 语句3*4*5的分析树如右 DFS可知动作执行顺序 A71,A5, A72, A41, A73, A42, A2 注意，一个动作的不同实例所访问的属性值属于不同的结点 T3 F * digit:4 digit:5 T2 T1 F digit:3 F * E A7 A71 A72 A5 A41 A42 A2 A73 可在语法分析过程中实现的SDT 实现SDT时，实际上并不会真的构造语法分析树，而是在分析过程中执行语义动作 即使基础文法可以应用某种分析技术，仍可能因为动作的缘故导致此技术不可应用 判断是否可在分析过程中实现 将每个语义动作替换为一个独有的标记非终结符号；每个标记非终结符号M的产生式为M?ε。 如果新的文法可以由某种方法进行分析，那么这个SDT就可以在这个分析过程中实现。 注意：这个方法没有考虑变量值的传递等要求。 判断SDT可否用特定分析技术实现例子 L?E n M1 M1?ε E?E+T M2 M2?ε E?T M3 M3?ε … … … … 后缀翻译方案 文法可以自底向上分析且SDD是S属性的，比然可以构造出后缀SDT 后缀SDT：所有动作都在产生式最右端的SDT 构造方法： 将每个语义规则看作是一个赋值语义动作 将所有的语义动作放在规则的最右端 后缀翻译方案的例子 实现桌上计算器的后缀SDT 注意动作中对属性值的引用： 我们允许语句引用全局变量，局部变量，文法符号的属性。 文法符号的属性只能被赋值一次； 后缀SDT的语法分析栈实现 可以在LR语法分析的过程中实现 归约时执行相应的语义动作 定义用于记录各文法符号的属性的union结构 栈中的每个文法符号（或者说状态）都附带一个这样的union类型的值； 在按照产生式A?XYZ归约时，Z的属性可以在栈顶找到，Y的属性可以在下一个位置找到，X的属性可以在再下一个位置找到。 分析栈实现的例子 假设语法分析栈存放在一个被称为stack的记录数组中，下标top指向栈顶； stack[top]是这个栈的栈顶； stack[top-1]指向栈顶下一个位置； 如果不同的文法符号有不同的属性集合，我们可以使用union来保存这些属性值。 归约时能够知道栈顶向下的各个符号分别是什么；因此我们也能够确定各个union中究竟存放了什么样的值 后缀SDT的栈实现 这个SDT中没有局部变量，不会产生和局部变量有关的问题 注意：stack[top-i]和文法符号的对应 产