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

《【教学课件】第六章语法制导翻译与属性文法.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第六章语法制导翻译与属性文法.ppt（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 语法制导翻译与语法制导翻译与属性文法属性文法School of Computer Science&Technology Harbin Institute of Technology重点：重点：语法制导翻译的基本思想，语法制导定义，语法制导翻译的基本思想，语法制导定义，翻译模式，自顶向下翻译，自底向上翻译。翻译模式，自顶向下翻译，自底向上翻译。难点：难点：属性的意义，对综合属性，继承属性，属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，固有属性的理解，属性计算，怎么通过属性来表达翻译。怎么通过属性来表达翻译。2023/1/102第第6章章语法制导翻译与属性文法语法制导翻

2、译与属性文法 6.1语法制导翻译概述语法制导翻译概述6.2语法制导定义语法制导定义6.3属性计算属性计算6.4翻译模式翻译模式6.5本章小结本章小结2023/1/103n为什么进行词法和语法分析？为什么进行词法和语法分析？n用用A进行归约表达的是什么意思？进行归约表达的是什么意思？n看：看：operand+termnEE1+TnE1的值的值+T的值的结果作为的值的结果作为E的值的值即：取来即：取来E1的值和的值和T的值做加法运算，结果作为的值做加法运算，结果作为E的值的值E.val=E1.val+T.val问题2023/1/1046.1语法制导翻译概述语法制导翻译概述n为了提高编译程序的可移植

3、性，一般将编译程为了提高编译程序的可移植性，一般将编译程序划分为前端和后端。序划分为前端和后端。n前端通常包括词法分析、语法分析、语义分析、中前端通常包括词法分析、语法分析、语义分析、中间代码生成、符号表的建立，以及与机器无关的中间代码生成、符号表的建立，以及与机器无关的中间代码优化等，它们的实现一般不依赖于具体的目间代码优化等，它们的实现一般不依赖于具体的目标机器。标机器。n后端通常包括与机器有关的代码优化、目标代码的后端通常包括与机器有关的代码优化、目标代码的生成、相关的错误处理以及符号表的访问等。生成、相关的错误处理以及符号表的访问等。图图6.1编译器前端的逻辑结构编译器前端的逻辑结构2

4、023/1/1056.1语法制导翻译概述语法制导翻译概述n语义分析器的主要任务是检查各个语法结构的语义分析器的主要任务是检查各个语法结构的静态语义静态语义 ，称为静态语义分析或静态检查，称为静态语义分析或静态检查 n类型检查：操作数和操作符的类型是否相容；类型检查：操作数和操作符的类型是否相容；n控制流检查：控制流转向的目标地址是否合法；控制流检查：控制流转向的目标地址是否合法；n惟一性检查：对象是否被重复定义；惟一性检查：对象是否被重复定义；n关联名检查：同一名字的多次特定出现是否一致。关联名检查：同一名字的多次特定出现是否一致。n将静态检查和中间代码生成结合到语法分析中将静态检查和中间代码

5、生成结合到语法分析中进行的技术称为进行的技术称为语法制导翻译语法制导翻译 。2023/1/1066.1语法制导翻译概述语法制导翻译概述n语法制导翻译的基本思想语法制导翻译的基本思想n在进行语法分析的同时，完成相应的语义处理。也在进行语法分析的同时，完成相应的语义处理。也就是说，一旦语法分析器识别出一个语法结构就要就是说，一旦语法分析器识别出一个语法结构就要立即对其进行翻译，翻译是根据语言的语义进行的，立即对其进行翻译，翻译是根据语言的语义进行的，并通过调用事先为该语法结构编写的语义子程序来并通过调用事先为该语法结构编写的语义子程序来实现。实现。n对文法中的每个产生式附加一个对文法中的每个产生式

