第6章 属性文法和语法制导翻译

1、第六章属性文法和语法制导翻译第六章属性文法和语法制导翻译 “语义分析”是编译程序最实质性的工作。语义分析程序在整个编译过程中，首次对源程序的语义做出解释，引起源程序发生质的变化，而词法分析和语法分析仅是对源程序形式上的识别和处理。 高级程序语言结构的形式化描述已经有比较成熟的技术，由于这种形式化描述的完善，使分析器的构造甚至自动构造是比较容易的。1 编译程序的语义分析涉及到语言的语义，语义形式化是个专门的研究课题. 形式语义学（如指称语义学、公理语义学、操作语义学等）的研究从20世纪60年代已经开始，并且在理论研究方面也有了重要的进展。但不论哪种方法，其本身的符号系统比较繁杂，其描述文本不易读

2、，尚不便借助这些形式系统自动完成语义处理任务。并且在工程实现和应用方面还有一定的差距。2 目前实际应用中较流行的语义描述和语义处理方法主要还是属性文法和语法制导翻译方法。但它仍不是一种形式系统，只是比较接近形式化。 语法制导翻译方法的实质是在语法分析过程中同时进行语义处理的翻译技术。这种方法使用属性文法为工具来说明程序设计语言的语义。3第六章属性文法和语法制导翻译第六章属性文法和语法制导翻译6.1 属性文法6.2 基于属性文法的处理方法6.3 S属性文法的自下而上计算6.4 L属性文法和自顶向下翻译6.5 自下而上计算继承属性46.1 属性文法一、基本概念1、属性广广义义：用以描述事物或人的特

3、征、性：用以描述事物或人的特征、性质质、品、品质质等等。等等。属属性文法中：代表性文法中：代表与与文法符文法符号号相相关关的信息，其信息的信息，其信息值值即即为属为属性性值值。例如：其类型、值、代码序列、符号表内容等。例如：其类型、值、代码序列、符号表内容等。56.1 属性文法（1 1）属性与变量一样，可以进行计算和传递。）属性与变量一样，可以进行计算和传递。（2 2）属性加工的过程即是语义处理的过程。）属性加工的过程即是语义处理的过程。（3 3）属性）属性 综合属性：用于综合属性：用于“自下而上自下而上”传递信息。传递信息。 继承属性：用于继承属性：用于“自上而下自上而下”传递信息。传递信息

4、。 66.1 属性文法2 2、语义规则、语义规则 为为文法的每一文法的每一个产个产生式配生式配备备的的属属性的性的计计算算规则规则，称为语义规则称为语义规则。3 3、属性文法、属性文法上下文无上下文无关关文法文法 + 语义规则语义规则 = 属属性文法性文法76.1 属性文法二、基本规则1、语义规则的形式：产生式产生式A A 的语义规则的一般形式为的语义规则的一般形式为b:=f(cb:=f(c1 1,c ,c2 2,c,ck k) )其中：其中：(1) f是一个函数；是一个函数； (2) 或者或者b A的综合属性的综合属性，且，且c1,c2,ck是是中文中文 法符号的属性；法符号的属性； (3)

5、 或者或者b 中某个文法符号的继承属性，中某个文法符号的继承属性，且且 c1,c2,ck是是A或或中任何文法符号的属性。中任何文法符号的属性。属性属性b依赖于属性依赖于属性c1,c2,ck86.1 属性文法2、VTVN的属性(1) VT 只有只有综综合合属属性，由性，由词词法分析器提供。法分析器提供。(2) VN 既既可有可有综综合合属属性也可有性也可有继继承承属属性，性， 文法文法开开始符始符号号S的所有的所有继继承承属属性作性作为属为属性性 计计算前的初始算前的初始值值。96.1 属性文法3、属性的计算/获得(1) 产产生式右生式右边边的的继继承承属属性性 产产生式左生式左边边的的综综合合

