属性文法和语法制导编译

1、第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译内容内容 属性文法属性文法 基于属性文法的处理方法基于属性文法的处理方法 S-属性文法的自下而上计算属性文法的自下而上计算 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 自下而上计算继承属性自下而上计算继承属性第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译 语义语义：一组规则，用它可以定义一个程序的：一组规则，用它可以定义一个程序的意义。意义。 描述方法：描述方法：自然语言描述：隐藏错误、二义性和不完整性自然语言描述：隐藏错误、二义性和不完整性形式描述：形式描述：F 操作语义操作语义(PL/1)(PL/1)F 指称语义指

2、称语义(ADA)(ADA)F 代数语义代数语义(PASCAL)(PASCAL)属性文法属性文法第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译 编译中的语义处理包括两个功能编译中的语义处理包括两个功能： （1）审查每个语法结构的静态语义，即验证）审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。也称为语法结构合法的程序是否真正有意义。也称为静态语义分析或静态审查静态语义分析或静态审查；（2）如果静态语义正确，则执行真正的翻译，）如果静态语义正确，则执行真正的翻译，即即生成中间代码生成中间代码或生成实际的目标代码。或生成实际的目标代码。 以上工作普遍基于以上工作普遍基

3、于属性文法和语法制导翻属性文法和语法制导翻译方法译方法。6.1 属性文法属性文法 属性文法属性文法（也称属性翻译文法）（也称属性翻译文法）Knuth在在1968年提出年提出在上下文无关文法的基础上，为每个文法在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关符号（终结符或非终结符）配备若干相关的的“值值”（称为（称为属性属性）。）。属性代表与文法符号相关信息，如类型、值、属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等代码序列、符号表内容等属性可以进行计算和传递属性可以进行计算和传递语义规则语义规则：对于文法的每个产生式都配备了一：对于文法的每个产生式都配备

4、了一组属性的计算规则组属性的计算规则6.1 属性文法属性文法 属性属性综合属性综合属性：“自下而上自下而上”传递信息传递信息继承属性继承属性：“自上而下自上而下”传递信息传递信息 在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A 都都有一套与之相关联的语义规则，每条规则的形式有一套与之相关联的语义规则，每条规则的形式为：为：b:=f(c1, c2, , ck)这里，这里，f是一个函数，而且或者是一个函数，而且或者1. b是是A的一个的一个综合属性综合属性并且并且c1,c2,ck是产生式右边是产生式右边文法符号的属性，或者文法符号的属性，或者2. b是产生式右边某个文法符号

5、的一个是产生式右边某个文法符号的一个继承属性继承属性并且并且c1,c2,ck 是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。在两种情况下，属性在两种情况下，属性b依赖于属性依赖于属性c1,c2,ck。6.1 属性文法属性文法 说明说明终结符只有综合属性终结符只有综合属性，由词法分析器提供，由词法分析器提供非终结符既可有综合属性也可有继承属性，非终结符既可有综合属性也可有继承属性，文法文法开始符号的所有继承属性作为属性计算前的初始开始符号的所有继承属性作为属性计算前的初始值值对出现在产生式右边的继承属性和出现在产生式对出现在产生式右边的继承属性和出现在产生式左边的综合属性

6、都必须提供一个计算规则。左边的综合属性都必须提供一个计算规则。属性属性计算规则中只能使用相应产生式中的文法符号的计算规则中只能使用相应产生式中的文法符号的属性属性出现在产生式左边的继承属性和出现在产生式右出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则边的综合属性不由所给的产生式的属性计算规则进行计算，进行计算，它们由其它产生式的属性规则计算或它们由其它产生式的属性规则计算或者由属性计算器的参数提供者由属性计算器的参数提供6.1 属性文法属性文法 语义规则语义规则所描述的工作可以包括属性计算、所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等

