Lib.rs

Rustemo 是一个为 Rust 设计的 LR/GLR 解析器生成器。

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

欢迎反馈！

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

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

还有一些 示例。

愿景

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

  例如，从 GLR 开始以简化开发，然后重构为 LR 以提高性能；或者如果您的语言需要超过 1 个标记的前视或固有的歧义，则从 LR 移动到 GLR。

• 可用性和错误报告

  Rustemo 应该易于使用，并提供合理的默认值。每个错误都应捕获并使用足够详细的解释来解释。文档应始终是最新的，所有文档示例都应由 CI 进行测试。

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

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

• 常见模式的语法糖

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

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

  在解析过程中，解析器会向词法分析器请求下一个标记，同时告诉词法分析器由于当前的解析上下文，期望什么。这避免了某些类别的词法歧义。解析器在每次解析操作时都调用构建器以生成结果。

• 灵活性

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

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

• 从语法中推断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声明性歧义解决来解决shift-reduce冲突，从而使解析确定。为此，我们指定这两个操作都是左结合的，并且*操作具有更高的优先级

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。有一个可调用Rustemo语法的rcomp编译器CLI。此外，API允许将解析器代码生成集成到R build.rs脚本中。请参阅计算器示例或集成测试。
• 跟踪位置和报告带有行/列的错误。
• 支持布局（注释、空格以CFG的形式给出）。它通过特殊的语法规则实现，并由LR解析器解析。结果通过上下文传递给可以执行任何操作的函数。例如，一个通用的树构建器在以下树叶子节点上保持布局。请参阅测试。
• 语法分析和状态机构建期间的详细错误报告。
• 文档完成。
• 首次发布到crates.io！

v0.2.0

• 基于右空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或https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT许可协议（LICENSE-MIT或http://opensource.org/licenses/MIT）

贡献

除非您明确声明，否则根据Apache-2.0许可协议定义的，您有意提交以包含在作品中的任何贡献，都应按上述方式双许可，而无需任何额外的条款或条件。

鸣谢

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

类似项目

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

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

• LALRPOP - Rust的LR(1)解析器生成器。这个项目与Rustemo最相似，所以我从中找到了很多好主意。
• Nom - 解析器组合库。优秀的架构和精心设计的特性和。
• pest - Rust的PEG解析器。看起来不错且维护良好。

为什么这个名字？

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