6、属属性性(2) 产产生式左生式左边边的的继继承承属属性性 产产生式右生式右边边的的综综合合属属性性由该产生式提供的计由该产生式提供的计算规则计算获得算规则计算获得由其它产生式的属性由其它产生式的属性规则计算或由属性计规则计算或由属性计算器的参数提供算器的参数提供106.1 属性文法例例6.1：C.d:=B.c+1A.b:=A.a+B.c 产生式 ABC 的规则：C.d右部继承属性右部继承属性A.b左部综合属性左部综合属性A.a左部继承属性左部继承属性B.c右部综合属性右部综合属性116.1 属性文法例例6.2：一个简单台式计算器的属性文法产生式语义规则LEnEE1+TETTT1*FTFF(E)

7、FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval12产生式语义规则DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.type:=realL1.in:=L.inL.in:=T.typeaddtype(id.entry,L.in)13产生式语义规则SXYZXxYyZzZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX.d:=2*X.cY.

8、f:=Y.e*3Z.g:=Z.h+1146.1 属性文法二、综合属性1 1、语法树中、语法树中, ,一个结点的综合属性的值由其子结点一个结点的综合属性的值由其子结点 的属性值确定。的属性值确定。2 2、通常使用自底向上的方法在每一个结点处使用语、通常使用自底向上的方法在每一个结点处使用语 义规则计算综合属性的值。义规则计算综合属性的值。S属性文法：属性文法：仅使用综合属性的属性文法仅使用综合属性的属性文法156.1 属性文法例例6.3：例6.2的表中定义的属性文法说明了一个台式计算器，该计算器读入一个可含数字、括号和+、*运算符的算术表达式，并打印表达式的值，每个输入行以n作为结束。假设表达式

9、为3*5+4，后跟一个换行符n。则程序打印数值则程序打印数值19。其带注释的语法树其带注释的语法树16三、继承属性1 1、语法树中、语法树中, ,一个结点的继承属性由此结点的父结一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。点和或兄弟结点的某些属性确定。6.1 属性文法、用继承属性来表示程序设计语言结构中的上下、用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。文依赖关系很方便。176.1 属性文法例例6.：带继承属性L.in的属性文法产生式语义规则DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.t

10、ype:=realL1.in:=L.inL.in:=T.typeaddtype(id.entry,L.in)18输入串输入串: real id1,id2,id3的带注释的语法树的带注释的语法树D DT.type=realT.type=realL.in=realL.in=realrealrealL.in=realL.in=realL.in=realL.in=real，id2id2id3id3，id1id1191 1、构造依赖图的方法、构造依赖图的方法: :输入串语法树依赖图语义规则的计算次序进行语义规则计算，得到翻译结果6.2 基于属性文法的处理方法2 2、遍历语法树的方法、遍历语法树的方法单词

11、符号串单词符号串语法分析语法分析语法分析树语法分析树遍历遍历计算计算3 3、可用一遍扫描实现属性文法的语义规则计算。、可用一遍扫描实现属性文法的语义规则计算。20一、依赖图1、定义：一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图。6.2 基于属性文法的处理方法212、依赖图的构造方法（1）构造依赖图以前，先为每一个包含过程调用的语义规则引入一个虚综合属性b，在每一个语义规则均写成b:=f（c1 1，c2 2， ck k）的形式；（2）在依赖图中为每一个属性设置一个结点；（3）若属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。6.2 基于属性文法的处理方

12、法22例例6.5：AXY A.a:=f(X.x,Y.y) X.i:=g(A.a,Y.y)6.2 基于属性文法的处理方法233、例题例例6.6：将下面的产生式应用于语法树中产生式语义规则EE1+E2 E.val:=E1.val+E2.valE EE E1 1 + + E E2 2 valvalval E.Val是从E1.val和E2.val综合得出6.2 基于属性文法的处理方法24产生式语义规则DTLTintTrealLL1,idLidaddtype(id.entry,L.in)T.type:=integerT.type:=realL1.in:=L.inL.in:=T.typeaddtype(i

13、d.entry,L.in)25D DT TL LrealrealL LL L，id2id2id3id3，id1id1a4：=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,a1026二、树遍历的属性计算方法1、方法A、前提：假设语法树已经建立起来了，且树中已 有如下信息：开始符号继承属性 终结符综合属性B、遍历：以某种次序遍历语法树，直至计算出所 有属性。 遍历方法：深度优先，从左到右遍历方法：深度优先