6、附加一个/多个语义动作多个语义动作(或或语义子程序语义子程序)，在语法分析的过程中，每当需要使用，在语法分析的过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动行相应的语法分析动作外，还要执行相应的语义动作作(或调用相应的语义子程序或调用相应的语义子程序)。2023/1/1076.1语法制导翻译概述语法制导翻译概述n语义子程序的功能语义子程序的功能n指明相应产生式中各个文法符号的具体含义，并指明相应产生式中各个文法符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义规定了使用该产生式进

7、行分析时所应采取的语义动作动作(如传送或处理语义信息、查填符号表、计算如传送或处理语义信息、查填符号表、计算值、生成中间代码等值、生成中间代码等)。n语义信息的获取和加工是和语法分析同时进行的，语义信息的获取和加工是和语法分析同时进行的，而且这些语义信息是通过文法符号来携带和传递而且这些语义信息是通过文法符号来携带和传递的。的。2023/1/1086.1语法制导翻译概述语法制导翻译概述n一个文法符号一个文法符号X所携带的语义信息称为所携带的语义信息称为X的语的语义属性，简称为属性，它是根据翻译的需要设义属性，简称为属性，它是根据翻译的需要设置的置的(对应分析树结点的数据结构对应分析树结点的数据

8、结构)，主要用于，主要用于描述语法结构的语义。描述语法结构的语义。n一个变量的属性有类型、层次、存储地址等一个变量的属性有类型、层次、存储地址等n表达式的属性有类型、值等。表达式的属性有类型、值等。2023/1/1096.1语法制导翻译概述语法制导翻译概述n属性值的计算和产生式相关联，随着语法属性值的计算和产生式相关联，随着语法分析的进行，执行属性值的计算，完成语分析的进行，执行属性值的计算，完成语义分析和翻译的任务。义分析和翻译的任务。nEE1+E2E.val:=E1.val+E2.valn语法结构具有规定的语义语法结构具有规定的语义n问题：如何根据被识别出的语法成分进行问题：如何根据被识别

9、出的语法成分进行语义处理？语义处理？n亦即怎样亦即怎样将属性值的计算及翻译工作同产生式将属性值的计算及翻译工作同产生式相关联？相关联？2023/1/1010典型处理方法一典型处理方法一n语法制导定义语法制导定义n通过将属性与文法符号关联、将语义规则与产生通过将属性与文法符号关联、将语义规则与产生式关联来描述语言结构的翻译方案式关联来描述语言结构的翻译方案n对应每一个产生式编写一个语义子程序，当一个对应每一个产生式编写一个语义子程序，当一个产生式获得匹配时，就调用相应的语义子程序来产生式获得匹配时，就调用相应的语义子程序来实现语义检查与翻译实现语义检查与翻译nEE1+TE.val:=E1.val

10、+T.valnTT1*FT.val:=T1.val*F.valnF digitF.val:=digit.lexvaln适宜在完成归约的时候进行适宜在完成归约的时候进行2023/1/1011典型处理方法二典型处理方法二n翻译模式翻译模式n通过将属性与文法符号关联，并将语义规则插入到产生式通过将属性与文法符号关联，并将语义规则插入到产生式的右部来描述语言结构的翻译方案的右部来描述语言结构的翻译方案n在产生式的右部的适当位置，插入相应的语义动在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作作，按照分析的进程，执行遇到的语义动作nDTL.inh:=T.typeLnTin

11、tT.type:=integernTrealT.type:=realnLL1.inh:=L.inhL1,idaddtype(id.entry,L.inh)nLidaddtype(id.entry,L.inh)n适宜在进行推导时完成适宜在进行推导时完成2023/1/10126.2语法制导定义语法制导定义n语法制导定义是附带有属性和语义规则的上下语法制导定义是附带有属性和语义规则的上下文无关文法文无关文法n属性是与文法符号相关联的语义信息属性是与文法符号相关联的语义信息n语义规则是与产生式相关联的语义动作语义规则是与产生式相关联的语义动作n语法制导定义是基于语言结构的语义要求设计语法制导定义是基于

