第6章 属性文法和语法制导翻译

1、第六章属性文法和语法制导翻译第六章属性文法和语法制导翻译 “语义分析”是编译程序最实质性的工作。语义 分析程序在整个编译过程中，首次对源程序的语 义做出解释，引起源程序发生质的变化，而词法 分析和语法分析仅是对源程序形式上的识别和处 理。 高级程序语言结构的形式化描述已经有比较成熟 的技术，由于这种形式化描述的完善，使分析器 的构造甚至自动构造是比较容易的。 1 编译程序的语义分析涉及到语言的语义，语义形 式化是个专门的研究课题. 形式语义学（如指称语义学、公理语义学、操作 语义学等）的研究从20世纪60年代已经开始， 并且在理论研究方面也有了重要的进展。但不论 哪种方法，其本身的符号系统比较

2、繁杂，其描述 文本不易读，尚不便借助这些形式系统自动完成 语义处理任务。并且在工程实现和应用方面还有 一定的差距。 2 目前实际应用中较流行的语义描述和语义处理方 法主要还是属性文法和语法制导翻译方法。但它 仍不是一种形式系统，只是比较接近形式化。 语法制导翻译方法的实质是在语法分析过程中同 时进行语义处理的翻译技术。这种方法使用属性 文法为工具来说明程序设计语言的语义。 3 第六章属性文法和语法制导翻译第六章属性文法和语法制导翻译 6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S属性文法的自下而上计算 6.4 L属性文法和自顶向下翻译 6.5 自下而上计算继承属性 4 6.1 属

3、性文法 一、基本概念 1、属性 广广义义：用以描述事物或人的特征、性：用以描述事物或人的特征、性质质、品、品质质等等。等等。 属属性文法中：代表性文法中：代表与与文法符文法符号号相相关关的信息，其信息的信息，其信息 值值即即为属为属性性值值。 例如：其类型、值、代码序列、符号表内容等。例如：其类型、值、代码序列、符号表内容等。 5 6.1 属性文法 （1 1）属性与变量一样，可以进行计算和传递。）属性与变量一样，可以进行计算和传递。 （2 2）属性加工的过程即是语义处理的过程。）属性加工的过程即是语义处理的过程。 （3 3）属性）属性 综合属性：用于综合属性：用于“自下而上自下而上”传递信息。

4、传递信息。 继承属性：用于继承属性：用于“自上而下自上而下”传递信息。传递信息。 6 6.1 属性文法 2 2、语义规则、语义规则 为为文法的每一文法的每一个产个产生式配生式配备备的的属属性的性的计计算算 规则规则，称为语义规则称为语义规则。 3 3、属性文法、属性文法 上下文无上下文无关关文法文法 + 语义规则语义规则 = 属属性文法性文法 7 6.1 属性文法 二、基本规则 1、语义规则的形式： 产生式产生式A A 的语义规则的一般形式为的语义规则的一般形式为b:=f(cb:=f(c1 1,c ,c2 2,c,ck k) ) 其中：其中：(1) f是一个函数；是一个函数； (2) 或者或者

5、b A的综合属性的综合属性，且，且c1,c2,ck是是中文中文 法符号的属性；法符号的属性； (3) 或者或者b 中某个文法符号的继承属性，中某个文法符号的继承属性，且且 c1,c2,ck是是A或或中任何文法符号的属性。中任何文法符号的属性。 属性属性b依赖于属性依赖于属性c1,c2,ck 8 6.1 属性文法 2、VTVN的属性 (1) VT 只有只有综综合合属属性，由性，由词词法分析器提供。法分析器提供。 (2) VN 既既可有可有综综合合属属性也可有性也可有继继承承属属性，性， 文法文法开开始符始符号号S的所有的所有继继承承属属性作性作为属为属性性 计计算前的初始算前的初始值值。 9 6

6、.1 属性文法 3、属性的计算/获得 (1) 产产生式右生式右边边的的继继承承属属性性 产产生式左生式左边边的的综综合合属属性性 (2) 产产生式左生式左边边的的继继承承属属性性 产产生式右生式右边边的的综综合合属属性性 由该产生式提供的计由该产生式提供的计 算规则计算获得算规则计算获得 由其它产生式的属性由其它产生式的属性 规则计算或由属性计规则计算或由属性计 算器的参数提供算器的参数提供 10 6.1 属性文法 例例6.1： C.d:=B.c+1 A.b:=A.a+B.c 产生式 ABC 的规则： C.d右部继承属性右部继承属性 A.b左部综合属性左部综合属性 A.a左部继承属性左部继承属