7、静态语义检查、符号表操作、代码生成等等。等。 例，考虑非终结符例，考虑非终结符A，B和和C，其中，其中，A有有一个继承属性一个继承属性a和一个综合属性和一个综合属性b，B有综有综合属性合属性c，C有继承属性有继承属性d。产生式。产生式ABC可能有规则可能有规则 C.d:=B.c+1 A.b:=A.a+B.c而属性而属性A.a和和B.c在其它地方计算在其它地方计算 n 属性文法的例子：简单算术表达式求值的语义描述。属性文法的例子：简单算术表达式求值的语义描述。非终结符非终结符E、T及及F都有一个都有一个综合属性综合属性val，符号符号digit有一个综合属性有一个综合属性lexval，它的值由词

8、法分析器提供。，它的值由词法分析器提供。与产生式与产生式LE对应的语义规则仅仅是打印由对应的语义规则仅仅是打印由E产生的算术表达产生的算术表达式的值的一个过程，我们可认为这条规则定义了式的值的一个过程，我们可认为这条规则定义了L的一个的一个虚属性虚属性。某些某些非终结符加下标非终结符加下标是为了区分一个产生式中同一非终结符多是为了区分一个产生式中同一非终结符多次出现次出现语语 义义 规规 则则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val

9、T.val:=F.valF.val:=E.valF.val:=digit.lexval产生式产生式6.1 属性文法属性文法 综合属性综合属性在语法树中，一个结点的综合属性的值由其子在语法树中，一个结点的综合属性的值由其子结点的属性值确定。结点的属性值确定。使用自底向上的方法在每一个结点处使用语义使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值规则计算综合属性的值 仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性文属性文法法结点属性值的计算正好和自底向上分析建立分析树结点同步进行。表达式表达式3*5+4n的带注释的语法树的带注释的语法树(语义动作打印数值语义动作打印数值

10、19) digit.lexval=3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL6.1 属性文法属性文法 继承属性继承属性在语法树中，一个结点的继承属性由此结点的在语法树中，一个结点的继承属性由此结点的父结点和父结点和/或兄弟结点的某些属性确定或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下用继承属性来表示程序设计语言结构中的上下文依赖关系很方便文依赖关系很方便6.1 属性文法属性文法 产产 生生 式式 语语 义义 规规 则则 DTLL.in

11、 := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.type, L.in) Lid addtype(id.type, L.in) 句子句子real id1，id2，id3的带注释的语法树的带注释的语法树 id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real6.2 基于属性文法的处理方法基于属性文法的处理方法 语法制导翻译语法制导翻译即基于属性文法的处理过程处理过程是：对单词符号串进行语法分析，构造语法分析树，然后根据

12、需要遍历语法树并在语法树的各结点处按语义规则进行计算。 由源程序的语法结构所驱动的处理办法就是由源程序的语法结构所驱动的处理办法就是语语法制导翻译法法制导翻译法 语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行其他动作。对输入符号串的翻译就是根据语义规则进行计算的结果。输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序6.2.1 依赖图依赖图 在一棵语法树中的结点的继承属性和综合属性之在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作间的相互依赖关系可以由称作依赖图依赖图的一个有向的一个有向图来描述图来描述 为每一个包含过程调用的语义规则引

13、入一个虚综为每一个包含过程调用的语义规则引入一个虚综合属性合属性b，这样把每一个语义规则都写成，这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式的形式 依赖图中为每一个属性设置一个结点，如果属性依赖图中为每一个属性设置一个结点，如果属性b依赖于属性依赖于属性c，则从属性，则从属性c的结点有一条有向边的结点有一条有向边连到属性连到属性b的结点。的结点。6.2.1 依赖图依赖图 依赖图的构造算法依赖图的构造算法：for 语法树中每一结点语法树中每一结点n do for 结点结点n的文法符号的每一个属性的文法符号的每一个属性a do 为为a在依赖图中建立一个结点在依赖图中建立一个结点；

