我正在为 Scala 或 Haskell 寻找一个成熟的解析器库。最重要的一点是，图书馆可以处理歧义。如果表达式不明确，我想要与表达式匹配的所有可能的抽象语法树。简单的例子：表达式a ⊗ b ⊗ c可以看作(a ⊗ b) ⊗ c或a ⊗ (b ⊗ c)，我需要两个变体。谢谢！
问问题
1014 次
4 回答
13
当 Walder 的论文 Comprehending Monads（do 表示法的前身）令人兴奋和新颖时，我感觉就像是个老家伙。这个想法是你（引用）用成功列表替换失败，这意味着维护所有可能解析的列表。最后，您通常只参加第一场比赛，但是通过此设置，您可以参加所有比赛。
对于确定性解析器来说，这些并不是那么有效，这就是为什么它们不太流行，但它们正是你所需要的。
看看polyparse，尤其是Text.ParserCombinators.HuttonMeijerand Text.ParserCombinators.HuttonMeijerWallace。
（Hutton & Meijer 将解析器库翻译为 Haskell（来自 Gofer），Wallace 添加了额外的功能。）
确保你在简单的情况下检查它，比如"aaaa"解析
testP = do
a <- many $ char 'a'
b <- many $ char 'a'
return (a,b)
看看它是否具有您所寻求的语义。
你要求成熟。这些库是纯函数式编程遗产的一部分！话虽如此，我认为秒差距更成熟，即使它更年轻。
（推测：我不认为 parsec 可以做你想做的事。它的标准选择组合是确定性的。我没有考虑调整或替换这种行为，我不想我害怕。）
于 2012-11-08T02:12:22.283 回答
4
这个问题立即让我想起了Yacc 已死/不，这不是2010 年底的辩论。Yacc 的作者已死论文提供了一个在 Scala（未维护）、Haskell 和 Racket 中的库。在Yacc is alive响应中，Russ Cox 指出对于模棱两可的语法，代码在指数时间内运行。
众所周知，可以在 中解析模棱两可的语法O(n^3)，但显然，在它们的数量成倍增加的情况下，枚举所有解析树可能需要指数时间——在x1 + x2 + x3 ... + xn. bison实现这样做的 GLR 算法；不幸的是，虽然bison它确实很成熟（如果不是真的垂死），它既不是用 Haskell 也不是用 Scala 编写的。
Daniel Spiewak 在 Scala IIRC 中实现了 GLL 解析器，但我上次查看它时，遇到了一些性能问题。所以我也不确定它是否可以被描述为成熟。
于 2012-11-08T15:53:38.130 回答
3
我不能说它有多成熟或给你任何使用示例，但我已经在标签中打开了 scala gll-combinators库几天。它处理模棱两可的语法，看起来很漂亮。
于 2012-11-08T15:11:53.223 回答