chapter4.ppt

第四章 语法制导的翻译,本章内容1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案2、介绍语法制导翻译的实现方法,4.1 语法制导的定义,例简单计算器的语法制导定义,4.1 语法制导的定义,4.1.1 语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A 有一组形式为b=f(c1,c2,ck)的语义规则，其中b和c1,c2,ck 是该产生式文法符号的属性，f 是函数综合属性：如果b是A的属性，c1,c2,ck 是产生式右部文法符号的属性或A的其它属性继承属性：如果b是右部某文法符号X的属性,4.1 语法制导的定义,4.1.2 综合属性S属性定义：仅使用综合属性的语法制导定义,4.1 语法制导的定义,注释分析树:结点的属性值都标注出来的分析树8+5*2 n的注释分析树,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,4.1.3 继承属性int id,id,id,4.1 语法制导的定义,例int id1,id2,id3的标注了部分属性的分析树不可能像像综合属性那样自下而上标注属性,4.1 语法制导的定义,4.1.4 属性依赖图例int id1,id2,id3的分析树（虚线）的依赖图（实线）D TL L.in=T.type,4.1 语法制导的定义,4.1.4 属性依赖图例int id1,id2,id3的分析树（虚线）的依赖图（实线）L L1,id L1.in=L.in;addType(id.entry,L.in),4.1 语法制导的定义,4.1.4 属性依赖图例int id1,id2,id3的分析树（虚线）的依赖图（实线）L id addType(id.entry,L.in),4.1 语法制导的定义,4.1.5 属性计算次序1、拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点例1，2，3，4，5，6，7，8，9，10,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序,4.1 语法制导的定义,4.1.5 属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性,4.1 语法制导的定义,语义规则的计算方法分析树方法：刚才介绍的方法，动态确定计算次序，效率低概念上的一般方法基于规则的方法：（编译器实现者）静态确定（编译器设计者提供的）语义规则的计算次序 适用于手工构造的方法忽略规则的方法：（编译器实现者）事先确定属性的计算策略（如边分析边计算）,（编译器设计者提供的）语义规则必须符合所选分析方法的限制 适用于自动生成的方法,4.2 S属性定义的自下而上计算,4.2.1 语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：if B then S1 else S2 8+5 2,4.2 S属性定义的自下而上计算,4.2.2 构造语法树的语法制导定义,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算LR分析器的栈增加一个域来保存综合属性值,若产生式A XYZ的语义规则是A.a=f(X.x,Y.y,Z.z)，那么归约后：,top,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,简单计算器的语法制导定义改成栈操作代码,栈 state val,top,4.3 L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,4.3 L属性定义的自上而下计算,4.3.1 L属性定义如果每个产生式AX1Xj-1XjXn的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，但它仅依赖：该产生式中Xj左边符号X1,X2,Xj-1的属性；A的继承属性S属性定义属于L属性定义,4.3 L属性定义的自上而下计算,变量类型声明的语法制导定义是一个L属性定义,4.3 L属性定义的自上而下计算,4.3.2 翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是8 5+2 E T RR addop T print(addop.lexeme)R1|T num print(num.val)E T R num print(8)R numprint(8)addop Tprint(+)R numprint(8)addop numprint(5)print(+)R print(8)print(5)print(+)addop Tprint()R print(8)print(5)print(+)print(2)print(),4.3 L属性定义的自上而下计算,例数学排版语言EQN E sub 1.val S B B B1 B2 B B1 sub B2 B text,4.3 L属性定义的自上而下计算,例数学排版语言EQN（语法制导定义）E sub 1.val,4.3 L属性定义的自上而下计算,例数学排版语言EQN（翻译方案）S B.ps=10 B继承属性的计算BS.ht=B.ht 位于B的左边,4.3 L属性定义的自上而下计算,例数学排版语言EQN（翻译方案）S B.ps=10 B综合属性的计算BS.ht=B.ht 放在右部末端,4.3 L属性定义的自上而下计算,例数学排版语言EQN（翻译方案）S B.ps=10 BS.ht=B.ht B B1.ps=B.ps B1B2.ps=B.ps B2B.ht=max(B1.ht,B2.ht)B B1.ps=B.ps B1sub B2.ps=shrink(B.ps)B2B.ht=disp(B1.ht,B2.ht)B textB.ht=text.h B.ps,4.3 L属性定义的自上而下计算,例左递归的消除引起继承属性,4.3 L属性定义的自上而下计算,E T R.i=T.nptr T+T+T+RE.nptr=R.sR+TR1.i=mkNode(+,R.i,T.nptr)R1R.s=R1.sR R.s=R.i T F W.i=F.nptrWT.nptr=W.sW FW1.i=mkNode(,W.i,F.nptr)W1W.s=W1.sW W.s=W.i F 产生式部分不再给出,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,