属性文法和语法制导翻译

第六章属性文法和语法制导翻译,“语义分析”是编译程序最实质性的工作。语义分析程序在整个编译过程中，首次对源程序的语义做出解释，引起源程序发生质的变化，而词法分析和语法分析仅是对源程序形式上的识别和处理。,高级程序语言结构的形式化描述已经有比较成熟的技术，由于这种形式化描述的完善，使分析器的构造甚至自动构造是比较容易的。,1,编译程序的语义分析涉及到语言的语义，语义形式化是个专门的研究课题.形式语义学（如指称语义学、公理语义学、操作语义学等）的研究从20世纪60年代已经开始，并且在理论研究方面也有了重要的进展。但不论哪种方法，其本身的符号系统比较繁杂，其描述文本不易读，尚不便借助这些形式系统自动完成语义处理任务。并且在工程实现和应用方面还有一定的差距。,2,目前实际应用中较流行的语义描述和语义处理方法主要还是属性文法和语法制导翻译方法。但它仍不是一种形式系统，只是比较接近形式化。,语法制导翻译方法的实质是在语法分析过程中同时进行语义处理的翻译技术。这种方法使用属性文法为工具来说明程序设计语言的语义。,3,第六章属性文法和语法制导翻译,6.1属性文法6.2基于属性文法的处理方法6.3S属性文法的自下而上计算6.4L属性文法和自顶向下翻译6.5自下而上计算继承属性,4,6.1属性文法,一、基本概念,1、属性,广义：用以描述事物或人的特征、性质、品质等等。,属性文法中：代表与文法符号相关的信息，其信息值即为属性值。,例如：其类型、值、代码序列、符号表内容等。,5,6.1属性文法,（1）属性与变量一样，可以进行计算和传递。（2）属性加工的过程即是语义处理的过程。（3）属性综合属性：用于“自下而上”传递信息。继承属性：用于“自上而下”传递信息。,6,6.1属性文法,2、语义规则,为文法的每一个产生式配备的属性的计算规则，称为语义规则。,3、属性文法,上下文无关文法+语义规则=属性文法,7,6.1属性文法,二、基本规则,1、语义规则的形式：,产生式A的语义规则的一般形式为b:=f(c1,c2,ck),其中：(1)f是一个函数；(2)或者bA的综合属性，且c1,c2,ck是中文法符号的属性；(3)或者b中某个文法符号的继承属性，且c1,c2,ck是A或中任何文法符号的属性。,属性b依赖于属性c1,c2,ck,8,6.1属性文法,2、VTVN的属性,(1)VT只有综合属性，由词法分析器提供。(2)VN既可有综合属性也可有继承属性，文法开始符号S的所有继承属性作为属性计算前的初始值。,9,6.1属性文法,3、属性的计算/获得,(1)产生式右边的继承属性产生式左边的综合属性,(2)产生式左边的继承属性产生式右边的综合属性,10,6.1属性文法,例6.1：,C.d:=B.c+1A.b:=A.a+B.c,产生式ABC的规则：,C.d右部继承属性A.b左部综合属性A.a左部继承属性B.c右部综合属性,11,6.1属性文法,例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,12,addtype(id.entry,L.in),T.type:=integer,T.type:=real,L1.in:=L.in,L.in:=T.type,addtype(id.entry,L.in),13,14,6.1属性文法,二、综合属性,1、语法树中,一个结点的综合属性的值由其子结点的属性值确定。,2、通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。,S属性文法：仅使用综合属性的属性文法,15,6.1属性文法,例6.3：例6.2的表中定义的属性文法说明了一个台式计算器，该计算器读入一个可含数字、括号和+、*运算符的算术表达式，并打印表达式的值，每个输入行以n作为结束。假设表达式为3*5+4，后跟一个换行符n。,则程序打印数值19。,其带注释的语法树,16,三、继承属性,1、语法树中,一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。,6.1属性文法,、用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。,17,6.1属性文法,例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),18,输入串:realid1,id2,id3的带注释的语法树,D,T.type=real,L.in=real,real,L.in=real,L.in=real,，,id2,id3,，,id1,19,1、构造依赖图的方法:,6.2基于属性文法的处理方法,2、遍历语法树的方法,单词符号串,语法分析树,计算,3、可用一遍扫描实现属性文法的语义规则计算。,20,一、依赖图,1、定义：一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图。,6.2基于属性文法的处理方法,21,2、依赖图的构造方法,（1）构造依赖图以前，先为每一个包含过程调用的语义规则引入一个虚综合属性b，在每一个语义规则均写成b:=f（c1，c2，ck）的形式；,（2）在依赖图中为每一个属性设置一个结点；,（3）若属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。,6.2基于属性文法的处理方法,22,A.a,X.i,X.x,Y.y,6.2基于属性文法的处理方法,23,3、例题,例6.6：将下面的产生式应用于语法树中,产生式语义规则EE1+E2E.val:=E1.val+E2.val,E.Val是从E1.val和E2.val综合得出,6.2基于属性文法的处理方法,24,addtype(id.entry,L.in),T.type:=integer,T.type:=real,L1.in:=L.in,L.in:=T.type,addtype(id.entry,L.in),25,D,T,L,real,L,L,，,id2,id3,，,id1,a4,a6,a7,a8,a9,a10,a1,a2,a3,a5,a4：=reala5：=a4Addtype(id3.entry，a5)；a7：=a5；addtype(id2.entry，a7)；a9：=a7；Addtype(id1.entry，a9)；,拓扑序列a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,26,二、树遍历的属性计算方法,1、方法,A、前提：假设语法树已经建立起来了，且树中已有如下信息：开始符号继承属性终结符综合属性,B、遍历：以某种次序遍历语法树，直至计算出所有属性。,遍历方法：深度优先，从左到右,6.2基于属性文法的处理方法,27,6.2基于属性文法的处理方法,2、算法,While还有未被计算的属性doVisitNode(S)/*S是开始符号*/procedureVisitNode(N:Node);beginIfN是一个非终结符then/*假设它的产生式为NX1Xm*/fori:=1tomdoifnotXiVTthen/*即Xi是非终结符*/begin计算Xi的所有能够计算的继承属性;VisitNode(Xi)end;计算N的所有能够计算的综合属性end,注：只要文法的属性是非循环定义的，则每次扫描至少有一个属性值被计算出来。,28,其中，S有继承属性a，综合属性b；X有继承属性c，综合属性d；Y有继承属性e，综合属性f；Z有继承属性h，综合属性g。,3、举例,例6.9：考虑下表所给的属性文法G。,6.2基于属性文法的处理方法,29,S:a=0,X,Y,Z,x,y(a),z,S:a=0,X,Y,Z：h=0g=1,x,y(b),z,30,S:a=0,b=0,X:c=1d=2,Y:e=0f=0,Z：h=0g=1,x,y(d),z,S:a=0,b=0,X:c=1d=2,Y,Z：h=0g=1,x,y(c),z,31,6.2基于属性文法的处理方法,三、一遍扫描的处理方法,1、特点,在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。,注：采用该处理方法，当一个属性值不再用于计算其它属性值时，编译程序就不必再保留这个属性值。如果需要，可把语义值存到文件中。,32,6.2基于属性文法的处理方法,2、相关因素：,（1）所使用的语法分析方法L-属性文法一遍扫描的自上而下分析S-属性文法一遍扫描的自下而上分析（2）属性的计算次序,33,上节课的内容：,属性文法,属性,综合属性,继承属性,产生式+属性计算规则（语义规则）,AX1XK,A.a=Xi.x=,属性计算方法,123,S-属性文法-6.3L-属性文法-6.4,34,6.2基于属性文法的处理方法,例2：构造表达式产生抽象语法树（AbstractSyntaxTree）的属性文法,1、定义：在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示，这种经变换后的语法树称之为抽象语法树。,注：抽象语法树中，操作符和关键字都不作为叶结点出现。,35,抽象语法树,内部结点,外部结点,操作符关键字,标识符常数,如：a+3*b的抽象语法树,+,a,*,3,b,36,6.2基于属性文法的处理方法,2、如何建立表达式的抽象语法树,（1）方法：通过为每一个运算分量或运算符号都建立一个结点来为子表达式建立子树；运算符号结点的各个子结点分别表示该运算符号的各个运算分量的子表达式组成的子树的根。,37,6.2基于属性文法的处理方法,（2）抽象语法树中每个结点可由包含几个域的记录来实现。运算符号结点：一个域运算符号其它域指向运算符号分量的结点的指针结点：附加的域存放结点的属性值/指向属性值的指针。,38,6.2基于属性文法的处理方法,39,6.2基于属性文法的处理方法,例6.10：下面一系列函数调用建立了表达式a-4+c的抽象语法树（如图）。在这个序列中，p1,p2,p5是指向结点的指针，entrya和entryc分别是指向符号表中的标识符a和c的指针。,id,+,-,id,num4,toentryfora,toentryforc,(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),（4）如何设计产生表达式抽象语法树的属性文法？EE1+TEE1-TETT(E)TidTnum,41,为表达式建立抽象语法树的属性文法,T.nptr:=mkleaf(num,num.val),T.nptr:=mkleaf(id,id.entry),T.nptr:=E.nptr,E.nptr:=T.nptr,E.nptr:=mkNode(+,E1.nptr,T.nptr)E.nptr:=mkNode(-,E1.nptr,T.nptr),42,E,nptr,T,nptr,E,nptr,E,T,nptr,num,T,nptr,id,+,id,带注释的语法分析树,Toentryfora,Toentryforc,43,6.3S-属性文法的自下而上计算,1、S-属性文法：只含综合属性的属性文法。2、S-属性文法的翻译借助于LR分析器来实现,LR分析器,44,3、对分析栈改造,状态栈符号栈属性栈,S0#-,Sm-1xx.val,Smyy.val,45,3、对分析栈改造自底向上分析法中：栈存放已经分析过的子树的内容附加域存放综合属性数组State：元素一个指向LR(1)分析表的指针(索引），指向表中某个状态文法符号为隐含在State中而不需存在栈中数组Val：符号的属性值,46,6.1属性文法,例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,47,状态栈符号栈属性栈,S0#-,Sm-2EE.val,Sm-1+-,考虑：EE1+TE.val:=E1.val+T.val,SmTT.val,SEE.val,转换为：EE1+Tvalntop:=valtop-2+valtop,48,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,把下面文法的语义规则转换为对属性栈的操作：,Print(valtop),Valntop=valtop-2+valtop,Valntop=valtop-1,Valntop=valtop-2*valtop,49,6.11举例,LEnEE1+TETTT1*FTFF(E)Fdigit输入串3*5+4n,为表达式建立抽象语法树的属性文法,T.nptr:=mkleaf(num,num.val),T.nptr:=mkleaf(id,id.entry),T.nptr:=E.nptr,E.nptr:=mkNode(+,E1.nptr,T.nptr)E.nptr:=mkNode(-,E1.nptr,T.nptr)E.nptr:=T.nptr,nptrntop:=mkNode(+,nptrtop-2,nptrtop)nptrntop:=mkNode(-,nptrtop-2,nptrtop)nptrntop=nptrtop-1nptrntop=mkleaf(id,id.entry)nptrntop=mkleaf(num,num.val),51,6.4L-属性文法和自顶向下翻译,对语法分析树进行一次深度优先遍历就能计算出所有的属性。即在自上而下建立语法树的过程中完成对属性的计算。,L-属性文法,52,A,X1,Xj.,Xk,AX1.XjXk,A.a=Xj.x=,53,6.4L-属性文法和自顶向下翻译,L-属性文法：对任意产生式AX1X2Xn，其每个语义规则中的属性或者是综合属性，或者Xj是一个继承属性，且仅依赖与（1）X1X2Xj-1；（2）A的继承属性。,S-属性文法是L-属性文法的一个特例。,54,6.4L-属性文法和自顶向下翻译,判定下面属性文法是否是L-属性文法。,Q.i:=q(R.s),55,6.4.1翻译模式,属性文法是语言翻译的高级规范说明。翻译模式：描述文法符号属性的语义规则和计算次序。ETRRaddopTpr(addop.lex)R1|Tnumpr(num.val),56,翻译模式举例,ETRRaddopTpr(addop.lex)R1|Tnumpr(num.val),输入：952,E,T,R,R,R,9,Pr(9),T,Pr(),T,Pr(),5,Pr(5),2,Pr(2),深度优先遍历后输出：952,建立翻译模式的方法：,1、产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来；2、一个动作不能引用这个动作右边符号的综合属性；3、产生式左边非终结符的综合属性只能在它所引用的所有属性都计算出来以后才能计算。通常这类动作可放在产生式右端的末尾。,58,例：把下面属性文法修改为翻译模式：,59,SB.ps=10BS.ht=B.ht,BB1.ps=B.psB1B2.ps=B.psB2B.ht=max(B1.ht,B2.ht),60,6.4.2自顶向下翻译,消除左递归：规则PP|(1)PP(2)PP|,直接左递归：PP1|P2|Pm|1|2|n|(i)消除方法：P1P|2P|nPP1P|2P|mP|,在自顶向下分析过程中，在消除左递归的同时考虑属性计算，这样许多属性文法可以使用自顶向下来实现，适用综合和继承属性的计算。,61,EE1+TE.val:=E1.val+T.valEE1TE.val:=E1.valT.valETE.val:=T.valT(E)T.val:=E.valTnumT.val:=num.val,ETR.i:=T.valRE.val:=R.sR+TR1.i:=R.i+T.valR1R.s:=R1.sRTR1.i:=R.iT.valR1R.s:=R1.sRR.s:=R.sT(ET.val:=E.val)TnumT.val:=num.val,E,T,R,R,R,9,T,+,T,2,5,计算表达式952,.val=9,.val=5,.val=2,63,ETR.i:=T.valRE.val:=R.sR+TR1.i:=R.i+T.valR1R.s:=R1.sRTR1.i:=R.iT.valR1R.s:=R1.sRR.s:=R.iT(ET.val:=E.val)TnumT.val:=num.val,E,T.val=9,R.i=9,R.i=4,R.i=6,Num.val=9,T.val=5,+,T.val=2,Num.val=2,Num.val=5,计算表达式952,递归过程：综合属性计算,E.val,R.s,R.s,R.s,64,转换左递归翻译模式的一般方法：,AA1YA.a=g(A1.a,Y.yAXA.a=f(X.x),AXRRYR1R,带注释语法树,A.a=g(g(f(X.x),Y1.y),Y2.y),A.a=g(f(X.x),Y1.y),A.a=f(X.x),X,Y2,Y1,A,R.s,R.s,R.s,P155-156,R.i: