使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，但这种方法似乎更适合我的应用程序。

编辑：哦，实际上现在我想它应该是类似于fix的东西。。。不知道我是怎么忘记的。

EDIT2:Rotsor在我的例子中用他的替代方案提出了一个很好的观点，但我担心我的AST实际上比这更复杂。它实际上看起来更像这样（尽管这仍然是简化的）

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

其中字符串a -> b括号在右边，c:d括号在左边，其中:比->绑定得更紧密。

即a -> b评估为

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

CCD_ 9评估为

(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 parser相似
• many_v与recursiveParser parser相似

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