是否有任何用于功能语言的LL解析器生成器,如Haskell或Scala？

Question

我注意到明显缺乏LL解析器,它们在函数式语言中创建解析器.对于我一直在寻找没有成功的东西的理想发现是为ANTLR样式的LL(*)语法生成Haskell解析器(模式的重新格式化模式),并且惊讶于每个最后的解析器生成器都具有功能我找到的语言目标是某种LR解析器.

我想将我正在研究的这种语言的解析器从ANTLR转换为语言本身的自托管,如果我能用其他函数式语言输入几乎肯定正确的语言,它会有很大的帮助. (最好是我熟悉的,Haskell和Scala),而不是必须从头开始重写它,尽管最后我可能会这样做,因为核心语言很小.

在这一点上,甚至对此的解决方案甚至比我更好奇为什么没有这样的LL(*)甚至LL(k)解析器生成器,但是许多LR生成器,因为LL本身就更容易.

Answer 1

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

Haskell的parsec,attoparsec和polyparse以及Scala的股票解析器组合器都产生了有效的LL(*)解析器.

parsec和attoparsec都要求你使用一个显式的try组合来获得回溯,但这只是为了提高效率,而scala 解析器组合器也可以处理packrat解析.

请考虑Brent Yorgey最近发布的未绑定包的公告中的以下片段:

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

很容易看到原始语法.

LR解析器需要更复杂的预处理才能生成有效执行的表,因为使用递归上升之类的直接手动编码非常糟糕.

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

Answer 2

你激励我将一个旧的爱好项目发布到https://github.com/nrnrnr/ebnf。它支持标准 ML 的 LL(1) 解析器生成。适应 Haskell 并不难，只要你能找到懂 Icon 的人。

Edward 关于人们倾向于使用组合器进行解析的评论是非常正确的，但是一个工具可以找到 FIRST 和 FOLLOW 集并且会抱怨歧义，这是有优势的。

EBNF 的主要优势在于它的符号：序列、Maybe类型和保留字都是本机支持的，没有额外的麻烦。