第6章 属性文法

1、1词法分析与语法分析是编译程序的一部分。在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码中间语言代码，然后再将其翻译为目标代码。 ：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件 后面要讨论的中间代码生成中间代码生成，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成的表示方法。 目前常见的中间语言有逆波兰表示逆波兰表示、三元式三元式

2、、四元式四元式等等。 遗憾的是，中间代码生成与语言的语义密切相关，而语义的形式化描述是一件非常困难的事情; 存在一种称为语法制导翻译的模式，这种模式实际上是对上下文无关文法的一种扩充。 :对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。 这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。 由此可见，抽象文法符号的具体语义信息，是在。 文法符号X的语义信息我们称之为或简称为（Attributes

3、）。 我们用形如X.ATTR的记号来表示文法符号X的相关。 如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。 文法符号及其语义属性 例如,文法GEGE:EE(1)+TE.Val=E(1).val+T.val;ET E.Val=T.Val;TdigitT.Val=digit; 为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个 语法分析栈语义分析栈TT.Val+E#源语言程序源语言程序中间代码中间代码汇编代码汇编代码词法分析词法分析语义分析语义分析语法分析语法分析中间代码生成中间代码生成代码生成代码生成在编译中的逻辑阶段在编译中的逻

4、辑阶段前端处理前端处理后端处理后端处理语义处理语义处理语义处理（语义分析和中间代码生成）源语言程序源语言程序汇编代码汇编代码词法分析词法分析语义分析语义分析语法分析语法分析代码生成代码生成前端处理前端处理后端处理后端处理 语义处理语义处理语义处理7第六章属性文法和语法制导翻译第六章属性文法和语法制导翻译6.1 属性文法属性文法6.2 基于属性文法的处理方法基于属性文法的处理方法6.3 S S属性文法的自下而上计算属性文法的自下而上计算6.4 L属性文法和自顶向下翻译属性文法和自顶向下翻译6.5 自下而上计算继承属性自下而上计算继承属性86.1 属性文法属性文法一、基本概念一、基本概念1.1.属

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

6、息。传递信息。注注: :102. 语义规则语义规则 为文法的每一个产生式配备的为文法的每一个产生式配备的计算属性的计计算属性的计算规则算规则，称为语义规则。，称为语义规则。3. 属性文法属性文法在上下文无关文法的基础上，为在上下文无关文法的基础上，为每个文法符每个文法符号号（终结符或非终结符）引进（终结符或非终结符）引进一组属性一组属性，且让该文，且让该文法中的法中的重写规则重写规则附加上附加上语义规则语义规则时，称该上下文无时，称该上下文无关文法为属性文法。关文法为属性文法。6.1 属性文法属性文法注：语法制导翻译是指在语法分析的过程中，完成附加在所使注：语法制导翻译是指在语法分析的过程中，

7、完成附加在所使用的产生式上的语义规则所描述的动作。用的产生式上的语义规则所描述的动作。属性文法属性文法属性文法(attribute grammar)是一个三元组： A=(G,V,F),A=(G,V,F),其中 G:是一个上下文无关文法V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等 .属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。F:关于属性的属性断言或一组属性的计算规则(称为语义规则) . 断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性. 12二、基

8、本规则二、基本规则1. 语义规则的形式：语义规则的形式：产生式产生式A的语义规则的形式为的语义规则的形式为b:=f(c1,c2,ck)其中其中:(1) f是一个是一个函数函数; ;通常以表达式的形式出现通常以表达式的形式出现 属性属性b依赖于依赖于属性属性c1,c2,ck(2) 或者或者bA的的综合属性综合属性，且，且c1,c2,ck是是中中文法文法 符号的属性符号的属性; ;6.1 属性文法属性文法(3) 或者或者b中中某个文法符号的某个文法符号的继承属性继承属性, , 且且c1,c2,ck是是A或或中任何文法符号的属性中任何文法符号的属性. .b有两种可能132.VTVN的属性的属性(1)

