左右递归解析器

Question

这是的演变。

我需要用 megaparsec 解析像

这样的数据结构

data Foo =
    Simple String
    Dotted Foo String
    Paren String Foo

我想解析它的字符串，例如

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

例如字符串 "a(b.c).d" 应该被解析为 Dotted (Paren "a" (Dotted (Simple "b") "c")) "d".

我遇到的问题是，这是同时左右递归的。

我为第一种和第三种情况编写解析器没有问题：

parser :: Parser Foo
parser 
    = try (do
        prefix <- alphanum
        constant "("
        content <- parser
        constant ")"
        pure $ Paren prefix content
        )
    <|> Simple alphanum

但我无法将第二种情况的解析器放在一起。我试图用 sepBy1 或 makeExprParser 来处理它，但我无法正确处理

Answer 1

要分解出这里的左递归：

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

您可以先将其重写为：

foo ::= alphanum ("(" foo ")")?
      | foo "." alphanum

然后你可以使用标准的替换技巧分解出左递归：

x ::= x y | z

有：

x ::= z x'

x' ::= y x' | ∅

换句话说：

x ::= z y*

x = foo, y = "." alphanum, z = alphanum ("(" foo ")")?, 变成:

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

那么我相信你的解析器可以是这样的，因为 ? ~ 零个或一个 ~ Maybe ~ optional 和 * ~ 零个或多个 ~ []~many:

parser = do
  prefix <- Simple <$> alphanum
  maybeParens <- optional (constant "(" *> parser <* constant ")")
  suffixes <- many (constant "." *> alphanum)
  let
    prefix' = case maybeParens of
      Just content -> Paren prefix content
      Nothing -> prefix
  pure $ foldl' Dotted prefix' suffixes

左右递归解析器

Left and right recursive parser

parsing

haskell

megaparsec