14、for 语法树中每一个结点语法树中每一个结点n do for 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b:=f(c1,c2,ck ) do for i:=1 to k do 从从ci结点到结点到b结点构造一条有向边结点构造一条有向边； EE1E2 E.val:=E1.val+E2.val E1+E2Evalvalval句子句子real id1，id2，id3的带注释的语法树的的带注释的语法树的依赖图依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entry6.2.1 依赖图依赖图 如果一属性文法不存在属

15、性之间的循环依如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为赖关系，那么称该文法为良定义的良定义的 6.2.1 依赖图依赖图 属性的计算次序属性的计算次序一个依赖图的任何一个依赖图的任何拓扑排序拓扑排序都给出一个语法树中都给出一个语法树中结点的语义规则计算的有效顺序结点的语义规则计算的有效顺序 属性文法说明的翻译是很精确的属性文法说明的翻译是很精确的基础文法用于建立输入符号串的语法分析树基础文法用于建立输入符号串的语法分析树根据计算语义规则建立依赖图根据计算语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序规则的顺序 输

16、入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序句子句子real id1，id2，id3的带注释的语法树的带注释的语法树的依赖图的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);6.2.2 树遍历的属性计算方法树遍历的属性计算方法 通过树遍历的方法计算属性的值通过树遍历的方法计算属性的值 假设语法树已经建立起了，并且

17、树中已带有开假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性始符号的继承属性和终结符的综合属性 以某种次序遍历语法树，直至计算出所有属性以某种次序遍历语法树，直至计算出所有属性深度优先，从左到右的遍历深度优先，从左到右的遍历 无循环的属性文法计算算法：无循环的属性文法计算算法：While 还有未被计算的属性还有未被计算的属性 doVisitNode(S) /*S是开始符号是开始符号*/procedure VisitNode (N:Node) ;begin if N是一个非终结符是一个非终结符 then /*假设它的产生式为假设它的产生式为NX1Xm*/ for i :

18、=1 to m do if not Xi VT then /*即即Xi是非终结符是非终结符*/ begin 计算计算Xi的所有能够计算的继承属性；的所有能够计算的继承属性； VisitNode (Xi) end;计算计算N的所有能够计算的综合属性的所有能够计算的综合属性end产产 生生 式式语语 义义 规规 则则 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 例例: :考虑属性的文法考虑属性的文法G G。其中，。其中，S S有继承属性有继承属性a a，

19、综，综合属性合属性b b；X X有继承属性有继承属性c c、综合属性、综合属性d d；Y Y有继承有继承属性属性e e、综合属性、综合属性f f；Z Z有继承属性有继承属性h h、综合属性、综合属性g g 假设假设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

20、.3 一遍扫描的处理方法一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时一遍扫描的处理方法是在语法分析的同时计算属性值计算属性值 所采用的语法分析方法所采用的语法分析方法属性的计算次序属性的计算次序 L属性文法属性文法适合于一遍扫描的自上而下分适合于一遍扫描的自上而下分析析 S属性文法属性文法适合于一遍扫描的自下而上分适合于一遍扫描的自下而上分析析 6.2.3 一遍扫描的处理方法一遍扫描的处理方法 所谓所谓语法制导翻译法语法制导翻译法，直观上说就是为文，直观上说就是为文法中每个产生式配上一组语义规则，并且法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则在语法分析的同

21、时执行这些语义规则 语义规则就被计算的时机语义规则就被计算的时机在自上而下语法分析中，一个产生式匹配输入在自上而下语法分析中，一个产生式匹配输入串成功时串成功时在自下而上分析中，当一个产生式被用于进行在自下而上分析中，当一个产生式被用于进行归约时归约时6.2.4 抽象语法树抽象语法树 在语法树中去掉那些对翻译不必要的信息，在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种从而获得更有效的源程序中间表示。这种经变换后的语法树称之为经变换后的语法树称之为抽象语法树抽象语法树(Abstract Syntax Tree)BS1S2if_then_elseq Sif B then

