Parser Combinators

Parsers are values

Haskell is famous for parser combinators: small parsers for numbers, symbols or keywords are combined with ordinary functions into parsers for whole languages. A parser is a value of a type such as Parser a, which consumes input and produces an a or an error. Because parsers are Functors, Applicatives and Monads, you combine them with familiar tools: <$> to transform results, <*>, *> and <* to sequence, <|> (from Alternative) for choice, many and some for repetition, and do notation for context-sensitive parsing. megaparsec is the most widely used library, with excellent error messages, Text support and helpers for lexing (Text.Megaparsec.Char.Lexer); attoparsec is faster for machine formats, and parsec is the classic predecessor. Common pattern: define a lexeme combinator that skips trailing whitespace and build the grammar from the bottom up, handling operator precedence with layered parsers or makeExprParser from parser-combinators. Parsers built this way are type-checked, testable and much more maintainable than regular expressions for anything non-trivial.

An arithmetic expression parser and evaluator

Precedence by layering: expressions, terms and atoms.

import Data.Void (Void)
import Text.Megaparsec
import Text.Megaparsec.Char (space)
import qualified Text.Megaparsec.Char.Lexer as L

type Parser = Parsec Void String

data Expr = Num Integer | Add Expr Expr | Mul Expr Expr
  deriving Show

lexeme :: Parser a -> Parser a
lexeme = L.lexeme space

symbol :: String -> Parser String
symbol = L.symbol space

atom :: Parser Expr
atom = Num <$> lexeme L.decimal
   <|> between (symbol "(") (symbol ")") expr

term :: Parser Expr                  -- multiplication binds tighter
term = foldl Mul <$> atom <*> many (symbol "*" *> atom)

expr :: Parser Expr
expr = foldl Add <$> term <*> many (symbol "+" *> term)

eval :: Expr -> Integer
eval (Num n)   = n
eval (Add a b) = eval a + eval b
eval (Mul a b) = eval a * eval b

main :: IO ()
main = do
  case parse (space *> expr <* eof) "<input>" "2 + 3 * (4 + 1)" of
    Left err -> putStr (errorBundlePretty err)
    Right e  -> print (eval e)                    -- 17
  parseTest (space *> expr <* eof) "2 + * 3"      -- prints a helpful error message

Lego bricks for grammars

Parser combinators are Lego bricks: a brick that reads a digit, a brick that reads a plus sign, and connectors that say "one after another", "either this or that" or "as many as you like". Snap them together and you have a parser for a whole language.

Quick check: What does the <|> combinator do between two parsers?

• Runs both and combines results
• Repeats a parser
• Skips whitespace
• Tries the first parser and, if it fails without consuming input, tries the second