《语法制导翻译技术》由会员分享，可在线阅读，更多相关《语法制导翻译技术（85页珍藏版）》请在金锄头文库上搜索。
1、LI Wensheng, SCST, BUPT 第5章 语法制导翻译技术知识点：语法制导定义、翻译方案S属性、L属性S-属性定义的翻译L-属性定义的翻译1Wensheng Li BUPT 2008语法制导翻译技术n语义分析涉及到语言的语义n形式语义学的研究开始于20世纪60年代初n形式语义学可以分为三类 操作语义学：模拟数据加工过程中计算机系统的操作 指称语义学：描述数据加工的结果 公理语义学：用公理化的方法描述程序对数据的加工n语法制导翻译技术 多数编译程序普遍采用的一种技术 比较接近形式化2Wensheng Li BUPT 2008语法制导翻译技术5.1 语法制导定义及翻译方案 5.2 S
2、-属性定义的自底向上翻译 5.3 L-属性定义的自顶向下翻译 5.4 L-属性定义的自底向上翻译 5.5 非L属性定义的翻译小 结3Wensheng Li BUPT 20085.1 语法制导定义及翻译方案n对上下文无关文法的推广n每个文法符号都可以有一个属性集，可以包括两类 属性：综合属性和继承属性。 分析树中一个结点的综合属性是从其子结点的属性值 计算出来的 继承属性是从其兄弟结点和/或父结点的属性值计算 出来的 分析树中某个结点的属性值是由与在这个结点上所用 产生式相应的语义规则决定的。n和产生式相联系的语义规则建立了属性之间的关系 ，这些关系可用有向图（即：依赖图）来表示。4Wenshe
3、ng Li BUPT 2008内容安排一、语法制导定义 二、依赖图 三、计算次序 四、S属性定义和L属性定义 五、翻译方案5Wensheng Li BUPT 2008一、语法制导定义在一个语法制导定义中，对应于每一个文法产生 式A，都有与之相联系的一组语义规则，其形式 为：b=(c1,c2,ck)这里，是一个函数，而且或者 (1) b是A的一个综合属性，且c1、c2、ck是 产生式右部文法符号的属性，或者 (2) b是产生式右部某个文法符号的一个继承属性 ，且c1、c2、ck是A或产生式右部文法符号的属性 。n 属性b依赖于属性c1、c2、ck。n 语义规则函数都不具有副作用的语法制导定义称为
4、属性文法6Wensheng Li BUPT 2008语义规则n一般情况： 语义规则函数可写成表达式的形式。n某些情况下： 一个语义规则的唯一目的就是产生某个副作用，如打 印一个值、向符号表中插入一条记录等； 这样的语义规则通常写成过程调用或程序段。 看成是相应产生式左部非终结符号的虚拟综合属性。 虚属性和符号=都没有表示出来。7Wensheng Li BUPT 2008简单算术表达式求值的语法制导定义n综合属性val与每一个非终结符号E、T、F相联系n表示相应非终结符号所代表的子表达式的整数值nLn的语义规则是一个过程，打印出由E产生的算术表达式 的值，可以认为是非终结符号L的一个虚拟综合属性
5、。产生式 LEnEE1+TETTT1*FTFF(E) Fdigit语义规则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 8Wensheng Li BUPT 2008综合属性n分析树中，如果一个结点的某一属性由其子结点的 属性确定，则这种属性为该结点的综合属性。n如果一个语法制导定义仅仅使用综合属性，则称这 种语法制导定义为S-属性定义。n对于S-属性定义，通常采用自底向上的方法对其分 析树加注释，即从树叶到树根，按照语义规则计算每 个结点的属
6、性值。n简单台式计算机的语法制导定义是S-属性定义9Wensheng Li BUPT 20083*5+4n的分析树加注释的过程n属性值的计算可以在语法分析过程中进行。LE nE + TT FT * F digitF digitdigit.lexval=3.val=3.val=3.lexval=5.val=5.val=15.val=15.lexval=4.val=4.val=4.val=19Print (19)10Wensheng Li BUPT 2008继承属性n分析树中，一个结点的继承属性值由该结点的父结 点和/或它的兄弟结点的属性值决定。n可用继承属性表示程序设计语言结构中上下文之间 的依
7、赖关系 可以跟踪一个标识符的类型 可以跟踪一个标识符，了解它是出现在赋值号的右边 还是左边，以确定是需要该标识符的值还是地址。11Wensheng Li BUPT 2008一个带有继承属性L.in的语法制导定义nD产生的声明包含了类型关键字int或real，后跟一个标 识符表。nT有综合属性type，其值由声明中的关键字确定。nL的继承属性L.in，表示从父结点或兄弟结点继承下来的 类型信息。产生式DTLTintTrealLL1,idLid语义规则L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtyp
8、e(id.entry,L.in) 12Wensheng Li BUPT 2008语句real id1,id2,id3的分析树加注释L产生式的语义规则使用继承属性L.in把类型信息在分析 树中向下传递； 并通过调用过程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)13Wensheng Li BUPT 2008二、依赖图n分析树中
9、，结点的继承属性和综合属性之间的相互 依赖关系可以由依赖图表示。n为每个包含过程调用的语义规则引入一个虚拟综合 属性b，以便把语义规则统一为b=(c1,c2,ck)的 形式。n依赖图中： 为每个属性设置一个结点 如果属性b依赖于c，那么从属性c的结点有一条有向 边连到属性b的结点。14Wensheng Li BUPT 2008算法5.1 构造依赖图输入：一棵分析树 输出：一张依赖图 方法：for (分析树中每一个结点n)for (结点n处的文法符号的每一个属性a)为a在依赖图中建立一个结点;for (分析树中每一个结点n)for (结点n处所用产生式对应的每一个语义规则 b=(c1,c2,ck
10、)for (i=1;i=k;i+)从ci结点到b结点构造一条有向边;15Wensheng Li BUPT 2008依赖图构造举例产生式 依赖规则 AXY A.a=(X.x,Y.y)X.i=g(A.a,Y.y)AX Y.a.x.i.yDT LL , id2L , id3id1real4 type9 in10 addtype7 in 8 addtype5 in6 addtype1 entry2 entry3 entry16Wensheng Li BUPT 2008三、计算次序n有向非循环图的拓扑排序 图中结点的一种排序m1,m2,mk 有向边只能从这个序列中前边的结点指向后面的结 点 如果mimj
11、是从mi指向mj的一条边，那么在序列 中mi必须出现在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、1017Wensheng Li BUPT 2008计算顺序n从拓扑排序中可以得到下面的程序，an代表依赖图 中与序号n的结点有关的属性： a4=real； a5=a4； addtype(id3.entry,a5)； a7=a5； addtype(id2.entry,
12、a7)； a9=a7； addtype(id1.entry,a9)；18Wensheng Li BUPT 2008语法制导翻译过程n最基本的文法用于建立输入符号串的分析树；n为分析树构造依赖图；n对依赖图进行拓扑排序；n从这个序列得到语义规则的计算顺序；n照此计算顺序进行求值，得到对输入符号串的翻译 。 输入符号串分析树依赖图语义规则的计算顺序计算结果19Wensheng Li BUPT 2008四、L属性定义和L属性定义n L属性定义：一个语法制导定义是L属性定义，如 果 与每个产生式AX1X2Xn相应的每条语义规则计 算的属性都是A的综合属性，或是 Xj（1jn）的继承属性，而该继承属性仅
13、依赖于： 产生式中Xj左边的符号X1、X2、Xj-1的属性； A的继承属性。n 每一个S属性定义都是L属性定义20Wensheng Li BUPT 2008例：非L属性定义的语法制导定义产生式 语义规则ALM L.i=l(A.i) M.i=m(L.s)A.s=f(M.s)AQR R.i=r(A.i) Q.i=q(R.s)A.s=f(Q.s)产生式DTLTintTrealLL1,idLid语义规则L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in) 例：是L属性定义 的
14、语法制导定 义 21Wensheng Li BUPT 2008属性计算顺序深度优先遍历分析树void deepfirst(n:node) for (n的每一个子结点m，从左到右) 计算m的继承属性;deepfirst(m);计算n的综合属性; .n以分析树的根结点作为实参nL属性定义的属性都可以用深度优先的顺序计算。进入结点前，计算它的继承属性 从结点返回时，计算它的综合属性22Wensheng Li BUPT 2008五、翻译方案n上下文无关文法的一种便于翻译的书写形式n属性与文法符号相对应n语义动作括在花括号中，并插入到产生式右部某个 合适的位置上n给出了使用语义规则进行属性计算的顺序n分析过程中翻译的注释23Wensheng Li BUPT 2008例：一个简单的翻译方案ETRRaddo
