基于事件的文档转换：属性求值模式和描述性组合的算法派生

181《理论计算机科学电子札记》44卷第2期（2001年）网址：http://www.elsevier.nl/locate/entcs/volume44.html25页从基于树的规格说明Keisuke NAKANO1Susumu NISHIMURA2，3京都大学数学科学研究所，京都606-8502摘要结构化文档通常由基于树的文档转换器处理该转换器将表示输入文档结构的文档树转换为另一个树结构。相比之下，基于事件的文档转换器将输入识别为解析事件流，即。e. 词法标记，并以事件驱动的方式逐个处理事件。与构建中间树表示的基于树的转换器相比，基于事件的文档转换本文提出了一种算法，它派生出一个基于事件的Transformer，从一个给定的规范的文档转换树结构。在属性图的框架下，推导出了基于事件的转换器Transformer。 我们首先获得一个属性文法，它处理一个流的解析事件，通过应用森林砍伐的方法，然后，我们推导出一个属性评估计划相关的基于事件的转换。使用该算法，可以开发基于事件的文档转换器，这种方式比直接在解析事件流上编程更具声明性。关键词：基于事件的文档转换，属性求值模式，描述性组合，属性文法，XML1介绍结构化文档被广泛用于以传统的文本格式表示分层数据结构。有各种各样的结构化文档，1电邮地址：ksknac@kurims.kyoto-u.ac.jp2电子邮件地址：nisimura@kurims.kyoto-u.ac.jp3部分得到鼓励青年科学家援助赠款的支助，日本文部科学省和日本学术振兴机构，127802162001年由ElsevierScienceB出版。 诉 操作访问和C CB Y-NC-ND许可证。赤野石村182MENT格式，e. G. HTML用于Web表示，LATEX用于排版，最著名的是XML（可扩展标记语言）标准[1]，旨在用作多个平台之间无缝数据交换的公共数据表示。由于以结构化文档格式交换的数据量越来越多，转换结构化文档的技术变得越来越重要。用于文档变换的常规方案是基于树的方案，其中变换被定义为对文档树的操作，文档树对结构化文档的分层结构进行建模。基于树的转换首先在存储器上构造输入文档的文档树，操纵文档树，并将转换后的文档树翻译回结果文档。由于其描述文档转换的高表达性，基于树的转换方案在实践中被广泛使用（例如，G. 、XML转换语言XML [2]和文档对象模型（DOM）[3]）。然而，基于树的转换有一个缺点，即它们必须在开始树操作之前将整个文档加载到内存中。这表明基于树的转换处理的文档的大小当输入文档的大小非常大，或者当内存的大小相对较小时，这可能是一个严重的问题。为了减轻内存使用的压力，Simple API for XML（SAX）[4]被提出作为编程XML文档转换的替代方法。SAXAPI不是构造文档树，而是创建解析事件流（或形式语言理论术语中的词法标记）来通知后端程序当它读取输入XML文档时遇到的语法对象。例如，当使用SAXAPI的程序读取以下文档时 body>我喜欢甜食。/message>它由以下解析事件通知：消息标签的开始、主体标签的开始、字符串“Ilikesweets. ”, end of a 程序以事件驱动的方式处理文档，即：e. ，每个解析事件都由事件处理程序捕获，该事件处理程序负责处理该事件。这里我们面临着效率和表现力之间的紧张关系基于事件的文档转换器Transformer可以显著减少内存使用，特别是对于简单的文档转换。另一方面，基于事件的转换器的表达能力不如基于树的转换器。由于基于事件的转换的结构意识较差，因此基于事件的转换比基于树的转换更难编程，因此它们通常仅用于那些相对简单的转换。此外，基于事件的转换还有另一个缺点，即很难维护：赤野石村183◦◦EventStream基于事件的转换EventStream✻解析❄解析文档树文档树不Fig. 1.文档转换程序代码被分散到响应解析事件的小动作中，因此即使在原始转换程序中添加一个小更改也可能非常麻烦。本文提出了一种算法，自动推导出一个基于事件的文档转换从一个指定的树为基础的transformation。 如果自动获得基于事件的文档转换，这将非常有用。首先，我们同时获得了效率和表现力：一旦我们以基于树的风格指定文档转换，我们就可以从指定中导出可执行的基于事件的转换程序，并且导出的基于事件的转换程序不仅节省了内存空间，而且由于减少了数据管理任务，还节省了执行时间。此外，基于树的规范以声明式的方式给出，比基于事件的文档转换程序更容易维护。1.1毁林我们可以把目前推导基于事件的程序的问题看作是一个森林砍伐问题[14]。Deforestation代表通用程序转换技术，它通过将两个或多个复合函数统一为单个函数来消除中间数据构造。基于树的转换可以用三个函数的组合来表示，如图1中的图表所示。首先，函数Parse将给定的事件流转换为中间树表示。然后，中间文档树由函数T处理，该函数T负责树转换。最后，函数Unparse将结果文档树转换回相应的事件流。 (In本文省略了从输入文档的字符流生成解析事件流的过程，反之亦然。词法分析的标准技术[6]将支持这个过程。）基于树的转换由复合函数Unparse T Parse表示，基于事件的转换的派生只是为了找到一个等效的快捷函数（图中最上面的箭头），它不生成中间文档树。在本文中，我们应用现有的森林砍伐方法的基础上，赤野石村184◦◦形式主义的属性语法目前的问题。从一种语言L1的项到另一种语言L2的项的转换可以由L1上的属性文法（AG）定义，该属性文法的属性值范围在L2上。Ganzinger和Giegerich称这种AG为属性耦合文法[10，11]。让我们写GF表示两个AG的组合，其中输出F的处理是由G来完成的。Ganzinger和Giegerich [10]提出了一种AG森林砍伐方法，称为分解合成，该方法从两个属性耦合的gram-mars的给定合成GF导出单个森林砍伐AG。继Ganzinger和Giegerich之后，人们研究了对分数合成方法的几种扩展和改进[7，8，9]。1.2基于事件的单通道交互式程序用分数合成法求出的森林砍伐后的AGAG只是一个规范，因此不能直接执行。森林被砍伐的AG必须被翻译成一个程序相关的基于事件的文档转换。基于事件的文档转换器Transformer应该是一个单通道交互式程序。如果文档Transformer只遍历输入解析事件的流一次，则称为单遍;如果基于事件的文档Transformer在从输入流读取的同时写入输出流，并响应每个解 析 事 件 ， 则 称 为 交 互 式 为 了 获 得 这 样 一 个 一 次 通 过 的 交 互 式Transformer，我们需要找到一种方法，从森林被砍伐的AG规范中派生出一个适当的属性求值器在导出这样的一遍交互式文档转换程序中的主要困难在于，解析事件的属性值可能取决于随后的解析事件的属性值。我们称这种依赖性为前向依赖性. (Even一个简单的文档转换产生一个AG，其语义规则包含前向依赖性。详见第3.2.1节。）在本文中，我们提出了一个算法，系统地派生出一个一遍互动的基于事件的程序从AG规格。我们通过将每个语义规则分为两部分：属性依赖和值构造来解决上述困难。 前者可以通过静态地查看输入事件流来计算，结果表明依赖模式的范围是有限的。因此，我们可以通过有限状态转换机来建模评估方案，其中状态空间是依赖模式的集合，状态转换由解析事件引起。我们不再需要关心前向依赖，因为状态转换受制于依赖模式，而不是单个属性依赖。属性评价的其余部分，即。e. 通过让每个属性保持部分确定的属性值，为每个转换动态地计算值构造。有限状态机递增地输出转换的结果，赤野石村185a.一b c=0bc..阿代埃阿得埃.. .(a) XML样式表示（b）二叉树表示图二.文档树表示每个转换的结果的确定部分。 本文的技术贡献是给出了一个可判定的终止算法，用于从AG规范产生这样的状态转移机本文的其余部分组织如下：第2节在一个更正式的环境中定义了当前的问题。在第3节中，我们通过一个简单的例子来展示我们的算法。第4节讨论了在我们的框架中可以定义哪些文档最后，第五部分对本文进行了总结。2用于文档转换的AG2.1的数据模型本文中考虑的结构化文档格式是一种类似XML的标记语言，它包括（i）任意但固定的标记名称的有限集合，以及（ii）命名的开始标记和未命名的结束标记。例如，下面是我们格式的结构化文档 a>/> d>/> e>/>/><联系我们每个tagname>表示一个名为tagname的开始标记，而表示一个没有标记名的结束标记。如果开始标记和结束标记在通常意义上是平衡的，则文档是格式良好的。（与XML不同，结束标记以简化操作。在格式良好的文档中，它们确实是冗余信息。）格式良好的文档的深度是嵌套的最大级别，最外层为1。 例如，上面的文档具有深度3本文提出的文档格式是一种理想化的文档格式，为后续的理论研究奠定了基础。它缺少了在真实文档格式中发现的许多有用的功能，但作者相信有可能将它们纳入本文中提出的框架中。我们把这个话题留给未来的研究（见第5节）。赤野石村186联系我们AG：：=letF=SE：ECE：+：：=（occ=exp）|S.结果exp：：=occ|C expr图三. 属性文法记法我们用二叉树对结构化文档的内部表示--文档树进行建模。例如，图2（a）中给出的XML文档树，上面的示例文档由图2（b）中的二叉树表示。在二叉树表示中，每个左分支指向父文档节点的最左边的子节点，每个右分支指向要跟随的第一个兄弟节点。如果一个分支没有相关的节点可供指向，它将指向一个空节点（在图中用点表示）。这两种表示是同构的，因此一种表示上的变换可以转换为另一种表示上的变换。事件流语言和二进制文档树语言的形式定义如下。 假设标签1，标签2，...， 标签n是标签名称的固定集合。事件流的语言由以下集合指定：产 生 式 规 则 {S→E ， E→Begin tag1E ， ·· · ， E→Begin tagnE ，E→EndE，E→Nil}，其中非终结符S是开始符号。每个构造函数Begin标记i对应于一个名为tagi的开始标记，End对应于一个end标签，Nil到事件流的结尾例如，上述示例文档由表达式Begin a（Begin b（Begin a（End（Begin d（End（Begin e（End（Beginc（End（End Nil）表示。类似地，文档树的语言由产生式集合指定。规则{S→D，D→节点标签1D D，···，D→节点标签nD D，D→空}。每个构造器Node标记i对应于一个名为tagi的树节点，一个空节点。2.2属性文法我们的属性语法（AG）符号如图3所示。 AG的定义通过底层语法的产生式规则prod的prod：prod对的列表，以及其相关联的语义规则集。本文将一个产生式规则限制为S→E或E→CE1···Ek（k≥ 0），其中S是起始符号，E，E1，. E k是非终结符，C是数据构造函数。每个语义规则都有occ=e的形式，其中occ是一个属性出现E. a，它表示附加到非终结符E的属性a的值，e是一个表达式，它定义了什么值被分配给出现occ。我们只允许那些表达式是一个引用的属性出现或数据结构Ce1. E K。我们假设一个特殊的合成属性结果只针对启动生产S→E，指定属性评价的总体结果请注意，与传统AG相比，我们允许赤野石村187产生式规则没有对应的语义规则。我们可以显式地写这样一个未定义的语义规则为E. a=undef，它读作如果表达式e1，. e n是unfined，那么表达式Ce1..，n也是不确定的。未定义的属性在定义用于解析的AG中起着至关重要的作用（第2.3节）。代数群需要满足一定的条件，才能应用代数合成方法。最重要的是，原始的功能合成方法要求AG遵守一个称为SSUR的条件[11]。在本文中，我们放松了SSUR条件，以便允许语义组合与未定义的语义规则一起工作[11，pp.378]。在本文的其余部分，我们假设每个AG都满足以下条件：• 它是非圆的[13]，• 满足准SSUR条件。一个AG满足SSUR（syntactic single use requirement）条件[11]，如果一个语法属性的每个不同的出现在每个产生式规则的语义规则的定义表达式中被引用一次。如果属性的范围在单一语言的术语集上，则该属性是句法的。AG满足准SSUR条件，如果恰好一次使用限制放宽到最多一次使用。2.3用于解析和取消解析的现在，我们定义用于解析和反解析的AG，它们对应于函数Parse和Unparse，分别。，如图1所示。为了定义用于解析的AG，我们假设每个格式良好的输入文档都具有小于或等于固定数d（d >0）的深度。 虽然这看起来似乎是有限制的，但实际中使用的大部分文档转换应该由那些输入文档具有有限深度的转换所覆盖。例如，当XML文档用于表示数据库时（这是XML最典型的用法之一！），文档的最大深度主要由文档附带的数据库模式[5]决定。相比之下，用于数据表示的呈现语言（如HTML和LATEX）通常没有有限的深度。然而，一个足够大的数字将作为实际用途的界限。 在本文中，我们不讨论文档的转换任意深度，留待以后调查对输入文档的有限深度限制是导出一遍交互式基于事件的程序的关键。用于解析文档的AG（稍后将给出）包含未定义的语义规则，用于在输入文档具有超出深度时标记错误。这使得我们的算法可以终止，因为静态分析可以停止有限数量的前瞻赤野石村188→→→→→→→→let（d）=S E：S. 结果=E。parseEJ.stack h1=undef.EJ.stack hd=undefE开始标记1EJ：E. parse=Nodetag 1EJ. 解析EJ.stacks1E.stack s1=EJ.stack s2.E.stack sd−1=EJ.stack sdE.stacksd=undefEJ.stackh1=EmptyEJ.stackh2=E.stack h1.EJ.stack hd=E.stack hd−1.E结束EJ：E. parse=E.stackh1E.stack s1=EJ. 解析E.stack s2=EJ.stack s1.E.stack sd=EJ.stacksd−1EJ.stack h1=E.stackh2.EJ.stack hd−1=E.stack hdEJ.stack hd=undefE无：E. parse=空E.stack s1=undef.E.stack sd=undefEBegin tagnEJ：（定义同上）图四、用于解析的AGletunparse =.S→T：S. 结果= T。解析T.acc=NilT节点标记1T1T2：T. unparse= Begin tag 1T1.unparseT1.acc= EndT2. 解译T2.acc=T.accT节点标签nT1T2：（与上面的定义类似）T空：T. unparse=T.acc图五、用于解解析的AG事件到输入解析事件流中。图4定义了一个AGParse （d），它处理深度为d或更小的文档，并生成一个文档树。合成属性集堆栈 s1，. . . stack s d模拟深度为d的有限堆栈，其中堆栈s1是堆栈顶部。每个属性堆栈s，i保存解析兄弟节点的结果，兄弟节点位于包含当前解析点的第i个外部开始和结束标记对之后。将d个以上的元素推入堆栈会导致溢出，溢出的数据会丢失。输入文档的超出深度由未定义的属性值undef标记，该属性值表示一个pars-赤野石村189◦◦ing错误。不平衡标签以类似的方式被由继承属性栈h1，. . . ，stack h d.开始标记的每个解析事件都会将一个空节点推到堆栈上，当匹配的结束标记出现时，它将被弹出并用作子节点的结尾。图5定义了AGunparse，它从给定的文档树中生成解析事件流与解析相反，这个AG总是成功地产生结果，而不管输入文档树的深度。AG旨在对文档树执行深度优先遍历。深度优先遍历的结果被累积到继承的属性acc，并且累积的结果将被传播到文档树的根作为最终结果。2.4XML文档转换现在要解决的问题正式表述如下：给定一个复合形式的document变换的具体形式，不pares（d），其中d是输入文档的最大深度d，T是表示基于树的变换的AG，导出一个单路径交互式基于事件的文档变换程序，该程序为深度d或更小的每个输入文档计算复合规范所期望的结果。注意，输出文档可以具有任意深度，而与输入文档的深度无关。3该算法本节介绍了一种算法，用于导出一次通过的基于事件的文档，从树变换的一个复合具体化中得到的一个变换程序。在本节中，我们用恒等变换Tid解释我们的算法，其平凡AG定义为下面，我们举一个例子。letid=S→T：S.结果=T.itT→节点AT1T2：T.it=节点AT1.it T2.it T→节点BT1T2： T.it=节点BT1.it T2.it T→空：T.it=空(We为了简单起见，我假设只有两个不同的标记名，A和B。）我们注意到运行示例的选择仅用于说明目的。即使是一个简单的例子也足以说明目前问题的困难是什么以及我们如何解决这些问题。我们的算法可以应用于满足2.2节条件的AG指定的任何变换。我们将在第4节讨论在这种限制下可以表达什么样的变换。赤野石村190◦◦◦◦◦我们的算法由三个阶段组成。第一，D_o_cume_t变换的非近似复合规范不通过应用所述组合物，将参数e（d）统一到单个森林砍伐AG中。其次，将产生的AG进一步转换为表示文档转换的有限状态转换机。最后，我们从有限状态转换机获得一个单通道交互式基于事件的程序。我们将依次解释每个阶段，并在本节的其余部分中观察通过我们的算法获得让我们定义一些符号。一个函数f称为有限映射，如果它的定义域，记为dom（f），是一个有限集。我们通常记为{x1<$→v1，. xn <$→v n}表示有限映射f，使得dom（f）={x1，.，xn}和f（xi）= vi. 对于任何有限映射f和g，使得dom（f）dom（g）/=f，fg表示满足dom（h）=dom（f）≠dom（g）的有限映射hsuch当x∈dom（f）时，h（x）=f（x）;当x∈dom（g）时，h（x）=g（x）.3.1描写成分在推导的第一阶段，我们从以下复合规范中获得一个单一的森林砍伐AG，它不产生任何中间数据：一个文档转换。为此，我们简单地应用现有的分数合成方法对本问题。 本节 不打算是正式的，但通过运行的例子给出一个简短的总结的概念组成方法。对于算法的详细、正式定义，读者可以参考[10，11，8，9]。为了从复合规范unparseTparse（d）中获得单个森林砍伐的AG，我们需要两次应用复合规范：首先将T与parse（d）复合，然后与所得的AGunparse。 对于运行的例子，恒等变换T id和AGpars e（d）的组合恰当地导致pars e（d）。 4因此，我们将通过unparse和parse（d）的合成来解释概念合成。该组合物通过三个步骤得到单一的森林砍伐AG设F和G是合成GF的两个AG。在我们的运行示例中，F是pars e（d），G是un pars e。 在本节的其余部分中，为了简单起见，我们假设d= 2。投影第一步是投影，其导出组合AG的中间表示，其中两个AG之间的中间数据构造尚未消除。在中间表示中，我们暂时写e. a来表示任意表达式e上的属性出现。中间表示是通过将G的每个属性映射到F中的每个语义规则N. a=e上而得到的，[4]我们没有展示这种合成的过程，它比下面介绍的简单赤野石村191→→→→→形式（N.a）.b=e.b（e.b=（N.a）.b，resp. “凡所有相，皆是虚妄”。）G的 属 性 b 。 例 如 ， 将 unparse 的 属 性 投 影 到 语 义 规 则 E.parse=NodeAEJ.parse EJ.stack s1上，productionEBegin AEJ ofparse，我们得到以下新的语义规则：（E.parse）.unparse=（Node AEJ.parse EJ.stack s1）.unparse=（Node AEJ.parse EJ.stack s1）.acc=（E.parse）.acc开始生产与其他生产不同。首先，从语义规则中移除用于F的开始产生式的语义规则S.result=e F，并将投影算法应用于其余的语义规则，如对其他产生式规则所做的那样。然后，将G的开始产生式ST的语义规则添加到F的投影语义规则中，并且将对G的T. a形式的属性a的每个引用替换为e F.a，即，e. ，中间结果上的相应属性。5如果应用于运行的示例，则投影会导致以下开始产生式S→E的新语义规则。S.result=（E.parse）.unparse（E.parse）.acc=Nil在这个特殊的例子中，没有来自F的投射规则，因为在F的开始产生式的语义规则中没有定义除了结果之外的属性。象征性的评价。 第二步是符号求值[8，9]，它消除了在前一个投影步骤中导出的形式（Ce）.a的表达式。考虑上面为产生式EBegin AEJ规划的语义规则。它们包含相同中间数据结构的属性（下划线部分）。设T节点AT1T2为构造的产生式规则，T=（节点AEJ.parse EJ.stack s1），T1=EJ.parse，T2=EJ.stack s1。根据以下公式，该中间数据构造的相应语义规则由以下公式给出：unparse的定义。（Node AEJ.parse EJ.stack s1）.unparse=Begin A（（EJ.parse）.unparse）J=（EJ.parse）.acc=End（（EJ.stacks1）.unparse）（EJ.stack s1）.acc=（NodeAEJ.parse EJ.stack s1）.acc通过合并EBegin和EBeginJ，并利用等式的传递性去掉带下划线的表达式，我们可以取消中间的数据构造，并得到产生式EBegin AEJ的一组新的语义规则。（E.parse）.unparse=Begin A（（EJ.parse）.unparse）（EJ.parse）.acc=End（（EJ.stack s1）.unparse）（EJ.stacks1）.acc=（E.parse）.acc[5]这是[9]中描述的剖面符号评估的特殊情况赤野石村192→→→→→···◦letident=S E：S. 结果= E。s1E. h1=NilE.h2=undefE.h3=undefE.h4=undefE.h5=undefEBegin AEJ：E. s1=BeginAEJ. s1E.s2= EJ. S4E. s3= EJ. s5E.s4=undefE. s5= undefEJ.h1=结束EJ。s3EJ.h2= EJ. s2EJ. h3=E. h1EJ. h4= E.h2EJ. h5= E. H3EBegin BEJ：E. s1=开始BEJ。s1E. s2= EJ. S4E. s3= EJ. s5E.s4=undefE. s5= undefEJ.h1=结束EJ。s3EJ.h2= EJ. s2EJ. h3=E. h1EJ. h4= E.h2EJ. h5= E. H3E结束EJ：E. s1=E。h2E. s2=E.h1E. s3=EJ.s1E. s4=EJ.s2E. s5=EJ.s3EJ. h1=E.h3EJ. h2=E.h4EJ. h3=E.h5EJ. h4=undefEJ.h5=undefE无：E. s1= E。H1E.s2=undefE. s3=undefE. s4=undefE.s5=undef见图6。 分数合成我们可以通过对F中每个产生式规则的每个投影语义规则重复上述重写过程来消除所有中间数据结构。请注意，由于我们允许未定义属性，因此投射的语义规则集可能没有语义规则（Ce1en）。一些继承的属性h，其中属性h需要被定义根据G.在这种情况下，任何子表达式（Ce1···en）.h都应该被理解为表示一个未定义的值。改名概念合成的最后一步是重命名。此步骤通过将连续的两个属性名称组合成单个属性名称，将形式为（x.a）.b的任何连续属性重写为单个属性x.ab。将该方法应用于非线性光学系统，parese （d）（在属性名上进行α转换之后）如图6所示。注意，准SSUR条件在整个合成过程中被保留，即。e. ，所得到的AG也是准SSUR。3.2导出基于事件的转换程序我们算法的第二阶段生成一个有限状态转换机，用于从上一阶段获得的森林砍伐的AG进行基于事件的一次属性评估。设GF表示森林被砍伐的AG。我们可以观察到，森林被砍伐的AGGF的输入和输出都是事件流，并且每个at-赤野石村193→→S→EE→Begin AEJE→Begin BEJE→结束EJE →无见图7。属性依赖图GF的贡献范围在事件流的集合上。在下文中，我们将生成规则C写成表示对应于生成规则的语义规则集。 到事件流的每个构造器C。每个定义语义rule或者是对属性出现的引用，或者是事件流构造。我们假设{syn1，.，syn s}是合成属性的集合，并且{inh1，...，inh h}是GF的继承属性的集合。3.2.1基于图的依赖分析为了澄清从AG规范生成基于事件的程序的困难，并说明我们算法中的关键思想，我们用图7表示每个产生式规则的语义规则集。 在这个图形表示中，我们只关心属性出现之间的依赖关系，暂时忽略了语义规则的计算。每个图形表示由两个（或一个）水平条和一些依赖性边组成。对于形式为ECEJ的每个产生式规则，其中E和EJ是非终结符，C是数据构造函数，E上的属性出现被放置在上部条上，而EJ上的属性出现被放置在下部条上。（ 生产规则E没有下条无）每个依赖性边连接两个属性，这两个属性由条形图上我们将合成的属性放在左边，赤野石村194≥→→解开=(a) S→E，E→开始AE′(b) S→开始AE见图8。解开依赖图在每个酒吧的右边。数据流的方向由每个三角形标记的顶点指示。请注意，由于定义属性值的每个表达式要么是对属性实例的引用，要么是对数据构造的引用，因此每个属性实例最多依赖于单个其他实例。(An只有当出现的语义规则被定义为occ = C1（.）时，属性出现occ才没有传入边。（CkNil）.. . ）（k0）.）因此，任何属性都没有两个以上的传入边。此外，由于准SSUR条件，没有属性具有两个以上的离开边。我们称属性依赖为前向依赖，如果它从一个合成属性出发例如，产生式规则Begin A的依赖关系图包含两个前向依赖关系边，在下条上从s2到h2以及从s3到h1。前向依赖性对于一次属性计算来说是很麻烦的。在本例中，假设当前事件是Begin A。要完成当前事件的处理，一次传递属性计算器需要h2和h1的值，这些值将被传递以处理下一个事件。然而，h2和h1的值分别依赖于s2和s3。，其值仅在处理下一个事件后获得。因此，一遍求值器卡在这里。为了找到一个一遍属性评估策略的AG包含向前依赖，我们的算法执行一个分析，利用静态前瞻到输入事件流。静态分析基于将两个连续产生式规则的语义规则集合合并为单个规则的过程。假设输入流的请求是一个解析事件Begin A。对应的语法产生式是SE后跟E开始AEJ。 这些成果促进了属性评价的两个步骤图8（a）显示了依赖性。 该图是通过粘贴后一个产品的依赖图在前一个产品的依赖图之下。这个粘贴图被统一成一个单一的，通过省略中间条（对应于中间生产），然后采取传递⇒赤野石村195DDD→q0结束，无年q3年q4结束，无开始_A开始_B结束，无开始_A开始_B端无年q1无Q2开始_A开始_B端Q5开始_A开始_B无端开始_A开始_B开始_A开始_B解开=(a) S→开始AE，E→结束E′(b) S→结束E图9.第九条。通过解缠探索新的解析状态图10个。的状态转换图依赖边缘的闭合（图8（b））。我们把这个取传递闭包的过程称为解纠缠过程。在下文中，我们用有限映射表示依赖图，其中对于属性定义依赖于occJ的每个occ，（occ）=occJ;如果occ不依赖于任何出现，我们写（occ）=none，其中none是一个特殊的符号，表示没有依赖关系。3.2.2生成有限状态转换机我们的算法构造了一个属性评估器，把每个属性依赖图所产生的解纠缠过程中的一个新的状态的解析表示。例如，假设我们处于图8（b）中依赖关系图所表示的解析状态，下一个事件要跟进。为了获得新的解析状态，我们再次应用解纠缠过程，即。e. ，最后一个解纠缠图（图8（b））和产生式规则EEndEJ的依赖图被粘贴在一起（图9（a）），然后它们被解开。新的解析状态由图9（b）中的曲线图表示。请注意，该图同构于开始产生式的图，因此我们处于与解析的初始状态等价的状态。我们的算法构造了一个解析器的属性评估⇒赤野石村196◦◦ ◦ ◦ ◦◦所有可能的依赖图，从依赖图开始制作。该算法检查每个可能的下一个解析事件（即，开始标记1，. . 、开始标记n、结束和无）。由于只有有限数量的属性，因此只有有限种类的依赖图，因此这个过程必须终止。对于正在运行的示例，我们获得了6种依赖关系图模式，如图10所示。将每个图视为解析的状态，我们可以将图10的图表视为有限状态转换机。从初始状态q0开始，机器根据要读取的解析事件重复改变其状态，沿着标有事件名称的箭头。当到达最终状态时，机器终止;如果属性结果没有依赖边，则依赖图表示有限状态。在图中，最终状态由双线框定虽然状态转换规则可以通过分析属性依赖关系来静态确定，但如何计算转换过程中的属性值仍然是一个悬而未决的问题。本文的解决方案是让每个属性携带一个部分评估值。部分计算的值由一元函数表示，该函数在应用时返回完全计算的值 设置为尚未计算的属性的值由于语义规则仅限于事件流构造，部分评估值的函数表示可以表示为由有限数量的函数常数组成，开始标记1，...，开始标记n、End、Nil 、Id 和 Undef ， 其 中 最 后 三 个 常 量 应 理 解 为 函 数 Nil=λx 。 Nil ，Id=λx.x，Undef=λx.undef（i. e. 一个不为任何输入定义的函数），分别。我们可以将函数常量Begin tag1，. 作为元符号，并作为一个复合运算符在他们身上，其中该运算符是联合和一些额外的等式Id f= fId =f，无f= Nil，Undeff= fUndef=Undef保持。 我们称这种表示为部分求值属性的符号表示。 我们可以假设每一个语义规则都以如下形式occ=（C1···CkNil）（无）或occ=（C1···Ck）（occJ），其中C1，...，Ck（k≥0）既不是Nil也不是Undef。状态转换机改变了park的语法表示在状态转换期间，只传递继承属性的部分求值值。我们使用元变量Xinh1，.，X inhh表示继承属性的那些部分评估的值，并且元变量可以以符号表示出现，以引用从先前解析状态传递的继承属性的部分评估的属性。下面给出了有限状态转换机的定义定义3.1（有限状态转换机）设FRep表示形式为{result → f0，inh 1→ f1，.的有限映射的集合，inh h<$→ f h}，它为每个属性分配一个符号表示f i。有限状态转移机是七元组M=（A，Q，q0，T，δ，Γ，γ0），赤野石村197∈→→D×→∈⊆D/D◦联系我们/◦⇒∈⇒∈其中A是输入解析事件的集合，Q是状态的集合（依赖图的模式的集合），q0（Q）是初始状态，T（Q）是最终状态的集合，δ是表示状态转换规则的集合的有限映射Q A Q，Γ是表示用于计算每个状态转换的部分评估的属性值的符号表示的规则的集合的有限映射Q（A FRep），并且γ0（FRep）是给出初始符号表示的有限映射。如果当前状态是q，并且要读取的下一个解析事件是C，则状态转换机转换到状态δ（q，C）。新状态的符号表示由有限映射Γ（q）（C）给出。 对于运行的示例，当机器在初始状态q0读取解析事件Begin A时，符号表示由以下给出：{result<$→Begin A，h1<$→End，h2<$<$→Id，h3<$→Xh1，h4<$→Xh2，h5<$→Xh3}，其中元变量X h1，X h2，X h3 最初的象征性代表，在这种情况下，对应的继承属性的sentation。在状态转换期间，有限状态转换机不保存值除了结果之外的合成属性，因为结果是与最终转换结果唯一相关的合成属性。其他合成属性的值通过解缠过程与结果或固有属性hi为了给出一个生成这样一个有限状态转移机的算法，我们首先定义一个解纠缠的过程DISENTD，C上标是表示当前解析上下文的属性依赖图，C是要读取的下一个解析事件。设E→CEJ（或E→Nil）为对应的产生式规则和CQC是相关联的语义规则的集合。算法1（解开）程序DISENTD，C（occ）输入occ：要分离过程DISENT2（occ，f）案例发生率S.resultif（S.result）=nonethenDISENT2（（S.result），Id）else return（none，Id）E.inhj如果D（E.inhj）无，则DISENT 2（D（E.inhj），f<$Xinhj）else return（none，f Xinhj）E.synk如果E.synk=fJ（occJ）<$C，则如果occJ=none，则DISENT2（occJ，ffJ）return（none，ffJ）return（none，f）如果EJ.inhj=fJ（occJ）<$C，则如果occJ=none，则DISENT2（occJ，fJ）return（none，fJ）else return（none，Id）赤野石村198⇒→F∈∈D端C如果C（S.结果）=无，则T：=TCDEJ.synk返回（E.synk，f）端returnDISENT2（occ，Id）端过程调用DISENT D，C（occ）遍历属性依赖关系并返回一对（occJ，f）属性出现和符号表示：occJ是occ依赖的出现，f是函数的符号表示，该函数取occj的值并计算occ的值。现在，我们准备提出将森林砍伐的AGGF转换为有限状态转换机的算法。算法2（有限状态转移机构造）设D0和0分别为起始产生式SE的属性依赖图和符号表示，即. e. 、.D0（occ）=occJ（ifocc=f（occJ）<$S）无（否则）f（如果a=result且S.result=f（occ）∈S）F0（a）=g（如果a=inhi且E.inhi=g（occ）S）Undef（否则）其中，STOS是用于开始产生式的语义规则集。该算法由以下过程MakeFSTM定义。过程MakeFSTM（GF）输入GF：由分数合成A：={开始标记1，...，开始标记n，结束，无};Q：={D0};q0：=D0T：=0;δ：={};Γ：={};γ0：=F0当存在D ∈Q使得Γ（D）不被定义时，ΓD：={}对于每个C∈A，D：={};FC：={}（occ，f）：=DISENTD，C（S.result）;C C CD：= D{S.result<$→occ}; FD：= FD{result <$→ f};如果C/=Nil，则对于每inhjdo（occ，f）：=DISENTD，C（EJ.inhj）;C C C端：= D{E.inh j<$$> →occ}; FD：= FD{inh j<$→f}δ：=δ{（D，C）<$→DC}; ΓD：= ΓD{C<$→FC};Q：=Q<${DC} D<${D}r：= r{D <$→Γ D}D端赤野石村199DDMD ∈{|D ∈\ }returnM：=（A，Q，q0，T，δ，Γ，γ0）过程MakeFSTM从初始依赖图D0开始枚举所有可能的属性依赖图。对于每个依赖图D，它依次检查每个解析事件C作为要读取的可能解析事件，并计算新的依赖图DC和新的解析事件C符号表示的赋值FC如果C=Nil，由于没有解析事件之后，我们不需要计算继承属性的赋值inh1，.，印 河依赖图C被添加到最终状态的集合T，如果它对于出现S.result没有依赖性。重复这个过程，直到没有生成新的依赖图在Kastens的访问序列构造[