Parsec for balanced brackets

Question

As an exercise in learning to use Parsec, I'm writing a parser that validates balanced brackets. I'm only worried about the pairs (), [], and {}, but can't get my parser to handle multiple bracket groups inside the first.

I'm testing against a number of test cases pulled from the bracket-push exercise from exercism.io, but notable edge cases are:

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

and my parser looks like:

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

My parser as-is works for all the above cases, but the following test case that should pass does not

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

I've identified the problem as my alternation of betweens only allowing one occurrence of go between a pair of brackets, and the open paren in [{}(... makes two, but I'm not sure how to fix it. I tried slapping skipMany1 in front of go, to read

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

but I get the error:

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

sepp2k sepp2k · Accepted Answer · 2018-04-13T20:49:08

Using many is the right solution, but you need to get rid of the optional first.

The problem is that, as the error message says, optional can match the empty string and the problem with that is that many repeats the match for as long as the given parser can still find a match. If a parser matches the empty string, it'll always find a match (the empty string), so it'll never stop looping. So this is disallowed to prevent infinite loops.

Since many can already match zero occurrences, the optional isn't needed and you can just get rid of it.

Parsec for balanced brackets

1 Answers