第六章 属性文法 20(1)

1、 属性文法和语法制导翻译属性文法和语法制导翻译 语义处理在编译程序中的逻辑位置语义处理在编译程序中的逻辑位置词法分析词法分析语法分析语法分析中间代码生成中间代码生成中间代码优化（可选）中间代码优化（可选）目标代码优化（可选）目标代码优化（可选）目标代码生成目标代码生成静态语义分析静态语义分析语义处理语义处理- 两项工作：两项工作：静态语义分析，中间代码生成静态语义分析，中间代码生成 静态语义分析：主要工作如类型检查、名字的作用域静态语义分析：主要工作如类型检查、名字的作用域 分析等分析等 中间代码生成中间代码生成：从语法分析的结果生成中间代码（个：从语法分析的结果生成中间代码（个 别编译程序可

2、能直接生成目标代码）别编译程序可能直接生成目标代码）- 跨分析和综合两个阶段跨分析和综合两个阶段 分析分析阶段：理解源程序，挖掘源程序的语义阶段：理解源程序，挖掘源程序的语义 综合综合阶段：生成与源程序语义上等价的目标程序阶段：生成与源程序语义上等价的目标程序- 跨编译程序的前端和后端跨编译程序的前端和后端 语义处理在编译程序中的逻辑位置语义处理在编译程序中的逻辑位置 编译程序的设计中，语义分析和中间（目标）代码生编译程序的设计中，语义分析和中间（目标）代码生 成的实现多采用成的实现多采用语法制导的语义处理语法制导的语义处理（许多时候直接（许多时候直接 称之为称之为语法制导的翻译语法制导的翻译

3、） 语法制导语义处理技术的基础是应用语法制导语义处理技术的基础是应用属性文法属性文法 语义处理技术语义处理技术本章我们应该掌握什么本章我们应该掌握什么v属性文法的一些基本概念属性文法的一些基本概念 v基于属性文法的几种处理方法基于属性文法的几种处理方法vS S- -属性文法的自上而下计算属性文法的自上而下计算vL-L-属性文法和自顶向下翻译属性文法和自顶向下翻译v自下而上计算继承属性自下而上计算继承属性一一 属性文法的基本概念属性文法的基本概念 属性文法属性文法（也称属性翻译文法）： Kunth在1968年首先提出的。 它是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相

4、关的“值”（称为属性属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等。 属性与变量一样，可以进行计算和传递。 属性加工的过程即是语义处理的过程。 - 识别语言识别语言 L = aibjck i, j, k 1 但显示但显示 anbncn (n 1) 是合法的是合法的产生式产生式S ABCA A1aA aB B1bB bC C1cC c 语义规则语义规则 if (A.num=B.num) and (B.num=C.num) then print(“Accepted!” ) else print(“Refused!” ) A.num := A1.num + 1 A.

5、num := 1 B.num := B1.num + 1 B.num := 1 C.num := C1.num + 1 C.num := 1 语义规则：语义规则： 在一个属性文法中，对应于每个产生式A 都有一套与之相关语义规则，每条规则的形式为 b:= f(c1,c2,ck)这里，f是一个函数 b是A的一个综合属性综合属性并且c1,c2,ck是产生式右边文法符号的属性；或者 b是产生式右边某个文法符号的一个继承属性继承属性并且c1,c2,ck是A或产生式右边任何文法符号的属性。在这两种情况下，我们都说属性b依赖于属性c1,c2,ck。对于文法的每个产生式都配备的一组属性的计算规则。例一例一产生

6、式ABC可能有规则 C.d := B.c + 1 A.b := A.a + B.c这些属性是什么类型？A.a和B.c在什么地方计算？强调强调v终结符只有综合属性，它们由词法分析器提供；v非终结符既可以有综合属性也可有继承属性v文法开始符号的所有继承属性作为属性计算前的初始值v对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则v出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其他产生式的属性计算规则或者由属性计算器的参数提供综合属性综合属性 综合属性在实际中被广泛应用。在语法树中，一个结点的综合属性的值由其子结点的属

