编译原理 5 语法制导翻译学习课件

语法制导翻译

哈尔滨工业大学陈鄞第五章编译的阶段词法分析语法分析语义分析中间代码生成代码优化目标代码生成语义翻译语法制导翻译(Syntax-DirectedTranslation)语法制导翻译使用CFG来引导对语言的翻译，是一种面向文法的翻译技术什么是语法制导翻译如何表示语义信息？为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息如何计算语义属性？文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联的语义规则来计算的对于给定的输入串x，构建x的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值语法制导翻译的基本思想将语义规则同语法规则（产生式）联系起来涉及的两个概念语法制导定义(Syntax-DirectedDefinitions,SDD)语法制导翻译方案(SDT,Syntax-DirectedTranslationScheme)语法制导翻译的基本思想SDD是对CFG的推广将每个文法符号和一个语义属性集合相关联将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值如果X是一个文法符号，a是X的一个属性，则用X.a表示属性a在某个标号为X的分析树结点上的值例语法制导定义(SDD)

产生式

语义规则D→T

L

L.inh=T.type

T→int T.type=integerT→real T.type=realL→L1,id L1.inh=L.inhSDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内例D→T

{L.inh=T.type}LT→int{T.type=int}T→real{T.type=real}L→{L1.inh=L.inh}L1,id一个语义动作在产生式中的位置决定了这个动作的执行时间语法制导翻译方案(SDT)SDD是关于语言翻译的高层次规格说明隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序SDT可以看作是对SDD的一种补充，是SDD的具体实施方案显式地指明了语义规则的计算顺序，以便说明某些实现细节SDD与SDT5.1语法制导定义SDD5.2S-属性定义与L-属性定义5.3语法制导翻译方案SDT5.4L-属性定义的自顶向下翻译5.5L-属性定义的自底向上翻译本章内容语法制导定义SDD是对CFG的推广将每个文法符号和一个语义属性集合相关联将每个产生式和一组语义规则相关联，用来计算该产生式中各个文法符号的属性值文法符号的属性综合属性（synthesizedattribute）继承属性（inheritedattribute）5.1语法制导定义SDD综合属性（synthesizedattribute）在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义例

终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值。因此在SDD中没有计算终结符的属性值的语义规则+TvalEvalE1val产生式语义规则E

E1+TEval=E1val+Tval继承属性(inheritedattribute)在分析树结点N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或N本身的属性值来定义例终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值产生式语义规则D

TL

L.

inh=T.

typedigit.lexval=3F.val=3T.val=3digit.lexval=5F.val=5T.val=15*+digit.lexval=4F.val=4T.val=4E.val=19LnE.val=15注释分析树(Annotated

parsetree)：每个节点都带有属性值的分析树输入：3*5+4n产生式

语义规则(1)L

En print(Eval)(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)Fdigit Fval=digitlexval副作用(Sideeffect)SDD：例：带有综合属性的SDD

id.lexeme=aid.lexeme=bid.lexeme=cDL.in=realT.type=realrealL.in=real,L.in=real,SDD：

产生式语义规则(1)

D

TL L.inh=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.inh=L.inh

addtype(id.lexeme,L.inh)(5)

Lid addtype(id.lexeme,L.inh)输入：reala

,b,c例：带有继承属性L.in的SDD

一个没有副作用的SDD有时也称为属性文法属性文法的规则仅仅通过其它属性值和常量来定义一个属性值例产生式

语义规则(1)L

En

Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)F

digit

Fval=digit

lexval属性文法(AttributeGrammar)SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值按照什么顺序计算属性值？语义规则建立了属性之间的依赖关系，在对语法分析树结点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值SDD的求值顺序依赖图是一个描述了分析树中结点属性间依赖关系的有向图分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边依赖图(DependencyGraph)typeinininlexemelexemelexeme，idLDTL，idLidrealSDD：

产生式语义规则(1)

D

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)输入：reala

,b,c例for分析树中的每个结点ndofor与结点n对应的文法符号的每个属性ado在依赖图中为a构造一个结点；for

分析树的每个结点n

do

for结点n所用产生式对应的每条语义规则b:＝f(c1,c2,…,ck

)dofori:=1tok

do

从结点ci到结点b构造一条有向边；依赖图的构造方法typeinininlexemelexemelexeme，idLDTL，idLidrealSDD：

产生式语义规则(1)

D

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)输入：reala

,b,c例可行的求值顺序是满足下列条件的结点序列N1,N2,…,Nk

：如果依赖图中有一条从结点Ni到

Nj

