哈工大编译原理5-1.1.ppt

第五章 语法制导翻译,2,程序设计语言中更重要的一个方面，是附着在语言结构上的语义,语法表述的是语言的形式，或者说是语言的样子和结构,语义揭示了程序本身的涵义、施加于语言结构上的限制或者要执行的动作,“老鼠吃猫” 问题,语法正确的句子，它的语义可能存在问题,3,语义分析的任务： 检查语言结构的语义是否正确,执行所规定的语义动作,如表达式的求值、,符号表的填写、,中间代码的生成,4,语法制导翻译的基本思想：,对于文法: E E1+T E T T F F digit,digitlexval为digit的属性；,F.val、T.val、E.val为文法符号F、T、E对应的属性值,将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号，,5,当digit为常数时， digitlexval为digit在常数表中的入口,当digit为标识符时， digitlexval为digit在符号表中的入口；,F.val、T.val、E.val 可以看作是中间变量,6,E E1+T,E val := E1 val+T val,F digit,F val := digitlexval,T F,T val := F val,E T,E val := T val,而属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式；,在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理,7,换句话说是：为每一个产生式配上语义规则并且在适当的时候执行这些规则。,即当归约（或推导）到某个产生式时，除了按照产生式进行相应的代换之外(语法分析)，,还要按照产生式所对应的语义规则执行相应的语义动作，,如计算表达式、查填符号表、产生中间代码(语义分析),8,语法制导翻译是目前最常用的语义分析技术,语法分析建立语法分析树,语义分析-遍历语法分析树,语法制导翻译-建立与遍历同时完成,9,例1 台式计算器程序的语法制导定义,产生式 语义规则,LEn print(Eval) E E1+T E val := E1 val+T val E T E val := T val T T1*F T val := T1 val*F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,3*5 +4的分析过程,12,10,3,*,F,5,T,F,E,+,T,F,4,E,T,3*5 +4的语法分析过程,11,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,n,3*5 +4的语义分析过程,12,5.1 语法制导定义(Syntax-directed definitions),语法制导定义也叫属性文法，,通过每一 个产生式和一个语义规则集合相关联。,它是在上 下文无关文法的基础上，,通过每个文法 符号和一个属性集合相关联，,语义规则用来计算与产生式中出现的 符号相关联的属性的值 。,9,13,属性,属性可以代表任何对象：,字符串、数字、类型、内存单元或其它对象,综合属性,继承属性,14,5.1.1 属性,1b是A属性，,在一个语法制导定义中，,规则可表示为：b= f（c1，c2，,ck）,其中：f是一个函数，且满足下面两种情况之一：,c1,c2,ck是中的文 法符号的属性，,或者A的其它属性，则 称b是A的综合属性；,AP 都有与之相关联的一套语义规则，,15,在两种情况下，都说属性b依赖于属性c1，c2，ck。,2c1,c2,ck是A或中的任何文法 符号的属性,则称b是中的符号的 一个继承属性。,16,5.1.2 综合属性,综合属性从下到上包括自身，其属性可从后代和自身的其它属性计算得到,S-属性定义: 只使用综合属性的语法制导定义。,利用S-属性定义进行语义分析时,结点属性值的计算正好和自底向上分析建立分析树结点同步进行。,17,例1 台式计算器程序的S-属性定义,产生式 语义规则,LEn print(Eval) E E1+T E val := E1 val+T val E T E val := T val T T1*F T val := T1 val*F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,3*5 +4的分析过程,18,3,*,F,5,T,F,E,+,T,F,4,E,T,3*5 +4的语法分析过程,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,Eval:=15,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,n,L,19,19,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,n,20,在分析树中为每个文法符号上加上它们的属性，则称为带注释的分析树，简称注释分析树,综合属性值的计算方法,在建立每一个结点处使用语义规则来计算综合属性值，,即在 用哪个产生式进行归约后，,就执行那个产生式的s-属性定义计算属性的值，,从叶结点到根结点进行计算,对于s-属性定义，通常使用自底向上的分析方法，,21,5.1.3 继承属性 继承属性值是由此结点的父结点和或兄弟结点的某些属性值来决定的。,继承属性从上到下包括兄弟，也即继承属性从前辈和兄弟的属性计算得到,22,表2 带有继承属性L.in的语法制导定义,产生式 语义规则 DTL Lin:=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),23,练习：设AS为文法的综合属性集，AI为继承属性集，则下列语法制导定义中,PxQR Q.b=R.d R.c=1 R.e=Q.a,Q u Q.a=3,产生式 语义规则,24,PyQR Q.b=R.f R.c=Q.a R.e=2,Rv R.d=R.c R.f=R.e,试求AS和AI,25,解：由1知：Q.b,R.eAI,整理：AS=Q.a,R.d,R.f AI=Q.b,R.c,R.e,由3知： R.cAI,由4知： R.d,R.f AS,由2知：Q.a=3AS,26,5.2 语义规则,语义规则通常有两种表现形式：,语义规则也叫语义子程序或语义动作,语法制导定义和翻译模式,27,5.2.1 语法制导定义,语法制导定义是关于语言翻译高层次规格说明，,例：下面是将中缀表达式转化为后缀表达式的文法和相应的语法制导定义,它隐藏了具体实现细节，,使用户不用显式地说明翻译发生的顺序,28,产生式 语法制导定义 L E print(E.val) E E1+E2 E.val=E1.val|E2.val|+ E digit E.val=Digit.lexval,语法制导定义 只考虑“做什么”，用抽象的属性表示文法符号所代表的语义,29,翻译模式也叫翻译方案,5.2.2翻译模式,一个翻译模式是一个上下文无关文法，,其中被称为语义动作的程序段被嵌入到产生式的右部。,一个翻译模式类似于语法制导定义，只是语义规则的计算顺序是显式给出的。,30,这是一种语法分析和语义动作交错的表示法，,翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,他表达在按深度优先遍历分析树的过程中何时执行语义动作。,31,例2： 一个简单的翻译模式（中缀变后缀） ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val),32,3+5的语义翻译过程,E,R,T,Pr3,3,T,+,Pr+,5,R,Pr5,结果：35+,33,翻译方案不仅要考虑“做什么”，还要考虑“怎么做”,某种意义上说，语法制导定义类似于算法，而翻译方案更象程序,34,带有继承属性L.in的翻译方案,DT Lin:=T type L T int T type :=integer T real T type :=real L L1 in :=L in L1,idaddtype(id entry,L in) L id addtype(id entry,L in) ,例5 . 3 变量说明的类型定义 int a,b,c,35,D,L.in=t.type,L,real,L1.in=L.in,id3,L1.in=L.in,id2,id1,句子real id1,id2,id3的带继承属性的分析树,T,T.type=real,L,L,Add(L.in),Add(L.in),Add(L.in),36,例：文法G的产生式如下： S（L） S a L L,S L S 1.试写出一个语法制导定义，输出配对括号个数 2.写一个翻译方案，打印每个a的嵌套深度,37,解：1.为S，L引入属性h 产生式 语法制导定义 S（L） S.h=L.h+1 S a S.h=0 L L1,S L.h=L1.h+S.h L S L.h=s.h S S print(S.h),38,(,a,S,S.h=0,L,(,a,L.h=0,S,S.h=0,L,L.h=0,),S,S.h=1,L,L.h=1,),S,S.h=2,(a,(a)的分析过程,39,2.为S，L引入属性d,翻译方案如下 S S.d=0 S S（ L.d=S.d+1 L） S a print(s.d) L L1.d=L.d L1, S.d=L.dS L S.d=L.d S,40,S,S.h=0,S,(,L.d=1,L,),L.d=1,L,S.d=1,S,S.d=1,S,Print(1),a,(,L.d=2,L,),S.d=2,S,Print(2),a,(a,(a)的分析过程,41,5.3 S-属性定义及其自底向上的计算,state,val,top,在分析栈中使用一个附加的域来存放综 合属性值。,下图为一个带有综合属性值域的分析栈：,Z Y Z ,Z.val Y.val Z.val ,42,A b:=f(c1,c2,ck),A b,X x Y y Z z,例：AXYZ Ab:=f(X x, Y y,Z z),ci(1 ik)是 中符号的属性。,其中：b是A的综合属性，,综合属性的值在自底向上的分析过程中，,每步归约时，计算相应的属性值。,X Y Z,A,43,state,val,.,.,A,A .b,top,定义式 A .b=f(X.x, Y.y, Z.z)(抽象) 变成 valntop=f(valtop-2,valtop-1,valtop)（具体可执行代码）。,归约后,分析栈为：,在执行代码段之前执行： ntop:=top-r+1,执行代码段后执行： top:=ntop;,其中:r是句柄的长度, ntop为归约后栈顶,44,例5.10 用LR分析器实现台式计算器 产生式 代码段(和表5.1对比） 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,45,表5.5 翻译输入3*5+4n所做的移动,输入 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,46,+4n T 15 T T*F,+4n E 15 E T,4n E+ 15-,n E+4 15-4,n E+F 15-4 F digit,n E+T 15-4 T F,n E 19 E E+T,En 19 -,L 19 L En,输入 state val 使用的产生式,47,总结：,采用自底向上分析，,例如LR分析，,首先 给出S-属性定义，,然后,把S-属性定义变成 可执行的代码段,这就构成了翻译程序。,象一座建筑,语法分析是构架，,归约 处有一个“挂钩”,语义分析和翻译的 代码段（语义子程序）就挂在这个钩子 上。,这样，随着语法分析的进行，,归约前调用相应的语义子程序,48,在这种分析模式中，,语法分析是 主动的，,语义分析是从动的，,语法分 析制导着语义分析,49,5.4 L-属性定义,一种自然的计算属性的顺序是按深 度优先访问分析树结点的顺序，,在语法分析过程中进行语义分析 和翻译，,属 性的计算顺序受到语法分 析建立分析树结点顺序的限制。,它适应 多种自底向上和自顶向下的翻译方法。,50,深度优先顺序计算属性 PROCEDURE dfvisit(n:node); BEGIN FOR n 的每个子结点m,从左至右 DO BEGIN 计算m的继承属性； dfvisit(m) END; 计算n的综合属性 END;,51,一个语法制导定义是L-属性定义，,5.4.1 L-属性定义,每一个S-属性定义都是L-属性定义。,如果AX1X2XnP,或是Xj(1j n)的一个继承属性，,1、产生式中Xj的左边符号X1,X2，Xj-1 的属性；,2A的继承属性。,其每一个语义规则中的每一个属性都是一个综合属性，,这个继承属性仅依赖于,52,例.一个简单的翻译模式 ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val),9 5 2 +,它是输入表达式9-5+2的后缀式。,把语义动作看成终结符号，,输入9-5+2,其分析树如图，,当按深度优先遍历它，,执行遍历中访问的语义动作，,将输出：,53,E,T,9,T,Pt(9),R,Pt(-),Pt(+),R,-,5,Pt(5),+,T,2,Pt(2),R,9-5+2的带语义动作的分析树,54,设计翻译模式（根据语法制导定义）,TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val,1. 只需要综合属性的情况： 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：,条件：语法制导定义是L-属性定义，保证语义动作不会引用还没有计算的属性值。,55,产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。,一个动作不能引用这个动作右边符号的综合属性。,产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。,2. 既有综合属性又有继承属性,计算这种属性的动作通常可放在产生式右端的未尾。,56,下面的翻译模式不满足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) ,S,A2,A1,a,Pr(A.in),A1.in=1,A2.in=2,end,57,5.5 自顶向下的翻译-用翻译模式构造自顶向下翻译。,5.5.1 从翻译模式中消除左递归,对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。,58,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 图5.13 带左递归的文法的翻译模式,59,ET Ri:=T val RE val:=R s R TR1i:=R.i+T. val R1R. s:=R1 s R- TR1 i:=R i-Tval R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val 经过转换的带有右递归文法的翻译模式,67,69,60,E,T,R.i=T.val,R,E.val=R.s,9,t.val=9,-,T,R1.i=R.i-T.val,R1,R.s=R1.s,5,T.val=5,+,T,R1.i=R.i+T.val,R1,R.s=R1.s,2,T.val=2,R.s=R.i,61,关于左递归翻译模式更一般化的讨论,左递归翻译模式 AA1YA.a:=g(A1.a,Y.y) AX A.a:=f(X.x) (5.2),每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。,消除左递归，文法转换成 AX R RY R|,62,再考虑语义动作，翻译模式变为： AX Ri:=f(X x) R A a:=R s RY R1 i:=g（R i,Y y） R1 R s:=R1 s RR s:=R i （5.4）,为什么？,经过转换的翻译模式与图5.14中一样,使用R的继承属性i和综合属性s。 （5.2）和（5.4）的结果是一样的,63,A a=g(g(f(X x),Y1 y),Y2 y),A a=g(f(X x),Y1 y),A a=f(X x),Y2,Y1,X,(a),输入：XY1Y2,64,A,Ri=f(X x),R i=g(f(X x),Y1 y),R i=g(g(f(X x),Y1 y),Y2 y),Y2,Y1,X,(b),65,5.5.2 预测