Scala Parsers:可用性,差异和组合？

Question

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

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

我发现至少这些:

• Scala的"标准"解析器(似乎是一个LL解析器)
• Scala的Packrat解析器(从2.8开始,是一个LALR解析器)
• 该蒸谷米解析器(PEG解析器？)
• Spiewak的GLL解析器组合器

Answer 1

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

Answer 2

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

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

Answer 3

还有一种称为"用衍生物解析"的新方法.这里描述了这种方法.Daniel Spiewak 在Scala中实现了一个实现.

Answer 4

只是想用指向 parboiled 项目最新迭代（称为 parboiled2）的指针来更新此答案：

https://github.com/sirthias/parboiled2

parboiled2 仅针对 Scala（而不是 Scala + Java），使用 Scala 宏，并且维护得非常积极。