9、 VT 只有只有综合属性综合属性, ,由词法分析器提供由词法分析器提供. .6.1 属性文法属性文法(2) VN 既可有综合属性也可有继承属性既可有综合属性也可有继承属性; ; 开始符号开始符号S S的所有继承属性作为属性计算的所有继承属性作为属性计算 前的前的初始值初始值. .出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。 AX1 X2 XnA的综合属性S(A)计算公式 S(A):=f(I(X1),I(Xn)Xj的继承属性T(Xj)计算公式 T(Xj):=f(I(A),. I(Xn)

10、1)非终结符既可有综合属性也可有继承属性 2)终结符只有综合属性,它们由词法程序提供.153.属性的计算属性的计算/ /获得获得(1) 产生式产生式右边右边的的继承继承属性属性 产生式产生式左边左边的的综合综合属性属性(2) 产生式产生式左边左边的的继承继承属性属性 产生式产生式右边右边的的综合综合属性属性由该产生式提供的计由该产生式提供的计算规则计算获得算规则计算获得由其它产生式的属性由其它产生式的属性规则计算或由属性计规则计算或由属性计算器的参数提供算器的参数提供6.1 属性文法属性文法16例例6.1:考虑非终结符考虑非终结符，和和，其中，其中，有一个继承属性有一个继承属性 和一个综合属性

11、和一个综合属性，有综合属性有综合属性，有继承属有继承属 性性。C.d:=B.c+1A.b:=A.a+B.c产生式产生式ABC可能有规则：可能有规则：属性属性A.a和和B.c在其它地方计算。在其它地方计算。A.a左部继承属性左部继承属性A.b左部综合属性左部综合属性B.c右部综合属性右部综合属性C.d右部继承属性右部继承属性6.1 属性文法属性文法17例例6.2: 一个简单台式计算器的属性文法一个简单台式计算器的属性文法产生式语义规则LEnEE1+TETTT1*FTFF(E)FdigitPrint (E.val)E.val:= E1.val+T.valE.val:= T.valT.val:= T

12、1.val*F.valT.val:= F.valF.val:= E.valF.val:= digit.lexval6.1 属性文法属性文法18三、综合属性三、综合属性1. .语法树中语法树中, ,一个结点的一个结点的综合属性综合属性的值由其的值由其子结点的子结点的 属性值属性值确定确定; ;2. .通常使用通常使用自底向上自底向上的方法在每一个结点处使用语义的方法在每一个结点处使用语义 规则计算综合属性的值规则计算综合属性的值. .S属性文法：属性文法：仅使用综合属性的属性文法仅使用综合属性的属性文法.6.1 属性文法属性文法19例例6.3:例例6.2的表中定义的属性文法说明了一个台式计算器，

13、该的表中定义的属性文法说明了一个台式计算器，该计算器读入一个可含数字、括号和计算器读入一个可含数字、括号和+ +、* *运算符的算术表达式，运算符的算术表达式，并打印表达式的值，每个输入行以并打印表达式的值，每个输入行以n作为结束。假设表达作为结束。假设表达式为式为3*5+4，后跟一个换行符，后跟一个换行符n。程序打印数值程序打印数值1919其带注释的语法树其带注释的语法树6.1 属性文法属性文法20 L L E.val=19 E.val=19 n nE.val=15 +E.val=15 +T.val=4T.val=4T.val=15T.val=15T.val=3 T.val=3 * *F.v

14、al=5F.val=5F.val=3F.val=3digit.lexval=3digit.lexval=3digit.lexval=5digit.lexval=5digit.lexval=4digit.lexval=4F.val=4F.val=4返回返回*+的带注释的语法树的带注释的语法树21四、继承属性四、继承属性1. 语法树中语法树中, ,一个结点的一个结点的继承属性继承属性由此结点的由此结点的父结点父结点 和或兄弟结点和或兄弟结点的某些属性确定的某些属性确定; ; 2. 用继承属性来表示程序设计语言结构中的用继承属性来表示程序设计语言结构中的上下文上下文 依赖关系依赖关系很方便很方便.

15、.6.1 属性文法属性文法22例例6.:带继承属性带继承属性L.in的属性文法的属性文法产生式产生式语义规则语义规则DTLTintTrealLL1,idLidaddtype (id.entry, L.in)T.type:= integerT.type:= realL1.in:= L.inL.in:= T.typeaddtype (id.entry, L.in)6.1 属性文法属性文法23输入串输入串: :real id1,id2,id3 的带注释的语法树的带注释的语法树D DT.type=realT.type=realL.in=realL.in=realrealrealL.in=realL.i