7、性值确定。因为，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。 下面的简单例子说明综合属性的使用和计算过程。下面的简单例子说明综合属性的使用和计算过程。 说明：非终结符E，T，F都有一个综合属性val的整数值。符号digit有一个综合属性lexval，由词法分析器提供。产生式LEn对应的语法规则为打印由E产生的算术表达式的值的过程。 产生式 语义规则LEnEE1+TETTT1*FTFF (E)FdigitPrint ( E.val )E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.val

8、T.val:=F.valF.val:=E.valF.val:=digit.lexval表一表一 一个简单计算器的属性文法一个简单计算器的属性文法假设表达式是354，后跟换行符n画出语法树，并根据语义规则加注释Digit.lexval=3F.val=3T.val=3Digit.lexval=5T.val=15*F.val=5E.val=15E.val=19T.val=4F.val=4Digit.vexval=4Ln+例二例二- 语法分析树中各结点属性值的计算过程被称为对语语法分析树中各结点属性值的计算过程被称为对语 法分析树的法分析树的标注标注（annotating）或）或修饰修饰（decora

9、ting），）， 用用带标注带标注（annotatedannotated）的语法分析树的语法分析树表示属性值的计算结果表示属性值的计算结果继承属性继承属性 语法树中，一个结点的继承属性由此结点的父结点和或兄弟语法树中，一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。结点的某些属性确定。 用继承属性来表示程序设计语言结构中的上下文依赖关系很用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。方便。给出句子real id1,id2,id3,看看它的带注释的语法树例三例三产生式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type:=integer

10、T.type:=realL1.in:=L.inAddtype(id.entry,L.in)Addtype(id.entry,L.in)realT.type=realDL.in=realL.in=realL.in=real,id1id2id3此例为继承属性在说明中为各种标识符提此例为继承属性在说明中为各种标识符提供类型信息供类型信息非终结符非终结符T有一个综合属性有一个综合属性type，它的值由，它的值由说明中的关键字确定说明中的关键字确定.与产生式与产生式DTL相应的语义规相应的语义规L.in:=T.type把说明中的类型赋值给继承属性把说明中的类型赋值给继承属性L.in.利用语义规则把继承属

11、性利用语义规则把继承属性L.in沿着语沿着语法树往下传法树往下传.Addtype把每个标志符的类型填入符号表把每个标志符的类型填入符号表的相应项中的相应项中.二二 基于属性文法的处理方法基于属性文法的处理方法v基于属性文法的处理过程基于属性文法的处理过程 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译语法制导翻译。语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其他动作。对输入符号串的翻译也就是根据语义规则进行计算的结果。输入串输入串 语法树语法树依赖图依赖图 语义规则计算次序语义规则计算次序 如果在一颗语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的

12、语义规则必须在确定c的语义规则之后使用。在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图依赖图的一个有向图来描述。 强调：在为一颗语法树构造依赖图以前，为每一个包含过程调用的语义规则引入一个虚综合属性虚综合属性b，这样把每一个语义规则都写成 b := f(c1,c2,ck)的形式。依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。 举例四举例四当下面的产生式应用于语法树时，产生的依赖图如图。 产生式 语义规则 E1E1+E2 E.val := E1.val+E2.val图中虚线表示的是语法树，它不是依赖图中的一部分

13、。E1 E E2画出语法树画出语法树根据规则，画出依赖图根据规则，画出依赖图.val.val.val句子句子real id1，id2，id3的的带注释的语法树的依赖图带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10 addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in add

14、type(id.entry, L.in) Lid addtype(id.entry, L.in) 举例五举例五v循环依赖关系循环依赖关系例如：p,c1,c2都是属性，有如下求值规则p:=f1(c1) , c1:= f2(c2) , c2 := f3(p) ，此时无法对p求值 v良定义属性文法良定义属性文法如果一属性文法不存在属性之间的循环依赖关系，那么该属性文法为良定义良定义的。 （我们只处理良定义的属性文法）v拓扑序拓扑序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说mimj是mi到mj的一条边，那么在序列中mi必须出现在