12、语言结构的语义要求设计的，类似于程序设计，语法制导定义中的属的，类似于程序设计，语法制导定义中的属性类似于程序中用到的数据结构，用于描述性类似于程序中用到的数据结构，用于描述语义信息，语义规则类似于计算，用于收集、语义信息，语义规则类似于计算，用于收集、传递和计算语义信息的。传递和计算语义信息的。n属性通常被保存在分析树的相关节点中属性通常被保存在分析树的相关节点中2023/1/1013概念术语概念术语n综合属性：节点的属性值是通过分析树中该节综合属性：节点的属性值是通过分析树中该节点或其子节点的属性值计算出来的点或其子节点的属性值计算出来的n继承属性：节点的属性值是由该节点、该节点继承属性：

13、节点的属性值是由该节点、该节点的兄弟节点或父节点的属性值计算出来的的兄弟节点或父节点的属性值计算出来的n固有属性：通过词法分析直接得到的属性固有属性：通过词法分析直接得到的属性n依赖图：描述属性之间依赖关系的图，根据语依赖图：描述属性之间依赖关系的图，根据语义规则来构造义规则来构造n注释分析树：节点带有属性值的分析树注释分析树：节点带有属性值的分析树2023/1/1014语法制导定义的形式语法制导定义的形式n在一个在一个语法制导定义语法制导定义中，中，A P都有与之相关联的都有与之相关联的一套语义规则，规则形式为一套语义规则，规则形式为b：=f（c1，c2，ck），），f是一个函数，而且或者是

14、一个函数，而且或者1b是是A的一个综合属性并且的一个综合属性并且c1，c2，ck是是 中的中的符号的属性，或者符号的属性，或者2b是是 中中某个某个符号的一个继承属性并且符号的一个继承属性并且c1，c2，ck是是A或或 中的中的任何文法符号的属性。任何文法符号的属性。这两种情况下，都说属性这两种情况下，都说属性b依赖于属性依赖于属性c1，c2，ck2023/1/1015例例6.1 台式计算器的语法制导定义台式计算器的语法制导定义产生式 语义规则LEn print(Eval)(可看作是L的虚属性)E E1+T Eval:=E1val+TvalE T Eval:=TvalT T1*F Tval:=

15、T1val+FvalT F Tval:=FvalF(E)Fval:=EvalF digit Fval:=digitlexval2023/1/1016S-属性属性定义定义n只含综合属性的语法制导定义称为只含综合属性的语法制导定义称为S-属性定义属性定义n对于对于S-属性定义，通常使用自底向上的分析方属性定义，通常使用自底向上的分析方法，在建立每一个结点处使用语义规则来计法，在建立每一个结点处使用语义规则来计算综合属性值，即在用哪个产生式进行归约算综合属性值，即在用哪个产生式进行归约后，就执行那个产生式的后，就执行那个产生式的S-属性定义计算属性属性定义计算属性的值，从叶结点到根结点进行计算。的值

16、，从叶结点到根结点进行计算。n没有副作用的语法制导定义有时又称为没有副作用的语法制导定义有时又称为属性文属性文法法，属性文法的语义规则单纯根据常数和其，属性文法的语义规则单纯根据常数和其它属性的值来定义某个属性的值它属性的值来定义某个属性的值2023/1/1017继承属性继承属性n当分析树的结构同源代码的抽象语法不当分析树的结构同源代码的抽象语法不“匹配匹配”时，继承属性将非常有用。下面的例子可时，继承属性将非常有用。下面的例子可以说明怎样用继承属性来解决这种不匹配问以说明怎样用继承属性来解决这种不匹配问题，产生这种不匹配的原因是因为文法通常题，产生这种不匹配的原因是因为文法通常是为语法分析而

17、不是为翻译设计的。是为语法分析而不是为翻译设计的。n例例6.2n考虑如何在自顶向下的分析过程中计算考虑如何在自顶向下的分析过程中计算3*5和和4*8*9这样的表达式项这样的表达式项n消除左递归之后的算数表达式文法的一个子集：消除左递归之后的算数表达式文法的一个子集：TFTT*FT1T Fdigit2023/1/1018表表6.3 为适于自顶向下分析的文法设为适于自顶向下分析的文法设计的语法制导定义计的语法制导定义 产生式产生式语义规则语义规则TFTT.inh:=F.valT.val:=T.syn T*FT1T1.inh:=T.inhF.valT.syn:=T1.synT T.syn:=T.in

