parsing - 使 attoparsec 解析器递归

Question

我一直在编写 attoparsec 解析器，并且一直在寻找一种模式，我想将解析器转换为递归解析器(将它们与 monad 绑定(bind) >>= 运算符递归地组合)。

所以我创建了一个函数将解析器转换为递归解析器，如下所示:

recursiveParser :: (a -> A.Parser a) -> a -> A.Parser a
recursiveParser parser a = (parser a >>= recursiveParser parser) <|> return a

如果您有类似的递归数据类型，这很有用

data Expression = ConsExpr Expression Expression | EmptyExpr

parseRHS :: Expression -> Parser Expression
parseRHS e = ConsExpr e <$> parseFoo

parseExpression :: Parser Expression
parseExpression = parseLHS >>= recursiveParser parseRHS
  where parseLHS = parseRHS EmptyExpr

有更惯用的解决方案吗？看起来recursiveParser应该是某种折叠...我还在文档中看到了sepBy，但这种方法似乎更适合我的应用程序。

编辑:哦，实际上现在我想它实际上应该类似于修复......不知道我怎么忘记了。

编辑2: Rotsor 在我的例子中用他的替代方案提出了很好的观点，但恐怕我的 AST 实际上比这更复杂一些。它实际上看起来更像这样(尽管这仍然是简化的)

data Segment = Choice1 Expression
             | Choice2 Expression
data Expression = ConsExpr Segment Expression 
                | Token String
                | EmptyExpr

其中字符串 a -> b 括号位于右侧，c:d 括号位于左侧，其中 : 绑定(bind)比->。

即a -> b 计算结果为

(ConsExpr (Choice1 (Token "a")) (Token "b"))

和c:d 计算结果为

(ConsExpr (Choice2 (Token "d")) (Token "c"))

我想我可以使用 foldl 作为一个，使用 foldr 作为另一个，但其中仍然有更多的复杂性。请注意，它的递归方式有点奇怪，因此 "a:b:c -> e:f -> :g:h ->" 实际上是一个有效的字符串，但 "-> a" 和 "b:" 不是。最后，fix 对我来说似乎更简单。我已将递归方法重命名为:

fixParser :: (a -> A.Parser a) -> a -> A.Parser a
fixParser parser a = (parser a >>= fixParser parser) <|> pure a

谢谢。

Answer 1

为什么不直接解析一个列表，然后将其折叠成你想要的任何内容呢？也许我错过了一些东西，但这对我来说看起来更自然:

consChain :: [Expression] -> Expression
consChain = foldl ConsExpr EmptyExpr

parseExpression :: Parser Expression
parseExpression = consChain <$> many1 parseFoo

而且它也更短。

如您所见，consChain 现在独立于解析，并且可以在其他地方有用。此外，如果您将结果折叠分开，在这种情况下，有些不直观的递归解析会简化为 many 或 many1。

您可能还想看看实现了多少many:

many :: (Alternative f) => f a -> f [a]
many v = many_v
    where many_v = some_v <|> pure []
          some_v = (:) <$> v <*> many_v

它与您的recursiveParser有很多共同点:

• some_v 类似于 parser a >>= recursiveParser 解析器
• many_v 类似于 recursiveParser 解析器

您可能会问为什么我称您的递归解析器函数不直观。这是因为这种模式允许解析器参数影响解析行为(a -> A.Parser a，还记得吗？)，这可能很有用，但并不明显(我没有看到用例还为此)。事实上，您的示例没有使用此功能，这使它看起来多余。