编译原理第6章

1、源语言程序,中间代码,汇编代码,词法分析,语义分析,语法分析,中间代码生成,代码生成,在编译中的逻辑阶段,前端处理,后端处理,语义处理,语义处理（语义分析和中间代码生成）,源语言程序,汇编代码,词法分析,语义分析,语法分析,代码生成,前端处理,后端处理,语义处理,语义处理,语义处理,语义处理的任务： 静态语义检查 静态语义：语法规则的良形式条件 静态语义检查：审查静态语义 动态语义处理 动态语义：程序单元执行的操作 动态语义处理：生成(中间/目标)代码,语义处理,语义处理的实现： 属性文法：描述语义规则。 语法制导翻译：在语法分析的同时，执行语义规则描述的动作： 检查静态语义 生成中间代码/目

2、标代码,语义处理,语义处理的环境：符号表 为语义分析提供类型、作用域等信息。 为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。,6,第六章属性文法和语法制导翻译,6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S属性文法的自下而上计算 6.4 L属性文法和自顶向下翻译 6.5 自下而上计算继承属性,7,6.1 属性文法,一、基本概念,1.属性,广义：用以描述事物或人的特征、性质、品质等等。,狭义：代表与文法符号相关的信息，其信息值即为 属性值。,例如：其类型、值、代码序列、符号表内容等。,8,（1）属性与变量一样，可以进行计算和传递。,6.1 属性文法,（2）属性加工的

3、过程即是语义处理的过程。,用于“自上而下”传递信息。,用于“自下而上”传递信息。,注:,9,2. 语义规则,为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。,3. 属性文法,在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）引进一组属性，且让该文法中的重写规则附加上语义规则时，称该上下文无关文法为属性文法。,注：属性文法往往以语法制导翻译和翻译方案两种形式出现。,6.1 属性文法,属性文法,属性文法(attribute grammar)是一个三元组： A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代

4、表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等 .属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。 F:关于属性的属性断言或一组属性的计算规则(称为语义规则) . 断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性.,11,二、基本规则,1. 语义规则的形式：,产生式A的语义规则的形式为b:=f(c1,c2,ck),其中:(1) f是一个函数;通常以表达式的形式出现,属性b依赖于属性c1,c2,ck,(2) 或者bA的综合属性，且c1,c2,ck是中文法 符号的属性;,6.1 属性文法,(3) 或者b中某个文法符号的继承属性

5、, 且c1,c2,ck是A或中任何文法符号的属性.,b有两种可能,12,2.VTVN的属性,(1) VT 只有综合属性,由词法分析器提供.,6.1 属性文法,(2) VN 既可有综合属性也可有继承属性; 开始符号S的所有继承属性作为属性计算 前的初始值.,出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。 AX1 X2 Xn A的综合属性S(A)计算公式 S(A):=f(I(X1),I(Xn) Xj的继承属性T(Xj)计算公式 T(Xj):=f(I(A),. I(Xn) 1)非终结符既可有综

6、合属性也可有继承属性 2)终结符只有综合属性,它们由词法程序提供.,14,3.属性的计算/获得,(1) 产生式右边的继承属性 产生式左边的综合属性,(2) 产生式左边的继承属性 产生式右边的综合属性,6.1 属性文法,15,例6.1:考虑非终结符，和，其中，有一个继承属性 和一个综合属性，有综合属性，有继承属 性。,C.d:=B.c+1 A.b:=A.a+B.c,产生式ABC可能有规则：,属性A.a和B.c在其它地方计算。,A.a左部继承属性 A.b左部综合属性 B.c右部综合属性 C.d右部继承属性,6.1 属性文法,16,例6.2: 一个简单台式计算器的属性文法,Print (E.val)

7、,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 属性文法,17,三、综合属性,1.语法树中,一个结点的综合属性的值由其子结点的 属性值确定;,2.通常使用自底向上的方法在每一个结点处使用语义 规则计算综合属性的值.,S属性文法：仅使用综合属性的属性文法.,6.1 属性文法,18,例6.3:例6.2的表中定义的属性文法说明了一个台式计算器，该计算器读入一个可含数字、括号和+、*运算符的算术表达式，并打印表达式的值，每个输入行以

8、n作为结束。假设表达 式为3*5+4，后跟一个换行符n。,程序打印数值19,其带注释的语法树,6.1 属性文法,19,返回,*+的带注释的语法树,20,四、继承属性,1. 语法树中,一个结点的继承属性由此结点的父结点 和或兄弟结点的某些属性确定;,2. 用继承属性来表示程序设计语言结构中的上下文 依赖关系很方便.,6.1 属性文法,21,例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

