使用Rust和Nom的解析器组合器的错误恢复

随着新冠肺炎疫情继续肆虐全球，许多人都呆在家里，要么远程工作，要么无所事事地坐着。前一天下午，我无意中看到一则在线公告，称ACM数字图书馆已向所有人免费开放，供所有人阅读和下载，以帮助在这一危机时期促进研究、发现和学习。我感到好奇，而且之前曾想阅读ACM DL的某些研究论文，于是利用这个机会仔细阅读了它的图书馆，并尽可能多地阅读内容。就在我这么做的时候，我偶然发现了一篇非常有用的论文，名为“解析表达式语法中的语法错误恢复”(Medeiros，S.和Fabio Mascarenhas，2018)的文章，我想与大家分享一下，我将在Nomcrate的帮助下使用Rust编写的原型解析器来测试它的一些概念。

语言解析是一个非常广泛和有趣的主题，有一系列不同的方法和工具可供选择，具体取决于任务的要求，但基本前提很简单：解析器的目标是使用某些数据作为输入，根据某些语法将其分解为其组成部分，并从中获取含义或理解(Wiki)。在编写我自己的项目时，我个人碰巧喜欢使用解析表达式语法(Peg)和解析器组合器。

如果您不熟悉，PEG是一种声明性形式语言，用于从字符串模式匹配的角度描述其他语言。也就是说，PEG允许解析器作者使用如下所示的表达式集声明他们想要的语言的语法：

