ch05-语法制导翻译技术市公开课一等奖百校联赛优质课金奖名师赛课获奖课件

第5章语法制导翻译技术知识点：语法制导定义、翻译方案

S属性、L属性

S-属性定义翻译L-属性定义翻译1/851语法制导翻译技术语义分析包括到语言语义形式语义学研究开始于20世纪60年代初形式语义学能够分为三类操作语义学：模拟数据加工过程中计算机系统操作指称语义学：描述数据加工结果公理语义学：用公理化方法描述程序对数据加工语法制导翻译技术多数编译程序普遍采取一个技术比较靠近形式化2/852语法制导翻译技术5.1语法制导定义及翻译方案5.2S-属性定义自底向上翻译5.3L-属性定义自顶向下翻译5.4L-属性定义自底向上翻译5.5非L属性定义翻译小结3/8535.1语法制导定义及翻译方案对上下文无关文法推广每个文法符号都能够有一个属性集，能够包含两类属性：综合属性和继承属性。分析树中一个结点综合属性是从其子结点属性值计算出来继承属性是从其弟兄结点和/或父结点属性值计算出来分析树中某个结点属性值是由与在这个结点上所用产生式对应语义规则决定。和产生式相联络语义规则建立了属性之间关系，这些关系可用有向图（即：依赖图）来表示。4/854内容安排一、语法制导定义二、依赖图三、计算次序四、S属性定义和L属性定义五、翻译方案5/855一、语法制导定义在一个语法制导定义中，对应于每一个文法产生式A

，都有与之相联络一组语义规则，其形式为：b=

(c1,c2,…,ck)这里，

是一个函数，而且或者(1)b是A一个综合属性，且c1、c2、…、ck是产生式右部文法符号属性，或者(2)b是产生式右部某个文法符号一个继承属性，且c1、c2、…、ck是A或产生式右部文法符号属性。属性b依赖于属性c1、c2、…、ck。语义规则函数都不含有副作用语法制导定义称

为属性文法6/856语义规则普通情况：语义规则函数可写成表示式形式。一些情况下：一个语义规则唯一目标就是产生某个副作用，如打印一个值、向符号表中插入一条统计等；这么语义规则通常写成过程调用或程序段。看成是对应产生式左部非终止符号虚拟综合属性。虚属性和符号‘=’都没有表示出来。7/857简单算术表示式求值语法制导定义综合属性val与每一个非终止符号E、T、F相联络表示对应非终止符号所代表子表示式整数值L

n语义规则是一个过程，打印出由E产生算术表示式值，能够认为是非终止符号L一个虚拟综合属性。产生式L

EnE

E1+TE

TT

T1*FT

FF

(E)F

digit语义规则 print(E.val) E.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.valF.val=digit.lexval8/858综合属性分析树中，假如一个结点某一属性由其子结点属性确定，则这种属性为该结点综合属性。假如一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S-属性定义。对于S-属性定义，通常采取自底向上方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个结点属性值。简单台式计算机语法制导定义是S-属性定义9/8593*5+4n分析树加注释过程属性值计算能够在语法分析过程中进行。LEnE+TTFT*FdigitFdigitdigit.lexval=3.val=3.val=3.lexval=5.val=5.val=15.val=15.lexval=4.val=4.val=4.val=19Print(19)10/8510继承属性分析树中，一个结点继承属性值由该结点父结点和/或它弟兄结点属性值决定。可用继承属性表示程序设计语言结构中上下文之间依赖关系能够跟踪一个标识符类型能够跟踪一个标识符，了解它是出现在赋值号右边还是左边，以确定是需要该标识符值还是地址。11/8511一个带有继承属性L.in语法制导定义D产生申明包含了类型关键字int或real，后跟一个标识符表。T有综合属性type，其值由申明中关键字确定。L继承属性L.in，表示从父结点或弟兄结点继承下来类型信息。产生式D

TLT

intT

realL

L1,id

L

id语义规则L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)12/8512语句realid1,id2,id3分析树加注释L产生式语义规则使用继承属性L.in把类型信息在分析树中向下传递；并经过调用过程addtype，把类型信息填入标识符在符号表中对应表项中。