9、 属性文法,22,输入串:real id1,id2,id3 的带注释的语法树,D,T.type=real,L.in=real,real,L.in=real,L.in=real,，,id2,id3,，,id1,23,基于属性文法的处理过程:,单词符号串,语法分析树,计算,例:,6.2 基于属性文法的处理方法,24,语法制导翻译法,语义规则的计算将有下列作用：,产生代码，在符号表中存放信息，给出错误信息或执行其它动作。,由源程序的语法结构所驱动的处理方法。,6.2 基于属性文法的处理方法,对输入符号串的翻译也就是根据语义规则进行计算的结果。,6.2 基于属性文法的处理方法,依赖图 树遍历 一遍扫描

10、,26,一、依赖图,1.定义：一个表示一棵语法树中结点的继承属性和综合属性之间的相互依赖关系的有向图。,6.2 基于属性文法的处理方法,27,2.依赖图的构造方法,（1）构造依赖图以前，先为每一个包含过程调用的语义规则引入一个虚综合属性b，在每一个语义规则均写成b=f（c1,c2,ck） 的形式.,（2）在依赖图中为每一个属性设置一个结点.,（3）若属性b依赖于属性c，则从属性c的结点有 一条有向边连到属性b的结点。,6.2 基于属性文法的处理方法,28,返回,6.2 基于属性文法的处理方法,29,A.a,X.i,X.x,Y.y,6.2 基于属性文法的处理方法,30,3.例题,例6.6: 将下

11、面的产生式应用于语法树中,产生式语义规则 EE1+E2E.val:=E1.val+E2.val, E.Val是从 E1.val和E2.val综合得出,6.2 基于属性文法的处理方法,句子real id1，id2，id3的带注释的语法树的依赖图,id1,L,id2,L,id3,L,real,T,D,4 type,5 in,6 - addtype(id.entry, L.in),7 in,8 addtype,9 in,10 addtype,1 entry,2 entry,3 entry,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.type := integer

12、Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),例6.7: 例6.4中语法分析树的依赖图,32,. 属性的计算次序：,6.2 基于属性文法的处理方法,一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。,注:在拓扑排序中,在一个结点上，语义规则 b:=f(c1,c2,ck)中的属性c1,c2,ck 在计算b以前是可用的。,良定义的：若一个属性文法不存在属性之间的循 环依赖关系，则称该文法为良定义的。,属性的计算次序,一个依赖图的任何拓扑

13、排序都给出一个语法树中结点的语义规则计算的有效顺序 属性文法说明的翻译是很精确的 基础文法用于建立输入符号串的语法分析树 根据语义规则建立依赖图 从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序,输入串,语法树,依赖图,语义规则计算次序,句子real id1，id2，id3的带注释的语法树的依赖图,a4:=real; a5:=a4 addtype (id3.entry,a5); a7:=a5; addtype (id2.entry,a7); a9:=a7 addtype (id1.entry,a9);,6.2 基于属性文法的处理方法,依赖图 树遍历 一遍扫描,36,二、树遍历的属性计算方法

14、,1.方法,A.前提：假设语法树已经建立起来了，且树中已 有如下信息：开始符号继承属性 终结符综合属性,B.遍历：以某种次序遍历语法树，直至计算出所 有属性.,遍历方法：深度优先，从左到右,6.2 基于属性文法的处理方法,37,2.算法,While 还有未被计算的属性 do VisitNode (S) /*S是开始符号*/,procedure VisitNode (N:Node); begin If N是一个非终结符 then /*假设它的产生式为NX1Xm*/ for i:=1 to m do if not XiVT then /*即Xi是终结符*/ begin 计算Xi的所有能够计算的继承

15、属性; VisitNode (Xi) end; 计算N的所有能够计算的综合属性 end,38,6.2 基于属性文法的处理方法,注：只要文法的属性是非循环定义的，则每次扫 描至少有一个属性值被计算出来。,39,其中，S有继承属性a，综合属性b；X有继承属性c，综合属性d；Y有继承属性e，综合属性f；Z有继承属性h，综合属性g。,3.举例,例6.9: 考虑下表所给的属性文法G。,6.2 基于属性文法的处理方法,40,6.2 基于属性文法的处理方法,41,6.2 基于属性文法的处理方法,假设S.a的初始值为0，输入串为xyz,S:a=0,X,Y,Z,x,y,z,Z:h=0 g=1,X:c=1 d=2