15、mj之前。句子句子real id1，id2，id3的带注释的语法树的带注释的语法树的依赖图属性计算顺序的依赖图属性计算顺序id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);v通过树遍历的方法计算属性的值通过树遍历的方法计算属性的值 假设语法树已建立，且树中已带有开始符号的假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性继承属

16、性和终结符的综合属性 以某种次序遍历语法树，直至计算出所有属性以某种次序遍历语法树，直至计算出所有属性v深度优先，从左到右的遍历深度优先，从左到右的遍历 最常用的遍历方法是深度优先，从左到右的遍历的方法。可使用多次遍历（或称遍）。While 还有未被计算的属性 do VisitVode(S) /*S是开始符号*/procedure VisitNode(N:Node);begin if N是一个非终结符 then /* 假设它的产生式为N X1Xm*/ for i:= 1 to m do if XiVN then /*即Xi是非终结符*/ begin 计算Xi的所有能够计算的继承属性 Visit

17、Node(Xi） end 计算N的所有能够计算的综合属性endS有继承属性a，综合属性b X有继承属性c，综合属性dY有继承属性e，综合属性f Z有继承属性h，综合属性g 举例六举例六产生式语义规则S XYZX xY yZ zZ.h := S.aX.c := Z.gS.b := X.d 2Y.e :=S.bX.d := 2*X.cY.f :=Y.e*3Z.g := Z.h+1参照树遍历的算法,对其计算属性VisitNode (S)首先首先,画出语法树画出语法树S.a=0XYZxyz然后执行第一次遍历然后执行第一次遍历,如左图所示如左图所示X.c不能计算不能计算VisitNode (X)X.d不

18、能计算不能计算Y.e不能计算不能计算VisitNode (Y)Y.f不能计算不能计算Z.h:=0VisitNode (Z)Z.g:=1S.b不能计算不能计算:h=0g=1第一遍计算了第一遍计算了Z.h和和Z.g,下面进行第二遍遍历下面进行第二遍遍历VisitNode (S)X.c:=1VisitNode (X)X.d:=2Y.e不能计算不能计算VisitNode (Y)Y.f不能计算不能计算Z.h:=0VisitNode (Z)Z.g:=1S.b不能计算不能计算:c=1d=2第二遍计算出了第二遍计算出了X.c和和X.d,继续第三遍遍历继续第三遍遍历VisitNode (S)X.c:=1Visi

19、tNode (X)X.d:=2Y.e:=0VisitNode (Y)Y.f:=0Z.h:=0VisitNode (Z)Z.g:=1S.b不能计算不能计算:e=0f=0经过三次遍历经过三次遍历,完成了属性的计算完成了属性的计算假设假设S.a的初始值为的初始值为0，输入串为，输入串为xyz产产 生生 式式 语语 义义 规规 则则 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 v一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语一遍扫描的处理方法是在语

20、法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算。法分析构造语法树之后进行属性的计算。v一遍扫描处理方法与下面两个因素密切相关一遍扫描处理方法与下面两个因素密切相关v所采用的语法分析方法所采用的语法分析方法v属性的计算次序属性的计算次序v L-属性文法可用于一遍扫描的自上而下分析，属性文法可用于一遍扫描的自上而下分析， S-属性文法适合于一遍扫描的自下而上分析属性文法适合于一遍扫描的自下而上分析 在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为（Abstract Syntax Tree)。 在抽象语法树中，操作符和关键字都不作为

21、叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点。问表达式3*5+4 的抽象语法树？BS1S2if_then_elseq Sif B then S1 else S2q 3*5+4*54+3Digit.lexval=3F.val=3T.val=3Digit.lexval=5T.val=15*F.val=5E.val=15E.val=19T.val=4F.val=4Digit.vexval=4Ln+这是这是 3*5+4 的带注释语法树的带注释语法树这是它的抽象语法树这是它的抽象语法树35*+4v如何建立表达式的抽象语法树如何建立表达式的抽象语法树vmknode(op,left,right)