16、n=realL.in=realL.in=real，id2id2id3id3，id1id124基于属性文法的处理过程基于属性文法的处理过程: :单词符号串单词符号串语法分析语法分析语法分析树语法分析树遍历遍历计算计算例例: :输入串输入串语法树语法树依赖图依赖图语义规则的计语义规则的计算次序算次序进行语义规则计算，得到翻译结果进行语义规则计算，得到翻译结果6.2 基于属性文法的处理方法基于属性文法的处理方法25语法制导翻译法语法制导翻译法语义规则的计算将有下列作用：语义规则的计算将有下列作用： 产生代码，在符号表中存放信息，给出错产生代码，在符号表中存放信息，给出错误信息或执行其它动作。误信息或

17、执行其它动作。由源程序的语法结构所驱动的处理方法。由源程序的语法结构所驱动的处理方法。6.2 基于属性文法的处理方法基于属性文法的处理方法对输入符号串的对输入符号串的翻译翻译也就是根据语义规则进也就是根据语义规则进行行计算计算的结果。的结果。 6.2 基于属性文法的处理方法基于属性文法的处理方法依赖图依赖图树遍历树遍历一遍扫描一遍扫描27一、依赖图一、依赖图1.1.定义：定义：一个表示一棵语法树中结点的继承属性和一个表示一棵语法树中结点的继承属性和综合属性之间的综合属性之间的相互依赖关系的有向图相互依赖关系的有向图。6.2 基于属性文法的处理方法基于属性文法的处理方法282.2.依赖图的构造方

18、法依赖图的构造方法（1 1）构造依赖图以前，先为每一个）构造依赖图以前，先为每一个包含过程调包含过程调用用的语义规则引入一个的语义规则引入一个虚综合属性虚综合属性b b，在每，在每一个语义规则均写成一个语义规则均写成b=fb=f（c c1 1,c,c2 2, ,c,ck k） 的形式的形式. .（2 2）在依赖图中为每一个）在依赖图中为每一个属性属性设置一个设置一个结点结点. .（3 3）若）若属性属性b b依赖于属性依赖于属性c c，则从，则从属性属性c c的结点有的结点有一条一条有向边有向边连到连到属性属性b b的结点。的结点。程序程序6.2 基于属性文法的处理方法基于属性文法的处理方法2

19、9依赖图的构造方法依赖图的构造方法for 语法树中每一结点语法树中每一结点n do for 结点结点n的文法符号的每一个属性的文法符号的每一个属性 a do 为为a在依赖图中建立一个结点在依赖图中建立一个结点；for 语法树中每一结点语法树中每一结点n do for 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b := f（C1,C2,Ck）do fori :=1 to k do 从从 Ci 结点到结点到 b 结点构造一条有向边结点构造一条有向边；返回6.2 基于属性文法的处理方法基于属性文法的处理方法30例例6.5: AXY A.a:=f (X.x, Y.y) X

20、.i:=g (A.a, Y.y)A.aX.iX.xY.y6.2 基于属性文法的处理方法基于属性文法的处理方法313.例题例题例例6.6: 将下面的产生式应用于语法树中将下面的产生式应用于语法树中产生式产生式语义规则语义规则EE1+E2E.val:=E1.val+E2.valE EE E1 1 + +E E2 2 valvalval E.Val是从是从 E1.val和和E2.val综合得出综合得出6.2 基于属性文法的处理方法基于属性文法的处理方法句子句子real id1，id2，id3的的带注释的语法树的依赖图带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6 -

21、 addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer 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中中语法分语法分析树的析树的依赖图依赖图33. 属性的计算次序：属性的计算次序：6.2 基于属性文法的处理方法基于属性文法的处理方

22、法 一个依赖图的任何拓扑排序都给出一个语法树一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的中结点的语义规则计算的有效顺序有效顺序。注注: :在拓扑排序中在拓扑排序中, ,在一个结点上，语义规则在一个结点上，语义规则 b:=f(c1,c2,ck)中的属性中的属性c1,c2,ck 在计算在计算b以前是以前是可用的可用的。良定义的：良定义的：若一个属性文法不存在属性之间的循若一个属性文法不存在属性之间的循 环依赖关系，则称该文法为良定义的。环依赖关系，则称该文法为良定义的。属性的计算次序属性的计算次序 一个依赖图的任何拓扑排序都给出一个语法树一个依赖图的任何拓扑排序都给出一个语法树中

