Monadic Parser Combinators

This repository contains the support material for a presentation I made about "monadic parser combinators". I took the key concepts from the chapter 8 of the book Programming in Haskell book by Graham Hutton.

If you want to check out the slides of the aforementioned presentation, plase click here.

What is Covered?

Parser Type

A parser for things
Is a function from strings
To lists of pairs
Of things and strings

type Parser a = String -> [(a, String)]

Primitive Parsers

The success parser.

return :: a -> Parser a
return v = \input -> [(v, input)]

The failure parser.

failure :: Parser a
failure = \input -> []

The item parser.

item :: Parser Char
item = \input -> case input of
                  []     -> []
                  (x:xs) -> [(x, xs)]

Combinators

Choice. +++ can be read as "or else".

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \input -> case parse p input of
                     []         -> parse q input
                     [(v, out)] -> [(v, out)]

Sequencing. >>= can be read as "then" or even better, "bind".

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = \input -> case parse p input of
                      []         -> []
                      [(v, out)] -> parse (f v) out

Derived Primitives

sat. Parse a character that satisfies a predicate.

sat :: (Char -> Bool) -> Parser Char
sat p = do
  c <- item
  if p c
     then return c
     else failure

digit. Parse a character if it is a digit.

digit :: Parser Char
digit = sat isDigit

Keep in mind that isDigit is defined in Data.Char.

char. Parse a character if it is the given char.

char :: Char -> Parser Char
char c = sat (c ==)

many. Apply a parser zero or more times.
many1. Apply a parser one or more times

many :: Parser a -> Parser [a]
many p = many1 p +++ return []


many1 :: Parser a -> Parser [a]
many1 p = do
  v  <- p
  vs <- many p
  return (v:vs)

Arithmetic Expressions

Grammar

ε means empty string
expr   = term (+ expr | ε)
term   = factor (* term | ε)
factor = (expr) | digit
digit  = 0 | 1 | 2 ...

So that 2 + 3 + 4 is:

Then, the grammar is defined as follows:

1. expr

   expr :: Parser Int
   expr = do
     t <- term
     addExprTo t +++ return t
     where
       addExprTo t = do
         char '+'
         e <- expr
         return (t + e)

2. term

   term :: Parser Int
   term = do
     f <- factor
     multTermWith f +++ return f
     where
       multTermWith f = do
         char '*'
         t <- term
         return (f * t)

3. factor

   factor :: Parser Int
   factor = do
     expr' +++ digit'
       where
         expr' = do
           char '('
           e <- expr
           char ')'
           return e
         digit' = do
           d <- digit
           return (digitToInt d)

eval evaluates a given expression.

eval :: String -> Int
eval xs = case parse expr xs of
            [(n, [])]  -> n
            [(_, out)] -> error ("unused input " ++ out)
            []         -> error "invalid input"

Local Development

1. Fork the project on GitHub and clone your fork locally.

   $ git clone git://github.com/username/parser-combinators.git
   $ cd parser-combinators
   $ git remote add upstream https://github.com/acamino/parser-combinators.git

2. Install Stack.

3. Get the appropriate GHC for the project.

   $ stack setup

4. Make sure the tests succeed.

   $ stack test

5. If you want to launch a REPL and have fun with this parser.

   $ stack repl

Issues & Support

Please file tickets for bug or problems.

Contributing

Edits and enhancements are welcome. Just fork the repository, make your changes and send me a pull request.

Licence

The code in this repository is licensed under the terms of the MIT License.
Please see the LICENSE file for details.