# Parsing a component of a regex followed by an optional quantifier character

I have a piece of parsec code that parses a unit optionally followed by ?, + or *. Depending on which type I build my Regex (this is a part of a regex parser) as follows:

factor = unit >>= (\x -> (try (char '?' >> return (Or Epsilon x))
<|> try (char '+' >> return (Then x (Star x)))
<|> try (char '*' >> return (Star x))
<|> return x))


This is ugly, so is the do version:

factor = do
x <- unit
(try (char '?' >> return (Or Epsilon x))    <|>
try (char '+' >> return (Then x (Star x))) <|>
try (char '*' >> return (Star x))          <|>
return x)


Whenever I find myself using a lambda, I usually replace it with a local definition:

factor = unit >>= factor'
where
factor' x
=  try (char '?' >> return (Or Epsilon x))
<|> try (char '+' >> return (Then x (Star x)))
<|> try (char '*' >> return (Star x))
<|> return x


Since you only need to look at one character to pick the right branch, you don't need to use try everywhere:

factor = unit >>= factor'
where
factor' x
=  (char '?' >> return (Or Epsilon x))
<|> (char '+' >> return (Then x (Star x)))
<|> (char '*' >> return (Star x))
<|> return x


Finally, we can get rid of the extra parens by using *> instead of >>, and we can replace return with pure:

factor = unit >>= factor'
where
factor' x
=  char '?' *> pure (Or Epsilon x)
<|> char '+' *> pure (Then x (Star x))
<|> char '*' *> pure (Star x)
<|> pure x


This works because *> has higher precedence than <|> which has higher precedence than >>.

I find this easier to read. We've restricted the bulk of our code to Applicative operations, and we only need to use Monadic bind at the beginning where factor' has a direct dependency on unit.

EDIT: We don't need try anymore because char x only consumes a character if the next character in the input stream matches x. Furthermore, each of your branches can either completely match or it can completely fail, and there's no danger of overlap between rules. As an example, here's a simple parser that, like yours, has simple match-or-fail parsers that consume only one character and do not overlap:

data Foo = One | Zero
deriving (Eq, Show)

foo =  char '1' *> pure One
<|> char '0' *> pure Zero


If we decide to add a new rule that does overlap, we'll have a problem:

data Foo = One | Zero | Ten
deriving (Eq, Show)

foo =  char '1' *> pure One
<|> char '0' *> pure Zero
<|> char '1' *> char '0' *> pure Ten


Now our first and last rule overlap! We can never successfully parse a Ten:

> parse foo "" "1"
Right One
> parse foo "" "10"
Right One


One's first instinct might be to switch the order of the rules, but this just introduces a new problem:

foo =  char '1' *> char '0' *> pure Ten
<|> char '0' *> pure Zero
<|> char '1' *> pure One

> parse foo "" "10"
Right Ten
> parse foo "" "1"
Left (line 1, column 2):
unexpected end of input
expecting "0"


Since the first char '1' has already consumed a character, we've committed to that branch. This is the case where you want to use try; where you might need to backtrack after initially committing to some rule that consumes input:

foo =  try (char '1' *> char '0' *> pure Ten)
<|> char '0' *> pure Zero
<|> char '1' *> pure One

> parse foo "" "0"
Right Zero
> parse foo "" "1"
Right One
> parse foo "" "10"
Right Ten


Because many parsers are more complicated than char, it can be easy to just add try without thinking. This can make your parser less efficient because it may have to backtrack many times before it makes progress. It can be worth your time to investigate whether a try is really necessary.