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

第六章属性文法和语法制导翻译源程序表格管理词法分析语法分析语义分析与中间代码产生优化器目标代码生成器单词符号语法单位中间代码中间代码目标代码出错处理语义分析是编译程序的第三个阶段，这是编译程序最实质性的工作。一个源程序在经历了词法分析和语法分析之后，表明它在书写和语法结构上是正确的。然而，语法的正确并不能保证语义的正确。粗略地说，语义分析阶段就是分析源程序的含义，并做相应的语义处理，生成目标代码或某种形式的中间代码。目前大多数编译程序普遍采用的一种语义分析方法——语法制导翻译方法语义分析的任务是根据语义规则对识别出的各种语法成分分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。具体来说，其主要任务包括以下几部分。(1)确定类型。即确定标识符所对应数据对象的数据类型，这部分工作有时也由词法分析来完成。(2)语义检查。动态语义检查在运行时进行，需要生成相应的目标代码；而静态语义检查则在编译时完成，它主要涉及以下四个方面。

①类型检查。按照语言的类型规则，对运算及运算对象进行类型检查，检查运算的合法性与运算对象类型的一致性，必要时作相应的类型转换。语义分析任务②控制流检查。通过检查控制流语句，以确保控制语句有合法的转向点。例如，c语言中break语句的作用是使程序跳离包括该语句的最小的switch、while或for语句，如果不存在这样的语句，则应报错。③一致性检查。很多情况下要求对象只能被定义一次。例如，c语言中规定一个标识符在同一作用域中只能被说明一次，同一switch语句的case语句标号不能相同，枚举类型的元素不能重复出现等。④相关名字检查。有的语言中有时规定，同一名字必须出现两次或多次。例如，Ada语言中，循环或程序块可以有两个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。语义分析任务

(3)识别含义。如果静态语义正确，则进行真正的翻译，即识别程序中各种语法成分的含义，并做相应的语义处理。生成相应的中间代码或直接生成目标代码。语义分析程序是在词法分析和语法分析之后，可以由语法分析程序直接调用相应的语义。语义分析任务属性文法在上下文无关文法基础上，赋予每个文法符号以一定属性，并规定文法的每个产生式对相关属性的运算规则，这些附加了一组属性和运算规则的文法称为属性文法。属性的运算规则又称为语义规则或语义子程序属性的值是由语义规则计算出来的，而语义规则的计算可以产生中间代码或目标代码属性的表示在属性文法中，文法符号X的属性t常用X.t,例如，可以用X.val,X.type,X.addr分别表示X的值、类型和地址。但是对于特定的属性文法，每个文法符号只可能涉及部分属性。例如，对于表达式文法G（E）：EE+T|TTT*F|FF(E)|i如果只想计算表达式的结果，则只关心各文法符号的值属性，因此E、T、F，都有一个整数值的属性，分别表示为E.val、T.val、F.val，而对于终结符i，由于它是词法分析传过来的整数，设其内部值用lexval来表示，则i的属性表示i.lexval。至于其他终结符号+、*、(、)等所代表的都是语义动作，这些语义动作将在语义规则中反映出来。语义规则表示一个产生式对应的语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关。不同的产生式对应不同的语义规则，不同的分析目标也对应不同的语义规则。例6.1：文法G（E）：EE+T|TTT*F|FF(E)|i

以表达式求值为目标，构造各产生式的语义规则。因为语义分析的目的是求算术表达式的值，不产生中间代码，因而相应的语义子程序只需进行值的运算和传递，各产生式的语义规则如下表所示。产

生

式

语

义

规

则

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

i

