第6章属性文法及语法制导翻译 (编译原理 陈火旺)

1、1本章在编译程序中的地位 表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理2教学要求 掌握： 两种属性: 综合属性，继承属性 基于属性文法的处理方法-语法制导翻译方法3教学内容 6.1 属性文法 综合属性，继承属性，语义规则，属性文法 6.2 基于属性文法的处理方法 语法制导翻译，依赖图法计算属性，树遍历计算属性，一遍扫描的处理方法，抽象语法树4 CH.6 属性文法和语法制导翻译 在分析-综合模式的编译器中,语义分析是分析过程的最后一个步骤，只有在这一步才真正开始考虑程序语言的意义，并着手把它们翻译成某种中间代码。这一

2、过程通常采用的方法是属性文法和语法制导翻译方法。 语法制导翻译方法的基本思想是，根据翻译的需要设置文法符号的属性，用属性描述语法结构的语义，用属性的计算完成翻译。 属性文法使文法符号属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，从而完成语义分析和翻译的任务。 56.1 属性文法 属性文法, 也称属性翻译文法或语法制导定义,是Knuth在1968年首先提出来的。 属性：在上下文无关文法的基础上为每个文法符号X(终结符或非终结符)配备若干个相关的“值”-这些“值”就称为文法符号X的属性。 属性值的设置和语法结构的语义以及翻译程序的需要有关。 属性代表与文法符号相关语义信息，如类

3、型、值、代码序列、符号表内容等6属性、语义规则、属性文法 属性一般分为两类：综合属性和继承属性。 属性和变量一样，可以在语法分析过程中进行计算和传递。 语义规则：属性的计算规则。属性的加工和计算的过程即是语义处理的过程。 属性文法：以一个上下文无关文法为基础, 为每个文法符号引进一组属性，对文法的每个产生式都配备一组与之相关联的属性的计算规则(语义规则), 这样得到的文法。 属性文法是对上下文无关文法的推广。7属性文法、语义规则(1) 属性文法的形式： 产生式 语义规则 . A b:=f(c1,c2,ck) 这里, f 是一个函数, 表示属性 b 依赖于属性 c1,c2,ck，而且规定b: (

4、1) b是A的一个综合属性并且c1,c2,ck是产生式右部文法符号的属性； 或者 (2) b是产生式右边某个文法符号的一个继承属性并且 c1,c2,ck 是A或产生式右部任何文法符号的属性 。8 属性文法的说明(1) P136n(1) (1) 终结符只有综合属性终结符只有综合属性, ,它它由词法分析器提供由词法分析器提供n例如例如 digit.lexval 表示单词符号表示单词符号“数数”的词法值的词法值 id.entry 表示单词符号表示单词符号“标识符标识符”的符号表入口的符号表入口n(2) (2) 非终结符既可以有综合属性也可以有继承非终结符既可以有综合属性也可以有继承属性属性，在，在属

5、性文法的语义规则中计算属性文法的语义规则中计算n(3) (3) 关于属性计算的规定关于属性计算的规定n 文法的文法的开始符号的所有继承属性开始符号的所有继承属性作为属性计算作为属性计算前的初始值。前的初始值。n 一般来讲，对出现在产生式一般来讲，对出现在产生式 A X1X2Xn左边左边的的非终结符非终结符A的综合属性的综合属性和出现在产生式右部的和出现在产生式右部的符号符号Xi的继承属性的继承属性都必须提供一个计算规则。都必须提供一个计算规则。9属性文法的说明(2)n 与产生式与产生式 A X1X2Xn 相关联的属性计算相关联的属性计算不不能有能有A的继承属性的继承属性和和Xi 的综合属性的综

6、合属性的计算规则。的计算规则。n 出现在出现在产生式左边非终结符产生式左边非终结符A的继承属性的继承属性和出和出现在产生式右边符号现在产生式右边符号Xi 的综合属性的综合属性由其它产生式由其它产生式的属性规则计算或者由属性计算器的参数提供。的属性规则计算或者由属性计算器的参数提供。10属性文法、语义规则(2) 属性文法的形式： 产生式 语义规则 . A b:=f(c1,c2,ck) 例如 P137.表6.1的属性文法: EE1+ T E.val := E1.val+ T.val 例如 P139.表6.2的属性文法: DTL L.in := T.typeLL1 , id L1.in := L.i

