资源预览内容
第1页 / 共65页
第2页 / 共65页
第3页 / 共65页
第4页 / 共65页
第5页 / 共65页
第6页 / 共65页
第7页 / 共65页
第8页 / 共65页
第9页 / 共65页
第10页 / 共65页
亲,该文档总共65页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五章 语法制导的翻译 赵建华 南京大学计算机系 2010年3月 介绍 使用上下文无关文法引导语言的翻译 CFG的非终结符号代表了语言的某个构造 程序设计语言的构造由更小的构造组合而成 一个构造的语义可以由小构造的含义综合而来 比如:表达式x+y的类型由x、y的类型和运算符+决 定。 也可以从附近的构造继承而来 比如:声明int x;中x的类型由它左边的类型表达式 决定。 语法制导定义和语法制导翻译 语法制导定义: 将文法符号和某些属性相关联, 并通过语义规则来描述如何计算属性的值 EE1+TE.code=E1.code|T.code | + 属性code代表中缀表达式的逆波兰表示,规则说明 加法表达式的逆波兰表示由两个分量的逆波兰表示 并置,然后加上+得到。 语法制导翻译: 在产生式体中加入语义动作,并在适当的时候执行 这些语义动作 EE1+Tprint +; 语法制导的定义(SDD) SDD是上下文无关文法和属性/规则的结合 ; 属性和文法符号相关联,按照需要来确定各个 文法符号需要哪些属性 规则和产生式相关联 对于文法符号X和属性a,我们用X.a表示分 析树中的某个标号为X的结点的值。 一个分析树结点和它的分支对应于一个产 生式规则,而对应的语义规则确定了这些 结点上的属性的取值。 分析树和属性值(1) 假设我们需要知道一个表达式的类型,以及对 应代码将它的值存放在何处,我们就需要两个 属性: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.lexValue=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。 使用依赖图来表示计算顺序。 显然,这些值的计算顺序应该形成一个偏 序关系。如果依赖图中出现了环,表示属 性值无法计算 依赖图 描述了某棵特定的分析树上各个属性实例之间 的信息流(计算顺序) 从实例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。 可能的计算顺序: 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 每个属性都是综合属性 都是根据子构造的属性计算出父构造的属性。 在依赖图中,总是通过子结点的属性值来计算 父结点的属性值。可以和自顶向下、自底向上 的语法分析过程一起计算 自底向上: 在构造分析树的结点的同时计算相关的属性(此时其子 结点的属性必然已经计算完毕) 自顶向下: 递归子程序法中,在过程A()的最后计算A的属性(此时 A调用的其他过程(对应于子结构)已经调用完毕) 在分析树上计算SDD 按照后序遍历的顺序计算属性值即可 postorder(N) for(从左边开始,对N的每个子结点C) postorder(c); /递归调用返回时,各子结点的属性计算完毕 对N的各个属性求值; 在LR分析过程中,我们实际上不需要构造分析树的 结点。 L属性的SDD 每个属性 要么是综合属性, 要么是继承属性,且产生式AX1X2Xn中计算Xi.a的 规则只能使用 A的继承属性 Xi左边的文法符号Xj的继承属性或综合属性。 Xi自身的继承或综合属性。且这些属性之间的依赖关系不形成 环。 特点: 依赖图的边: 继承属性从左到右,从上到下。 综合属性从下到上 在扫描过程中,计算一个属性值时,和它相关的依赖 属性都已经计算完毕。 L属性SDD和自顶向下语法分析 在递归子程序法中实现L属性 对于每个非终结符号A,其对应的过程的参数 为继承属性,返回值为综合属性 在处理规则AX1X2Xn时, 在调用Xi()之前计算Xi的继承属性值,然后以它 们为参数调用Xi(); 在产生式对应代码的最后计算A的综合属性 注意:如果所有的文法符号的属性计算按上面 的方式进行,计算顺序必然和依赖关系一致。 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) /digit是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;返回值保存在某个变量 中。 具有受控副作用的语义规则 属性文法没有副作用,但增加了描述的复杂度 比如语法分析时如果没有副作用,标识符表就必须 作为属性传递。 可以把标识符表作为全局变量,然后通过副作用函 数来添加新标识符; 受控的副作用 不会对属性求值产生约束,即可以按照任何拓扑顺 序求值,不会影响最终结果。 或者对求值过程添加简单的约束。 受控副作用的例子 LE nprint(E.val) 通过副作用打印出E的值 总是在最后执行,而且不会影响其它属性的求值 变量声明的SDD中的副作用 addType将标识符的类型信息加入到标识符表中。 只要标识符不被重复声明,标识符的类型信息总是正确的。 语法制导翻译的应用例子 抽象语法树的构造 基本类型和数组类型的L属性定义 构造抽象语法树的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属性定 义中的计算过程一致。 继承属性可以把值从一个结构传递到另一个并列的结构; 也可把值从父结构传递到子结构。 抽象语法树和分析树不一致时,继承属性很有用。 类型结构 简化的类型表达式的语法 TB CBint | float CnumC | 生成类型表达式的SDD 类型的含义 类型包括两个部分:TB C 基本类型B 分量C 分量形如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, 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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号