16、,S:a=0, b=0,Y:e=0 f=0,产 生 式语 义 规 则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b Xx X.d :=2*X.c Yy Y.f := Y.e*3 Zz Z.g :=Z.h+1,6.2 基于属性文法的处理方法,依赖图 树遍历 一遍扫描,44,三、一遍扫描的处理方法,1.特点,在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。,注：采用该处理方法，当一个属性值不再用于计算 其它属性值时，编译程序就不必再保留这个属性 值。如果需要，可把语义值存到文件中。,6.2

17、基于属性文法的处理方法,45,2. 相关因素：,（1）所使用的语法分析方法 L-属性文法一遍扫描的自上而下分析 S-属性文法一遍扫描的自下而上分析,6.2 基于属性文法的处理方法,（2）属性的计算次序,46,3. 语法制导翻译,A. 在语法规则的制导下，通过计算语义规则，完成对输 入符号串的翻译。,6.2 基于属性文法的处理方法,该产生式相应的语义规则被计算，完成有关的语义分析 和代码产生工作。,由此可见，在该情况下，语法分析工作和语义规则的计 算是穿插进行的。,B. 为文法中每个产生式配上一组语义规则，并在语法分析 的同时执行这些语义规则。,47,四、抽象语法树Abstract Syntax

18、 Tree,1.定义：,注：抽象语法树中，操作符和关键字都不作为叶结点出现,而是把它们作为内部结点,即这些叶结点的父结点.,6.2 基于属性文法的处理方法,在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示，这种经变换后的语法树称之为抽象语法树。,Sif B then S1 else S2,3*5+4,四、抽象语法树Abstract Syntax Tree,6.2 基于属性文法的处理方法,49,2.如何建立表达式的抽象语法树,（1）方法：通过为每一个运算分量或运算符号都 建立一个结点来为子表达式建立子树；,6.2 基于属性文法的处理方法,运算符号结点的各个子结点分别是表示该运

19、算符号的各个运算分量的子表达式组成的子树的根。,50,（2）抽象语法树中每个结点可由包含几个域的记录 来实现,6.2 基于属性文法的处理方法,运算符号结点： 一个域 运算符号 其它域 指向运算符号分量的结点的指针,结点： 附加的域存放结点的属性值/指向属性值的指针。,51,6.2 基于属性文法的处理方法,52,例6.10:下面一系列函数调用建立了表达式a-4+c的抽象语法树（如图）。在这个序列中，p1,p2,p5是指向结点的指针，entrya和entryc分别是指向符号表中的标识符a和c的指针。,6.2 基于属性文法的处理方法,(1)p1:=mkleaf (id, entrya); (2)p2

20、:=mkleaf (num,4); (3)p3:=mknode(-,p1,p2); (4)p4:=mkleaf (id, entryc); (5)p5:=mknode(+,p3,p4),53,为表达式建立抽象语法树的属性文法,6.2 基于属性文法的处理方法,54,E,nptr,T,nptr,E,nptr,E,T,nptr,num,T,nptr,id,+,id,带注释的语法分析树,To entry for a,To entry for c,55,6.3 S属性文法的自下而上计算,1. S属性文法 定义:（1）所有非终结符只具有综合属性； （2）在一个产生式中，每个符号的各个综合属性 的定义互不依

21、赖。,2. 综合属性的计算 在分析输入符号串的同时由自下而上的分析器来计算，分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算.,56,3. S-属性文法的翻译器通常可借助于LR分析器实现 在S-属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。,6.3 S属性文法的自下而上计算,产生式 语义规则 ） （.） ）1 .1. ） .l ）1* .1. ）F .F. ）（） . ）ii .:. LR分析器可以改造为一个翻译器,增加语义栈 ， 在对输入串进行语法分析的同时对属性进行计算。,

22、分析器模型,总控程序,output,Input#,S1,Xm, S1, X1,S0,#,栈,状态,符号,ACTION,GOTO,LR分析表,产生式表,Vm,V1,-,语义, S1,S0,Vm,V1,-,*的分析和计值过程,步骤 动作 状态栈 语义栈(值栈) 符号栈 余留输入串 ） 3* ） 2 3 * ） * ） * ） * ） * ） * ） * ） * ） * ） * ） （） * # ） （） ） （） ）接受,60,4. 分析栈,6.3 S属性文法的自下而上计算,自底向上分析法中：栈存放已经分析过的子树的内容 附加域存放综合属性值,数组State: 元素一个指向LR(1)分析表的指针(