DTLL,id2L,id3id1real.type=real.in=real.in=real.in=realaddtype(id3.entry,L.in)addtype(id1.entry,L.in)addtype(id2.entry,L.in)13/8513二、依赖图分析树中，结点继承属性和综合属性之间相互依赖关系能够由依赖图表示。为每个包含过程调用语义规则引入一个虚拟综合属性b，方便把语义规则统一为b=

(c1,c2,…,ck)形式。依赖图中：为每个属性设置一个结点假如属性b依赖于c，那么隶属性c结点有一条有向边连到属性b结点。14/8514算法5.1结构依赖图输入：一棵分析树输出：一张依赖图方法：for(分析树中每一个结点n)for(结点n处文法符号每一个属性a)为a在依赖图中建立一个结点;for(分析树中每一个结点n)for(结点n处所用产生式对应每一个语义规则b=

(c1,c2,…,ck))for(i=1;i<=k;i++)从ci结点到b结点结构一条有向边;15/8515依赖图结构举例产生式依赖规则A

XYA.a=

(X.x,Y.y)X.i=g(A.a,Y.y)AXY.a.x.i.yDTLL,id2L,id3id1real4

type9

in10

addtype7

in8

addtype5

in6

addtype1

entry2

entry

3

entry16/8516三、计算次序有向非循环图拓扑排序图中结点一个排序m1,m2,…,mk有向边只能从这个序列中前边结点指向后面结点假如mi

mj是从mi指向mj一条边，那么在序列中mi必须出现在mj之前。依赖图任何拓扑排序给出了分析树中结点语义规则计算有效次序在拓扑排序中，一个结点上语义规则b=

(c1,c2,…,ck)中属性c1,c2,…,ck在计算b时都是可用。拓扑排序：1、2、3、4、5、6、7、8、9、104、5、3、6、7、2、8、9、1、1017/8517计算次序从拓扑排序中能够得到下面程序，an代表依赖图中与序号n结点相关属性：a4=real；a5=a4；addtype(id3.entry,a5)；a7=a5；addtype(id2.entry,a7)；a9=a7；addtype(id1.entry,a9)；18/8518语法制导翻译过程最基本文法用于建立输入符号串分析树；为分析树结构依赖图；对依赖图进行拓扑排序；从这个序列得到语义规则计算次序；照此计算次序进行求值，得到对输入符号串翻译。输入符号串分析树依赖图语义规则计算次序计算结果19/8519四、L属性定义和L属性定义

L属性定义：一个语法制导定义是L属性定义，假如与每个产生式A

X1X2…Xn对应每条语义规则计算属性都是A综合属性，或是Xj（1

j

n）继承属性，而该继承属性仅依赖于：产生式中Xj左边符号X1、X2、…、Xj-1属性；A继承属性。每一个S属性定义都是L属性定义20/8520例：非L属性定义

语法制导定义产生式语义规则A

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

QRR.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)产生式D

TLT

intT

realL

L1,id

L

id语义规则L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)例：是L属性定义语法制导定义21/8521属性计算次序——深度优先遍历分析树voiddeepfirst(n:node){for(n每一个子结点m，从左到右){计算m继承属性;deepfirst(m);};计算n综合属性;}.以分析树根结点作为实参L属性定义属性都能够用深度优先次序计算。进入结点前，计算它继承属性从结点返回时，计算它综合属性22/8522五、翻译方案上下文无关文法一个便于翻译书写形式属性与文法符号相对应语义动作括在花括号中，并插入到产生式右部某个适当位置上给出了使用语义规则进行属性计算次序分析过程中翻译注释23/8523例：一个简单翻译方案

E

TR

R

addopT{print（addop.lexeme）}R1|

T

num{print(num.val)}9-5+2分析树：ET

R9

-

T

R5+TR2

语义动作作为对应产生式左部符号对应结点子结点深度优先遍历树中结点，执行其中动作，打印出95-2+{print(

9

)}{print(

-

)}{print(

5

)}{print(

+

)}{print(

2

)}24/8524翻译方案设计对于S属性定义：为每一个语义规则建立一个包含赋值动作把这个动作放在对应产生式右边末尾例：产生式语义规则

T

T1*FT.val=T1.val*F.val以下安排产生式和语义动作：

T