23、结点的语义规则计算的有效顺序中结点的语义规则计算的有效顺序属性文法说明的翻译是很精确的属性文法说明的翻译是很精确的 基础文法用于建立输入符号串的语法分析树基础文法用于建立输入符号串的语法分析树 根据语义规则建立依赖图根据语义规则建立依赖图 从依赖图的拓扑排序中，我们可以得到计算语义从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序规则的顺序 输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序句子句子real id1，id2，id3的带注释的语法树的带注释的语法树的依赖图的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entr

24、y3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);6.2 基于属性文法的处理方法基于属性文法的处理方法依赖图依赖图树遍历树遍历一遍扫描一遍扫描37二、树遍历的属性计算方法二、树遍历的属性计算方法1.1.方法方法A.前提：前提：假设语法树已经建立起来了，且树中已假设语法树已经建立起来了，且树中已 有如下信息：有如下信息：开始符号开始符号继承属性继承属性 终结符终结符综合属性综合属性B.遍历：遍历：以以某种次序遍历语法树某种次序遍历语法树，直

25、至计算出所，直至计算出所 有属性有属性. .遍历方法：深度优先，从左到右遍历方法：深度优先，从左到右6.2 基于属性文法的处理方法基于属性文法的处理方法382.算法算法While 还有未被计算的属性还有未被计算的属性 doVisitNode (S) / /* *S是开始符号是开始符号* */ /procedure VisitNode (N:Node);begin If N是一个非终结符是一个非终结符 then / /* *假设它的产生式为假设它的产生式为NX1Xm* */ / for i:=1 to m do if not XiVT then / /* *即即Xi是非终结符是非终结符* */

26、/ begin 计算计算Xi的所有能够计算的继承属性的所有能够计算的继承属性; ; VisitNode (Xi) end; 计算计算N的所有能够计算的的所有能够计算的综合属性综合属性end396.2 基于属性文法的处理方法基于属性文法的处理方法注：注：只要文法的属性只要文法的属性是是非循环定义的非循环定义的，则每次扫，则每次扫 描描至少至少有有一个属性值一个属性值被计算出来。被计算出来。40其中，其中，S有继承属性有继承属性a，综合属性，综合属性b；X有继承属有继承属性性c，综合属性，综合属性d；Y有继承属性有继承属性e，综合属性，综合属性f；Z有继承属性有继承属性h，综合属性，综合属性g。

27、3.举例举例例例6.9: 考虑下表所给的属性文法考虑下表所给的属性文法G。产生式产生式语义规则语义规则SXYZXxYyZzZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+16.2 基于属性文法的处理方法基于属性文法的处理方法41S:a=0XYZxy(a)z6.2 基于属性文法的处理方法基于属性文法的处理方法S:a=0XYZ：h=0g=1xyz(b)426.2 基于属性文法的处理方法基于属性文法的处理方法S:a=0,b=0X:c=1d=2YZ：h=0g=1xyz(c)S:a=0,b=0X:c=1d=2Y:e=0f=0Z

28、：h=0g=1xyz(d)假设假设S.a的初始值为的初始值为0，输入串为，输入串为xyzS:a=0XYZxyzZ:h=0 g=1X:c=1 d=2S:a=0, b=0Y:e=0 f=0产产 生生 式式语语 义义 规规 则则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1 6.2 基于属性文法的处理方法基于属性文法的处理方法依赖图依赖图树遍历树遍历一遍扫描一遍扫描45三、一遍扫描的处理方法三、一遍扫描的处理方法1.1.特点特点 在在语法分析的同时语法分析的

29、同时计算属性值计算属性值，而不是而不是语法分语法分析构造语法树析构造语法树之后之后进行属性的计算进行属性的计算，而且，而且无需构造无需构造实际的语法树实际的语法树。注：注：采用该处理方法，当一个属性值不再用于计算采用该处理方法，当一个属性值不再用于计算 其它属性值时，编译程序就不必再保留这个属性其它属性值时，编译程序就不必再保留这个属性 值。如果需要，可把语义值存到文件中。值。如果需要，可把语义值存到文件中。6.2 基于属性文法的处理方法基于属性文法的处理方法462. 相关因素：相关因素：（1 1）所使用的语法分析方法）所使用的语法分析方法 L- -属性文法属性文法一遍扫描的自上而下分析一遍扫