的边(Ni→Nj),那么i<j（即：在节点序列中，Ni排在Nj前面）这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topologicalsort)属性值的计算顺序type4in5

6

in7

8in109lexeme

3lexeme

2

lexeme1，idLDTL，idLidrealSDD：

产生式语义规则(1)

D

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)输入：reala

,b,c例拓扑排序：1,2,3,4,5,6,7,8,9,104,3,2,1,5,7,6,9,8,10例如果图中没有环，那么至少存在一个拓扑排序A.sB.iAB产生式语义规则A

B A.s

=B.iB.i

=A.s+1对于只具有综合属性的SDD

，可以按照任何自底向上的顺序计算它们的值对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图不仅如此，接下来介绍的两类SDD可以和自顶向下及自底向上的语法分析过程一起高效地实现S-属性定义

(S-AttributedDefinitions,S-SDD)L-属性定义

(L-AttributedDefinitions,L-SDD)5.1语法制导定义SDD5.2S-属性定义与L-属性定义5.3语法制导翻译方案SDT5.4L-属性定义的自顶向下翻译5.5L-属性定义的自底向上翻译提纲S-属性定义仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD例如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值S-属性定义可以在自底向上语法分析的过程中实现

产生式

语义规则(1)L

En Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)Fdigit Fval=digitlexval5.2S-属性定义与L-属性定义L-属性定义（也称为L属性的SDD或L-SDD）的直观含义：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左（因此称为L属性的，L是Left的首字母）L-属性定义一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi(1

i

n)的继承属性仅依赖于下列属性：A的继承属性产生式中Xi左边的符号

X1,X2,…,Xi-1

的属性Xi本身的属性，但Xi的全部属性不能在依赖图中形成环路每个S-属性定义都是L-属性定义L-SDD的正式定义一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi(1

i

n)的继承属性仅依赖于下列属性：A的继承属性产生式中Xi左边的符号

X1,X2,…,Xi-1

的属性Xi本身的属性，但Xi的全部属性不能在依赖图中形成环路为什么不能是综合属性？L-SDD的正式定义一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式A→X1X2…Xn，其右部符号Xi(1

i

n)的继承属性仅依赖于下列属性：A的继承属性产生式中Xi左边的符号

X1,X2,…,Xi-1

的属性Xi本身的属性，但Xi的全部属性不能在依赖图中形成环路XjAisisL-SDD的正式定义

产生式语义规则(1)

T

FT′

T′.inh=F.val

T.val

=T′.syn(2)T′

*FT1′

T1′.inh=T′.inh×F.val

T′.syn=

T1′.syn

(3)T′

ε

T′.syn=T′.inh(4)

Fdigit F.val=digit.lexval综合属性继承属性例：L-SDD非L属性的SDD例

产生式

语义规则(1)A

LM L.i=l(A.i) M.i=m(L.s) A.s=f(M.s)(2)A

QR R.i=r(A.i) Q.i=q(R.s)

A.s=f(Q.s)综合属性继承属性×5.1语法制导定义SDD5.2S-属性定义与L-属性定义5.3语法制导翻译方案SDT5.4L-属性定义的自顶向下翻译5.5L-属性定义的自底向上翻译提纲

语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的CFG例D→T

{L.inh=T.type}LT→int{T.type=integer}T→real{T.type=real}L→{L1.inh=L.inh}L1,id5.3语法制导翻译方案SDT

语法制导翻译方案(SDT)是在产生式右部中嵌入了程序片段(称为语义动作)的CFG语法制导翻译方案SDTSDT可以看作是SDD的具体实施方案本节主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可以在语法分析过程中实现基本文法可以使用LR分析技术，且SDD是S属性的基本文法可以使用LL分析技术，且SDD是L属性的

将一个S-SDD转换为SDT的方法：将每个语义动作都放在产生式的最后例SDT产生式

语义规则(1)L

En

Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E) Fval=Eval(7)F

digit

Fval=digit

lexval(1)L

En

{Lval=Eval}(2)E

E1+T{Eval=E1val+Tval}(3)E

T

{Eval=Tval}(4)T

T1*F

{Tval=T1val×Fval}(5)T

F

{Tval=Fval}(6)F(E){Fval=Eval}(7)F

digit

{Fval=digit

lexval}S-SDD将S-SDD转换为SDT如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现例

产生式

语义规则(1)L

En

Lval=Eval(2)E

E1+TEval=E1val+Tval(3)E

T

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

F

Tval=Fval(6)F(E)Fval=Eval(7)F

digit

Fval=digit

