中国科学技术大学陈意云编译原理全套参考资料陈意云编译原理全套参考资料chapter4

第四章语法制导的翻译本章内容介绍一种形式化的语义描述方法：语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案。介绍语法制导的翻译的实现方法。4.1语法制导的定义例 简单台式计算器的语法制导定义产

生

式

语

义

规

则

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语法制导的定义4.1.1语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A

有一组形式为b:=f(c1,c2,…,ck)的语义规则，其中f

是函数，b和c1,c2,…,ck

是该产生式文法符号的属性。综合属性：如果b是A的属性，c1,c2,…,ck

是产生式右部文法符号的属性或A的其它属性。继承属性：如果b是产生式右部某个文法符号X的属性。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语法制导的定义

继承属性

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.1.4属性依赖图 intid1,id2,id3的分析树的依赖图DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。例：1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义属性计算次序构造输入的分析树DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义属性计算次序构造输入的分析树，构造属性依赖图DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义属性计算次序构造输入的分析树，构造属性依赖图，对结点进行拓扑排序DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义属性计算次序构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义语义规则的计算方法分析树方法：前面介绍的方法。4.1语法制导的定义语义规则的计算方法分析树方法：前面介绍的方法。基于规则的方法：静态确定语义规则的计算次序。4.1语法制导的定义语义规则的计算方法分析树方法：前面介绍的方法。基于规则的方法：静态确定语义规则的计算次序。忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制。4.2S属性定义的自下而上计算

语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点。

语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：if-then-elseBS1S2+*2584.2S属性定义的自下而上计算

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

义

规

则

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)

4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口4.2S属性定义的自下而上计算4.2.3S属性的自下而上计算

将LR分析器增加一个域来保存综合属性值。......ZZ.zYY.yXX.x......栈statevaltop4.2S属性定义的自下而上计算4.2.3S属性的自下而上计算

将LR分析器增加一个域来保存综合属性值。......ZZ.zYY.yXX.x......栈statevaltop若产生式A

→XYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)4.2S属性定义的自下而上计算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

4.3L属性定义的自上而下计算边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。4.3L属性定义的自上而下计算边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。分析树的结点是自左向右生成。4.3L属性定义的自上而下计算边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。分析树的结点是自左向右生成。如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算。4.3L属性定义的自上而下计算4.3.1L属性定义如果每个产生式AX1

X2…Xn

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

的继承属性，1

j

n,但它仅依赖：该产生式中Xj左边符号X1,X2,…,Xj-1的属性；A的继承属性。4.3L属性定义的自上而下计算4.3.1L属性定义如果每个产生式AX1

X2…Xn

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

的继承属性，1

j

n,但它仅依赖：该产生式中Xj左边符号X1,X2,…,Xj-1的属性；A的继承属性。S属性定义属于L属性定义。4.3L属性定义的自上而下计算变量类型声明的语法制导定义是一个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)

4.3L属性定义的自上而下计算4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+52，则输出是85+2。

4.3L属性定义的自上而下计算4.3.2翻译方案例把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+52，则输出是85+2。

E

TR

RaddopT{print(addop.lexeme)}R1|

Tnum{print(num.val)}

4.3L属性定义的自上而下计算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()}4.3L属性定义的自上而下计算例数学排版语言EQN

Esub1.valSBBB1B2

BB1

subB2BtextE1.val4.3L属性定义的自上而下计算例数学排版语言EQN

Esub1.val产

生

式

语

义

规

则

SB

B.ps:=10;S.ht:=B.ht

BB1B2

B1.ps:=B.ps;B2.ps:=B.ps;B.ht:=max(B1.ht,B2.ht)BB1

subB2

B1.ps:=B.ps;B2.ps:=shrink(B.ps);B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.h

B.ps

E1.val4.3L属性定义的自上而下计算例数学排版语言EQN

S {B.ps:=10} B {S.ht:=B.ht}

B {B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=max(B1.ht,B2.ht)}

B {B1.ps:=B.ps}

B1 sub {B2.ps:=shrink(B.ps)} B2 {:=disp(B1.ht,B2.ht)}

Btext {B.ht:=text.h

B.ps}4.3L属性定义的自上而下计算例左递归的消除引起继承属性产生式语