22、 S1 else S2q 3*5+4*54+3建立表达式的抽象语法树建立表达式的抽象语法树 mknode (op,left,right) 建立一个运算符号建立一个运算符号结点，标号是结点，标号是op，两个域，两个域left和和right分别分别指向左子树和右子树。指向左子树和右子树。 mkleaf (id,entry) 建立一个标识符结点，建立一个标识符结点，标号为标号为id，一个域，一个域eutry指向标识符在符号指向标识符在符号表中的入口。表中的入口。 mkleaf (num,ral) 建立一个数结点，标号建立一个数结点，标号为为num，一个域，一个域ral用于存放数的值。用于存放数的值。

23、建立抽象语法树的语义规则建立抽象语法树的语义规则产产 生生 式式 语语 义义 规规 则则 EE1+TE.nptr := mknode( +, E1.nptr, T.nptr ) EE1-TE.nptr := mknode( -, E1.nptr, T.nptr ) ETE.nptr := T.nptr T (E) T.nptr := E.nptr TidT.nptr := mkleaf( id, id.entry ) Tnum T.nptr := mkleaf( num, num.val ) a4c的抽象语法树的抽象语法树E nptrT nptrE nptrTo entry for aET n

24、ptrid-T nptridid-idnum4+To entry for c+num6.3 S-属性文法的自下而上计算属性文法的自下而上计算 S-属性文法属性文法：只含有综合属性：只含有综合属性 综合属性可以在分析输入符号串的同时由综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。自下而上的分析器来计算。 分析器可以保存与栈中文法符号有关的综分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属就由栈中正在归约的产生式右边符号的属性值来计算。性值来计算。6.3 S-属性文法的自下而上计算属性文法

25、的自下而上计算 在分析栈中使用一个附加的域来存放综合在分析栈中使用一个附加的域来存放综合属性值属性值 假设语义规则假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于是对应于产生式产生式AXYZ的的 Sm Z.z Z Sm-1 Y.y Y Sm-2 X.x X S0 # TOP Sm-2 A.a A S0 # TOP 产生式产生式 代代 码码 段段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit 翻译输入翻译

26、输入3 3* *5+4n5+4n所做的移动所做的移动输入输入 stateval 用到的产生式用到的产生式 3*5+4n *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T*3 - +4n T*53 - 5 +4n T*F3 - 5 Fdigit +4n T 15 TT*F翻译输入翻译输入3 3* *5+4n5+4n所做的移动所做的移动 输入输入 stateval 用到的产生式用到的产生式 +4n E 15 ET 4n E+15- n E+415- 4 n E+F15- 4 Fdigit n E+T15- 4 TF n E 19 EE+T En19- L

27、 19 LEn6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 通过深度优先的方法对语法树进行遍历，通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值计算属性文法的所有属性值 LL（1）：自上而下分析方法，深度优先）：自上而下分析方法，深度优先建立语法树建立语法树6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 一个属性文法称为一个属性文法称为L-属性文法属性文法，如果对于，如果对于每个产生式每个产生式AX1X2Xn，其每个语义规，其每个语义规则中的每个属性或者是综合属性，或者是则中的每个属性或者是综合属性，或者是Xj(1 j n)的一个继承属性且这个继承属性的一个继

28、承属性且这个继承属性仅依赖于：仅依赖于：(1) 产生式产生式Xj的左边符号的左边符号X1，X2，Xj-1的属的属性；性；(2) A的继承属性。的继承属性。 S-属性文法一定是属性文法一定是L-属性文法属性文法6.4 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 产产 生生 式式 语语 义义 规规 则则 ALM L.i := l(A.i) M.i :=m(l.s) AQR R.i := r(A.i) Q.i :=q(R.s) A.s :=f(Q.s) 上述文法不是上述文法不是L-属性文法，属性文法，Q的继承属性的继承属性Q.i依赖于它右边的文法符号的属性依赖于它右边的文法符号的属性R.s 6

