parsec 如何递归解析简单表达式？

Question

我有这样的字符串：***、**(*)*、****(**(**)*)**

我想在这样的数据结构中解析它：

data Tree = Node [S] Tree Tree | Empty 其中 S 是 * （* 不代表任何字符，它只是星号）

我尝试构建解析器（我使用 megaparsec 但它与习惯性的 parsec 非常相似）：

data Tree = Node [Char] Tree Tree | Empty deriving (Show)

chain :: Parser Tree 
chain = do
    line <- many $ char '*'
    branch <- between (char '(') (char ')') chain
    cont <- (eof >> return Empty) <|> chain
    return $ Node line branch cont

test = parseTest chain "****(*(*)***)*(*)**"

但它不起作用。我尝试了很多方法，但无法与之抗争。

Answer 1

让我们从一个更简单的测试用例开始：

> parseTest chain "*"
parse error at (line 1, column 2):
unexpected end of input
expecting "*" or "("

请注意，读取第一颗星后出现解析错误。输入结束，但解析器希望读取另一个星号或左括号。

查看您的解析器，很明显：

line <- many $ char '*'

通过读取第一串星星成功，但下一行：

branch <- between (char '(') (char ')') chain

要求在输入中有一个左括号，这在任何方面都不是可选的。

我们可以通过以下方式解决这个问题：

branch <- option Empty $ between (char '(') (char ')') chain

现在，解析器在 "***" 上工作正常，但在 "**(*)*" 上挂起。问题是行：

cont <- (eof >> return Empty) <|> chain

这会尝试根据检测输入的结尾来决定何时停止解析，但这仅适用于顶层 chain 调用，其中当前树的结尾对应于输入的结尾 - - 在递归调用中，树可以在输入结束之前结束，所以这是行不通的。

具体来说，在测试用例"**(*)*"中，在解析括号内的树时，即*，我们得到line设置为*，branch 设置为 Empty，然后 cont 行发现我们不在输入的末尾（因为输入的其余部分 ")*" 仍待读取）和递归调用 chain。在此递归调用中，line 被设置为空字符串，branch 被设置为 Empty，并且 cont 行再次导致对 chain 的递归调用，我们有一个无限循环。

相反，让我们编写一个解析器 tree 来解析树的 line：

tree = do
  line <- many $ char '*'

现在可选括号中的 tree （对于左侧）：

  mleft  <- optionMaybe $ between (char '(') (char ')') tree

如果没有左手边，那么也不可能有右手边（说服自己这是真的！--试着写一棵树，在括号中没有左手边，但仍然有一个非空的右手边，你会看到它不能完成），所以我们完成了：

  case mleft of
    Nothing -> return $ Node line Empty Empty

如果有左侧，则读取右侧树（可能为空，但没关系）和return节点：

    Just left -> do
      right <- tree
      return $ Node line left right

整个解析器如下所示：

tree :: Parser Tree
tree = do
  line <- many $ char '*'
  mleft  <- optionMaybe $ between (char '(') (char ')') tree
  case mleft of
    Nothing -> return $ Node line Empty Empty
    Just left -> do
      right <- tree
      return $ Node line left right

希望能达到您的期望：

> parseTest tree "*"
Node "*" Empty Empty
> parseTest tree "***"
Node "***" Empty Empty
> parseTest tree "**(*)*"
Node "**" (Node "*" Empty Empty) (Node "*" Empty Empty)
> parseTest tree "****(**(**)*)**"
Node "****" (Node "**" (Node "**" Empty Empty)
    (Node "*" Empty Empty)) (Node "**" Empty Empty)

此解析器仅忽略尾随输入：

> parseTest tree "*hello*"
Node "*" Empty Empty

但是你可以写一个包装器来要求最外层树的末尾对应于输入的末尾：

treeOnly :: Parser Tree
treeOnly = tree <* eof

parsec 如何递归解析简单表达式？

parsec how to recursively parse simple expression?

haskell

parsec

megaparsec