7、n综合属性综合属性综合属综合属性性继承属性继承属性继承属性继承属性继承属性继承属性11 例例, , P137.P137. 假设：假设：产生式产生式 语义规则语义规则 A ABC BC A.b:=A.a+B.c A.b:=A.a+B.c C.d C.d:=B.c+1:=B.c+1 A A有综合属性有综合属性b b和继承属性和继承属性a a B B有综合属性有综合属性c c C C有继承属性有继承属性d d继承属性继承属性A.aA.a和和综合综合属性属性B.cB.c在其他适当的地方计算。在其他适当的地方计算。12语义规则所描述的工作 语义规则所描述的工作可以是任何希望的翻译工作，如: 属性计算、静

8、态语义检查、符号表操作、中间代码生成、报告出错， 等等。 语义规则可能产生副作用(如产生代码)，也可能不是变元的严格函数 b:=f(c1,c2,ck) ，如某个规则给出可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段- 这时认为定义了一个虚属性。13属性文法举例：P137.表6.1 一个简单的台式计算器的属性文法。输入一个含+、*、(、)和数字的算术表达式(文法的句子), 计算并输出其值, 输入行以 n 结束。 产生式 语义规则 LEn Print(E.val) EE1+T E.val:=E1.val+T.val ET E.val:=T.val TT1*F T.val:=T1

9、.val*F.val TF T.val:=F.val F(E) F.val:=E.val Fdigit F.val:=digit.lexval1. 非终结符非终结符E, T, FE, T, F有综有综合属性合属性val - val - 表达式值表达式值2.2. 终结符终结符digitdigit有综合属有综合属性性lexval - lexval - 数的二进制数的二进制值，由词法分析器提供值，由词法分析器提供3. 3. 注：注：同一个产生式的相同一个产生式的相同非终结符加上同非终结符加上下标下标，以，以区分这些非终结符的属性区分这些非终结符的属性值引用的二义性值引用的二义性14两种属性：综合属性

10、 综合属性用于“自下而上”传递信息。 综合属性：在语法树中，一个结点的综合属性的值由其子结点的属性值确定。 通常结合使用自下而上的分析方法在每一个结点处使用语义规则计算综合属性的值 - 由下层子结点的属性值计算上层父结点的综合属性值，随着自下而上语法分析的进行，最终可计算出开始符号的综合属性值。A X1 X2 XnA.b X1. .c1 X2 .c.c2 Xn . ckA X1X2Xn b:=f(c1,c2,ck) 带注释的带注释的语法树语法树15综合属性举例：例6.1 综合属性的使用及其自下而上的计算过程 P137.表6.1台式计算器的属性文法，输入一个表达式(以n结尾)，计算并打印其值。

11、例如：输入表达式 3*5+4n，输出数值19。 P138.图6.1给出了输入串3*5+4n的带注释的语法树 属性化的语法树。 综合属性X.val值随着自下而上语法分析的进行，自下而上的计算、传递和流动 - 在每次归约时执行语义规则，计算属性值，最终计算出开始符号的综合属性值，打印出来完成翻译。见下页图16digit lexval digit lexvaldigit lexval F val T1 val F val T val* E1 val F val T val+ E valLnPrint(E.val)翻译翻译3 3* *5+45+4n n求表达式值求表达式值=3=3=5=5=15=15=

12、4=4=4=19=317两种属性：继承属性 继承属性用于“自上而下”传递信息。 继承属性：在语法树中，一个结点的继承属性由此结点的父结点和(或)兄结点的某些属性确定。 可以用继承属性来表示程序语言结构中的上下文依赖关系。 继承属性的计算可以结合自上而下的语法分析进行。A X1 X XnA. ck X1. .c1 X.b Xn A X1X2Xn b:=f(c1,c2,ck) 18 表表6.2 6.2 带有继承属性带有继承属性L.inL.in的属性文法的属性文法 产生式 语义规则 DTL L in:= T type T int T type := integer T real T type :=