22、建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树。vmkleaf（id，entry）建立一个标识符结点，标号为id，一个域entry指向标识符在符号表中的入口。vmkleaf（num，val）建立一个数结点，标号为num，一个域val用于存放数的值。注：每一个函数都返回一个指向新建立结点的指针。注：每一个函数都返回一个指向新建立结点的指针。下面一系列函数调用建立了表达式a-4+c的抽象语法树，在这个序列中，p1，p2,p5是指向结点的指针，entrya和entryc分别是指向符号表中的标识符a和c的指针。 举例七举例七(1) p1 := mkleaf (id

23、, entrya) ;id to entry for a(2) p2 :=mkleaf (num, 4 );(3) p3 := mknode ( , p1,p2 );(4) p4 := mkleaf (id , entryc ) ;(5) p5 := mknode ( + , p3,p4 );-+num4id to entry for c下面考虑建立语法分析树的语义规则下面考虑建立语法分析树的语义规则 下表是一个为包涵运算符号下表是一个为包涵运算符号+和和-的表达式建立抽象语法树的的表达式建立抽象语法树的 S-属性文法属性文法. 利用文法的基本产生式来安排函数利用文法的基本产生式来安排函数mk

24、node和和mkleaf 的调用来建立语法树的调用来建立语法树. E 和和T 的综合属性的综合属性nptr是函数调用返回的是函数调用返回的 指针指针产生式语义规则EE1 + TEE1 TETT(E)T idTnumE.nptr := mknode(+,E1.nptr,T.nptr)E.nptr := mknode(-,E1.nptr,T.nptr)E.nptr :=T.nptrE.nptr :=T.nptrT.nptr:=mknode (id,id.entry)T.nptr:=mknode (num,num.val) 举例八举例八E nptrT nptrE nptrT nptrET nptri

25、dnum+-首先画出带注释的语法分析树首先画出带注释的语法分析树根据根据上表上表中的语义规则中的语义规则,各个结点分别应用各个结点分别应用,可以很容易地画出抽象语法树可以很容易地画出抽象语法树id to entry for a-+num4id to entry for c产生式语义规则EE1 + TEE1 TETT(E)T idTnumE.nptr := mknode(+,E1.nptr,T.nptr)E.nptr := mknode(-,E1.nptr,T.nptr)E.nptr :=T.nptrE.nptr :=T.nptrT.nptr:=mknode (id,id.entry)T.npt

26、r:=mknode (num,num.val)表达式表达式a-4+cv属性文法属性文法v属性分类属性分类v综合属性：综合属性：v继承属性：继承属性：自下而上自上而下v基于属性文法的处理方法基于属性文法的处理方法v依赖图依赖图v属性的计算次序（拓扑序）属性的计算次序（拓扑序）v树遍历的属性计算方法树遍历的属性计算方法v一遍扫描的处理方法一遍扫描的处理方法v抽象语法树抽象语法树vS-属性文法：只含有属性文法：只含有综合属性综合属性。v综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。 分析器可以保存与栈中文法符号有关的综合属性值

27、，每当进行归约分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约 时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计 算。算。vS-属性文法的翻译通常可借助于属性文法的翻译通常可借助于LR分析器分析器实现。在实现。在S-属性文法的基属性文法的基 础上，础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析分析器可以改造为一个翻译器，在对输入串进行语法分析 的同时对属性进行计算。的同时对属性进行计算。三三 v分析栈中的综合属性分析栈中的综合属性在自底向上的分析方法中，使用一个栈来存放已经分析过的子树的信息。在分析栈中

