l-语法制导翻译技术-5

1、LI Wensheng, SCST, BUPT 第第5章章 语法制导翻译技术语法制导翻译技术知识点：语法制导定义、翻译方案知识点：语法制导定义、翻译方案 S-属性定义、属性定义、L-属性定义属性定义 S-属性定义的翻译属性定义的翻译 L-属性定义的翻译属性定义的翻译Wensheng Li BUPT 20082/84语法制导翻译技术语法制导翻译技术n语义分析涉及到语言的语义语义分析涉及到语言的语义n形式语义学的研究开始于形式语义学的研究开始于2020世纪世纪6060年代初年代初n形式语义学可以分为三类形式语义学可以分为三类操作语义学：操作语义学：通过说明程序在一个机器中是如何执行的来定义程序的通

2、过说明程序在一个机器中是如何执行的来定义程序的语义，着重语义，着重模拟数据加工过程中计算机系统的操作模拟数据加工过程中计算机系统的操作指称语义学：指称语义学：使用数学函数来描述程序和程序的构成，函数通过把语使用数学函数来描述程序和程序的构成，函数通过把语义值联系到正确的语法结构来描述程序的语义，主要义值联系到正确的语法结构来描述程序的语义，主要描述数据加工的描述数据加工的结果结果公理语义学：公理语义学：把数理逻辑应用于语言的语义，语言结构与谓词转换器把数理逻辑应用于语言的语义，语言结构与谓词转换器联系在一起，语言结构的行为以命题刻画，通过描述程序执行对程序联系在一起，语言结构的行为以命题刻画，

3、通过描述程序执行对程序断言的影响来定义程序、语句或语言结构的语义，主要用于程序正确断言的影响来定义程序、语句或语言结构的语义，主要用于程序正确性证明性证明n语法制导翻译技术语法制导翻译技术多数编译程序普遍采用的一种技术多数编译程序普遍采用的一种技术比较接近形式化比较接近形式化Wensheng Li BUPT 20083/84语法制导翻译语法制导翻译n基本思想：为了翻译由上下文无关文法确定的语言，可以对文法符号基本思想：为了翻译由上下文无关文法确定的语言，可以对文法符号附加属性，并且在文法中设置对属性求值的语义规则，语义规则和非附加属性，并且在文法中设置对属性求值的语义规则，语义规则和非终结符的

4、每个产生式相关终结符的每个产生式相关n两种描述语法制导翻译的形式两种描述语法制导翻译的形式 语法制导定义：是关于语言翻译的高层次规格说明，隐去实现细节，不规语法制导定义：是关于语言翻译的高层次规格说明，隐去实现细节，不规定翻译顺序定翻译顺序 翻译方案：给出实现途径，指明语义规则的求值顺序翻译方案：给出实现途径，指明语义规则的求值顺序n语法制导翻译的一般步骤：语法制导翻译的一般步骤：输入符号串 分析树 依赖图 语义规则的计算顺序 计算结果n在某些限制下，可以在一遍扫描中实现，不需要显式地产生分析树和在某些限制下，可以在一遍扫描中实现，不需要显式地产生分析树和依赖图。依赖图。“L-属性属性”定义包

5、含了所有能够不显式构造分析树而完成的定义包含了所有能够不显式构造分析树而完成的翻译翻译Wensheng Li BUPT 20084/84翻译结果翻译结果n生成代码生成代码可以为源程序产生中间代码可以为源程序产生中间代码可以直接生成目标机指令可以直接生成目标机指令n对输入符号串进行解释执行对输入符号串进行解释执行n向符号表中存放信息向符号表中存放信息n给出错误信息给出错误信息n翻译的结果取决于语义规则翻译的结果取决于语义规则使用语义规则进行计算所得到的结果就是对输入符号串使用语义规则进行计算所得到的结果就是对输入符号串进行翻译的结果。进行翻译的结果。Wensheng Li BUPT 20085/

6、84语法制导翻译技术语法制导翻译技术5.1 5.1 语法制导定义及翻译方案语法制导定义及翻译方案5.2 5.2 S-属性定义的自底向上翻译属性定义的自底向上翻译5.3 5.3 L-属性定义的自顶向下翻译属性定义的自顶向下翻译5.4 5.4 L-属性定义的自底向上翻译属性定义的自底向上翻译 小小 结结Wensheng Li BUPT 20086/845.1 5.1 语法制导定义及翻译方案语法制导定义及翻译方案n是上下文无关文法的推广是上下文无关文法的推广n每个文法符号都可以有一个每个文法符号都可以有一个属性集属性集，可以包括两类属性：综，可以包括两类属性：综合属性和继承属性。合属性和继承属性。分