T1*F{T.val=T1.val*F.val}25/8525为L属性定义设计翻译方案标准产生式右部文法符号继承属性必须在这个符号以前动作中计算出来计算该继承属性动作必须出现在对应文法符号之前一个动作不能引用这个动作右边文法符号综合属性产生式左边非终止符号综合属性只有在它所引用全部属性都计算出来之后才能计算这种属性计算动作放在产生式右端末尾26/8526例：考虑以下翻译方案

S

A1A2{A1.in=1；A2.in=2}

A

a{print(A.in)}SA1A2{A1.in=1;A2.in=2}a{print(A.in)}a{print(A.in)}a{print(A.in)}S{A1.in=1;A2.in=2}A1A2a{print(A.in)}

27/8527例：为以下L属性定义设计翻译方案产生式语义规则S

BB.ps=10S.ht=B.htB

B1B2B1.ps=B.psB2.ps=B.psB.ht=max(B1.ht,B2.ht)B

B1subB2B1.ps=B.psB2.ps=shrink(B.ps)B.ht=disp(B1.ht,B2.ht)B

textB.ht=text.h

B.ps28/8528把语义规则插入到产生式中适当位置S

{B.ps=10}B{S.ht=B.ht}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}B1sub{B2.ps=shrink(B.ps)}B2{B.ht=disp(B1.ht,B2.ht)}B

text{B.ht=text.h

B.ps}29/85295.2S-属性定义自底向上翻译S属性定义：只用综合属性语法制导定义一、语法树二、结构表示式语法树三、结构表示式语法树语法制导定义四、表示式有向非循环图（dag）五、S属性定义自底向上实现30/8530一、语法树把语法规则中对语义无关紧要详细要求去掉，剩下来本质性东西称为抽象语法。如：赋值语句：x=y、x:=y、或y

x抽象形式：assignment(variable,expression)语法树：分析树抽象（或压缩）形式。也称为语法结构树或结构树。内部结点表示运算符号，其子结点表示它运算分量。31/8531语法树示例S

ifEthenS1elseS2语法树if--then--elseES1S2+*435表示式3*5+4语法树LEnE+TTFT*FdigitFdigitdigit32/8532二、结构表示式语法树表示式语法树形式每一个运算符号或运算分量都对应树中一个结点运算符号结点子结点分别是与该运算符各个运算分量对应子树根。每一个结点可包含若干个域：标识域、指针域、属性值域等在运算符结点中一个域标识运算符号其它各域包含指向与各运算分量对应结点指针称运算符号为该结点标号33/8533结构函数makenode(op,left,right)建立一个运算符号结点，标号是op；域left和right是指向其左右运算分量结点指针。makeleaf(id,entry)建立一个标识符结点，标号是id；域entry是指向该标识符在符号表中对应条目标指针。makeleaf(num,val)建立一个数结点，标号为num；域val用于保留该数值。34/8534建立表示式a-4+c语法树p1=makeleaf(id,entrya);p2=makeleaf(num,4);p3=makenode(‘-’,p1,p2);p4=makeleaf(id,entryc);p5=makenode(‘+’,p3,p4);

id符号表中a入口P1num4P2

-

P3

id符号表中c入口P4

+

P5+-ca435/8535三、结构表示式语法树语法制导定义目标：为表示式创建语法树产生式语义：创建与产生式左部符号代表子表示式对应子树，即创建子树根结点。文法符号属性：统计所建结点，E.nptr、T.nptr指向对应子树根结点指针产生式语义动作：E

E1+TE.nptr=makenode(

+

,E1.nptr,T.nptr)

T

idT.nptr=makeleaf(id,id.entry)

T

numT.nptr=makeleaf(num,num.val)36/8536结构表示式语法树语法制导定义产生式E

E1+TE

E1-TE

TT

(E)T

idT

numE.nptr=makenode(

+

,E1.nptr,T.nptr)E.nptr=makenode(

-

,E1.nptr,T.nptr)E.nptr=T.nptrT.nptr=E.nptrT.nptr=makeleaf(id,id.entry)T.nptr=makeleaf(num,num.val)语义规则37/8537表示式a-4+c语法树结构num4

id符号表中a入口aEEETc4.nptr.nptr.nptr.nptr.nptr.nptr

-

id符号表中c入口+

