## Parser combinators

Parser combinators serve as a great introduction to Functional Programming, and are one of the most-studied topics in the field. Nevertheless, they are a very complex and broad topic, covering concepts such as non-determinism, monads, and higher-order functions.

What people may not get as much exposure to, at least in my experience, is many of the Haskell type classes and their relationship to parsers. As we'll see in this article, the most common and useful combinators are actually parser-specific versions of more widely useful generic operations.

## Type classes

The definitions of the type classes used are based on both the standard Haskell classes of the same name (minus the '), and Brent Yorgey's Typeclassopedia. I've added a ' to the end of each of their names to indicate that they're not identical to the standard Haskell classes, and in some cases are quite different. I've also added one type class of my own -- Switch' -- which represents the ability to convert a failing computation into a successful one with a default value, and to convert a successful computation into a failing one. I wasn't able to find a type class providing this functionality on Hoogle.

## Parser definition and basic combinators

Following convention, parsers are modeled as functions that operate on token streams, either producing a result paired with the rest of the token stream, or failing. A convenient choice for representing possible failure is the Maybe data type.

newtype Parser t a = Parser { getParser :: [t] -> Maybe ([t], a) } run :: Parser t a -> [t] -> Maybe ([t], a) run = getParserIn addition, we'll use these basic parsers repeatedly throughout the examples to build bigger and more exotic parsers:

-- succeeds, consuming one token, as -- long as input is not empty getOne :: Parser s s getOne = Parser (\xs -> case xs of (y:ys) -> pure (ys, y); _ -> empty) -- runs the parser, and if it succeeds, -- checks that its result satisfies a predicate check :: (a -> Bool) -> Parser s a -> Parser s a check f p = p >>= \x -> guard (f x) >> pure x -- consumes one token if the token -- satisfies a predicate satisfy :: (a -> Bool) -> Parser a a satisfy p = check p getOne -- builds a parser that only -- matches the given token literal :: Eq a => a -> Parser a a literal tok = satisfy (== tok)

## Alternation and failure

Alternation and failure are covered by the semigroup and monoid classes, respectively. Semigroups are characterized by an associative, binary, closed operation.

The parser interpretation of semigroups is choice: given two parsers, use the first one if it succeeds, but use the second one if the first fails.

class Semigroup' a where (<|>) :: a -> a -> a instance Semigroup' (Parser s a) where Parser f <|> Parser g = Parser (\xs -> f xs <|> g xs)This implementation exploits the fact that the Maybe datatype can also form a left-biased semigroup.

Monoids are semigroups whose binary operation has an identity element; for parsers, this means that applying the choice operator to any parser plus the identity parser will always return the result of the first parser, regardless of whether it fails or succeeds. The identity parser always ignores its input and fails:

class Semigroup' a => Monoid' a where empty :: a instance Monoid' (Parser s a) where empty = Parser (const Nothing)

Here are some examples:

-- combining two parsers with choice: succeeds if either parser succeeds a :: Parser Char Char a = literal 'a' b :: Parser Char Char b = literal 'b' ab :: Parser Char Char ab = a <|> b $ run ab "babcd" Just ("abcd",'b') $ run ab "abcd" Just ("bcd",'a') -- the empty parser always fails fail :: Parser Char Char fail = empty $ run fail "abcd" $ Nothing -- the empty parser is both a right and a left identity a_ :: Parser Char Char a_ = a <|> fail _a :: Parser Char Char _a = fail <|> a $ run a_ "abcd" Just ("bcd",'a') $ run a_ "babcd" Nothing $ run _a "abcd" Just ("bcd",'a') $ run _a "babcd" NothingWe're not limited to combining two parsers at a time, of course; there is also the 'mconcat' combinator:

mconcat :: Monoid' a => [a] -> a mconcat = foldr (<|>) empty $ run (mconcat []) "abcde" Nothing digits :: [Parser Char Char] digits = map literal ['0' .. '9'] $ run (mconcat digits) "4hi!!" Just ("hi!!", '4')'mconcat' combines a list of monoids using the binary operation, and the identity element as the base case. This means that using 'mconcat' on an empty list will generate a parser that always fails.

## Success

Similarly to the parser that always fails, we have a parser that always succeeds. This is captured by the pointed class, which is the 'pure' part of the Applicative class in the standard Haskell libraries. This class allows you to lift a value into a context; for parsers, we build a parser that always succeeds, with the specified value as its result, and consuming zero tokens.

class Pointed' f where pure :: a -> f a instance Pointed' (Parser s) where pure a = Parser (\xs -> Just (xs, a))

Examples:

pass :: Parser Integer String pass = pure "Hello, world!" $ run pass [] Just ([],"Hello, world!") $ run pass [1,100,31] Just ([1,100,31],"Hello, world!")The parser 'pass' always succeeds, even with empty input; it simply returns its input token stream along with its value.

## Mapping and sequencing

It's also useful to have access to a parser's value for further processing; a common use case is building up a parse tree. This concept is captured by the Functor class, which lifts a normal function to a function that operates on the result value of a parser. The parser interpretation is that, given a function and a parser, if the parser succeeds, map the function over its results; whereas if the parser fails, just propagate the failure.

class Functor' f where fmap :: (a -> b) -> f a -> f b instance Functor' (Parser s) where -- one 'fmap' for the Maybe, one for the tuple fmap f (Parser g) = Parser (fmap (fmap f) . g)

The Applicative class enables not just lifting, but application in which both the function and its arguments are in contexts. It allows parsers to be run in sequence, where the first parser is run, and if it fails, the whole chain fails; if it succeeds, the rest of the token stream is passed to the next parser and its result is collected, and so on. This implementation makes use of the Monad instance of Maybe, although it could also be implemented without such an assumption.

class Functor' f => Applicative' f where (<*>) :: f (a -> b) -> f a -> f b instance Applicative' (Parser s) where Parser f <*> Parser x = Parser h where h xs = f xs >>= \(ys, f') -> x ys >>= \(zs, x') -> Just (zs, f' x')

Here are some examples:

one :: Parser Char Char one = literal '1' oneInt :: Parser Char Int oneInt = fmap (\x -> (read :: String -> Int) [x .. '9']) one $ run oneInt "123" Just ("23",123456789) two :: Parser Char Char two = literal '2' twelve :: Parser Char (Char, Char) twelve = pure (,) <*> one <*> two $ run twelve "123" Just ("3",('1','2')) $ run twelve "1123" Nothing

The first example shows a Char parser ('one') that is converted into an Int parser using 'fmap' and a function of type 'Char -> Int'. The second example applies the '(,)' function within an Applicative parser context, tupling the results of the parsers 'one' and 'two'. The third example shows that parsers run in sequence must all succeed for the entire match to succeed; although the '1' is matched, the '2' cannot be.

The power of Applicative parsers can also be harnessed to create parsers that ignore the results (but not the effects!) of some or all of their parsers:

(*>) :: Parser t a -> Parser t b -> Parser t b l *> r = fmap (flip const) l <*> r (<*) :: Parser t a -> Parser t b -> Parser t a l <* r = fmap const l <*> rBoth '(*>)' and '(<*)' will only succeed if both of their arguments succeed in sequence; the difference is that '(*>)' only returns the result of the 2nd parser, while '(<*)' only returns the result of the 1st parser. Examples, using the 'one' and 'two' parsers defined above:

$ run (two *> one) "212345" Just ("2345",'1') $ run (two <* one) "212345" Just ("2345",'2')

Combining Applicatives with Semigroups, we can create repeating parsers:

many :: Parser t a -> Parser t [a] many p = some p <|> pure [] some :: Parser t a -> Parser t [a] some p = fmap (:) p <*> many p(note that 'some' and 'many' are mutually recursive). 'many' tries to run its parser as many times as possible, progressively chewing up input; it always succeeds since it's fine with matching 0 times. On the other hand, 'some' matches its parser at least once, failing if it can't match it at all, but other than that is identical to 'many'. Examples (using 'one' from above):

$ run (fmap length $ many one) "111111234" Just ("234",6) $ run (many one) "23434593475dkljdfs" Just ("23434593475dkljdfs","") $ run (fmap length $ one) "111111234" Just ("234",6) $ run (some one) "23434593475dkljdfs" Nothing

## Negations

Oftentimes, parsing conditions are easier to state in the negative than in the positive. For instance, if you were parsing a string, you might look for a double-quote character to open the string, and another double-quote to end the string. Meanwhile, anything that's *not* a double-quote which comes after the opening will be part of the string. To capture this pattern, I created the 'Switch' class:

class Switch' f where switch :: f a -> f () instance Switch' (Parser s) where switch (Parser f) = Parser h where h xs = fmap (const (xs, ())) $ switch (f xs)This converts a failing parser to a successful one and vice versa. Importantly, it consumes no input from the token stream -- it acts as a negative lookahead parser, which allows us to build flexible parsers on top of it. Examples:

not1 :: Parser t b -> Parser t t not1 p = switch p *> getOne dq :: Parser Char Char dq = literal '"' not_dq :: Parser Char Char not_dq = not1 dq dq_string :: Parser Char String dq_string = dq *> many not_dq <* dq $ run dq_string "\"no ending double-quote" Nothing $ run dq_string "\"I'm a string\"abcxyz" Just ("abcxyz","I'm a string")The 'not1' combinator takes a parser as input, runs that parser, and if it succeeds, 'not1' fails; if that parser fails, 'not1' then tries to consume a single token (any token). In other words, it's like saying "I want anything but

The 'not_dq' parser matches any character that's not a double-quote; the string parser matches a double-quote followed by any number of non-double-quotes, followed by another double-quote; it throws away the results of both double-quote parsers, only returning the body of the string.

## Running many parsers in sequence

Traversable is an interesting type class. It allows you to 'commute' two functors; i.e. if you have '[Maybe Int]', it allows you to create 'Maybe [Int]' (that is, turn a list of 'Maybe Int's into a 'Maybe' list of Ints. This is also useful for parsing, where it allows one to convert a list of parsers into a (single) parser of lists. In this case, we don't need to supply an instance for 'Parser' because the Functor in question is lists:class Functor' t => Traversable' t where commute :: (Pointed' f, Applicative' f) => t (f a) -> f (t a)Here are some examples (using 'digits' from above):

six_fours :: [Parser Char Char] six_fours = replicate 6 (literal '4') $ run (commute digits) "0123456789abcxyz" Just ("abcxyz","0123456789") $ run (commute six_fours) "4444449999999" Just ("9999999","444444") $ run (commute six_fours) "44444 oops that was only 5 fours" Nothing

## Monads

What parsing article could be complete without mentioning monads? Monads are similar to applicatives, but add the extra ability to have computations depend on the result of previous computations. Here's the class definition and parser implementation:

class (Applicative' m, Pointed' m) => Monad' m where join :: m (m a) -> m a instance Monad' (Parser s) where join (Parser f) = Parser h where h xs = f xs >>= \(o, Parser g) -> g oA good example of putting this extra power to work is this combinator:

twice :: Eq a => Parser a a -> Parser a a twice p = p >>= \x -> literal xIt runs its input parser, and if it succeeds, attempts to match the *same* output a second time. Thus, the second match depends on the results of the first. We can't build such a parser using applicatives (although we can build less general versions by enumerating multiple cases). Here's an example showing how it's different from an Applicative version, using the 'ab' parser from earlier:

ab_twice :: Parser Char Char ab_twice = twice ab -- using monads $ run ab_twice "aa123" Just ("123",'a') $ run ab_twice "ab123" Nothing -- using applicatives $ run (pure (,) <*> ab <*> ab) "aa123" Just ("123",('a','a')) $ run (pure (,) <*> ab <*> ab) "ab123" Just ("123",('a','b'))In the first example, which uses monadic parsing, 'ab_twice' parses the first input and fails on the second. However, the second example -- with applicatives -- successfully parses both inputs. It sees the two parsers as being totally independent of each other and thus isn't able to require that the second one match the same tokens as the first one.

## Relationship to BNF grammars, regular expressions, etc.

Of course, all of these useful parsing combinators have also been applied in other parsing approaches, such as grammars and regular expressions. Here's a quick correspondence:BNF/regex | combinators |
---|---|

| | <|> of semigroups |

sequencing | <*> of applicatives |

* | many |

+ | some |

grouping | always explicitly grouped |

## What's next & further reading

There are a few topics that weren't covered in this article. First and foremost, good error detection and reporting is a key component of a parser library that's friendly and easy to use. Second, although I chose to use the Maybe data type to model the results, this could be extended to use any arbitrary monad -- resulting in a much richer set of parsers. Two examples are the list monad, to allow non-deterministic parses, and the state monad, two allow context-dependent parses.

If you're interested in learning more about parsing, Philip Wadler, Graham Hutton, and Doaitse Swierstra have published some excellent papers over the years on the topic; reading their papers was what really helped me to understand parsing. And of course there's also the powerful Parsec tool, a Haskell-based library for parser combinators which illustrates these ideas in a practical context.

## No comments:

## Post a Comment