18、hFdigitF.val:=digit.lexval2023/1/10194*8*9的注释分析树的注释分析树2023/1/1020表表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

19、 T.syn:=T.inhnFdigitF.val:=digit.lexval2023/1/10216.3属性计算属性计算n语义规则定义了属性之间的依赖关系，这种依语义规则定义了属性之间的依赖关系，这种依赖关系将影响属性的计算顺序赖关系将影响属性的计算顺序n为了确定分析树中各个属性的计算顺序，我们为了确定分析树中各个属性的计算顺序，我们可以用图来表示属性之间的依赖关系，并将可以用图来表示属性之间的依赖关系，并将其称为依赖图其称为依赖图n如果依赖图中没有回路，则利用它可以很方便如果依赖图中没有回路，则利用它可以很方便地求出属性的计算顺序。地求出属性的计算顺序。n注释分析树只是给出了属性的值，而依

20、赖图则注释分析树只是给出了属性的值，而依赖图则可以帮助我们确定如何将这些属性值计算出可以帮助我们确定如何将这些属性值计算出来。来。2023/1/10226.3.1依赖图依赖图n所谓依赖图其实就是一个有向图，用于描述分所谓依赖图其实就是一个有向图，用于描述分析树中节点的属性和属性间的相互依赖关系，析树中节点的属性和属性间的相互依赖关系，称为分析树的依赖图。称为分析树的依赖图。n每个属性对应依赖图中的一个节点，如果属性每个属性对应依赖图中的一个节点，如果属性b依赖于属性依赖于属性c，则从属性，则从属性c的节点有一条有向的节点有一条有向边指向属性边指向属性b的节点。的节点。n属性间的依赖关系是根据相

21、应的语义规则确定属性间的依赖关系是根据相应的语义规则确定的。的。2023/1/1023依赖图的构造方法依赖图的构造方法for分析树的每个节点分析树的每个节点ndofor与节点与节点n对应的文法符号的每个属性对应的文法符号的每个属性ado在依赖图中为在依赖图中为a构造一个节点；构造一个节点；for分析树的每个节点分析树的每个节点ndofor节点节点n所用产生式对应的每条语义规则所用产生式对应的每条语义规则b:=f(c1,c2,ck)dofori:=1tokdo构造一条从节点构造一条从节点ci到节点到节点b的有向边；的有向边；2023/1/1024例例6.3图图6.3中注释分析树的依赖图中注释分析

22、树的依赖图2023/1/10256.3.2属性的计算顺序属性的计算顺序n拓扑排序拓扑排序n一个无环有向图的拓扑排序是图中结点的任何顺一个无环有向图的拓扑排序是图中结点的任何顺序序m1，m2，mk，使得边必须是从序列中前面，使得边必须是从序列中前面的结点指向后面的结点，也就是说，如果的结点指向后面的结点，也就是说，如果mimj是是mi到到mj的一条边的一条边,那么在那么在序列中序列中mi必须出现在必须出现在mj的前面。的前面。n若依赖图中无环，则存在一个拓扑排序，它就是若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。属性值的计算顺序。n例例6.4图图6.4的拓扑排序为：的拓扑排序为：

23、1，2，3，4，5，6，7，8，9，10，11，12，132023/1/10266.3.2属性的计算顺序属性的计算顺序n根据拓扑排序得到的翻译程序根据拓扑排序得到的翻译程序na4:=4a5:=a4a6:=8na7:=a5a6a8:=9a9:=a7a8na10:=a9a11:=a10a12:=a11na13:=a12n上述属性计算方法又称为上述属性计算方法又称为分析树法分析树法，这种方法在编，这种方法在编译时需要显式地构造分析树和依赖图，所以编译的译时需要显式地构造分析树和依赖图，所以编译的时空效率比较低，而且如果分析树的依赖图中存在时空效率比较低，而且如果分析树的依赖图中存在回路的话，这种方法