F.val:=i.lexval语义规则表示语法制导翻译的过程在文法中，文法符号有明确的语义，文法符号之间有确定的语义关系。用属性描述语义信息，用语义规则描述属性间的关系，将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。这就是语法制导翻译的思想。具体实现时，语法制导翻译分为以下两种处理方法。(1)属性文法，即对每个产生式编制一个语义分析子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义分析子程序实现语义检查与翻译。这种实现方案隐藏了语义规则的计算次序等细节，不必规定翻译顺序。(2)翻译模式，即在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。不论是应用属性文法方式还是应用翻译模式，翻译过程都是类似的，可分为以下几步：(1)分析输入符号串，建立语法分析树；(2)从分析树得到描述结点属性间依赖关系的依赖图，由依赖图得到语义规则的计算次序；(3)进行语义规则的计算，得到翻译结果。然而，一个具体的实现并不一定按照上述步骤进行。例如，当编译程序应用语法制导定义一遍扫描实现语义规则计算时，它就在语法分析过程中同时完成语义规则的计算，而不产生明显的语法分析树或依赖图。由于单遍编译的效率较高，所以被一些编译程序所采用。语法制导翻译的过程属性分类属性文法是上下文无关文法的推广，其中每一个文法符号都有一个与之相关联的属性集，它分成两个子集，分别叫做该文法符号的综合属性集合和继承属性集合。如果我们把分析树上的结点看成是保存对应文法符号的属性的记录，那么属性对应记录的域。属性可以表示任何东西：串、数、类型、内存单元，或其他想表示的内容。分析树结点的属性值由该结点所用产生式的语义规则定义。从分析树上来看，一个结点的综合属性值是从其子结点的属性值计算出来的，而继承属性值则是由该结点的兄弟结点和父结点的属性值计算出来的。属性分类设在属性文法中，对应于每个文法产生式A

都有与之相关联的一套语义规则，规则形式为b:=f(c1,c2,…,ck)

，其中，f是一个函数，b和c1,c2,…,ck

是产生式文法符号的属性。具体分为以下两种情况：(1)如果b是A的属性，c1,c2,…,ck是产生式右部文法符号的属性或A的其他属性，那么b叫做文法符号A的综合属性；(2)如果b是产生式右部某个文法符号X的属性，c1,c2,…,ck是A或产生式右部任何文法符号的属性，那么b叫做文法符号X的继承属性。在这两种情况下，我们都说属性b依赖于属性c1,c2,…,ck。在语法制导定义中，我们把其中的文法称为基础文法。终结符：只有综合属性，由词法分析器提供非终结符：既可有综合属性又可有继承属性；文法开始符：所有继承属性作为属性计算前的初始值。综合属性综合属性在实际中被广泛地应用。只使用综合属性的语法制导定义称为s属性定义。在s属性定义的语法分析树中，可以使用自底向上的方法在每一个结点处使用语义规则来计算综合属性值，即从叶结点到根结点进行计算。注释分析树每个结点的属性值都标注出来的分析树叫做注释分析树对例6．1中的表达式文法G[E]进行拓广，增加一个产生式L

En(n代表换行符)，并附以相应的语义规则来计算并打印表达式的值，如下表所示。产

生

式

语

义

规

则

L

E

n

print(E.val)

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:=digit.lexval每个产生式左部的E、T、F的属性值的计算来自它右部的非终结符，都是综合属性。单词i仅有综合属性，它的值是由词法分析程序提供的。和产生式L

En相联的语义规则是一个过程，打印由E产生的表达式的值。L在语义规则中没有出现，可以理解L的属性是空的或是虚的。用分析树计算表达式2+3*4i.lexval=4LE.val=14T.val=12E.val=2T.val=2F.val=2i.lexval=2T.val=3+*F.val=3F.val=4i.lexval=3nS属性文法仅仅使用综合属性的文法产

生

式

语

义

规

则

L

E

n

print(E.val)

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

i

F.val:=i.lexvalS属性文法的特点仅仅使用综合属性的文法语法树中每个节点的综合属性值由其子节点的属性值决定属性值的计算采用自下而上的方法计算实例：8+5*2\n语法分析树iLETETFiT+*FFin分析树各结点属性的计算可以自下而上地完成i.lexvalLE.valnT.valE.valT.valF.vali.lexvalT.val+*F.valF.vali.lexval分析树各结点属性的计算可以自下而上地完成i.lexvalLE.valnT.valE.valT.valF.vali.lexval

=8T.val+*F.valF.vali.lexval分析树各结点属性的计算可以自下而上地完成digit.lexvalLE.valnT.valE.valT.valF.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval分析树各结点属性的计算可以自下而上地完成digit.lexvalLE.valnT.valE.valT.val