14、，从左到右6.2 基于属性文法的处理方法276.2 基于属性文法的处理方法2、算法While While 还有未被计算的属性还有未被计算的属性 dodoVisitNode(S)VisitNode(S)/ /* *S S是开始符号是开始符号* */ /procedure VisitNode(N:Node);procedure VisitNode(N:Node);beginbegin If N If N是一个非终结符是一个非终结符 thenthen / /* * 假设它的产生式为假设它的产生式为N NX X1 1XXm m * */ / for i:=1 to m do for i:=1 to m

15、 doif not Xif not Xi iVVT T then / then /* * 即即X Xi i是非终结符是非终结符 * */ /beginbegin 计算计算X Xi i的所有能够计算的继承属性的所有能够计算的继承属性; ; VisitNode(XVisitNode(Xi i) )end;end;计算计算N N的所有能够计算的综合属性的所有能够计算的综合属性endend注：只要文法的属性是非循环定义的，则每次扫注：只要文法的属性是非循环定义的，则每次扫描至少有一个属性值被计算出来。描至少有一个属性值被计算出来。28其中，其中，S有继承属性有继承属性a，综合属性，综合属性b；X有继承

16、属有继承属性性c，综合属性，综合属性d；Y有继承属性有继承属性e，综合属性，综合属性f；Z有继承属性有继承属性h，综合属性，综合属性g。 3、举例例例6.9：考虑下表所给的属性文法考虑下表所给的属性文法G G。产生式语义规则SXYZXxYyZzZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+16.2 基于属性文法的处理方法29S:a=0XYZxy(a)zS:a=0XYZ：h=0 g=1xy(b)z30S:a=0,b=0X:c=1 d=2Y:e=0 f=0Z：h=0 g=1xy(d)zS:a=0,b=0X:c=1 d=

17、2YZ：h=0 g=1xy(c)z316.2 基于属性文法的处理方法三、一遍扫描的处理方法1、特点在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。注：注：采用该处理方法采用该处理方法 ，当一个属性值不再用于计，当一个属性值不再用于计算其它属性值时，编译程序就不必再保留这个属算其它属性值时，编译程序就不必再保留这个属性值。如果需要，可把语义值存到文件中。性值。如果需要，可把语义值存到文件中。326.2 基于属性文法的处理方法2、相关因素：（1）所使用的语法分析方法 L-属性文法一遍扫描的自上而下分析 S-属性文法一遍扫描的自下而上分析（2）属性的

18、计算次序33上节课的内容：属性文法属性综合属性继承属性产生式+属性计算规则（语义规则）AX1XK A.a=Xi.x= 属性计算方法123 S-属性文法-6.3L-属性文法-6.4346.2 基于属性文法的处理方法例例2 2：构造表达式产生抽象语法树（Abstract Syntax Tree）的属性文法1、定义：在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示，这种经变换后的语法树称之为抽象语法树。注：注：抽象语法树中，操作符和关键字都不作为叶抽象语法树中，操作符和关键字都不作为叶 结点出现。结点出现。35抽象语法树内部结点外部结点操作符关键字标识符常数如：a+3*b的抽象语