24、将会失效。回路的话，这种方法将会失效。n这种方法的优点是可以多次遍历分析树，从而使得这种方法的优点是可以多次遍历分析树，从而使得属性的计算不依赖于所采用的语法分析方法以及属属性的计算不依赖于所采用的语法分析方法以及属性间严格的依赖关系。性间严格的依赖关系。2023/1/1027计算语义规则的其他方法计算语义规则的其他方法n基于规则的方法基于规则的方法n在构造编译器时，用手工或专门的工具来分析语在构造编译器时，用手工或专门的工具来分析语义规则义规则,确定属性值的计算顺序。确定属性值的计算顺序。n忽略语义规则的方法忽略语义规则的方法n在分析过程中翻译，那么计算顺序由分析方法来在分析过程中翻译，那么

25、计算顺序由分析方法来确定而表面上与语义规则无关。这种方法限制了确定而表面上与语义规则无关。这种方法限制了能被实现的语法制导定义的种类。能被实现的语法制导定义的种类。n这两种方法都不必显式构造依赖图，因此时这两种方法都不必显式构造依赖图，因此时空效率更高。空效率更高。2023/1/1028S-属性定义属性定义n定义定义6.1只含综合属性的语法制导定义称为只含综合属性的语法制导定义称为S-属性定属性定义，又称为义，又称为S-属性文法。属性文法。n如果某个语法制导定义是如果某个语法制导定义是S-属性定义，则可以按照属性定义，则可以按照自下而上的顺序来计算分析树中节点的属性。自下而上的顺序来计算分析树

26、中节点的属性。n一种简单的属性计算方法是对分析树进行后根遍历，一种简单的属性计算方法是对分析树进行后根遍历，并在最后一次遍历节点并在最后一次遍历节点N时计算与节点时计算与节点N相关联的属相关联的属性。性。npostorder(N)nforN的每个子节点的每个子节点M(从左到右从左到右)postorder(M);n计算与节点计算与节点N相关联的属性相关联的属性;n2023/1/1029L-属性定义属性定义n定义定义6.2一个语法制导定义被称为一个语法制导定义被称为L-属性定义，属性定义，当且仅当它的每个属性或者是综合属性，或当且仅当它的每个属性或者是综合属性，或者是满足如下条件的继承属性：设有产

27、生式者是满足如下条件的继承属性：设有产生式AX1X2Xn，其右部符号，其右部符号Xi(1in)的继承属的继承属性只依赖于下列属性：性只依赖于下列属性：A的继承属性；的继承属性；产生式中产生式中Xi左边的符号左边的符号X1、X2、Xi-1的综合的综合属性或继承属性；属性或继承属性；Xi本身的综合属性或继承属性，但前提是本身的综合属性或继承属性，但前提是Xi的属的属性不能在依赖图中形成回路。性不能在依赖图中形成回路。nL-属性定义又称为属性定义又称为L-属性文法。属性文法。2023/1/1030表表6.3 L-属性属性定义示例定义示例 产生式产生式语义规则语义规则TFTT.inh:=F.valT.

28、val:=T.syn T*FT1T1.inh:=T.inhF.valT.syn:=T1.synT T.syn:=T.inhFdigitF.val:=digit.lexval2023/1/1031例例6.7不是不是L-属性定义的语法制导定义属性定义的语法制导定义产生式产生式语义规则语义规则ABCA.syn:=B.bB.inh:=f(C.c,A.syn)语义规则语义规则B.inh:=f(C.c,A.syn)定义了一个继承属性，所以整个定义了一个继承属性，所以整个语法制导定义就不是语法制导定义就不是S-属性定义了。此外，虽然这条语义规则属性定义了。此外，虽然这条语义规则是合法的属性定义规则，但不满足

