编译原理课件 第6章 属性文法及语法制导翻译

本章在编译程序中的地位

表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理1教学要求掌握：两种属性:综合属性，继承属性基于属性文法的处理方法---语法制导翻译方法2教学内容6.1属性文法综合属性，继承属性，语义规则，属性文法6.2基于属性文法的处理方法语法制导翻译，依赖图法计算属性，树遍历计算属性，一遍扫描的处理方法，抽象语法树3

CH.6属性文法和语法制导翻译在分析-综合模式的编译器中,语义分析是分析过程的最后一个步骤，只有在这一步才真正开始考虑程序语言的意义，并着手把它们翻译成某种中间代码。这一过程通常采用的方法是属性文法和语法制导翻译方法。语法制导翻译方法的基本思想是，根据翻译的需要设置文法符号的属性，用属性描述语法结构的语义，用属性的计算完成翻译。属性文法使文法符号属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，从而完成语义分析和翻译的任务。46.1属性文法属性文法,也称属性翻译文法或语法制导定义,是Knuth在1968年首先提出来的。属性：在上下文无关文法的基础上为每个文法符号X(终结符或非终结符)配备若干个相关的“值”---这些“值”就称为文法符号X的属性。属性值的设置和语法结构的语义以及翻译程序的需要有关。属性代表与文法符号相关语义信息，如类型、值、代码序列、符号表内容等5属性、语义规则、属性文法属性一般分为两类：综合属性和继承属性。属性和变量一样，可以在语法分析过程中进行计算和传递。语义规则：属性的计算规则。属性的加工和计算的过程即是语义处理的过程。属性文法：以一个上下文无关文法为基础,为每个文法符号引进一组属性，对文法的每个产生式都配备一组与之相关联的属性的计算规则(语义规则),这样得到的文法。属性文法是对上下文无关文法的推广。6属性文法、语义规则(1)属性文法的形式：产生式语义规则.

Ab:=f(c1,c2,…,ck)这里,f是一个函数,表示属性b依赖于属性c1,c2,…,ck，而且规定b:(1)b是A的一个综合属性并且c1,c2,…,ck是产生式右部文法符号的属性；或者(2)b是产生式右边某个文法符号的一个继承属性并且

c1,c2,…,ck是A或产生式右部任何文法符号的属性

。7属性文法的说明(1)P136(1)终结符只有综合属性,它由词法分析器提供例如digit.lexval

表示单词符号“数”的词法值

id.entry表示单词符号“标识符”的符号表入口(2)非终结符既可以有综合属性也可以有继承属性，在属性文法的语义规则中计算(3)关于属性计算的规定①文法的开始符号的所有继承属性作为属性计算前的初始值。②一般来讲，对出现在产生式AX1X2…Xn左边的非终结符A的综合属性和出现在产生式右部的符号Xi的继承属性都必须提供一个计算规则。8属性文法的说明(2)③与产生式AX1X2…Xn

相关联的属性计算不能有A的继承属性和Xi的综合属性的计算规则。④出现在产生式左边非终结符A的继承属性和出现在产生式右边符号Xi的综合属性由其它产生式的属性规则计算或者由属性计算器的参数提供。9属性文法、语义规则(2)属性文法的形式：产生式语义规则.

Ab:=f(c1,c2,…,ck)例如P137.表6.1的属性文法:

EE1+TE.val:=E1.val+T.val例如P139.表6.2的属性文法:

DTLL.in:=T.typeLL1,idL1.in:=L.in综合属性综合属性继承属性继承属性继承属性10例,P137.

假设：产生式语义规则ABCA.b:=A.a+B.cC.d:=B.c+1

A有综合属性b和继承属性aB有综合属性cC有继承属性d继承属性A.a和综合属性B.c在其他适当的地方计算。11语义规则所描述的工作语义规则所描述的工作可以是任何希望的翻译工作，如:属性计算、静态语义检查、符号表操作、中间代码生成、报告出错，等等。语义规则可能产生副作用(如产生代码)，也可能不是变元的严格函数b:=f(c1,c2,…,ck)，如某个规则给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段---这时认为定义了一个虚属性。12属性文法举例：P137.表6.1一个简单的台式计算器的属性文法。输入一个含+、*、(、)和数字的算术表达式(文法的句子),计算并输出其值,输入行以n结束。产生式语义规则LEn