13、real L L1, id L1 in := L in addtype(id entry, L in) L id addtype(id entry, L in)n 例例6.26.2 说明句的带有继承属性计算的属性文法说明句的带有继承属性计算的属性文法 T.type 是是 综合属性综合属性 - 标识符标识符的类型的类型 L.in 为为 继承属性继承属性 - 传递类传递类 型信息型信息19继承属性的使用和计算：例6.2 继承属性的使用及其自上而下的计算过程 P137.表6.2的属性文法，用继承属性 L.in 为说明语句中的各个标识符提供类型信息。 例如：说明语句 real a, b, c; int

14、 i, j, k; T.type是综合属性, 由说明语句中的关键字 real / int确定, 结合产生式Tint 或Treal 赋值 T.type := integer 或 real。Tint T.type:=integerTreal T.type:=realT.typeintintT.typereal20继承属性的使用和计算：例6.2续 例6.2, P137.表6.2属性文法，用继承属性 in为说明语句中的各个标识符提供类型信息。 L.in 继承属性, 在DTL L.in:=T.type LL1 , id L1.in:=L.in 中计算。D T.type L.inL.inL1.in ， i

15、d 依赖依赖于兄于兄依赖依赖于父于父nAddtype(id.entry, L.in)Addtype(id.entry, L.in)把标识符的类型信息把标识符的类型信息填入符号表填入符号表, , 入口为入口为id.entry - id.entry - 这个过程定义这个过程定义了一个了一个虚属性虚属性。21图6.2 说明语句 real id1,id2,id3的带有继承属性的语法树继承属性继承属性 in的值自上的值自上而下从左到右计算、而下从左到右计算、传递和流动。传递和流动。三个三个L结点的结点的 L.in分分别给出标识符别给出标识符id1、id2和和id3的类型。的类型。过程过程addtype(

16、id.entry,L.in)把把 id 的类型填入符号的类型填入符号表。表。id3T.type=realDL.in=realL.in=realrealL.in=real,id1id2,226.2 基于属性文法的处理方法 属性文法： 产生式 语义规则 . A b:=f(c1,c2,ck) 语义规则的计算可以执行任何翻译动作。对输入串的翻译也就是根据语义规则进行计算得出结果。 属性文法是比较抽象的翻译说明，隐藏了一些实现细节, 主要是无须指明翻译时语义规则的计算次序。 本节讨论语义规则的计算方法，指明属性文法中语义规则的计算次序，从而把语义规则改造为计算属性的语义程序，把静态的语义规则改写为可动态

17、执行的语义动作 - 语法制导翻译方法。23语法制导翻译法 语法制导翻译法：由源程序的语法结构所驱动的处理办法。 这种处理方法是基于属性文法的处理过程： 对单词符串进行语法分析, 构造带属性的语法树 根据需要遍历语法树, 并在语法树的各结点处按语义规则进行计算即得翻译结果。 P139.图6.3 语法制导翻译的轮廓: 输入串语法树(带属性注释)语法分析深度优先树遍历对输入串的翻译结果进行计算拓扑排序 语义规则 计算次序 结点属性间依赖 关系的依赖图 构造24 所谓遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。25一遍扫描的语法制导翻译一

18、遍扫描的语法制导翻译n一个具体的一个具体的语法制导翻译语法制导翻译的实现不一定非要的实现不一定非要按图按图6.36.3的轮廓不可。在某些情况下可用一遍的轮廓不可。在某些情况下可用一遍扫描实现属性文法的语义规则计算扫描实现属性文法的语义规则计算 - - 即即在在语法分析的同时完成语义规则的计算语法分析的同时完成语义规则的计算。无须无须明显地构造语法树或依赖图明显地构造语法树或依赖图。n此节以后的各节以及此节以后的各节以及CH7.CH7.都讨论这种特殊方都讨论这种特殊方法法 - - 一遍扫描的语法制导翻译方法。一遍扫描的语法制导翻译方法。n一遍扫描的语法制导翻译轮廓一遍扫描的语法制导翻译轮廓: :

19、 输入串输入串 翻译结果翻译结果语法分析的同时语法分析的同时完成语义规则的计算完成语义规则的计算26 6.2.1 依赖图 语义规则建立了属性之间的依赖关系，这些关系可以用图来表示，这样的图称为属性依赖图。 语法树结点属性的依赖图是一个有向图： 结点：语法树结点的属性(综合属性或继承属性) 有向边：属性的依赖关系，如果属性b依赖于属性c，即b:= f(c)，则:n语义规则语义规则 b:= f(c1,c2, , ck)，b可能是一个虚综合属性可能是一个虚综合属性(即即没有没有b, f是一个过程是一个过程)，其依，其依赖图见右图。赖图见右图。n依赖图构造方法见依赖图构造方法见P140.bcbc1ck