7、析树中一个结点的分析树中一个结点的综合属性综合属性是从其子结点的属性值计算出来的是从其子结点的属性值计算出来的继承属性继承属性是从其兄弟结点和是从其兄弟结点和/ /或父结点的属性值计算出来的或父结点的属性值计算出来的分析树中某个结点的分析树中某个结点的属性值属性值是由与在这个结点上所用产生式相应的是由与在这个结点上所用产生式相应的语语义规则决定的义规则决定的。n依赖图：由语义规则建立的属性之间的关系依赖图：由语义规则建立的属性之间的关系用途：可以得到语义规则的计算顺序用途：可以得到语义规则的计算顺序n语义规则的副作用：语义规则是一个动作或过程语义规则的副作用：语义规则是一个动作或过程n带注释的

8、分析树：每个节点都带有属性值带注释的分析树：每个节点都带有属性值n分析树加注释（装饰分析树）：计算各节点属性值的一系列分析树加注释（装饰分析树）：计算各节点属性值的一系列活动活动Wensheng Li BUPT 20087/84本节内容安排本节内容安排一、语法制导定义一、语法制导定义二、依赖图二、依赖图三、计算次序三、计算次序四、四、S S属性定义和属性定义和L L属性定义属性定义五、翻译方案五、翻译方案Wensheng Li BUPT 20088/84一、语法制导定义一、语法制导定义在一个语法制导定义中，对应于每一个文法产生式在一个语法制导定义中，对应于每一个文法产生式A，都有与之相联系的一

9、组语义规则，其形式为：都有与之相联系的一组语义规则，其形式为：b= (c1,c2,ck) 这里，这里， 是一个函数，而且或者是一个函数，而且或者(1) (1) b是是A的一个综合属性的一个综合属性，且，且c1、c2、ck是产生式是产生式右部文法符号的属性，或者右部文法符号的属性，或者(2) (2) b是产生式是产生式右部某个文法符号的一个继承属性右部某个文法符号的一个继承属性，且，且c1、c2、ck是是A或产生式右部任何文法符号的属性。或产生式右部任何文法符号的属性。n 属性属性b依赖于属性依赖于属性c1、c2、ck。n 语义规则函数都不具有语义规则函数都不具有副作用副作用的语法制导定义称的语

10、法制导定义称 为为属性文法属性文法Wensheng Li BUPT 20089/84语义规则语义规则n一般情况：一般情况：语义规则函数可写成表达式的形式。语义规则函数可写成表达式的形式。n某些情况下：某些情况下：一个语义规则的唯一目的就是一个语义规则的唯一目的就是产生某个副作用产生某个副作用，如打印一，如打印一个值、向符号表中插入一条记录等；个值、向符号表中插入一条记录等；这样的语义规则通常写成这样的语义规则通常写成过程调用或程序段过程调用或程序段。看成是相应产生式左部非终结符号的看成是相应产生式左部非终结符号的虚拟综合属性虚拟综合属性。虚属性和符号虚属性和符号=都没有表示出来。都没有表示出来

11、。Wensheng Li BUPT 200810/84简单算术表达式求值的语法制导定义简单算术表达式求值的语法制导定义n综合属性综合属性val与每一个非终结符号与每一个非终结符号E、T、F相联系相联系n表示相应非终结符号所代表的子表达式的整数值表示相应非终结符号所代表的子表达式的整数值nLE的语义规则是一个过程，打印出由的语义规则是一个过程，打印出由E E产生的算术表达式产生的算术表达式的值，可以认为是非终结符号的值，可以认为是非终结符号L的一个虚拟综合属性的一个虚拟综合属性。 产生式产生式 LE EE1+T ET TT1*F TF F(E) Fdigit 语义规则语义规则 print(E.v

12、al) E.val=E1.val+T.val E.val=T.val T.val=T1.val*F.val T.val=F.val F.val=E.val F.val=digit.lexval Wensheng Li BUPT 200811/84综合属性综合属性n分析树中，如果一个结点的某一属性由其子结点的分析树中，如果一个结点的某一属性由其子结点的属性确定，则这种属性为该结点的属性确定，则这种属性为该结点的综合属性。综合属性。n如果一个语法制导定义仅仅使用综合属性，则称这如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为种语法制导定义为S-属性定义属性定义。n对于对于S-属性定义，

13、通常采用属性定义，通常采用自底向上自底向上的方法对其分的方法对其分析树加注释，即从树叶到树根，按照语义规则计算析树加注释，即从树叶到树根，按照语义规则计算每个结点的属性值。每个结点的属性值。n简单台式计算机的语法制导定义是简单台式计算机的语法制导定义是S-属性定义属性定义Wensheng Li BUPT 200812/843*5+4的分析树加注释的过程的分析树加注释的过程n属性值的计算可以在语法分析过程中进行。属性值的计算可以在语法分析过程中进行。LE E + TT FT * F digitF digitdigit.lexval=3.val=3.val=3.lexval=5.val=5.val