义

规

则

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)

4.3L属性定义的自上而下计算ET {R.i:=T.nptr} R {E.nptr:=R.s}R+ T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr} W {T.nptr:=}W

* F {W1.i:=mknode(‘*’,W.i,F.nptr)} W1 {W.s:=W1.s}W

{W.s:=W.i}4.3L属性定义的自上而下计算ET {R.i:=T.nptr} T+T+T+… R {E.nptr:=R.s}R+ T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr} W {T.nptr:=}W

* F {W1.i:=mknode(‘*’,W.i,F.nptr)} W1 {W.s:=W1.s}W

{W.s:=W.i}4.3L属性定义的自上而下计算TF.nptrF.nptridi

W**F.nptridnumididnum5**指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算4.3.3预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现产生式R+TR|

的分析过程procdureR; begin iflookahead=‘+’thenbegin match(‘+’);T;R end elsebegin/*

什么也不做*/ end end

4.3L属性定义的自上而下计算functionR(i:syntax_tree_node):syntax_tree_node; var nptr,i1,s1,s:syntax_tree_node;

addoplexeme:char; begin iflookahead=‘+’thenbegin /*

产生式R+TR

*/ addoplexeme:=lexval; match(‘+’); nptr:=T;

i1:=mknode(addoplexme,i,nptr);

s1:=R(i1);

s:=s1 end elses:=i;/*

产生式

R

*/ returns end;R:i,sT:nptr+:addoplexeme4.3L属性定义的自上而下计算4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integer D

L:T

Tinteger|char

L

L,id|id4.3L属性定义的自上而下计算4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integer D

L:T

Tinteger|char

L

L,id|id改成从右向左归约 DidL

L,idL|:T

Tinteger|char4.3L属性定义的自上而下计算4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integer D

L:T

Tinteger|char

L

L,id|id改成从右向左归约 DidL

L,idL|:T

Tinteger|charD:L,idLidintegerT4.3L属性定义的自上而下计算D

idL {addtype(id.entry,L.type)}L

,idL1{L.type:=L1.Type;

addtype(id.entry,L1.type)}L:T {L.type:=T.type}T

integer{T.type:=integer}T

real {T.type:=real}D:L,idLidintegerT4.4L属性的自下而上计算在自下而上分析的框架中实现L属性定义的方法它能实现任何基于LL(1)文法的L属性定义。也能实现许多（但不是所有的）基于LR(1)的L属性定义。4.4L属性的自下而上计算

删除翻译方案中嵌入的动作E

TRR+T{print(‘+’)}R1|

T{print(‘’)}R1|

Tnum{print(num.val)}

4.4L属性的自下而上计算

删除翻译方案中嵌入的动作E

TRR+T{print(‘+’)}R1|

T{print(‘’)}R1|

Tnum{print(num.val)} 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M

的右端。4.4L属性的自下而上计算

删除翻译方案中嵌入的动作E

TRR+T{print(‘+’)}R1|

T{print(‘’)}R1|

Tnum{print(num.val)} 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M

的右端。E

TRR+TMR1|

TNR1|Tnum{print(num.val)}M

{print(‘+’)}N

{print(‘’)}

4.4L属性的自下而上计算4.4.2分析栈上的继承属性例intp,q,rD

T{L.in:=T.type} LTint{T.type:=integer}Treal{T.type:=real}L{L1.in:=L.in}

L1,id{addtype(id.entry,L.in)}Lid{addtype(id.entry,L.in)}4.4L属性的自下而上计算4.4.2分析栈上的继承属性属性位置能预测例intp,q,rD

T{L.in:=T.type} LTint{T.type:=integer}Treal{T.type:=real}L{L1.in:=L.in}

L1,id{addtype(id.entry,L.in)}Lid{addtype(id.entry,L.in)}DTLL,rL,qpinttypeininin4.4L属性的自下而上计算DTLL,rL,qpinttypeininin产生式

代码段

D

TL

Tintval[top]:=integer

Trealval[top]:=real

L

L1,idaddtype(val[top],val[top3])Lidaddtype(val[top],val[top1])4.4L属性的自下而上计算属性的位置不能预测S

aAC C.i:=A.sS