7、性 B.c右部综合属性右部综合属性 11 6.1 属性文法 例例6.2：一个简单台式计算器的属性文法 产生式语义规则 LEn EE1+T ET TT1*F TF F(E) Fdigit Print(E.val) 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 12 产生式语义规则 DTL Tint Treal LL1,id Lid addtype(id.entry,L.in) T.type:=integer T.type:=real L1.in:

8、=L.in L.in:=T.type addtype(id.entry,L.in) 13 产生式语义规则 SXYZ Xx Yy Zz Z.h:=S.a X.c:=Z.g S.b:=X.d-2 Y.e:=S.b X.d:=2*X.c Y.f:=Y.e*3 Z.g:=Z.h+1 14 6.1 属性文法 二、综合属性 1 1、语法树中、语法树中, ,一个结点的综合属性的值由其子结点一个结点的综合属性的值由其子结点 的属性值确定。的属性值确定。 2 2、通常使用自底向上的方法在每一个结点处使用语、通常使用自底向上的方法在每一个结点处使用语 义规则计算综合属性的值。义规则计算综合属性的值。 S属性文法：

9、属性文法：仅使用综合属性的属性文法仅使用综合属性的属性文法 15 6.1 属性文法 例例6.3：例6.2的表中定义的属性文法说明了一个台 式计算器，该计算器读入一个可含数字、括号和+、 *运算符的算术表达式，并打印表达式的值，每个 输入行以n作为结束。假设表达式为3*5+4，后跟一 个换行符n。 则程序打印数值则程序打印数值19。 其带注释的语法树其带注释的语法树 16 三、继承属性 1 1、语法树中、语法树中, ,一个结点的继承属性由此结点的父结一个结点的继承属性由此结点的父结 点和或兄弟结点的某些属性确定。点和或兄弟结点的某些属性确定。 6.1 属性文法 、用继承属性来表示程序设计语言结构

10、中的上下、用继承属性来表示程序设计语言结构中的上下 文依赖关系很方便。文依赖关系很方便。 17 6.1 属性文法 例例6.：带继承属性L.in的属性文法 产生式语义规则 DTL Tint Treal LL1,id Lid addtype(id.entry,L.in) T.type:=integer T.type:=real L1.in:=L.in L.in:=T.type addtype(id.entry,L.in) 18 输入串输入串: real id1,id2,id3的带注释的语法树的带注释的语法树 D D T.type=realT.type=realL.in=realL.in=real

11、realreal L.in=realL.in=real L.in=realL.in=real，id2id2 id3id3 ， id1id1 19 1 1、构造依赖图的方法、构造依赖图的方法: : 输入串语法树依赖图语义规则的计 算次序进行语义规则计算，得到翻译结果 6.2 基于属性文法的处理方法 2 2、遍历语法树的方法、遍历语法树的方法 单词符号串单词符号串 语法分析语法分析 语法分析树语法分析树 遍历遍历 计算计算 3 3、可用一遍扫描实现属性文法的语义规则计算。、可用一遍扫描实现属性文法的语义规则计算。 20 一、依赖图 1、定义：一个表示一棵语法树中结点的继承 属性和综合属性之间的相互

12、依赖关 系的有向图。 6.2 基于属性文法的处理方法 21 2、依赖图的构造方法 （1）构造依赖图以前，先为每一个包含过程调 用的语义规则引入一个虚综合属性b，在每 一个语义规则均写成b:=f（c1 1，c2 2， ck k）的 形式； （2）在依赖图中为每一个属性设置一个结点； （3）若属性b依赖于属性c，则从属性c的结点有 一条有向边连到属性b的结点。 6.2 基于属性文法的处理方法 22 例例6.5：AXY A.a:=f(X.x,Y.y) X.i:=g(A.a,Y.y) 6.2 基于属性文法的处理方法 23 3、例题 例例6.6：将下面的产生式应用于语法树中 产生式语义规则 EE1+E2

13、 E.val:=E1.val+E2.val E E E E1 1 + + E E2 2 val valval E.Val是从 E1.val和E2.val 综合得出 6.2 基于属性文法的处理方法 24 产生式语义规则 DTL Tint Treal LL1,id Lid addtype(id.entry,L.in) T.type:=integer T.type:=real L1.in:=L.in L.in:=T.type addtype(id.entry,L.in) 25 D D T TL L realreal L L L L ， id2id2 id3id3 ， id1id1 a4：=real