28、使用一个附加的域来存放综合属性。XX.xYY.yZZ.zstatevaltop语义规则A.a := f(X.x,Y.y,Z.z)是对应于产生式AXYZ的。 举例九举例九此例对象是例二台式计算器的属性文法此例对象是例二台式计算器的属性文法.加入代码段后是如下左表加入代码段后是如下左表右表为分析栈右表为分析栈,我们分析在输入我们分析在输入3*5+4n上的移动序列上的移动序列 产生式 语义规则LEnEE1+TETTT1*FTFF (E)FdigitPrint (val top )val ntop:= val top-2+ val top val ntop:= val top-2* val topva

29、l ntop:= val top-1statevaltop输入输入333应用产生式应用产生式FdigitF应用产生式应用产生式TFT输入输入*top*-输入输入5top55应用产生式应用产生式FdigitF应用产生式应用产生式TT1*F15应用产生式应用产生式ETE下面的步骤和上面类似下面的步骤和上面类似,在用到有代码段的产生式时在用到有代码段的产生式时,就就进行一次归约进行一次归约vL-L-属性文法属性文法：如果对于每个产生式如果对于每个产生式A AX1X2X1X2XnXn，其每个其每个 语义规则中的每个属性语义规则中的每个属性 或者是综合属性或者是综合属性 或者是或者是XjXj（1=j=n

30、1=j95-2+输入串9-5+2v翻译模式设计翻译模式设计v注意：保证某个动作引用一个属性时它必须是有定义的。注意：保证某个动作引用一个属性时它必须是有定义的。vL-L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。属性文法本身就能确保每个动作不会引用尚未计算出来的属性。v对于对于S-属性属性，只需要综合属性时，为每一个语义规则建立一个包含，只需要综合属性时，为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如，。例如，有如下产生式和语义规则：有如下产生式和语义规则： 产生式 语义规则 TT1 * F

31、T.val := T1.val * F.val 建立产生式和语义动作： TT1 * F T.val := T1.val * F.valv对于对于L-属性，如果既有综合属性又有继承属性属性，如果既有综合属性又有继承属性（1）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。（2）一个动作不能引用这个动作右边的符号的综合属性。（3）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。v复习：复习：L-L-属性文法属性文法：如果对于每个产生式如果对于每个产生式A AX1X2X1X2XnXn，其每个其每个 语义规则中的每

32、个属性语义规则中的每个属性 或者是综合属性或者是综合属性 或者是或者是XjXj（1=j=n1=jA1A2 A1.in := 1; A2.in := 2Aa print(A.in)按深度优先遍历输入串aa的语法树时，能想出会出现什么错误吗？翻译模式不满足上述三个条件中的第一个条件打印第二个产生式里继承属性A.in的值时，该属性还没有定义。解决方案：将第一条产生式变为：S S A A1 1.in := 1 .in := 1 A A1 1 A A2 2 .in := 2 .in := 2 A A2 2 L-属性文法在自顶向下分析中的实现。属性文法在自顶向下分析中的实现。用翻译模式进行动作的顺序和属性

33、计算的顺序的描述用翻译模式进行动作的顺序和属性计算的顺序的描述 自顶向下翻译自顶向下翻译v算术表达式的左递归文法相应的翻译模式EE1+TE.val:=E1.val+T.valEE1-T E.val:=E1.val-T.valETE.val:=T.valT(E) T.val:=E.valTnumT.val:=num.valE T RR + T R1R - T R1R T ( E )T num为了构造不带回溯的自顶向下语法分析，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。必须消除文法中的左递归。v构造新的翻译模式 E TR.i:=T.val RE.val:=R.sR + TR1.i

34、:=R.i+T.val R1R.s:=R1.sR - TR1.i:=R.i-T.val R1R.s:=R1.sR R.s:=R.iT ( E )T.val:=E.valT numT.val:=num.valE T RR +TR1R -TR1R T ( E )T numR.i: R前面子表达式的值R.s: 分析完R时子表达式的值计算表达式952 ETRnumnum.val=9T.val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.val=2R.i=6R.s=6R.s=6R.s=6E.val=6E T R.i:=T.val R E.val:=

