属性文法与语法制导翻译-0.ppt

本章的主要内容： 属性文法和语法制导的翻译的概念 综合属性和继承属性的概念、特点 S-属性文法与L-属性文法的概念及分析方法 翻译模式 递归下降翻译器的设计,第六章 属性文法和语法制导翻译,语法制导翻译,语法分析器,syntax + translation rules (typically hardcoded in the parser),记号流,抽象语法树 或者汇编代码,描述 实现 词法分析器 正规式 有限自动机 语法分析器 上下文无关文法 下推自动机 语义分析器 如何描述？ 如何实现？ Syntax analysis form Semantic analysis- meaning,语法制导翻译: 描述 把语法分析树翻译成其值或者抽象语法树 类型检查 语法制导翻译：实现 LR语法分析中 LL语法分析中,语法制导翻译(syntax-directed translation)：通过给语法上各个符号赋予一定的含义并且将各个符号进行有结构的连接，可以形成语言的具体语句的含义。这给予我们以启示：可以通过扩充文法，在文法符号上附着某些语义信息，并在这些语义信息间建立相互计算关系，从而在语法分析的同时进行语义分析。由于这种分析是在语法分析的控制下进行的，故称为语法制导翻译。,6.1 属性文法（属性翻译文法）,属性文法的概念,属性文法的定义： 在上下文无关文法的基础上，为每个文法符号（终结符和非终结符）配备若干相关的“值”（也称：“属性”），对于文法的每个产生式都配备了一组属性的计算规则（语义规则），这种文法称为属性文法。1968年，Knuth首先提出。,说明：在一般情况下，整个属性文法是非常复杂的。但属性的函数关系却通常非常简单。属性也很少依赖于大量的其它属性，因此可以将相互依赖的属性分割成较小的独立属性集，然后单独对每一属性集写出一个属性文法。,（2）属性（Attribute）是编程语言结构的任意特性。属性在其包含的信息和复杂性等方面变化很大。属性的典型例子有： 变量的数据类型。 表达式的值。 存储器中变量的位置。 程序的目标代码。 数的有效位数。,（3）属性文法一般表示方法：,一个简单台式计算器的属性文法,无符号整数的属性文法,属性的分类 综合属性：用于自下而上传递信息；在语法树中，一个结点的综合属性由其子结点的属性值确定，因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。,继承属性：用于自上而下传递信息；在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。,属性文法为例1中的属性文法，输入：3*5+4n,产生式 语义规则 E E1 + T E.loc=newtemp(), E.code = E1.code | T.code | add E1.loc,T.loc,E.loc E T E.loc = T.loc, E.code=T.code T T1 * F T.loc=newtemp(), T.code = T1.code | F.code | mult T1.loc,F.loc,T.loc T F T.loc = F.loc, T.code=F.code F ( E ) F.loc = E.loc, F.code=E.code F id F.loc = , F.code=“”,例 继承属性的类型说明文法,real id1，id2，id3,属性的计算规则 属性的计算规则：设有产生式A 定义 b= f（c1，c2，ck）f是一个计算函数，并且 (a) b是A的一个综合属性并且c1，c2，ck是产生式右边文法符号的属性.或者 (b) b是产生式右边某文法符号的一个继承属性并且c1，c2，ck是A或产生式右边任何文法符号的属性。,注意： 如果同一文法符号在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来。 终结符只有综合属性，它们由词法分析器提供 非终结符既可有综合属性也可有继承属性，文法开始符的所有继承属性为属性计算前的初始值,属性计算规则中仅能使用相应产生式中文法符号的属性（封装性） 产生式左边的继承属性和产生式右边的文法符号的综合属性由其它产生式的属性规则计算 一个句型的语法树可以加以扩充，用来表示句型分析中得到的各个符号的属性间的关系： 语法树中，一个结点的综合属性的值由其子结点的属性值确定 语法树中，一个结点的继承属性的值由该结点的父结点和（或）兄弟结点的某些属性值确定,语法制导翻译 基于属性文法的处理过程通常是：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。,基于属性文法的处理办法,在具体实现时，一般都是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。也就是语义分析是伴随语法分析的过程进行。,依赖图 a依赖图：一种有向图，在一颗语法树中表示结点的继承属性和综合属性之间的相互依赖关系（这种属性之间的依赖关系由文法的语义规则确定）。,b依赖图的构造方法： for 语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 语法树中每一个结点n do for 结点n所用产生式对应的每一条语义规则 bf（c1，c2，ck ) do for i1 to k do 从结点ci到结点b构造一条有向边； 注意：如果属性文法不存在属性之间循环的依赖关系，那么称该文法为良定义。,例 EE1+E2 E.val=E1.val+E2.val,带继承属性文法对于real id1，id2，id3,c属性的计算顺序 拓扑排序 一个有向非循环图的拓扑排序是图中结点的任何顺序m1，m2，mk，使得边必须是从序列中前面的结点指向后面的结点，也就是说,如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj前面。 若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排序，它就是属性值的计算顺序。,计算语义规则的方法 1）分析树法：输入串分析树依赖图计算次序 2）基于规则的方法：在构造编译器时，用手工或专门的工具来分析语义规则，确定属性值的计算顺序。 3）忽略语义规则的方法：在语法分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。实际上，要求限制语法制导定义，使属性值的计算顺序能和语法分析过程同步进行。,树遍历的属性计算方法 前提：1）假设语法树已经建立 2）且树中已带有开始符号的继承属性和终结符的综合属性； 方法：深度优先，从左到右进行（也是一种分析树的方法）,具体算法： While 还有未被计算的属性 do VisitNode(S) /S是开始符号 Procedure VisitNode (N：Node)； begin if NVN then /假设它的产生式NX1Xm for i = 1 to m do if XiVN then begin 计算Xi的所有能够计算的继承属性； VisitNode（Xi）； end； 计算N的所有能够计算的综合属性； end 例子：6.6 P143,一遍扫描的处理办法 在语法分析的同时计算属性值，无需构造实际的语法树；这种方法同下面两个因素有关：,所采用的语法分析方法 属性的计算次序 使用一遍扫描的语义分析方法，就是为文法中的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。在自上而下的分析中就是在产生式匹配输入串成功，或者在自下而上的分析中，当一个产生式被用于进行规约时，此产生式相应的语义规则就被计算，完成有关的语义分析和代码产生的工作。 语法分析过程中完成翻译有许多优点，但也有一些不足： 适于语法分析的文法可能不完全反映语言成分的自然层次结构； 语法分析方法限制，对语法树结点的访问次序和翻译需要的访问次序不一致。,抽象语法树（Abstract Syntax Tree） （1）表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常用的一种中间表示形式。,（2）在抽象语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。 产生式Sif B then S1 else S2 赋值语句的语法树 if-then-else assignment | B S1 S2 variable expression,（3）建立表达式的抽象语法树 建立表达式的抽象语法树使用的函数 1）mknode（op，left，right）建立一个运算符号结点，标号是op，两个域left和right指向运算分量结点的指针。 2）mkleaf(id，entry) 建立一个标识符结点，由标号id标识，一个域entry指向标识符符号表中相应的项。 3）mkleaf（num，val）建立一个数结点，标号为num，域val用于存放数的值。返回新建立结点的指针。,产生式 语义规则 EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val),S-属性文法的自下而上计算 s-属性文法：只含有综合属性 s-属性文法通常借助于LR分析器来实现，在分析栈中使用一个附加的域来存放文法符号的综合属性值。,A b=f（c1，c2，ck） b是A的综合属性，ci(1 ik)是中符号的属性。综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。,例如：AXYZ Aa f(Xx，Yy，Zz) Aa X x Y y Z z,定义式 A.a=f（X.x，Y.y，Z.z）（抽象）变成： valntopf（valtop-2，valtop-1，valtop）（具体可执行代码）。在执行代码段之前执行：ntoptop - r + 1（r是句柄的长度） 执行代码段后执行：topntop；,总结： 采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。,例 用LR分析器实现台式计算器 产生式 代码段 LEn printf(valntop) E E+T valntop:=valtop-2+valtop E T T T*F valntop:=valtop-2*valtop T F F (E) valntop:=valtop-1 F digit,输入 state val 产生式 3*5+4n - - *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T* 3- +4n T* 5 3-5 +4n T* F 3-5 F digit +4n T 15 TT*F +4n E 15 ET 4n E+ 15- n E+4 15-4 n E+F 15-4 Fdigit n E+T 15-4 T F n E 19 EE+T En 19 L 19 L En,思考：S属性文法如果伴随自上而下的语法分析方法如何实现语义的翻译？,语法分析树的遍历,procedure dfsvisit(n:node) for each child m of n from left to right do evaluate inherited attributes of m; dfsvisit(m) evaluate synthesized attributes of n ,L-属性文法和自顶向下翻译 在语法分析过程中进行语义分析和翻译，属 性的计算顺序受到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L-属性文法可用按深度优先顺序计算属性值。,L-属性文法的定义： 如果AX1X2XnP，其每一个语义规则中的每一个属性都是一个综合属性，或是Xj(1j n)的一个继承属性，这个继承属性仅依赖于： a产生式中Xj的左边符号X1，X2，Xj-1的属性； bA的继承属性。 每一个S-属性文法都是L-属性文法,1）翻译模式的概念： 翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号 括起来，可以被插入到产生式右部的任何合适的位置上。,6.4.2 翻译模式,这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。 翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,翻译模式保证了按深度优先次序一次扫描就能完成属性的计算。,例 一个简单的翻译模式 ETR Raddop T print(addop.lexeme)R1| Tnum print(num.val),9-5+2翻译成后缀式95-2+,2）翻译模式的构造 条件：属性文法是L-属性文法； 保证语义动作不会引用还没有计算的属性值。 a. 只需要综合属性的情况： 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。 例如：TT1*F Tval = T1 val*F val TT1*F Tval = T1 val*F val,b. 既有综合属性又有继承属性: 产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。 一个动作不能引用这个动作右边符号的综合属性。( 因为综合属性是在该符号所有分析动作结束后计算） 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。,例：哪个正确？,S A1 S.s = A1.s+A2.s A2 A a A.s = 1 S A1 A2 S.s = A1.s+A2.s A a A.s = 1,S A1 A2 A1.in = 1; A2.in = 2 A a print(A.in) S A1.in = 1; A2.in = 2 A1 A2 A a print(A.in) S A1.in = 1 A1 A2.in = 2 A2 A a print(A.in),产生式 语义规则 S B B.ps = 10; S.ht = B.ht B B1 B2 B1.ps = B.ps; B2.ps = B.ps; B.ht = max(B1.ht, B2.ht) B B1 sub B2 B1.ps = B.ps; B2.ps = shrink(B.ps); B.ht = disp(B1.ht, B2.ht) B text B.ht = text.h * B.ps 这个属性文法是L-属性文法。,产生式 语义规则 S B B.ps = 10; S.ht = B.ht B B1 B2 B1.ps = B.ps; B2.ps = B.ps; B.ht = max(B1.ht, B2.ht) B B1 sub B2 B1.ps = B.ps; B2.ps = shrink(B.ps); B.ht = disp(B1.ht, B2.ht) B text B.ht = text.h * B.ps,翻译模式 S B.ps = 10 B S.ht = B.ht B B1.ps = B.ps B1 B2.ps = B.ps B2 B.ht = max(B1.ht, B2.ht) B B1.ps = B.ps B1 sub B2.ps = shrink(B.ps) B2 B.ht = disp(B1.ht, B2.ht) B text B1.ht = text.h * B.ps ,自顶上下的翻译 用翻译模式构造自顶向下翻译。 从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取公共左因子，在改写基本文法时考虑属性值的计算。,main() E(); ,T() F(); T(); ,TE() T(); E(); ,E() if lookahead = + then match(+); T(); E(); ,F() if lookahead = ( then match(); E(); match(); else . ,E() if lookahead = * then match(*); F(); T(); ,例 带左递归的文法的翻译模式被转换成的带右递归的文法的翻译模式。 EE1+T E val:=E1val+T val E E1-T E val:=E1 val-T val E T E.val:=T val T (E) T val:=E val T num T val:=num val,左递归消除 E T R E.val = ? R + T R ? R - T R ? R ? T (E) T.val = E.val T num T.val = text.val ,ET Ri:=T val RE val:=R s R T R1i:=R.i+T. val R1R. s:=R1 s R- T R1 i:=R i-Tval R1R s:=R1 s RR s:=R i T（ E ）T val:=E.val Tnum T val:=num val 图 经过转换的带有右递归文法的翻译模式,E,T.val=9,num.val=9,R.i=9,-,T.val=5,num.val=5,R.i=4,+,T.val=2,num.val=2,R.i=6,R.s=R.i,R.s=R1.i,R.s=R1.i,E.val=R.s,计算表达式9-5+2,关于左递归翻译模式更一般化的讨论 左递归翻译模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) 每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。 消除左递归，文法转换成 AX R RY R|,再考虑语义动作，翻译模式变为： AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i，Y y） R1 R s:=R1 s R R s:=R i 经过转换的翻译模式中一样,使用R的继承属性i和综合属性s。结果是一样的,输入：XY1Y2,AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) （6.2）,AX Ri:=f(X x) R A. a:=R. s RY R1 i:=g（R i，Y y） R1 R s:=R1 s R R s:=R i （6.4）,表达式建立语法树的翻译模式： EE1+T Enptr :=mknode(+,E1nptr,Tnptr) EE1-T Enptr :=mknode(-,E1nptr,Tnptr) ET Enptr :=Tnptr 从翻译模式中消除左递归，变成以下翻译模式： ET Ri:=Tnptr R Enptr:=Rs R T R1i:=mknode(+,Ri,Tnptr) R1 Rs:=R1 s R- T R1i:=mknode(-,Ri,Tnptr) R1 Rs:=R1s R Rs:=Ri T(E) Tnptr:=Enptr Tid Tnptr:=mkleaf(id, identry) Tnum Tnptr:=mkleaf(num,numval),使用继承属性构造a-4+5的语法树,递归下降翻译器的设计 算法 预测语法制导翻译器的建立 输入：一个带有适合预测分析的基础文法的语法制导翻译模式。 输出：一个语法制导翻译器的代码。 方法：在预测分析器中加入语义动作代码。 AVN,建立一个可递归调用的函数过程 A。为A的每一个继承属性都设置 一个形式参数，函数的返回值是A的综合属性值。 函数过程A的代码（指用符号形式表示的数据和程序）要根据当前的输入符号来决定使用哪一个产生式。 与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、非终结符号还是语义动作，分别是： （a）对于带有综合属性x的单词符号X，x存放在X.x中，Match(X)。 （b）对于BVN，编写一个赋值语句c：= B（b1, b2, ，bk) 其中， b1， b2， ，bk是继承属性， c是综合属性。 （c）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替对属性的每一次引用。,例: Raddop T R1i:=mknode（addop lexeme，R i， Tnptr） R1 R.s:=R1.s R R.s:=R.i 递归下降构造语法树 function R(in:AST-node):AST-node; var nptr,i1,s1,s:AST-node; addoplexeme:char; begin if sym=addop then begin addoplexeme=lexval; advance; /执行一个匹配 nptr=T; /调用T的函数，返回T的综合属性 i1=mknode(addoplexeme,in,nptr);/返回R1的继承属性 s1=R(i1) /调用R过程形参为R的继承属性，返回R的综合属性 s=s1 /执行R.s=R1.s end else s= in /如果sym不是addop，则R-自动匹配，执行R.s=R.i return s end,main() E(); ,E() T(); R(); ,T() if lookahead = ( then match(); E(); match(); else if lookahead = id then match(id); else if lookahead = num then match(num); else error,R() if lookahead=addop then match(addop); T(); R(); else ,递归下降翻译,node main() return E(); ,node TD_E() nptr = T(); return R(nptr); ,node T() if lookahead = ( then match(); nptr=E(); match(); else if lookahead = id then match(id); label = lexval; nptr=mkleaf(label); else if lookahead = num then match(num); label = lexval; nptr=mkleaf(label); else error; return nptr,node R(i:node) if lookahead=addop then match(addop); addoplex=lexval; nptr = T(); i = mknode(addoplex,i,nptr); s = R(i); else s=i return s ,S属性文法如果伴随自上而下的语法分析方法如何实现语义的翻译？,A B print(B.n0), print(B.n1) B 0 B1 B.n0=B1.n0+1, B.n1=B1.n1 B 1 B1 B.n0=B1.n0, B.n1=B1.n1+1 B B.n0=0, B.n1=0,procedure A() call B(); A B procedure B() if (currtoken=0) consume 0; call B(); B 0 B else if (currtoken=1) consume 1; call B(); B 1 B else if (currtoken=$) / $ is end-marker B else error(“unexpected token”); ,procedure A() int n0,n1; call B( ,procedure B(int *n0, int *n1) if (currtoken=0) int a,b; consume 0; call B( ,D T id addtype(id.entry,T.type), L.in = T.type L T int T.type = integer T real T.type = real L id addtype(id.entry,L.in), L1.in = L.in L1 L ,procedure D() int Ttype,Lin,identry; call T( ,procedure T(int *Ttype) if (currtoken is int) consume(int); *Ttype=TYPEINT; else if (currtoken is real) consume(real); *Ttype=TYPEREAL; else error(“unexpected type”); ,procedure L(int Lin) if (currtoken is id) int L1in,identry; consume(id, ,自下而上计算继承属性 从翻译模式中去掉嵌入在产生是中间的动作 在自下而上的翻译方法中要求把所有的语义动作都放在产生式的末尾，而在前面讲到的递归下降翻译方法中，需要在产生式右部的不同地方嵌入语义动作。等价转换的方法如下： 在基础文法中加入新的产生式，这种产生式的形式为M，其中M为新引入的一个标记非终结符，把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾。,例如： ETR R+Tprint(+)R|- Tprint(-)| Tnumprint(num.val) 等价转换为： ETR R+TMR|-TNR| Tnumprint(num.val) Mprint(+) Nprint(-) 分析栈中的继承属性 参见P159对类型说明语句的翻译模式。,模拟继承属性的计算 思想：通过引进新的非终结符和相应的产生式，将新的文法符号插入到某些产生式中去，使得在文法在翻译过程中可以按继承属性的计算方法来处理。也就是在分析过程中文法符号的属性值在分析栈是确定的。 用综合属性代替继承属性 对基础文法进行等价改变，避免使用文法符号的继承属性。,PRODUCTION SEMANTIC RULE D T L L.in = T.type T int T.type = integer T real T.type = real L L1 , id L1.in = L.in addtype(id.entry, L.in) L id addtype(id.entry, L.in),PRODUCTION SEMANTIC RULE D T L T int valntop = integer T real valntop = real L L1 , id addtype(id.entry, valtop-3) L id addtype(id.entry, valtop-1),The value of C.i will be found in Valtop-1,语法制导翻译的处理方法,对应每一个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。,具体的说，若一个语言描述其文法是G，给G的每个产生式配备一个翻译子程序（语义子程序），该语义子程序的功能是生成该产生式对应的中间代码序列。在进行语法分析采用的是自上而下的分析方法，则当一个产生式匹配输入串成功时，就调用该语义子程序，若采用自下而上的分析分年个分，则当一个产生式用于归约时，就调用该语义子程序，从而生成相应的中间代码。,产生式： 一个产生式描述一个语法单位，但它只说明该语法单位能产生的符号串，并没有指明所产生的符号串有什么实际意义，即该符号串究竟要做什么。 语义规则：一个产生式的语义规则描述了该产生式的具体的动作意义，即该产生式的符号串要作什么。 语义子程序：按照产生式的语义规则生成某种中间代码，实现相应的动作。,属性 属性分为综合属性和继承属性两种，从语法树的角度来看，分析树的一个结点（是一个文法符号）的某一个属性值若是根据其子结点的属性值来计算的，则该属性为综合属性，属性值若是根据其父结点的属性值来计算的，则该属性称为继承属性。,终结符只有综合属性，他们由词法分析器提供； 非终结符既有综合属性也可以有继承属性，文法开始符号的所有继承属性，文法开始符号的继承属性作为属性计算前的初始值。,规则：文法中的一个产生式对应一组语义规则，用以说明该产生式的具体动作意义。语义规则所描述的工作可以包括属性计算，静态语义检查，符号表操作，代码生成等。语义规则通常写成过程调用或过程段，即语义子程序。,语义翻译有两种常用的描述形式： 1、语法制导定义：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。 2、翻译模式： 除了定义翻译所必须的语义属性和语义规则，还给出计算顺序。 语法制导翻译(Syntax-Directed Translations)： 一个句子的语义翻译过程与语法分析过程同时进行。 在文法中，文法符号有明确的意义，文法符号之间有确定的语义关系。用属性描述语义信息，用语义规则描述属性间的的关系，将语义规则与语法规则相结合，在语法分析的过程中计算语义属性值。,翻译模式（方案）：如果构造属性文法时