Lib.rs

译术莫是 Rust 的 LR/GLR 解析器生成器。

状态：功能集相对完整。测试/文档覆盖率非常好。尚未针对速度进行优化，因此不要期望有爆炸性的性能。

欢迎反馈！

请务必查看 译术莫书籍。在那里您可以找到详细描述和全面的教程。

所有功能都有 集成测试 覆盖。因此，这些可以作为非常好的信息来源。

还有一些 示例。

抱负

• 从同一语法进行 LR 和 GLR 解析

  例如，从 GLR 开始以便更容易开发，然后重构为 LR 以提高性能，或者如果您的语言需要超过 1 个前瞻的标记或本质上具有歧义，则从 LR 转到 GLR。

• 可用性和错误报告

  译术莫应该易于使用，具有合理的默认设置。每个错误都应捕获并详细解释。文档应始终是最新的，所有文档示例都应由 CI 测试。

• CFG 语法和用 Rust 编写的语义动作的清晰分离

  因此，可以使用常规编辑器来编辑 Rust 代码以发挥其全部潜力。同时，保持语言的语法清洁，并且可以轻松地将现有语法移植到译术莫。

• 常见模式的语法糖

  例如，零个或多个（*）、一个或多个（+）、可选的（?）、组（()）、带有分隔符的多重匹配等。

• 词法分析器、解析器和构建器的清晰分离

  解析器在解析过程中询问词法分析器下一个标记，同时根据当前的解析上下文告诉词法分析器期望的内容。这避免了某些类别的词法歧义。解析器在每个解析操作中调用构建器以生成结果。

• 灵活性

  提供/生成默认的词法分析器和构建器，但用户可以选择编写自定义词法分析器和/或构建器。

  当提供自定义词法分析器/构建器时，译术莫可用于解析几乎任何类型的序列，并构建任何类型的输出。

• 从语法推断AST节点类型

  对于默认内置构建器，AST节点类型和语义动作是从语法中推断并自动生成的，但用户可以引入手动更改。

• 默认为零拷贝

  内置构建器应默认通过从输入借用来生成输出。

• 高测试覆盖率

  有相当数量的测试。我通常在实现每个新功能之前编写测试（TDD）。由于每个功能都有测试，因此它们可以作为如何信息的好来源。

小型示例

让我们从歧义性语法开始：calc.rustemo

E: E '+' E
 | E '*' E
 | Number
;

terminals
Number: /\d+/;
Add: '+';
Mul: '*';

这个语法不能被LR(1)解析器接受，但可以被GLR接受。所以让我们为这个语法创建GLR解析器，以及解析器自动机的dot可视化

$ rcomp --dot --parser-algo glr calc.rustemo
Generating parser for grammar "calc.rustemo"
Writting dot file: "calc.dot"

该语法的LALR(1)自动机在状态5和6中有冲突，但对GLR来说这不是问题。

现在让我们测试我们的解析器。

#![cfg(test)]
mod calc;
mod calc_actions;
use crate::calc::{CalcParser, DefaultBuilder};
use rustemo::Parser;

#[test]
fn test_glr() {
    let forest = CalcParser::new().parse("2 + 3 * 4 + 1").unwrap();

    // We have 5 possible solutions, see https://en.wikipedia.org/wiki/Catalan_number
    assert_eq!(forest.solutions(), 5);

    // Evaluate each tree from the forest
    let results = forest
        .into_iter()
        .map(|tree| {
            let mut builder = DefaultBuilder::new();
            tree.build(&mut builder)
        })
        .collect::<Vec<_>>();

    assert_eq!(results, vec![21, 15, 25, 15, 17]);
}

由rcomp生成的DefaultBuilder使用从calc_actions生成的和手动调优的动作。有关更多详细信息，请参阅Rustemo书中的完整教程。

现在，让我们使这个语法可以通过LR解析器。最容易的方法是同时保持语法的可读性，使用Rustemo声明性歧义消除来解决移位-减少冲突，从而使解析确定性。为此，我们指定这两个操作都是左结合的，并且*操作具有更高的优先级

E: E '+' E {left, 1}
 | E '*' E {left, 2}
 | Number
;

terminals
Number: /\d+/;
Add: '+';
Mul: '*';

