工作中。 您可以在此处查看文档。

该引擎旨在成为一个优化解析器生成器的基石。

Gearley受到Jeffrey Kegler的Marpa解析器的启发。

属性

• 非常快
  • 与YAEP一样快
  • 比Marpa快得多
  • 内存高效
  • 使用在线排序的新算法
  • 待办事项：新的混合算法
    • 待办事项：LALR
    • 待办事项：LL(1)
    • 待办事项：LR(1)
  • 对于简单语法，时间和内存复杂度都较小
    • 时间复杂度：对于LR(1)语法，为 O(n log n) （n = 输入长度）
    • 内存复杂度：对于LR(1)语法，与输入长度线性相关
  • 前瞻
    • 1个前瞻令牌
  • 待办事项：多线程解析
  • 待办事项：无恐惧的右递归
    • 待办事项：Leo算法
• 通用
  • 接受所有上下文无关语法
  • 可能通过Pāṇini扩展到接受任何语法
    • 待办事项：数据依赖语法
    • 待办事项：PEG
    • 待办事项：否定
    • 待办事项：布尔语法
  • 与任何解析算法的互操作性
• 安全
  • 待办事项：纯安全Rust
• 优雅
  • 识别器具有简单的设计
    • 小巧的核心
      • 只有470行代码实现核心算法
    • 数学上优雅
      • 使用简单的数据结构
    • 每个令牌的三个独立遍历
      • 就像Marpa一样
    • 高度预处理的语法
      • 识别器和解析森林的复杂性较低，以补偿语法转换的繁重工作
  • 命名
    • Pāṇini是以一位古代语法学家和印度学者命名的
    • 解析森林的命名灵感来自代数
• 良好的错误报告
  • 完美的解析进度信息
  • 跟踪调试
• 可定制
  • 在各个级别上可扩展
  • 可定制的识别器
    • 可选的向下解析片段完成控制
      • 您控制哪些片段被允许进入森林
    • 可选的自定义解析事件
    • 可选的以给定内存容量初始化
    • 泛型于可选的性能策略
  • 可定制的解析森林
    • 可选的模糊节点排序控制
    • 编写您自己的解析森林
    • 两个官方的解析森林实现和一个空森林
      • 在更快的森林和内存高效森林之间进行选择
      • 可选地忽略解析结果，只获取解析成功或失败
• 开源
  • 免费是合理的价格

扩展 Gearley

语法存储在字节字符串中。您可以自己序列化或反序列化它。语法构造实现在cfg库中。

识别器提供了一个接口，用于编写自定义解析森林。或者您可以使用默认的解析森林算法，但编写自己的代码来控制规则顺序，并在每个树节点内存储评估值。

另一个接口提供了对规则完成的控制。您可以在解析过程中拒绝某些已完成的规则或修改它们的解析森林。

Gearley 在每个层面上都具有完美的可扩展性。

词汇表

识别器

点 — 语法中的一个位置，是一个整数。

Earleme — 标量位置，目前等效于输入位置索引。

项目 — 由一个点、一个来源和一个 bocage 节点组成的值。

来源 — 规则预测的 Earley 集编号。对于非预测项目，始终小于当前 Earley 集ID。

规则历史 — 包含操作编号和有关语义以及规则在转换过程中的路径的其他信息的规则摘要。每个规则都携带自己的历史。

解析森林

Bocage — 以有向无环图形式呈现的解析森林。

深度优先 bocage — 通过每次评估一个完整的 bocage 节点来遍历的 bocage。

求和节点 — 一个计算森林中树的数量。

乘法节点 — 一个可能乘以森林中树的数量。

叶节点 — 开始森林中单个树的终端节点。

根节点 — 用作解析结果。

相关工作

在 Rust 中

• LALRPOP — 一个关注易用性的 LR(1) 解析生成器。
• rust-lang的 GLL — 一个解析框架。
  • grammer with an E — 一个语法框架。
• Oak — 一个具有类型表达式的 PEG 解析生成器。

在其他语言中

• Marpa — 具有高级功能的 Earley 解析器（不是生成器）。用 literate C 和 Perl 编写。
• YAEP — 具有当前最佳速度和较小内存使用的 Earley 解析器引擎。用 C 编写。

在学术界

• OMeta — 具有超越解析的高级功能的 PEG 解析器。
• SPPF-Style Parsing From Earley Recognisers — Elizabeth Scott.

引用

我非常希望有一个超级快的通用解析器，但一些非常聪明的人40年来都无法解决这个问题。

— ANTLR作者Terence Parr

我非常期待看到这个。

— mydoghasticks

感谢

感谢Jay Earley、John Aycock、R. Nigel Horspool和Elizabeth Scott，他们开创了Earley解析。

特别感谢mr Jeffrey Kegler，他使我关注到解析，并通过他对Marpa/Earley和Kollos的工作使这个项目成为可能。

特别感谢CD PROJEKT RED、HAEVN、Kaśka Sochacka、sanah、Kwiat Jabłoni、Alex Rainbird、Beth Paterson、Carbon Based Lifeforms和Solar Fields，他们提供了惊人的音乐，使编码变得更加有趣。

许可证

双许可，以与Rust项目兼容。

许可协议：Apache License Version 2.0：http://www.apache.org/licenses/LICENSE-2.0，或MIT许可证：http://opensource.org/licenses/MIT，任选其一。