23、索引）, 指向表中某个文法符号. 数组Val: 存放语法树中与结点对应的属性值.,注: (1)假定综合属性刚好在每次归约前计算. (2)若一个符号无综合属性,则数组val中相应的元素就不定义.,61,5.举例,L En E E1+T E T T T1*F T F F ( E ) F digit,输入串 3*5+4n,3*5+4n ,*5+4n 3 3,*5+4n F 3,*5+4n T 3,5+4n T* 3 ,+4n T*5 3 5,+4n T 15,+4n E 15,4n E+ 15 ,+4n T*F 3 5,F digit,T F,F digit,T T*F,E T,62,L En E

24、E1+T E T T T1*F T F F ( E ) F digit,输入串 3*5+4n,4n E+ 15 ,n E+4 15 4,n E+F 15 4,n E+T 15 4,n E 19,En 19 ,L 19,F digit,T F,E E+T,L En,5.举例,63,6.4 L-属性文法和自顶向下翻译,L-属性文法,1.定义:若属性文法中每个产生式AX1X2Xn, 其相关的每个语义规则中的每个属性:,或者是综合属性;,或者是Xj的一个继承属性且该继承属性仅依赖于 Xj左边符号X1,X2,Xj-1的属性和A的继承属性。,则称该属性文法为L-属性文法.,64,2. 特点:,6.4 L-

25、属性文法和自顶向下翻译,L-属性文法,A. 该类属性文法允许我们通过一次遍历就计算出所 有属性值.,B. 可在自上而下语法分析的同时实现L-属性文法的 计算.,C. S-属性文法一定是L-属性文法.,65,6.4 L-属性文法和自顶向下翻译,一个非L-属性文法,66,一. 翻译模式,1. 翻译模式的定义：,一种适合语法制导翻译的语义描述形式,给出了 使用语义规则进行计算的次序,可把某些实现细节表 示出来.,形式:在翻译模式中,和文法符号相关的属性和语义规 则,用 括起来,插入到产生式右部的合适位置上.,例:E TR R addop T pr(addop.lex) R1| T num pr(nu

26、m.val),6.4 L-属性文法和自顶向下翻译,67,为每一个语义规则建立一个包含赋值的动作,并 把这个动作放在相应的产生式右边的末尾.,6.4 L-属性文法和自顶向下翻译,2. 翻译模式的设计：,A. 只有综合属性时,可以按如下方式建立翻译模式:,68,B.若既有综合属性又有继承属性时,则按如下方式建立 翻译模式:,产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来.,一个动作不能引用这个动作右边的符号的综合属性.,产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算.计算这种属性的动作通常可放在产生式右端的末尾.,6.4 L-属性文法和自顶向下翻译,2.

27、翻译模式的设计：,69,举例:,E TR R addop Tpr(addop.lex)R1| T num pr(num.val),输入：952 深度优先遍历后 输出：952,E,T,R,R,R,9,Pr(9),T,Pr(),T,Pr(),5,Pr(5),2,Pr(2),70,二.自顶向下翻译,1.讨论: L-属性文法在自顶向下分析中的实现,6.4 L-属性文法和自顶向下翻译,自顶向下语法分析的前提是消除文法中的左递归.,71,EE1+T E.val:=E1.val+T.val EE1T E.val:=E1.valT.val ET E.val:=T.val T(E) T.val:=E.val T

28、num 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.i T(E) T.val:=E.val Tnum T.val:=num.val ,2.例题:,72,计算表达式 952,带注释语法树 i: 继承属性 s : 综合属性,E,T.val=9,R.i=9,R.i=4,R.i=6,Num.val=9,T.val=5,+,T.val=2,Num.val=2,Num.val=5,6.4

29、L-属性文法和自顶向下翻译,E.val,R.s,R.s,R.s,73,AA1Y A.a=g(A1.a ,Y.y AX A.a= f (X.x) ,AX R.i:=f (X.x) R A.a:=R.s RY R1.i =g (R.i, Y.y) R1 R.s:=R1.s R R.s := R.i ,6.4 L-属性文法和自顶向下翻译,3. 转换左递归翻译模式的一般方法：,消除左递归前:,消除左递归后:,74,6.4 L-属性文法和自顶向下翻译,带注释语法树,P 155-156,75,递归下降分析器的构造 p156 举例 AST:Abstract Syntax Tree,三.递归下降翻译器的设计,6.4 L-属性文法和自顶向下翻译,76