语法制导的翻译.pptVIP

0102抽象语法树的构造基本类型和数组类型的L属性定义语法制导翻译的应用例子构造抽象语法树的SDD抽象语法树每个结点代表一个语法结构；对应于一个运算符；结点的每个子结点代表其子结构；对应于运算分量；表示这些子结构按照特定方式组成了较大的结构。可以忽略掉一些标点符号等非本质的东西。语法树的表示方法每个结点用一个对象表示对象有多个域叶子结点中只存放词法值；内部结点中存放了op值和参数（通常指向其它结点）；构造简单表达式的语法树的SDD属性E.node指向E对应的语法树的根结点；表达式语法树的构造过程输入： a-4+c步骤：p1=newLeaf(id,entry_a)p2=newLeaf(num,4);p3=newNode(‘-’,p1,p2);p4=newLeaf(id,entry_c);p5=newNode(‘+’,p3,p4);自顶向下方式处理的L属性定义（1）在消左递归时，按照规则得到此SDD自顶向下方式处理的L属性定义（2）对于这个SDD，各属性值的计算过程实际上和原来S属性定义中的计算过程一致。继承属性可以把值从一个结构传递到另一个并列的结构；也可把值从父结构传递到子结构。抽象语法树和分析树不一致时，继承属性很有用。类型结构简化的类型表达式的语法T?BC B?int|floatC?[num]C|ε生成类型表达式的SDD类型包括两个部分：T?BC基本类型 B分量 Cint [3][4]分量形如[3][4]表示3X4的二维数组数组构造算符arrayarray(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注意，一个动作的不同实例所访问的属性值属于不同的结点T3F*digit:4digit:5T2T1Fdigit:3F*EA7A71A72A5A41A42A2A73可在语法分析过程中实现的SDT实现SDT时，实际上并不会真的构造语法分析树，而是在分析过程中执行语义动作即使基础文法可以应用某种分析技术，仍可能因为动作的缘故导致此技术不可应用判断是否可在分析过程中实现将每个语义动作替换为一个独有的标记非终结符号；每个标记非终结符号M的产生式为M?ε。如果新的文法可以由某种方法进行分析，那么这个SDT就可以在这个分析过程中实现。注意：这个方法没有考虑变量值的传递等要求。判断SDT可否用特定分析技术实现例子L?EnM1 M1?εE?E+TM2 M2?εE?TM3 M3?ε…………文法可以自底向上分析且SDD是S属性的，比然可以构造出后缀SDT后缀SDT：所有动作都在产生式最右端的SDT构造方法：将每个语义规则看作是一个赋值语义动作将所有的语义动作放在规则的最右端后缀翻译方案后缀翻译方案的例子注意动作中对属性值的引用：文法符号的属性只能被赋值一次；实现桌上计算器的后缀SDT我们允许语句引用全局变量，局部变量，文法符号的属性。后缀SDT的语法分析栈实现可以在LR语法分析的过程中实现归约时执行相应的语义动作01定义用于记录各文法符号的属性的union结构02栈中的每个文法符号（或者说状态）都附带一个这样的union类型的值；03在按照产生式A?XYZ归约时，Z的属性可以在栈顶找到，Y的属性可以在下一个位置找到，X的属性可以在再下一个位置找到。04分析栈实现的例子假设语法分析栈存放在一个被称为stack的记录数组中，下标top指向栈顶；stack[top]是这个栈的栈顶；stack[top-1]指向栈顶下一个位置；如果不同的文法符号有不同的属性集合，我们可以使用union来保存这些属性值。归约时能够知道栈顶向下的各个符号分别是什么；因此我们也能够确定各个union中究竟存放了什么样的值第五章语法制导的翻译赵建华南京大学计算机系2010年3月介绍使用上下文无关文法引导语言的翻译CFG的非终结符号代表了语言的某个构造程序设计语言的构造由更小的