14、=15.val=15.lexval=4.val=4.val=4.val=19Print (19)?Wensheng Li BUPT 200813/84继承属性继承属性n分析树中，一个结点的分析树中，一个结点的继承属性继承属性值由该结点的父结值由该结点的父结点和点和/ /或它的兄弟结点的属性值决定。或它的兄弟结点的属性值决定。n可用继承属性表示程序设计语言结构中可用继承属性表示程序设计语言结构中上下文之间上下文之间的依赖关系的依赖关系可以跟踪一个标识符的类型可以跟踪一个标识符的类型可以跟踪一个标识符，了解它是出现在赋值号的右边还是可以跟踪一个标识符，了解它是出现在赋值号的右边还是左边，以确定是需

15、要该标识符的值还是地址。左边，以确定是需要该标识符的值还是地址。Wensheng Li BUPT 200814/84用继承属性用继承属性L.in传递类型信息传递类型信息的语法制导定义的语法制导定义nD产生的声明语句包含了类型关键字产生的声明语句包含了类型关键字int或或real，后跟一个，后跟一个标识符表。标识符表。nT有综合属性有综合属性type，其值由声明中的关键字确定。，其值由声明中的关键字确定。nL的继承属性的继承属性L.in，产生式产生式DTL, , L.in 表表示从其兄弟结点示从其兄弟结点T继承下来的类型信息。继承下来的类型信息。产生式产生式LL1,id， L1.in 表表示从其

16、父结点示从其父结点L继承下来的类型信息继承下来的类型信息 产生式产生式 DTL Tint Treal LL1,id Lid 语义规则语义规则 L.in=T.type T.type=integer T.type=real L1.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) Wensheng Li BUPT 200815/84语句语句real id1,id2,id3的注释分析树的注释分析树L产生式的语义规则使用继承属性产生式的语义规则使用继承属性L.in把类型信息在分析树把类型信息在分析树中向下传递；中向下传递；并通过调用过程并通过调用

17、过程addtype，把类型信息填入标识符在符号表，把类型信息填入标识符在符号表中相应的表项中。中相应的表项中。 DT LL , id2L , id3id1real.type=real.in=real.in=real.in=realaddtype(id3.entry,L.in)addtype(id1.entry,L.in) )addtype(id2.entry,L.in)?Wensheng Li BUPT 200816/84二、二、依赖图依赖图n分析树中，结点的继承属性和综合属性之间的相互分析树中，结点的继承属性和综合属性之间的相互依赖关系可以由依赖图表示。依赖关系可以由依赖图表示。n为每个包含

18、过程调用的语义规则引入一个为每个包含过程调用的语义规则引入一个虚拟综合虚拟综合属性属性b，以便把语义规则统一为，以便把语义规则统一为b= (c1,c2,ck)的形式。的形式。n依赖图中：依赖图中：为每个属性设置一个结点为每个属性设置一个结点如果属性如果属性b依赖于依赖于c，那么从属性，那么从属性c的结点有一条有向边连的结点有一条有向边连到属性到属性b的结点。的结点。Wensheng Li BUPT 200817/84算法算法5.1 5.1 构造依赖图构造依赖图输入：一棵分析树输入：一棵分析树输出：一张依赖图输出：一张依赖图方法：方法： for (分析树中每一个结点分析树中每一个结点n) for

