《语法制导的翻译_南京大学计算机科学与技术系》由会员分享，可在线阅读，更多相关《语法制导的翻译_南京大学计算机科学与技术系（65页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法制导的翻译 赵建华 南京大学计算机系 2010年3月 介绍 使用上下文无关文法引导语言的翻译 CFG的非终结符号代表了语言的某个构造 程序设计语言的构造由更小的构造组合而成 一个构造的语义可以由小构造的含义综合而来 比如：表达式x+y的类型由x、y的类型和运算符+决 定。 也可以从附近的构造继承而来 比如：声明int x;中x的类型由它左边的类型表达式 决定。 语法制导定义和语法制导翻译 语法制导定义： 将文法符号和某些属性相关联， 并通过语义规则来描述如何计算属性的值 EE1+TE.code=E1.code|T.code | + 属性code代表中缀表达式的逆波兰表示，规则说明
2、加法表达式的逆波兰表示由两个分量的逆波兰表示 并置，然后加上+得到。 语法制导翻译： 在产生式体中加入语义动作，并在适当的时候执行 这些语义动作 EE1+Tprint +; 语法制导的定义（SDD） SDD是上下文无关文法和属性/规则的结合 ； 属性和文法符号相关联，按照需要来确定各个 文法符号需要哪些属性 规则和产生式相关联 对于文法符号X和属性a，我们用X.a表示分 析树中的某个标号为X的结点的值。 一个分析树结点和它的分支对应于一个产 生式规则，而对应的语义规则确定了这些 结点上的属性的取值。 分析树和属性值(1) 假设我们需要知道一个表达式的类型，以及对 应代码将它的值存放在何处，我们
3、就需要两个 属性：type，place； 产生式规则：EE1+T 语义规则：(假设只有int/float类型） E.type = if (E1.type=T.type) T.type else float E.place = newTempPlace(); /返回一个新的内存位置 ； 产生式规则：Fid F.type = lookupIDTable(id.lexValue)-type; F.place = lookupIDTable(id.lexValue)-address; 分析树和属性值(2) a+b*c的语法分析树以及属性值 E ET+ T F id TF* F id idid.lexV
4、alue=a F.Type = FLOAT F.Place = E.Type = FLOAT E.Place = A.a = R.s R YR1R1.i = g(R.i, Y.y); R.s=R1.s R R.s = R.i 新文法中R对应的部分和原文法中A对应的部分互补； 对于AXY1Y2Yn；如果R对应于YYiYn；互补的 A对应于AY1Yi-1 R.i等于互补的A的A.s SDD的求值顺序 在对SDD的求值过程中，如果结点N的属性 a依赖于结点M1的属性a1，M2的属性a2， 。那么我们必须先计算出Mi的属性，才能 计算N的属性a。 使用依赖图来表示计算顺序。 显然，这些值的计算顺序应该
5、形成一个偏 序关系。如果依赖图中出现了环，表示属 性值无法计算 依赖图 描述了某棵特定的分析树上各个属性实例之间 的信息流（计算顺序） 从实例a1到实例a2的有向边表示计算a2时需要a1的值 。（必须先计算a2，再计算a1） 对于标号为X的分析树结点N，和X关联的每个 属性a都对应依赖图的一个结点N.a。 结点N对应的产生式的语义规则通过X.c计算了 A.b的值，且在分析树中X和A分别对应于N1和 N2，那么从N1.c到N2.b有一条边。 N1和N2可以等于/不等于N。 依赖图的例子 3*2的注释分析树； TFT T.val = T.syn; T.inh = F.val; 边e1、e2。 可能
6、的计算顺序： 1,2,3,4,5,6,7,8.9 1,3,5,2,4,6,7,8,9 属性值的计算顺序 各个属性的值需要按照依赖图的拓扑顺序计算 。 如果依赖图中存在环，则属性计算无法进行。 给定一个SDD，很难判定是否存在一棵分析树 ，其对应的依赖图包含环。 但是特定类型的SDD一定不包含环，且有固定 的排序模式 S属性的SDD L属性的SDD 对于这些类型的SDD，我们可以确定属性的计 算顺序，且可以把不需要的属性（及分析树结 点）抛弃以提高效率 S属性的SDD 每个属性都是综合属性 都是根据子构造的属性计算出父构造的属性。 在依赖图中，总是通过子结点的属性值来计算 父结点的属性值。可以和
7、自顶向下、自底向上 的语法分析过程一起计算 自底向上： 在构造分析树的结点的同时计算相关的属性（此时其子 结点的属性必然已经计算完毕） 自顶向下： 递归子程序法中，在过程A()的最后计算A的属性（此时 A调用的其他过程（对应于子结构）已经调用完毕） 在分析树上计算SDD 按照后序遍历的顺序计算属性值即可 postorder(N) for(从左边开始，对N的每个子结点C) postorder(c); /递归调用返回时，各子结点的属性计算完毕 对N的各个属性求值； 在LR分析过程中，我们实际上不需要构造分析树的 结点。 L属性的SDD 每个属性 要么是综合属性， 要么是继承属性，且产生式AX1X2
8、Xn中计算Xi.a的 规则只能使用 A的继承属性 Xi左边的文法符号Xj的继承属性或综合属性。 Xi自身的继承或综合属性。且这些属性之间的依赖关系不形成 环。 特点： 依赖图的边： 继承属性从左到右，从上到下。 综合属性从下到上 在扫描过程中，计算一个属性值时，和它相关的依赖 属性都已经计算完毕。 L属性SDD和自顶向下语法分析 在递归子程序法中实现L属性 对于每个非终结符号A，其对应的过程的参数 为继承属性，返回值为综合属性 在处理规则AX1X2Xn时， 在调用Xi()之前计算Xi的继承属性值，然后以它 们为参数调用Xi()； 在产生式对应代码的最后计算A的综合属性 注意：如果所有的文法符号
9、的属性计算按上面 的方式进行，计算顺序必然和依赖关系一致。 L属性SDD的例子 非L属性的例子： ABCA.s=B.b；B.i=f(C.c, A.s) 各子程序的类型 int T( ); int T1(int inh); int F( ); 文法符 号 函数名 综合属性/类 型 返回类 型 继承属性/ 类型 参数类型 TTval / intint无无 TT1syn / int intinh / intint FFval / intint无无 考虑一下：如果有多个继承属性/多个 综合属性是如何处理 递归子程序法中实现L属性SDD int T( ) if(curToken = digit) /di
10、git是first(FT)中唯一的符号 /处理规则TFT。 intfval = F( );/F的综合属性Value； intt1inh = fval;/计算T的继承属性 intt1syn = T1(t1inh);/计算得到T的综合属性 inttval = t1syn;/计算得到T的综合属性 returntval;/返回T的综合属性 else error();/报错 注意：if(curToken = )肯定不对，因 为不是一个符号 对规则中某个文法符号X的处理： 1、计算X的所有继承属性的值 2、用这些值调用子函数X；返回值保存在某个变量 中。 具有受控副作用的语义规则 属性文法没有副作用，但增
11、加了描述的复杂度 比如语法分析时如果没有副作用，标识符表就必须 作为属性传递。 可以把标识符表作为全局变量，然后通过副作用函 数来添加新标识符； 受控的副作用 不会对属性求值产生约束，即可以按照任何拓扑顺 序求值，不会影响最终结果。 或者对求值过程添加简单的约束。 受控副作用的例子 LE nprint(E.val) 通过副作用打印出E的值 总是在最后执行，而且不会影响其它属性的求值 变量声明的SDD中的副作用 addType将标识符的类型信息加入到标识符表中。 只要标识符不被重复声明，标识符的类型信息总是正确的。 语法制导翻译的应用例子 抽象语法树的构造 基本类型和数组类型的L属性定义 构造抽
12、象语法树的SDD 抽象语法树 每个结点代表一个语法结构；对应于一个运算符； 结点的每个子结点代表其子结构；对应于运算分量 ； 表示这些子结构按照特定方式组成了较大的结构。 可以忽略掉一些标点符号等非本质的东西。 语法树的表示方法 每个结点用一个对象表示 对象有多个域 叶子结点中只存放词法值； 内部结点中存放了op值和参数（通常指向其它结点）； 构造简单表达式的语法树的SDD 属性E.node指向E对应的语法树的根结点； 表达式语法树的构造过程 输入： a-4+c 步骤： p1=new Leaf(id, entry_a) p2=new Leaf(num, 4); p3=new Node(-, p
13、1,p2); p4=new Leaf(id, entry_c); p5=new Node(+, p3,p4); 自顶向下方式处理的L属性定义（1 ） 在消左递归时，按照规则得到此SDD 自顶向下方式处理的L属性定义（2 ） 对于这个SDD，各属性值的计算过程实际上和原来S属性定 义中的计算过程一致。 继承属性可以把值从一个结构传递到另一个并列的结构； 也可把值从父结构传递到子结构。 抽象语法树和分析树不一致时，继承属性很有用。 类型结构 简化的类型表达式的语法 TB CBint | float CnumC | 生成类型表达式的SDD 类型的含义 类型包括两个部分：TB C 基本类型B 分量C
14、分量形如34 表示3X4的二维数组 int 34 数组构造算符array array(3,array(4,int)表示抽象的3X4的二维数组 类型表达式的生成过程 输入：int 23 语法制导的翻译方案 语法制导的翻译方案（SDT）是在产生式体中 嵌入程序片断（语义动作）的上下文无关文法 SDT的基本实现方法： 建立语法分析树； 将语义动作看作是虚拟的结点； 从左到右、深度优先地遍历分析树，在访问虚拟结 点时执行相应动作 用SDT实现两类重要的SDD 基本文法是LR的，SDD是S属性的 基本文法是LL的，SDD是L属性的 例子 语句3*4*5的分析树如右 DFS可知动作执行顺序 A71,A5,
15、 A72, A41, A73, A42, A2 注意，一个动作的不同实例所访问 的属性值属于不同的结点 T3 F * digit:4 digit:5 T2 T1F digit:3 F * E A7 A71 A72 A5 A41 A42 A2 A73 可在语法分析过程中实现的SDT 实现SDT时，实际上并不会真的构造语法分 析树，而是在分析过程中执行语义动作 即使基础文法可以应用某种分析技术，仍 可能因为动作的缘故导致此技术不可应用 判断是否可在分析过程中实现 将每个语义动作替换为一个独有的标记非终结 符号；每个标记非终结符号M的产生式为M 。 如果新的文法可以由某种方法进行分析，那么 这个SDT就可以在这个分析过程中实现。 注意：这个方法没有考虑变量值的传递等要求 。 判断SDT可否用特定分析技术实现例子 LE n M1M1 EE+T M2M2 ET
