Chumsky

一个为人类设计的具有强大错误恢复能力的解析器库。

<a href = "https://www.github.com/zesterer/tao"> <img src="https://yellow-cdn.veclightyear.com/835a84d5/f800ffa1-d24a-46dd-a5fd-9b7c02a20a78.png" alt="使用我自己的语言Tao的示例"/> </a>

注：错误诊断渲染由Ariadne执行

目录

• 特性
• Brainfuck解析器示例
• 教程
• 什么是解析器组合子？
• 为什么使用解析器组合子？
• 分类
• 错误恢复
• 性能
• 计划功能
• 理念
• 注意事项
• 许可证

特性

• 大量组合子！
• 适用于各种输入、输出、错误和跨度类型
• 强大的错误恢复策略
• 内联映射到您的AST
• 针对u8和char的文本特定解析器
• 递归解析器
• 完全支持回溯，允许解析所有已知的上下文无关文法
• 解析嵌套输入，允许您将分隔符解析移至词法阶段（就像Rust那样！）
• 内置解析器调试

Brainfuck解析器示例

完整的解释器请参见[examples/brainfuck.rs]（cargo run --example brainfuck -- examples/sample.bf）。

use chumsky::prelude::*;

#[derive(Clone)]
enum Instr {
    Left, Right,
    Incr, Decr,
    Read, Write,
    Loop(Vec<Self>),
}

fn parser<'a>() -> impl Parser<'a, &'a str, Vec<Instr>> {
    recursive(|bf| choice((
        just('<').to(Instr::Left),
        just('>').to(Instr::Right),
        just('+').to(Instr::Incr),
        just('-').to(Instr::Decr),
        just(',').to(Instr::Read),
        just('.').to(Instr::Write),
        bf.delimited_by(just('['), just(']')).map(Instr::Loop),
    ))
        .repeated()
        .collect())
}

其他示例包括：

• [JSON解析器]（cargo run --example json -- examples/sample.json）
• [一个简单的类Rust语言解释器][examples/nano_rust.rs] （cargo run --example nano_rust -- examples/sample.nrs）

教程

Chumsky有一个[教程]，教您如何为一种简单的动态语言编写解析器和解释器，该语言具有一元和二元运算符、运算符优先级、函数、let声明和调用。

什么是解析器组合子？

解析器组合子是一种通过用其他解析器定义解析器来实现解析器的技术。生成的解析器使用递归下降策略将令牌流转换为输出。使用解析器组合子定义解析器大致类似于使用Rust的Iterator特性定义迭代算法：Iterator的类型驱动API使得犯错变得更加困难，并且比手动编写相同代码更容易编码复杂的迭代逻辑。解析器组合子也是如此。

为什么使用解析器组合子？

编写具有良好错误恢复能力的解析器在概念上很困难且耗时。它需要理解递归下降算法的复杂性，然后在此基础上实现恢复策略。如果您正在开发一种编程语言，您几乎肯定会在过程中改变对语法的看法，导致一些缓慢而痛苦的解析器重构。解析器组合子通过提供一个符合人体工程学的API来解决这两个问题，该API允许快速迭代语法。

对于现有解析器不存在的特定领域语言，解析器组合子也是一个很好的选择。在这种情况下，编写可靠、容错的解析器可以从多天的任务变成半小时的任务，只要有一个不错的解析器组合子库的帮助。

分类

Chumsky的解析器是递归下降解析器，能够解析包括所有已知的上下文无关语言在内的解析表达文法（PEG）。理论上可以进一步扩展Chumsky以接受有限的上下文相关文法，尽管这种需求很少。

错误恢复

Chumsky支持错误恢复，这意味着它可以在遇到语法错误时报告错误，然后尝试恢复到可以继续解析的状态，从而一次性产生多个错误，并仍然能够从输入中生成部分抽象语法树（AST）供后续编译阶段使用。

然而，错误恢复没有万能的策略。根据定义，如果解析器的输入无效，那么解析器只能对输入的含义做出有根据的猜测。不同的恢复策略对不同的语言以及这些语言中的不同模式效果会有所不同。

Chumsky提供了多种恢复策略（每种都实现了Strategy特征），但重要的是要理解以下几点：

• 你应用哪些策略
• 在哪里应用它们
• 以什么顺序应用它们

这些都会极大地影响Chumsky能够产生的错误质量，以及它能够恢复有用AST的程度。在可能的情况下，你应该先尝试更"具体"的恢复策略，而不是那些盲目跳过大量输入的策略。

建议你尝试在不同情况下和解析器的不同层级应用不同的策略，以找到令你满意的配置。如果提供的错误恢复策略都无法覆盖你希望捕获的特定模式，你甚至可以通过深入研究Chumsky的内部机制来实现自己的策略！如果你想出了有用的策略，欢迎向主仓库提交PR！

性能

Chumsky注重高质量的错误处理和人体工程学，而非性能。尽管如此，Chumsky能跟上编译器其他部分的速度也很重要！不幸的是，要提出合理的基准测试极其困难，因为Chumsky的具体表现完全取决于你解析的内容、解析器的结构、解析器首先尝试匹配的模式、错误类型的复杂程度、构建AST所涉及的内容等。尽管如此，以下是仓库中包含的JSON基准测试在我的Ryzen 7 3700x上运行的一些数据。

test chumsky ... bench:   4,782,390 ns/iter (+/- 997,208)
test pom     ... bench:  12,793,490 ns/iter (+/- 1,954,583)

我包含了另一个具有类似设计的解析器组合器crate pom的结果作为参考点。被解析的样本文件基本代表了典型的JSON数据，有3,018行。这相当于每秒解析超过630,000行JSON。

显然，这比经过良好优化的手写解析器要慢一些：但这没关系！Chumsky的目标是"足够快"。如果你已经为你的语言编写了足够多的代码，以至于解析性能开始成为问题，那么你已经投入了足够的时间和资源，手写解析器是最佳选择！

计划功能

• 优化的"快乐路径"解析器模式，跳过错误恢复和错误生成
• 更快的"验证"解析器模式，保证不分配内存，不生成输出，只验证输入的有效性

理念

Chumsky应该：

• 易于使用，即使你不完全理解解析器在底层的工作原理
• 类型驱动，在编译时推动用户远离反模式
• 默认情况下是成熟的、"包含电池"的上下文无关解析解决方案。如果你需要手动实现Parser或Strategy，那就是需要修复的问题
• 够快就行，但不需要更快（即：当在错误质量和性能之间权衡时，Chumsky总是选择前者）
• 模块化和可扩展，允许用户实现自己的解析器、恢复策略、错误类型、跨度，并对输入令牌和输出AST进行泛型处理

注意

为选择如此荒谬的名字向诺姆道歉。

许可证

Chumsky采用MIT许可证（见主仓库中的LICENSE文件）。