19、法树+a*3b366.2 基于属性文法的处理方法2、如何建立表达式的抽象语法树（1）方法：通过为每一个运算分量或运算符号都建立一个结点来为子表达式建立子树； 运算符号结点的各个子结点分别表示该运算符号的各个运算分量的子表达式组成的子树的根。376.2 基于属性文法的处理方法（2）抽象语法树中每个结点可由包含几个域的记录来实现。 运算符号结点：一个域运算符号 其它域指向运算符号分量的结点的指针 结点：附加的域存放结点的属性值/指向属性值的指针。386.2 基于属性文法的处理方法（3）建立带有二目算符的表达式的抽象语法树结点的函数： mknode(op,left,right) mkleaf(id,

20、entry) mkleaf(num,ral) 每个函数均返回一个指向新建立结点的指针。396.2 基于属性文法的处理方法例例6.10：下面一系列函数调用建立了表达式下面一系列函数调用建立了表达式a-4+ca-4+c的抽的抽象语法树（如图）。在这个序列中，象语法树（如图）。在这个序列中，p p1 1,p ,p2 2, ,p ,p5 5是指向是指向结点的指针，结点的指针，entryaentrya和和entrycentryc分别是指向符号表中的标分别是指向符号表中的标识符识符a a和和c c的指针。的指针。 id + - idnum 4to entry for ato entry for c (1)

21、 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）如何设计产生表达式抽象语法树的属性文法？E E1+TE E1-TE TT (E)T idT num41产生式产生式语义规则语义规则E E1+TE E1-TE TT (E)T idT num为表达式建立抽象语法树的属性文法为表达式建立抽象语法树的属性文法T. nptr:=mkleaf(num,num.val)T. nptr:=mkleaf(id,id

22、.entry)T. nptr:=E. nptrE. nptr:=T. nptrE.nptr:=mkNode(+,E1. nptr,T. nptr)E. nptr:=mkNode(-,E1. nptr,T. nptr)42E nptrTnptrE nptrET nptrnumTnptrid+id ididnum4 4带注释的语法分析树带注释的语法分析树To entry for aTo entry for c436.3 S-属性文法的自下而上计算1 1、S-S-属性文法：属性文法： 只含综合属性的属性文法。只含综合属性的属性文法。2 2、S-S-属性文法的翻译借助于属性文法的翻译借助于LRLR分析

23、器来实现分析器来实现输入串输入串输出输出栈栈 分析表分析表a1 ai an #LR分析程序分析程序action gotoSm Xm s1 x1s0 #LR分析器443、对分析栈改造、对分析栈改造 状态栈 符号栈 属性栈S0 # -Sm-1 x x.valSm y y.val453、对分析栈改造、对分析栈改造 自底向上分析法中：栈存放已经分析过的子树的内容附加域存放综合属性 数组State：元素一个指向LR(1)分析表的指针(索引），指向表中某个状态 文法符号为隐含在State中而不需存在栈中数组Val：符号的属性值Stateval466.1 属性文法例例6.2：一个简单台式计算器的属性文法产生

24、式语义规则LEnEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval47状态栈 符号栈 属性栈S0 # -Sm-2 E E.valSm -1 + -考虑：考虑：EE1+T E.val:=E1.val+T.valSm T T.valS E E.val转换为：转换为：EE1+T valntop:=valtop-2+valtop48产生式语义规则LEnEE1+TETTT1*FTFF(E)Fdigi

25、tPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval把下面文法的语义规则转换为对属性栈的操作：把下面文法的语义规则转换为对属性栈的操作：Print(valtop)Valntop=valtop-2+valtopValntop=valtop-1Valntop=valtop-2*valtop496.11 举例L En E E1+TE TT T1*FT FF ( E )F digit 输入串 3*5+4n输入输入stateval产生式产生式3*

26、5+4n*5+4n33*5+4nF3F digit*5+4nT3T F5+4nT*3 +4nT*53 5+4nT*F3 5F digit+4nT15T T*F+4nE15E T4nE+15 nE+415 4nE+F15 4F digitnE+T15 4T FnE19E E+TEn19 L19L En产生式产生式语义规则语义规则E E1+TE E1-TE TT (E)T idT num为表达式建立抽象语法树的属性文法为表达式建立抽象语法树的属性文法T. nptr:=mkleaf(num,num.val)T. nptr:=mkleaf(id,id.entry)T. nptr:=E. nptrE.n