30、描的自上而下分析 S- -属性文法属性文法一遍扫描的自下而上分析一遍扫描的自下而上分析6.2 基于属性文法的处理方法基于属性文法的处理方法（2 2）属性的计算次序）属性的计算次序473. 语法制导翻译语法制导翻译A. 在语法规则的制导下，在语法规则的制导下，通过计算语义规则，完成对输通过计算语义规则，完成对输 入符号串的翻译入符号串的翻译。6.2 基于属性文法的处理方法基于属性文法的处理方法 该产生式相应的语义规则被计算，完成有关的语义分析该产生式相应的语义规则被计算，完成有关的语义分析和代码产生工作。和代码产生工作。 由此可见，在该情况下，语法分析工作和语义规则的计由此可见，在该情况下，语法

31、分析工作和语义规则的计算是算是穿插进行穿插进行的。的。即：即：自上而下分析中，一个产生式匹配输入串成功时自上而下分析中，一个产生式匹配输入串成功时 语义规则语义规则 自下而上分析中，一个产生式被用于进行规约时自下而上分析中，一个产生式被用于进行规约时被计算的时机被计算的时机B. 为文法中为文法中每个产生式配上一组语义规则每个产生式配上一组语义规则，并，并在语法分析在语法分析 的同时执行这些语义规则的同时执行这些语义规则。48四、抽象语法树四、抽象语法树Abstract Syntax Tree1.定义：定义：注：注：抽象语法树中，抽象语法树中，操作符操作符和和关键字关键字都不作为叶结点出现都不作

32、为叶结点出现, ,而是而是把它们作为内部结点把它们作为内部结点, ,即这些叶结点的父结点即这些叶结点的父结点. .6.2 基于属性文法的处理方法基于属性文法的处理方法 在语法树中在语法树中去掉那些对翻译不必要的信息去掉那些对翻译不必要的信息，从而，从而获得更有效的源程序中间表示，这种经变换后的语法获得更有效的源程序中间表示，这种经变换后的语法树称之为树称之为抽象语法树抽象语法树。BS1S2if_then_elseSif B then S1 else S23*5+4*54+3四、抽象语法树四、抽象语法树Abstract Syntax Tree6.2 基于属性文法的处理方法基于属性文法的处理方法5

33、02.如何建立表达式的抽象语法树如何建立表达式的抽象语法树（1）方法：方法：通过为每一个通过为每一个运算分量运算分量或或运算符号运算符号都都 建立一个结点来为子表达式建立子树；建立一个结点来为子表达式建立子树；6.2 基于属性文法的处理方法基于属性文法的处理方法 运算符号结点运算符号结点的的各个子结点各个子结点分别是表示该运算分别是表示该运算符号的符号的各个运算分量各个运算分量的子表达式组成的子树的根。的子表达式组成的子树的根。51（2）抽象语法树中每个结点可由包含几个域的记录抽象语法树中每个结点可由包含几个域的记录来实现来实现6.2 基于属性文法的处理方法基于属性文法的处理方法运算符号结点：

34、运算符号结点： 一个域一个域 运算符号运算符号 其它域其它域 指向运算符号分量的结点的指针指向运算符号分量的结点的指针结点：结点： 附加的域附加的域存放结点的属性值存放结点的属性值/ /指向属性值的指针。指向属性值的指针。52（3）建立带有二目算符的表达式的抽象语法树结点建立带有二目算符的表达式的抽象语法树结点的函数：的函数： mknode (op, left, right)建立一个运算符号结点，标号是建立一个运算符号结点，标号是op，两个域两个域left 和和right分别指向左子树和右子树分别指向左子树和右子树。 mkleaf (id, entry)建立一个标识符结点，标号为建立一个标识符

35、结点，标号为id，一个域一个域entry指向标识符指向标识符在符号表中的入口。在符号表中的入口。 mkleaf (num, ral)建立一个数结点，标号为建立一个数结点，标号为num，一个域一个域val用于存放数的值。用于存放数的值。 每个函数均返回一个指向新建立结点的指针。每个函数均返回一个指向新建立结点的指针。6.2 基于属性文法的处理方法基于属性文法的处理方法53例例6.10:下面一系列函数调用建立了表达式下面一系列函数调用建立了表达式a-4+c的抽象语法树的抽象语法树（如图）。在这个序列中，（如图）。在这个序列中，p1,p2,p5是指向结点的指针，是指向结点的指针，entrya和和en