=8F.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval分析树各结点属性的计算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval分析树各结点属性的计算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val+*F.valF.valdigit.lexval

=5分析树各结点属性的计算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val+*F.val

=5F.valdigit.lexval

=5分析树各结点属性的计算可以自下而上地完成digit.lexvalLE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.valdigit.lexval

=5分析树各结点属性的计算可以自下而上地完成digit.lexval

=2LE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.valdigit.lexval

=5分析树各结点属性的计算可以自下而上地完成digit.lexval

=2LE.valnT.valE.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.val

=2digit.lexval

=5分析树各结点属性的计算可以自下而上地完成digit.lexval

=2LE.valnT.val

=10E.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.val

=2digit.lexval

=5分析树各结点属性的计算可以自下而上地完成digit.lexval

=2LE.val=18nT.val

=10E.val

=8T.val

=8F.val

=8digit.lexval

=8T.val

=5+*F.val

=5F.val

=2digit.lexval

=5例题6.2例6.2为文法G[S】：S(L)|aLL，S|S写一个语法制导定义，输出括号的对数。例如对于句子(a，(a，a))，输出是2。解：首先对文法进行拓广，增加一个产生式S’

S，以使输出动作唯一，保证正确输出结果。然后分析题目的要求，求出所有括号的对数。我们从后向前依次查看每个产生式：当使用LS归约时，L中的括号对数等于S中的括号对数；当使用LL1，S归约时，Ll与S用“，”连接，因此L中的括号对数等于S中的括号对数与L1中的括号对数之和；当使用Sa归约时，S中的括号对数等于O；当使用S(L)归约时，S中的括号对数等于L中的括号对数加1：当使用S’S归约时，输出S的括号对数。在此分析的基础上，为S和L引入综合属性num记录括号的对数，很容易就能写出各个产生式的语义规则了，如下表所示。例6.2为文法G[S】：S’

SS(L)|aLL，S|S产生式

语义规则

S’Sprint(S.num)S(L)S.num=L.num+1SaS.num=0LL1，SL.num=L1.num+S.numLSL.num=S.num从语法分析树上来看，一个结点继承属性的值是由其父结点或兄弟结点的某些属性来决定的。用继承属性来表示程序设计语言上下文的结构关系是很方便的。继承属性例6.3：描述说明语句中各种变量类型的文法G[D]如下：D

TL

T

int

T

real

L

L1,

id

L

id构造各产生式的语义规则，将每个变量名及其类型信息填入符号表。

举例，继承属性用来给说明语句中的各个标识符传递类型信息。产生式

语义规则

D

TL

L.in:=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)

举例，继承属性用来给说明语句中的各个标识符传递类型信息。这个例子的文法所定义的说明语句是由int或real开头，后跟一个标识符表，标识符之间由逗号分隔。非终结符号T有一个综合属性type，它的值是由说明中的关键字int或real来确定的。语义规则L．in=T．type对应于产生式DTL，它把说明中的类型赋给继承属性L.in，这些规则使用继承属性L.in把这个类型信息在分析树中向下传递。与L的产生式对应的语义规则调用过程

addtype

，把标识符的名字及其类型信息填写在符号表中，属性entry代表标识符在符号表中的入口地址。继承属性L．in在说明中为各个标识符提供了类型信息。intid1,id2,id3的注释分析树DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,产生式

语

义

规

则

D

TL

L.in:=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)

使用继承属性的地方很多，例如可以利用继承属性来跟踪一个标识符是出现在赋值符号的右边还是左边，以确定是需要这个标识符的值还是地址。对于一个语法制导定义，可以通过改写使其只具有综合属性，但改写之后，有时会使得文法失去了简洁和直观，反而不如使用带继承属性的语法制导定义自然。例题6.4下面是产生字母表={0,1,2}上数字串的一个文法：

SDSD|2 D0|1写一个属性文法（语法制导定义），判断它接受的句子是否为回文。解：

首先对文法进行拓广，增加一个产生式S’

S，引入S的综合属性boolean记录句子为回文，引入D的综合属性val记录其值，则其属性文法如下：S

S print(S.boolean)SD1S1D2S.boolean=(D1.val==D2.val)andS1.boolean