35、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 T num T.val:=num.val 一般方法v假设有翻译模式： AA1YA.a:=g(A1.a,Y.y) AXA.a:=f(X.x)它的每个文法符号都有一个综合属性，用小写字母表示，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

36、:=R.iR.i: R前面子表达式的值R.s: 分析完R时子达式的值将构造抽象语法树的属性文法定义转换为翻译模式转换前：转换后： 举例十一举例十一EE1+T E.nptr:=mknode( + ,E1.nptr,T.nptr )EE1-T E.nptr:=mknode( - ,E1.nptr,T.nptr )ET E.nptr:= T.nptr ET R.i:=T.nptr R E.nptr:=R.sR+ T R1.i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.sR- T R1.i:=mknode(-,R.i,T.nptr) R1 R1.s:=R.sR R.s=R1.s

37、T ( E ) T.nptr :=E.nptrTid T.nptr:=mkleaf(id,id.entry)Tnum T.nptr:=mkleaf(num,num.val)使用继承属性构造使用继承属性构造a4c的抽象语法树的抽象语法树ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i R. sR. sR. sE.nptrE T R.i:=T.nptr R E.nptr:=R.sR + T R1.i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.sR - T

38、R1.i:=mknode(,R.i,T.nptr) R1 R.s:=R.sR R.s:=R.iT ( E ) T.nptr:=E.nptrT id T.nptr:=mkleaf(id,id.entry)T num T.nptr:=mkleaf(num,num.val)L-属性定义的递归下降翻译法属性定义的递归下降翻译法1. 对每个非终结符A构造一个函数u函数的返回值为A的综合属性u如果有多个综合属性可设置记录型数据结构，记录中有若干域，每个属性对应一个域u对A的每个继承属性设置一个形式参数u在函数体中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。2. 非终结符A对应的函

39、数体中，不仅要进行语法分析，而且还要处理相应的语义属性。根据当前的输入符号决定使用哪个产生式候选展开A，然后根据3中的方法对产生式进行处理。v3. 每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：i) 对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。ii) 对于每个非终结符B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,bk)，其中，b1,b2,bk是为B的继承属性设置的变量，c是为B的综合属性设置的变量。iii) 对于语义动作，把动作的代码抄进分析器中，用代表

40、属性的变量来代替对属性的每一次引用。v非终结符非终结符E、R、T的函数及其参数类型的函数及其参数类型 function E:AST-node;function R(in:AST-node): AST-node;function T: AST-node;v 用用oddop代表和代表和 R oddop TR1.i:=mknode(addop.lexme, R.i,T.nptr) R1R.s:=R1.s R R.s:=R.i复习：复习： 产生式产生式Raddop TR| 的递归下降分析过程的递归下降分析过程 procedare R; begin if sym=addop then begin adv

41、ance;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 /*产生式Raddop TR */ addoplexeme:=lexval; advance; nptr:=T; i1:=mknode (addoplexeme, in, nptr); s1:=R (i1) s:=s1 end else s:= in; return s e

42、nd;R oddop TR1.i:=mknode(addop.lexme, R.i, T.nptr) R1 R.s:=R1.s R R.s:=R.ivS-属性文法的自下而上翻译属性文法的自下而上翻译vS-属性文法：属性文法：只含有综合属性v带有附加域（存放综合属性）的分析栈，用带有附加域（存放综合属性）的分析栈，用（ ） 实现的实现的v用代码段代替语义规则。用代码段代替语义规则。一对数组state与valvL-属性文法和自顶向下翻译属性文法和自顶向下翻译vL-属性文法属性文法v翻译模式翻译模式将语义规则（即语义动作）按一定要求插入到产生式右部的合适位置v自顶向下翻译：消除左递归后如何构造翻译模