bABC

C.i:=A.sC

c

C.s:=g(C.i)4.4L属性的自下而上计算属性的位置不能预测S

aAC C.i:=A.sS

bABC

C.i:=A.sC

c

C.s:=g(C.i)增加标记非终结符S

aAC C.i:=A.sS

bABMC

M.i:=A.s;C.i:=M.sC

c

C.s:=g(C.i)M

M.s:=M.i4.4L属性的自下而上计算

模拟继承属性的计算继承属性是某个综合属性的一个函数 S

aAC C.i:=f(A.s)

C

c

C.s:=g(C.i)

4.4L属性的自下而上计算

模拟继承属性的计算继承属性是某个综合属性的一个函数 S

aAC C.i:=f(A.s)

C

c

C.s:=g(C.i)

增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行。 S

aANC N.i:=A.s;C.i:=N.s N

N.s:=f(N.i)

C

c

C.s:=g(C.i)4.4L属性的自下而上计算例数学排版语言EQN

S {B.ps:=10} B {S.ht:=B.ht}

B {B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=max(B1.ht,B2.ht)}

B {B1.ps:=B.ps}

B1 sub {B2.ps:=shrink(B.ps)} B2 {:=disp(B1.ht,B2.ht)}

Btext {B.ht:=text.h

B.ps}4.4L属性的自下而上计算产

生

式

语义规则

SLB

B.ps:=L.s;S.ht:=B.ht

L

L.s:=10BB1MB2

B1.ps:=B.ps;M.i:=B.ps;B2.ps:=M.s;B.ht:=max(B1.ht,B2.ht)M

M.s:=M.i

BB1

subNB2

B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht,B2.ht)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

B.ps:=L.s;S.ht:=B.ht

L

L.s:=10BB1MB2

B1.ps:=B.ps;M.i:=B.ps;B2.ps:=M.s;B.ht:=max(B1.ht,B2.ht)M

M.s:=M.i

BB1

subNB2

B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht,B2.ht)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

L.s:=10BB1MB2

B1.ps:=B.ps;M.i:=B.ps;B2.ps:=M.s;B.ht:=max(B1.ht,B2.ht)M

M.s:=M.i

BB1

subNB2

B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht,B2.ht)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

B1.ps:=B.ps;M.i:=B.ps;B2.ps:=M.s;B.ht:=max(B1.ht,B2.ht)M

M.s:=M.i

BB1

subNB2

B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht,B2.ht)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

M.s:=M.i

BB1

subNB2

B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht,B2.ht)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht,B2.ht)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

val[top3]:=disp(val[top3],val[top]

)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

val[top3]:=disp(val[top3],val[top]

)N

val[top+1]

:=shrink(val[top2])BtextB.ht:=text.h

B.ps

4.4L属性的自下而上计算产

生

式

代码段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

val[top3]:=disp(val[top3],val[top]

)N

val[top+1]

:=shrink(val[top2])Btextval[top]:=val[top]val[top1]4.5递归计算

回顾：语法制导定义的实现分析树方法。4.5递归计算

回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。4.5递归计算

回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）。4.5递归计算

回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）。为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分。4.5递归计算

回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）。为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分。为非终结符的不同综合属性构造不同的函数。4.5递归计算4.5.1自左向右遍历为B构造一个属性计算函数

S {B.ps:=10} B {S.ht:=B.ht}

B {B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=max(B1.ht,B2.ht)}

B {B1.ps:=B.ps}

B1 sub {B2.ps:=shrink(B.ps)} B2 {:=disp(B1.ht,B2.ht)}

Btext {B.ht:=text.h

B.ps}4.5递归计算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在结点n的产生式

of ‘BB1B2’:

ps1:=ps;

ht1:=B(child(n,1),ps1);

ps2:=ps;

ht2:=B(child(n,2),ps2); returnmax(ht1,ht2);B {B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=

max(B1.ht,B2.ht)}4.5递归计算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在结点n的产生式

of ‘BB1

subB2’:

ps1:=ps; ht1:=B(child(n,1),ps1);

ps2:=shrink(ps);

ht2:=B(child(n,3),ps2); returndisp(ht1,ht2);B {B1.ps:=B.ps