S2 S.boolean

=trueD0 D.val=0D1 D.val=1例题6.5为下面文法写一个属性文法，用S的综合属性val给出下面文法中S产生的二进制数的十进制值。例如，输入101.101时，S.val:=5.625。不得修改文法，但属性使用没有限制。 SL.R|L LLB|B RBR|B B0|1解：将二进制数转换为十进制数，其方法是按权展开，引入综合属性val记录S,L,R的十进制值，引入综合属性c记录了B的二进制位的结果值，所以其属性文法如下：SL.R SL

LL1B LB

RBR1

RB

B0B1S.val:=L.val+R.valS.val:=L.val

L.val:=L1.val

2+B.cL.val:=B.c

R.val:=(R1.val+B.c)/2R.val:=B.c/2B.c:=0B.c:=1S.LLBLBBRRBRBB例题6.6为文法S->(L)|aL->L,S|S写一个属性文法，它输出括号嵌套的最大深度S->(L)|aL->L,S|SSa(L)L,SSS深度的定义:a,(a),((a),(a)),(((a),(a)),(a))S->(L)S.d=L.d+1S->aS.d=0L->L,SL.d=MAX(L.d,S.d)L->SL.d=S.d6.2基于属性文法的处理方法

——属性的计算方法输入串语法树依赖图语义规则的计算语法制导翻译过程语法制导翻译可以不遵循这一过程。语法制导翻译也可以在语法分析阶段完成，例如S-属性文法和L-属性文法属性依赖图对于一个输入符号串，在建立注释分析树后，可以构造一个有向图，用来描述分析树结点的属性间的互相依赖关系。如果分析树一结点的属性b依赖某个结点的属性c，那么属性b的语义规则的计算必须在属性c的语义规则的计算之后。这样由依赖图可以得到语义规则的计算次序，据此进行语义规则的计算便得到了翻译结果。属性依赖图的构造为了构造属性依赖图，需要对那些由过程调用组成的语义规则引入虚拟综合属性b，使得每条语义规则都能写成b=f(c1，c2，…，ck)的形式。依赖图构造的基本思想是：对分析树上每个结点的所有属性都构造一个结点，如果属性b依赖于属性c，则从c的结点到b的结点作一条有向边。在语法树的基础上完成针对语法树中的每一个文法符号的每一个属性，建立一个节点；对于涉及到过程调用组成的语义规则，建立一个虚节点根据语义规则中关于属性的计算规则的定义，在节点之间建立连线，描述属性之间的依赖关系。例如，若X.x=f(A.a

B.b)是产生式XAB的语义规则，它定义了依赖于属性A.a和B.b的综合属性X.x。如果把这个产生式用于分析树，那么在依赖图上有三个结点X.x、A.a和B.b，并且结点A.a和B.b分别有一条有向边到结点X.x,如果产生式XAB有语义规则A．a=g(X.x，B.b)，那么在依赖图上，结点X.x和B.b分别有边到结点A.a，因为A.a依赖于X.x和B.b。intid1,id2,id3的分析树的依赖图其中虚线表示的是分析树；依赖图的结点用数表示,

边用实线表示。

,D

intTid3LLLid2id1,1

entry102

entry3

entryin

98in

76in

54

type产生式

语

义

规

则

D

TL

L.in:=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)

根据产生式DTL的语义规则L.in=T.type，有L.in依赖于T.type，所以从结点4的T.type到结点5的L.in构造一条边。根据产生式LL1,id的语义规则L1.in=L.in，有L1.in依赖于L.in，因此可以分别构造到达结点7和9的两条向下的边。根据产生式Lid的语义规则addtype(id.entry,L.in),建立虚拟属性结点6，8，10。属性计算次序拓扑排序：是无环有向图的结点的一种排序。这种排序满足：依赖图中的边只会从该次序中先出现的结点到后出现的结点。例如，在下图所示的依赖图中，每条边从序号较低的结点到序号较高的结点，因此结点l，2，…，10构成该图的一个拓扑排序。我们把依赖图中序号为n的结点的属性写成an，那么从这个拓扑排序可以得下面的程序：D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54typea4=integera5=a4Addtype(id3.entry,a5)a7=a5Addtype(id2.entry,a7)a9=a7Addtype(id1.entry,a7)6.2.2树遍历的属性计算方法通过树遍历计算属性值得方法很多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有的属性。最常用的遍历方法是深度优先，从左到右的遍历方法。While还有未被计算的属性do