14、a5：=a4 Addtype(id3.entry，a5)； a7：=a5； addtype(id2.entry，a7)； a9：=a7； Addtype(id1.entry，a9)； 拓扑序列 a1,a2,a3,a4,a5,a6,a7,a8,a9,a10 26 二、树遍历的属性计算方法 1、方法 A、前提：假设语法树已经建立起来了，且树中已 有如下信息：开始符号继承属性 终结符综合属性 B、遍历：以某种次序遍历语法树，直至计算出所 有属性。 遍历方法：深度优先，从左到右遍历方法：深度优先，从左到右 6.2 基于属性文法的处理方法 27 6.2 基于属性文法的处理方法 2、算法 While Wh

15、ile 还有未被计算的属性还有未被计算的属性 dodo VisitNode(S)VisitNode(S)/ /* *S S是开始符号是开始符号* */ / procedure VisitNode(N:Node);procedure VisitNode(N:Node); beginbegin If N If N是一个非终结符是一个非终结符 thenthen / /* * 假设它的产生式为假设它的产生式为N NX X1 1XXm m * */ / for i:=1 to m do for i:=1 to m do if not Xif not Xi iVVT T then / then /* *

16、即即X Xi i是非终结符是非终结符 * */ / beginbegin 计算计算X Xi i的所有能够计算的继承属性的所有能够计算的继承属性; ; VisitNode(XVisitNode(Xi i) ) end;end; 计算计算N N的所有能够计算的综合属性的所有能够计算的综合属性 endend 注：只要文法的属性是非循环定义的，则每次扫注：只要文法的属性是非循环定义的，则每次扫 描至少有一个属性值被计算出来。描至少有一个属性值被计算出来。 28 其中，其中，S有继承属性有继承属性a，综合属性，综合属性b；X有继承属有继承属 性性c，综合属性，综合属性d；Y有继承属性有继承属性e，综合属

17、性，综合属性f； Z有继承属性有继承属性h，综合属性，综合属性g。 3、举例 例例6.9：考虑下表所给的属性文法考虑下表所给的属性文法G G。 产生式语义规则 SXYZ Xx Yy Zz Z.h:=S.a X.c:=Z.g S.b:=X.d-2 Y.e:=S.b X.d:=2*X.c Y.f:=Y.e*3 Z.g:=Z.h+1 6.2 基于属性文法的处理方法 29 S:a=0 X YZ x y (a) z S:a=0 XYZ：h=0 g=1 xy (b) z 30 S:a=0,b=0 X:c=1 d=2 Y:e=0 f=0 Z：h=0 g=1 x y (d) z S:a=0,b=0 X:c=1

18、 d=2 YZ：h=0 g=1 x y (c) z 31 6.2 基于属性文法的处理方法 三、一遍扫描的处理方法 1、特点 在语法分析的同时计算属性值，而不是语法分析 构造语法树之后进行属性的计算，而且无需构造 实际的语法树。 注：注：采用该处理方法采用该处理方法 ，当一个属性值不再用于计，当一个属性值不再用于计 算其它属性值时，编译程序就不必再保留这个属算其它属性值时，编译程序就不必再保留这个属 性值。如果需要，可把语义值存到文件中。性值。如果需要，可把语义值存到文件中。 32 6.2 基于属性文法的处理方法 2、相关因素： （1）所使用的语法分析方法 L-属性文法一遍扫描的自上而下分析 S

19、-属性文法一遍扫描的自下而上分析 （2）属性的计算次序 33 上节课的内容： 属性文法 属性 综合属性 继承属性 产生式+属性计算规则（语义规则） AX1XK A.a= Xi.x= 属性计算方法 1 2 3 S-属性文法-6.3 L-属性文法-6.4 34 6.2 基于属性文法的处理方法 例例2 2：构造表达式产生抽象语法树（Abstract Syntax Tree）的属性文法 1、定义：在语法树中去掉那些对翻译不必要 的信息，从而获得更有效的源程序 中间表示，这种经变换后的语法树 称之为抽象语法树。 注：注：抽象语法树中，操作符和关键字都不作为叶抽象语法树中，操作符和关键字都不作为叶 结点出