19、 (结点结点n处的文法符号的每一个属性处的文法符号的每一个属性a) 为为a在依赖图中建立一个结点在依赖图中建立一个结点; for (分析树中每一个结点分析树中每一个结点n) for (结点结点n处所用产生式对应的每一个处所用产生式对应的每一个 语义规则语义规则 b= (c1,c2,ck) for (i=1;i=k;i+) 从从ci结点到结点到b结点构造一条有向边结点构造一条有向边;Wensheng Li BUPT 200818/84依赖图构造举例依赖图构造举例产生式产生式 依赖规则依赖规则 A AXY A.a=XY A.a= (X.x,Y.y)(X.x,Y.y) X.i=g(A.a,Y.y)

20、X.i=g(A.a,Y.y) AX Y.a.x.i.yDT LL , id2L , id3id1real4 type9 in10 addtype7 in 8 addtype5 in6 addtype 1 entry 2 entry 3 entry?Wensheng Li BUPT 200819/84三、计算次序三、计算次序n有向非循环图的有向非循环图的拓扑排序拓扑排序图中结点的一种排序图中结点的一种排序m1,m2,mk有向边只能从这个序列中前边的结点指向后面的结点有向边只能从这个序列中前边的结点指向后面的结点如果如果mimj是从是从mi指向指向mj的一条边，那么在序列中的一条边，那么在序列中m

21、i必须出现在必须出现在mj之前。之前。n依赖图的依赖图的任何任何拓扑排序拓扑排序给出了分析树中结点的语义规则计算的给出了分析树中结点的语义规则计算的有效有效顺序顺序在拓扑排序中，一个结点上语义规则在拓扑排序中，一个结点上语义规则 b= (c1,c2,ck) 中的属性中的属性c1,c2,ck在计算在计算b时都时都是可用的。是可用的。n拓扑排序：拓扑排序： 1、2、3、4、5、6、7、8、9、10 4、5、3、6、7、2、8、9、1、10?Wensheng Li BUPT 200820/84计算顺序计算顺序n从拓扑排序中可以得到下面的程序，从拓扑排序中可以得到下面的程序，a an n代表依赖图代表

22、依赖图中与序号中与序号n n的结点有关的属性：的结点有关的属性：a a4 4:=real:=real；a a5 5:=a:=a4 4；addtype(idaddtype(id3 3.entry,a.entry,a5 5) )；a a7 7:=a:=a5 5；addtype(idaddtype(id2 2.entry,a.entry,a7 7) )；a a9 9:=a:=a7 7；addtype(idaddtype(id1 1.entry,a.entry,a9 9) )；Wensheng Li BUPT 200821/84语法制导翻译过程语法制导翻译过程n最基本的文法用于建立输入符号串的分析树；

23、最基本的文法用于建立输入符号串的分析树；n为分析树构造依赖图；为分析树构造依赖图；n对依赖图进行拓扑排序；对依赖图进行拓扑排序；n从这个序列得到语义规则的计算顺序；从这个序列得到语义规则的计算顺序；n照此计算顺序进行求值，得到对输入符号串的翻译。照此计算顺序进行求值，得到对输入符号串的翻译。输入符号串输入符号串 分析树分析树 依赖图依赖图 语义规则的计算顺序语义规则的计算顺序 计算结果计算结果Wensheng Li BUPT 200822/84四、四、S属性定义和属性定义和L属性定义属性定义n S属性定义：仅涉及综合属性的语法制导定义属性定义：仅涉及综合属性的语法制导定义n L属性定义：一个语

24、法制导定义是属性定义：一个语法制导定义是L属性定义属性定义，如果，如果与每个产生式与每个产生式AX1X2Xn相应的每条语义规则计算的相应的每条语义规则计算的属性都是属性都是A的综合属性的综合属性，或是，或是Xj（1 j n）的继承属性的继承属性，而该继承属性而该继承属性仅依赖于仅依赖于： A的继承属性；的继承属性； 产生式中产生式中Xj左边的符号左边的符号X1、X2、Xj-1的属性；的属性；n 每一个每一个S属性定义都是属性定义都是L L属性定义属性定义Wensheng Li BUPT 200823/84例：非例：非L属性定义的属性定义的 语法制导定义语法制导定义产生式产生式 语义规则语义规则

25、 A ALM L.i=l(A.i) LM L.i=l(A.i) M.i=m(L.s) M.i=m(L.s) A.s=f(M.s) A.s=f(M.s) A AQR R.i=r(A.i) QR R.i=r(A.i) Q.i=q(R.s) Q.i=q(R.s) A.s=f(Q.s) A.s=f(Q.s) 产生式产生式 D DTLTL T Tintint T Trealreal L LL L1 1,id,id L Lidid 语义规则语义规则 L.in=T.typeL.in=T.type T.type=integer T.type=integer T.type=real T.type=real L

26、L1 1.in=L.in.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) addtype(id.entry,L.in) addtype(id.entry,L.in) 例：是例：是L属性定义的属性定义的 语法制导定义语法制导定义 Wensheng Li BUPT 200824/84属性计算顺序属性计算顺序深度优先遍历分析树深度优先遍历分析树 void deepfirst (n: node) for (n的每一个子结点的每一个子结点m，从左到右，从左到右) 计算计算m的继承属性的继承属性; deepfirst(m); ; 计算计算n的综合

27、属性的综合属性;.n以分析树的根结点作为以分析树的根结点作为实参实参nL属性定义的属性都可以用属性定义的属性都可以用深度优先的顺序深度优先的顺序计算。计算。 进入进入结点前，计算它的继承属性结点前，计算它的继承属性 从结点从结点返回返回时，计算它的综合属性时，计算它的综合属性Wensheng Li BUPT 200825/84五、翻译方案五、翻译方案n上下文无关文法的一种便于翻译的书写形式上下文无关文法的一种便于翻译的书写形式n属性与文法符号相对应属性与文法符号相对应n语义动作括在花括号中，并插入到产生式右部某个语义动作括在花括号中，并插入到产生式右部某个合适的位置上合适的位置上n给出了使用语

