程序设计语言编译原理(第三版)第6章.ppt

1,第六章属性文法和语法制导翻译,6.1 属性文法6.2 基于属性文法的处理方法6.3 S属性文法的自下而上计算6.4 L属性文法和自顶向下翻译6.5 自下而上计算继承属性,2,6.1 属性文法,一、基本概念,1.属性,广义：用以描述事物或人的特征、性质、品质等等。,狭义：代表与文法符号相关的信息，其信息值即为 属性值。,例如：其类型、值、代码序列、符号表内容等。,3,（1）属性与变量一样，可以进行计算和传递。,6.1 属性文法,（2）属性加工的过程即是语义处理的过程。,用于“自上而下”传递信息。,用于“自下而上”传递信息。,注:,4,2.语义规则,为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。,3.属性文法,在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）引进一组属性，且让该文法中的重写规则附加上语义规则时，称该上下文无关文法为属性文法。,注：属性文法往往以语法制导翻译和翻译方案两种形式出现。,6.1 属性文法,5,补充:,语法制导定义：基于上下文无关文法，是关于语言翻 译的抽象规格说明，其中除去了一些 实现细节，不规定翻译顺序。,翻译模式：规定实现途径和细节，指明使用语义规则 进行计算的顺序。,6.1 属性文法,6,二、基本规则,1.语义规则的形式：,产生式A的语义规则的形式为b:=f(c1,c2,ck),其中:(1)f是一个函数;,属性b依赖于属性c1,c2,ck,(2)或者bA的综合属性，且c1,c2,ck是中文法 符号的属性;,6.1 属性文法,(3)或者b中某个文法符号的继承属性,且c1,c2,ck是A或中任何文法符号的属性.,7,2.VTVN的属性,(1)VT 只有综合属性,由词法分析器提供.,6.1 属性文法,(2)VN 既可有综合属性也可有继承属性;开始符号S的所有继承属性作为属性计算 前的初始值.,8,3.属性的计算/获得,(1)产生式右边的继承属性 产生式左边的综合属性,(2)产生式左边的继承属性 产生式右边的综合属性,6.1 属性文法,9,例6.1:考虑非终结符，和，其中，有一个继承属性 和一个综合属性，有综合属性，有继承属 性。,C.d:=B.c+1,产生式ABC可能有规则：,属性A.a和B.c在其它地方计算。,A.a左部继承属性A.b左部综合属性B.c右部综合属性C.d右部继承属性,6.1 属性文法,10,例6.2:一个简单台式计算器的属性文法,Print(E.val),E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val*F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,6.1 属性文法,11,三、综合属性,1.语法树中,一个结点的综合属性的值由其子结点的 属性值确定;,2.通常使用自底向上的方法在每一个结点处使用语义 规则计算综合属性的值.,S属性文法：仅使用综合属性的属性文法.,6.1 属性文法,12,例6.3:例6.2的表中定义的属性文法说明了一个台式计算器，该计算器读入一个可含数字、括号和+、*运算符的算术表达式，并打印表达式的值，每个输入行以n作为结束。假设表达式为3*5+4，后跟一个换行符n。,程序打印数值19,其带注释的语法树,6.1 属性文法,13,返回,*+的带注释的语法树,14,四、继承属性,1.语法树中,一个结点的继承属性由此结点的父结点 和或兄弟结点的某些属性确定;,2.用继承属性来表示程序设计语言结构中的上下文 依赖关系很方便.,6.1 属性文法,15,例6.:带继承属性L.in的属性文法,addtype(id.entry,L.in),T.type:=integer,T.type:=real,L1.in:=L.in,L.in:=T.type,addtype(id.entry,L.in),6.1 属性文法,16,输入串:real id1,id2,id3 的带注释的语法树,D,T.type=real,L.in=real,real,L.in=real,L.in=real,，,id2,id3,，,id1,17,基于属性文法的处理过程:,单词符号串,语法分析树,计算,例:,6.2 基于属性文法的处理方法,18,语法制导翻译法,语义规则的计算将有下列作用：,产生代码，在符号表中存放信息，给出错误信息或执行其它动作。,由源程序的语法结构所驱动的处理方法。,6.2 基于属性文法的处理方法,19,一、依赖图,1.定义：一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图。,6.2 基于属性文法的处理方法,20,2.依赖图的构造方法,（1）构造依赖图以前，先为每一个包含过程调用的语义规则引入一个虚综合属性b，在每一个语义规则均写成b=f（c1,c2,ck）的形式.,（2）在依赖图中为每一个属性设置一个结点.,（3）若属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。,6.2 基于属性文法的处理方法,21,返回,6.2 基于属性文法的处理方法,22,6.2 基于属性文法的处理方法,23,3.例题,例6.6:将下面的产生式应用于语法树中,产生式语义规则EE1+E2E.val:=E1.val+E2.val,E.Val是从 E1.val和E2.val综合得出,6.2 基于属性文法的处理方法,24,例6.7:例6.4中语法分析树的依赖图,in 5 6type3 typein 7 8in 9 10 2 entry 1 entry,6.2 基于属性文法的处理方法,25,.属性的计算次序：,6.2 基于属性文法的处理方法,一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。,注:在拓扑排序中,在一个结点上，语义规则 b:=f(c1,c2,ck)中的属性c1,c2,ck 在计算b以前是可用的。,良定义的：若一个属性文法不存在属性之间的循 环依赖关系，则称该文法为良定义的。,26,基础文法用于建立输入符号串的语法分析树,从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。,6.2 基于属性文法的处理方法,a4：=reala5：=a4addtype（id3.entry，a5）；a7：=a5；addtype（id2.entry，a7）；a9：=a7；addtype（id1.entry，a9）；,例6.8:,27,二、树遍历的属性计算方法,1.方法,A.前提：假设语法树已经建立起来了，且树中已 有如下信息：开始符号继承属性 终结符综合属性,B.遍历：以某种次序遍历语法树，直至计算出所 有属性.,遍历方法：深度优先，从左到右,6.2 基于属性文法的处理方法,28,2.算法,While 还有未被计算的属性 doVisitNode(S)/*S是开始符号*/,procedure VisitNode(N:Node);begin If N是一个非终结符 then/*假设它的产生式为NX1Xm*/for i:=1 to m do if not XiVT then/*即Xi是终结符*/begin 计算Xi的所有能够计算的继承属性;VisitNode(Xi)end;计算N的所有能够计算的综合属性end,29,6.2 基于属性文法的处理方法,注：只要文法的属性是非循环定义的，则每次扫 描至少有一个属性值被计算出来。,30,其中，S有继承属性a，综合属性b；X有继承属性c，综合属性d；Y有继承属性e，综合属性f；Z有继承属性h，综合属性g。,3.举例,例6.9:考虑下表所给的属性文法G。,6.2 基于属性文法的处理方法,31,6.2 基于属性文法的处理方法,32,6.2 基于属性文法的处理方法,33,三、一遍扫描的处理方法,1.特点,在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。,注：采用该处理方法，当一个属性值不再用于计算 其它属性值时，编译程序就不必再保留这个属性 值。如果需要，可把语义值存到文件中。,6.2 基于属性文法的处理方法,34,2.相关因素：,（1）所使用的语法分析方法 L-属性文法一遍扫描的自上而下分析 S-属性文法一遍扫描的自下而上分析,6.2 基于属性文法的处理方法,（2）属性的计算次序,35,3.语法制导翻译,A.在语法规则的制导下，通过计算语义规则，完成对输 入符号串的翻译。,6.2 基于属性文法的处理方法,该产生式相应的语义规则被计算，完成有关的语义分析和代码产生工作。,由此可见，在该情况下，语法分析工作和语义规则的计算是穿插进行的。,B.为文法中每个产生式配上一组语义规则，并在语法分析 的同时执行这些语义规则。,36,四、抽象语法树Abstract Syntax Tree,1.定义：,注：抽象语法树中，操作符和关键字都不作为叶结点出现,而是把它们作为内部结点,即这些叶结点的父结点.,6.2 基于属性文法的处理方法,在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示，这种经变换后的语法树称之为抽象语法树。,37,2.如何建立表达式的抽象语法树,（1）方法：通过为每一个运算分量或运算符号都 建立一个结点来为子表达式建立子树；,6.2 基于属性文法的处理方法,运算符号结点的各个子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根。,38,（2）抽象语法树中每个结点可由包含几个域的记录来实现,6.2 基于属性文法的处理方法,运算符号结点：一个域 运算符号 其它域 指向运算符号分量的结点的指针,结点：附加的域存放结点的属性值/指向属性值的指针。,39,6.2 基于属性文法的处理方法,40,例6.10:下面一系列函数调用建立了表达式a-4+c的抽象语法树（如图）。在这个序列中，p1,p2,p5是指向结点的指针，entrya和entryc分别是指向符号表中的标识符a和c的指针。,6.2 基于属性文法的处理方法,(1)p1:=mkleaf(id,entrya);(2)p2:=mkleaf(num,4);(3)p3:=mknode(-,p1,p2);(4)p4:=mkleaf(id,entryc);(5)p5:=mknode(+,p3,p4),41,为表达式建立抽象语法树的属性文法,6.2 基于属性文法的处理方法,42,E,nptr,T,nptr,E,nptr,E,T,nptr,num,T,nptr,id,+,id,带注释的语法分析树,To entry for a,To entry for c,43,6.3 S属性文法的自下而上计算,1.S属性文法 定义:（1）所有非终结符只具有综合属性；（2）在一个产生式中，每个符号的各个综合属性 的定义互不依赖。,2.综合属性的计算 在分析输入符号串的同时由自下而上的分析器来计算，分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算.,44,3.S-属性文法的翻译器通常可借助于LR分析器实现 在S-属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。,6.3 S属性文法的自下而上计算,45,4.分析栈,6.3 S属性文法的自下而上计算,自底向上分析法中：栈存放已经分析过的子树的内容 附加域存放综合属性值,数组State:元素一个指向LR(1)分析表的指针(索引）,指向表中某个文法符号.数组Val:存放语法树中与结点对应的属性值.,注:(1)假定综合属性刚好在每次归约前计算.(2)若一个符号无综合属性,则数组val中相应的元素就不定义.,46,5.举例,L En E E1+TE TT T1*FT FF(E)F digit,输入串 3*5+4n,3*5+4n,*5+4n 3 3,*5+4n F 3,*5+4n T 3,5+4n T*3,+4n T*5 3 5,+4n T 15,+4n E 15,4n E+15,+4n T*F 3 5,F digit,T F,F digit,T T*F,E T,47,L En E E1+TE TT T1*FT FF(E)F digit,输入串 3*5+4n,4n E+15,n E+4 15 4,n E+F 15 4,n E+T 15 4,n E 19,En 19,L 19,F digit,T F,E E+T,L En,5.举例,48,6.4 L-属性文法和自顶向下翻译,L-属性文法,1.定义:若属性文法中每个产生式AX1X2Xn,其相关的每个语义规则中的每个属性:,或者是综合属性;,或者是Xj的一个继承属性且该继承属性仅依赖于 Xj左边符号X1,X2,Xj-1的属性和A的继承属性。,则称该属性文法为L-属性文法.,49,2.特点:,6.4 L-属性文法和自顶向下翻译,L-属性文法,A.该类属性文法允许我们通过一次遍历就计算出所 有属性值.,B.可在自上而下语法分析的同时实现L-属性文法的 计算.,C.S-属性文法一定是L-属性文法.,50,6.4 L-属性文法和自顶向下翻译,一个非L-属性文法,51,一.翻译模式,1.翻译模式的定义：,一种适合语法制导翻译的语义描述形式,给出了使用语义规则进行计算的次序,可把某些实现细节表示出来.,形式:在翻译模式中,和文法符号相关的属性和语义规 则,用 括起来,插入到产生式右部的合适位置上.,例:E TR R addop T pr(addop.lex)R1|T num pr(num.val),6.4 L-属性文法和自顶向下翻译,52,为每一个语义规则建立一个包含赋值的动作,并把这个动作放在相应的产生式右边的末尾.,6.4 L-属性文法和自顶向下翻译,2.翻译模式的设计：,A.只有综合属性时,可以按如下方式建立翻译模式:,53,B.若既有综合属性又有继承属性时,则按如下方式建立 翻译模式:,产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来.,一个动作不能引用这个动作右边的符号的综合属性.,产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算.计算这种属性的动作通常可放在产生式右端的末尾.,6.4 L-属性文法和自顶向下翻译,2.翻译模式的设计：,54,举例:,E TR R addop Tpr(addop.lex)R1|T num pr(num.val),输入：952深度优先遍历后输出：952,E,T,R,R,R,9,Pr(9),T,Pr(),T,Pr(),5,Pr(5),2,Pr(2),55,二.自顶向下翻译,1.讨论:L-属性文法在自顶向下分析中的实现,6.4 L-属性文法和自顶向下翻译,自顶向下语法分析的前提是消除文法中的左递归.,56,EE1+T E.val:=E1.val+T.val EE1T E.val:=E1.valT.val ET E.val:=T.val T(E)T.val:=E.val Tnum T.val:=num.val,ET R.i:=T.val R E.val:=R.s R+T R1.i:=R.i+T.val R1 R.s:=R1.s R T R1.i:=R.i-T.val R1 R.s:=R1.s R R.s:=R.i T(E)T.val:=E.val Tnum T.val:=num.val,2.例题:,57,计算表达式 952,带注释语法树i:继承属性s:综合属性,6.4 L-属性文法和自顶向下翻译,58,计算表达式 952,递归过程：综合属性计算,6.4 L-属性文法和自顶向下翻译,59,AA1Y A.a=g(A1.a,Y.y AX A.a=f(X.x),AX R.i:=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 L-属性文法和自顶向下翻译,3.转换左递归翻译模式的一般方法：,消除左递归前:,消除左递归后:,60,6.4 L-属性文法和自顶向下翻译,带注释语法树,P 155-156,61,递归下降分析器的构造 p156举例 AST:Abstract Syntax Tree,三.递归下降翻译器的设计,6.4 L-属性文法和自顶向下翻译,62,L-属性文法的自上而下分析翻译方法，适用于所有基于LL(1)文法和许多基于LR(1)文法的L-属性文法，是S-属性文法自下而上翻译技术的一般化。（1）从翻译模式中去掉嵌入在产生式中间的动作（2）分析栈中的继承属性（3）模拟继承属性的计算（4）用综合属性代替继承属性,6.5 自下而上的计算继承属性,63,S属性文法翻译自下而上规约时进行，翻译模式允许翻译动作嵌入产生式，如何保证嵌入的动作在产生式的末尾？标记非终结符 M 标记非终结符代替嵌入在产生式中间的语义动作，并将这个动作放在产生式M 的末尾。,一.从翻译模式中去掉嵌入在产生式中间的动作,6.5 自下而上的计算继承属性,64,AXY综合属性 X.s继承属性 Y.i复写：Y.i:=X.s,D TL.in:=T.typeLT intT.type:=integerT realT.type:=realL L1.in:=L.in L1,id addtype(id_entry,L.in L id addtype(id_entry,L.in,二.分析栈中的继承属性,6.5 自下而上的计算继承属性,65,输入串:real id1,id2,id3,D,T,L,real,L,L,，,id2,id3,，,id1,1,9,10,4,5,6,7,8,2,3,6.5 自下而上的计算继承属性,二.分析栈中的继承属性,66,文法与属性位置 唯一确定 计算属性的确定性不确定到确定的转换 引入标记非终结符M，通过M的继承属性，传递属性计算的复写内容。,三.模拟继承属性的计算,6.5 自下而上的计算继承属性,67,SaACC.i=A.s SaACC.i=A.s SbABCC.i=A.s SbABMCM.i=A.s;C.i=M.s M M.s=M.i SaACC.s=g(C.i)SaACC.s=g(C.i),S,b,A,B,C,S,b,A,B,M,C,s,i,s,i,s,i,三.模拟继承属性的计算,6.5 自下而上的计算继承属性,68,改变文法，用综合属性代替继承属性例：DL:T Did L Tinteger|real L,id L|:T LL,id|id Tinteger|real,四.用综合属性代替继承属性,6.5 自下而上的计算继承属性,