29、.4.1 翻译模式翻译模式 翻译模式翻译模式：给出了使用语义规则进行计：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表算的次序，这样就可把某些实现细节表示出来示出来 在翻译模式中，和文法符号相关的属性在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称和语义规则（这里我们也称语义动作语义动作），），用花括号用花括号 括起来，插入到产生式右部括起来，插入到产生式右部的合适位置上的合适位置上 可将语义动作当成终结符可将语义动作当成终结符n翻译模式示例：翻译模式示例：把带加号和减号的中缀表把带加号和减号的中缀表达式翻译成相应的后缀表达式达式翻译成相应的后缀表达式 ETR Raddo

30、p T print(addop.lexeme) R1 | Tnum print(num.val)-ETR9print(9)TR5print(5)print(-)+T2print(2)Rprint(+) 输入串输入串9-5+2 后缀表达式后缀表达式95-2+6.4.1 翻译模式翻译模式 设计翻译模式时，必须保证当某个动作引设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。用一个属性时它必须是有定义的。 L-属性文法本身就能确保每个动作不会引属性文法本身就能确保每个动作不会引用尚未计算出来的属性。用尚未计算出来的属性。 6.4.1 翻译模式翻译模式 建立翻译模式建立翻译模式:当只需

31、要综合属性时：当只需要综合属性时：为每一个语义规则建立为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾的产生式右边的末尾 产生式产生式 语义规则语义规则 TT1*F T.val:=T1.valF.val建立产生式和语义动作：建立产生式和语义动作： TT1*F T.val:=T1.valF.val6.4.1 翻译模式翻译模式 建立翻译模式建立翻译模式:如果既有综合属性又有继承属性，在建立翻译模式时就如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：必须保证：1. 产生式产生式右边的符号的继承属性必须在这个符号以前的动作

32、中右边的符号的继承属性必须在这个符号以前的动作中计算出来计算出来。2. 一个动作不能引用这个动作右边的符号的综合属性一个动作不能引用这个动作右边的符号的综合属性。3. 产生式左边非终结符的综合属性只有在它所引用的所有属性产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。都计算出来以后才能计算。计算这种属性的动作通常可放在产生计算这种属性的动作通常可放在产生式右端的末尾式右端的末尾。如下列翻译模式不满足条件如下列翻译模式不满足条件1： SA1A2 A1.in:=1; A2.in:=2 Aa print(A.in)6.4.1 翻译模式翻译模式 基于数学格式语言基于数学格式

33、语言EQN给定输入给定输入 E sub 1 .valE1.val识别输入并进行格式安放的识别输入并进行格式安放的L-L-属性文法属性文法 产产 生生 式式语语 义义 规规 则则SBB.ps :=10S.ht :=B.htBB1B2 B1.ps :=B.ps B2.ps :=B.ps B.ht := max(B1.ht, B2.ht)BB1 sub B2B1.ps :=B.ps B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B2.ht)Btext B.ht :=text.hB.ps翻译模式翻译模式 S B.ps:=10 B S.ht:=B.ht B B1.ps:

34、=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2 B.ht:=disp(B1.ht,B2.ht) B textB.ht:=text.hB.ps6.4.2 自顶向下翻译自顶向下翻译 动作是在处于相同位置上的符号被展开动作是在处于相同位置上的符号被展开（匹配成功）时执行的。（匹配成功）时执行的。 为了构造不带回溯的自顶向下语法分析，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归必须消除文法中的左递归 当当消除一个翻译模式的基本文法的左递归消除一个翻译模式的

