4

我需要解析，使用 Megaparsec 像这样的数据结构

data Foo
    = Simple String
    | Dotted Foo String

我可以用点分隔字母数字字符串。

例如abc应该解析为Simple "abc"和。abc.defDotted (Simple "abc") "def"

我现在的解析器就像

fooParser :: Parser Foo
fooParser
    = Simple <$> alphaNum
    <|> do
        foo <- fooParser
        constant "."
        end <- alphaNum
        pure $ Dotted foo end

这适用于Simple，但它不解析任何Dotted，因为第一个选项总是成功解析字符串的第一段。

哪个是修复我的解析器的最佳选择？

4

1 回答 1

6

它不解析任何 Dotted，因为第一个选项总是成功解析字符串的第一段。

通过更改备选方案的顺序，可以很容易地解决这个问题。通常，每当您有一个始终可以匹配的替代方案时，该替代方案必须排在最后。

然而，这只会让你遇到下一个问题：你的Dotted解析器是左递归的，它不支持 parsec，这意味着一旦实际到达它就会导致无限递归。

通常，当我们想将左递归语法与不处理左递归的解析算法一起使用时，我们将递归替换为重复，然后对结果列表执行左折叠。所以给定原始语法：

foo ::= alphanum
      | foo "." alphanum

我们可以像这样使用重复来重写它：

foo ::= alphanum ("." alphanum)*

现在最直接的 Parsec 转换将many用于*然后左折叠结果列表。但是，我们可能会注意到该模式rule ("seperator" rule)*可以更简单地由 匹配sepBy1。所以这给了我们：

fooParser =
  do
    first : rest <- sepBy1 alphanum $ constant "."
    return $ foldl Dotted (Simple first) rest
于 2018-09-06T08:02:58.720 回答