20、c227 依赖图：例6.3 简例: 下面属性文法的依赖图： AXY A.a:=f(X.x, Y.y) X.i:=g(A.a, Y.y) n例例6.3: 下面的属性文法的依赖图下面的属性文法的依赖图nEE1+E2 E.val:=E1.val+E2.val语法树语法树EE1 + E2依赖图依赖图 P141. 图图6.4E.valE1.valE2.valA.aX.iX.xY.yA XY28例例6.4 6.4 图图6.5 句子句子 real id1,id2,id3的语法树及依赖图的语法树及依赖图TLLid3Lid2Did1real,4typein 5L.in:=T.typein 7L1.in:=L.i

21、nin 9L1.in:=L.in3 entry6addtype(id.entry,L.in )2 entry8addtype(id.entry,L.in )1 entry10addtype(id.entry,L.in )结点1、2、3是id.entry属性结点6、8、10代表虚属性有向边表示属性的依赖关系数字标识结点表示计算次序29良定义的属性文法 对语义规则 b:= f(c1,c2, , ck)来说, 只有在属性 c1,c2, ,ck均已知的情况才可以使用来计算b。 但，有时会出现一个属性对另一个属性的循环依赖关系。 如果一属性文法不存在属性之间的循环依赖关系，那么该属性文法为良定义的。为了

22、设计编译程序，我们只处理良定义的属性文法。 例如 设p，c1，c2都是属性，以下计算规则就无法对p求值。 p:=f1(c1) c1:=f2(c2) c2:=f3(p) DAG图：良定义属性文法的依赖图， 无环有向图(Directed Acyclic Graph) pc2c130 依赖图法：属性的计算次序 1. 一个有向非循环图(DAG图)的拓扑序: 是图中结点的任何顺序 m1, m2, , mk, 使得有向边必须是从序列中前面的结点指向后面的结点。 也就是说，如果 mi mj 是 mi 到 mj 的一条边，那么在序列中 mi 必须出现在 mj 之前。 2.一个依赖图(DAG图)的任何拓扑排序都

23、给出一个语法树中结点的语义规则计算的有效顺序。 这就是说，在拓扑排序中，在一个结点上，语义规则 b:= f(c1,c2, ck)中的属性 c1,c2, ck 在计算b以前都是可用的。31n例例6.5 P141.图图6 . 5的依赖图的一个拓扑排序是：的依赖图的一个拓扑排序是： 1， 2， 3，4，5，6，7，8，9，10n由此拓扑序可以得到下面的程序由此拓扑序可以得到下面的程序(an代表与代表与n有关的属有关的属性性), 该程序把该程序把3个标识符个标识符 a, b, c 的类型信息的类型信息(real)填入填入符号表中每个标识符对应的符号表项中。符号表中每个标识符对应的符号表项中。程序程序

24、a4:=real; 语义规则语义规则 T.type:=real a5:=a4; L.in:=T.type addtype(id3 entry, a5); 虚属性虚属性 6 a7:=a5; L1.in:=L.in addtype(id2 entry, a7); 虚属性虚属性 8 a9:=a7; L1.in:=L.in addtype(id1 entry, a9); 虚属性虚属性 10依赖图法属性的计算次序：例依赖图法属性的计算次序：例 32n属性文法说明的语法制导翻译是很精确的：属性文法说明的语法制导翻译是很精确的：n(1) (1) 基础文法用于建立输入串的语法分析基础文法用于建立输入串的语法分

25、析树树( (可带属性注释可带属性注释); );n(2) (2) 构造对应语法树的依赖图构造对应语法树的依赖图; ;n(3) (3) 对依赖图进行拓扑排序对依赖图进行拓扑排序; ;n(4) (4) 从拓扑序得到计算语义规则的次序从拓扑序得到计算语义规则的次序; ;n(5) (5) 按此次序计算语义规则便得到输入串按此次序计算语义规则便得到输入串的翻译结果。的翻译结果。依赖图法属性的计算次序：说明依赖图法属性的计算次序：说明 336.2.2 树遍历的属性计算方法 通过语法树遍历计算属性值的方法有很多种。这些方法都假设： 1. 语法树已经建立起来了，并且树中已带有开始符号的继承属性和终结符的综合属性