visitNode(s)/*S是文法开始符号*/Procedurevisitnode(N:node);BeginifN是一个非终结符then{对于该非终结符的候选式中的每一个文法符号X{ifX是非终结符{计算该非终结符的所有继承属性；

visitnode（该非终结符）}}}计算N的所有能够计算的综合属性end

,D

intTid3LLLid2id1,下面算法可对任何无循环的属性文法进行计算6.2.3一遍扫描的处理方法与树遍历的属性计算方法不同，一遍扫描的方法是在语法分析的同时计算属性值。如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，所谓语法制导翻译法，直观上说是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则.在自上而下的语义分析中,若一个产生式匹配输入串成功,或者在自下而上分析中,当一个产生式被用于进行归约时,此产生式相应的语义规则就被计算,完成有关语义分析和代码生成的工作.为了适应语义分析的需要，把语法规则中对语义无关紧要的具体规定去掉，剩下来的本质性的东西叫做抽象语法。在不同的语言中赋值语句有不同的写法，如

x=y；x=y；yx；等，但本质是一样的，因此可用抽象形式：

assignment(variable,expression)把前面各种具体形式统一起来，把assignment看作运算符号，把expression和variable看作它的两个运算分量。与此相应可以使用抽象语法树来反映抽象的语法结构，也称作语法结构树，或结构树。而分析树是反映具体语法结构的。抽象语法树是分析树的抽象形式，或压缩形式，它把分析树中对语义无关紧要的成分去掉。语法树中的每一个结点表示一个运算符号，各子结点表示运算分量。6.2.4抽象语法树(自学)抽象语法树是分析树的浓缩表示：算符和关键字是作为内部结点。

语法制导翻译可以基于分析树，也可以基于抽象语法树抽象语法树的例子：if-then-elseBS1S2+*258抽象语法树S->ifBthenS1elseS28+5*2构造抽象语法树的语法制导定义建立表达式的语法树与把表达式翻译成后缀形式类似。我们通过为每一个运算对象或运算符都建立一个结点来为子表达式建立子树。运算符结点的各子结点分别是表示该运算符的各个运算对象的子表达式组成的子树的根。语法树中的每个结点都是由包含几个域的记录来表示的。对于运算符结点，其中一个域标识运算符，其他域包含指向运算对象的结点的指针。运算符通常叫作这个结点的标号。在翻译时，语法树中的结点可能会用附加的域来存放结点的属性值(或指向属性值的指针)。下面定义一些函数用来建立带有二元运算符的表达式的语法树结点。每个函数都返回一个指向新建结点的指针。

(1)mknode(op,left,right)：建立一个运算符号结点，其中标号是op，两个域left和right是分别指向左右运算对象结点的指针。

(2)mkleaf(id,entry)：建立一个标识符结点，由标号id标识，域entry是指向标识符在符号表中的相应表项的指针。

(3)mkleaf(num，val):建立一个数结点，标号为num，域val用于存放数的值。构造抽象语法树的语法制导定义产生式语

义

规

则

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,

T.nptr)

ET

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,

F.nptr)

T

F

T.nptr:=F.nptr

F(E)

F.nptr:=E.nptr

Fid

F.nptr:=mkleaf

(id,id.entry)

Fnum

F.nptr:=mkleaf

(num,num.val)

下表是一个为包含+和*的表达式构造语法树的S属性定义。语义规则中调用函数mknode和mkleaf，非终结符E、T和F的综合属性nptr是用来记录函数调用返回值的指针。a+5*b语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnum+*id指向符号表中b的入口id指向符号表中a的入口num5E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,

T.nptr)

ET

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,

F.nptr)

T

F

T.nptr:=F.nptr

F(E)

F.nptr:=E.nptr

Fid

F.nptr:=mkleaf

(id,id.entry)

Fnum