36、tryc分别是指向符号表中的标识符分别是指向符号表中的标识符a和和c的指针。的指针。 + -num 4 id to entry for c6.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) idTo entry for a 54产生式产生式语义规则语义规则E E1+TE E1-TE TT (E)T idT numE.nptr:=mkNode(+,E1.n

37、ptr, T.nptr)E.nptr:=mkNode(-,E1.nptr, T.nptr)E.nptr:=T.nptrE.nptr:=T.nptrT.nptr:=mkleaf (id,id.entry)T.nptr:=mkleaf (num, num.val)为表达式建立抽象语法树的属性文法为表达式建立抽象语法树的属性文法6.2 基于属性文法的处理方法基于属性文法的处理方法55E nptrTnptrE nptrET nptrnumTnptrid+id ididnum4 4带注释的语法分析树带注释的语法分析树To entry for aTo entry for c566.3 S属性文法的自下而上

38、计算属性文法的自下而上计算1. S属性文法属性文法 定义定义: :（1）所有非终结符所有非终结符只具有只具有综合属性综合属性； （2）在一个产生式中，每个符号的各个综合属性在一个产生式中，每个符号的各个综合属性 的定义的定义互不依赖互不依赖。2. 综合属性的计算综合属性的计算 在分析输入符号串的同时由自下而上的分析器来计算，分在分析输入符号串的同时由自下而上的分析器来计算，分析器可以析器可以保存保存与栈中文法符号有关的与栈中文法符号有关的综合属性值综合属性值，每当进行归，每当进行归约时，约时，新的属性值新的属性值就由栈中正在归约的就由栈中正在归约的产生式右边符号的属性产生式右边符号的属性值来计

39、算值来计算. .573. S-属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LR分析器实现分析器实现 在在S-属性文法的基础上，属性文法的基础上，LR分析器可以改造为一分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进个翻译器，在对输入串进行语法分析的同时对属性进行计算。行计算。6.3 S属性文法的自下而上计算属性文法的自下而上计算产生式 语义规则） （.）1 . 1.） . .l）1* . 1. ）F . F.）（）（） . . ）ii .:.LR分析器可以改造为一个翻译器,增加增加语义栈语义栈 ，在对输入串进行语法分析的同时对属性进行计算。 分析分析器模型总控程序o

40、utputInput#S1 XmS1X1S0 #栈 状态 符号ACTIONGOTOLR分析表产生式表VmV1- 语义S1S0VmV1- *的分析和计值过程步骤 动作 状态栈 语义栈(值栈) 符号栈 余留输入串） 3*） 2 3 *） *） *） *） *） *） *） *） * ） * ） （）（） * #） （）（） ） （）（） ）接受）接受614. 分析栈分析栈Stateval6.3 S属性文法的自下而上计算属性文法的自下而上计算自底向上分析法中：自底向上分析法中：栈栈存放已经分析过的子树的内容存放已经分析过的子树的内容 附加域附加域存放综合属性值存放综合属性值数组数组State: 元素

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

42、 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 5F digitT FF digitT T*FE T63L En E E1+TE TT T1*FT FF ( E )F digit 输入串输入串 3*5+4n输入输入stateval产生式产生式 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 digitT FE E+TL En5.举例举例646.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译L-属

43、性文法属性文法1.1.定义定义: :若属性文法中每个若属性文法中每个产生式产生式AX1X2Xn, , 其相关的每个语义规则中的每个属性其相关的每个语义规则中的每个属性: :或者是或者是综合属性综合属性; ;或者是或者是Xj的一个继承属性且的一个继承属性且该继承属性该继承属性仅依赖于仅依赖于 Xj左边符号左边符号X1,X2,Xj-1的属性和的属性和A的继承属性。的继承属性。则称该属性文法为则称该属性文法为L-属性文法属性文法. .652. 特点特点: :6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译L-属性文法属性文法A. 该类属性文法允许我们通过一次遍历就计算出所该类属性文法允许我们

44、通过一次遍历就计算出所 有属性值有属性值. .B. 可在自上而下语法分析的同时实现可在自上而下语法分析的同时实现L-L-属性文法的属性文法的 计算计算. .C. S-属性文法一定是属性文法一定是L-属性文法属性文法. .666.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 一个非一个非L-属性文法属性文法产生式产生式语义规则语义规则A LMA QRL.i=l(A.i)M.i=m(L.s)R.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)67一一. . 翻译模式翻译模式1. 翻译模式的定义：翻译模式的定义： 一种适合语法制导翻译的语义描述形式一种适合语法制导翻译的语义描述形式,

