递归解析器

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

它不会解析任何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