parsing - 左右递归解析器

Question

这是 this 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)*

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

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