F.nptr:=mkleaf

(num,num.val)a+5*b的语法树的构造（红色为抽象语法树）E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口6.3S属性文法的自下而上计算

要建立一个通用的语法制导定义的翻译器是很困难的，但是可以针对某一类的语法制导定义给出其翻译的实现方案。介绍只含有综合属性的语法制导定义，即S属性定义和只带有继承属性的语法制导定义即L属性定义的实现。

因为S属性定义只有综合属性，所以可以在自底向上的语法分析过程中，对输入符号串进行语法分析的同时，实现对综合属性的计算。分析器可以把文法符号的综合属性值放在它扩充分析栈里，每当归约时，根据出现在栈顶的产生式右部符号的属性来计算左部符号的综合属性。

6.3S属性文法的自下而上计算在具体实现时，s属性定义的翻译器可以借助像Yacc那样的LR分析器来实现，通过扩充LR分析器的分析栈，在栈中增加一个域来保存综合属性值。扩充后的分析栈包括状态数组state和值数组val，如图所示。其中，state表示分析栈中的状态，val表示属性值。如果第i个状态所涉及的文法符号是A，则用val[i]保存分析树中对应A的结点的属性值。栈顶由指针top指示，并假定综合属性刚好在每步归约前计算。若产生式AXYZ的语义规则是A.a=f(X.x，Y.y，Z.z)，则在XYZ

归约成A之前，属性Z.z的值在val[top]中，Y.y的值在val[top-1]中，X.x的值在val[top-2]中。归约后，top的值减2，A对应的状态保存在state[top](即x原来的位置)中，综合属性的值A.a放进val[top]中。......ZZ.zYY.yXX.x......栈statevaltop台式计算器的语法制导定义改成栈操作代码

......ZZ.zYY.yXX.x......栈statevaltop产

生

式

代码段

L

E

n

print(E.val)

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:=digit.lexval台式计算器的语法制导定义改成栈操作代码

......ZZ.zYY.yXX.x......栈statevaltop产

生

式

代码段

L

E

n

print(val[top1])

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:=digit.lexval台式计算器的语法制导定义改成栈操作代码

......ZZ.zYY.yXX.x......栈statevaltop产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

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:=digit.lexval台式计算器的语法制导定义改成栈操作代码

......ZZ.zYY.yXX.x......栈statevaltop产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

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:=digit.lexval台式计算器的语法制导定义改成栈操作代码

产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval......ZZ.zYY.yXX.x......栈statevaltop台式计算器的语法制导定义改成栈操作代码

产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval......ZZ.zYY.yXX.x......栈statevaltop台式计算器的语法制导定义改成栈操作代码

产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

val

[top2]

:=val

[top1]

F

digit

F.val:=digit.lexval......ZZ.zYY.yXX.x......栈statevaltop台式计算器的语法制导定义改成栈操作代码

产

生

式

代码段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

val

[top2]

:=val

[top1]

F

digit

......ZZ.zYY.yXX.x......栈statevaltop输入3*5+4n所做的移动6.4L属性定义的自上而下计算S属性定义的翻译可以通过扩充LR分析器，在语法分析的同时进行翻译，那么这种边分析边翻译的方式是否适用于有继承属性的情况呢?

当在语法分析的同时进行翻译时，对属性的计算顺序一定受到语法分析时所建立语法分析树中结点顺序的制约。不管是自顶向下分析还是自底向上分析，分析树的结点都是自左向右生成。这样我们不妨设想，如果属性信息出现的顺序是自左向右流动。那么就有可能在分析的同时完成属性计算。下面我们按这种想法定义L属性定义，L代表左(left)，因为属性信息是从左向右出现的。*L属性文法如果每个产生式AX1

X2…Xn

的每条语义规则计算的属性是A的综合属性；或者是Xj

的继承属性，1

j

n,但它仅依赖：（1）该产生式中Xj左边符号X1,X2,…,Xj-1的属性；（2）A的继承属性。则称其是L属性文法。显然，S属性文法属于L属性文法，因为(1)和(2)仅对继承属性进行限制。变量类型声明的语法制导定义是一个L属性定义

产生式

语

义

规

则

D

TL

