六章语法制导翻译与属文法Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望2024/7/192第第6章章语法制导翻译与属性文法语法制导翻译与属性文法 6.1语法制导翻译概述语法制导翻译概述6.2语法制导定义语法制导定义6.3属性计算属性计算6.4翻译模式翻译模式6.5本章小结本章小结2024/7/193n为什么进行词法和语法分析？为什么进行词法和语法分析？n用用A进行归约表达的是什么意思？进行归约表达的是什么意思？n看：看：operand+termnEE1+TnE1的值的值+T的值的结果作为的值的结果作为E的值的值即：取来即：取来E1的值和的值和T的值做加法运算，结果作为的值做加法运算，结果作为E的值的值E.val=E1.val+T.val问题2024/7/1946.1语法制导翻译概述语法制导翻译概述n为了提高编译程序的可移植性，一般将编译程为了提高编译程序的可移植性，一般将编译程序划分为前端和后端。序划分为前端和后端。n前端通常包括词法分析、语法分析、语义分析、中前端通常包括词法分析、语法分析、语义分析、中间代码生成、符号表的建立，以及与机器无关的中间代码生成、符号表的建立，以及与机器无关的中间代码优化等，它们的实现一般不依赖于具体的目间代码优化等，它们的实现一般不依赖于具体的目标机器。标机器。n后端通常包括与机器有关的代码优化、目标代码的后端通常包括与机器有关的代码优化、目标代码的生成、相关的错误处理以及符号表的访问等。生成、相关的错误处理以及符号表的访问等。图图6.1编译器前端的逻辑结构编译器前端的逻辑结构2024/7/1956.1语法制导翻译概述语法制导翻译概述n语义分析器的主要任务是检查各个语法结构的语义分析器的主要任务是检查各个语法结构的静态语义静态语义 ，称为静态语义分析或静态检查，称为静态语义分析或静态检查 n类型检查：操作数和操作符的类型是否相容；类型检查：操作数和操作符的类型是否相容；n控制流检查：控制流转向的目标地址是否合法；控制流检查：控制流转向的目标地址是否合法；n惟一性检查：对象是否被重复定义；惟一性检查：对象是否被重复定义；n关联名检查：同一名字的多次特定出现是否一致。关联名检查：同一名字的多次特定出现是否一致。 n将静态检查和中间代码生成结合到语法分析中将静态检查和中间代码生成结合到语法分析中进行的技术称为进行的技术称为语法制导翻译语法制导翻译 。2024/7/1966.1语法制导翻译概述语法制导翻译概述n语法制导翻译的基本思想语法制导翻译的基本思想n在进行语法分析的同时，完成相应的语义处理。也在进行语法分析的同时，完成相应的语义处理。也就是说，一旦语法分析器识别出一个语法结构就要就是说，一旦语法分析器识别出一个语法结构就要立即对其进行翻译，翻译是根据语言的语义进行的，立即对其进行翻译，翻译是根据语言的语义进行的，并通过调用事先为该语法结构编写的语义子程序来并通过调用事先为该语法结构编写的语义子程序来实现。实现。n对文法中的每个产生式附加一个对文法中的每个产生式附加一个/多个语义动作多个语义动作(或或语义子程序语义子程序)，在语法分析的过程中，每当需要使用，在语法分析的过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动行相应的语法分析动作外，还要执行相应的语义动作作(或调用相应的语义子程序或调用相应的语义子程序)。2024/7/1976.1语法制导翻译概述语法制导翻译概述n语义子程序的功能语义子程序的功能n指明相应产生式中各个文法符号的具体含义，并指明相应产生式中各个文法符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义规定了使用该产生式进行分析时所应采取的语义动作动作(如传送或处理语义信息、查填符号表、计算如传送或处理语义信息、查填符号表、计算值、生成中间代码等值、生成中间代码等)。n语义信息的获取和加工是和语法分析同时进行的，语义信息的获取和加工是和语法分析同时进行的，而且这些语义信息是通过文法符号来携带和传递而且这些语义信息是通过文法符号来携带和传递的。的。2024/7/1986.1语法制导翻译概述语法制导翻译概述n一个文法符号一个文法符号X所携带的语义信息称为所携带的语义信息称为X的语的语义属性，简称为属性，它是根据翻译的需要设义属性，简称为属性，它是根据翻译的需要设置的置的(对应分析树结点的数据结构对应分析树结点的数据结构)，主要用于，主要用于描述语法结构的语义。描述语法结构的语义。n一个变量的属性有类型、层次、存储地址等一个变量的属性有类型、层次、存储地址等n表达式的属性有类型、值等。表达式的属性有类型、值等。2024/7/1996.1语法制导翻译概述语法制导翻译概述n属性值的计算和产生式相关联，随着语法属性值的计算和产生式相关联，随着语法分析的进行，执行属性值的计算，完成语分析的进行，执行属性值的计算，完成语义分析和翻译的任务。义分析和翻译的任务。nEE1+E2E.val:=E1.val+E2.valn语法结构具有规定的语义语法结构具有规定的语义n问题：如何根据被识别出的语法成分进行问题：如何根据被识别出的语法成分进行语义处理？语义处理？n亦即怎样亦即怎样将属性值的计算及翻译工作同产生式将属性值的计算及翻译工作同产生式相关联？相关联？2024/7/1910典型处理方法一典型处理方法一n语法制导定义语法制导定义n通过将属性与文法符号关联、将语义规则与产生通过将属性与文法符号关联、将语义规则与产生式关联来描述语言结构的翻译方案式关联来描述语言结构的翻译方案n对应每一个产生式编写一个语义子程序，当一个对应每一个产生式编写一个语义子程序，当一个产生式获得匹配时，就调用相应的语义子程序来产生式获得匹配时，就调用相应的语义子程序来实现语义检查与翻译实现语义检查与翻译nEE1+TE.val:=E1.val+T.valnTT1*FT.val:=T1.val*F.valnF digitF.val:=digit.lexvaln适宜在完成归约的时候进行适宜在完成归约的时候进行2024/7/1911典型处理方法二典型处理方法二n翻译模式翻译模式n通过将属性与文法符号关联，并将语义规则插入到产生式通过将属性与文法符号关联，并将语义规则插入到产生式的右部来描述语言结构的翻译方案的右部来描述语言结构的翻译方案n在产生式的右部的适当位置，插入相应的语义动在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作作，按照分析的进程，执行遇到的语义动作nDTL.inh:=T.typeLnTintT.type:=integernTrealT.type:=realnLL1.inh:= L.inhL1,idaddtype(id.entry,L.inh)nLidaddtype(id.entry,L.inh)n适宜在进行推导时完成适宜在进行推导时完成2024/7/19126.2语法制导定义语法制导定义n语法制导定义是附带有属性和语义规则的上下语法制导定义是附带有属性和语义规则的上下文无关文法文无关文法n属性是与文法符号相关联的语义信息属性是与文法符号相关联的语义信息n语义规则是与产生式相关联的语义动作语义规则是与产生式相关联的语义动作n语法制导定义是基于语言结构的语义要求设计语法制导定义是基于语言结构的语义要求设计的，类似于程序设计，语法制导定义中的属的，类似于程序设计，语法制导定义中的属性类似于程序中用到的数据结构，用于描述性类似于程序中用到的数据结构，用于描述语义信息，语义规则类似于计算，用于收集、语义信息，语义规则类似于计算，用于收集、传递和计算语义信息的。传递和计算语义信息的。n属性通常被保存在分析树的相关节点中属性通常被保存在分析树的相关节点中2024/7/1913概念术语概念术语n综合属性：节点的属性值是通过分析树中该节综合属性：节点的属性值是通过分析树中该节点或其子节点的属性值计算出来的点或其子节点的属性值计算出来的n继承属性：节点的属性值是由该节点、该节点继承属性：节点的属性值是由该节点、该节点的兄弟节点或父节点的属性值计算出来的的兄弟节点或父节点的属性值计算出来的n固有属性：通过词法分析直接得到的属性固有属性：通过词法分析直接得到的属性n依赖图：描述属性之间依赖关系的图，根据语依赖图：描述属性之间依赖关系的图，根据语义规则来构造义规则来构造n注释分析树：节点带有属性值的分析树注释分析树：节点带有属性值的分析树2024/7/1914语法制导定义的形式语法制导定义的形式n在一个在一个语法制导定义语法制导定义中，中， A P都有与之相关联的都有与之相关联的一套语义规则，规则形式为一套语义规则，规则形式为b：=f（c1，c2，ck），），f是一个函数，而且或者是一个函数，而且或者1b是是A的一个综合属性并且的一个综合属性并且c1，c2，ck是是 中的中的符号的属性，或者符号的属性，或者2b是是 中中某个某个符号的一个继承属性并且符号的一个继承属性并且c1，c2，ck是是A或或 中的中的任何文法符号的属性。任何文法符号的属性。这两种情况下，都说属性这两种情况下，都说属性b依赖于属性依赖于属性c1，c2，ck2024/7/1915例例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 := digitlexval2024/7/1916S-属性属性定义定义n只含综合属性的语法制导定义称为只含综合属性的语法制导定义称为S-属性定义属性定义n对于对于S-属性定义，通常使用自底向上的分析方属性定义，通常使用自底向上的分析方法，在建立每一个结点处使用语义规则来计法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式的后，就执行那个产生式的S-属性定义计算属性属性定义计算属性的值，从叶结点到根结点进行计算。的值，从叶结点到根结点进行计算。n没有副作用的语法制导定义有时又称为没有副作用的语法制导定义有时又称为属性文属性文法法，属性文法的语义规则单纯根据常数和其，属性文法的语义规则单纯根据常数和其它属性的值来定义某个属性的值它属性的值来定义某个属性的值2024/7/1917继承属性继承属性n当分析树的结构同源代码的抽象语法不当分析树的结构同源代码的抽象语法不“匹配匹配”时，继承属性将非常有用。下面的例子可时，继承属性将非常有用。下面的例子可以说明怎样用继承属性来解决这种不匹配问以说明怎样用继承属性来解决这种不匹配问题，产生这种不匹配的原因是因为文法通常题，产生这种不匹配的原因是因为文法通常是为语法分析而不是为翻译设计的。是为语法分析而不是为翻译设计的。n例例6.2n考虑如何在自顶向下的分析过程中计算考虑如何在自顶向下的分析过程中计算3*5和和4*8*9这样的表达式项这样的表达式项n消除左递归之后的算数表达式文法的一个子集：消除左递归之后的算数表达式文法的一个子集： TFTT *FT1T Fdigit2024/7/1918表表6.3 为适于自顶向下分析的文法设为适于自顶向下分析的文法设计的语法制导定义计的语法制导定义 产生式语义规则TFT T .inh := F.valT.val:= T .syn T *FT1T1.inh := T .inhF.valT .syn := T1.synT T .syn := T .inhFdigitF.val:=digit.lexval2024/7/19194*8*9的注释分析树的注释分析树2024/7/1920表表6.3中语法制导定义对应的翻译模式中语法制导定义对应的翻译模式n如果对如果对4*8*9进行自顶向下的语法制导翻译，进行自顶向下的语法制导翻译，则则val的值的计算顺序为的值的计算顺序为n根据上述对根据上述对val值的计算顺序值的计算顺序，可以将表可以将表6.3中中的语法制导定义转换成如下的翻译模式的语法制导定义转换成如下的翻译模式nTFT .inh:=F.valTT.val:= T .synnT *FT1.inh:=T .inhF.valT1T .syn := T1.synnT T .syn:=T .inhnFdigitF.val:=digit.lexval2024/7/19216.3属性计算属性计算n语义规则定义了属性之间的依赖关系，这种依语义规则定义了属性之间的依赖关系，这种依赖关系将影响属性的计算顺序赖关系将影响属性的计算顺序n为了确定分析树中各个属性的计算顺序，我们为了确定分析树中各个属性的计算顺序，我们可以用图来表示属性之间的依赖关系，并将可以用图来表示属性之间的依赖关系，并将其称为依赖图其称为依赖图n如果依赖图中没有回路，则利用它可以很方便如果依赖图中没有回路，则利用它可以很方便地求出属性的计算顺序。地求出属性的计算顺序。n注释分析树只是给出了属性的值，而依赖图则注释分析树只是给出了属性的值，而依赖图则可以帮助我们确定如何将这些属性值计算出可以帮助我们确定如何将这些属性值计算出来。来。2024/7/19226.3.1依赖图依赖图n所谓依赖图其实就是一个有向图，用于描述分所谓依赖图其实就是一个有向图，用于描述分析树中节点的属性和属性间的相互依赖关系，析树中节点的属性和属性间的相互依赖关系，称为分析树的依赖图。称为分析树的依赖图。n每个属性对应依赖图中的一个节点，如果属性每个属性对应依赖图中的一个节点，如果属性b依赖于属性依赖于属性c，则从属性，则从属性c的节点有一条有向的节点有一条有向边指向属性边指向属性b的节点。的节点。n属性间的依赖关系是根据相应的语义规则确定属性间的依赖关系是根据相应的语义规则确定的。的。2024/7/1923依赖图的构造方法依赖图的构造方法for分析树的每个节点分析树的每个节点ndofor与节点与节点n对应的文法符号的每个属性对应的文法符号的每个属性ado在依赖图中为在依赖图中为a构造一个节点；构造一个节点；for分析树的每个节点分析树的每个节点ndofor节点节点n所用产生式对应的每条语义规则所用产生式对应的每条语义规则b:=f(c1,c2,ck)dofori:=1tokdo构造一条从节点构造一条从节点ci到节点到节点b的有向边；的有向边；2024/7/1924例例6.3图图6.3中注释分析树的依赖图中注释分析树的依赖图2024/7/19256.3.2属性的计算顺序属性的计算顺序n拓扑排序拓扑排序n一个无环有向图的拓扑排序是图中结点的任何顺一个无环有向图的拓扑排序是图中结点的任何顺序序m1，m2，mk，使得边必须是从序列中前面，使得边必须是从序列中前面的结点指向后面的结点，也就是说，如果的结点指向后面的结点，也就是说，如果mimj是是mi到到mj的一条边的一条边,那么在那么在序列中序列中mi必须出现在必须出现在mj的前面。的前面。n若依赖图中无环，则存在一个拓扑排序，它就是若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。属性值的计算顺序。n例例6.4图图6.4的拓扑排序为：的拓扑排序为：1，2，3，4，5，6，7，8，9，10，11，12，132024/7/19266.3.2属性的计算顺序属性的计算顺序n根据拓扑排序得到的翻译程序根据拓扑排序得到的翻译程序na4:=4a5:=a4a6:=8na7:=a5a6a8:=9a9:=a7a8na10:=a9a11:=a10a12:=a11na13:=a12n上述属性计算方法又称为上述属性计算方法又称为分析树法分析树法，这种方法在编，这种方法在编译时需要显式地构造分析树和依赖图，所以编译的译时需要显式地构造分析树和依赖图，所以编译的时空效率比较低，而且如果分析树的依赖图中存在时空效率比较低，而且如果分析树的依赖图中存在回路的话，这种方法将会失效。回路的话，这种方法将会失效。n这种方法的优点是可以多次遍历分析树，从而使得这种方法的优点是可以多次遍历分析树，从而使得属性的计算不依赖于所采用的语法分析方法以及属属性的计算不依赖于所采用的语法分析方法以及属性间严格的依赖关系。性间严格的依赖关系。2024/7/1927计算语义规则的其他方法计算语义规则的其他方法n基于规则的方法基于规则的方法n在构造编译器时，用手工或专门的工具来分析语在构造编译器时，用手工或专门的工具来分析语义规则义规则,确定属性值的计算顺序。确定属性值的计算顺序。n忽略语义规则的方法忽略语义规则的方法n在分析过程中翻译，那么计算顺序由分析方法来在分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。这种方法限制了确定而表面上与语义规则无关。这种方法限制了能被实现的语法制导定义的种类。能被实现的语法制导定义的种类。n这两种方法都不必显式构造依赖图，因此时这两种方法都不必显式构造依赖图，因此时空效率更高。空效率更高。2024/7/1928S-属性定义属性定义n定义定义6.1只含综合属性的语法制导定义称为只含综合属性的语法制导定义称为S-属性定属性定义，又称为义，又称为S-属性文法。属性文法。n如果某个语法制导定义是如果某个语法制导定义是S-属性定义，则可以按照属性定义，则可以按照自下而上的顺序来计算分析树中节点的属性。自下而上的顺序来计算分析树中节点的属性。n一种简单的属性计算方法是对分析树进行后根遍历，一种简单的属性计算方法是对分析树进行后根遍历，并在最后一次遍历节点并在最后一次遍历节点N时计算与节点时计算与节点N相关联的属相关联的属性。性。npostorder(N)nforN的每个子节点的每个子节点M(从左到右从左到右)postorder(M);n计算与节点计算与节点N相关联的属性相关联的属性;n2024/7/1929L-属性定义属性定义n定义定义6.2一个语法制导定义被称为一个语法制导定义被称为L-属性定义，属性定义，当且仅当它的每个属性或者是综合属性，或当且仅当它的每个属性或者是综合属性，或者是满足如下条件的继承属性：设有产生式者是满足如下条件的继承属性：设有产生式AX1X2Xn，其右部符号，其右部符号Xi(1in)的继承属的继承属性只依赖于下列属性：性只依赖于下列属性：A的继承属性；的继承属性；产生式中产生式中Xi左边的符号左边的符号X1、X2、Xi-1的综合的综合属性或继承属性；属性或继承属性；Xi本身的综合属性或继承属性，但前提是本身的综合属性或继承属性，但前提是Xi的属的属性不能在依赖图中形成回路。性不能在依赖图中形成回路。nL-属性定义又称为属性定义又称为L-属性文法。属性文法。2024/7/1930表表6.3 L-属性属性定义示例定义示例 产生式语义规则TFT T .inh := F.valT.val:= T .syn T *FT1T1.inh := T .inhF.valT .syn := T1.synT T .syn := T .inhFdigitF.val:=digit.lexval2024/7/1931例例6.7不是不是L-属性定义的语法制导定义属性定义的语法制导定义产生式语义规则ABCA.syn := B.bB.inh:=f(C.c, A.syn)语义规则语义规则B.inh:=f(C.c,A.syn)定义了一个继承属性，所以整个定义了一个继承属性，所以整个语法制导定义就不是语法制导定义就不是S-属性定义了。此外，虽然这条语义规则属性定义了。此外，虽然这条语义规则是合法的属性定义规则，但不满足是合法的属性定义规则，但不满足L-属性定义的要求。这是因属性定义的要求。这是因为：属性为：属性B.inh的定义中用到了属性的定义中用到了属性C.c，而，而C在产生式的右部在产生式的右部处在处在B的右边。虽然在的右边。虽然在L-属性定义中可以使用兄弟节点的属性属性定义中可以使用兄弟节点的属性来定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因来定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因此，该语法制导定义也不是此，该语法制导定义也不是L-属性定义。属性定义。2024/7/1932L-属性定义中的属性计算属性定义中的属性计算visit(N)forN的每个子节点的每个子节点M(从左到右从左到右)计算节点计算节点M的继承属性的继承属性; visit(M);计算节点计算节点N的综合属性的综合属性;2024/7/1933抽象语法树抽象语法树是表示程序层次结构的树，它把分析树中是表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式对语义无关紧要的成分去掉，是分析树的抽象形式 ，也称作语法结构树，或结构树。也称作语法结构树，或结构树。 语法树是常用的一种语法树是常用的一种中间表示中间表示形式。形式。 把语法分析和翻译分开。语法分析过程中完成翻译把语法分析和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：有许多优点，但也有一些不足： 1.1.适于语法分析的文法可能不完全反映语言成分的适于语法分析的文法可能不完全反映语言成分的自然层次结构；自然层次结构； 2. 2. 由于语法分析方法的限制，对分析树结点的访由于语法分析方法的限制，对分析树结点的访问顺序和翻译需要的访问顺序不一致。问顺序和翻译需要的访问顺序不一致。 6.3.5属性计算示例属性计算示例抽象语法树的构造抽象语法树的构造 2024/7/1934产生式产生式SifBthenS1elseS2的语法树的语法树if-then-else|BS1S2赋值语句赋值语句的语法树的语法树assignmentvariableexpression在语法树中，运算符号和关键字都不在叶结点，在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。而是在内部结点中出现。语法树语法树2024/7/1935构造表达式的语法树使用的函数构造表达式的语法树使用的函数1.mknode(op,left,right)建立一个标记为建立一个标记为op的运算的运算符结点，两个域符结点，两个域left和和right分别是指向左右运算对象分别是指向左右运算对象的指针。的指针。2mkleaf(id,entry)建立一个标记为建立一个标记为id的标识符结的标识符结点，其域点，其域entry是指向该标识符在符号表中相应表项的是指向该标识符在符号表中相应表项的指针。指针。3.mkleaf(num,val)建立一个标记为建立一个标记为num的数结点，的数结点，其域其域val用于保存该数的值。用于保存该数的值。构造表达式的语法树构造表达式的语法树2024/7/1936构造表达式语法树的语法制导定义构造表达式语法树的语法制导定义产生式语义规则 T T1 * FT.node := mknode(*, T1.node, F.node) T T1 / FT.node := mknode(/, T1.node, F.node) T FT.node := F.node F (E) F.node:= E.node F idF.node := mkleaf(id, id.entry) F numF.node := mkleaf(num, num.val)2024/7/1937图图6.53*x/y的的语法树的构造语法树的构造2024/7/19383*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中的抽象语法树。当然，中的抽象语法树。当然，分析树的结构可能大不相同，而且可能需要引入继分析树的结构可能大不相同，而且可能需要引入继承属性来传递语义信息。承属性来传递语义信息。2024/7/1939在自顶向下分析过程中构造语法树在自顶向下分析过程中构造语法树产生式语义规则 T FT T.node := T .synT .inh := F.node T *FT1T1.inh := mknode(*, T .inh, F.node)T .syn:= T1.syn T /FT1T1.inh := mknode(/, T .inh, F.node)T .syn:= T1.syn T T .syn := T .inh F (E)F.node := E.node F idF.node := mkleaf(id, id.entry) F numF.node := mkleaf(num, num.val)2024/7/1940根据表根据表6.6的语法制导定义构造的语法制导定义构造的的语法树语法树2024/7/1941l 定义定义 翻译模式翻译模式是语法制导定义的一种便于实现的书写是语法制导定义的一种便于实现的书写形式。其中属性与文法符号相关联，语义规则或语义形式。其中属性与文法符号相关联，语义规则或语义动作用花括号动作用花括号 括起来，并可被插入到产生式右括起来，并可被插入到产生式右部的任何合适的位置上。部的任何合适的位置上。 这是一种语法分析和语义动作交错的表示法，它这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义表达在按深度优先遍历分析树的过程中何时执行语义动作。动作。 翻译模式给出了使用语义规则进行计算的顺序。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。可看成是分析过程中翻译的注释。6.4翻译模式翻译模式2024/7/1942将中缀表达式翻译成后缀表达式：将中缀表达式翻译成后缀表达式：ETRRaddopTprint(addop.lexeme)R1|Tnumprint(num.val)把语义动作看成终结符号，输入把语义动作看成终结符号，输入3+4-5,其分析树其分析树如图如图6.8，当按深度优先遍历它，执行遍历中访问的，当按深度优先遍历它，执行遍历中访问的语义动作，将输出语义动作，将输出34+5-它是输入表达式它是输入表达式3+4-5的后缀式。的后缀式。例例6.10一个简单的翻译模式一个简单的翻译模式2024/7/1943图图6.83+4-5的带语义动作的分析树的带语义动作的分析树2024/7/1944l前提前提语法制导定义是语法制导定义是L-属性定义属性定义保证语义动作不会引用还没计算出来的属性值保证语义动作不会引用还没计算出来的属性值1.只需要综合属性的情况只需要综合属性的情况为每一个语义规则建立一个包含赋值的动作，为每一个语义规则建立一个包含赋值的动作，并把该动作放在相应的产生式右部的末尾。并把该动作放在相应的产生式右部的末尾。例如：例如：TT1*FT val:=T1 val*F val转换成：转换成：TT1*FT val:=T1 val*F val翻译模式的设计翻译模式的设计根据语法制导定义根据语法制导定义2024/7/19452. 既有综合属性又有继承属性既有综合属性又有继承属性l 产生式右边的符号的继承属性必须在这个产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。符号以前的动作中计算出来。 l 一个动作不能引用这个动作右边符号的综一个动作不能引用这个动作右边符号的综合属性。合属性。 l 产生式左边非终结符号的综合属性只有在产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的计算这种属性的动作通常可放在产生式右端的末尾。末尾。翻译模式的设计翻译模式的设计根据语法制导定义根据语法制导定义2024/7/1946下面的翻译模式不满足要求：下面的翻译模式不满足要求：SA1A2A1 in:=1;A2 in:=2Aaprint(A in)/*A.in尚无定义尚无定义*/例例6.11从从L-属性制导定义建立一个满足上面属性制导定义建立一个满足上面要求的要求的翻译模式。翻译模式。使用文法产生的语言是数学排版语言使用文法产生的语言是数学排版语言EQNEsub1 val编排结果编排结果2024/7/1947B表示盒子表示盒子BB1B2代表两个相邻盒子的并列，且代表两个相邻盒子的并列，且B1位于位于B2的的左边。左边。BB1subB2代表盒子代表盒子B1后随下标盒子后随下标盒子B2，下标盒，下标盒子子B2以较小的字体和较低的位置出现。以较小的字体和较低的位置出现。B(B1)代表一个由括号括起来的盒子代表一个由括号括起来的盒子B1，主要是为，主要是为了对多个盒子或下标进行分组。在了对多个盒子或下标进行分组。在EQN中，使用花括中，使用花括号进行分组，此处使用圆括号是为了避免跟语义动作号进行分组，此处使用圆括号是为了避免跟语义动作外面的花括号产生冲突。外面的花括号产生冲突。Btext代表文本字符串，即任意字符组成的串。代表文本字符串，即任意字符组成的串。该文法是二义性的文法，将该文法是二义性的文法，将“并列并列”和和“下标下标”看成看成是左结合的，并令是左结合的，并令“下标下标”的优先级高于的优先级高于“并列并列”的的话，则可以对该文法所描述的语言进行自底向上的语话，则可以对该文法所描述的语言进行自底向上的语法分析。法分析。2024/7/1948属性设置属性设置pointsize用于表示盒子中文本的尺寸用于表示盒子中文本的尺寸(以点来计算，以点来计算，也就是字号也就是字号)。如果标准盒子的尺寸为。如果标准盒子的尺寸为p，则下标盒子，则下标盒子的尺寸为的尺寸为0.7p。属性。属性B.ps表示盒子表示盒子B的尺寸，该属性的尺寸，该属性是继承属性。是继承属性。每个盒子都有一个基线每个盒子都有一个基线(baseline)，用来表示每个文，用来表示每个文本底部的垂直位置。本底部的垂直位置。height用来表示从盒子的顶部到基线的距离。属性用来表示从盒子的顶部到基线的距离。属性B.ht表示盒子表示盒子B的高度的高度height，该属性是综合属性。，该属性是综合属性。depth用来表示从基线到盒子底部的距离。用属性用来表示从基线到盒子底部的距离。用属性B.dp表示盒子表示盒子B的深度的深度depth，该属性也是综合属性。，该属性也是综合属性。2024/7/1949表表6.7对盒子进行排版的语法制导定义对盒子进行排版的语法制导定义产生式语义规则S BB.ps:=10S.ht := B.htS.dp:= B.dpB B1B2B1.ps := B.psB2.ps := B.psB.ht := max(B1.ht, B2.ht)B.dp := max(B1.dp, B2.dp)BB1 sub B2B1.ps:=B.psB2.ps:=0.7B.psB.ht:=max(B1.ht, B2.ht-0.25B.ps)B.dp:=max(B1.dp, B2.dp+0.25B.ps)B (B1)B1.ps:=B.psB.ht:=B1.htB.dp:=B1.dpB textB.ht:=getheight(B.ps,text.lexval)B.dp:=getdepth(B.ps,text.lexval)2024/7/1950SB.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构造的翻译模式构造的翻译模式2024/7/1951TFT .inh:=F.nodeT T.node:=T .synT *FT1.inh :=mknode(*, T .inh,F.node)T1T .syn:=T1.synT /FT1.inh:=mknode(/, T .inh,F.node)T1T .syn:=T1.synT T .syn:=T .inhF(E )F.node:=E.nodeFidF.node:=mkleaf(id,id.entry)FnumF.node:=mkleaf(num,num.val)从表从表6.6构造的翻译模式构造的翻译模式2024/7/1952在分析栈中使用一个附加的域来存放综合属性在分析栈中使用一个附加的域来存放综合属性值。下图为一个带有综合属性值域的分析栈：值。下图为一个带有综合属性值域的分析栈：stackval.XX.xY.Y.y.ZZ.ztop6.4.2S-属性定义的自底向上计算属性定义的自底向上计算2024/7/1953 A b:=f(c1,c2,ck)b是是A的综合属性，的综合属性，ci (1 i k)是是 中符号的属中符号的属性。性。综合属性的值是在自底向上的分析过程中，综合属性的值是在自底向上的分析过程中，每次归约之前进行计算的。每次归约之前进行计算的。AXYZ A a:=f(X x,Y y,Z z)A aX xY yZ z2024/7/1954topstackval.XX.xYY.yZZ.zstackval.AA.atop实现时，将定义式实现时，将定义式A.a:=f(X.x,Y.y,Z.z)(抽象抽象)变变成成stackntop.val:=f(stacktop-2.val,stacktop-1.val,stacktop.val)(具体可执行代码具体可执行代码)。在执行代码段之前执行：在执行代码段之前执行： ntop:=top-r+1r是句柄的长度是句柄的长度执行代码段后执行：执行代码段后执行：top:=ntop;2024/7/1955例例6.14用用LR分析器实现分析器实现台式计算器台式计算器与表与表6.26.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.valstacktop.val;top:=top-2;TFF(E)stacktop-2.val:=stacktop-1.val;top:=top-2;Fdigit2024/7/1956表表6.8翻译输入翻译输入6+7*8n上的移动序列上的移动序列输入输入 stateval使用的产生式使用的产生式6+7*8n-+7*8n66+7*8nF6Fdigit+7*8nT6TF+7*8nE6ET 7*8nE+6+*8nE+76+72024/7/1957*8nE+F6+7Fdigit*8nE+T6+7TF8nE+T*6+7*nE+T*86+7*8nE+T*F6+7*8FdigitnE+T6+56TT*FnE62EE+TEn62L62LEn2024/7/1958 采用自底向上分析，例如采用自底向上分析，例如LR分析，首先给分析，首先给出出S- -属性定义，然后，把属性定义，然后，把S- -属性定义变成可执属性定义变成可执行的代码段，这就构成了翻译程序。象一座建行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个筑，语法分析是构架，归约处有一个“挂钩挂钩”，语义分析和翻译的代码段（语义子程序）语义分析和翻译的代码段（语义子程序）就就挂在这个钩子上。这样，随着语法分析的进行，挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序归约前调用相应的语义子程序, ,完成翻译的任务。完成翻译的任务。S-属性定义小结属性定义小结2024/7/1959l 用翻译模式构造自顶向下的翻译。用翻译模式构造自顶向下的翻译。1. 1. 从翻译模式中消除左递归从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基础文必须消除左递归和提取左公因子，在改写基础文法时考虑属性值的计算。法时考虑属性值的计算。 对于自顶向下语法分析，假设语义动作是在对于自顶向下语法分析，假设语义动作是在与之处于同一位置的文法非终结符被展开时执行与之处于同一位置的文法非终结符被展开时执行的，而且的，而且不考虑继承属性的处理（很简单）不考虑继承属性的处理（很简单）。6.4.3L-属性定义的自顶向下翻译属性定义的自顶向下翻译2024/7/1960l例例6.15考虑如下将中缀表达式翻译为后考虑如下将中缀表达式翻译为后缀表达式的翻译模式中的两个产生式：缀表达式的翻译模式中的两个产生式：E E1+Tprint(+);E TE TRR +Tprint(+);RR 只有简单语义动作时的左递归消除只有简单语义动作时的左递归消除2024/7/1961l设有如下左递归翻译模式：设有如下左递归翻译模式：AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)假设每个非终结符都有一个综合属性，用相应的小假设每个非终结符都有一个综合属性，用相应的小写字母表示，写字母表示，g和和f是任意函数。是任意函数。l消除左递归后，文法转换成消除左递归后，文法转换成AX RRY R|S-属性定义的左递归消除属性定义的左递归消除2024/7/1962l再考虑语义动作，翻译模式变为：再考虑语义动作，翻译模式变为：AXR i:=f(X x)RA a:=R sRYR1 i:=g(R i,Y y)R1R s:=R1 sRR s:=R i经过转换的翻译模式使用经过转换的翻译模式使用R的继承属性的继承属性i和综合属性和综合属性s。转换前后的结果是一样的转换前后的结果是一样的,为什么？为什么？为什么？为什么？S-属性定义的左递归消除属性定义的左递归消除AA1YA.a:=g(A1.a,Y.y) AXA.a:=f(X.x)引入继承属性引入继承属性R.i来收集应用函数来收集应用函数g的计算结果。其的计算结果。其初始值为初始值为A.a:=f(X.x）引入综合属性引入综合属性R.s在在R结束生成结束生成Y时时复制复制R.i的值。的值。2024/7/1963A a=g(g(f(X x),Y1 y),Y2 y)A a=g(f(X x),Y1 y)A a=f(X x)Y2Y1X(a)输入：输入：XY1Y22024/7/1964AR i=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)Y2Y1X(b)2024/7/1965L-属性定义的递归下降翻译器的构造：属性定义的递归下降翻译器的构造：1对每个非终结符对每个非终结符A构造一个函数构造一个函数A，将非终结符，将非终结符A的各个继承属性当作函数的各个继承属性当作函数A的形式参数，而将非终结的形式参数，而将非终结符符A的综合属性集当作函数的综合属性集当作函数A的返回值，为了便于讨的返回值，为了便于讨论，假设每个非终结符只具有一个综合属性。论，假设每个非终结符只具有一个综合属性。2在函数在函数A的过程体中，不仅要进行语法分析，而的过程体中，不仅要进行语法分析，而且要处理相应的语义属性。函数且要处理相应的语义属性。函数A的代码首先根据当的代码首先根据当前输入确定用哪个产生式展开前输入确定用哪个产生式展开A，然后按照，然后按照3中所给中所给的方法对各产生式进行编码。的方法对各产生式进行编码。2. L-属性定义的递归下降翻译法属性定义的递归下降翻译法2024/7/19663与每个产生式对应的程序代码的工作过程为：与每个产生式对应的程序代码的工作过程为：按照从左到右的次序，依次对产生式右部的记号、按照从左到右的次序，依次对产生式右部的记号、非终结符和语义动作执行如下的动作：非终结符和语义动作执行如下的动作：1)对带有综合属性对带有综合属性x的符号的符号X，将，将x的值保存在的值保存在X.x中，中，并生成一个函数调用来匹配并生成一个函数调用来匹配X，然后继续读入下一个，然后继续读入下一个输入符号；输入符号；2)对非终结符对非终结符B，生成一个右部带有函数调用的赋值，生成一个右部带有函数调用的赋值语句语句c:=B(b1,b2,bk)，其中，其中，b1,b2,bk是代表是代表B的的继承属性的变量，继承属性的变量，c是代表是代表B的综合属性的变量；的综合属性的变量；3)对于语义动作，将其代码复制到语法分析器中，对于语义动作，将其代码复制到语法分析器中，并将对属性的引用改为对相应变量的引用。并将对属性的引用改为对相应变量的引用。2. L-属性定义的递归下降翻译法属性定义的递归下降翻译法2024/7/1967 例例 6.16 6.16 functionT:syntax_tree_node;functionT(inh:syntax_tree_node):syntax_tree_node;functionF:syntax_tree_node;functionT:syntax_tree_node;var node,syn:syntax_tree_node;beginnode:=F;syn:=T (node);return synend;2024/7/1968functionT(inh:syntax_tree_node):syntax_tree_node;varnode,inh1,syn1:syntax_tree_node;oplexeme:char;begin iflookahead=*thenbegin/*匹配产生式匹配产生式T *FT */oplexeme:=lexval;match(*);node:=F;inh1:=mknode(*, inh,node);syn1:=T (inh1);syn:=syn1endelseiflookahead=/thenbegin/*匹配产生式匹配产生式T /FT */oplexeme:=lexval;match(/);node:=F;inh1:=mknode(/,inh,node); syn1:=T (inh1);syn:=syn1endelsesyn:=inh;returnsynend; 2024/7/1969functionF:syntax_tree_node;varnode:syntax_tree_node;beginiflookahead=(thenbegin/*匹配产生式匹配产生式F(E)*/match();node:=E;match()endelseiflookahead=idthenbegin/*匹配产生式匹配产生式Fid*/match(id);node:=mkleaf(id,id.entry)endelseiflookahead=numthenbegin/*匹配产生式匹配产生式Fnum*/match(num);node:=mkleaf(num,num.val)endreturnnode end; 2024/7/19703.L-属性定义的属性定义的LL(1)翻译法翻译法n预先在源文法中的相应位置上嵌入语义动作预先在源文法中的相应位置上嵌入语义动作符号符号(每个对应一个语义子程序每个对应一个语义子程序)，用于提示语，用于提示语法分析程序，当分析到达这些位置时应调用法分析程序，当分析到达这些位置时应调用相应的语义子程序。相应的语义子程序。n带有语义动作符号的文法又叫翻译文法。带有语义动作符号的文法又叫翻译文法。2024/7/19713.L-属性定义的属性定义的LL(1)翻译法翻译法n与递归子程序法的区别与联系与递归子程序法的区别与联系n都是在扫描过程中进行产生式的推导，同时在适都是在扫描过程中进行产生式的推导，同时在适当的地方加入语义动作。当的地方加入语义动作。n递归子程序法将语义动作溶入分析程序；递归子程序法将语义动作溶入分析程序；LL(1)分分析法则由语义子程序完成相应的翻译。析法则由语义子程序完成相应的翻译。n递归子程序法隐式地使用语义栈；递归子程序法隐式地使用语义栈；LL(1)分析法分析法则用显式的语义栈（程序自身控制对栈的操作）。则用显式的语义栈（程序自身控制对栈的操作）。注：语义与语法栈不同步。注：语义与语法栈不同步。2024/7/1972例例6.17n对于图对于图6.14的翻译模式，设置两个栈，一个是的翻译模式，设置两个栈，一个是分析栈，一个是语义栈。分析栈，一个是语义栈。TFe1T e2T *Fe3T1e4T /Fe5T1e4T e6F(E)e7Fide8Fnume92024/7/1973-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作1.初始化初始化T2024/7/1974-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作2.选产生式选产生式的右部进栈的右部进栈e2e1FT 2024/7/1975-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作3.选择产生式选择产生式,num3不进栈，调不进栈，调用用e9，调用，调用e9后，叶结点后，叶结点F.node被压入语义栈被压入语义栈e2e1e9T F.node2024/7/1976-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作4.执行动作执行动作e1，F.node出栈，出栈，T .inh被压入栈被压入栈 e2e1T T .inh2024/7/1977-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作5.选择产生式选择产生式,*不进栈不进栈e2T e5e4FT .inh2024/7/1978-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作6.选择产生式选择产生式,idx不进栈，调用不进栈，调用e8，调用，调用e8后，叶结点后，叶结点F.node被压入语义栈被压入语义栈 e2T e5e4T .inhF.nodee82024/7/1979-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作7.执行动作执行动作e5，F.node和和T .inh均被弹出栈，新的均被弹出栈，新的T .inh被压入栈被压入栈 T .inhe2T e5e42024/7/1980-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作8.选择产生式选择产生式,/不进栈不进栈 T .inhe2e4T e4e3F2024/7/1981-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作9.选择产生式选择产生式,idy不进栈，调用不进栈，调用e8，调用，调用e8后，叶结点后，叶结点F.node被压入语义栈被压入语义栈 T .inhF.nodee2e4T e4e3e82024/7/1982-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作10.执行动作执行动作e3，F.node和和T .inh均被弹出栈，新的均被弹出栈，新的T .inh被压入栈被压入栈 T .inhe2e4T e4e32024/7/1983-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作11.选择产生式选择产生式，T .inh被弹出被弹出栈，栈，T .syn被压入栈被压入栈 e2e4e6e4T .inh2024/7/1984-#语义栈语义栈语法栈语法栈3*x/y#输入串输入串例例6.17对输入串对输入串3*x/y的翻译的翻译语法分析动作和语义操作语法分析动作和语义操作12.依次执行动作依次执行动作e6,e4,e4,e2,最终语义栈中最终语义栈中只有只有T.node,代表代表3*x/y的语法树的的语法树的根结点根结点 T.node2024/7/19856.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译在在自底向上分析的框架中实现自底向上分析的框架中实现L属性定义的方法属性定义的方法n它能实现任何基于它能实现任何基于LL(1)文法的文法的L属性定义。属性定义。n也能实现许多（但不是所有的）基于也能实现许多（但不是所有的）基于LR(1)文文法的法的L属性定义。属性定义。2024/7/19866.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)首先像首先像6.4.1所介绍的那样构造翻译模式，所介绍的那样构造翻译模式，它将计算继承属性的动作嵌入在非终结符它将计算继承属性的动作嵌入在非终结符的前面，而将计算综合属性的动作放在产的前面，而将计算综合属性的动作放在产生式的末尾。生式的末尾。在每个嵌入动作处引入一个标记性非终在每个嵌入动作处引入一个标记性非终结符结符(markernonterminals)。不同位置所。不同位置所对应的标记是不同的，每个标记性非终结对应的标记是不同的，每个标记性非终结符符M都有一个形如都有一个形如M的产生式。的产生式。2024/7/19876.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)如果标记性非终结符如果标记性非终结符M取代了某个产生取代了某个产生式式Aa中的动作中的动作a，则按如下方式将，则按如下方式将a修改为修改为a，并将动作，并将动作a放在产生式放在产生式M的末尾。的末尾。为为M设置继承属性来复制动作设置继承属性来复制动作a所需要所需要的的A或或中符号的继承属性；中符号的继承属性；以与动作以与动作a相同的方式计算属性，只不相同的方式计算属性，只不过要将这些属性置为过要将这些属性置为M的综合属性。的综合属性。2024/7/19886.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)n与与M相关联的语义动作可能需要用到没出相关联的语义动作可能需要用到没出现在该产生式中的文法符号的属性。不过，现在该产生式中的文法符号的属性。不过，由于要在由于要在LR分析栈中实现所有的语义动作，分析栈中实现所有的语义动作，所以在分析栈中所以在分析栈中M下面的某个已知位置总能找下面的某个已知位置总能找到所需的属性。到所需的属性。n例如，假设在某个例如，假设在某个LL(1)文法中有一个形如文法中有一个形如ABC的产生式，的产生式，B的继承属性的继承属性B.inh是从是从A的的继承属性继承属性A.inh按照公式按照公式B.inh :=f(A.inh)来计来计算的，亦即翻译模式可能包含如下片断：算的，亦即翻译模式可能包含如下片断： AB.inh:=f(A.inh);BC2024/7/19896.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)n根据上面的论述，为了在自底向上的分析过程根据上面的论述，为了在自底向上的分析过程中计算中计算B.inh :=f(A.inh)，需要引入一个标记性，需要引入一个标记性非终结符非终结符M，并为其设置一个继承属性，并为其设置一个继承属性M.inh用用来复制来复制A的继承属性的继承属性，而且还要用而且还要用M的综合属的综合属性性M.syn代替代替B.inh，于是，该翻译模式片段将，于是，该翻译模式片段将被修改为如下形式：被修改为如下形式：AMBCMM.inh:=A.inh;M.syn :=f(M.inh)2024/7/19906.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)n注意，执行注意，执行M的语义规则时，的语义规则时，A.inh是不可是不可用的，但实际上，实现时会把每个非终结用的，但实际上，实现时会把每个非终结符符X的继承属性都放在堆栈中紧靠在的继承属性都放在堆栈中紧靠在X将将被归约出来的位置之下。于是，当将被归约出来的位置之下。于是，当将归归约为约为M时，时，A.inh恰好就在它的下面。随恰好就在它的下面。随M保存在栈中的保存在栈中的M.syn的值，也就是的值，也就是B.inh的的值，亦将被放在紧靠在值，亦将被放在紧靠在B将被归约出来的将被归约出来的位置之下，需要的时候同样是可用的。位置之下，需要的时候同样是可用的。2024/7/19916.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)n下面的化简可以减少标记性非终结符的下面的化简可以减少标记性非终结符的个数，其中第个数，其中第2条还可以避免左递归文法条还可以避免左递归文法中的分析冲突：中的分析冲突：如果如果Xj没有继承属性，则不需要使用标记没有继承属性，则不需要使用标记Mj。当。当然，如果省略了然，如果省略了Mj，属性在栈中的预期位置就会改，属性在栈中的预期位置就会改变，但是分析器可以很容易地适应这种变化。变，但是分析器可以很容易地适应这种变化。如果如果X1.inh存在，但它是由复制规则存在，但它是由复制规则X1.inh:= A.inh计算的，此时可以省略计算的，此时可以省略M1。因为。因为A.inh存放在存放在栈中紧挨在栈中紧挨在X1下面的地方，所以该值也可同时作为下面的地方，所以该值也可同时作为X1.inh的值。的值。2024/7/19926.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)例例6.18数学排版语言数学排版语言EQNS B.ps:=10BS.ht:=B.ht;S.dp:=B.dpB B1.ps:=B.ps B1B2.ps:=B.ps B2B.ht:=max(B1.ht,B2.ht )B B1.ps:=B.psB1subB2.ps:=0.7 B.psB2B.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在栈中的位置。在栈中的位置。2024/7/19936.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续)n由于存在一个继承属性和两个综合属性，所由于存在一个继承属性和两个综合属性，所以语义栈以语义栈val需要被扩展为需要被扩展为val1、val2和和val3nval1用于保存继承属性用于保存继承属性ps的值的值nval2和和val3分别用于保存综合属性分别用于保存综合属性ht和和dp的值的值n假设分析栈仍为假设分析栈仍为stackntop和和ntop分别是归约前和归约后栈顶的下标。分别是归约前和归约后栈顶的下标。2024/7/19946.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续) 产 生 式 语 义 规 则 S LB B.ps := L.syn; S.ht := B.ht ; S.dp := B.dp L L.syn := 10 B B1 MB2 B1.ps := B.ps; M.inh := B.ps;B2.ps := M.syn;B.ht := max(B1.ht, B2.ht ) M M.syn := M.inh B B1 sub NB2 B1.ps :=B.ps; N.inh := B.ps;B2.ps := N.syn; B.ht := disp (B1.ht, B2.ht);B.dp:=max(B1.dp, B2.dp) N N.syn := 0.7N.inhB text B.ht := getheight(B.ps,text.lexval);B.dp:= getdepth(B.ps,text.lexval)2024/7/19956.4.4L-属性定义的自底向上翻译属性定义的自底向上翻译(续续) 产 生 式 代 码 段S LB stackntop.val2 := stacktop.val2stackntop.val3 := stacktop.val3 L stackntop.val1 := 10 B B1 MB2 stackntop.val2 := max(stacktop-2.val2, stacktop.val2)stackntop.val3 := max(stacktop-2.val3, stacktop.val3) M stackntop.val1 := stacktop-1.val1 B B1 sub NB2 stackntop.val2:= max(stacktop-3.val2, stacktop.val2-0.25stacktop-4.val1)stackntop.val3 := max(stacktop-3.val3, stacktop.val3+0.25stacktop-4.val1) N stackntop.val1 := 0.7stacktop-2.val1 B text stackntop.val2 := getheight(stacktop-1.val1,text.lexval)stackntop.val3 := getdepth(stacktop-1.val1,text.lexval) 2024/7/1996本章小结本章小结n语法分析中进行静态语义检查和中间代码生语法分析中进行静态语义检查和中间代码生成的技术称为语法制导翻译技术。成的技术称为语法制导翻译技术。n为了通过将语义属性关联到文法符号、将语为了通过将语义属性关联到文法符号、将语义规则关联到产生式，有效地将语法和语义义规则关联到产生式，有效地将语法和语义关联起来，人们引入了语法制导定义。没有关联起来，人们引入了语法制导定义。没有副作用的语法制导定义又称为属性文法。副作用的语法制导定义又称为属性文法。2024/7/1997本章小结本章小结n为相应的语法成分设置表示语义的属性，属为相应的语法成分设置表示语义的属性，属性的值是可以计算的，根据属性值计算的关性的值是可以计算的，根据属性值计算的关联关系，将其分成综合属性和继承属性，根联关系，将其分成综合属性和继承属性，根据属性文法中所含的属性将属性文法分成据属性文法中所含的属性将属性文法分成S-属性文法和属性文法和L-属性文法。属性文法。n如果不仅将语义属性关联到文法符号、将语如果不仅将语义属性关联到文法符号、将语义规则关联到产生式，而且还通过将语义动义规则关联到产生式，而且还通过将语义动作嵌入到产生式的适当位置来表达该语义动作嵌入到产生式的适当位置来表达该语义动作的执行时机，这就是翻译模式。翻译模式作的执行时机，这就是翻译模式。翻译模式给语义分析的实现提供了更好的支持。给语义分析的实现提供了更好的支持。2024/7/1998本章小结本章小结n注释分析树和相应的依赖图是属性值的关联注释分析树和相应的依赖图是属性值的关联关系和计算顺序的表达形式，语义关系可以关系和计算顺序的表达形式，语义关系可以使用抽象语法树表示。使用抽象语法树表示。n依据语法分析方法有自底向上的和自顶向下依据语法分析方法有自底向上的和自顶向下的，语法制导翻译既可以按照自底向上的策的，语法制导翻译既可以按照自底向上的策略进行，也可以按照自顶向下的策略进行。略进行，也可以按照自顶向下的策略进行。