43、式自顶向下翻译：消除左递归后如何构造翻译模式 这里，我们讨论在自下而上的分析过程中实现这里，我们讨论在自下而上的分析过程中实现L-L-属性文法的方法。这种方法可以实现任何基于属性文法的方法。这种方法可以实现任何基于LLLL（1 1）文法的文法的L-L-属性文法，它还可以实现许多（不是所有属性文法，它还可以实现许多（不是所有）基于）基于LR(1)LR(1)文法的文法的L-L-属性文法。这种方法是前面介属性文法。这种方法是前面介绍的自下而上翻译技术的一般化。绍的自下而上翻译技术的一般化。 从翻译模式中去掉嵌入在产生式中间的动作从翻译模式中去掉嵌入在产生式中间的动作 我们要介绍一种转换方法，它可以使

44、所有嵌入的动作都出现我们要介绍一种转换方法，它可以使所有嵌入的动作都出现在产生式的末尾，这样就可以自下而上处理继承属性。这样在自在产生式的末尾，这样就可以自下而上处理继承属性。这样在自下而上分析过程中产生式右部被归约时执行相应的动作。下而上分析过程中产生式右部被归约时执行相应的动作。 ETR R + T print(+) R|- T print(-) R| T num print(num.val)使用标记非终结符号使用标记非终结符号M和和N转换为转换为 ETR R + T M R|- T N R| T num print(num.val) M print(+) N print(-) 转换方法为

45、：在基础文法中加入新的产生式，这种产生式的形式转换方法为：在基础文法中加入新的产生式，这种产生式的形式为为M ，其中其中M为新引入的一个为新引入的一个。把嵌入在产生。把嵌入在产生式中的每个语义动作用不同的标记非终结符式中的每个语义动作用不同的标记非终结符M代替，并把这个动代替，并把这个动作放在产生式作放在产生式M 的末尾。的末尾。 分析栈中的继承属性分析栈中的继承属性 自下而上分析器对产生式AXY的右部是通过把X和Y从分析栈中移出并用A代替它们。假设X有一个综合属性X.s，由于X.s的值在Y以下的子树中的任何归约之前已经放在栈中，这个值可以被Y继承。也就是说，如果继承属性Y.i是由复写规则Y.

46、i := X.s定义的，则可以在需要Y.i值的地方使用X.s的值。产生式翻译模式DT LTintTrealL L1,idLidL.in:=T.typeT.type:=integerT.type:=realL1.in:=L.inAddtype(id.entry,L.in)Addtype(id.entry,L.in)输入为输入为int p,q,r ,语法树如上语法树如上DTLLL,r,qpint按照翻译模式,标识符类型通过继承属性复写规则来传递.type. in. in. in使用L产生式时是怎样得到属性 T.type 的值. 对输入串进行语法分析的过程如下表所示. 为了清楚,我们用文法符号表示栈

47、中该文法符号所对应的状态,用实际的标识符表示id输入串状态所用产生式int p,q,rp,q,rp,q,r,q,r,q,rq,r,r,rr-intTTpTLTL,TL,qTLTL,TL,rTLDTintLidLL,idLL,idDTL翻译模式翻译模式D T L.in := T.type LT int T.type := integer real T.type := real L L1.in := L.in L1 , v addtype(v.entry,L.in) L v addtype(v.entry,L.in) D T LT int val top := integerT real val

48、top := realL L , v addtype(val top , val top-3 )L v addtype(val top , val top-1 )(分析栈分析栈val 存放文法符号的综合属性，存放文法符号的综合属性，top为栈顶指针为栈顶指针)产生式产生式 依产生式归约时语义处理的代码片断依产生式归约时语义处理的代码片断1.属性位置能预测属性位置能预测2.2.属性的位置不能预测属性的位置不能预测3.属性是某个综合属性的一个函数模拟继承属性的计算继承分析栈上的继承属性计算的问题分析分析栈上的继承属性计算的问题分析 考虑如下翻译模式： S a A C.i := A.s C b A

49、B C.i := A.s C C c C.s := g(C.i)若直接应用上述复写规则的处理方法，则在使用 C c 进行归约时，C.i 的值或存在于次栈顶（top-1），或存在于次次栈顶（top-2），不能确定用哪一个. 一种可行的做法是引入新的非终结符 M，将以上翻译模式改造为：S a A C.i := A.s C b A B M.i := A.s M C.i := M.s C C c C.s := g(C.i)M M.s := M.i 这样，在使用C c 进行归约时，C.I 的值就一定可以通过访问次栈顶（top-1）得到 属性的位置不能预测属性的位置不能预测下图给出了修改产生式前后把属性值