29、是合法的属性定义规则，但不满足L-属性定义的要求。这是因属性定义的要求。这是因为：属性为：属性B.inh的定义中用到了属性的定义中用到了属性C.c，而，而C在产生式的右部在产生式的右部处在处在B的右边。虽然在的右边。虽然在L-属性定义中可以使用兄弟节点的属性属性定义中可以使用兄弟节点的属性来定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因来定义某个属性，但这些兄弟节点必须是左兄弟节点才行。因此，该语法制导定义也不是此，该语法制导定义也不是L-属性定义。属性定义。2023/1/1032L-属性定义中的属性计算属性定义中的属性计算visit(N)forN的每个子节点的每个子节点M(从左到右从左

30、到右)计算节点计算节点M的继承属性的继承属性;visit(M);计算节点计算节点N的综合属性的综合属性;2023/1/1033抽象语法树抽象语法树是表示程序层次结构的树，它把分析树中是表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式对语义无关紧要的成分去掉，是分析树的抽象形式 ，也称作语法结构树，或结构树。也称作语法结构树，或结构树。语法树是常用的一种语法树是常用的一种中间表示中间表示形式。形式。把语法分析和翻译分开。语法分析过程中完成翻译把语法分析和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：有许多优点，但也有一些不足：1.1.适于语法分析的文法

31、可能不完全反映语言成分的适于语法分析的文法可能不完全反映语言成分的自然层次结构；自然层次结构；2.2.由于语法分析方法的限制，对分析树结点的访由于语法分析方法的限制，对分析树结点的访问顺序和翻译需要的访问顺序不一致。问顺序和翻译需要的访问顺序不一致。6.3.5属性计算示例属性计算示例抽象语法树的构造抽象语法树的构造 2023/1/1034产生式产生式SifBthenS1elseS2的语法树的语法树if-then-else|BS1S2赋值语句赋值语句的语法树的语法树assignmentvariableexpression在语法树中，运算符号和关键字都不在叶结点，在语法树中，运算符号和关键字都不在

32、叶结点，而是在内部结点中出现。而是在内部结点中出现。语法树语法树2023/1/1035构造表达式的语法树使用的函数构造表达式的语法树使用的函数1.mknode(op,left,right)建立一个标记为建立一个标记为op的运算的运算符结点，两个域符结点，两个域left和和right分别是指向左右运算对象分别是指向左右运算对象的指针。的指针。2mkleaf(id,entry)建立一个标记为建立一个标记为id的标识符结的标识符结点，其域点，其域entry是指向该标识符在符号表中相应表项的是指向该标识符在符号表中相应表项的指针。指针。3.mkleaf(num,val)建立一个标记为建立一个标记为nu

33、m的数结点，的数结点，其域其域val用于保存该数的值。用于保存该数的值。构造表达式的语法树构造表达式的语法树2023/1/1036构造表达式语法树的语法制导定义构造表达式语法树的语法制导定义产生式产生式语义规则语义规则TT1*FT.node:=mknode(*,T1.node,F.node)TT1/FT.node:=mknode(/,T1.node,F.node)TFT.node:=F.nodeF(E)F.node:=E.nodeFidF.node:=mkleaf(id,id.entry)FnumF.node:=mkleaf(num,num.val)2023/1/1037图图6.53*x/y的

34、的语法树的构造语法树的构造2023/1/10383*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中的抽象语法树。当然，中的抽象语法树。当然，分析树的结构可能大不相同

35、，而且可能需要引入继分析树的结构可能大不相同，而且可能需要引入继承属性来传递语义信息。承属性来传递语义信息。2023/1/1039在自顶向下分析过程中构造语法树在自顶向下分析过程中构造语法树产生式产生式语义规则语义规则TFT T.node:=T.synT.inh:=F.nodeT*FT1T1.inh:=mknode(*,T.inh,F.node)T.syn:=T1.synT/FT1T1.inh:=mknode(/,T.inh,F.node)T.syn:=T1.synT T.syn:=T.inhF(E)F.node:=E.nodeFidF.node:=mkleaf(id,id.entry)Fnu

