平衡括号的Parsec

Question

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

我正在针对从托架推杆练习中从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

我的解析器是-is，适用于上述所有情况，但下面的测试用例应该通过。

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

我已经发现了这个问题，因为我对between的修改只允许在两个括号之间出现一个go，而[{}(...中的open产生了两个，但我不知道如何修复它。我试着在skipMany1面前拍go，读到

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

但我知道错误是：

*例外: Text.ParserCombinators.Parsec.Prim.many: combinator‘多’被应用于接受空字符串的解析器。

Answer 1

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

问题是，正如错误消息所述，optional可以匹配空字符串，问题是只要给定的解析器仍能找到匹配，many就会重复匹配。如果解析器与空字符串匹配，它将始终找到匹配(空字符串)，因此它将永远不会停止循环。因此，这是不允许的，以防止无限循环。

因为many已经可以匹配零次，所以不需要optional，所以您可以直接摆脱它。