高效无扫描句法分析算法研究及实现

理论计算机科学电子笔记253（2010）135-148www.elsevier.com/locate/entcs具有规则右侧的高效Earley句法分析特雷弗·吉姆1 伊扎克·曼德尔鲍姆2AT T实验室研究摘要我们提出了一个新的变体的Earley解析算法能够有效地支持上下文无关的语法与常规的右手边。我们提出了核心的状态机驱动的算法，翻译的语法到状态机，和重建算法。我们还包括一个理论框架，提出的算法和评估优化。最后，我们通过测试其实现评估算法。关键词：上下文无关文法，Earley句法分析，规则右侧，无扫描句法分析，转换器，增广迁移网络1介绍本文介绍了一种新的语法分析算法，它具有三个重要的特点：它处理任意上下文无关的语言，它支持无扫描的语法分析，它直接处理规则的右侧语法。在为网络协议（如HTTP、邮件和VoIP（SIP））中使用的消息格式生成解析器时，这些特性都会发挥作用。这些格式由英语规范文档中的语法定义，称为“请求评论”。这些语法旨在作为文档，因此不遵守编程语言社区中使用的解析器生成器通常施加的限制。语法不能直接由现有的解析器生成器处理，因此解析器通常是手工编写的，这是一个容易出错的过程，可能会导致互操作性问题。我们的算法可以处理这些1电子邮件地址：trevor@research.att.com2电子邮件地址：yitzhak@research.att.com3有一些工具可以将RFC语法作为输入，但由于语法的二义性，它们不能生成正确的解析器。1571-0661© 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2010.08.037136T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135语法直接，而不需要任何手工重写-一个重要的考虑，因为语法是复杂的，模糊的，和大的，有数百个非终结符。这些特性在其他领域也很有用，比如解析编程语言。许多其他人已经指出了使用任意上下文无关语言解析器[9]和无扫描器解析器[12]用于编程语言的优点，但常规右侧不太受欢迎，并且不太受解析器生成器的支持。规则右边的主要优点是它们比非规则的等价物更简洁和可读。文档中的语法通常使用规则的右侧这一事实证明了这一点。这不仅包括我们已经提到的评论请求，还包括编程语言文档。例如，Python，Haskell，Ocaml，甚至Pascal在它们的官方语言规范中使用某种形式的常规右侧语法当语言以更严格的语法形式体系进行文档化时，这通常是明确的，以便它们的语法可以与解析器生成器一起使用最著名的例子是C，其语法被制定为与YACC兼容[6]（参见Kernighan和Ritchie的附录B [8]）。 这是方便对于编译器作者来说，但对于更大的C程序员我们的解析器基于Earley它们是无扫描器的，因此它们不需要将语法规范分成单独的词法分析和解析阶段（尽管如果需要，可以使用词法分析器）。最后，它们直接处理规则的右侧，而不需要将直接处理常规右侧很重要，原因有二。首先，去糖化引入了解析器生成器在将去糖化的语法与原始语法相关联以处理语义动作、报告错误以及可视化和调试解析过程方面的困难。第二，也是更重要的一点，去糖会导致解析器效率降低。直观地说，这是因为当语法有更多的歧义时，解析器必须更加努力地工作。正则表达式是一个非常重要的-双金属（例如，（x））和去糖促进这些歧义进入语法非终结符，也就是解析树。我们的基准测试显示，脱糖的开销为22从理论上讲，我们的解析器与Woods [13]的增强转换网络（ATN）关系最密切，它也直接处理常规右侧，并且以前曾用于Earley解析[2]。我们的形式主义使用了一种新的有限状态转换器，它允许我们表达一些优化，这些优化显著提高了ATN的性能。其中一些优化类似于Aycock和Horspool [1]的Earley解析器所使用的优化，不直接处理常规右侧。在本文中，我们提出并评估新的Earley分析算法。在第二节中，我们介绍了一个新的分析转换器，并提出了一个非确定性分析算法，其中转换器作为下推au的控制T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135137|S = A |xyA= |BACB = xC = y图1.一、 语法xnyn|x=y; S是起始非终结符。番茄。我们形式化了语法和解析转换器之间的关系，并指定了一个给定的转换器将解析一个给定语法的语言的充分条件。在第3节中，我们提出了一个算法，用于构建一个适当的转换器给定的语法作为输入。在第4节中，我们提出了一个决定性的，Earley式的，识别算法的基础上解析转换器，并表明，对于一个给定的转换器，它识别相同的语言作为nondeterministicitic下推算法。在第5节中，我们描述了如何调整解析算法，并提出了一个解析重建算法。我们在第6节中通过将其性能与以前的方法进行比较来评估解析算法，并在第7节中讨论相关工作。2基础在这里，我们奠定了我们的解析算法的理论基础，由于空间的限制，省略了证明。2.1语法和语言文法G是一个四元组（A， Δ，A0，L），其中• 是一组有限的终端;• Δ是非终结符的有限集合;• A0∈Δ是起始非终结符;• L是（环Δ）上的正则语言族，索引为Δ：L A0，. . .我们使用A，B，C来对非终结符进行范围划分，使用x，y，z来对终结符进行范围划分，使用w来对终结符序列进行范围划分，使用W来对终结符和非终结符序列进行范围划分是空序列。对于每个非终结符A，我们通过同时归纳法定义一个语言LAw0A1w1· · ·Anwn∈LA，wi∈LAi对所有inw01<$w1· · ·wn<$wn∈LA（n≥0）G的语言被定义为起始非终结符A0的语言：LA0.图1给出了xnynxy语言的一个语法示例，使用正则表达式将非终结符的右侧写成2.2解析转换器我们的解析器与Woods的增强转换网络（ATN）密切相关。ATN是下推机，其控制由一组自动机提供，每个自动机对应于文法的每个非终结符;138T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135⇒输入 s→xt（s，α）<$x（t，α）呼叫s−ca→llt（s，α）（t，tsα）重置s›→A，t→Au（s，tα）（u，tα）RETURNs›→A，v→Au（s，tvα）（u，α）图二. 句法分析转换器对应于它的正常右侧。我们使用这种方法的推广，用transduc- ers代替自动机，也就是说，自动机输出。一般来说，变换器可以在转换和最终状态上有输出，但是为了我们的目的，这里只考虑最终状态上的一个parsingtransduc erT是一个8元组（A，Δ，Q，A0，q0，→，−ca→ll，<$→），其中• 是一组有限的终端;• Δ是非终结符的有限集合;• Q是状态的有限集合•A0∈Δ是起始非终结符;• q0∈Q是初始状态;• →Δ） ×Q是跃迁关系;呼叫• −→Q ×Q是调用关系;• <$→ Δ Q × Δ是从最终态到非终结态的输出关系。我们用q，r，s，t，u，v来排列状态，用α，β，γ来排列状态序列，如果（q，W，r）∈ →，我们写q→Wr。一个配置是一个对（q，α），其中α就像一个向左增长的堆栈。图2定义了一个配置的单步评估关系式- 多级评价关系，”““像往常一样定义。请注意，多步求值关系定义了一种不确定性算法，用于使用解析转换器解析输入四个求值规则中有三个（几乎）是普通的：INPUT消耗input的一个字符;CALL不确定地在当前输入位置开始解析非终结符，在堆栈上记录一些状态;RETURN检测到非终结符已经正确解析（通过到达一个非终结符作为输出的状态来指示）并弹出堆栈。有一个转折：当一个新的解析开始时，CALL将调用方和被调用方都RETURN使用调用者找到下一个状态（ RESET使用被调用方来找到下一个状态，但不弹出堆栈。正如我们将在讨论中看到的在图4和第3节中，这为在构建转换器时左分解语法提供了更多的机会。最后y，LA（q），A在q处的语言，is{w|（q，q）w（r，q），r<$→A}，以及转换器的语言LT=LA0（q0）。注意我们从q开始求值T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）1351393、→→yX4（A呼叫5AB15C6（A呼1X3一y2（S9y10（C）呼8（BX7呼Xx787 8 44515y9106y9104 5B A1B A一C15 6C2图3.第三章。 用于解析xnyn的转换器|xxyy，以及x x y y 的换能器评估。在堆栈上;假设总是有一个被调用者在堆栈的顶部， 供规则重置使用。图3给出了用于解析图1的语言的转换器，并以图形形式给出了转换器评估。这种特殊的换能器大致相当于伍兹的ATN公式。 伍兹对每个右侧使用了一个不相交的自动机，我们在图中将这些自动机框起来：节点1，4，7和9分别对应于S、A、B和C的自动机。 在评价中，- 边表示呼叫，- 边缘表示返回，箭头标记为非终结符表示由返回完成的解析，标有端子指示输入。此评估中不使用规则重置图4给出了一个更有效的转换器。在这个转换器中，不再有对应于右手边的不相交状态机.例如，状态8开始A和B的同时解析，并且状态1开始S、A和B的同时解析（具体地，S的解析B是左因子分解的）。评估使用重置规则三次，由虚线箭头指示。请注意，计算时间较短，堆栈不会像第一次计算时那样增长。在第3节中，我们描述了一种算法，用于构建像这样的优化传感器2.3语法和转换器我们的例子表明，可以有多个转换器能够解析语法。在这里，我们概述了足以确保语法和转换器接受相同语言的条件。这些条件基本上说： 在被访者处，转换器的频率引起右手侧的语言。一个重要的结果是，像确定化和最小化这样不改变由诱导的语言的转换可以用于优化转换器。对于→的迭代组合，我们写为→W，并定义LA（q）={W|140T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135yX3（BXX4y2（S1（阿、A，yB5调用B8（AX9（B7呼叫C11y10（C）6（AyX1 35一BX88 9 5一B111076Cy11107 6 2C图四、一种用于解析xnyn的优化转换器|xxyy，以及对 xx y y 的评估。呼叫q→Wr→A}。如果q = q 0或q r，则Wesayq是一个cal ee。r−→q。我们是一个语法变换器T=（n，Δ，Q，A0，q0，→，-ca→ll，<$→）是语法的变换器如果下列条件成立，则G=（λ，Δ，L，A0）。（T0）LA0（q0）=LA0。（T1）如果q是被调用方且q→Ar，则LA（q）=LA。（T2）如果q→Wr→As，则对于某个t，r−ca→llt，其中LA（t）=LA。（T3）如果q是被调用者，则对于所有A，LA（q）<$LA。定理1若T是G的变换子，则LT= LG.3从语法到转换器有很多方法可以为语法构建转换器，只需记住我们需要满足条件T0 构造一个如图3所示的转换器（对应于伍兹ATN）很容易：使用标准方法将每个语法右侧转换为确定性有限自动机，将最终状态标记为输出其相应的非终结符，并将每个状态的调用T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135141→→→→|→ → →→对于每个非终结符A，设A是一个新的状态对于每个规则A=r，设（s，F，E）=conv（r）建立sA→sE，F›→A其中thompson（A）=设s，F为新状态Builds→AFs呼叫sA返回s，Fconv（r）=设s，F，E为新态情况r=A：构建s→AFssA（E断开）情况r=0：构建服务器（F断开）情况r=x：构建sxF（E断开）情况r=（r2r3）：设 s2 ， F2 ， E2=conv（ r2 ） 设 s3 ， F3 ，E3=conv（r3）设scalll，Fcall=thompsonn（r3）Builds→Builds2F2 →E2→E3F3，Fcall→FE3→E情况r=（r2）：设s2，F2，E2=conv（r2）设fcall=thompsonnn（r2）版本s，E2→版本s2s，E2→β-EF2，F call→s callF2，F call→F情况r=（r2r3）：设 s2 ， F2 ， E2=conv（ r2 ） 设 s3 ， F3 ，E3=conv（r3）构建s→构造s2，s3F2，F3→F3E2、E3→β-E返回s，F，E。图五.将常规的右侧文法转换为转换器，转换器构造中包含了转换器转换。注意，我们只给出了非终结的thompson函数。构建一个优化的传感器，如图4所示，只是稍微复杂一点。这个想法是为了避免连续的调用序列，本质上是替换任何s呼叫t打电话给你呼叫t你好 我们的算法如图5所示。 它的输入是一个由（语法）规则右侧定义的语法，它的输出是一个带有转换的转换器。我们通过应用标准的确定和最小化变换获得语法的解析转换器（满足条件T0关键过程是conv（r），它产生一个三元组（s，F，E）状态。 状态s是r的初始状态，F和E是最终状态。 该构造确保从s到F的所有路径包含非调用、非转换转换，并且从s到E的所有路径仅包含转换。此不变量用于以下情况r=（r2r3）和r=（r2r 3），以确保条件T2。函数thompson是用于计算正则表达式的Thompson142T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135∈∈›→INIT（q0，0）∈E0SCAN（t，i）∈Ej−1t→xjs（s，i）∈Ej（t，i）∈Ejt−ca→lls预测（s，j）∈Ej完备（t，k）∈Ejt→A（u，i）∈Eku→As（s，i）∈Ej见图6。 Earley集一个NFA [11]的压缩，扩展为非终结符A的情况：它产生A-转换和调用-转换。相反，conv（A）使用一个转换转换而不是调用转换. 请注意，thompsonn用于r=（r2r3）和r=（r2）而不是精确地conv以确保T2。4转换器的Earley语法分析Earley解析是一种自顶向下的解析方法，可以解析任何上下文无关语言[5]。 它对输入字符串的所有可能的最左边的派生执行广度优先搜索。 Earley解析的上限为O（n3），其中n是大小Earley证明了他的算法对于unam-bibliographs文法在O（n2）时间内有效，对于一大类文法在线性时间内有效。我们的Earley版本保留了O（n3）的上限。在本节的其余部分，我们将展示如何将Earley解析应用于解析转换器。4.1Earley集对于输入x1x2. xn，我们将Earley集定义为满足图6规则的最小集。 每个元素（q，i）Ej被称为Earley项，表示从输入位置i开始并已进展到位置j的解析，导致换能器状态q。因此，规则INIT表示我们在状态q0中从输入位置0开始解析，SCAN对应于INPUT，PREDICT对应于CALL。规则完成对应于返回和重置，其中从i开始的解析的返回地址从集合Ei中找到。从技术上讲，Earley集合构造定义了一个识别器，它接受一个输入，如果（q，0）En，其中q A0。 为识别的输入构建解析树需要更多的工作，我们将在第5节中讨论。定理2如果T是G的变换子，则W被Earley集接受，Ti∈G.T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135143∈∈→→NNCOMPLETE（t，k）∈Ej t→<$A（u，i）∈Eku→As（s，i）∈Ej（t，i）∈Ejt−ca→lls<$→At→Au（j/=k）恩卡勒恩卡莱（u，i）∈Ej（t，i）∈Ejt−ca→lls<$→A s→Au（u，j）∈EjNINITq0<$→A q0→Ar（r，0）∈E0图第七章处理可空符号的规则4.2创建Earley集Earley集可以通过首先En的顺序如下：(i) 对于当前集合Ej，应用规则PREDICT并完成，直到不能添加更多的项。(ii) 使用扫描来播种Ej+1。众所周知，当文法具有可空非终结符时（A可空，如果A是空的），该算法是无效的。如果在E j中调用一个可空的A，它也将返回到Ej，没有消耗任何终端。这意味着将在j = k时调用complete。不幸的是，COMPLETE需要考虑完整的集合Ek来寻找A-转换，如果j = k，那么Ek实际上就是正在构造的集合。因此，可空非终结符需要额外的处理。出于这个原因，我们的算法将完整的规则替换为图7中的规则。规则NNCOMPLETE只是非空A的COMPLETE的特殊情况.其余的规则处理空完成。NCALLER将 PREDICT 与 immediateCOMPLETE 组 合 到 调 用 方 ， NCALLEE 将 PREDICT 与immediateCOMPLETE组合到被调用方。NINIT对初始Earley项（q0，0）E0执行空补全;回想一下，q0是我们解析转换器的被调用者的特殊情况，因此NINIT类似于NCALLEE。新规则定义了与原始规则完全相同的Earley集，前提是换能器满足T2和以下条件：（P1）如果t是A的被调用者（即，，LA（t）=LA）且A可空，则t<$→A.要看到这一点，考虑当任何（t，i），其中tA为空A，通过扫描或完成添加到Ej时，T2表示将有来自t的调用，并且P1确保NCALLER将在转换t A上执行空完成。当（t，i）通过预测相加时，P1确保NCALLEE适用。剩下的情况是初始项（q0，0）∈ E0，这里P1确保NINIT适用。144T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135∈−→一CyE3E0B(10（2）（1，0）x（3，0）E1（5X（8（6，1）（7，0）y（8，3）CyX一E4(10，3）（6，0）（2，0）E2（9，1）（5，1）（8，2）B（4，0）图八、解析xxyy的Earley图。某些传感器不满足P1，例如，语法的任何转换器S= A， A = N。这里S是可为零的，所以通过P1，我们想要q0S;但是T0意味着q∈ LS，这是错误的然而，这很容易处理：任何语法都可以转换成识别相同语言的语法，并且通过将A = r替 换 为A =（r），其转换器满足P1|a）对于所有可空的A。为了效率，我们的算法应用所有的规则预测，NCALLER，和NCALLEE在一起，每当考虑一个项目（t，i）Ej，使t调用s在关闭阶段。5解析重建第4节的算法是一个识别器：它完全接受根据语法解析的输入，但它不返回输入的解析树或解析森林。在这里，我们扩展了算法，使树木和森林可以重建的输入。其主要思想是修改识别器，使其在应用扫描等规则时记住一些信息。存储的信息采用图的形式，其节点用Earley项标记，并且其边指示节点为什么被添加到Earley集合。由此产生的图体现了一个解析森林，我们展示了如何从中提取解析树我们的方法可以看作是Aycock和Horspool方法的推广[1]正确的处理。它也类似于Scott [10]的工作，他展示了如何有效地修改传统的Earley算法来构建共享打包解析森林（SPPF）。我们将在5.3节讨论森林重建。5.1Earley图重构的第一步是在解析过程本身。我们扩展了第4节的算法，在解析过程中构造一个（Earley）解析图 图的每个节点对应于Earley集合中的Earley项。 来自节点的有向边描述了在解析期间如何使用规则来将Earley项添加到Earley集合。我们解释厄利图的例子。图8示出了在输入xxyy上评估的图4的换能器的Earley图。有好几种T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135145fun_parse_tree sym item_complete = funcomplete_children item children =如果为空（链接项），则子项其他let l= CHOOSEfrom links item inifis_nonterminal lthenletchild=complete_children（item_pred l）中的parse_tree（sym_subl）（item_sub l）（child：：children）其他complete_children（item_pred l）children在let children = complete_children item_complete [] in（sym，item_complete.i，item_complete.j，children）图中的边见图9。 树重建• 用终端标记的边缘对应于规则扫描的使用。例如，通过从E0中的项目（1，0）开始扫描x，将项目（3，0）添加到E1。• 粗体边缘对应于预测的使用。例如，通过从E1中的项（5，0）开始的预测，将项（8，1）添加到E1。• 虚线边缘对应于完成。虚线边成对出现一条边用已经完成的非终结符标记，它指向发起非终结符解析的节点。另一条边指向完成非终结符解析的节点例如，项（5，0）被添加到E1，作为完成由E 0中的项（1，0）发起并由E 1中的项（3，0）完成的B的解析的结果。用于预测的第二种边缘不被Aycock和Horspool使用， 斯科特。 在我们的例子中，有必要处理一个我们将讨论的微妙细节第5.3节。Earley图编码解析树的集合。例如，在图8的图表中，S的两个解析树是明显的。一个以E3中的项（2，0）为根，它表明通过三次扫描完成对前缀xxy的解析。第二棵树以E4中的item（2，0）为根，它对应于图4中给出的完整输入的解析树。5.2重新构造解析树在图9中，我们简要介绍了为Earley图的输入非确定性地重建解析树的算法该算法的定义如下：两个相互递归的函数，parse_tree和complete_children。函数parse_tree有两个参数：要重新构造解析树的非终结符（sym）;以及完成非终结符的节点（item_complete）。它返回一个由非终结符组成的解析树， 在输入中，以及它的孩子（如果有的话）。 函数complete_children接受一个节点和一个子节点列表，并将该列表扩展为与参数节点关联parse_tree从右到左重新构造解析树的子树。它以一个空列表和已完成的nontermi- nal （ item_complete ） 的 最 右 边 的 项 开 始 。 然 后 调 用complete_children（递归）遍历146T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135predecessor链接，直到到达一个没有链接的项目，它必须是某个调用的被调用者在遍历链接时，当遇到非终结链接时，complete_children会重新构造子树。子树重构是通过递归调用parse_tree来完成的。某些项目可能是多个转换的目标，从而导致多个链接。 在这种情况下，算法非确定性地选择一个单一的链接，然后使用抽象的CHOOSE函数。5.3重新构造分析森林我们已经论证了Earley图包含了输入的所有解析树，并且刚刚描述了如何从Earley图重建解析树。然而，我们可能希望有一个比Earley图更容易访问的解析树表示：解析森林。我们已经实现了一个解析森林重构算法，但这里没有空间来完整地描述它。 相反，我们将讨论由于使用解析转换器而产生的一些微妙之处我们的传感器结构被设计为通过组合状态（即，，LR（0）项），它们总是一起出现。然而，这样的组合可能潜在地导致单个厄利状态成为多个换能器状态的一部分。特别地，这可能发生在被调用者状态。例如，考虑以下语法：S = x（A |yB）A = y（B |C） B = wwwC = zB的起始状态将出现在两个不同的传感器状态中，一个状态 C的起始状态和一个没有。正如在子集构造中常见的那样，这种类型的多条路径可以在自动机中收敛为一条路径。相应地，在Earley集内可以有多条路径，它们收敛到通常，收敛表示在收敛点处的模糊性。 然而，在这种情况下，它并不（然而，它确实表明了一种模糊性在调用堆栈中的某个较高级别）。因此，在重建解析森林时，我们必须注意不要将这种收敛视为多个解析路径的指示。请注意，Scott为了过滤这种错误的解析树，我们需要用它们的呼叫源。因此，在解析过程中，我们必须跟踪每个状态的调用者集。然后，在重建过程中，我们为重建函数提供负责调用重建中的非终结符的项。接下来，我们过滤调用者集不包括指定调用者的链接。4最后，我们通过提供非终结符链接的前导项来指定重构函数的适当调用者。4为了以这种方式过滤链接，每个链接的调用者集必须包含在Earley图中。 在在我们的实现中，我们只包括被调用者的调用者集，并且我们只在完成时过滤路径（通过拒绝具有不匹配调用者的路径）。T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135147∼语法输入大小执行时间常规脱糖ATN塔顶脱糖ATNIMAP330 KB1.091.721.61百分之五十八百分之四十八OCaml228 KB1.151.405.77百分之二十二百分之四百表1平均解析时间和开销。每个平均值来自10次试验。6评价我们已经实现了我们的算法的几个版本，并在表1中比较它们。“正则”是本文所描述的识别算法。 “Desuging- ared”是相同的算法，但使用的是从原始语法中获得的常规右侧去糖语法。我们相信，这应该近似于Aycock和Horspool的PEP算法，并显示出直接处理规则右侧的性能优势。最后，这应该显示出使用我们优化的解析转换器的性能优势。我们在两种风格明显不同的语法上测试了我们的算法：IMAP，流行的邮件协议[4];和OCaml编程语言。IMAP语法是从几个RFC中自动提取的，并且是以无扫描器的风格编写的。我们从OCaml编译器源代码发行版（3.09.3）中提供的Lex和Yacc规范中改编了OCaml语法。 IMAP输入是一个330KB的跟踪，它是通过多次连接一个较小的跟踪（3.3KB）生成的。OCaml输入是50个OCaml源文件，总共228 KB;最大的文件是34 KB。 我们在MacBook Pro上运行了所有实验，GHz的英特尔酷睿2双核处理器和2 GB的RAM。表1给出了我们的结果。前三列数字给出了三种算法的执行时间。 最后两列给出了相对于常规变体的去糖和ATN变体的开销。 请注意，对于这两种语法，其他方法的开销为22- 400%，这表明我们的算法具有明显的优势。其次，IMAP和OCaml的算法差异之间的关系，考虑到语法风格。7相关工作Earley它不直接处理常规的右侧。Woods它们直接处理常规的右侧，并已在Earley解析中使用[2]。伍兹还考虑了基于传感器的ATN [14]，尽管不是在Earley的背景148T. Jim，Y.Mandelbaum/Electronic Notes in Theoretical Computer Science 253（2010）135解析 我们的传感器专门设计为比ATN更高效 用于Earley分析。Aycock和Horspool他们的解析器不是无扫描的，也不直接处理常规的右侧。我们不知道另一个解析算法，处理一般的上下文无关的语法与规则的右侧没有desugaring。对于LR（1）子集[7，3]，已经有一些关于正则右侧的Scott展示了如何使用Earley解析来构造SPPF [10]。她的算法是为传统的Earley算法设计的;研究如何将她的二进制SPPF用于具有规则右侧的语法引用[1] John Aycock和R.奈杰尔·霍斯博。 实用的Earley语法分析。 Computer Journal，45（6）：620[2] S. M. Chou和K. S. Fu.模式识别的过渡网络。技术报告[3] Bullman Resources，Inc.Yacc++和语言对象库。http://world.std.com/~ compres/.[4] M.克里斯平互联网信息访问协议-版本4 rev 1。http://www.ietf.org/rfc/rfc3501的网站。txt，2003年3月[5] 杰·厄利一个高效的上下文无关语法分析算法。Communications of the ACM，13（2）：94-102，1970.[6] S. C.约翰逊Yacc：又一个编译器。技术报告32，AT T贝尔实验室，Murray Hill，NJ，1975年。[7] Séonk e Kannapinn. 构造LR理论消除Redundan--在 ELR语法分析器构造中的应用博士论文，柏林工业大学，2001年。[8] 布莱恩·W作者声明：Dennis M.里奇C语言编程，第二版。普伦蒂斯·霍尔公司，一九八八年[9] Scott McPeak和George C. Necula Elkhound：一个快速，实用的GLR解析器生成器。在CC 2004：建筑，第13届国际会议，2004年。[10] 伊 丽 莎 白 · 斯 科 特 。 Earley 识 别 器 的 SPPF 风 格 解 析 。 在 Proceedings of the Seventh Workshop onLanguage Descriptions，Tools，and Applications（LDTA 2007），Volume 203 ofElectronic Notesin Theoretical Computer Science，pages 53爱思唯尔，2008年。[11] 肯·汤普森编程技巧：正则表达式搜索算法. Communications of the ACM，11（6）：419[12] 最大直径van den Brand、J. Scheerder、J.J. Vinju和E.维瑟无扫描广义LR解析器的消歧滤波器。在《计算机科学讲义》2002年第2304卷第143-158页中[13] W. A.伍兹.自然语言分析的转换网络文法。Communications of the ACM，13（10）：591[14] W. A.伍兹.级联ATN语法。American Journal of Computational Linguistics，6（1）：1-12，1980.