第四章 语法制导翻译

第四章语法制导的翻译

语义规则的两种描述方法：语法制导定义和翻译方案

综合属性和继承属性

语义规则的三种计算方法S属性的自下而上计算L属性的自上而下计算

语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，对附着于此结构的语义进行处理，如计算表达式的值、生成中间代码等。语法制导翻译简介<1>

语法与语义的关系语法是指语言的结构、即语言的“样子”；语义是指附着于语言结构上的实际含意，即语言的“意义”。对于语法和语义：语义不能离开语法独立存在；语义远比语法复杂；同一语言结构可以包含多种含意，不同语言结构表示相同含意；语法与语义之间没有明确的界线。

<2>语义分析的两个作用检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如： 表达式求值 符号表填写 中间代码生成等<3>语义分析的方法语法制导翻译语义规则有两种常用的描述形式：1、语法制导定义：定义翻译所必须的语义属性和语义规则，一般不涉及计算顺序。2、翻译模式：除了定义翻译所必须的语义属性和语义规则，还给出计算顺序。4.1语法制导的定义

语法制导的定义是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。属性和变量一样，可以进行计算和传递。

属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。属性加工加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。语法制导翻译的基本思想(Syntax-DirectedTranslations)通俗地讲：

以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。

具体方法：

1．将文法符号所代表的语言结构的意思，用附着于该文法符号的属性表示；2．用语义规则规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现属性计算。

语义规则的执行：在语法分析的适当时刻（如推导或归约）执行附着在对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。

每个文法符号有一组属性每个文法产生式A

有一组形式为b:=f(c1,c2,…,ck)的语义规则，其中f是函数，b和c1,c2,…,ck是该产生式文法符号的属性综合属性：如果b是A的属性，c1,c2,…,ck是产生式右部文法符号的属性或A的其它属性。继承属性：如果b是产生式右部某个文法符号X的属性。

在这两种情况下，我们都说属性b依赖于属性c1,c2…,ck.

要特别强调的是：

（1）终结符只有综合属性，它由词法分析器提供；

（2）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。

4.1语法制导的定义4.1.2综合属性S属性定义：仅仅使用综合属性的语法制导定义产

生

式

语

义

规

则

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.lexval4.1语法制导的定义8+5*2n的注释分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义注释分析树:结点的属性值都标注出来的分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1语法制导的定义4.1.3

继承属性 intid,id,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)

4.1语法制导的定义intid1,id2,id3的注释分析树DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,4.1.4属性依赖图

如果在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的属性规则必须在确定c的语义规则之后使用。在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,…ck)的形式。依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。

这里要掌握依赖图的画法。例如，属性A.a:=f(X.x,Y.y)对应于产生式AXY的语义规则,这条语义规则确定了依赖于属性X.x和Y.y的综合属性A.a。如果在语法树中应用这个产生式，那么在依赖图中会有三个结点A.a,X.x,和Y.y。由于A.a依赖X.x，所以有一条有向边从X.x到A.a.由于A.a也依赖于Y.y，所以还有一条有向边从Y.y连到A.a.如果与产生式AXY对应的语义规则还有：X.i:=g(A.a,Y.y)那么，图中还应有两条有向边，一条从A.a连到X.i，另一条从Y.y连到X.i,因为X.i依赖于A.a和Y.y.例：当下面的产生式应用于语法树时，我们就像图6.4所示的那样把有向边加到依赖图中。产生式语义规则EE1+E2E.val:=E1.val+E2.val intid1,id2,id3的分析树的依赖图

D

TL

L.in:=T.typeDintT,id3LLLid2id1,1entry102entry3entryin98in76in54type intid1,id2,id3的分析树的依赖图

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1.5属性计算次序

一个有向非循环图的拓扑排序是图中结点的任何顺序m1,m2,…mk,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语义规则b:=f（c1,c2,…ck)中的属性c1,c2…ck在计算b以前都是可用的。例：1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type翻译过程：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type语义规则的计算方法

1.分析树法:输入串分析树依赖图计算次序2.基于规则的方法：在构造编译器时，用手工或专门的工具来分析语义规则,确定属性值的计算顺序。3.忽略语义规则的方法：在分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。实际上，限制语法制导定义，使属性值的计算顺序能和语法分析过程同步进行。4.2S属性定义的自下而上计算4.2.1语法树（抽象语法树）表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式。

产生式s→ifBthenS1elseS2的语法树

在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。if-then-elseBS1S2+*2584.2.2构造语法树的语法制导定义建立表达式的语法树使用的函数

1.mknode(op,left,right)建立一个运算符号结点，标号是op,两个域left和right指向运算分量结点的指针。2．mkleaf(id,entry)建立一个标识符结点,由标号id标识，一个域entry指向标识符符号表中相应的项。3.mkleaf(num,val)建立一个数结点，标号为num，域val用于存放数的值。返回新建立结点的指针。4.2.2

构造语法树的语法制导定义产生式语

义

规

则

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)

a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2.3S属性的自下而上计算 将LR分析器增加一个域来保存综合属性值。......ZZ.zYY.yXX.x......栈statevaltop4.2.3S属性的自下而上计算 将LR分析器增加一个域来保存综合属性值。......ZZ.zYY.yXX.x......栈statevaltop若产生式A

→XYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)4.2.3S属性的自下而上计算 将LR分析器增加一个域来保存综合属性值。......ZZ.zYY.yXX.x......栈statevaltop若产生式A

→XYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)，那么归约后：......AA.a......top4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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.lexval4.2S属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码

......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

S－属性文法，它只含有综合属性。综合属性可以在分析输入符号串的同时自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。S－属性文法的翻译器通常可借助于LR分析器实现。在S－属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。总结：采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。4.3L属性定义的自上向下计算

在语法分析过程中进行语义分析和翻译，属性的计算顺序受到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L属性定义可用于按深度优先顺序计算属性值。4.3.1L属性定义如果每个产生式AX1

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

的继承属性，1

j

n,但它仅依赖：该产生式中Xj左边符号X1,X2,…,Xj-1的属性；A的继承属性。S属性定义属于L属性定义。L－属性文法允许一次遍历就计算出所有属性值。例：非L-属性的语法制导定义产生式语义规则ALMAQRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)上表的语法制导定义不是L-属性定义文法符号Q的继承属性依赖于它右边文法符号R的属性4.3.2翻译方案

属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，称为翻译方案。翻译方案给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号{}括起来，插入到产生式右部的合适位置上，以表达动作的执行时刻。这样翻译模式给出了使用语义规则进行计算的顺序。4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+52，则输出是85+2。

4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+52，则输出是85+2。

E

TR T+T+T+…

RaddopT{print(addop.lexeme)}R1|

Tnum{print(num.val)}

4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+52，则输出是85+2。

E

TR

RaddopT{print(addop.lexeme)}R1|

Tnum{print(num.val)} E

TRnum{print(8)}R num{print(8)}addopT{print(+)}R

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

…{print(8)}{print(5)}{print(+)}addopT{print()}R…{print(8)}{print(5)}{print(+)}{print(2)}{print()}◆设计翻译模式（根据语法制导定义）条件：语法制导定义是L-属性定义

保证语义动作不会引用还没有计算的属性值。1.只有综合属性的情况： 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：TT1*FTval:=T1val*FvalTT1*F{Tval:=T1val*Fval}2.既有综合属性又有继承属性产生式右边的符号的继承属性必须在这个符号以