haskell - 平衡括号的秒差距

Question

作为学习使用 Parsec 的练习，我正在编写一个验证平衡括号的解析器。我只担心 ()、[] 和 {} 对，但无法让我的解析器处理多个括号第一个里面的组。

我正在针对从 the bracket-push exercise 中提取的大量测试用例进行测试来自 exercism.io，但值得注意的边缘情况是:

isBalanced "" = True
isBalanced "(some[nonsense]with)brackets" = True
isBalanced "}{" = False   -- reversed brackets no good.
isBalanced "{}}" = False  -- extra ending brackets no good either.

我的解析器看起来像:

import Text.Parsec
import Text.Parsec.Char

hasMatchingBrackets = go >> eof
  where
  go = skipMany (noneOf "[{()}]")
        >> optional (
           between (char '(') (char ')') go
       <|> between (char '{') (char '}') go
       <|> between (char '[') (char ']') go )
        >> skipMany (noneOf "[{()}]")

isBalanced :: String -> Bool
isBalanced xs = case parse hasMatchingBrackets "isBalanced" xs of
                  Right _ -> True
                  Left  _ -> False

我的解析器按原样适用于所有上述情况，但以下应该通过的测试用例却没有

isBalanced "([{}({}[])])" = True  -- Fails with the parser above!

我已经确定问题是我的 between 的交替只允许在一对括号之间出现一次 go，并且 [ {}(... 变成两个，但我不确定如何解决它。我尝试在 go 前面敲击 skipMany1，以阅读

    between (char '(') (char ')') (skipMany1 go)
<|> ...etc

但是我得到了错误:

*** Exception: Text.ParserCombinators.Parsec.Prim.many: combinator 'many' is applied to a parser that accepts an empty string.

Answer 1

使用 many 是正确的解决方案，但您需要先摆脱 optional。

问题是，正如错误消息所说，optional 可以匹配空字符串，问题是 many 会重复匹配给定的解析器仍然可以找到匹配项。如果解析器匹配空字符串，它总会找到一个匹配项(空字符串)，因此它永远不会停止循环。所以这是不允许的，以防止无限循环。

因为 many 已经可以匹配零次出现，所以不需要 optional 并且你可以去掉它。