Print(E.val)

EE1+T

E.val:=E1.val+T.valET

E.val:=T.valTT1*FT.val:=T1.val*F.valTF

T.val:=F.valF(E)

F.val:=E.valFdigit

F.val:=digit.lexval1.

非终结符E,T,F有综合属性val---表达式值2.

终结符digit有综合属性lexval---数的二进制值，由词法分析器提供3.注：同一个产生式的相同非终结符加上下标，以区分这些非终结符的属性值引用的二义性13两种属性：综合属性综合属性用于“自下而上”传递信息。综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。通常结合使用自下而上的分析方法在每一个结点处使用语义规则计算综合属性的值---由下层子结点的属性值计算上层父结点的综合属性值，随着自下而上语法分析的进行，最终可计算出开始符号的综合属性值。AX1X2…XnA.bX1.c1X2.c2…Xn.

ckAX1X2…Xnb:=f(c1,c2,…,ck)带注释的语法树14综合属性举例：例6.1综合属性的使用及其自下而上的计算过程P137.表6.1台式计算器的属性文法，输入一个表达式(以n结尾)，计算并打印其值。例如：输入表达式3*5+4n，输出数值19。P138.图6.1给出了输入串3*5+4n的带注释的语法树–属性化的语法树。综合属性X.val值随着自下而上语法分析的进行，自下而上的计算、传递和流动---在每次归约时执行语义规则，计算属性值，最终计算出开始符号的综合属性值，打印出来完成翻译。见下页图15digitlexvaldigitlexvaldigitlexvalFvalT1valFvalTval*E1valFvalTval+EvalLnPrint(E.val)翻译3*5+4n求表达式值=3=3=5=5=15=15=4=4=4=19=316两种属性：继承属性继承属性用于“自上而下”传递信息。继承属性：在语法树中，一个结点的继承属性由此结点的父结点和(或)兄结点的某些属性确定。可以用继承属性来表示程序语言结构中的上下文依赖关系。继承属性的计算可以结合自上而下的语法分析进行。A

X1…X

…XnA.ck

X1.c1…X.b…XnAX1X2…Xnb:=f(c1,c2,…,ck)17表6.2带有继承属性L.in的属性文法

产生式语义规则

DTLLin:=TtypeTintTtype:=integerTrealTtype:=realLL1,idL1

in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)

例6.2说明句的带有继承属性计算的属性文法T.type是综合属性---标识符的类型L.in为继承属性---传递类型信息18继承属性的使用和计算：例6.2继承属性的使用及其自上而下的计算过程P137.表6.2的属性文法，用继承属性L.in

为说明语句中的各个标识符提供类型信息。例如：说明语句reala,b,c;inti,j,k;T.type是综合属性,由说明语句中的关键字real/int确定,结合产生式Tint或Treal

赋值T.type:=integer或real。TintT.type:=integerTreal

T.type:=realT.typeintT.typereal19继承属性的使用和计算：例6.2续例6.2,

P137.表6.2属性文法，用继承属性in为说明语句中的各个标识符提供类型信息。L.in继承属性,在DTLL.in:=T.typeLL1,id

L1.in:=L.in中计算。D

T.type

L.inL.inL1.in，id

依赖于兄依赖于父Addtype(id.entry,L.in)把标识符的类型信息填入符号表,入口为id.entry---这个过程定义了一个虚属性。20图6.2说明语句

realid1,id2,id3

的带有继承属性的语法树继承属性in的值自上而下从左到右计算、传递和流动。三个L结点的L.in分别给出标识符id1、id2和id3的类型。过程addtype(id.entry,L.in)把id的类型填入符号表。id3T.type=realDL.in=realL.in=realrealL.in=real,id1id2,216.2基于属性文法的处理方法属性文法：产生式语义规则.

Aα

b:=f(c1,c2,…,ck)