45、 ,给出了给出了使用语义规则进行计算的次序使用语义规则进行计算的次序, ,可把某些实现细节表可把某些实现细节表示出来示出来. . 形式形式: :在翻译模式中在翻译模式中, ,和文法符号相关的属性和语义规和文法符号相关的属性和语义规 则则, ,用用 括起来括起来, ,插入到产生式右部的合适位置上插入到产生式右部的合适位置上. .例例: :E TR R addop T pr(addop.lex) R1| T num pr(num.val) 6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译68 为每一个语义规则建立一个包含赋值的动作为每一个语义规则建立一个包含赋值的动作, ,并并把这个动作放

46、在相应的产生式右边的末尾把这个动作放在相应的产生式右边的末尾. .6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译2. 翻译模式的设计：翻译模式的设计： A. 只有综合属性时只有综合属性时, ,可以按如下方式建立翻译模式可以按如下方式建立翻译模式: :69B.若若既有综合属性又有继承属性时既有综合属性又有继承属性时, ,则按如下方式建立则按如下方式建立 翻译模式翻译模式: : 产生式产生式右边的符号的右边的符号的继承属性继承属性必须在这个符号必须在这个符号以前以前的动作中计算出来的动作中计算出来. . 一个动作一个动作不能引用不能引用这个动作这个动作右边右边的的符号符号的的综合属性综合

47、属性. 产生式产生式左边非终结符的综合属性左边非终结符的综合属性只有在它所引用的只有在它所引用的所有属性都计算出来以后才能计算所有属性都计算出来以后才能计算.计算这种属性的计算这种属性的动作通常可放在动作通常可放在产生式右端的末尾产生式右端的末尾. 6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译2. 翻译模式的设计：翻译模式的设计： 70举例举例:E TR R addop Tpr(addop.lex)R1| T num pr(num.val) 输入输入：952深度优先遍历后深度优先遍历后输出输出：952ETRRR9Pr(9) T Pr() T Pr()5Pr(5)2Pr(2)71二二

48、. .自顶向下翻译自顶向下翻译1.讨论讨论: : L-属性文法在自顶向下分析中的实现属性文法在自顶向下分析中的实现6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译自顶向下语法分析的自顶向下语法分析的前提前提是是消除文法中的左递归消除文法中的左递归. .72EE1+T E.val:=E1.val+T.val EE1T E.val:=E1.valT.val ET E.val:=T.val T(E) T.val:=E.val Tnum T.val:=num.valET R.i := T.val R E.val:=R.s R+ T R1.i := R.i +T.val R1 R.s := R1

49、.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.例题例题: : 73计算表达式计算表达式 952带注释语法树带注释语法树i: 继承属性继承属性s : 综合属性综合属性ET.val=9R.i=9R.i=4R.i=6Num.val=9T.val=5+T.val=2Num.val=2Num.val=56.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译E.valR.sR.sR.s74AA1Y A.a=g(A1.a ,Y.y AX A.a= f (X.x) A

50、X 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. 转换左递归翻译模式的一般方法：转换左递归翻译模式的一般方法：消除左递归前消除左递归前: :消除左递归后消除左递归后: :75A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=g(f(X.x),Y1.y)A.a=f(X.x)XY2Y16.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译带注释语法树带注释语法树R.i=g(g(f(X.x),Y1.y),Y2.y)Y2R.i=g(

51、f(X.x),Y1.y)R.i=f(X.x)AXY1R.sR.sR.sA.aP 155-15676 递归下降分析器的构造 p156 举例 AST:Abstract Syntax Tree 三三. .递归下降翻译器的设计递归下降翻译器的设计6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译77 L-属性文法的自上而下分析翻译方法，适用于属性文法的自上而下分析翻译方法，适用于所有基于所有基于LL(1)文法和许多基于文法和许多基于LR(1)文法的文法的L-属性属性文法，是文法，是S-属性文法自下而上翻译技术的一般化。属性文法自下而上翻译技术的一般化。（1）从翻译模式中去掉嵌入在产生式中间的动作）从翻译模式中去掉嵌入在产生式中间的动作（2