20、现。结点出现。 35 抽象语法树 内部结点 外部结点 操作符 关键字 标识符 常数 如：a+3*b的抽象语法树 + a* 3 b 36 6.2 基于属性文法的处理方法 2、如何建立表达式的抽象语法树 （1）方法：通过为每一个运算分量或运算符号都 建立一个结点来为子表达式建立子树； 运算符号结点的各个子结点分别表示该运算 符号的各个运算分量的子表达式组成的子树的根。 37 6.2 基于属性文法的处理方法 （2）抽象语法树中每个结点可由包含几个域的记录 来实现。 运算符号结点：一个域运算符号 其它域指向运算符号分量的结点的指针 结点：附加的域存放结点的属性值/指向属性值的指针。 38 6.2 基于

21、属性文法的处理方法 （3）建立带有二目算符的表达式的抽象语法树结点 的函数： mknode(op,left,right) mkleaf(id,entry) mkleaf(num,ral) 每个函数均返回一个指向新建立结点的指针。 39 6.2 基于属性文法的处理方法 例例6.10：下面一系列函数调用建立了表达式下面一系列函数调用建立了表达式a-4+ca-4+c的抽的抽 象语法树（如图）。在这个序列中，象语法树（如图）。在这个序列中，p p1 1,p ,p2 2, ,p ,p5 5是指向是指向 结点的指针，结点的指针，entryaentrya和和entrycentryc分别是指向符号表中的标分别

22、是指向符号表中的标 识符识符a a和和c c的指针。的指针。 id + - idnum 4 to entry for ato entry for c (1) p1:=mkleaf(id,entrya); (2) p2:=mkleaf(num,4); (3) p3:=mknode(-,p1,p2); (4) p4:=mkleaf(id,entryc); (5) p5:=mknode(+,p3,p4) （4）如何设计产生表达式抽象语法树的属性文法？ E E1+T E E1-T E T T (E) T id T num 41 产生式产生式语义规则语义规则 E E1+T E E1-T E T T (E

23、) T id T num 为表达式建立抽象语法树的属性文法为表达式建立抽象语法树的属性文法 T. nptr:=mkleaf(num,num.val) T. nptr:=mkleaf(id,id.entry) T. nptr:=E. nptr E. nptr:=T. nptr E.nptr:=mkNode(+,E1. nptr,T. nptr) E. nptr:=mkNode(-,E1. nptr,T. nptr) 42 E nptr T nptr E nptr ET nptr num T nptr id + id id idnum4 4 带注释的语法分析树带注释的语法分析树 To entry

24、for a To entry for c 43 6.3 S-属性文法的自下而上计算 1 1、S-S-属性文法：属性文法： 只含综合属性的属性文法。只含综合属性的属性文法。 2 2、S-S-属性文法的翻译借助于属性文法的翻译借助于LRLR分析器来实现分析器来实现 输入串输入串 输出输出 栈栈 分析表分析表 a1 ai an # LR分析程序分析程序 action goto Sm Xm s1 x1 s0 # LR 分 析 器 44 3、对分析栈改造、对分析栈改造 状态栈 符号栈 属性栈 S0 # - Sm-1 x x.val Sm y y.val 45 3、对分析栈改造、对分析栈改造 自底向上分析

