《程序设计语言编译原理(第三版)第6章》由会员分享，可在线阅读，更多相关《程序设计语言编译原理(第三版)第6章（68页珍藏版）》请在金锄头文库上搜索。
1、1,第六章 属性文法和语法制导翻译,6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S属性文法的自下而上计算 6.4 L属性文法和自顶向下翻译 6.5 自下而上计算继承属性,2,6.1 属性文法,一、基本概念,1.属性,广义：用以描述事物或人的特征、性质、品质等等。,狭义：代表与文法符号相关的信息，其信息值即为 属性值。,例如：其类型、值、代码序列、符号表内容等。,3,（1）属性与变量一样，可以进行计算和传递。,6.1 属性文法,（2）属性加工的过程即是语义处理的过程。,用于“自上而下”传递信息。,用于“自下而上”传递信息。,注:,4,2. 语义规则,为文法的每一个产生式配备的计算属
2、性的计算规则，称为语义规则。,3. 属性文法,在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）引进一组属性，且让该文法中的重写规则附加上语义规则时，称该上下文无关文法为属性文法。,注：属性文法往往以语法制导翻译和翻译方案两种形式出现。,6.1 属性文法,5,补充:,语法制导定义：基于上下文无关文法，是关于语言翻 译的抽象规格说明，其中除去了一些 实现细节，不规定翻译顺序。,翻译模式：规定实现途径和细节，指明使用语义规则 进行计算的顺序。,6.1 属性文法,6,二、基本规则,1. 语义规则的形式：,产生式A的语义规则的形式为b:=f(c1,c2,ck),其中:(1) f是一个函数;,
3、属性b依赖于属性c1,c2,ck,(2) 或者bA的综合属性，且c1,c2,ck是中文法 符号的属性;,6.1 属性文法,(3) 或者b中某个文法符号的继承属性, 且c1,c2,ck是A或中任何文法符号的属性.,7,2.VTVN的属性,(1) VT 只有综合属性,由词法分析器提供.,6.1 属性文法,(2) VN 既可有综合属性也可有继承属性; 开始符号S的所有继承属性作为属性计算 前的初始值.,8,3.属性的计算/获得,(1) 产生式右边的继承属性 产生式左边的综合属性,(2) 产生式左边的继承属性 产生式右边的综合属性,6.1 属性文法,9,例6.1:考虑非终结符，和，其中，有一个继承属性
4、 和一个综合属性，有综合属性，有继承属 性。,C.d:=B.c+1,产生式ABC可能有规则：,属性A.a和B.c在其它地方计算。,A.a左部继承属性 A.b左部综合属性 B.c右部综合属性 C.d右部继承属性,6.1 属性文法,10,例6.2: 一个简单台式计算器的属性文法,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,6.1 属性文法,11,三、综合属性,1.语法树中,一个结点的综合属性的值由其子结点的
5、 属性值确定;,2.通常使用自底向上的方法在每一个结点处使用语义 规则计算综合属性的值.,S属性文法：仅使用综合属性的属性文法.,6.1 属性文法,12,例6.3:例6.2的表中定义的属性文法说明了一个台式计算器，该计算器读入一个可含数字、括号和+、*运算符的算术表达式，并打印表达式的值，每个输入行以n作为结束。假设表达 式为3*5+4，后跟一个换行符n。,程序打印数值19,其带注释的语法树,6.1 属性文法,13,返回,*+的带注释的语法树,14,四、继承属性,1. 语法树中,一个结点的继承属性由此结点的父结点 和或兄弟结点的某些属性确定;,2. 用继承属性来表示程序设计语言结构中的上下文
6、依赖关系很方便.,6.1 属性文法,15,例6.:带继承属性L.in的属性文法,addtype (id.entry, L.in),T.type:= integer,T.type:= real,L1.in:= L.in,L.in:= T.type,addtype (id.entry, L.in),6.1 属性文法,16,输入串:real id1,id2,id3 的带注释的语法树,D,T.type=real,L.in=real,real,L.in=real,L.in=real,，,id2,id3,，,id1,17,基于属性文法的处理过程:,单词符号串,语法分析树,计算,例:,6.2 基于属性文法的
7、处理方法,18,语法制导翻译法,语义规则的计算将有下列作用：,产生代码，在符号表中存放信息，给出错误信息或执行其它动作。,由源程序的语法结构所驱动的处理方法。,6.2 基于属性文法的处理方法,19,一、依赖图,1.定义：一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图。,6.2 基于属性文法的处理方法,20,2.依赖图的构造方法,（1）构造依赖图以前，先为每一个包含过程调 用的语义规则引入一个虚综合属性b，在每 一个语义规则均写成b=f（c1,c2,ck） 的形式.,（2）在依赖图中为每一个属性设置一个结点.,（3）若属性b依赖于属性c，则从属性c的结点有 一条有向边连到
8、属性b的结点。,6.2 基于属性文法的处理方法,21,返回,6.2 基于属性文法的处理方法,22,6.2 基于属性文法的处理方法,23,3.例题,例6.6: 将下面的产生式应用于语法树中,产生式 语义规则 EE1+E2 E.val:=E1.val+E2.val, E.Val是从 E1.val和E2.val综合得出,6.2 基于属性文法的处理方法,24,例6.7: 例6.4中语法分析树的依赖图,in 5 6 type 3 type in 7 8 in 9 10 2 entry 1 entry,6.2 基于属性文法的处理方法,25,. 属性的计算次序：,6.2 基于属性文法的处理方法,一个依赖图的
9、任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。,注:在拓扑排序中,在一个结点上，语义规则 b:=f(c1,c2,ck)中的属性c1,c2,ck 在计算b以前是可用的。,良定义的：若一个属性文法不存在属性之间的循 环依赖关系，则称该文法为良定义的。,26,基础文法用于建立输入符号串的语法分析树,从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。,6.2 基于属性文法的处理方法,a4：=real a5：=a4 addtype（id3.entry，a5）； a7：=a5； addtype（id2.entry，a7）； a9：=a7；
10、addtype（id1.entry，a9）；,例6.8:,27,二、树遍历的属性计算方法,1.方法,A.前提：假设语法树已经建立起来了，且树中已 有如下信息：开始符号继承属性 终结符综合属性,B.遍历：以某种次序遍历语法树，直至计算出所 有属性.,遍历方法：深度优先，从左到右,6.2 基于属性文法的处理方法,28,2.算法,While 还有未被计算的属性 do VisitNode (S) /*S是开始符号*/,procedure VisitNode (N:Node); begin If N是一个非终结符 then /*假设它的产生式为NX1Xm*/ for i:=1 to m do if no
11、t XiVT then /*即Xi是终结符*/ begin 计算Xi的所有能够计算的继承属性; VisitNode (Xi) end; 计算N的所有能够计算的综合属性 end,29,6.2 基于属性文法的处理方法,注：只要文法的属性是非循环定义的，则每次扫 描至少有一个属性值被计算出来。,30,其中，S有继承属性a，综合属性b；X有继承属性c，综合属性d；Y有继承属性e，综合属性f；Z有继承属性h，综合属性g。,3.举例,例6.9: 考虑下表所给的属性文法G。,6.2 基于属性文法的处理方法,31,6.2 基于属性文法的处理方法,32,6.2 基于属性文法的处理方法,33,三、一遍扫描的处理方
12、法,1.特点,在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。,注：采用该处理方法，当一个属性值不再用于计算 其它属性值时，编译程序就不必再保留这个属性 值。如果需要，可把语义值存到文件中。,6.2 基于属性文法的处理方法,34,2. 相关因素：,（1）所使用的语法分析方法 L-属性文法一遍扫描的自上而下分析 S-属性文法一遍扫描的自下而上分析,6.2 基于属性文法的处理方法,（2）属性的计算次序,35,3. 语法制导翻译,A. 在语法规则的制导下，通过计算语义规则，完成对输 入符号串的翻译。,6.2 基于属性文法的处理方法,该产生式相应的语义
13、规则被计算，完成有关的语义分析 和代码产生工作。,由此可见，在该情况下，语法分析工作和语义规则的计 算是穿插进行的。,B. 为文法中每个产生式配上一组语义规则，并在语法分析 的同时执行这些语义规则。,36,四、抽象语法树Abstract Syntax Tree,1.定义：,注：抽象语法树中，操作符和关键字都不作为叶结点出现,而是把它们作为内部结点,即这些叶结点的父结点.,6.2 基于属性文法的处理方法,在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示，这种经变换后的语法树称之为抽象语法树。,37,2.如何建立表达式的抽象语法树,（1）方法：通过为每一个运算分量或运算符号都
14、建立一个结点来为子表达式建立子树；,6.2 基于属性文法的处理方法,运算符号结点的各个子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根。,38,（2）抽象语法树中每个结点可由包含几个域的记录 来实现,6.2 基于属性文法的处理方法,运算符号结点： 一个域 运算符号 其它域 指向运算符号分量的结点的指针,结点： 附加的域存放结点的属性值/指向属性值的指针。,39,6.2 基于属性文法的处理方法,40,例6.10:下面一系列函数调用建立了表达式a-4+c的抽象语法树（如图）。在这个序列中，p1,p2,p5是指向结点的指针，entrya和entryc分别是指向符号表中的标识符a和c的
15、指针。,6.2 基于属性文法的处理方法,(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),41,为表达式建立抽象语法树的属性文法,6.2 基于属性文法的处理方法,42,E,nptr,T,nptr,E,nptr,E,T,nptr,num,T,nptr,id,+,id,带注释的语法分析树,To entry for a,To entry for c,43,6.3 S属性文法的自下而上计算,1. S属性
16、文法 定义:（1）所有非终结符只具有综合属性； （2）在一个产生式中，每个符号的各个综合属性 的定义互不依赖。,2. 综合属性的计算 在分析输入符号串的同时由自下而上的分析器来计算，分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算.,44,3. S-属性文法的翻译器通常可借助于LR分析器实现 在S-属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。,6.3 S属性文法的自下而上计算,45,4. 分析栈,6.3 S属性文法的自下而上计算,自底向上分析法中：栈存放已经分析过的子树的内容 附加域存放综合属性值,数组State: 元素一个指向LR(1)分析表的指针(索引）, 指向表中某个文法符号. 数组Val: 存放语法树中与结点对