36、mF.node:=mkleaf(num,num.val)2023/1/1040根据表根据表6.6的语法制导定义构造的语法制导定义构造的的语法树语法树2023/1/1041l 定义定义 翻译模式翻译模式是语法制导定义的一种便于实现的书写是语法制导定义的一种便于实现的书写形式。其中属性与文法符号相关联，语义规则或语义形式。其中属性与文法符号相关联，语义规则或语义动作用花括号动作用花括号 括起来，并可被插入到产生式右括起来，并可被插入到产生式右部的任何合适的位置上。部的任何合适的位置上。这是一种语法分析和语义动作交错的表示法，它这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过

37、程中何时执行语义表达在按深度优先遍历分析树的过程中何时执行语义动作。动作。翻译模式给出了使用语义规则进行计算的顺序。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。可看成是分析过程中翻译的注释。6.4翻译模式翻译模式2023/1/1042将中缀表达式翻译成后缀表达式：将中缀表达式翻译成后缀表达式：ETRRaddopTprint(addop.lexeme)R1|Tnumprint(num.val)把语义动作看成终结符号，输入把语义动作看成终结符号，输入3+4-5,其分析树其分析树如图如图6.8，当按深度优先遍历它，执行遍历中访问的，当按深度优先遍历它，执行遍历中访问的语义

38、动作，将输出语义动作，将输出34+5-它是输入表达式它是输入表达式3+4-5的后缀式。的后缀式。例例6.10一个简单的翻译模式一个简单的翻译模式2023/1/1043图图6.83+4-5的带语义动作的分析树的带语义动作的分析树2023/1/1044l前提前提语法制导定义是语法制导定义是L-属性定义属性定义保证语义动作不会引用还没计算出来的属性值保证语义动作不会引用还没计算出来的属性值1.只需要综合属性的情况只需要综合属性的情况为每一个语义规则建立一个包含赋值的动作，为每一个语义规则建立一个包含赋值的动作，并把该动作放在相应的产生式右部的末尾。并把该动作放在相应的产生式右部的末尾。例如：例如：T

39、T1*FT val:=T1 val*F val转换成：转换成：TT1*FT val:=T1 val*F val翻译模式的设计翻译模式的设计根据语法制导定义根据语法制导定义2023/1/10452.既有综合属性又有继承属性既有综合属性又有继承属性l 产生式右边的符号的继承属性必须在这个产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。符号以前的动作中计算出来。l 一个动作不能引用这个动作右边符号的综一个动作不能引用这个动作右边符号的综合属性。合属性。l 产生式左边非终结符号的综合属性只有在产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。它所引用的所有属性

40、都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的计算这种属性的动作通常可放在产生式右端的末尾。末尾。翻译模式的设计翻译模式的设计根据语法制导定义根据语法制导定义2023/1/1046下面的翻译模式不满足要求：下面的翻译模式不满足要求：SA1A2A1 in:=1;A2 in:=2Aaprint(A in)/*A.in尚无定义尚无定义*/例例6.11从从L-属性制导定义建立一个满足上面属性制导定义建立一个满足上面要求的要求的翻译模式。翻译模式。使用文法产生的语言是数学排版语言使用文法产生的语言是数学排版语言EQNEsub1 val编排结果编排结果2023/1/1047B表示盒子表示

41、盒子BB1B2代表两个相邻盒子的并列，且代表两个相邻盒子的并列，且B1位于位于B2的的左边。左边。BB1subB2代表盒子代表盒子B1后随下标盒子后随下标盒子B2，下标盒，下标盒子子B2以较小的字体和较低的位置出现。以较小的字体和较低的位置出现。B(B1)代表一个由括号括起来的盒子代表一个由括号括起来的盒子B1，主要是为，主要是为了对多个盒子或下标进行分组。在了对多个盒子或下标进行分组。在EQN中，使用花括中，使用花括号进行分组，此处使用圆括号是为了避免跟语义动作号进行分组，此处使用圆括号是为了避免跟语义动作外面的花括号产生冲突。外面的花括号产生冲突。Btext代表文本字符串，即任意字符组成的