25、法中： 栈存放已经分析过的子树的内容 附加域存放综合属性 数组State：元素一个指向LR(1)分析表的 指针(索引），指向表中某个状态 文法符号为隐含在State中而不需存在栈中 数组Val：符号的属性值 Stateval 46 6.1 属性文法 例例6.2：一个简单台式计算器的属性文法 产生式语义规则 LEn EE1+T ET TT1*F TF F(E) Fdigit Print(E.val) 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

26、47 状态栈 符号栈 属性栈 S0 # - Sm-2 E E.val Sm -1 + - 考虑：考虑：EE1+T E.val:=E1.val+T.val Sm T T.val S E E.val 转换为：转换为：EE1+T valntop:=valtop-2+valtop 48 产生式语义规则 LEn EE1+T ET TT1*F TF F(E) Fdigit Print(E.val) 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 把下面文法的

27、语义规则转换为对属性栈的操作：把下面文法的语义规则转换为对属性栈的操作： Print(valtop) Valntop=valtop-2+valtop Valntop=valtop-1 Valntop=valtop-2*valtop 49 6.11 举例 L En E E1+T E T T T1*F T F F ( E ) F digit 输入串 3*5+4n 输入输入stateval产生式产生式 3*5+4n *5+4n33 *5+4nF3F digit *5+4nT3T F 5+4nT*3 +4nT*53 5 +4nT*F3 5F digit +4nT15T T*F +4nE15E T 4n

28、E+15 nE+415 4 nE+F15 4F digit nE+T15 4T F nE19E E+T En 19 L19L En 产生式产生式语义规则语义规则 E E1+T E E1-T E T T (E) T id T num 为表达式建立抽象语法树的属性文法为表达式建立抽象语法树的属性文法 T. nptr:=mkleaf(num,num.val) T. nptr:=mkleaf(id,id.entry) T. nptr:=E. nptr E.nptr:=mkNode(+,E1. nptr,T. nptr) E. nptr:=mkNode(-,E1. nptr,T. nptr) E. np

29、tr:=T. nptr nptrntop:=mkNode(+,nptrtop-2, nptrtop) nptrntop:=mkNode(-,nptrtop-2, nptrtop) nptrntop=nptrtop-1 nptrntop=mkleaf(id,id.entry) nptrntop=mkleaf(num,num.val) 51 6.4 L-属性文法和自顶向下翻译 对语法分析树进行一次深度优先遍历就能对语法分析树进行一次深度优先遍历就能 计算出所有的属性。计算出所有的属性。即即 在自上而下建立语法树的过程中完成对属在自上而下建立语法树的过程中完成对属 性的计算。性的计算。 L-属性文法

30、 52 A X1Xj. Xk AX1.XjXk A.a= Xj.x= 53 6.4 L-属性文法和自顶向下翻译 L-属性文法：属性文法： 对任意产生式AX1X2Xn，其每个语义规则中 的属性或者是综合属性，或者Xj是一个继承属性， 且仅依赖与 （1）X1X2Xj-1； （2）A的继承属性。 S-属性文法是L-属性文法的一个特例。 54 6.4 L-属性文法和自顶向下翻译 判定下面属性文法是否是L-属性文法。 产生式语义规则 A LM A QR L.i:=l(A.i) M.i:=m(L.s) R.i:=r(A.i) A.s:=f(Q.s) Q.i:=q(R.s) 55 6.4.1 翻译模式 属性

31、文法是语言翻译的高级规范说明。 翻译模式：翻译模式： 描述文法符号属性的语义规则和计算次序。 E TR R addop T pr(addop.lex) R1| T num pr(num.val) 56 翻 译 模 式 举 例 E TR R addop T pr(addop.lex) R1| T num pr(num.val) 输入：952 E T R R R 9Pr(9) TPr() TPr() 5Pr(5) 2Pr(2) 深度优先遍历后 输出： 952 建立翻译模式的方法： 1、产生式右边的符号的继承属性必须在这个符号以 前的动作中计算出来； 2、一个动作不能引用这个动作右边符号的综合属性；

32、 3、产生式左边非终结符的综合属性只能在它所引用 的所有属性都计算出来以后才能计算。通常这类 动作可放在产生式右端的末尾。 58 例：把下面属性文法修改为翻译模式： 产生式语义规则 S B B B1B2 B B1subB2 B text B.ps=10 S.ht=B.ht B1.ps=B.ps B2.ps=B.ps B.ht=max(B1.ht,B2.ht) B1.ps=B.ps B2.ps=shrink(B.ps) B.ht=disp(B1.ht,B2.ht) B.ht=text.h*B.ps 59 S B.ps=10 BS.ht=B.ht B B1.ps=B.ps B1B2.ps=B.ps

33、 B2B.ht=max(B1.ht,B2.ht) 60 6.4.2 自顶向下翻译 消除左递归： 规则 P P| (1) P P (2) P P| 直接左递归： P P1| P2 | | Pm| 1 | 2 | | n | (i ) 消除方法： P 1P | 2P | | nP P 1P| 2P| | mP | 在自顶向下分析过程中，在消除左递归的同时 考虑属性计算，这样许多属性文法可以使用自顶 向下来实现，适用综合和继承属性的计算。 61 EE1+T E.val:=E1.val+T.val EE1T E.val:=E1.valT.val ET E.val:=T.val T(E) T.val:=

34、E.val Tnum T.val:=num.val ET 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.s T(E T.val:=E.val) Tnum T.val:=num.val E T R R R 9 T + T 2 5 计算表达式 952 .val=9 .val=5 .val=2 63 ET R.i := T.valR E.val:=R.s R+ T R1.i := R.i +T.valR1 R.s := R1.s RT R1.i := R.i T.val R1 R.s := R1.s R R.s := R.i T(E T.val:=E.val) Tnum T.val:=num