语义规则的计算可以执行任何翻译动作。对输入串的翻译也就是根据语义规则进行计算得出结果。属性文法是比较抽象的翻译说明，隐藏了一些实现细节,主要是无须指明翻译时语义规则的计算次序。本节讨论语义规则的计算方法，指明属性文法中语义规则的计算次序，从而把语义规则改造为计算属性的语义程序，把静态的语义规则改写为可动态执行的语义动作---语法制导翻译方法。22语法制导翻译法语法制导翻译法：由源程序的语法结构所驱动的处理办法。这种处理方法是基于属性文法的处理过程：①对单词符串进行语法分析,构造带属性的语法树②根据需要遍历语法树,并在语法树的各结点处按语义规则进行计算即得翻译结果。P139.图6.3语法制导翻译的轮廓:

输入串语法树(带属性注释)语法分析深度优先树遍历对输入串的翻译结果进行计算拓扑排序语义规则计算次序结点属性间依赖关系的依赖图构造23所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

24一遍扫描的语法制导翻译一个具体的语法制导翻译的实现不一定非要按图6.3的轮廓不可。在某些情况下可用一遍扫描实现属性文法的语义规则计算---即在语法分析的同时完成语义规则的计算。无须明显地构造语法树或依赖图。此节以后的各节以及CH7.都讨论这种特殊方法---一遍扫描的语法制导翻译方法。一遍扫描的语法制导翻译轮廓:

输入串───翻译结果语法分析的同时完成语义规则的计算256.2.1依赖图语义规则建立了属性之间的依赖关系，这些关系可以用图来表示，这样的图称为属性依赖图。语法树结点属性的依赖图是一个有向图：结点：语法树结点的属性(综合属性或继承属性)有向边：属性的依赖关系，如果属性b依赖于属性c，即b:=f(c)，则:语义规则b:=f(c1,c2,…,ck)，b可能是一个虚综合属性(即没有b,f是一个过程)，其依赖图见右图。依赖图构造方法见P140.bcbc1ckc2…26依赖图：例6.3简例:下面属性文法的依赖图：AXYA.a:=f(X.x,Y.y)X.i:=g(A.a,Y.y)

例6.3:下面的属性文法的依赖图EE1+E2

E.val:=E1.val+E2.val语法树EE1+E2依赖图

P141.图6.4E.valE1.valE2.valA.aX.iX.xY.yA

XY27例6.4图6.5句子

realid1,id2,id3

的语法树及依赖图TLLid3Lid2Did1real,,4typein5L.in:=T.typein7L1.in:=L.inin9L1.in:=L.in3entry6addtype(id.entry,L.in)2entry8addtype(id.entry,L.in)1entry10addtype(id.entry,L.in)结点1、2、3是id.entry属性结点6、8、10代表虚属性有向边表示属性的依赖关系数字标识结点表示计算次序28良定义的属性文法对语义规则b:=f(c1,c2,…,ck)来说,只有在属性c1,c2,…,ck均已知的情况才可以使用来计算b。但，有时会出现一个属性对另一个属性的循环依赖关系。如果一属性文法不存在属性之间的循环依赖关系，那么该属性文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。例如设p，c1，c2都是属性，以下计算规则就无法对p求值。p:=f1(c1)c1:=f2(c2)c2:=f3(p)DAG图：良定义属性文法的依赖图，

无环有向图(DirectedAcyclicGraph)pc2c129依赖图法：属性的计算次序1.一个有向非循环图(DAG图)的拓扑序:是图中结点的任何顺序m1,m2,…,mk,使得有向边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj

是mi

到mj

的一条边，那么在序列中mi必须出现在mj

之前。2.一个依赖图(DAG图)的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语义规则b:=f(c1,c2,…ck)中的属性c1,c2,…ck在计算b以前都是可用的。30例6.5

P141.图6.5的依赖图的一个拓扑排序是：

1，2，3，4，5，6，7，8，9，10由此拓扑序可以得到下面的程序(an代表与n有关的属性),该程序把3个标识符a,b,c的类型信息(real)填入符号表中每个标识符对应的符号表项中。程序

a4:=real;语义规则

T.type:=reala5:=a4;L.in:=T.typeaddtype(id3entry,a5);虚属性6a7:=a5;L1.in:=L.inaddtype(id2entry,a7);虚属性8a9:=a7;L1.in:=L.inaddtype(id1entry,a9);虚属性10依赖图法属性的计算次序：例

