可以使用Haskell的Parsec库来实现带备份的递归下降解析器吗？

Question

我一直在考虑使用Haskell的Parsec解析库来解析Java的一个子集作为递归下降解析器,作为更传统的解析器生成器解决方案(如Happy)的替代.Parsec似乎很容易使用,解析速度绝对不是我的一个因素.不过,我想知道是否可以用Parsec实现"备份",这是一种通过依次尝试每个产品来找到正确生产的技术.举一个简单的例子,考虑JLS Java语法的开头:

Literal:
    IntegerLiteral  
    FloatingPointLiteral

我想要一种方法来不必弄清楚我应该如何命令这两个规则来使解析成功.就目前而言,这样一个天真的实现:

literal = do {
    x <- try (do { v <- integer; return (IntLiteral v)}) <|>
         (do { v <- float; return (FPLiteral v)});
    return(Literal x)
}

无法工作......像"15.2"之类的输入将导致整数解析器首先成功,然后整个事情将会扼杀"." 符号.当然,在这种情况下,您可以通过重新订购两个产品来解决问题.然而,在一般情况下,发现这样的事情将成为一场噩梦,我很可能会错过一些案例.理想情况下,我想要一种方法让Parsec为我找出这样的东西.这可能,或者我只是想对图书馆做太多事情？Parsec文档声称它可以"解析上下文敏感的,无限的前瞻语法",所以看起来像我应该能够在这里做点什么.

Answer 1

一种方法是使用try组合器,它允许解析器使用输入并失败,而不会使整个解析失败.

另一个是使用Text.ParserCombinators.ReadP,它实现了一个对称选择运算符,在其中证明了这一点a +++ b = b +++ a,因此无论哪个顺序都无关紧要.我很偏爱ReadP,因为它很小但提供了构建一个非常强大的解析器所需的东西.

Answer 2

要么使用秒差距notFollowedBy来确保integer消耗了直到某个标记分隔符的所有内容（这种方法在大多数情况下都可以扩展到任意场景），要么看看解析器组合器，它探索所有可能的解析替代方案。首先想到的是UU_Parsing库。