代码之家 › 专栏 › 技术社区 › marcosh

左右递归分析器

megaparsec haskell parsing

4

marcosh · 技术社区 · 6 年前

我需要用megaparsc分析数据结构,比如

data Foo =
    Simple String
    Dotted Foo String
    Paren String Foo

我想分析它的字符串

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

例如a字符串 "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 但我没能弄好

1 回复 | 直到 6 年前

1

3

Jon Purdy 6 年前

要在此中考虑左递归:

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)*

那么我相信你的解析器可以是这样的,因为 ? 0或1 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