L.in:=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)

D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54typeL属性文法中属性值的计算特点在自上而下分析中进行属性计算的问题D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54type非L-属性文法的例子产生式语义规则A->LML.i=l(A.i)M.i=m(l.s)A->QRR.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)翻译模式：适合于语法制导翻译的另一种描述方式特点：翻译方案中包含以下内容： 基础文法 文法符号的属性 关于语义动作的定义，定义了语义动作执行的时间语义动作的表示：在产生式的右部的任何地方，用{}，实现动作和分析的交叉表示6.4.1翻译模式翻译模式语义动作的执行时间： Aa{……}b翻译方案示例：将中缀表达式翻译成后缀表达式 E

TR

R

addop

T{print(addop.lexeme)}R1|

Tnum{print(num.val)}例把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+52，则输出是85+2。

E

TR

R

addop

T{print(addop.lexeme)}R1|

Tnum{print(num.val)}E

TRnum{print(8)}

R

num{print(8)}addopT{print(+)}Rnum{print(8)}addopnum

{print(5)}{print(+)}R{print(8)}{print(5)}{print(+)}

addop

T{print()}

R{print(8)}{print(5)}{print(+)}{print(2)}{print()}只保留翻译方案设计应注意的问题基本原则：动作在引用属性时，属性的值应该是已知的实现方案：（1）当只有综合属性时，可以把语义动作放在产生式的最后D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54type产生式

语

义

规

则

D

TL

L.in:=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)

翻译方案设计应注意的问题（2）如果有继承属性产生式右部的文法符号的继承属性必须在先于这个符号的动作中计算一个动作不能引用该动作右边符号的综合属性左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。D

intT,id3LLLid2id1,1entry102entry3entryin98in76in54type产生式

语

义

规

则

D

TL

L.in:=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)

翻译模式示例构造抽象语法树的翻译模式E->E+TE->T{E.nptr=makenode(+,E1.nptr,T.nptr)}{E.nptr=T.nptr}翻译方案示例：将中缀表达式翻译成后缀表达式E

TR R

addop

T{print(addop.lexeme)}R1|Tnum{print(num.val)}8+52Enum{print(num.val)}TRaddop

T{print(addop.lexeme)}R1num{print(num.val)}翻译模式示例为文法S->(L)|aL->L,S|S写一个翻译模式，它输出每个a的嵌套深度。例如对句子(a,(a,a)),输出的结果是1，2，2基本原则：动作在引用属性时，属性的值应该是已知的实现方案：（1）当只有综合属性时，可以把语义动作放在产生式的最后（2）如果有继承属性产生式右部的文法符号的继承属性必须在先于这个符号的动作中计算一个动作不能引用该动作右边符号的综合属性左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。S->(L)|aL->L,S|S写一个翻译模式，它输出每个a的嵌套深度。例如对句子(a,(a,a)),输出的结果是1，2，2分析：由于a的嵌套深度不是由a本身决定的．所以一定得用继承属性。另外，a的嵌套深度从a左边的部分足以判断，因此可以用L属性定义解决，为S和L引入继承属性val记录a的嵌套深度。a的嵌套深度等于当前还没有匹配完的左括号的个数，因此累加操作应该在读入一个左括号之后立即进行，而当读入一个字符a的时候立即输出它的深度。据此便可写出如下的属性文法和翻译模式：SaS(L)L,SSS->(L)|aL->L,S|S写一个翻译模式，它输出每个a的嵌套深度。例如对句子(a,(a,a)),输出的结果是1，2，2a属性文法(val是继承属性）S’->S {S.val=0}S->(L) {L.val=S.val+1}S->a {printf(S.val)}L->L1,S{L1.val=L.val,S.val=L.val}L->S{S.val=L.val}S(L)L,SSaa翻译模式S’->{S.val=0}SS->({L.val=S.val+1}

L) S->a{printf(S.val)}L->{L1.val=L.val}L,{S.val=L.val}SL->{S.val=L.val}

S输出句子(a,(a,a))中每个a的嵌套深度：翻译模式S’->{S.val=0}SS->({L.val=S.val+1}

L) S->a{printf(S.val)}L->{L1.val=L.val}L,{S.val=L.val}SL->{S.val=L.val}

SS({L.val=S.val+1}

L)S({L.val=S.val+1}

L){L1.val=L.val}L,{S.val=L.val}S{L1.val=L.val}L,{S.val=L.val}Sa{printf(S.val)}

a{printf(S.val)}

Sa{printf(S.val)}

已知文法：S->aBS|bAS|εB->aBB|bA->bAA|a构造一个翻译模式，它统计句子中a的个数和b的个数

属性文法S->aBS {S.a=B.a+s1.a+1;S.b=B.b+S.b}S->bAS {S.a=A.a+s1.a;S.b=A.b+S.b+1}S->ε {S.a=0;S.b=0}B->aBB {B.a=B1.a+B2.a+1;B.b=B1.b+B2.b}B->b {B.a=0;B.b=1}A->bAA {A.a=A1.a+A2.a;A.b=A1.b+A2.b+1}A->a {A.a=1;A.b=0}翻译模式S->aBS {S.a=B.a+s1.a+1;S.b=B.b+S.b}S->bAS {S.a=A.a+s1.a;S.b=A.b+S.b+1}S->ε {S.a=0;S.b=0}B->aBB {B.a=B1.a+B2.a+1;B.b=B1.b+B2.b}B->b {B.a=0;B.b=1}A->bAA {A.a=A1.a+A2.a;A.b=A1.b+A2.b+1}A->a {A.a=1;A.b=0}6.4.2自顶向下翻译对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。

EE1+T｛E

val:=E1val+T

val}EE1-T｛E