现在可以使用默认的LR算法和默认的lalr-pager表（LALR的改进版本）来生成解析器（如果需要，还有标准的lalr表支持，请参阅rcomp --help）

$ rcomp calclr.rustemo
Generating parser for grammar "calclr.rustemo"

让我们测试我们的LR语法

mod calclr;
mod calclr_actions;
use self::calclr::CalclrParser;
use rustemo::Parser;

#[test]
fn test_lr() {
    let result = CalclrParser::new().parse("2 + 3 * 4 + 1").unwrap();

    // As the parsing is deterministic now we have just 1 solution which is
    // automatically evaluated using the default builder and provided actions
    assert_eq!(result, 15);
}

这只是可能性的一个缩影。有关更多信息，请参阅Rustemo书。

路线图（暂定）

v0.1.0

• LR解析。
• 引导。Rustemo 是自己实现的。
• 内置的字符串解析器。支持自定义解析器。
• 内置构建器：AST、泛型CST、切片构建器。支持自定义构建器。将上下文传递给动作。请参阅测试。
• 提供AST构建动作的动作是自动生成的，但可以进行手动修改。在代码重新生成时保留手动修改，同时将新类型/动作添加到文件中。这允许快速开发，同时保持对AST的完全控制。
• 正则表达式类似语法糖。请参阅测试。
• 重复修饰符（例如分隔符）
• 消歧义过滤器：优先级、结合性。
• 规则/生成元数据。例如，生成类型。
• CLI和API。有一个rcomp编译器CLI，可以在Rustemo语法上调用。此外，API允许将解析器代码生成集成到Rust build.rs脚本中。请参阅计算器示例或集成测试。
• 跟踪位置和报告带有行/列的错误。
• 支持布局（注释和空白作为CFG给出）。它作为特殊的语法规则实现，并由LR解析器解析。结果通过上下文传递给可以执行任何操作的动态。例如，一个通用的树构建器在后续的树叶子中保持布局。请参阅测试。
• 语法分析和状态机构建过程中的详细错误报告。
• 文档完成。
• 首次发布到crates.io！

v0.2.0

• 基于Right-Nulled GLR算法（RNGLR）的GLR解析。
  • 基于Tomita算法。共享打包的解析森林。
  • 从森林中提取懒惰树。
  • 在提取的树上调用任意构建器。
  • 通过RN表条目支持EMPTY产生式（RNGLR算法）。
• GLR文档
• 发布到crates.io

直到v1.0的后续版本（有关详细信息，请参阅CHANGELOG.md）

• 森林迭代。
• 支持不同的解析表生成器。
• 基准测试和性能优化。
• 贪婪重复。
• 内置构建器的零拷贝。
• 括号分组。尚不确定这是否是一个好主意。有时它可以很好地减少混乱，但如果使用过多，则降低可读性。

v1.0

• 语法组合。语法导入、规则继承等。
• 更好的歧义消除（研究动态消除）。
• GLR解析过程的可视化/调试。

后v1.0

• 错误恢复，例如tree-sitter采用的方案。
• 增量解析（仅重新解析输入的更改部分）。
• Elkhound风格的LR/GLR切换。
• 用于处理Rustemo语法的工具（例如，LSP服务器，流行的编辑器的插件）。

许可协议

根据以下协议许可

• Apache License，版本2.0（LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0）
• MIT许可（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

贡献

除非你明确表示，否则你提交的任何贡献，根据Apache-2.0许可证的定义，应按上述方式双许可，而无需任何额外条款或条件。

致谢

自举方法和宏加载生成代码的想法基于LALRPOP项目采用的方案。

类似的项目

Rustemo的架构和总体想法类似于一个类似的Python项目，名为parglare，我在几年前开始。

我在以下项目中找到了许多灵感和想法

• LALRPOP - Rust的LR(1)解析器生成器。该项目与Rustemo最为相似，因此我在那里找到了很多不错的想法。
• Nom - 解析器组合库。架构优雅且trait设计得很好。
• pest - Rust的PEG解析器。看起来很好且维护得很好。

为什么这个名字？

Rustemo发音与塞尔维亚语单词"растемо"相同，意为"我们成长"。这个名字是对不断壮大的Rust社区的致敬。