编译原理课件：第五章 语法制导的翻译

编译原理Compilers–Principles,TechniquesandTools第五章语法制导的翻译本章内容1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案2、介绍语法制导翻译的实现方法5.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.lexval5.1

语法制导的定义5.1.1语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A

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

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

是函数综合属性：如果b是A的属性，c1,c2,…,ck

是产生式右部文法符号的属性或A的其它属性继承属性：如果b是右部某文法符号X的属性5.1

语法制导的定义5.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.lexval5.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=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val=2digit.lexval=55.1

语法制导的定义5.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)

5.1

语法制导的定义例 intid1,id2,id3的标注了部分属性的分析树不可能像像综合属性那样自下而上标注属性DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,5.1

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

D

TL

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

entry3entryin98in76in54type5.1

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

L

L1,

id

L1.in=L.in;

addType(id.entry,L.in)

DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type5.1

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

Lid

addType(id.entry,L.in)

DintT,id3LLLid2id1,1entry102

entry3entryin98in76in54type5.1

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

entry3entryin98in76in54type5.1

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

entry3entryin98in76in54type5.1

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

entry3entryin98in76in54type5.1

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

entry3entryin98in76in54type5.1

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

entry3entryin98in76in54type5.1

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

S属性定义的自下而上计算5.2.1

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

ifBthenS1

elseS2 8+52if-then-elseBS1S2+*2585.2

S属性定义的自下而上计算5.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)

5.2

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

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

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

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

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

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

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

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

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

S属性定义的自下而上计算5.2.3S属性的自下而上计算 LR分析器的栈增加一个域来保存综合属性值若产生式A

→XYZ的语义规则是A.a=f(X.x,Y.y,Z.z)，那么归约后：......AA.a......top......ZZ.zYY.yXX.x......栈statevaltop5.2

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

S属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码

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

5.3

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

L属性定义的自上而下计算5.3.1L属性定义如果每个产生式AX1…Xj-1Xj…Xn的每条语义规则计算的属性是A的综合属性；或者是Xj

的继承属性，但它仅依赖：该产生式中Xj左边符号X1,X2,…,Xj-1的属性；A的继承属性S属性定义属于L属性定义5.3

L属性定义的自上而下计算变量类型声明的语法制导定义是一个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)

5.3

L属性定义的自上而下计算5.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()}5.3

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

Esub1.valSBBB1B2

BB1

subB2BtextE1.val5.3

L属性定义的自上而下计算例 数学排版语言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.val5.3

L属性定义的自上而下计算例 数学排版语言EQN（翻译方案）

S {B.ps=10} B继承属性的计算 B {S.ht=B.ht} 位于B的左边5.3

L属性定义的自上而下计算例 数学排版语言EQN（翻译方案）

S {B.ps=10} B综合属性的计算 B {S.ht=B.ht} 放在右部末端5.3

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

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

义

规

则

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)

5.3

L属性定义的自上而下计算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产生式部分不再给出5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

W

siW略去了E

TR

T

部分5.3

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

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

} else/

什么也不做/}5.3

L属性定义的自上而下计算5.3.3预测翻译器的设计为每个非终结符A构造一个函数，A的每个继承属性作为形参，A的综合属性作为返回值A函数的代码的骨架根据当前的输入决定什么产生式对于有综合属性x的记号X，则保存在X.x中，并匹配记号X对于非终结符B，相应计算c=B(b1,b2,…,bk),则b1,b2,…,bk对应B的继承属性，c对应B的综合属性5.3

L属性定义的自上而下计算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+:addoplexeme5.4

L属性的自下而上计算在自下而上分析的框架中实现L属性定义的方法它能实现任何基于LL(1)文法的L属性定义也能实现许多（但不是所有的）基于LR(1)的L属性定义5.4

L属性的自下而上计算5.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(‘’)}

这些动作的一个重要特点： 没有引用原来产生式文法符号的属性5.4

L属性的自下而上计算5.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)}5.4

L属性的自下而上计算5.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,qpinttypeininin5.4

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

继承属性的计算可以略去，引用继承属性的地方改成引用其他符号的综合属性5.4

L属性的自下而上计算DTLL,rL,qpinttypeininin产生式

代码段

D

TL

Tintval[top]=integer

Trealval[top]=real

L

L1,idaddType(val[top],val[top3])LidaddType(val[top],val[top1])5.4

L属性的自下而上计算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.i5.4

L属性的自下而上计算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计算的可预测5.4

L属性的自下而上计算5.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)5.4

L属性的自下而上计算例数学排版语言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}5.4

L属性的自下而上计算产

生

式

语义规则

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

5.4

L属性的自下而上计算产

生

式

语义规则

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

5.4

L属性的自下而上计算产

生

式

语义规则

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

5.4

L属性的自下而上计算举例说明 在text归约成B时，B的ps属性 都在次栈顶位置SMsBLs

BBtextBsubNsBtexttext5.4

L属性的自下而上计算产

生

式

语义规则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

5.4

L属性的自下而上计算产

生

式

代码段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

5.4

L属性的自下而上计算产

生

式

代码段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

5.4

L属性的自下而上计算产

生

式

代码段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

5.4

L属性的自下而上计算产

生

式

代码段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

5.4

L属性的自下而上计算产

生

式

代码段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

5.4

L属性的自下而上计算产

生

式

代码段SLB

val[top1]=val[top]L

val[top+1]

=10BB1MB2

val[top2]=max(val[top2],val[