26、。 2. 然后以某种次序遍历语法树，直至计算出所有结点的属性值。 最常用的遍历方法是深度优先，对语法树自上而下从左到右遍历的方法。对遍历到的结点计算其所有能够计算的属性值。可能需要使用多次树遍历，直到把所有的结点的所有属性都计算出来。 P142. 有一个深度优先树遍历的算法，对任何良定义的属性文法进行属性的计算。用例子说明。34深度优先树遍历计算属性：例6.6 P143.表6.3的属性文法。属性S.a(=0)继, S.b综; X.c继, X.d综; Y.e继, Y.f综; Z.h继, Z.g综 图6.6 产生式 语义规则 SXYZ X.c:=Z.g Y.e:=S.b Z.h:=S.a S.b:

27、=X.d-2 Xx X.d:=2*X.c Yy Y.f:=Y.e*3 Zz Z.g:=Z.h+1xyz.h=0第一次遍历第一次遍历 S.a=0 XYZ.g=1.d=2.c=1.b=0第二次遍历第二次遍历 .e=0.f=0第三次遍历第三次遍历 35 6.2.3 一遍扫描的处理方法 与树遍历的属性计算方法不同，一遍扫描的处理方法是在语法分析的同时计算属性值。 这种属性计算方法与两个因素密切相关: 1. 所采用的语法分析方法(自上而下或自下而上)。 2. 属性的计算次序，即语法分析到什么时候计算属性。 一遍扫描的处理方法语义规则执行的时间: 1. 在自上而下语法分析中，若一个产生式匹配输入串成功时执

28、行与此产生式相应的语义规则。 2. 在自下而上语法分析中，当一个产生式被用于进行归约时，此产生式相应的语义规则就被计算。36一遍扫描的处理方法 按一遍扫描的编译程序模型来理解语法制导翻译方法，直观上说是为基础文法的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。 一遍扫描的属性计算方法是语法分析工作和语义规则的计算穿插进行。但以语法分析作主导。 S-属性文法(仅含综合属性的属性文法)可用于一遍扫描的自下而上分析。 L-属性文法(含有继承属性的属性文法)可用于一遍扫描的自上而下分析。376.2.4 抽象语法树 语法制导翻译以语法树作基础, 实际上, 语法树可以作为一种合适的中间

29、语言形式。 现在对语法树进行改造，去掉那些对翻译不必要的信息，将语法树进行抽象 - 抽象语法树。 在表达式的抽象语法树中，运算符、关键字不作叶子结点而作为内部结点，叶子结点只是运算量。 抽象语法树也可以属性化，给结点加上属性变成带附注的抽象语法树。 语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行，采用的基本方法是一样的。38抽象语法树：简例 例，为下面文法的句子 a-4+c 建立抽象语法树。 E E+T | ET | T T (E) T id | num 为每个运算量或运算符号都建立一个结点。 可以根据表达式的运算顺序自下而上的构造 - 手工构造。a+c4抽象语法树抽象语法树运算符作

30、内运算符作内部结点部结点id(a)E E TE + TTnum(4)id(c )语法树语法树39抽象语法树的实现 抽象语法树中的每一个结点可以由包含几个域的记录来实现；有向边用指针实现。 在一个运算量对应的结点(叶结)中,一个域标识运算量，另一个域是该运算量的属性值(或指针)。 在一个运算符号对应的结点中,一个域标识运算符号，其它域包含指向运算分量的结点的指针。运算符号通常叫做这个结点的标号。 进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值(或指向属性的指针）。numvalid .op . .To entry of id右子树根结右子树根结左子树根结左子树根结40n建立表达式的抽象语法树使用的函数建立表达式的抽象语法树使用的函数, 这些函数返回这些函数返回新建立结点的指针。新建立结点的指针。n1. mknode(op, left, right) 建立一个建立一个运算符号结点运算符号结点，标号是标号是 op, 两个域两个域 left 和和 right 指向左右运算分指向左右运算分量结点的指针。量