-T+T38/8538四、表示式有向非循环图(dag)dag与语法树相同地方：表示式每一个子表示式都有一个结点一个内部结点表示一个运算符号，且它子结点表示它运算分量。dag与语法树不一样地方：dag中，对应一个公共子表示式结点含有多个父结点语法树中，公共子表示式被表示为重复子树为表示式创建dag函数makenode和makeleaf建立新结点之前先检验是否已经存在一个相同结点若已存在，返回一个指向先前已结构好结点指针；不然，创建一个新结点，返回指向新结点指针。39/8539为表示式a+a*(b-c)+(b-c)*d结构dag函数调用p1=makeleaf(id,a)；p2=makeleaf(id,a)；p3=makeleaf(id,b)；p4=makeleaf(id,c)；p5=makenode(

-

,p3,p4)；p6=makenode(

*

,p2,p5)；p7=makenode(

+

,p1,p6)；p8=makeleaf(id,b)；p9=makeleaf(id,c)；p10=makenode(

-

,p8,p9)；p11=makeleaf(id,d)；p12=makenode(

*

,p10,p11)；p13=makenode(

+

,p7,p12)；abc

-*+d*+

p1

p2

p3

p4

p5

p6

p7

p8

p9

p10

p11

p12

p1340/8540五、S-属性定义自底向上实现已知自底向上分析方法中，分析程序使用一个栈来存放已经分析过子树信息。分析树中某结点综合属性由其子结点属性值计算得到自底向上分析程序在分析输入符号串同时能够计算综合属性考虑怎样保留文法符号综合属性值？保留属性值数据结构怎样与分析栈相联络？怎样确保：每当进行归约时，由栈中正在归约产生式右部符号属性值计算其左部符号综合属性值。41/8541扩充分析栈目标：使之能够保留综合属性做法：在分析栈中增加一个域，来存放综合属性值例：带有综合属性域分析栈栈由一对数组state和val实现state元素是指向LR(1)分析表中状态指针（或索引）假如state[i]对应符号为A，val[i]中就存放分析树中与结点A对应属性值。假设综合属性刚好在每次归约前计算A

XYZ对应语义规则是A.a=

(X.x,Y.y,Z.z)ZZ.zYY.yXX.x┅┅topstateval42/8542修改分析程序对于终止符号其综合属性值由词法分析程序产生当分析程序执行移进操作时，其属性值随终止符号（或状态符号）一起入栈。为每个语义规则编写一段代码，以计算属性值对每一个产生式A

XYZ把属性值计算与归约动作联络起来归约前，执行与产生式相关代码段归约：右部符号及其属性出栈左部符号及其属性入栈LR分析程序中应增加计算属性值

代码段ZZ.zYY.yXX.xtop®

......statevalAA.a43/8543例：用LR分析程序实现表示式求值产生式L

EnE

E1+TE

TT

T1*FT

FF

(E)F

digit语义规则 print(E.val) E.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.valF.val=digit.lexval代码段print(val[top])val[ntop]=val[top-2]+val[top]val[ntop]=val[top-2]*val[top]val[ntop]=val[top-1]44/8544对3*5+4n进行分析动作序列步骤输入分析栈分析动作(1)3*5+4nstate:0

val:-移进(2)*5+4nstate:05

val:-3归约，用F

digit(3)*5+4nstate:03val:-3归约，用T

F(4)*5+4nstate:02val:-3移进(5)5+4nstate:027val:-3-移进(6)+4nstate:0275val:-3-5归约，用F

digit(7)+4nstate:02710val:-3-5归约，用T

T*F45/8545步骤输入分析栈分析动作(8)+4nstate:02val:-15归约，用E

T(9)+4nstate:01val:-15移进(10)4nstate:016val:-15-移进(11)nstate:0165val:-15-4归约，用F

digit(12)nstate:0163val:-15-4归约，用T

F(13)nstate:0169val:-15-4归约，用E

E+T(14)nstate:01val:-19接收46/85465.3L-属性定义自顶向下翻译在自顶向下分析过程中实现L属性定义翻译预测分析方法对文法要求不含左递归A

FIRST()FIRST()=一、消除翻译方案中左递归二、预测翻译程序设计47/8547一、消除翻译方案中左递归例：考虑关于表示式语法制导定义产生式语义规则E

E1+TE.val=E1.val+T.valE

E1-TE.val=E1.val-T.valE

T

E.val=T.valT

(E)

T.val=E.valT

num

T.val=num.val翻译方案：(1)E

