正在进行中。 您可以在此处查看文档。

此引擎旨在成为优化解析器的基石。

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

特性

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

扩展Gearley

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

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

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

Gearley在每一层都可以完美扩展。

术语表

识别器

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

earleme - 标量位置，目前相当于输入位置索引。

项 - 由点、起源和bocage节点组成的一个值。

起源 - 规则预测的Earley集合编号。对于非预测项，始终小于当前Earley集合ID。

规则历史 - 包含动作编号以及有关语义和规则在转换中的旅程的其他信息的规则摘要。每个规则都有自己的历史。

解析森林

Bocage - 以有向无环图形式的解析森林。

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

求和节点 - 一个总结森林中树的数量。

乘法节点 - 可能乘以森林中树的数量。

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

根节点 - 作为一个解析结果使用的节点。

bocage符号

根节点

• 顶峰空地
• 顶层节点
  • 相关研究
• In Rust

LALRPOP - 一个以易于使用为重点的LR(1)解析器生成器。

• 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 许可协议第 2 版：https://apache.ac.cn/licenses/LICENSE-2.0，或 MIT 许可协议：http://opensource.org/licenses/MIT，任选其一。