50、传递到C.i的依赖关系图SbA . sB. CiSbA . sB. M .i s. Ci. . 模拟继承属性的实现模拟继承属性的实现 考虑如下翻译模式：考虑如下翻译模式： S a A C.i := f(A.s) C 这里，继承属性这里，继承属性 C.i 不是通过复写规则来求值，而是通过普通函数不是通过复写规则来求值，而是通过普通函数 f(A.s) 调用来计算调用来计算. 在计算在计算 C.i 时，时，A.s 在语义栈上，但在语义栈上，但 f(A.s)并未并未存在于语义栈存在于语义栈. 同样，一种做法是引入新的非终结符同样，一种做法是引入新的非终结符M，将以上翻，将以上翻译模式改造为：译模式改造

51、为： S a A M.i := A.s M C.i := M.s C M M.s := f(M.i) 这样，这样，就解决了上述问题。想一想，为什么？就解决了上述问题。想一想，为什么？注：从注：从翻译模式中去掉嵌在产生式中间的语义规则集时，若语义翻译模式中去掉嵌在产生式中间的语义规则集时，若语义规则集中有关联的属性，则规则集中有关联的属性，则可参照此例的解决方案可参照此例的解决方案模拟继承属性的计算又一例继承属性是某个综合属性的一个函数S aACC.i = f (A.s)C cC.s = g(C.i)增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行S aANCN.i = A.s

52、; C.i = N.sN N.s = f (N.i)C cC.s = g(C.i)例 数学排版语言EQN S B.ps = 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 产产 生生 式式 语语 义义 规规 则则 S LB B.ps = L.s; S.ht = B.ht L L.s = 10 B B1 M

53、B2 B1.ps = B.ps; M.i = B.ps;B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M M.s = M.i B B1 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N N.s = shrink(N.i) B text B.ht = text.h B.ps 举例说明举例说明SM sB L s BBtext BsubN sBtext text产产 生生 式式 代代 码码 段段S LB B.ps = L.s; S.ht = B.ht L L.s = 10

54、 B B1 MB2 B1.ps = B.ps; M.i = B.ps;B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M M.s = M.i B B1 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N N.s = shrink(N.i) B text B.ht = text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式 代代 码码 段段S LB valtop- -1 = valtopL L.s = 10 B B1 MB2 B1.ps = B.

55、ps; M.i = B.ps;B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M M.s = M.i B B1 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N N.s = shrink(N.i) B text B.ht = text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式 代代 码码 段段S LB valtop- -1 = valtopL valtop+1 = 10B B1 MB2 B1.ps = B.ps; M.i = B.ps;B

56、2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M M.s = M.i B B1 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N N.s = shrink(N.i) B text B.ht = text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式 代代 码码 段段S LB valtop- -1 = valtopL valtop+1 = 10B B1 MB2 valtop- -2 = max(valtop- -2, valtop) M M.s

57、 = M.i B B1 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N N.s = shrink(N.i) B text B.ht = text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式 代代 码码 段段S LB valtop- -1 = valtopL valtop+1 = 10B B1 MB2 valtop- -2 = max(valtop- -2, valtop) M valtop+1 = valtop- -1B B1 sub NB2 B1.ps =B.ps

58、; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N N.s = shrink(N.i) B text B.ht = text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式 代代 码码 段段S LB valtop- -1 = valtopL valtop+1 = 10B B1 MB2 valtop- -2 = max(valtop- -2, valtop) M valtop+1 = valtop- -1B B1 sub NB2 valtop- -3 = disp (valtop- -3, valtop )N N.s = shrink(N.i) B text B.ht = text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式 代代 码码 段段S LB valtop- -1 = valt