5

这是这个问题的演变。

我需要用 megaparsec 解析一个数据结构，比如

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但我做错了

4

1 回答 1

4

要在此分解左递归：

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
于 2018-09-11T09:33:22.010 回答