42、串。代表文本字符串，即任意字符组成的串。该文法是二义性的文法，将该文法是二义性的文法，将“并列并列”和和“下标下标”看成看成是左结合的，并令是左结合的，并令“下标下标”的优先级高于的优先级高于“并列并列”的的话，则可以对该文法所描述的语言进行自底向上的语话，则可以对该文法所描述的语言进行自底向上的语法分析。法分析。2023/1/1048属性设置属性设置pointsize用于表示盒子中文本的尺寸用于表示盒子中文本的尺寸(以点来计算，以点来计算，也就是字号也就是字号)。如果标准盒子的尺寸为。如果标准盒子的尺寸为p，则下标盒子，则下标盒子的尺寸为的尺寸为0.7p。属性。属性B.ps表示盒子表示盒子B

43、的尺寸，该属性的尺寸，该属性是继承属性。是继承属性。每个盒子都有一个基线每个盒子都有一个基线(baseline)，用来表示每个文，用来表示每个文本底部的垂直位置。本底部的垂直位置。height用来表示从盒子的顶部到基线的距离。属性用来表示从盒子的顶部到基线的距离。属性B.ht表示盒子表示盒子B的高度的高度height，该属性是综合属性。，该属性是综合属性。depth用来表示从基线到盒子底部的距离。用属性用来表示从基线到盒子底部的距离。用属性B.dp表示盒子表示盒子B的深度的深度depth，该属性也是综合属性。，该属性也是综合属性。2023/1/1049表表6.7对盒子进行排版的语法制导定义对盒

44、子进行排版的语法制导定义产生式产生式语义规则语义规则SBB.ps:=10S.ht:=B.htS.dp:=B.dpBB1B2B1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B.dp:=max(B1.dp,B2.dp)BB1subB2B1.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.dpBtextB.ht:=getheight(B.ps,text.lexval)B.

45、dp:=getdepth(B.ps,text.lexval)2023/1/1050SB.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);

46、B.dp:=getdepth(B.ps,text.lexval)从表从表6.7构造的翻译模式构造的翻译模式2023/1/1051TFT.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构造的翻译模式构造的

47、翻译模式2023/1/1052在分析栈中使用一个附加的域来存放综合属性在分析栈中使用一个附加的域来存放综合属性值。下图为一个带有综合属性值域的分析栈：值。下图为一个带有综合属性值域的分析栈：stackval.XX.xY.Y.y.ZZ.ztop6.4.2S-属性定义的自底向上计算属性定义的自底向上计算2023/1/1053 A b:=f(c1,c2,ck)b是是A的综合属性，的综合属性，ci(1 i k)是是 中符号的属中符号的属性。性。综合属性的值是在自底向上的分析过程中，综合属性的值是在自底向上的分析过程中，每次归约之前进行计算的。每次归约之前进行计算的。AXYZ A a:=f(X x,Y

48、y,Z z)A aX xY yZ z2023/1/1054topstackval.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;2023/1/1055例例6.14用用LR分析器实现分析器实现台式

49、计算器台式计算器与表与表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;Fdigit2023/1/1056表表6.8翻译输入翻译输入6+7*8n上的移动序列上的移动序列输入输入 stateval使用的产生式使用的产生式

50、6+7*8n-+7*8n66+7*8nF6Fdigit+7*8nT6TF+7*8nE6ET 7*8nE+6+*8nE+76+72023/1/1057*8nE+F6+7Fdigit*8nE+T6+7TF8nE+T*6+7*nE+T*86+7*8nE+T*F6+7*8FdigitnE+T6+56TT*FnE62EE+TEn62L62LEn2023/1/1058 采用自底向上分析，例如采用自底向上分析，例如LR分析，首先给分析，首先给出出S-属性定义，然后，把属性定义，然后，把S-属性定义变成可执属性定义变成可执行的代码段，这就构成了翻译程序。象一座建行的代码段，这就构成了翻译程序。象一座建筑，语法