递归解析器

Question

我需要使用 Megaparsec 解析像

这样的数据结构

data Foo
    = Simple String
    | Dotted Foo String

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

例如 abc 应解析为 Simple "abc"，abc.def 应解析为 Dotted (Simple "abc") "def"。

我现在的解析器就像

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

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

修复我的解析器的最佳选择是什么？

Answer 1

it does not parse any Dotted, because the first option always succeeds parsing the first piece of the string.

通过更改备选方案的顺序可以很容易地解决该问题。通常，只要您有始终匹配的备选方案，则该备选方案必须排在最后。

然而，这只会导致您遇到下一个问题：您的 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

递归解析器

Recursive Parser

parsing

haskell

megaparsec