35、基本文法的左递归时同时考虑属性时同时考虑属性适合带综合属性的翻适合带综合属性的翻译模式译模式 6.4.2 自顶向下翻译自顶向下翻译 关于算术表达式的左递归文法相应的翻译关于算术表达式的左递归文法相应的翻译模式模式EE1+TE.val:=E1.val+T.valEE1-T E.val:=E1.val-T.valET E.val:=T.valT(E)T.val:=E.valTnumT.val:=num.val 消除左递归，构造新的翻译模式消除左递归，构造新的翻译模式 E TR.i:=T.val RE.val:=R.sR + TR1.i:=R.i+T.val R1R.s:=R1.sR - TR1.i

36、:=R.i-T.val R1R.s:=R1.sR R.s:=R.iT ( E ) T.val:=E.valT num T.val:=num.val计算表达式计算表达式9 95 52 2 ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.val=2R.i=6 R.s=6R.s=6R.s=6E.s=6自顶向下分析一般方法自顶向下分析一般方法 假设有翻译模式：假设有翻译模式： AA1YA.a:=g(A1.a,Y.y) AXA.a:=f(X.x)它的每个文法符号都有一个综合属性，用小写它的每个文法符号都有一个综

37、合属性，用小写字母表示，字母表示，g和和f是任意函数。是任意函数。q消除左递归：消除左递归： AXR RYR | q翻译模式变为翻译模式变为 ：A XR.i:=f (X.x) RA.a:=R.sR Y R1.i:=g(R.i,Y.y) R1R.s:=R1.sR R.s:=R.iXYY XA A.a=f(X.x)Y1A A.a=g(f(X.x),Y1.y)Y2A A.a=g(g(f(X.x),Y1.y), Y2.y) XYY AXR R.i=f(X.x)Y1R R.i= g(f(X.x),Y1.y)Y2R R.i= g(g(f(X.x),Y1.y), Y2.y) R.s= g(g(f(X.x),

38、Y1.y), Y2.y) R.s= g(g(f(X.x),Y1.y), Y2.y)R.s= g(g(f(X.x),Y1.y), Y2.y)A.a= g(g(f(X.x),Y1.y), Y2.y)构造抽象语法树的构造抽象语法树的属性文法定义转化属性文法定义转化成翻译模式成翻译模式 EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr构造抽象语法树的构造抽象语法树的属性文法定义转化属性文法定义转化成翻译模式成翻译模式 E TR.i:=T.nptr RE.nptr:=R.s

39、R + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR TR1.i:=mknode(,R.i,T.nptr) R1R.s:=R1.sR R.s:=R.iT ( E )T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T numT.nptr:=mkleaf(num,num.val)使用继承属性构造使用继承属性构造a a4 4c c的抽象语法树的抽象语法树ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i R

40、. sR. sR. sE.nptr6.4.3 递归下降翻译器的设计递归下降翻译器的设计 如何在递归下降分析中实现翻译模式，构如何在递归下降分析中实现翻译模式，构造造递归下降翻译器递归下降翻译器 设计递归下降翻译器的方法设计递归下降翻译器的方法6.4.3 递归下降翻译器的设计递归下降翻译器的设计 设计递归下降翻译器的方法：设计递归下降翻译器的方法：1. 对每个非终结符对每个非终结符A构造一个函数过程构造一个函数过程，对对A的每的每个继承属性设置一个形式参数个继承属性设置一个形式参数，函数的返回值为函数的返回值为A的综合属性的综合属性（作为记录，或指向记录的一个指针，（作为记录，或指向记录的一个指

41、针，记录中有若干域，每个属性对应一个域）。为了记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性。简单，我们假设每个非终结只有一个综合属性。A对应的函数过程中，为出现在对应的函数过程中，为出现在A的产生式中的每一的产生式中的每一个文法符号的每一个属性都设置一个局部变量个文法符号的每一个属性都设置一个局部变量。2. 非终结符非终结符A对应的函数过程中，根据当前的输对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。入符号决定使用哪个产生式候选。6.4.3 递归下降翻译器的设计递归下降翻译器的设计 设计递归下降翻译器的方法：设计递归下降翻译器的方法：3. 每

