左右递归解析器

问题描述 投票:4回答:1

这是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

但是我无法将第二种情况下的解析器放在一起。我试图用sepBy1makeExprParser接近它,但我无法做到正确

parsing haskell megaparsec
1个回答
3
投票

将此递归分解为:

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 = fooy = "." alphanumz = alphanum ("(" foo ")")?,变为:

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

然后我相信你的解析器可以是这样的,因为?~0或者一个~Maybe~optional*~0或更多~[]~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
© www.soinside.com 2019 - 2024. All rights reserved.