25

我的问题是关于 Scala 解析器：

  • 哪些是可用的（在标准库和外部），
  • 它们之间有什么区别，
  • 他们是否共享一个通用的 API 和
  • 可以组合不同的解析器来解析一个输入字符串吗？

我至少找到了这些：

  • Scala 的“标准”解析器（似乎是 LL 解析器）
  • Scala 的Packrat 解析器（从 2.8 开始，是一个 LALR 解析器）
  • Parboiled解析器（PEG 解析器？）
  • Spiewak 的GLL 解析器组合器
4

4 回答 4

12

还有 Dan Spiewak 的GLL 解析器组合器的实现。

于 2010-12-15T01:06:54.097 回答
11

值得注意的是，Scala 的标准解析器组合器不是 LL，Packrat 组合器也不是 LALR。解析器组合器是一种具有无限回溯的递归下降形式。你可以把它们想象成“LL(*)”。该技术支持的语言类别正是明确的上下文无关语言类别，或与 LALR(1) 和 Packrat 相同的类别。然而，语法类有很大的不同，最显着的弱点是不支持左递归。

Packrat 组合器确实支持左递归，但它们仍然不支持 LALR 的许多其他更微妙的特性。这种弱点通常源于有序选择运算符，这可能导致一些非常棘手的语法错误，并阻止某些好的语法表述。这些错误最常见的示例发生在您不小心将不明确的选择排序为最短时，导致贪婪匹配，从而阻止尝试正确的分支。LALR 没有这个问题，因为它只是一次尝试所有可能的分支，将决策点推迟到生产结束。

于 2012-02-06T16:41:09.023 回答
8

还有一种称为“用导数解析”的新方法。此处描述了该方法。Daniel Spiewak在 Scala 中有一个实现。

于 2012-02-06T14:20:13.333 回答
4

只是想用指向 parboiled 项目的最新迭代的指针来更新这个答案，称为 parboiled2：

https://github.com/sirthias/parboiled2

parboiled2 仅针对 Scala（与 Scala + Java 相对），使用 Scala 宏，并且非常积极地维护。

于 2014-03-10T17:39:23.403 回答