lexvalS-SDDSLR自动机当归约发生时执行相应的语义动作S-属性定义的SDT实现状态文法符号综合属性S0$.........Sm-2XX.xSm-1YY.ySmZZ.z.........top若支持多个属性使栈记录变得足够大在栈记录中存放指针扩展的LR语法分析栈在分析栈中使用一个附加的域来存放综合属性值A

XYZ{A.a=f(X.x,Y.y,Z.z)}A.aX.X

Y.y

Z.zstack[top-2].symb=A

stack[top-2].val=f(stack[top-2].val,stack[top-1].val,stack[top].val)top=top-2;重写语义动作使其显示地操作语法分析栈

产生式语义动作(1)E′→E print(Eval) {print

(stack[top].val);}(2)E→E1+TEval=E1val+Tval {stack[top-2].val=stack[top-2].val+stack[top].val; top=top-2;}(3)E→T Eval=Tval(4)T→T1*

FTval=T1val×Fval {stack[top-2].val=stack[top-2].val×stack[top].val; top=top-2;}(5)T→F Tval=Fval(6)F→(E)Fval=Eval {stack[top-2].val=stack[top-1].val; top=top-2;}(7)F→digitFval=digitlexval

例：在自底向上语法分析栈中实现桌面计算器例状态

符号

属性输入：3*5+40$_5d3SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

例输入：3*5+40$_3F3SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_2T37*_5d5SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_2T37*_10F155SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_2T315SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_1E3156+_5d4SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_1E3156+_3F4SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_1E3156+_9T419SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性例输入：3*5+40$_1E31519SLR自动机

产生式语义动作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*

F{stack[top-2].val=stack[top-2].val×stack[top].val;top=top-2;}(5)T→F(6)F→(E){stack[top-2].val=stack[top-1].val;top=top-2;}(7)F→digit

状态

符号

属性把计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上将计算一个产生式左部的综合属性的动作放置在这个产生式右部的最右端将一个L-SDD转换为SDT的规则

产生式语义规则(1)

T

FT′

T′.inh=F.val

T.val

=T′.syn(2)T′

*FT1′

T1′.inh=T′.inh×F.val

T′.syn=

T1′.syn

(3)T′

ε

T′.syn=T′.inh(4)

FdigitF.val=digit.lexvalL-SDDSDT1)

T→F

{T΄.inh=F.val}T΄

{T.val=T΄.syn}2)T΄→*F

{T1΄.inh=T΄.inh×F.val}T1΄

{T΄.syn=T1΄.syn}3)T΄→ε

{T΄.syn=

T΄.inh}4)F→digit{F.val=digit.lexval}例如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现例1)

T→F

{T΄.inh=F.val}T΄

{T.val=T΄.syn}2)T΄→*F

{T1΄.inh=T΄.inh×F.val}T1΄

{T΄.syn=T1΄.syn}3)T΄→ε

{T΄.syn=

T΄.inh}4)F→digit

{F.val=digit.lexval}SELECT(1)={digit}SELECT(2)={*}SELECT(3)={$}SELECT(4)={digit}L-属性定义的SDT实现如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现在非递归的预测分析过程中进行语义翻译在递归的预测分析过程中进行语义翻译在LR分析过程中进行语义翻译L-属性定义的SDT实现5.1语法制导定义SDD5.2S-属性定义与L-属性定义5.3语法制导翻译方案SDT5.4L-属性定义的自顶向下翻译5.5L-属性定义的自底向上翻译提纲5.4.1在非递归的预测分析过程中进行翻译5.4.2在递归的预测分析过程中进行翻译5.4L-属性定义的自顶向下翻译扩展的LL(1)语法分析栈A

actionAsyn指向将被执行的语义动作代码的指针A的继承属性A的综合属性SymbolValue

5.4.1在非递归的预测分析过程中进行翻译1)

T→F

{T′.inh=F.val}T′{T.val=T′.syn}2)T′

→*F

{T1′.inh=T′.inh×F.val}T1′

{T′.syn=

T1′.syn}3)T′

→ε

{T′.syn=

T′.inh}4)F→digit{F.val=digit.lexval}a1：T′.inh=F.val

a2：

T.val=T′.syn

a3：

T1′.inh=T′.inh×F.val

a4

：

T′.syn=

T1′.syn

a5

：

T′.syn=

T′.inh

a6

：

F.val=digit.lexval

1)

T→F{a1}T′

{a2

}2)T΄→*F{a3}T1′{a4

}3)T΄→ε

