scala - 是否有适用于 Haskell 或 Scala 等功能语言的 LL 解析器生成器？

Question

我注意到明显缺乏用函数式语言创建解析器的 LL 解析器。我一直在寻找但没有成功的理想发现是为 ANTLR 风格的 LL(*) 语法生成 Haskell 解析器(对语法进行模小重新格式化)，并且惊讶于每一个具有功能的解析器生成器我发现的语言目标是某种 LR 解析器。

我想将我正在研究的这种语言的解析器转换为语言本身的功能特性从 ANTLR 到自托管，如果我可以将某些几乎可以肯定在另一种功能语言中正确的东西移植到我的语言中，这将有很大帮助(最好是我熟悉的 Haskell 和 Scala)，而不必完全从头开始重写它，尽管最终我可能会这样做，因为核心语言很小。

在这一点上，甚至不仅仅是解决方案，我很好奇为什么没有这样的 LL(*) 甚至 LL(k) 解析器生成器，但是有许多 LR 生成器，因为 LL 似乎天生就更容易。

Answer 1

主要原因是大多数用函数式语言编写的 LL(k) 解析器只是使用解析器组合器实现的，因为生成解析器组合器库的最简单路径是 recursive descent。 .

Haskell 的 parsec , attoparsec , 和 polyparse Scala 的普通解析器组合器都产生了有效的 LL(*) 解析器。

parsec 和 attoparsec 都要求你使用显式的 try 组合子来进行回溯，但这只是为了提高效率和 scala parser combinators还可以处理packrat parsing .

考虑 announcement 中的以下片段Brent Yorgey 最近的 unbound包裹:

parseAtom = parens parseTerm
    <|> var <$> ident
    <|> lam <$> brackets ident <*> parseTerm

很容易看到原始语法。

LR 解析器需要更复杂的预处理来生成有效执行的表，因为使用类似 recursive ascent 的直接手动编码很糟糕。

通过将解析器组合器实现为 EDSL 而不是外部工具，您可以更好地使用编程语言的高级特性。您可以使部分语法更高阶，构建 lexer hack直接进入解析器等。典型的 LR 解析器生成器不能做这些事情，或者只能在有限的上下文中以特别的方式提供它们，因为最终需要能够发出表。