EXPR←SUMSUM←产品(('；+'；/'；-'；)产品)*PRODUCT←Value(('；*'；/'；)Value)*Value←[0-9]+/'；('；EXPR'；)'；

然后，这些PEG规则将能够将规则描述为行为如下的简单算术语言：

任何PEG表达式都可以直接转换为递归下降解析器，可以使用解析器生成器自动转换，也可以使用您选择的编程语言手动创建。

我真的很喜欢使用像NOM这样的解析器组合框架作为这两种选择之间的一个很好的中间点，因为它们给了您完全用宿主语言(在本例中是Rust)编写解析器的自由和灵活性，但是如果您足够努力地斜着头看，得到的代码是简洁的，相当具有声明性的，并且看起来有点像PEG。

FN expr(input：&；str)->；IResult<；&；str，&；str；{sum(Input)}fn sum(input：&；str)->；IResult<；&；str；{let op=alt((char('；+'；)，char('；-'；))。Recognize(Pair(product，many0(Pair(op，product)(Input)}fn product(input：&；str)->；IResult<；&；str，&；str>；{let op=alt((char('；*'；，char('；/'；)；Recognition(Pair(value，many0(Pair(op，value)(input。字符串)->；IResult<；&；str，&；str；{Recognition(digit1，delimated(char('；('；)，expr，char('；)'；)(输入)}

上面的四个解析器中的每一个都对应一个PEG规则，因为每个解析器都表示为一个纯函数，所以它们可以很好地在代码中组合，并且每个解析器都可以很容易地独立于其他解析器进行测试，例如使用内联单元测试。ALLIN ALL，我喜欢使用PEG和解析器组合子！

我作为一个副业(GitHub)一直在为Nix编程语言(GitHub)破解一个解析器和语言服务器已经有一段时间了，这段被困在家里的长时间重新燃起了我从事这项工作的兴趣。该语言服务器旨在为兼容的第三方文本编辑器和IDE提供代码分析和自动完成功能。这个项目对我来说非常具有挑战性，因为语言服务器往往对其底层解析器有非常严格的要求。

大多数编译器和静态分析工具都是批处理程序，其行为类似于adumb管道，一端消耗源代码，另一端吐出可执行文件(是的，增量编译和工件缓存稍微偏离了这个类比，但基本前提仍然成立)。这意味着它们的解析器和生成的抽象语法树针对与交互式IDE需要的截然不同的东西进行了优化。

由于用户不断地修改源文本并将击键输入到他们的编辑器中，为他们的编辑器提供语法检查的解析器经常暴露于不完整或完全无效的代码片段。这意味着，与许多传统的parsersdo一样，无论何时遇到第一个错误，都不能使用错误消息停止解析和保释。

相反，解析器需要尽可能地容错，始终在每次解析时生成某种语法树，并从用户输入中派生出尽可能多的语法和语义意义，无论它的格式可能有多不正确。您的编辑器应该仍然能够提供有意义的代码完成、悬停文档、转到定义和符号搜索，而不管页面中途是否有缺失的分号。

当我第一次开始这个项目时，我选择使用NOM 5.0在Rust中实现我的Nixparser，因为那是我当时用来编写解析器最舒服的工具。

当我编写解析器时，我很快意识到，提早放弃使用Err(Nom：：Err：：Err(_))或Err(Nom：：Error：：Failure(_))进行解析对于产生错误不是一个好主意。前者会触发回溯，这并不是我一直想要的，而后者会因为出现错误而完全停止解析，这是我从来不想要的。Err(Nom：：Error：：Complete(_))因为名字听起来很有希望，但考虑到我考虑到的设计限制，它最终也是毫无用处的。我需要一些方法来记录遇到非致命的解析错误，并继续解析，就好像什么都没有发生一样，但幸运的是，在庞大的NOM解析器组合工具箱中似乎没有任何东西可以帮助我处理这个问题。

我决定在输出中携带这些非致命的解析错误，而不是使用我命名为PARTIAL的自定义数据结构通过Result：：Err(NOM：：Error：：Error(_))返回它们。这是一种一元数据结构，本质上是：

发布结构部分<；T>；{value：option<；T>；，错误：VEC<；Error>；，}实施<；T>；部分<；T>；{pub FN map<；U，F>；(self，f：F)->；部分<；U>；其中F：FnOnce(T)->；U{。(MUT SELF，f：F)->；Partial<；U>；其中F：FnOnce(T)->；Partial<；U>；{...}pub FN Value(&；Self)->；Option<；&；T>；{...}PUB FN Errors(&；Self)->；&；[Error]{...}PUB FN Verify(Self)-&GPUB FN Verify(&；Self。T，Vec<；错误>；>；{...}}。

这个数据结构还补充了一组自定义的NOM组合符，例如map_part()、Expect_Terminated()和SKIP_IF_ERR()，它们允许我将这些容错解析器组合在一起，同时累积错误字段中的错误。

通过调用expr.ify()，将部分<；T>；转换为结果<；T，Vec<；Error>；，断言他们需要没有错误的有效AST。这个选项对于传统的批处理编译器作者以及测试和调试都很有用。

分别提取并检查Value和Errors字段的内容。这就是语言服务器要做的事情：将累积的错误以诊断的形式发布给用户的编辑器，然后对VALUE中包含的语法树执行进一步的分析。

虽然这种方法最初似乎工作得很好，但一旦解析器增长到一定大小，它就会失控。部分特定组合符的数量增加了，解析器逻辑变得更加毛茸茸、更迫切、更难调试，从一个函数到另一个函数携带大量错误堆栈所带来的性能影响令人震惊地糟糕。它的外观和手感都不再那么像PEG了。

我承认，在这段时间里，我学到了很多关于广泛主题的知识，从使用Criteria对函数进行基准测试，到使用Cargo-Flamegraph生成火焰图，再到尽最大努力避免堆分配来尽可能快地创建解析器。我使用了NOM_LOCATE来保留字符串跨度信息，并在构建语法树时尽可能地零拷贝，但最终，我无法修复所有的缺点和根本缺陷。我需要一种新的方法。

最后，回到最初启发这篇文章的那篇文章！几个月前，由于工作和个人生活的原因，我搁置了这个项目，但上个月带着一些新的想法和更好的直觉回到了这个项目中。由于受到之前的挫折的打击，我质疑解析器组合器总体上是否足够灵活，可以表达既允许又容错的解析器，同时还能发出良好的手工诊断。但是，昨晚在ACM DL搜索引擎中搜索有趣的文章时，我无意中发现了语法错误恢复in parsingexpression gramars"；(2018)这篇论文。

本文作者实际上设法使用一组扩展的pegs来解析Lua编程语言，产生了出色的定制诊断，可与他们的控件(由ANTLR生成的自上而下的LL解析器)的自动错误恢复能力相媲美。他们的技术类似于@matklad在这篇优秀的博客文章中概述的技术，他是著名的铁锈分析器和Rowan的作者，Rowan是一个无损混凝土语法树库。

他们设法做到了所有这些，而不是在第一个解析错误时退出，并且在他们测试的所有情况下仍然100%地生成某种语法树。最终的结果看起来和感觉上仍然像PEG。放弃有希望的东西！😍。

我立即对这篇文章感到兴奋，因为我知道PEG的任何错误恢复策略都可能适用于类似NOM的解析器组合器库，因为这两种方法都使用递归下降。如果您对使用的特定错误恢复策略重新感兴趣，我强烈建议您自己阅读整篇文章。

如果你想要更具体的例子，我还推荐你看看LPegLabel，这是一个PEG解析器生成器的参考实现，它使用了作者Medeiros和Mascarenhas开发的这些技术。

解析应该永远不会失败。如果没有生成某种语法树，则认为是错误。基本上，顶级解析器的输出应该是a(T，Vec<；Error>；)，而不是Result<；T，Vec<；Error>；。此外，您的语法树应该提供回退错误节点类型来表示无效的、无法解析的表达式。

描述您的语言的PEG规则被松散和扩展，以包括由"；标签"；注释的恢复表达式，这基本上确保了解析永远不会失败。这些恢复表达式在评估时会发出错误消息，但会静默地允许解析继续进行。有时它们会向前跳过几个标记，但通常游标只是停留在原来的位置。稍后我将演示一个非常基本的恢复表达式，并使用NOMMAND来实现。

同步标记(如)、}和；用于在必要时在文本中向前跳过，以避免恢复表达式在先前的表达式已经触发后向下发出spuriouserrors。

第一和第三个概念在学术领域并不是什么新鲜事。错误解析、用于标记错误的特殊语法树节点以及用于错误恢复的同步令牌的使用是在手工编写的递归下降解析器中非常有效的常用策略，但是本文将它们很好地应用于PEG解析器(反过来，我将应用于解析器组合器)，而不牺牲它们的声明性质。它还提供了一个小型的恢复表达式库，您可以在不同的情况下使用这些表达式来释放或抑制高质量错误。

让我们来看看一个使用NOM 5.0解析器组合器库编写Rust的容错解析器的真实示例。

如果你想阅读整篇文章，可以在这里找到这个演示的全部源代码，但是我们的想法是使用解析器组合子将本文中概述的最基本的错误恢复策略应用于peg。

使用std：：ops：：range；/在我们的`nam`解析器中，使用std：：ops：：range；替代`&；str`或`&；[U8]`。键入LocatedSpan<；'；a>；=nom_locate：：LocatedSpan<；&；'；a>；>；；/`名称：：IResult<；I，O>；`简化为`IResult<；O>；`的便捷类型别名。类型IResult<；'；a，T&>；=nom：：IResult<；LocatedSpan<；'；a&>；，T&>；特征到范围{fn to_range(&；self)->；范围<；usize&>；}实施<；'；a>；到范围针对LocatedSpan<；&#。{让Start=Self。LOCATION_OFFSET()；设END=START+SELF。片段()。LEN()；START..END}}/包含要显示的文本范围和错误消息的错误。#[派生(Debug)]struct error(range<；usize>；，string)；/在/`nam`解析器之间的`LocatedSpan：：Extra`字段中携带。#[Deriate(Clone，Debug)]struct State<；(&；#39；a RefCell<；Vec<；Error>；)；Iml<；a&>；State<；'；a>；{/将错误从`nam`/解析器组合子内推送到错误堆栈上。PUB FN REPORT_ERROR(&；SELF，ERROR：ERROR){SELF.。0。Borrow_mut()。推送(错误)；}}。

Pub fn parse(source：&；str)->；(expr，vec<；error>；){/将我们的错误堆栈存储在这里的`onom`解析器外部。它/被包装在一个`RefCell`中，因此解析器函数可以/在错误运行时远程推送到它上。设Errors=RefCell：：New(VEC：：New())；设Input=LocatedSpan：：New_Extra(SOURCE，State(&；Errors))；LET(_，EXPR)=ALL_ECTURING(SOURCE_FILE)(INPUT)。期望("；解析器不会失败"；)；(expr，错误。INTO_INTER())}。

请注意我们是如何在消耗全部资源的source_file()解析器上使用.expect()的。请记住，如果我们不能生成某种语法树并100%地使用所有输入，那就被认为是解析器中的错误。

作为示例，我只实现了本文中列出的一个恢复表达式，其形式是我调用Expect()的自定义解析器组合子。它看起来是这样的：

/计算`parser`，并将结果包装在`Some(_)`中。否则，/发出提供的`error_msg`并返回`None`，同时允许/继续解析。Fn预期<；a，F，E，T>；(parser：F，error_msg：E)->；实施FN(LocatedSpan<；'；a&>；)->；IResult<；Option<；T>；其中F：fn(LocatedSpan<；&39；a>；)->；其中F：fn(LocatedSpan<；&39；a>；)->；其中F：fn(LocatedSpan<；&39；a>；)->；，E：ToString，{MOVE|INPUT|匹配解析器(INPUT){OK((剩余，输出))=&>；OK((剩余，一些(输出)，ERR(名称：：错误：：错误((输入，_)|ERR(名称：：错误：：失败((输入，_)=&>；{让ERR=错误(输入。To_range()，error_msg。To_string())；input.Extra。REPORT_ERROR(ERR)；//将错误推送到堆栈。OK((input，one))//解析失败，但继续。}ERR(ERR)=>；ERR(ERR)，}}。

这是解析器组合器库真正大放异彩的领域。这个Expect()组合符可以与其他解析器函数和生成器结果组合在一起，这些函数和生成器结果紧密映射到它们的PEG对应物。下面是一个能够分析使用Expect()来报告错误的带括号表达式的解析器示例：

FN Paren(input：LocatedSpan)->；IResult<；expr>；{//这种使用`expect()`注释解析器//消息的方法遵循原文中注释PEG语法某些部分的//标签的定义。让Paren=delimated(char('；('；)，Expect(expr，"；Expect Expression After`(`"；)，Expect(char('；)'；)，"；Missing`)`"；)，)；map(Paren，|Internal|{expr：：Paren(Box：：New(Inner.。UNWRAP_OR(expr：：Error)})(输入)}

这个玩具实现的最终结果相当惊人，一致地产生了一些非常漂亮的解析结果。给定一个非常普通的AST，如下所示：

/`foo`，`foo_bar`，`foo123`#[Derive(Debug)]struct Ident(String)；#[Derate(Debug)]enum expr{/`(Foo)`Paren(Box<；expr>；)，/`foo`Ident(Ident)，/无法解析的无效表达式。错误，}。

这些结果明显好于我以前使用NOM获得的结果，当时我依赖内置的自定义错误管理工具，并且逻辑比部分<；T>；方法更具说明性和更容易理解。最好的是，最终的解析器更短，更容易推理，并且更直接地类似于它们的PEG等效物，这使得项目在长期内更易于维护。

上面显示的示例被有意地设计得非常简单，以演示Medeiros'；和Mascarenhas 2018年论文中应用于带NOM的解析器组合器的核心概念。为了支持解析像NIX这样的复杂编程语言，我需要将本文中描述的更多恢复表达式转换为NOM组合符。我还需要研究更丰富的错误表示形式，可能包含多个范围、警告、链接等。

我还应该补充一点，我的实际项目中使用的解析器没有使用LocatedSpan，而是处理自定义令牌<；a>；类型。正因为如此，我无法将本例中使用的代码按原样集成到我的项目中。我需要调整它来处理这个自定义类型，这个主题被认为超出了这个特定帖子的范围。

在本指南中，我也没有涉及增量解析或具体语法树(那么多)，我计划让nix-parser生成无损的具体语法树(由Rowan提供)，而不是像本例那样的抽象语法树。

使用良好的错误恢复策略和丰富的、用户友好的诊断实现解析器既是一门艺术，也是一门科学(我想Rust编译器开发人员会同意这一点)。当涉及到分散到语言服务器、REPLS和其他交互使用需求的解析器时，这一点更是如此，在这些应用中，您需要非常宽容地解析错误，并提供有意义的诊断以响应混乱和不完整的输入。我在这次旅行中学到了很多有价值的东西，而且我还在继续学习。首先，我需要温习我的正式方法，并将论文再读几遍，以充分消化信息。

我非常感谢ACM在这场全球大流行期间向公众开放了他们的数字图书馆，我也非常感谢塞尔吉奥·梅代罗斯(UFRN，巴西)和法比奥·马斯卡伦哈斯(UFRJ，巴西)发表了最初的研究论文，我也非常感谢ACM在这场全球大流行期间向公众开放了他们的数字图书馆，我也对Sérgio Medeiros(UFRN，巴西)和Fabio Mascarenhas(UFRJ，巴西)表示敬意。我很高兴偶然发现了它，我从中学到了一些很好的教训。如果你是PEG解析器和/或解析器组合子的粉丝，并且你还没有读过这篇文章，请一定要读。它非常整洁！

在此期间，只要我有空闲时间，我就会随随便便地黑进任何语言服务器，用我以前没有的大量有用的知识和原则武装起来。也许一旦我能够专注于遍历语法树本身并构建一个对该语言进行评估的可用的解释器，我就会真正开始产生有意义的自动补全和语义分析。😛