31属性文法说明的语法制导翻译是很精确的：(1)基础文法用于建立输入串的语法分析树(可带属性注释);(2)构造对应语法树的依赖图;(3)对依赖图进行拓扑排序;(4)从拓扑序得到计算语义规则的次序;(5)按此次序计算语义规则便得到输入串的翻译结果。依赖图法属性的计算次序：说明

326.2.2树遍历的属性计算方法通过语法树遍历计算属性值的方法有很多种。这些方法都假设：1.语法树已经建立起来了，并且树中已带有开始符号的继承属性和终结符的综合属性。2.然后以某种次序遍历语法树，直至计算出所有结点的属性值。最常用的遍历方法是深度优先，对语法树自上而下从左到右遍历的方法。对遍历到的结点计算其所有能够计算的属性值。可能需要使用多次树遍历，直到把所有的结点的所有属性都计算出来。P142.有一个深度优先树遍历的算法，对任何良定义的属性文法进行属性的计算。用例子说明。33深度优先树遍历计算属性：例6.6

P143.表6.3的属性文法。属性S.a(=0)继,S.b综;X.c继,X.d综;Y.e继,Y.f综;Z.h继,Z.g综图6.6产生式语义规则SXYZX.c:=Z.gY.e:=S.bZ.h:=S.aS.b:=X.d-2Xx

X.d:=2*X.cYy

Y.f:=Y.e*3Zz

Z.g:=Z.h+1xyz.h=0第一次遍历S.a=0

XYZ.g=1.d=2.c=1.b=0第二次遍历.e=0.f=0第三次遍历346.2.3一遍扫描的处理方法与树遍历的属性计算方法不同，一遍扫描的处理方法是在语法分析的同时计算属性值。这种属性计算方法与两个因素密切相关:1.所采用的语法分析方法(自上而下或自下而上)。2.属性的计算次序，即语法分析到什么时候计算属性。一遍扫描的处理方法语义规则执行的时间:1.在自上而下语法分析中，若一个产生式匹配输入串成功时执行与此产生式相应的语义规则。2.在自下而上语法分析中，当一个产生式被用于进行归约时，此产生式相应的语义规则就被计算。35一遍扫描的处理方法按一遍扫描的编译程序模型来理解语法制导翻译方法，直观上说是为基础文法的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。一遍扫描的属性计算方法是语法分析工作和语义规则的计算穿插进行。但以语法分析作主导。S-属性文法(仅含综合属性的属性文法)可用于一遍扫描的自下而上分析。L-属性文法(含有继承属性的属性文法)可用于一遍扫描的自上而下分析。366.2.4抽象语法树语法制导翻译以语法树作基础,实际上,语法树可以作为一种合适的中间语言形式。现在对语法树进行改造，去掉那些对翻译不必要的信息，将语法树进行抽象---抽象语法树。在表达式的抽象语法树中，运算符、关键字不作叶子结点而作为内部结点，叶子结点只是运算量。抽象语法树也可以属性化，给结点加上属性变成带附注的抽象语法树。语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行，采用的基本方法是一样的。37抽象语法树：简例例，为下面文法的句子a-4+c

建立抽象语法树。EE+T|E－T|TT(E)Tid|num为每个运算量或运算符号都建立一个结点。可以根据表达式的运算顺序自下而上的构造---手工构造。a－+c4抽象语法树运算符作内部结点id(a)EE－TE+TTnum(4)id(c)语法树38抽象语法树的实现抽象语法树中的每一个结点可以由包含几个域的记录来实现；有向边用指针实现。在一个运算量对应的结点(叶结)中,一个域标识运算量，另一个域是该运算量的属性值(或指针)。在一个运算符号对应的结点中,一个域标识运算符号，其它域包含指向运算分量的结点的指针。运算符号通常叫做这个结点的标号。进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值(或指向属性的指针）。numvalid.op..Toentryofid右子树根结左子树根结39建立表达式的抽象语法树使用的函数,这些函数返回新建立结点的指针。1.mknode(op,left,right)

建立一个运算符号结点，标号是op,两个域