28、义规则进行属性计算的顺序给出了使用语义规则进行属性计算的顺序n分析过程中翻译的注释分析过程中翻译的注释Wensheng Li BUPT 200826/84例：一个简单的翻译方案例：一个简单的翻译方案 ETR R+T print（+） R1 | -T print（-） R1 | Tnum print(num.val) 9-5+2的分析树：的分析树：ET R9 - T R5 + T R2 语义动作作为相应产生式左部符号对应结点的子结点语义动作作为相应产生式左部符号对应结点的子结点深度优先遍历树中结点，执行其中的动作，打印出深度优先遍历树中结点，执行其中的动作，打印出95-2+print(print

29、( 9 9 ) print(print( - - ) print(print( 5 5 ) print() print( + + ) print(print( 2 2 ) Wensheng Li BUPT 200827/84翻译方案的设计翻译方案的设计n对于对于S属性定义：属性定义：为每一个语义规则建立一个包含赋值的动作为每一个语义规则建立一个包含赋值的动作把这个动作放在相应的产生式右边末尾把这个动作放在相应的产生式右边末尾例：例：产生式产生式 语义规则语义规则 TT1*F T.val=T1.val*F.val 如下安排产生式和语义动作：如下安排产生式和语义动作： TT1*FT.val=T1.

30、val*F.val Wensheng Li BUPT 200828/84为为L L属性定义设计翻译方案的原则属性定义设计翻译方案的原则n既有综合属性又有继承属性，要遵守以下三条原则既有综合属性又有继承属性，要遵守以下三条原则产生式右部文法符号的产生式右部文法符号的继承属性继承属性必须在这个符号以前的动必须在这个符号以前的动作中计算出来，即计算该继承属性的动作必须出现在相应作中计算出来，即计算该继承属性的动作必须出现在相应文法符号之前文法符号之前一个动作不能引用这个动作右边的文法符号的综合属性一个动作不能引用这个动作右边的文法符号的综合属性1.1.产生式左边非终结符号的产生式左边非终结符号的综合

31、属性综合属性只有在它所引用的所有只有在它所引用的所有属性都计算出来之后才能计算，这种属性的计算动作通常属性都计算出来之后才能计算，这种属性的计算动作通常放在产生式右部的末端放在产生式右部的末端Wensheng Li BUPT 200829/84例：考虑如下翻译方案例：考虑如下翻译方案 S SA A1 1A A2 2 A A1 1.in:=1.in:=1；A A2 2.in:=2.in:=2 A Aa print(A.in)a print(A.in)S SA1A1 A2 A2 A1.in:=1;A2.in:=2A1.in:=1;A2.in:=2a a print(A.in)print(A.in)

32、a a print(A.in)print(A.in)a a print(A.in)print(A.in)S SA1.in:=1;A2.in:=2A1.in:=1;A2.in:=2 A1 A2 A1 A2 a a print(A.in)print(A.in)不满足要求不满足要求1修改：修改：S SAA1 1.in:=1.in:=1；A A2 2.in:=2A.in:=2A1 1A A2 2 或：或：S SAA1 1.in:=1A.in:=1A1 1AA2 2.in:=2A.in:=2A2 2 ； Wensheng Li BUPT 200830/84L L属性定义翻译方案设计举例属性定义翻译方案设

33、计举例n语法制导定义语法制导定义 产生式产生式 DTL Tint Treal LL1,id Lid 语义规则语义规则 L.in=T.type T.type=integer T.type=real L1.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in) DT 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) n翻译方案翻译方案Wensheng Li

34、 BUPT 200831/84例：为如下例：为如下L属性定义设计翻译方案属性定义设计翻译方案nL属性定义属性定义n唯一的继承属性是非终结符号唯一的继承属性是非终结符号B的的ps属性属性 依赖于左部符号的继承属性，或者依赖于左部符号的继承属性，或者 常数常数 产生式产生式 语义规则语义规则 SB B.ps=10 S.ht=B.ht BB1B2 B1.ps=B.ps B2.ps=B.ps B.ht=max(B1.ht,B2.ht) BB1subB2 B1.ps=B.ps B2.ps=shrink(B.ps) B.ht=disp(B1.ht,B2.ht) Btext B.ht=text.h B.ps

35、Wensheng Li BUPT 200832/84例：例：16x16 点阵的点阵的“豪豪”字字 放大放大 10 倍的倍的“豪豪” 位信息位信息 字模数据字模数据Wensheng Li BUPT 200833/84把语义规则插入到产生式中适当的位置把语义规则插入到产生式中适当的位置SB.ps=10 B S.ht=B.htS B.ps=10 B S.ht=B.htB B1.ps=B.psB1 B2.ps=B.psB2 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

36、 B.ht=text.h B.ps ?Wensheng Li BUPT 200834/844.2 S-4.2 S-属性定义的自底向上翻译属性定义的自底向上翻译nS S属性定义：属性定义：只用综合属性的语法制导定义只用综合属性的语法制导定义一、一、S S属性定义的自底向上实现属性定义的自底向上实现二、语法树二、语法树三、构造表达式的语法树三、构造表达式的语法树四、构造表达式的语法树的语法制导定义四、构造表达式的语法树的语法制导定义五、表达式的有向非循环图（五、表达式的有向非循环图（dagdag）Wensheng Li BUPT 200835/84一、一、S-S-属性定义的自底向上实现属性定义的自

37、底向上实现n已知已知自底向上的分析方法中，分析器使用一个自底向上的分析方法中，分析器使用一个栈栈来存放已经来存放已经分析过的子树的信息。分析过的子树的信息。分析树中某结点的分析树中某结点的综合属性综合属性由其子结点的属性值计算得由其子结点的属性值计算得到到自底向上的分析器在分析输入符号串的自底向上的分析器在分析输入符号串的同时同时可以计算综可以计算综合属性合属性n考虑考虑如何如何保存保存文法符号的综合文法符号的综合属性值属性值？保存属性值的保存属性值的数据结构数据结构怎样与怎样与分析栈相联系分析栈相联系？怎样保证怎样保证：每当进行归约时，由栈中正在归约的产生式：每当进行归约时，由栈中正在归约的

38、产生式右部符号的属性值计算其左部符号的综合属性值。右部符号的属性值计算其左部符号的综合属性值。Wensheng Li BUPT 200836/84扩充分析栈扩充分析栈目的：使之能够保存综合属性目的：使之能够保存综合属性做法：在分析栈中做法：在分析栈中增加一个域增加一个域，来存放综合属性值，来存放综合属性值例：带有综合属性域的分析栈例：带有综合属性域的分析栈n栈由一对数组栈由一对数组statestate和和valval实现实现nstatestate元素是指向元素是指向LR(1)LR(1)分析表分析表中状态的指针（或索引）中状态的指针（或索引）n如果如果stateistatei对应的符号为对应的符

39、号为A A，valivali中就存放分析树中与结中就存放分析树中与结点点A A对应的属性值。对应的属性值。n假设假设综合属性刚好在每次归约前计算综合属性刚好在每次归约前计算A AXYZXYZ对应的语义规则是对应的语义规则是A.a:=A.a:= (X.x,Y.y,Z.z)(X.x,Y.y,Z.z) Z Z.z Y Y.y X X.x topstate valWensheng Li BUPT 200837/84修改分析程序修改分析程序n对于终结符号对于终结符号其综合属性值由词法分析器产生其综合属性值由词法分析器产生当分析器执行移进操作时，其属性值随终结符号（或当分析器执行移进操作时，其属性值随终结

40、符号（或状态符号）一起入栈。状态符号）一起入栈。n为每个语义规则编写一段代码，以计算属性值为每个语义规则编写一段代码，以计算属性值n对每一个产生式对每一个产生式A AXYZXYZ把属性值的计算把属性值的计算与归约动作联系起来与归约动作联系起来归约前，归约前，执行执行与产生式相关的与产生式相关的代码段代码段归约：右部符号及其属性出栈归约：右部符号及其属性出栈 左部符号及其属性入栈左部符号及其属性入栈nLRLR分析器中应增加计算属性值的代码段分析器中应增加计算属性值的代码段Z Z.zY Y.y X X.x. . . . . .state val top A A.a. . . . . .state

41、val top Wensheng Li BUPT 200838/84例：用例：用LRLR分析器实现台式计算器分析器实现台式计算器栈指针变量栈指针变量toptop（栈顶）和（栈顶）和ntopntop（新栈顶）的控制：（新栈顶）的控制：当用当用 A A 归约时，若归约时，若| | |=r|=r，在执行相应的代码段之，在执行相应的代码段之前，前， ntop:=top-r+1ntop:=top-r+1。在每一个代码段被执行之后，在每一个代码段被执行之后，top:=ntoptop:=ntop 产生式产生式 LEn EE1+TETTT1*FTFF(E) Fdigit 语义规则语义规则print(E.val

42、) E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval 代码段代码段 print(valtop) valntop:=valtop-2+valtop valntop:=valtop-2*valtop valntop:=valtop-1 Wensheng Li BUPT 200839/84对对 3 3* *5+4n 5+4n 进行分析的动作序列进行分析的动作序列 步骤 输入 分析栈 分析动作 (1) 3*5+4n state: - val: - 移进 (2) *5

43、+4n state: digit val: 3 归约，用Fdigit (3) *5+4n state: F val: 3 归约，用TF (4) *5+4n state: T val: 3 移进 (5) 5+4n state: T * val: 3 - 移进 (6) +4n state: T * digit val: 3 - 5 归约，用Fdigit (7) +4n state: T * F val: 3 - 5 归约，用TT*F (8) +4n state: T val: 15 归约，用ETWensheng Li BUPT 200840/84 (8) +4n state: T val: 15

44、归约，用ET (9) +4n state: E val:15 移进(10) 4n state: E + val:15 - 移进(11) n state: E + digit val:15 - 4 归约，用Fdigit(12) n state: E + F val:15 - 4 归约，用TF(13) n state: E + T val:15 - 4 归约，用EE+T(14) n state: E val:19 移进(15) state: E n val:19 - 归约，用LEn(16) state: L val:19 接受Wensheng Li BUPT 200841/84步骤 输入 分析栈

45、分析动作(1) 3*5+4n state: 0 val: - 移进(2) *5+4n state: 0 6 val: - 3 归约，用Fdigit(3) *5+4n state: 0 4 val: - 3 归约，用TF(4) *5+4n state: 0 3 val: - 3 移进(5) 5+4n state: 0 3 9 val: - 3 - 移进(6) +4n state: 0 3 9 6 val: - 3 - 5 归约，用Fdigit(7) +4n state: 0 3 9 12 val: - 3 - 5 归约，用TT*F(8) +4n state: 0 3 val: - 15 归约，用

46、ETWensheng Li BUPT 200842/84(8) +4n state: 0 3 val: - 15 归约，用ET(9) +4n state: 0 2 val: - 15 移进(10) 4n state: 0 2 8 val: - 15 - 移进(11) n state: 0 2 8 6 val: - 15 4 归约，用Fdigit(12) n state: 0 2 8 4 val: - 15 4 归约，用TF(13) n state: 0 2 8 11 val: - 15 4 归约，用EE+T(14) n state: 0 2 val: - 19 移进(15) state: 0

47、2 7 val: - 19 - 归约，用LEn(16) state: 0 1 val: - 19 接受Wensheng Li BUPT 200843/84二、语法树二、语法树n把语法规则中对语义无关紧要的具体规定去掉，剩把语法规则中对语义无关紧要的具体规定去掉，剩下来的本质性的东西称为下来的本质性的东西称为抽象语法抽象语法。n如：如：赋值语句：赋值语句：x=yx=y、x:=yx:=y、或、或y yx x抽象形式：抽象形式：assignment(variable,expression)assignment(variable,expression)n语法树（也称为语法结构树或结构树）：语法树（也称

48、为语法结构树或结构树）：语法树反映抽象的语法结构，分析树反映具体的语法结构语法树反映抽象的语法结构，分析树反映具体的语法结构按照语言结构的自然层次关系，完全用终结符号构造出的按照语言结构的自然层次关系，完全用终结符号构造出的树结构树结构内部结点内部结点表示运算符号，其表示运算符号，其子结点子结点表示它的运算分量。表示它的运算分量。分析树的抽象（或压缩）形式。分析树的抽象（或压缩）形式。1.1.算符和关键字都不在叶结点中出现算符和关键字都不在叶结点中出现2.2.单产生式的链可以被压缩（单产生式指单产生式的链可以被压缩（单产生式指A AX X）Wensheng Li BUPT 200844/84语

49、法树示例语法树示例nS Sif E then Sif E then S1 1 else S else S2 2 的语法树的语法树if - then - elseE S1 S2+ * 4 3 5n表达式表达式 3 3* *5+4 5+4 的语法树的语法树LE nE + TT FT * F digitF digitdigitWensheng Li BUPT 200845/84三、构造表达式的语法树三、构造表达式的语法树n表达式的语法树的形式表达式的语法树的形式每一个运算符号或运算分量都对应树中的一个结点每一个运算符号或运算分量都对应树中的一个结点运算符号结点的子结点分别是与该运算符的各个运算分运算

50、符号结点的子结点分别是与该运算符的各个运算分量相应的子树的根。量相应的子树的根。每一个结点可包含若干个域：每一个结点可包含若干个域： 标识域、指针域、属性值域等标识域、指针域、属性值域等n在运算符结点中在运算符结点中一个域标识运算符号一个域标识运算符号其它各域包含指向与各运算分量相应的结点的指针其它各域包含指向与各运算分量相应的结点的指针称运算符号为该结点的标号称运算符号为该结点的标号Wensheng Li BUPT 200846/84构造函数构造函数nmakenode(op,left,right)makenode(op,left,right)：建立一个运算符号结点，标号是建立一个运算符号结点

51、，标号是opop；域域leftleft和和rightright是指向其左右运算分量结点的指针。是指向其左右运算分量结点的指针。nmakeleaf(id,entry)makeleaf(id,entry)：建立一个标识符结点，标号是建立一个标识符结点，标号是idid；域域entryentry是指向该标识符在符号表中的相应条目的指针。是指向该标识符在符号表中的相应条目的指针。nmakeleaf(num,val)makeleaf(num,val)：建立一个数结点，标号为建立一个数结点，标号为numnum；域域valval用于保存该数的值。用于保存该数的值。Wensheng Li BUPT 200847

52、/84建立表达式建立表达式a*4+b的语法树的语法树p1=makeleaf(id,entrya); id符号表中符号表中a的入口的入口P1num 4P2 * P3 id符号表中符号表中b的入口的入口P4 + P5+ * b a 4p2=makeleaf(num,4);p3=makenode(*,p1,p2);p4=makeleaf(id,entryb);p5=makenode(+,p3,p4);Wensheng Li BUPT 200848/84四、构造表达式语法树的语法制导定义四、构造表达式语法树的语法制导定义n目标：为表达式创建语法树目标：为表达式创建语法树n产生式语义：创建与产生式左部符

53、号代表的子表达产生式语义：创建与产生式左部符号代表的子表达式对应的子树，即创建子树的根结点。式对应的子树，即创建子树的根结点。n文法符号的属性：记录所建结点，文法符号的属性：记录所建结点， E.nptr、 T.nptr、F.nptr 指向相应子树根结点的指针指向相应子树根结点的指针n产生式的语义动作举例：产生式的语义动作举例： E EE E1 1+T E.nptr=makenode(+T E.nptr=makenode( + + ,E,E1 1.nptr,T.nptr).nptr,T.nptr)T TF T.nptr=F.nptrF T.nptr=F.nptr F Fid F.nptr=mak

54、eleaf(id, id.entry)id F.nptr=makeleaf(id, id.entry)F Fnum F.nptr=makeleaf(num, num.val)num F.nptr=makeleaf(num, num.val)Wensheng Li BUPT 200849/84构造表达式语法树的语法制导定义构造表达式语法树的语法制导定义 n为了记录在构造过程中建立的子树为了记录在构造过程中建立的子树，为每个非终结符号引入，为每个非终结符号引入一个一个综合属性综合属性nptr。nnptrnptr是一个指针，指向语法树中相应非终结符号产生的表达是一个指针，指向语法树中相应非终结符号产

55、生的表达式子树的根结点。式子树的根结点。产生式产生式E EE E1 1+T+TE ET TT TT T1 1* * F FT TF FF F(E)(E)F FididF FnumnumE.nptr= makenode(E.nptr= makenode( + + ,E,E1 1.nptr,T.nptr).nptr,T.nptr)E.nptr=T.nptrE.nptr=T.nptrT.nptr= makenode(T.nptr= makenode( * * ,T,T1 1.nptr,F.nptr).nptr,F.nptr)T.nptr= F.nptrT.nptr= F.nptrF.nptr= E.

56、nptrF.nptr= E.nptrF.nptr= makeleaf(id,id.entry)F.nptr= makeleaf(id,id.entry)F.nptr= makeleaf(num,num.val)F.nptr= makeleaf(num,num.val)语义规则语义规则Wensheng Li BUPT 200850/84表达式a*4+b的语法树的构造num 4 id符号表中符号表中a的入口的入口a a E E E ET TF Fb b 4 4 . nptr. nptr. nptr. nptr. nptr. nptr * * id符号表中符号表中b的入口的入口 + + * *F F

57、 + +T T EE1+TETTT1*FTFF(E)FidFnumE.nptr= makenode(E.nptr= makenode( + + ,E,E1 1.nptr,T.nptr).nptr,T.nptr)E.nptr=T.nptrE.nptr=T.nptrT.nptr= makenode(T.nptr= makenode( * * ,T,T1 1.nptr,F.nptr).nptr,F.nptr)T.nptr= F.nptrT.nptr= F.nptrF.nptr= E.nptrF.nptr= E.nptrF.nptr= makeleaf(id,id.entry)F.nptr= make

58、leaf(id,id.entry)F.nptr= makeleaf(num,num.val)F.nptr= makeleaf(num,num.val)F F . nptrT T . nptrWensheng Li BUPT 200851/84五、表达式的有向非循环图五、表达式的有向非循环图(dag)(dag)ndagdag与语法树相同的地方：与语法树相同的地方：表达式的每一个子表达式都有一个结点表达式的每一个子表达式都有一个结点一个内部结点表示一个运算符号，且它的子结点表示它一个内部结点表示一个运算符号，且它的子结点表示它的运算分量。的运算分量。ndagdag与语法树不同的地方：与语法树不同的

59、地方：dagdag中，对应一个公共子表达式的结点具有多个父结点中，对应一个公共子表达式的结点具有多个父结点语法树中，公共子表达式被表示为重复的子树语法树中，公共子表达式被表示为重复的子树n为表达式创建为表达式创建dagdag的函数的函数makenodemakenode和和makeleafmakeleaf建立新结点之前先检查是否已经存在一个相同的结点建立新结点之前先检查是否已经存在一个相同的结点若已存在，返回一个指向先前已构造好的结点的指针；若已存在，返回一个指向先前已构造好的结点的指针；否则，创建一个新结点，返回指向新结点的指针。否则，创建一个新结点，返回指向新结点的指针。Wensheng L

60、i BUPT 200852/84实现方法（实现方法（FortranFortran语言）语言）n结点用记录实现，并存于数组中，用数组下标来引用一个结点用记录实现，并存于数组中，用数组下标来引用一个结点，下标叫做它的值编号结点，下标叫做它的值编号n例：例：赋值语句i:=i+10 dag := + i 10 表示123453 32 21 1:=:=1 1+ +1010ididnumnumn 构造dag结点的值编号方法算符结点表示成一个三元组op, l, r，由标记op，左儿子l和右儿子r组成输入：输入：标记op，结点l和r；输出：输出：基本结构为op, l, r的结点方法：方法：搜索数组，寻找结点m