1

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

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

data Tree = Node [S] Tree Tree | Empty在哪里 （S并不意味着任何字符，它只是星号）**

我尝试构建解析器（我使用megaparsec但它与 habitual 非常相似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 "****(*(*)***)*(*)**"

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

4

1 回答 1

2

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

> 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 '*'

现在可以选择括号中的a tree（用于左侧）：

  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

整个解析器看起来像：

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
于 2017-12-01T15:59:18.880 回答