编译原理-配套4syntax directed translation

第四章语法制导的翻译本章内容1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案2、介绍语法制导翻译的实现方法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)的语义规则，其中b和c1,c2,…,ck

是该产生式文法符号的属性，f

是函数综合属性：如果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语法制导的定义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.1.4属性依赖图例 intid1,id2,id3的分析树（虚线）的依赖图（实线）

D

TL

L.in=T.typeDintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.4属性依赖图例 intid1,id2,id3的分析树（虚线）的依赖图（实线）

L

L1,

id

L1.in=L.in;

addType(id.entry,L.in)

DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.4属性依赖图例 intid1,id2,id3的分析树（虚线）的依赖图（实线）

Lid

addType(id.entry,L.in)

DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序1、拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点例 1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序2、属性计算次序：构造输入的分析树DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type4.1语法制导的定义语义规则的计算方法分析树方法：刚才介绍的方法，动态确定计算次序，效率低 概念上的一般方法基于规则的方法：（编译器实现者）静态确定（编译器设计者提供的）语义规则的计算次序 适用于手工构造的方法忽略规则的方法：（编译器实现者）事先确定属性的计算策略（如边分析边计算）,（编译器设计者提供的）语义规则必须符合所选分析方法的限制 适用于自动生成的方法4.2S属性定义的自下而上计算4.2.1

语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：

ifBthenS1

elseS2 8+52if-then-elseBS1S2+*2584.2S属性定义的自下而上计算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)

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

→XYZ的语义规则是A.a=f(X.x,Y.y,Z.z)，那么归约后：......AA.a......top......ZZ.zYY.yXX.x......栈statevaltop4.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.3.1L属性定义如果每个产生式AX1…Xj-1Xj…Xn的每条语义规则计算的属性是A的综合属性；或者是Xj

的继承属性，但它仅依赖：该产生式中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 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继承属性的计算 B {S.ht=B.ht} 位于B的左边4.3L属性定义的自上而下计算例 数学排版语言EQN（翻译方案）

S {B.ps=10} B综合属性的计算 B {S.ht=B.ht} 放在右部末端4.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 {B.ht=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

T1F

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} 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.s}W

F {W1.i=mkNode(‘’,W.i,F.nptr)} W1 {W.s=W1.s}W

{W.s=W.i} F产生式部分不再给出4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

部分4.3L属性定义的自上而下计算TF.nptrF.nptridi

WF.nptridnumididnum5指向符号表中a的入口指向符号表中b的入口i

W

siW略去了E

TR

T

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

的分析过程voidR(){ if(lookahead=='+'){ match('+');T();R();

} else/

什么也不做/}4.3L属性定义的自上而下计算syntaxTreeNode

R(syntaxTreeNodei){ syntaxTreeNodenptr,i1,s1,s;

charaddoplexeme;

if(lookahead=='+'){/

产生式R+TR

/

addoplexeme=lexval;

match('+');nptr=T();

i1=mkNode(addoplexeme,i,nptr);

s1=R

(i1);s=s1;

}

elses=i;/

产生式

R

/

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

L:T （非L属性定义）

Tinteger|char

L

L,id|id信息从右向左流，归约从左向右，两者不一致4.3L属性定义的自上而下计算4.3.4用综合属性代替继承属性Pascal的声明，如m,n:integer D

L:T （非L属性定义）

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属性的自下而上计算4.4.1

删除翻译方案中嵌入的动作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分析栈上的继承属性1、属性位置能预测例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属性的自下而上计算4.4.2分析栈上的继承属性1、属性位置能预测例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,qpinttypeininin

继承属性的计算可以略去，引用继承属性的地方改成引用其他符号的综合属性4.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属性的自下而上计算2、属性的位置不能预测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属性的自下而上计算2、属性的位置不能预测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.sM

M.s=M.i计算的可预测4.4L属性的自下而上计算4.4.3

模拟继承属性的计算继承属性是某个综合属性的一个函数 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 {B.ht=disp(B1.ht,B2.ht)}

Btext {B.ht=text.h

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

生

式

语义规则

S

LB

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

L

L.s=10将B.ps存入栈中，便于引用BB1MB2

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

M.s=M.iBB1

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属性的自下而上计算产

生

式

语义规则

S

LB

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

L

L.s=10将B.ps存入栈中，便于引用BB1

MB2

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属性的自下而上计算产

生

式

语义规则

S

LB

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

L

L.s=10将B.ps存入栈中，便于引用BB1

MB2

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

sub

NB2

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属性的自下而上计算举例说明 在text归约成B时，B的ps属性 都在次栈顶位置SMsBLs

BBtextBsubNsBtexttext4.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]本章要点语义规则的两种描述方法：语法制导的定