27、ptr:=mkNode(+,E1. nptr,T. nptr)E. nptr:=mkNode(-,E1. nptr,T. nptr) E. nptr:=T. nptrnptrntop:=mkNode(+,nptrtop-2, nptrtop)nptrntop:=mkNode(-,nptrtop-2, nptrtop)nptrntop=nptrtop-1nptrntop=mkleaf(id,id.entry)nptrntop=mkleaf(num,num.val)516.4 L-属性文法和自顶向下翻译对语法分析树进行一次深度优先遍历就能对语法分析树进行一次深度优先遍历就能计算出所有的属性。计算出

28、所有的属性。即即在自上而下建立语法树的过程中完成对属在自上而下建立语法树的过程中完成对属性的计算。性的计算。L-属性文法52AX1Xj.XkAX1.XjXkA.a=Xj.x=536.4 L-属性文法和自顶向下翻译L-属性文法：属性文法： 对任意产生式AX1X2Xn，其每个语义规则中的属性或者是综合属性，或者Xj是一个继承属性，且仅依赖与 （1）X1X2Xj-1； （2）A的继承属性。S-属性文法是L-属性文法的一个特例。546.4 L-属性文法和自顶向下翻译 判定下面属性文法是否是L-属性文法。产生式语义规则A LMA QRL.i:=l(A.i)M.i:=m(L.s)R.i:=r(A.i)A.

29、s:=f(Q.s)Q.i:=q(R.s)556.4.1 翻译模式 属性文法是语言翻译的高级规范说明。 翻译模式：翻译模式： 描述文法符号属性的语义规则和计算次序。 E TR R addop T pr(addop.lex) R1| T num pr(num.val) 56翻译模式举例E TR R addop T pr(addop.lex) R1| T num pr(num.val) 输入：952ETRRR9Pr(9) TPr() TPr()5Pr(5)2Pr(2)深度优先遍历后输出： 952建立翻译模式的方法：1、产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来；2、一个动作不能引用

30、这个动作右边符号的综合属性；3、产生式左边非终结符的综合属性只能在它所引用的所有属性都计算出来以后才能计算。通常这类动作可放在产生式右端的末尾。58例：把下面属性文法修改为翻译模式：产生式语义规则S BB B1B2B B1subB2B textB.ps=10S.ht=B.htB1.ps=B.psB2.ps=B.psB.ht=max(B1.ht,B2.ht)B1.ps=B.psB2.ps=shrink(B.ps)B.ht=disp(B1.ht,B2.ht)B.ht=text.h*B.ps59S B.ps=10 BS.ht=B.htB B1.ps=B.ps B1B2.ps=B.ps B2B.ht=

31、max(B1.ht,B2.ht)606.4.2 自顶向下翻译消除左递归：规则 P P| (1) P P (2) P P| 直接左递归： P P1| P2 | | Pm| 1 | 2 | | n | (i )消除方法： P 1P | 2P | | nP P 1P| 2P| | mP | 在自顶向下分析过程中，在消除左递归的同时考虑属性计算，这样许多属性文法可以使用自顶向下来实现，适用综合和继承属性的计算。61EE1+T E.val:=E1.val+T.valEE1T E.val:=E1.valT.valET E.val:=T.valT(E) T.val:=E.valTnum T.val:=num

32、.valET R.i := T.val R E.val:=R.sR+ T R1.i := R.i +T.val R1 R.s := R1.sR T R1.i := R.i T.val R1 R.s := R1.sR R.s := R.sT(E T.val:=E.val)Tnum T.val:=num.valE T R R R 9 T+ T 2 5计算表达式 952 .val=9 .val=5 .val=263ET R.i := T.valR E.val:=R.sR+ T R1.i := R.i +T.valR1 R.s := R1.sRT R1.i := R.i T.val R1 R.s := R1.sR R.s := R.i T(E