42、个产生式对应的程序代码中，按照从左到每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：符和语义动作分别作以下工作：qi) 对于带有综合属性对于带有综合属性x的终结符的终结符X，把，把x的值存入为的值存入为X.x设置的设置的变量中。然后产生一个匹配变量中。然后产生一个匹配X的调用，并继续读入一个输入符的调用，并继续读入一个输入符号。号。qii) 对于每个非终结符对于每个非终结符B，产生一个右边带有函数调用的赋值，产生一个右边带有函数调用的赋值语句语句c=B(b1,b2,bk)，其中，其中，b1,b2,

43、bk是为是为B的继承属性设的继承属性设置的变量，置的变量，c是为是为B的综合属性设置的变量。的综合属性设置的变量。qiii) 对于语义动作，把动作的代码抄进分析器中，用代表属性对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。的变量来代替对属性的每一次引用。构造抽象语法树的构造抽象语法树的属性文法定义转化属性文法定义转化成翻译模式成翻译模式 E TR.i:=T.nptr RE.nptr:=R.sR + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR TR1.i:=mknode(,R.i,T.nptr) R1R.s:=R1.sR

44、R.s:=R.iT ( E )T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T numT.nptr:=mkleaf(num,num.val)递归下降翻译器实现递归下降翻译器实现 非终结符非终结符E、R、T的函数及其参数类型的函数及其参数类型 functionE:AST-node;functionR(in:AST-node): AST-node;functionT: AST-node; 用用oddop代表和代表和 R oddop TR1.i:=mknode(addop,lexme, R.i,T.nptr) R1R.s:=R1.s R R.s:=R.i递

45、归下降翻译器实现递归下降翻译器实现 产生式产生式Raddop TR| 的分析过程的分析过程 procedare R; begin if sym=addop then begin advance;T; R end else begin /*do nothing*/ end end; 在此基础上在此基础上,构造属性文法的函数过程构造属性文法的函数过程: function R (in:AST-node): AST-node; var nptr, i1,s1,s: AST-node; addoplexeme: char; begin if sym=addop then begin /*产生式产生式Ra

46、ddop TR */ addoplexeme:=lexval; advance; nptr:=T; i1:=mknode (addoplexeme, in, nptr); s1:=R (i1) s:=s1 end else s:=in; return s end;6.5 自下而上计算继承属性自下而上计算继承属性 在自下而上的分析过程中实现在自下而上的分析过程中实现L-属性文属性文法的方法法的方法 可实现任何基于可实现任何基于LL（1）文法的）文法的L-属性文属性文法，还可以实现许多（不是所有）基于法，还可以实现许多（不是所有）基于LR（1）文法的）文法的L-属性文法属性文法6.5.1从翻译模式

47、中去掉嵌入在产生式中间的动从翻译模式中去掉嵌入在产生式中间的动作作 要求把所有的语义动作都放在产生式的要求把所有的语义动作都放在产生式的末尾末尾 转换方法，它可以使所有嵌入的动作都转换方法，它可以使所有嵌入的动作都出现在产生式的末尾出现在产生式的末尾 加入新的产生式加入新的产生式M 把嵌入在产生式中的每个语义动作用不同的把嵌入在产生式中的每个语义动作用不同的标记非终结符标记非终结符M代替，并把这个动作放在产代替，并把这个动作放在产生式生式M 的末尾的末尾 6.5.1从翻译模式中去掉嵌入在产生式中间的动从翻译模式中去掉嵌入在产生式中间的动作作 翻译模式翻译模式 E TRR T print () R | T print ()R| T num print (num.val) 转换为转换为 E TRR TMR | TNR | T num print (num.val)M print ()N print ()6.5.2 分析栈中的继承属性分析栈中的继承属性 属性位置能预测L归约时，T恰在右部下面 例: int p, q, r D T L.in := T.type LT int T. type := integerT real T. type := realL L1.in := L.in L1, id addtype