【教学课件】第六章语法制导翻译与属性文法.ppt

第六章 语法制导翻译与属性文法,School of Computer Science&Technology Harbin Institute of Technology,重点：语法制导翻译的基本思想，语法制导定义，翻译模式，自顶向下翻译，自底向上翻译。难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。,2023/8/7,2,第6章语法制导翻译与属性文法,6.1 语法制导翻译概述6.2 语法制导定义6.3 属性计算6.4 翻译模式6.5 本章小结,2023/8/7,3,为什么进行词法和语法分析？用A进行归约表达的是什么意思？看：operand+term EE1+TE1的值+T的值的结果作为E的值即：取来E1的值和T的值做加法运算，结果作为E的值E.val=E1.val+T.val,问题,2023/8/7,4,6.1 语法制导翻译概述,为了提高编译程序的可移植性，一般将编译程序划分为前端和后端。前端通常包括词法分析、语法分析、语义分析、中间代码生成、符号表的建立，以及与机器无关的中间代码优化等，它们的实现一般不依赖于具体的目标机器。后端通常包括与机器有关的代码优化、目标代码的生成、相关的错误处理以及符号表的访问等。,图6.1 编译器前端的逻辑结构,2023/8/7,5,6.1 语法制导翻译概述,语义分析器的主要任务是检查各个语法结构的静态语义，称为静态语义分析或静态检查 类型检查：操作数和操作符的类型是否相容；控制流检查：控制流转向的目标地址是否合法；惟一性检查：对象是否被重复定义；关联名检查：同一名字的多次特定出现是否一致。将静态检查和中间代码生成结合到语法分析中进行的技术称为语法制导翻译。,2023/8/7,6,6.1 语法制导翻译概述,语法制导翻译的基本思想在进行语法分析的同时，完成相应的语义处理。也就是说，一旦语法分析器识别出一个语法结构就要立即对其进行翻译，翻译是根据语言的语义进行的，并通过调用事先为该语法结构编写的语义子程序来实现。对文法中的每个产生式附加一个/多个语义动作(或语义子程序)，在语法分析的过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作(或调用相应的语义子程序)。,2023/8/7,7,6.1 语法制导翻译概述,语义子程序的功能指明相应产生式中各个文法符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义动作(如传送或处理语义信息、查填符号表、计算值、生成中间代码等)。语义信息的获取和加工是和语法分析同时进行的，而且这些语义信息是通过文法符号来携带和传递的。,2023/8/7,8,6.1 语法制导翻译概述,一个文法符号X所携带的语义信息称为X的语义属性，简称为属性，它是根据翻译的需要设置的(对应分析树结点的数据结构)，主要用于描述语法结构的语义。一个变量的属性有类型、层次、存储地址等表达式的属性有类型、值等。,2023/8/7,9,6.1 语法制导翻译概述,属性值的计算和产生式相关联，随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。EE1+E2E.val:=E1.val+E2.val语法结构具有规定的语义问题：如何根据被识别出的语法成分进行语义处理？亦即怎样将属性值的计算及翻译工作同产生式相关联？,2023/8/7,10,典型处理方法一,语法制导定义通过将属性与文法符号关联、将语义规则与产生式关联来描述语言结构的翻译方案 对应每一个产生式编写一个语义子程序，当一个产生式获得匹配时，就调用相应的语义子程序来实现语义检查与翻译EE1+TE.val:=E1.val+T.valTT1*FT.val:=T1.val*F.valF digitF.val:=digit.lexval适宜在完成归约的时候进行,2023/8/7,11,典型处理方法二,翻译模式通过将属性与文法符号关联，并将语义规则插入到产生式的右部来描述语言结构的翻译方案 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作D T L.inh:=T.type LT int T.type:=integer T real T.type:=real L L1.inh:=L.inh L1,idaddtype(id.entry,L.inh)L idaddtype(id.entry,L.inh)适宜在进行推导时完成,2023/8/7,12,6.2 语法制导定义,语法制导定义是附带有属性和语义规则的上下文无关文法属性是与文法符号相关联的语义信息 语义规则是与产生式相关联的语义动作 语法制导定义是基于语言结构的语义要求设计的，类似于程序设计，语法制导定义中的属性类似于程序中用到的数据结构，用于描述语义信息，语义规则类似于计算，用于收集、传递和计算语义信息的。属性通常被保存在分析树的相关节点中,2023/8/7,13,概念术语,综合属性：节点的属性值是通过分析树中该节点或其子节点的属性值计算出来的继承属性：节点的属性值是由该节点、该节点的兄弟节点或父节点的属性值计算出来的固有属性：通过词法分析直接得到的属性 依赖图：描述属性之间依赖关系的图，根据语义规则来构造注释分析树：节点带有属性值的分析树,2023/8/7,14,语法制导定义的形式,在一个语法制导定义中，AP都有与之相关联的一套语义规则，规则形式为 b：=f（c1，c2，ck），f是一个函数，而且或者 1b是A的一个综合属性并且c1，c2，ck是中的符号的属性，或者 2b是中某个符号的一个继承属性并且c1，c2，ck是A或中的任何文法符号的属性。这两种情况下，都说属性b依赖于属性c1，c2，ck,2023/8/7,15,例6.1 台式计算器的语法制导定义,产生式 语义规则LEn print(Eval)(可看作是L的虚属性)E E1+T Eval:=E1val+TvalE T Eval:=TvalT T1*F Tval:=T1val+FvalT F Tval:=FvalF(E)Fval:=EvalF digit Fval:=digitlexval,2023/8/7,16,S-属性定义,只含综合属性的语法制导定义称为S-属性定义对于S-属性定义，通常使用自底向上的分析方法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式的S-属性定义计算属性的值，从叶结点到根结点进行计算。没有副作用的语法制导定义有时又称为属性文法，属性文法的语义规则单纯根据常数和其它属性的值来定义某个属性的值,2023/8/7,17,继承属性,当分析树的结构同源代码的抽象语法不“匹配”时，继承属性将非常有用。下面的例子可以说明怎样用继承属性来解决这种不匹配问题，产生这种不匹配的原因是因为文法通常是为语法分析而不是为翻译设计的。例6.2 考虑如何在自顶向下的分析过程中计算3*5和4*8*9这样的表达式项消除左递归之后的算数表达式文法的一个子集：TFT T*FT1 T Fdigit,2023/8/7,18,表6.3 为适于自顶向下分析的文法设计的语法制导定义,2023/8/7,19,4*8*9的注释分析树,2023/8/7,20,表6.3中语法制导定义对应的翻译模式,如果对4*8*9进行自顶向下的语法制导翻译，则val的值的计算顺序为根据上述对val值的计算顺序，可以将表6.3中的语法制导定义转换成如下的翻译模式 TFT.inh:=F.valT T.val:=T.synT*FT1.inh:=T.inhF.valT1T.syn:=T1.synT T.syn:=T.inhFdigitF.val:=digit.lexval,2023/8/7,21,6.3 属性计算,语义规则定义了属性之间的依赖关系，这种依赖关系将影响属性的计算顺序为了确定分析树中各个属性的计算顺序，我们可以用图来表示属性之间的依赖关系，并将其称为依赖图如果依赖图中没有回路，则利用它可以很方便地求出属性的计算顺序。注释分析树只是给出了属性的值，而依赖图则可以帮助我们确定如何将这些属性值计算出来。,2023/8/7,22,6.3.1 依赖图,所谓依赖图其实就是一个有向图，用于描述分析树中节点的属性和属性间的相互依赖关系，称为分析树的依赖图。每个属性对应依赖图中的一个节点，如果属性b依赖于属性c，则从属性c的节点有一条有向边指向属性b的节点。属性间的依赖关系是根据相应的语义规则确定的。,2023/8/7,23,依赖图的构造方法,for分析树的每个节点n dofor与节点n对应的文法符号的每个属性a do在依赖图中为a构造一个节点；for 分析树的每个节点n dofor 节点n所用产生式对应的每条语义规则b:=f(c1,c2,ck)dofor i:=1 to k do构造一条从节点ci到节点b的有向边；,2023/8/7,24,例6.3 图6.3中注释分析树的依赖图,2023/8/7,25,6.3.2 属性的计算顺序,拓扑排序一个无环有向图的拓扑排序是图中结点的任何顺序m1，m2，mk，使得边必须是从序列中前面的结点指向后面的结点，也就是说，如果mimj是mi到mj的一条边,那么在 序列中mi必须出现在mj的前面。若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。例6.4 图6.4的拓扑排序为：1，2，3，4，5，6，7，8，9，10，11，12，13,2023/8/7,26,6.3.2 属性的计算顺序,根据拓扑排序得到的翻译程序a4:=4 a5:=a4 a6:=8a7:=a5a6 a8:=9 a9:=a7a8a10:=a9 a11:=a10 a12:=a11a13:=a12上述属性计算方法又称为分析树法，这种方法在编译时需要显式地构造分析树和依赖图，所以编译的时空效率比较低，而且如果分析树的依赖图中存在回路的话，这种方法将会失效。这种方法的优点是可以多次遍历分析树，从而使得属性的计算不依赖于所采用的语法分析方法以及属性间严格的依赖关系。,2023/8/7,27,计算语义规则的其他方法,基于规则的方法 在构造编译器时，用手工或专门的工具来分析语义规则,确定属性值的计算顺序。忽略语义规则的方法 在分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。这种方法限制了能被实现的语法制导定义的种类。这两种方法都不必显式构造依赖图，因此时空效率更高。,2023/8/7,28,S-属性定义,定义6.1 只含综合属性的语法制导定义称为S-属性定义，又称为S-属性文法。如果某个语法制导定义是S-属性定义，则可以按照自下而上的顺序来计算分析树中节点的属性。一种简单的属性计算方法是对分析树进行后根遍历，并在最后一次遍历节点N时计算与节点N相关联的属性。postorder(N)for N的每个子节点M(从左到右)postorder(M);计算与节点N相关联的属性;,2023/8/7,29,L-属性定义,定义6.2 一个语法制导定义被称为L-属性定义，当且仅当它的每个属性或者是综合属性，或者是满足如下条件的继承属性：设有产生式AX1X2Xn，其右部符号Xi(1in)的继承属性只依赖于下列属性：A的继承属性；产生式中Xi左边的符号X1、X2、Xi-1的综合属性或继承属性；Xi本身的综合属性或继承属性，但前提是Xi的属性不能在依赖图中形成回路。L-属性定义又称为L-属性文法。,2023/8/7,30,表6.3 L-属性定义示例,2023/8/7,31,例6.7 不是L-属性定义的语法制导定义,语义规则B.inh:=f(C.c,A.syn)定义了一个继承属性，所以整个语法制导定义就不是S-属性定义了。此外，虽然这条语义规则是合法的属性定义规则，但不满足L-属性定义的要求。这是因为：属性B.inh的定义中用到了属性C.c，而C在产生式的右部处在B的右边。虽然在L-属性定义中可以使用兄弟节点的属性来定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因此，该语法制导定义也不是L-属性定义。,2023/8/7,32,L-属性定义中的属性计算,visit(N)for N的每个子节点M(从左到右)计算节点M的继承属性;visit(M);计算节点N的综合属性;,2023/8/7,33,抽象语法树是表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式，也称作语法结构树，或结构树。语法树是常用的一种中间表示形式。把语法分析和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：1.适于语法分析的文法可能不完全反映语言成分的自然层次结构；2.由于语法分析方法的限制，对分析树结点的访问顺序和翻译需要的访问顺序不一致。,6.3.5 属性计算示例抽象语法树的构造,2023/8/7,34,产生式Sif B then S1 else S2的语法树 if-then-else|B S1 S2 赋值语句的语法树 assignment variable expression 在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。,语法树,2023/8/7,35,构造表达式的语法树使用的函数 1.mknode(op,left,right)建立一个标记为op的运算符结点，两个域left和right分别是指向左右运算对象的指针。2mkleaf(id,entry)建立一个标记为id的标识符结点，其域entry是指向该标识符在符号表中相应表项的指针。3.mkleaf(num,val)建立一个标记为num的数结点，其域val用于保存该数的值。,构造表达式的语法树,2023/8/7,36,构造表达式语法树的语法制导定义,2023/8/7,37,图6.5 3*x/y的语法树的构造,2023/8/7,38,3*x/y的抽象语法树的构造步骤,p1:=mkleaf(num,3)；p2:=mkleaf(id,entry-x)；p3:=mknode(*,p1,p2)；p4:=mkleaf(id,entry-y)；p5:=mknode(/,p3,p4)；,图6.5的语法树是自底向上构造的，对于那些为便于进行自顶向下分析而设计的文法来说，使用同样的步骤照样可以建立图6.5中的抽象语法树。当然，分析树的结构可能大不相同，而且可能需要引入继承属性来传递语义信息。,2023/8/7,39,在自顶向下分析过程中构造语法树,2023/8/7,40,根据表6.6的语法制导定义构造的语法树,2023/8/7,41,定义 翻译模式是语法制导定义的一种便于实现的书写形式。其中属性与文法符号相关联，语义规则或语义动作用花括号 括起来，并可被插入到产生式右部的任何合适的位置上。这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,6.4 翻译模式,2023/8/7,42,将中缀表达式翻译成后缀表达式：ETR Raddop T print(addop.lexeme)R1|Tnumprint(num.val)把语义动作看成终结符号，输入3+4-5,其分析树如图6.8，当按深度优先遍历它，执行遍历中访问的语义动作，将输出 3 4+5-它是输入表达式3+4-5的后缀式。,例6.10 一个简单的翻译模式,2023/8/7,43,图6.8 3+4-5的带语义动作的分析树,2023/8/7,44,前提语法制导定义是L-属性定义 保证语义动作不会引用还没计算出来的属性值1.只需要综合属性的情况 为每一个语义规则建立一个包含赋值的动作，并把该动作放在相应的产生式右部的末尾。例如：TT1*F Tval:=T1val*Fval 转换成：TT1*FTval:=T1val*Fval,翻译模式的设计 根据语法制导定义,2023/8/7,45,2.既有综合属性又有继承属性 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。一个动作不能引用这个动作右边符号的综合属性。产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,翻译模式的设计 根据语法制导定义,2023/8/7,46,下面的翻译模式不满足要求：SA1A2 A1in:=1;A2in:=2 A a print(Ain)/*A.in尚无定义*/例6.11 从L-属性制导定义建立一个满足上面 要求的翻译模式。使用文法产生的语言是数学排版语言EQN E sub 1val编排结果,2023/8/7,47,B表示盒子 BB1B2代表两个相邻盒子的并列，且B1位于B2的左边。BB1 sub B2代表盒子B1后随下标盒子B2，下标盒子 B2以较小的字体和较低的位置出现。B(B1)代表一个由括号括起来的盒子B1，主要是为了对多个盒子或下标进行分组。在EQN中，使用花括号进行分组，此处使用圆括号是为了避免跟语义动作外面的花括号产生冲突。Btext代表文本字符串，即任意字符组成的串。该文法是二义性的文法，将“并列”和“下标”看成是左结合的，并令“下标”的优先级高于“并列”的话，则可以对该文法所描述的语言进行自底向上的语法分析。,2023/8/7,48,属性设置 point size用于表示盒子中文本的尺寸(以点来计算，也就是字号)。如果标准盒子的尺寸为p，则下标盒子的尺寸为0.7p。属性B.ps表示盒子B的尺寸，该属性是继承属性。每个盒子都有一个基线(baseline)，用来表示每个文本底部的垂直位置。height用来表示从盒子的顶部到基线的距离。属性B.ht表示盒子B的高度height，该属性是综合属性。depth用来表示从基线到盒子底部的距离。用属性B.dp表示盒子B的深度depth，该属性也是综合属性。,2023/8/7,49,表6.7 对盒子进行排版的语法制导定义,2023/8/7,50,SB.ps:=10B S.ht:=B.ht;S.dp:=B.dpBB1.ps:=B.psB1B2.ps:=B.ps B2B.ht:=max(B1.ht,B2.ht)BB1.ps:=B.psB1subB2.ps:=0.7B.ps B2B.ht:=max(B1.ht,B2.ht-0.25B.ps);B.dp:=max(B1.dp,B2.dp+0.25B.ps);B(B1.ps:=B.psB1)B.ht:=B1.ht;B.dp:=B1.dp;BtextB.ht:=getheight(B.ps,text.lexval);B.dp:=getdepth(B.ps,text.lexval),从表6.7构造的翻译模式,2023/8/7,51,T F T.inh:=F.nodeT T.node:=T.synT*F T1.inh:=mknode(*,T.inh,F.node)T1T.syn:=T1.synT/F T1.inh:=mknode(/,T.inh,F.node)T1T.syn:=T1.synT T.syn:=T.inhF(E)F.node:=E.nodeF id F.node:=mkleaf(id,id.entry)F num F.node:=mkleaf(num,num.val),从表6.6构造的翻译模式,2023/8/7,52,在分析栈中使用一个附加的域来存放综合属性值。下图为一个带有综合属性值域的分析栈：,stack,val,.,X,X.x,Y,.,Y.y,.,.,Z,Z.z,top,6.4.2 S-属性定义的自底向上计算,2023/8/7,53,A b:=f(c1,c2,ck)b是A的综合属性，ci(1 ik)是中符号的属性。综合属性的值是在自底向上的分析过程中，每次归约之前进行计算的。AXYZ Aa:=f(Xx,Yy,Zz),Aa,Xx Yy Zz,2023/8/7,54,top,stack,val,.,.,X,X.x,Y,Y.y,Z,Z.z,stack,val,.,.,A,A.a,top,实现时，将定义式 A.a:=f(X.x,Y.y,Z.z)(抽象)变成stackntop.val:=f(stacktop-2.val,stacktop-1.val,stacktop.val)(具体可执行代码)。在执行代码段之前执行：ntop:=top-r+1 r是句柄的长度执行代码段后执行：top:=ntop;,2023/8/7,55,例6.14 用LR分析器实现台式计算器与表6.2对比,LEnprint(stacktop-1.val);top:=top-1;EE1+Tstacktop-2.val:=stacktop-2.val+stacktop.val;top:=top-2;ETTT1*Fstacktop-2.val:=stacktop-2.val stacktop.val;top:=top-2;TFF(E)stacktop-2.val:=stacktop-1.val;top:=top-2;Fdigit,2023/8/7,56,表6.8 翻译输入6+7*8n上的移动序列,输入 state val 使用的产生式,6+7*8n-,+7*8n 6 6,+7*8n F 6 Fdigit,+7*8n T 6 TF,+7*8n E 6 ET,7*8n E+6+,*8n E+7 6+7,2023/8/7,57,*8n E+F 6+7 F digit,*8n E+T 6+7 T F,8n E+T*6+7*,n E+T*8 6+7*8,n E+T*F 6+7*8 F digit,n E+T 6+56 TT*F,n E 62 E E+T,En 62,L 62 L En,2023/8/7,58,采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。,S-属性定义小结,2023/8/7,59,用翻译模式构造自顶向下的翻译。1.从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基础文法时考虑属性值的计算。对于自顶向下语法分析，假设语义动作是在与之处于同一位置的文法非终结符被展开时执行的，而且不考虑继承属性的处理（很简单）。,6.4.3 L-属性定义的自顶向下翻译,2023/8/7,60,例6.15 考虑如下将中缀表达式翻译为后缀表达式的翻译模式中的两个产生式：E E1+T print(+);E TE TRR+T print(+);RR,只有简单语义动作时的左递归消除,2023/8/7,61,设有如下左递归翻译模式：AA1YA.a:=g(A1.a,Y.y)AX A.a:=f(X.x)假设每个非终结符都有一个综合属性，用相应的小写字母表示，g和f是任意函数。消除左递归后，文法转换成 AX R RY R|,S-属性定义的左递归消除,2023/8/7,62,再考虑语义动作，翻译模式变为：AX Ri:=f(Xx)R Aa:=Rs RY R1i:=g(Ri,Yy)R1 Rs:=R1s R Rs:=Ri 经过转换的翻译模式使用R的继承属性i和综合属性s。转换前后的结果是一样的,为什么？,S-属性定义的左递归消除,AA1Y A.a:=g(A1.a,Y.y)AX A.a:=f(X.x),引入继承属性R.i来收集应用函数g的计算结果。其初始值为A.a:=f(X.x）,引入综合属性R.s在R结束生成Y时复制R.i的值。,2023/8/7,63,Aa=g(g(f(Xx),Y1y),Y2y),Aa=g(f(Xx),Y1y),Aa=f(Xx),Y2,Y1,X,(a),输入：XY1Y2,2023/8/7,64,A,Ri=f(Xx),Ri=g(f(Xx),Y1y),Ri=g(g(f(Xx),Y1y),Y2y),Y2,Y1,X,(b),2023/8/7,65,L-属性定义的递归下降翻译器的构造：1对每个非终结符A构造一个函数A，将非终结符A的各个继承属性当作函数A的形式参数，而将非终结符A的综合属性集当作函数A的返回值，为了便于讨论，假设每个非终结符只具有一个综合属性。2在函数A的过程体中，不仅要进行语法分析，而且要处理相应的语义属性。函数A的代码首先根据当前输入确定用哪个产生式展开A，然后按照3中所给的方法对各产生式进行编码。,2.L-属性定义的递归下降翻译法,2023/8/7,66,3与每个产生式对应的程序代码的工作过程为：按照从左到右的次序，依次对产生式右部的记号、非终结符和语义动作执行如下的动作：1)对带有综合属性x的符号X，将x的值保存在X.x中，并生成一个函数调用来匹配X，然后继续读入下一个输入符号；2)对非终结符B，生成一个右部带有函数调用的赋值语句c:=B(b1,b2,bk)，其中，b1,b2,bk是代表B的继承属性的变量，c是代表B的综合属性的变量；3)对于语义动作，将其代码复制到语法分析器中，并将对属性的引用改为对相应变量的引用。,2.L-属性定义的递归下降翻译法,2023/8/7,67,例 6.16 function T:syntax_tree_node;function T(inh:syntax_tree_node):syntax_tree_node;function F:syntax_tree_node;function T:syntax_tree_node;var node,syn:syntax_tree_node;beginnode:=F;syn:=T(node);return syn end;,2023/8/7,68,function T(inh:syntax_tree_node):syntax_tree_node;var node,inh1,syn1:syntax_tree_node;oplexeme:char;beginif lookahead=*then begin/*匹配产生式T*FT*/oplexeme:=lexval;match(*);node:=F;inh1:=mknode(*,inh,node);syn1:=T(inh1);syn:=syn1endelse if lookahead=/then begin/*匹配产生式T/FT*/oplexeme:=lexval;match(/);node:=F;inh1:=mknode(/,inh,node);syn1:=T(inh1);syn:=syn1end else syn:=inh;return syn end;,2023/8/7,69,function F:syntax_tree_node;var node:syntax_tree_node;begin if lookahead=(then begin/*匹配产生式F(E)*/match();node:=E;match()endelse if lookahead=id then begin/*匹配产生式F id*/match(id);node:=mkleaf(id,id.entry)endelse if lookahead=num then begin/*匹配产生式F num*/match(num);node:=mkleaf(num,num.val)end return node end;,2023/8/7,70,3.L-属性定义的LL(1)翻译法,预先在源文法中的相应位置上嵌入语义动作符号(每个对应一个语义子程序)，用于提示语法分析程序，当分析到达这些位置时应调用相应的语义子程序。带有语义动作符号的文法又叫翻译文法。,2023/8/7,71,3.L-属性定义的LL(1)翻译法,与递归子程序法的区别与联系都是在扫描过程中进行产生式的推导，同时在适当的地方加入语义动作。递归子程序法将语义动作溶入分析程序；LL(1)分析法则由语义子程序完成相应的翻译。递归子程序法隐式地使用语义栈；LL(1)分析法则用显式的语义栈（程序自身控制对栈的操作）。注：语义与语法栈不同步。,2023/8/7,72,例6.17,对于图6.14的翻译模式，设置两个栈，一个是分析栈，一个是语义栈。TFe1T e2 T*Fe3T1e4 T/Fe5T1e4 T e6 F(E)e7 Fide8 Fnume9,2023/8/7,73,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,1.初始化,T,2023/8/7,74,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,2.选产生式的右部进栈,e2,e1,F,T,2023/8/7,75,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,3.选择产生式,num3不进栈，调用e9，调用e9后，叶结点F.node被压入语义栈,e2,e1,e9,T,F.node,2023/8/7,76,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,4.执行动作e1，F.node出栈，T.inh被压入栈,e2,e1,T,T.inh,2023/8/7,77,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,5.选择产生式,*不进栈,e2,T,e5,e4,F,T.inh,2023/8/7,78,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,6.选择产生式,idx不进栈，调用e8，调用e8后，叶结点F.node被压入语义栈,e2,T,e5,e4,T.inh,F.node,e8,2023/8/7,79,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,7.执行动作e5，F.node和T.inh均被弹出栈，新的T.inh被压入栈,T.inh,e2,T,e5,e4,2023/8/7,80,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,8.选择产生式,/不进栈,T.inh,e2,e4,T,e4,e3,F,2023/8/7,81,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,9.选择产生式,idy不进栈，调用e8，调用e8后，叶结点F.node被压入语义栈,T.inh,F.node,e2,e4,T,e4,e3,e8,2023/8/7,82,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,10.执行动作e3，F.node和T.inh均被弹出栈，新的T.inh被压入栈,T.inh,e2,e4,T,e4,e3,2023/8/7,83,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,11.选择产生式，T.inh被弹出栈，T.syn被压入栈,e2,e4,e6,e4,T.inh,2023/8/7,84,-,#,语义栈,语法栈,3*x/y#,输入串,例6.17 对输入串3*x/y的翻译,语法分析动作和语义操作,12.依次执行动作e6,e4,e4,e2,最终语义栈中只有T.node,代表3*x/y的语法树的根结点,T.node,2023/8/7,85,6.4.4 L-属性定义的自底向上翻译,在自底向上分析的框架中实现L属性定义的方法它能实现任何基于LL(1)文法的L属性定义。也能实现许多（但不是所有的）基于LR(1)文法的L属性定义。,2023/8/7,86,6.4.4 L-属性定义的自底向上翻译(续),首先像6.4.1所介绍的那样构造翻译模式，它将计算继承属性的动作嵌入在非终结符的前面，而将计算综合属性的动作放在产生式的末尾。在每个嵌入动作处引入一个标记性非终结符(marker nonterminals)。不同位置所对应的标记是不同的，每个标记性非终结符M都有一个形如M的产生式。,2023/8/7,87,6.4.4 L-属性定义的自底向上翻译(续),如果标记性非终结符M取代了某个产生式Aa中的动作a，则按如下方式将a修改为a，并将动作a放在产生式M的末尾。为M设置继承属性来复制动作a所需要的A或中符号的继承属性；以与动作a相同的方式计算属性，只不过要将这些属性置为M的综合属性。,2023/8/7,88,6.4.4 L-属性定义的自底向上翻译(续),与M相关联的语义动作可能需要用到没出现在该产生式中的文法符号的属性。不过，由于要在LR分析栈中实现所有的语义动作，所以在分析栈中M下面的某个已知位置总能找到所需的属性。例如，假设在某个LL(1)文法中有一个形如ABC的产生式，B的继承属性B.inh是从A的继承属性A.inh按照公式B.inh:=f(A.inh)来计算的，亦即翻译模式可能包含如下片断：AB.inh:=f(A.inh);BC,2023/8/7,89,6.4.4 L-属性定义的自底向上翻译(续),根据上面的论述，为了在自底向上的分析过程中计算B.inh:=f(A.inh)，需要引入一个标记性非终结符M，并为其设置一个继承属性M.inh用来复制A的继承属性，而且还要用M的综合属性M.syn代替B.inh，于是，该翻译模式片段将被修改为如下形式：AMBCM M.inh:=A.inh;M.syn:=f(M.inh),2023/8/7,90,6.4.4 L-属性定义的自底向上翻译(续),注意，执行M的语义规则时，A.inh是不可用的，但实际上，实现时会把每个非终结符X的继承属性都放在堆栈中紧靠在X将被归约出来的位置之下。于是，当将归约为M时，A.inh恰好就在它的下面。随M保存在栈中的M.syn的值，也就是B.inh的值，亦将被放在紧靠在B将被归约出来的位置之下，需要的时候同样是可用的。,2023/8/7,91,6.4.4 L-属性定义的自底向上翻译(续),下面的化简可以减少标记性非终结符的个数，其中第2条还可以避免左递归文法中的分析冲突：如果Xj没有继承属性，则不需要使用标记Mj。当然，如果省略了Mj，属性在栈中的预期位置就会改变，但是分析器可以很容易地适应这种变化。如果X1.inh存在，但它是由复制规则X1.inh:=A.inh计算的，此时可以省略M1。因为A.inh存放在栈中紧挨在X1下面的地方，所以该值也可同时作为X1.inh的值。,2023/8/7,92,6.4.4 L-属性定义的自底向上翻译(续),例6.18 数学排版语言EQN S B.ps:=10 BS.ht:=B.ht;S.dp:=B.dp B B1.ps:=B.ps B1B2.ps:=B.ps B2B.ht:=max(B1.ht,B2.ht)B B1.ps:=B.ps B1sub B2.ps:=0.7B.ps B2B.ht:=disp(B1.ht,B2.ht)B.dp:=max(B1.dp,B2.dp)B textB.ht:=getheight(B.ps,text.lexval);B.dp:=getdepth(B.ps,text.lexval),保证在B的子树被归约时，B.ps的值出现在分析栈中的已知位置,归约B1之前，B.ps可以在栈中找到，所以B1.ps:=B.ps 可以省略。但归约B2之前，无法确定其前有几个B1，因此，无法预测B.ps在栈中的位置。,2023/8/7,93,6.4.4 L-属性定义的自底向上翻译(续),由于存在一个继承属性和两个综合属性，所以语义栈val需要被扩展为val1、val2和val3val1用于保存继承属性ps的值val2和val3分别用于保存综合属性ht和dp的值假设分析栈仍为stacktop和ntop分别是归约前和归约后栈顶的下标。,2023/8/7,94,6.4.4 L-属性定义的自底向上翻译(续),2023/8/7,9