Combinator解析器：从玩具到工具——基于组合的解析器构造和性能优化

《理论计算机科学电子笔记》第41卷第1期（2001年）网址：http://www.elsevier.nl/locate/entcs/volume41.html22页Combinator解析器：从玩具到工具S.D. 斯维尔斯特拉乌得勒支大学荷兰乌得勒支摘要我们开发，在一个逐步的方式，一组解析器组合子构造确定性，纠错解析器。 对文法的唯一限制是它不是左递归的。广泛使用的是惰性评估，构造的解析器“分析自己”。我们的新组合子可用于构造大型语法分析器，以便在实际应用中用于编译器1介绍存在许多基本解析器组合子的不同实现;一些使用基本函数[3]，而另一些使用一元公式[4]。用这种传统的解析器组合子构造的解析器有两个缺点：当语法变得更大时，解析变得更慢;当输入不是语言的句子时，它们会崩溃。在[7]中，我们提出了一组没有表现出这些缺点的解析器组合子，只要语法具有所谓的LL（1）属性;这个属性使得可以通过查看输入中的下一个符号来决定如何在自顶向下解析过程中继续进行对于许多文法来说，LL（1）等价文法可以通过左因子分解来构造，但不幸的是，所得到的文法通常与语言设计者的想法几乎没有相似之处扩展这样的转换语法与功能的语义处理是繁琐的，优雅的基于组合的解析器所带来的损失。为了缓解这个问题，我们开始扩展我们以前的组合子的方式，使使用更长的前瞻序列的新的和完全不同的实现是既有效，并处理不正确的输入序列。唯一剩下的限制是，1电子邮件地址：doaitse@cs.uu.nl2000年1月，出版社dbyElsevierScienceB。 V. 操作访问和C CBYNCND许可证。S维尔斯特拉2既不是直接也不是间接的左递归：这可以通过使用适当的链组合子来轻松规避;我们并不认为这是一个真正的缺点，因为通常这种组合子的使用比显式左递归公式更好地表达了语言设计者的意图。最终实现已被用于一些大型解析器的构造中。维护能够修复错误所需的信息的额外成本可以忽略不计。在第2节中，我们概括了传统的解析器组合子，并研究了上述问题出现的地方。在第3节中，我们介绍了添加纠错的不同基本机制;由此产生的组合子仍然很短，可以用于小文法。 节中4我们展示了如何扩展组合子与（需求驱动）计算的前瞻信息。在这个过程中，我们尽量减少检查符号的次数。 最后，我们在第5节中给出了一些进一步的扩展，在第7节中给出了一些结论2常规 解析器组合子在图1中，我们展示了组合子的基本接口以及一个简单的实现。我们将定义新的实现和新的类型，但总是以这样一种方式，即已经构建的解析器可以用这些新的定义重用，而不需要或只需最小的更改。为了使表示尽可能简单，我们假设所有输入都是符号序列。使用这些组合子构造的解析器执行深度优先搜索遍历所有可能的解析树，并返回解析可以这是一个已经在[1]中找到的概念。请注意，我们在构造顺序组合的结果时采用了真正的“函数式”方法。我们没有从两个简单的类型b和a中构造一个更复杂的类型（b，a）的值，而是选择从更复杂的类型b -> a和b中构造一个更简单的类型a的值。基于这些基本组合子，可以构造更复杂的组合子。对于使用这种组合子的例子，以及更复杂的combinators，见[3，5，6]和网站为我们的combinators2。作为如何使用这些组合子构造解析器以及它们返回什么的例子，考虑一下（对于Symbol，我们使用Int）：p =（符号3<|>(+)<$> symbol 3 <*> symbol 4）解析器p [3，4，5]？2看到www.cs.uu.nl/groups/ST/Software/UU解析S维尔斯特拉3中缀13<|>--choice combinatorinfixl 4 <*>--sequential combinatortype Symbol =. typeInput =[Symbol]type Parser a= Input->[（a，Input）]成功：：一-> 解析器一符号：：符号-> 解析器符号（<|>）：：解析器一-> 解析器一-> 解析器一（*>） ：：解析器（b）->a）-> 解析器B -> 解析器一解析器：：解析器一-> 输入-> 结果一infixl3 $>--使用接口（$>） ：：（b->a）-> Parserb-> Parser af<$> p =成功 f<*> p--简单的实现succeedvinput=[（v ，input）]符号a（b：bs）=ifa== bthen [（b，bs）] else[]符号a[]=[]（p<|> q）输入=p输入++ q输入（p <*> q）输入=[（pv qv，rest）|（pv，qinput）<- p输入，（qv，rest）<- q qinput]type结果a =要么a字符串解析器p s= case p s of[]-> Right“Erroneous input”（（res，rest）：rs）->Left resFig. 1. 基本组合子>[（3，[4，5]），（7，[5]）]标准实现的主要缺点是，当输入不能被解析时，解析器返回一个空列表，没有任何关于输入中最有可能出错的地方的因此，这种形式的组合子对于任何显著大小的输入都是不可用的。从现代编译器，我们期望甚至不仅仅是这样一个指示：编译器应该纠正简单的类型错误，删除超括号，插入丢失的括号等，此外，它应该这样做，同时提供适S维尔斯特拉4当的错误消息。以这种方式构造的解析器的第二个缺点是，当产生式有许多替代方案时，解析会变慢，因为在每个分支点上顺序尝试所有替代方案，从而导致大量的符号比较。当天真的用户使用S维尔斯特拉5combinators来描述非常大的语法，如：1000万元人民币（<|>）（map symbol [1.. 1000]）这里平均需要500次比较才能识别一个符号。这样的解析器可以很容易地通过使用更复杂的派生组合子来隐式地构造，而用户实际上没有注意到。潜在的不确定性的另一个来源是由非决定论造成的。当许多备选方案可以识别具有公共前缀的字符串时，这个前缀将被解析多次，通常只有一个备选方案最终成功。因此，对于高度尽管如何从非确定性自动机构造确定性自动机是众所周知的，但是在该实现中不使用该知识，也不容易将其合并。我们现在开始描述一个新的实现，它解决了所有提到的问题。3纠错3.1基于延续的解析如果我们扩展上一节中的组合子来跟踪输入中到达的最远点，则解析器仅在回溯完成后才返回该值。不幸的是，到那时我们已经失去了所有的上下文信息，这些信息可能使我们能够决定正确的纠错步骤。 因此，我们将首先将组合子转换为一种形式，这种形式允许我们同时处理所有可能的替代方案，从而从搜索空间的深度优先探索转变为广度优先探索。这种广度优先的方法可以被看作是一种使许多解析器并行工作的方法，每个解析器探索一条可能的路径。作为第一步，我们在图2中介绍了组合子，它们是使用基于延续的风格构造的。正如我们将看到的，这将使得在构造完整的解析之前提供有关解析过程如何进行的信息成为可能我们暂时忽略要计算的结果，只返回一个布尔值，表明句子是否属于该语言。continuation参数r表示解析过程的其余部分，当当前解析器成功时将调用它它可以被看作是从部分识别的产品的右手侧封装了一堆未说明的符号，输入的其余部分将与之匹配。我们再次定义了一个函数parse来启动解析过程。它的continuation参数是函数null，它检查当挂起符号的堆栈被耗尽时，输入是否S维尔斯特拉6type结果a =布尔值类型解析器=（Input -> Bool）->（Input -> Bool）成功= \ R 输入 -> r输入符号a= \ R 输入 -> 案例输入（b：bs）-> a==brbs[]->错误p *> q= \ R 输入 -> p（q r）输入p<|>Q= \ R 输入 -> p r输入||q r输入parse p input = p null input-- null检查输入结束图二. 基于连续的组合子3.2解析历史现在一个重要的设计决策不仅仅是返回最终结果，而是将其与解析历史相结合，从而使我们能够跟踪导致此结果的解析步骤。我们考虑两种不同的解析步骤：OK步骤，表示成功识别输入符号失败步骤，表示解析过程中的纠正步骤;这样的步骤对应于插入或删除输入流数据步数结果= Ok（步数结果）| 未通过（步骤结果）|停止结果getresult：： Steps result ->result getresult（Okl）=getresultl getresult（Faill）=getresultl getresult（Stop v）= v对于结果和它的解析历史的组合，我们不简单地取一个carnival积，因为这个对只能在到达解析过程的末尾并因此能够访问最终结果之后才能构造。相反，我们引入了一种更复杂的数据类型，它允许我们在解析完成之前开始生成跟踪信息理想情况下，希望选择具有最少失败步骤的结果，即，该序列对应于与原始输入具有最小编辑距离的序列。不幸的是，这将是一个非常昂贵的操作，因为它意味着在输入中的所有可能位置处，必须考虑所有可能的校正步骤。例如，假设遇到一个不匹配的then符号，我们想找到插入缺失的if符号的最佳位置。在这种情况下，可能会有许多点可以插入，并且这些点中的许多点在编辑距离方面与S维尔斯特拉7正确的输入。为了防止组合爆炸，我们采取了贪婪的方法，优先考虑具有最长前缀的Ok步骤的解析。因此，我们根据Ok步骤的最长成功前缀来定义步骤best：： Stepsrslt-> Stepsrslt-> Stepsrslt_@（Okl）_@（失败l）_@（失败_）_这里有一个基本的观察：当两个序列之间没有基于第一步的偏好时，我们推迟了关于返回哪个操作数的决定，同时仍然返回关于所选结果中第一步的。3.3纠错步骤现在让我们讨论可能的纠错步骤。当输入中的下一个符号与我们期望的任何符号都不同时，或者当我们期望至少多一个符号并且输入耗尽时，我们必须采取这样的步骤。我们考虑两个可能的纠正步骤：• 假装这个符号本来就在那里，这相当于插入了它在输入流中• 删除当前输入符号，然后重试以查看预期符号是否存在在这两种情况下，我们都报告失败步骤。 如果我们将这个错误恢复添加到前面定义的组合子中，我们将得到图3中的代码。请注意，如果在解析过程结束时留下任何输入，则将其删除，从而导致许多失败的步骤（Fail（Fail（. (Stop True）.这可能看起来非常复杂 ， 但 需 要 表 明 并 非 所 有 输 入 都 被 消 耗 。操 作 员||,thatwasusedbeforetofindoutwhetheratabran chingpoi nt at least one ofthe alternatives finally led to success, has been replaced by the bestoperator which selects the“best”result. 正是在这里，从深度优先到广度优先的方法发生了变化：||只有在至少第一个操作数被完全求值后才返回结果，而函数最好以增量方式返回结果。 正是顶层的getresult函数通过重复请求Steps值头部的构造函数来实际驱动计算。S维尔斯特拉8type结果a =步骤布尔符号a=\ r输入->大小写输入of（b：bs）->if a== b thenOk（r bs）{-插入符号a-} else Fail（r input{-删除符号b-}符号 ar bs）{-插入符号a-}[]->失败（r输入）成功=\ r输入->r输入p<|> q=\r input -> p r input< 'best' q rinput p *> q = \ r input -> p（q r）input解析p = getresult。 p（foldr（const Fail）（Stop True））图三. 纠错分析器3.4计算语义结果刚刚定义的组合子是非常无用的，因为添加的错误纠正使解析器总是返回True。我们现在必须再加上两件事：(i) 结果的计算，就像在原始的组合子(ii) 生成错误消息，指示采取了哪些纠正步骤。这两个组件都可以通过将迄今为止计算的结果累积到解析函数的额外参数中来处理3.4.1计算结果自顶向下解析器维护两种堆栈：• 一个用于跟踪仍待识别的内容（此处由延续表示）• 一个用于存储请注意，我们的解析器（或者语法，如果你喜欢的话），虽然这可能不是第一次看到，是在一个正常的形式，其中每个右手边的alter- native的长度最多为2：每次出现一个<*>combinator引入一个（匿名的）非终结符。如果右边的长度大于2，<*>的左结合性决定了如何定义归一化。所以S维尔斯特拉9对于某个<*>解析器的每个已识别的左操作数，其右手侧部分还没有被识别，在栈上有一个待处理的元素。我们决定也用一个函数来表示挂起元素的堆栈，因为它可能包含非常不同类型的元素。包含减少的项目和延续的堆栈的类型现在变为：类型Stack a b = a -> btype Futureb result= b-> Input-> Steps结果这给了我们以下类型解析器的新定义：类型解析器a =对于所有B结果。未来b结果--延续-> Stack a b--挂起值->输入->步骤结果这是Haskell98标准不允许的特殊类型，因为它包含的类型变量b和结果不是类型Parser的参数。通过用forall构造进行量化，我们表明解析器的类型不依赖于这些类型变量，只有通过传递函数，我们才能将类型链接到其环境。这个扩展现在被大多数Haskell编译器接受。因此，识别类型a的值的解析器将该值与先前找到的值的堆栈相结合，这将产生类型b的新堆栈，该堆栈反过来被传递给延续作为新堆栈。这里有趣的组合子是负责顺序合成的组合子，现在变成了：((p<*>q）r栈输入= p（q r）（栈。）输入当pv是解析器p计算的值，qv是解析器q计算的值时，传递给r的值将是：（（叠。）pv）qv）=（stack. pv）qv =stack（pv qv）这正是我们所期望的最后，我们必须调整函数parse，使其将构造的结果转换为所需的结果，并修改堆栈（id）：解析p= getresult（p（\ stinp -> foldr（const Fail）（Stopst）inp）id）我们在这里不会给出其他组合子的新版本，因为它们在图4中几乎以相同的形式显示S维尔斯特拉103.4.2错误报告请注意，在我们引入错误纠正步骤的时候，我们不能确定这些纠正是否真的会出现在搜索树中的所选路径上，因此我们不能直接将错误消息添加到结果中：请记住，我们的策略的一个基本属性是，我们可能会产生关于结果的信息，而实际上还没有做出选择。在Fail构造函数中包含错误消息将迫使我们过早地决定选择哪条路径。因此，我们决定也在一个累积参数中传递错误消息，只是要包含在解析过程结束时的结果。为了让用户能够生成他们自己的错误消息（比如用他们自己的语言），我们以数据结构的形式返回错误消息，我们将其作为Show的实例（参见图4，其中也包含了前面的修改）。4介绍前瞻在上一节中，我们已经解决了第一个提到的问题，即我们确保总是返回一个结果，以及关于采取了什么错误纠正步骤在本节中，我们解决剩下的两个问题（回溯和顺序选择），这两个问题都与低效率有关，在一次扫描中。到目前为止，解析器都被定义为函数，我们不能轻易地获得任何进一步的信息。这种有用信息的一个例子是可以被解析器识别为第一符号的符号集，或者解析器是否可以识别空序列。由于我们不能从解析器本身获得这些信息，我们决定单独计算这些信息，并使用使用这些信息构造的解析器将这些信息元组化。4.1试图为了了解这样的信息可能是什么样子，我们首先引入基本组合子的另一个公式：我们构造一个trie-structure，它表示所表示的语法的语言中所有可能的句子（见图5）。这正是我们进行解析所需要的：语言中的所有句子都按照它们在trie结构中的公共前缀进行分组。因此，一旦结构被构建，就可以在线性时间内解析语言。有一段时间，我们又忘记了计算结果和错误消息。Trie中的每个节点代表具有共同前缀的句子的尾部，而该前缀又由表示语言的oevrall结构中的根的路径表示。 Choice节点表示非空尾通过将可能的下一个符号映射到表示其S维尔斯特拉类型Parser a =forall b result.未来b结果->堆栈a b->错误->输入->步骤结果data Errors =错误符号串错误| 插入的符号串错误| NotusedString实例显示错误show（显示）=“\n在“++pos++ showe show”之前删除“++ shows++“（插入s pos e）=“\n在“++pos++ showe show（NotUsed“”） =”之前插入“++ shows ++show（NotUsed pos）=“\n从“++ pos++“开始的符号被丢弃“eof=“输入结束”位置ss=if null ss then eof elseshow（head ss）符号a=letpr=\ r ste input->（b：bs）的大小写输入->如果a== bthenOk（r（st s）e bs）else Fail（（prr st（e.brab（position bs））bs）'最好'（r（st a）（e）插入a（显示b））输入））[]-> Fail（r（st a）（e. 插入一个eof）输入）在公关成功v =\r堆栈错误输入-> r（stack v）errorsinput p<|> q=\r堆栈错误输入-> pr stack errors input堆栈错误输入p *> q =\r堆栈错误输入-> p（q r）（stack.）错误输入解析p输入=getresult（ p（\ v错误输入p-> foldr（const Fail）(Stop（v，errors.position inp））inp）id id输入10）见图4。 纠错和报错组合子S维尔斯特拉11类型解析器=发送data Sents = Choice [（Symbol，Sents）]| 发送：|：发送--左为选择，右为结束| 端组合xss@（x@（s，ct）：xs）xss @（y@（= case comparison % s%sLT-> x：组合xs和 GT->y：组合xss和ysEQ->（s，ct<|>c t ' ） ：c o m b i n e x s y s c o m b i n e [ ] c s ' = c s 'combine cs[]= cssymbol a = Choice[（a， End）]succeed = Endl@（选择为） <|> r= caserof（Choice bs）-> Choice（combineas bs）（p：|：q）->（l<|>p）：|：q结束-> l：|：结束l<|> r@（Choice _）= r<|>L_<|>_=错误“歧义语法”Choice cs< *> q = Choice [（s，h< *> q）|（s，h）<- cs]l：|：r< *> q =（l <*> q）<|>（r< *> q）结束 *> q = qparse：： Parser -> Input -> Boolparse（Choice cs）（a：as）=或[parse f as|（s，f）<-cs，s==a] parse（p：|：q ）inp= parse p inp||解析q输入parse End[]= Trueparse__= False图五.代表所有可能的句子。对应的尾巴End节点表示句子的结尾。The：|：nodes对应于既是Choice节点（存储在左操作数中）又是End节点（存储在右操作数中）的节点。注意，语言ab|ac表示为：选择[其中共同前缀已被分解。这样一来，3我们可以使用稍微不同的结构来编码，但这将S维尔斯特拉12导致了后来更详细的程序文本S维尔斯特拉13|与解析器的回溯相关的问题现在已经转移到了Sents结构的构造中。对于语言a/b/c来说，构造trie是一个不终止的过程。幸运的是，惰性求值处理了这个问题，只够辨认当前的句子。然而，这种方法的一个缺点是，它引入了大量的复制，因为顺序组合的方式已经被建模。我们不仅使用该结构使决策过程具有确定性，而且还表示仍待识别的符号堆栈。此外，我们可能已经成功地在线性时间内解析，但这是唯一可能的，因为我们已经把工作转移到trie结构的构造在接下来的文章中，我们将展示如何通过组合预先计算的trie结构构建块来构建trie结构的等价物。4.2合并不同的方法比较两种不同的方法：• 计算值并并行• 解释trie数据结构的解析器，只检查输入中的每个符号一次在我们的最终解决方案中，我们将合并这两种方法。我们将计算Sents片段，我们将根据这些片段来决定如何进行解析，并使用基于延续的解析器来实际接受符号。由于新数据结构中表示的信息与LR（0）自动机状态中存储的信息非常相似，因此我们将使用该术语。因此，我们将构建一个类似的结构，而不是构建完整的Sents结构，该结构可用于选择要继续的解析器在继续之前，让我们考虑以下语法片段：succeed（\ x y-> x）*> symbol<|>成功（\x y-> y）*>符号这里出现的问题是如何处理相应符号这个问题的解决方法是将trie结构中的这些操作推到一个点，在这个点上，不同的备选方案的合并已经停止：在这个点上，我们再次处理一个备选方案，并且可以安全地执行推迟的计算。因此，实际的解析和结果的计算可能会不同步。我们现在讨论我们定义的结构的完整版本，以记录我们的前瞻信息（参见图6中的定义），S维尔斯特拉14data Look p = Shift p [（Symbol，Look p）]|（看 p）：|：（Lookp）|降低p| 找到p（查找 p）merge_ch：： Look p-> Look p-> Looksp l@（Shift ppcs）=案件权利Shiftq qcs-> Shift（p 'bestp' q）（合并pcs qcs）（左：|：right）->（l'merge_ch'left）：|：对（减少 p）->l：|：（Reduce p）（Found_c） ->l'merge_ch'c发现_ c_误差“歧义语法”（P p）= P（\r st e input -> pr st e input）见图6。 计算前瞻信息一旦做出决定，应采取的行动。 Look结构的p组件是实际接受符号并进行语义处理的解析函数。我们将以相反的顺序讨论不同的替代方案：Found p（Look p）这个替代方法表示唯一可能的解析器这是这个结构的第一部分。它对应于trie结构中的非合并节点。因此，它也标记了一个trie片段的结束，原始的try结构可以在不需要任何合并的情况下重新构造。（Look p）部分在结构与其他备选项合并时使用。当另一个备选方案包含与指向此Found的路径类似的路径时，就会出现这种情况node. 在函数'merge ch'中可以看到当该结构与其他备选方案合并时，将删除该结构。Reduce p这表示在使用先行信息时，我们已经遇到了产生式右侧的所有符号（我们已经达到LR术语中的reduce状态），并且解析器p是要使用的解析器。（：|：）这对应于这样一种情况：我们可以继续使用更多的符号来做出决定，或者我们必须使用关于这个非终结符的追随者的信息。这将是我们继续进行可能不确定的解析过程的唯一地方它对应于LR（0）自动机中的移位-归约约束。S维尔斯特拉15Shiftp[（s，Lookp）]这对应于一个移位状态，在这个状态中，我们至少需要多一个符号来决定如何继续。包含在该替代方案中的解析器p是当下一个输入符号不是该移位点的下一个表中的关键字时要调用的纠错解析器，因此没有符号可以在不采取纠正步骤的情况下被移位在描述如何构建这种前瞻结构之前，我们将首先解释如何使用它们（参见图7）。为了最小化与检查前瞻数据结构相关联的解释开销，我们将每个这样的结构与给定的函数配对，(i) 使用输入序列定位要调用的解析函数(ii) 然后用输入序列调用这个函数在一个适当的Haskell实现中，这意味着在前瞻结构中使用的构造函数被“编译掉”，作为部分或阶段评估的一种形式。注意，以这种方式构造的函数（类型为Realparser）将是要调用的真正的解析器：前瞻结构在它们的构造中只扮演中间角色，并且可能在函数构造完成后立即被丢弃。Realparser的第一个参数是continuation，第二个参数是累积的堆栈，第三个参数是迄今为止累积的错误消息，第四个参数是输入序列，其结果最终将是一个Steps序列，在最后包含函数mkparser解释一个Look结构，并将其与相应的Realparser配对。函数mkparser构造了一个函数choose，该函数在最终的Realparser中使用，以选择（选择输入）使用当前输入的Realparser p）。 一旦被选择，这个解析器p就被调用（prsteinput）。因此，函数choose，即在Look结构上同态的结果，具有类型Input->Realparsera。我们现在将讨论这个选择过程是如何发生的，再次从下到上考虑备选方案发现不需要进一步的选择，所以我们返回一个函数，给定输入的其余部分，返回包含在这个备选项中的解析器Reduce这个选项可以像Found选项一样处理;不需要检查输入的其他符号（：|：）在这种情况下，我们返回一个解析器，它将在两个可能的备选方案之间动态地进行选择：或者我们通过调用包含在这个备选方案（p）中的解析器来减少，或者我们通过使用进一步的前瞻信息（css）来继续定位解析器。这个选择是最有趣的一个。我们正在处理的情况下，我们必须检查下一个输入符号。由于在这里执行线性搜索可能非常昂贵，我们首先从表中构造一个二叉搜索树，并部分地评估函数pFind，S维尔斯特拉16这是一棵构造好的搜索树。返回的函数现在用于构造的函数中，以继续选择过程（如果失败，则返回错误纠正解析器p）。我们在图9中给出了附加函数的代码。它们代表了它们自己，对于理解整个选择过程并不重要。我们已经保证这个搜索函数只计算一次，并且包含在Realparser中。因此，与所有表学习相关的解释开销仅执行一次。在这方面，我们的组合子实际上起着解析器生成器的作用。至此，我们可以描述如何为不同的基本组合子构造Look结构图8给出了基本组合子的代码。的代码<|> combinator非常简单：我们通过合并两个trie结构来构造trie结构，如前所述，并在- voke mkparser中使用其关联的Realparser对其进行元组化。<*>combinator的代码有点复杂：发现我们用两个Realparser的顺序组合（'fwby'）替换了已经存在的解析器，并且可以在没有进一步前瞻的情况下选择解析器显然，从上下文（即顺序复合的右手操作数）中可以获得关于这个节点的追随者的进一步信息，我们使用它来提供急需的关于什么符号可能跟随的信息。因此，我们将这个Reduce节点替换为右侧解析器的trie结构，但替换了其中的所有元素由一个解析器从原来的左手边的减少解析器前缀侧节点4。（：|：）我们将两种选择合并。Shift我们更新了错误纠正解析器，并将choice结构中包含的所有解析器都更新为第二个解析器。这个定义似乎代价高昂，但我们又一次被懒惰的评估所拯救。 请记住，这些Look结构仅用于函数mkparser，并且只检查分支，直到Found或者到达Reduce节点。如果语法是LL（1），这将只是一个步骤！一旦mkparser完成了它的工作，整个结构可能会被垃圾收集。在symbol的代码中，我们看到两个局部函数：• pr：原始的纠错解析器• pr4严格地说，只有当reduce节点实际上是右操作数时才需要这样做。其中：|：构造，指示现在存在可解析的移位归约构造S维尔斯特拉newtype RealParser a= P（对于所有 b结果.（b ->错误->输入->步骤结果）->（a -> b）->错误->输入->步骤结果）data Parser a = Parser（Look（RealParsera））（RealParsera）mkparser：： Look a -> Parser acata_Look（sem_Shift，sem_Or，sem_Reduce，sem_Found）=let r=\c -> case c of（轮班p csr）->sem_Shiftp [（s，r ch）|（s，ch）<-csr](left ：|：右 ）-> sem_Or（r left）（r right）（减少p）-> sem_Reduce p（发现p cs）-> sem_Found p（rcs）in rmap_Lookf= cata_Look（\ qpcsr->Shift（f qp）csr，\left right->left：|：对，\qp-> Reduce（fqp），\qpcsr-> Found（fqp）csr）mkparser cs=让我们选择=cata_Look（\ pcss->let locfind= pFind（tab2tree css）in\inp-> case inp of[]-> p（s：ss）-> case locfind s of只是cp->（cp ss）无-> p，\cssp ->（p 'bestp'）. CSS，\p-> const p，\p cs-> const p）cs在解析器cs（P（\r st e input->let（P p）=choose input在前级输入中））16见图7。 从Lookahead结构S维尔斯特拉17符号a= let pr =. 像以前pr’=（移位（Ppr）[（a，（减少（P成功v= mkparser（End（P（\r->\st e input->r（st v）einput）（解析器cp _）<|>（Parser cq_）= mkparser（cp<' m e r g e _ c h ' c q ） （ P a r s e r c p _ ） * > ~ （ P a r s e rc s q q p ）=mkparser$cata_Look（\pp csr -> Shift（pp，\csr rp -> csr，\pp->map_Look（pp，\ppcsr-> Found（pp）cp其中（P p）'fwby'（P q）= P（\ r st e i -> p（q r）（st.）e（i）见图8。 最后的基本组合子在这种情况下，可以跳过它存在的检查和错误校正行为。因此，我们所要做的就是从输入中提取一个符号，将其合并到结果中，然后继续解析。我们通过添加OK步骤来记录成功的步骤。如果我们不使用前瞻信息，我们必须应用函数pr，这是包含在第一个Found构造中的函数。当这个解析器与其他解析器合并时，这个包装器被移除，只有在确定解析器会成功之后才会调用解析器：因此在文本的其余部分出现pr只有当测试以某种方式未能找到适当的前瞻性时，我们才再次使用旧的pr，以便纳入纠正步骤。为了完整起见，我们合并了图9中使用的其他函数。5扩展在完整的组合子集合中，我们包含了一些进一步的扩展。完全前瞻的计算可能是昂贵的，例如，当计算的选择结构变得非常大并且不经常使用时。在这种情况下，可能需要使用非确定性方法。为此目的，动态版本也可提供具有前面给出的回溯方法的效率。我们还注意到，传递值和错误消息的过程S维尔斯特拉18数据BinSearchTree a v= Node（BinSearchTree a v）a v（BinSearchTree a v）| Niltab2tree tab =树(tree，[]）=sl2bst（长度选项卡）（选项卡）sl2bst0列表 =（无，列表）sl2bst1（（a，v）：rest）=（NodeNil avNil，rest）sl2bstnlist让ll=（n-1）(rt，list2）=sl2bstrllist1in（Node lta v rt，list2）pFind Nil =\i->无pFind（Nodeleft r vright） =let findleft= pFindleftfindright= p在\i->情况下查找正确比较i rEQ-> Just VLT-> findleftiGT-> findrighti图9.第九条。Braun树构造和检查的附加功能可以扩展到包含任何进一步所需信息的累积;这类信息的例子是被解析的文件的名称、行号、定位特定标识符的环境等。在这种情况下，状态至少应该能够存储错误消息和识别的符号。库中引入了额外的组合子来更新状态。我们的组合子的生产版本包含许多进一步的小改进。作为这种微妙改进的一个例子，考虑函数choose的代码。一旦它不能在移位表中找到下一个符号，它就这个解析器将尝试所有的选择，并比较所有的结果。但我们可以肯定的是，每个结果的第一步都将是失败的，因此，选定结果的第一步也将是失败的。因此，与其先找出失败的最佳方式，然后才报告解析失败，不如立即报告失败步骤，并从实际结果中删除第一个失败步骤;很可能我们正在处理移位/归约冲突，并且已经转到两个备选方案的动态比较，并且，既然我们失败了，另一个备选方案将成功。由于修复是可能的，