val:=E1

val-Tval｝

ET{E.val:=T

val}T(E)｛T

val:=Eval｝

Tnum｛T

val:=numval}

例

带左递归的文法的翻译模式被转换成带右递归的文法的翻译模式。

E→T{Ri:=T

val}R｛E

val:=Rs｝

R→＋

T｛R1i:=R.i+T.val}R1｛R.s:=R1

s}R→-T｛R1

i:=R

i-Tval}R1｛Rs:=R1

s}R→ε｛Rs:=Ri}T→（E）｛Tval:=E.val}T→num{Tval:=numval}EE1+TEE1-TETT(E)Tnum继承属性i综合属性sETRR(+T|-T)R|εT(E)Tnum对于原左递归的文法，属性的计算自底向上；经过转换的带有右递归文法，属性的计算自左向右。

E→T{Ri:=T

val}R｛E

val:=Rs｝

R→＋T｛R1i:=R.i+T.val}R1｛R.s:=R1

s}R→-T｛R1

i:=R

i-Tval}R1｛Rs:=R1

s}R→ε｛Rs:=Ri}T→（E）｛Tval:=E.val}|num{Tval:=numval}E5+3T{Ri:=T

val}R

｛E

val:=Rs｝num{Tval:=numval}＋T｛R1i:=R.i+Tval}R1｛Rs:=R1s}ε

｛Rs:=Ri}

num{Tval:=numval}Eval=6Tval=9Ri=9;Rs=69–Tval=55Ri=4;Rs=6+Tval=2R

i=6;

Rs=62表达式9-5+2的计算

E→T{Ri:=T

val}R{E

val:=Rs}R→+T{R1i:=R.i+T.val}R1{R.s:=R1

s}R→-T{R1

i:=R

i-Tval}R1{Rs:=R1

s}R→ε｛Rs:=Ri}T→(E){Tval:=E.val}T→num{Tval:=numval}Tval=9Ri=9Tval=5Ri=4Tval=2R

i=6Rs=6Rs=6Rs=6Eval=6◆关于左递归翻译模式更一般化的讨论左递归翻译模式

A→A1Y｛A.a:=g(A1.a,Y.y)}A→X｛A.a:=f(X.x)}

每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。

消除左递归，文法转换成

A→XRR→YR|ε再考虑语义动作，翻译模式变为：

A→X｛Ri:=f(Xx)}R｛Aa:=Rs}R→Y｛R1

i:=g（Ri,Yy）}R1

｛Rs:=R1

s}R→ε｛Rs:=Ri}

经过转换的翻译模式，使用R的继承属性