{a5

}4)F→digit{a6

}例TTsyn$val输入:3*5a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’synFsyn{a1}FsynvalT’inha1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}Tsyn$val输入:3*5{a2}T’synsyn{a1}FsynvalT’inh{a6}digitlexval=3digit_lexval=3stack[top-1].val=stack[top].digit_lexvalFval=3val=3例Tsyn$val输入:3*5{a2}T’synsyn{a1}T’inhFval=3stack[top-1].inh=stack[top].Fvalinh=3a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’synsyn{a4}T1’T1’syn{a3}Fsyn*FT’inh=3syninhvala1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’synsyn{a4}T1’T1’syn{a3}FsynT’inh=3syninhval{a6}digitlexval=5digit_lexval=5stack[top-1].val=stack[top].digit_lexvalval=5Fval=5a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’synsyn{a4}T1’T1’syn{a3}T’inh=3syninhFval=5stack[top-1].inh=stack[top].T’inh

×stack[top].Fval

inh=15a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’synsyn{a4}T1’synsynT1’inh=15{a5}stack[top-1].syn=stack[top].T1’inhsyn=15T1’syn=15a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’synsyn{a4}T1’syn=15stack[top-1].syn=stack[top].T1’synsyn=15T’syn=15a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例Tsyn$val输入:3*5{a2}T’syn=15stack[top-1].val=stack[top].T’synval=15a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}例①在变量A的记录下面加一个综合记录，用来将计算得到的A的综合属性值回填②综合记录出栈时，要将综合属性值复制给后面特定的语义子程序③变量展开时（即普通记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义子程序分析栈中的每一个记录都对应着一段执行代码1)T→F{a1:T′.inh=F.val}T′

{a2:T.val=T′.syn}符号属性代码段F根据当前输入符号选择产生式进行推导F_synvalstack[top-1].Fval=stack[top].val；top=top-1;a1Fvalstack[top-1].inh=stack[top].Fval；top=top-1;T′inh根据当前输入符号选择产生式进行推导若选2):stack[top+3].T′inh

=stack[top].inh;top=top+6;若选3):stack[top].T′inh

=stack[top].inh;

T′_synsynstack[top-1].T′syn=stack[top].syn；top=top-1;a2T′synstack[top-1].val=stack[top].T′syn；top=top-1;1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

例2)T′

→*F{a3:T1′.inh=T′.inh×F.val}T1′{a4:T′.syn=T1′.syn}符号属性代码段*输入指针后移F根据当前输入符号选择产生式进行推导F_synvalstack[top-1].Fval=stack[top].val；top=top-1;a3T΄inh;Fvalstack[top-1].inh=stack[top].T′inh×

stack[top].Fval；top=top-1;T1′inh根据当前输入符号选择产生式进行推导若选2):stack[top+3].T′inh=stack[top].inh;top=top+6;若选3):stack[top].T′inh=stack[top].inh;

T1′_synsynstack[top-1].T1′syn=stack[top].syn；top=top-1;a4T1′synstack[top-1].syn=stack[top].T1′syn；top=top-1;1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

例3)T′

→

ε

{a5:T′.syn=

T′.inh}符号属性代码段a5T′inhstack[top-1].syn=stack[top].T′inh；top=top-1;1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

例4)F→digit{a6:F.val=digit.lexval}符号属性代码段digit输入指针后移digit_synlexvalstack[top-1].digitlexval=stack[top].lexval；top=top-1;a6digitlexvalstack[top-1].val=stack[top].digitlexval；top=top-1;1)

T→F

{a1}T΄{a2}2)T΄→*F

{a3}T1΄

{a4}3)T΄→ε

{a5}4)F→digit

{a6}a1：T΄.inh=F.val

a2：

T.val=T΄.syn

a3：

T1΄.inh=T΄.inh×F.val

a4

：

T΄.syn=

T1΄.syn

a5

：

T΄.syn=

T΄.inh

a6

：

F.val=digit.lexval

例T′syn

T′

(token,T′inh){

D:Fval,T1′inh,T1′syn；

iftoken=“*”then

{Getnext(token)；

Fval=F(token)；

T1′inh=T′inh×Fval；

Getnext(token)；

T1′syn=T1′(token,T1′inh)；

T΄syn=T1′syn； returnT′syn；

}

elseiftoken=

“$”

then

{

T′syn=T′inh； returnT′syn；}

elseError；}例SDT

1)

T→F{T′.inh=F.val}T′

{T.val=T′.syn}2)T′→*F{T1′.inh=T′.inh×F.val}T1′

{T′.syn=T1′.syn}3)T′

→ε

{T′.syn=

T′.inh}4)F→

digit

{F.val=digit.lexval}5.4.2在递归的预测分析过程中进行翻译对于每个动作，将其代码复制到语法分析器