E1+T{E.val=E1.val+T.val}(2)E

E1-T{E.val=E1.val-T.val}(3)E

T{E.val=T.val}(4)T

(E){T.val=E.val}(5)T

num{T.val=num.val}由(1)和(3)有：(1

)E

T{E.val=T.val}R(3

)R

+T{E.val=E1.val+T.val}R1(3")

R

继承属性R.i：表示在R之前已经推导出子表示式值综合属性R.s：表示在R完全展开之后得到表示式值消除左递归方法：A

A

|

替换为：A

RR

R|

48/8548R1.i语义规则为：R1.i=R.i+T.valR.s语义规则为：R.s=R1.s于是得到：(3

)R

+T{R1.i=R.i+T.val}R1{R.s=R1.s}一样可得到：(2

)R

-T{R1.i=R.i-T.val}R1{R.s=R1.s}为(3")设置把R.i传递给R.s语义动作，得到：

(3")R

{R.s=R.i}对于(1

)，E

T{E.val=T.val}R经过R属性R.s和R.i完成E和T综合属性传递E.val=T.val，得到：(1

)E

T{R.i=T.val}

R{E.val=R.s}对于(3

)R

+T{E.val=E1.val+T.val}R149/8549翻译方案ETRnum+TRnum-TRnum

.val=8.val=8.i=8.val=5.val=5.i=13.val=7.val=7.i=6.s=6.s=6.s=6.val=6E

T{R.i=T.val}R{E.val=R.s}R

+T{R1.i=R.i+T.val}R1{R.s=R1.s}R

-T{R1.i=R.i-T.val}R1{R.s=R1.s}R

{R.s=R.i}T

(E){T.val=E.val}T

num{T.val=num.val}表示式8+5-7翻译过程50/8550消除翻译方案中左递归普通方法翻译方案：A

A1Y{A.a=g(A1.a,Y.y)}A

X{A.a=f(X.x)}为R设置继承属性R.i和综合属性R.sR.i：表示在R之前已经扫描过符号串属性值R.s：表示在R完全展开为终止符号之后得到符号串属性值。消除基本文法中左递归：A

XRR

YR|

翻译方案转换为：A

X{R.i=f(X.x)}R{A.a=R.s}R

Y{R1.i=g(R.i,Y,y)}R1{R.s=R1.s}R

{R.s=R.i}

AXR

.x.i.s.aAXR

.x.i.s.aYR.y.i.s51/8551例：考虑建立表示式语法树语法制导定义翻译方案(1)E

E1+T{E.nptr=makenode(

+

,E1.nptr,T.nptr)}(2)E

E1-T{E.nptr=makenode(

-

,E1.nptr,T.nptr)}(3)E

T{E.nptr=T.nptr}(4)T

(E){T.nptr=E.nptr}(5)T

id{T.nptr=makelead(id,id.entry)}(6)T

num{T.nptr=makeleaf(num,num.val)}消除左递归：E

TRR

+TR|-TR|

非终止符号R，含有继承属性R.i和综合属性R.sR.i：保留指向在R之前建立子树根结点指针R.s：保留指向R完全展开之后建立子树根结点指针52/8552结构表示式语法树翻译方案E

T{R.i=T.nptr}R{E.nptr=R.s}R

+T{R1.i=makenode(

+

,R.i,T.nptr)}R1{R.s=R1.s}R

-T{R1.i=makenode(

-

,R.i,T.nptr)}R1{R.s=R1.s}R

{R.s=R.i}T

(E){T.nptr=E.nptr}T

id{T.nptr=makelead(id,id.entry)}T

num{T.nptr=makeleaf(num,num.val)}53/8553使用继承属性结构a-4+c语法树num4id符号表中a入口.nptr-

id符号表中c入口ETRid-TRnum+TRid

.

nptr.

nptr.

i.

i.

i+

.

s.

s.

s.

nptr54/8554二、预测翻译程序设计从翻译方案出发结构自顶向下语法制导翻译程序算法5.2：结构语法制导预测翻译程序输入：基础文法适合于预测分析语法制导翻译方案输出：语法制导翻译程序方法：（修改预测分析程序结构技术）(1)为每个非终止符号A建立一个函数(能够是递归函数)A每一个继承属性对应函数一个形参A综合属性作为函数返回值A产生式中每个文法符号每个属性都对应一个局部变量(2)A函数代码由多个分支组成55/8555按照从左到右次序考虑产生式右部记号、非终止符号和语义动作对带有综合属性x记号X把属性x值保留于为X.x申明变量中产生一个匹配记号X调用推进扫描指针对非终止符号B产生一个函数调用语句c=B(b1,b2,…,bk)bi(i=1,2,…,k)是对应于B继承属性变量c是对应于B综合属性变量对每一个语义动作把动作代码复制到分析程序中用代表属性变量代替翻译方案中引用属性(3)与每个产生式相关程序代码56/8556例：为结构表示式语法树翻译方案

结构翻译程序为每个非终止符号结构一个函数functionE:

syntax_tree_node；function(in:

syntax_tree_node):

syntax_tree_node；functionT:

syntax_tree_node；两个R产生式结合起来，用符号addop代表

+

和

-

R

addopT{R1.i=makenode(addop.lexeme,R.i,T.nptr)}R1{R.s=R1.s}R

{R.s=R.i}57/8557与R

addopTR|

对应分析过程voidproc_R(void){if(lookahead==addop){match(addop);proc_T();proc_R();}};58/8558实现翻译方案函数syntax_tree_nodefun_R(syntax_tree_nodein){syntax_tree_nodetnptr,i1,s1,s;charaddoplexeme;if(lookahead==addop){/*产生式R

addopTR*/addoplexeme=lexval;match(addop);tnptr=fun_T();i1=makenode(addoplexeme,in,tnptr);s1=R(i1);s=s1;};else/*产生式R

*/s=in;returns;};59/85595.4L属性定义自底向上翻译在自底向上分析过程中实现L属性定义翻译能够实现任何基于LL(1)文法L属性定义能够实现许多（不是全部）基于LR(1)文法L属性定义一、从翻译方案中去掉嵌入动作二、分析栈中继承属性三、模拟继承属性计算四、用综合属性代替继承属性60/8560一、从翻译方案中去掉嵌入动作自底向上地处理继承属性等价变换：使全部嵌入动作都出现在产生式右端末尾方法：在基础文法中引入新产生式，形如：M

M：标识非终止符号，用来代替嵌入在产生式中动作把被M替换动作放在产生式M

末尾61/8561例：去掉以下翻译方案中嵌入动作：

E

TR

R

+T{print(

+

)}R|-T{print(

-

)}R|

T

num{print(num.val)}标识非终止符号M和N，及产生式M

和N

用M和N替换出现在R产生式中动作新翻译方案E

TRR

+TMR|-TNR|

T

num{print(num.val)}M

{print(

+

)}N

{print(

-

)}62/8562变换前、后翻译方案是等价numprint(num.val)-Tprint(

-

)R4numprint(num.val)

5numprint(num.val)+Tprint(

+

)R3ETR深度优先次序进行遍历print(num1.val)print(num2.val)print(

+

)print(num3.val)print(

-

)动作执行结果是：34+5-变换前，表示式3+4-5分析树：63/8563变换后，表示式3+4-5分析树：深度优先次序进行遍历print(num1.val)print(num2.val)print(

+

)print(num3.val)print(

-

)动作执行结果是：34+5-Numprint(num.val)

print(

+

)-TNR4Numprint(num.val)

print(

-

)

5Numprint(num.val)+TMR3ETR64/8564二、分析栈中继承属性LR分析程序对产生式A

XY归约考虑分析过程中属性计算65/8565复制规则主要作用翻译方案：D

T{L.in=T.type}LT

int{T.type=integer}T

real{T.type=real}L

{L1.in=L.in}L1,id{addtype(id.entry,L.in)}L

id{addtype(id.entry,L.in)}DTLrealL,rL,qp.type.in.in.in.s.entry.s.entry.s.entry输入符号串：realp,q,r66/8566例：应用继承属性，用复制规则传递标识符类型输入栈分析动作realp,q,r$state:val:移进p,q,r$state:realval:real归约，用T

realp,q,r$state:Tval:real移进,q,r$state:Tpval:realpentry归约，用L

id,q,r$state:TLval:real-移进q,r$state:TL,val:real-,移进,r$state:TL,qval:real-,qentry归约，用L

L,id,r$state:TLval:real-移进r$state:TL,val:real-,移进$state:TL,rval:real-,rentry归约，用L

L,id$state:TLval:real-归约，用D

TL$state:Dval:-接收67/8567计算属性值代码段产生式代码段D

TLT

intval[ntop]=integerT

realval[ntop]=realL

L,idaddtype(val[top],val[top-3])L

idaddtype(val[top],val[top-1])68/8568三、模拟继承属性计算要想从栈中取得继承属性，当且仅当文法允许属性值在栈中存放位置能够预测。例：属性值在栈中位置不可预测语法制导定义产生式语义规则(1)S

aACC.i=A.s(2)S

bABCC.i=A.s(3)C

cC.s=g(C.i)引入标识非终止符号，对原语法制导定义进行等价变换产生式语义规则(1’)

S

aACC.i=A.s(2’)

S

bABMCM.i=A.s；C.i=M.s(3’)C

cC.s=g(C.i)

(4’)M

M.s=M.i SbA.sB.iM.s.iC

69/8569用标识非终止符号模拟

非复制规则语义规则例：考虑以下产生式及语义规则：S

aACC.i=f(A.s)C

cC.s=g(C.i)┉aANc┉A.sN.stop┉aAc┉A.stop引入标识非终止符号NS

aANCN.i=A.s；C.i=N.sN

N.s=f(N.i)全部继承属性均由复制规则实现继承属性在栈中位置能够预测70/8570例：用复制规则设置全部继承属性产生式语义规则S

LBB.ps=L.sS.ht=B.htL

L.s=10B

B1MB2B1.ps=B.psM.i=B.psB2.ps=M.sB.ht=max(B1.ht,B2.ht)B

B1subNB2B1.ps=B.psN.i=B.psB2.ps=N.sB.ht=disp(B1.ht,B2.ht)B

textB.ht=text.h

B.psM

M.s=M.iN

N.s=shrink(N.i)71/8571实现语法制导定义代码段产生式语义规则S

LBval[ntop]=val[top]L

val[ntop]=10B

B1MB2val[ntop]=max(val[top-2],val[top])B

B1subNB2val[ntop]=disp(val[top-3],val[top])B

textval[ntop]=val[top]

val[top-1]M

val[ntop]=val[top-1]N

val[ntop]=shrink(val[top-2]) 72/8572算法5.3：L属性定义自底向上分析和翻译输入：基础文法是LL(1)文法L属性定义输出：在分析过程中计算全部属性值分析程序方法：假设：每个非终止符号A都有一个继承属性A.i每一个文法符号X都有一个综合属性X.s(1)对每个产生式A

X1X2…Xn引入n个新标识非终止符号M1、M2、…、Mn用产生式A

M1X1M2X2…MnXn代替原来产生式Xj继承属性与标识非终止符号Mj相联络属性Xj.i(也就是Mj.s)总是在Mj处计算，且发生在开始做归约到Xj动作之前。73/8573(2)在自底向上分析过程中，各个属性值都能够

被计算出来第一个情况：用Mj

进行归约已知：每个标识非终止符号在文法中是唯一Mj属于哪个形式为A

M1X1M2X2…MnXn产生式计算属性Xj.i需要哪些属性、以及它们位置

M1X1M2X2

…Mj-1Xj-1

A.iX1.iX1.sX2.iX2.s…Xj-1.iXj-1.sstatevaltop-2(j-1)top-2(j-1)+2top-2(j-2)+2toptop-2(j-1)+1top-2(j-2)+1top-1MjMj.sntop74/8574第二种情况：用A

M1X1M2X2…MnXn进行归约已知：A.i值、及其位置计算A.s所需要属性值均已在栈中已知位置 即各相关Xj位置上stateval…M1X1M2X2

…MnXn…A.iX1.iX1.sX2.iX2.s…Xn.iXn.stoptop-2ntop-2n+2top-2n+4stateval…A…A.iA.stoptop-175/8575四、用综合属性代替继承属性例：PASCAL变量申明语句可由以下文法产生：D

L:TT

integer|charL

L,id|id问题：标识符由L产生，而类型不在L子树中归约从左向右进行，类型信息从右向左传递只用综合属性不能使类型和标识符联络在一起DL:TL,rL,qpchar.type.in.in.in...76/8576处理方法改写文法，使类型作为标识符表最终一个元素D

idLL

,idL|:TT

integer|char