Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 57 ยท Real-world Haskell

Parsing with Parser Combinators

Build a Haskell parser from small functions: Parser as a function, Functor, Applicative and Alternative instances, an expression grammar, and megaparsec.

Almost every program has to read text with some structure: a configuration file, a command, a formula, a query. Haskell has a beautiful answer called parser combinators. You write tiny parsers for the smallest pieces (one digit, one letter) and combine them with ordinary functions into parsers for bigger pieces (a number, a sum, a whole file). The finished parser reads like the grammar it implements.

This lesson builds a parser library in about thirty lines, then uses it for arithmetic. It relies on functors, applicatives and monads, and on recursive types.

Real Haskell is not installed on this site, so Haskell blocks are read-only. The runnable examples are JavaScript stand-ins with the same structure.

A parser is a function

The central idea: a parser takes the input text and either fails, or succeeds with a value and the rest of the input.

HASKELL
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

Nothing means failure. Just (value, rest) means a value was read and rest is what is left over. The simplest real parser reads one character that satisfies a test:

HASKELL
satisfy :: (Char -> Bool) -> Parser Char
satisfy ok = Parser $ \input -> case input of
  (c : cs) | ok c -> Just (c, cs)
  _               -> Nothing

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

Everything else is built from these.

A parser, in one sentence

Input A string of text.
Output A value plus the leftover text, or failure.
1 / 2

Functor, Applicative and Alternative

To combine parsers we give Parser the usual instances:

HASKELL
instance Functor Parser where
  fmap f (Parser p) = Parser $ \s -> case p s of
    Nothing        -> Nothing
    Just (a, rest) -> Just (f a, rest)

instance Applicative Parser where
  pure a = Parser $ \s -> Just (a, s)
  Parser pf <*> Parser pa = Parser $ \s -> case pf s of
    Nothing         -> Nothing
    Just (f, rest)  -> case pa rest of
      Nothing          -> Nothing
      Just (a, rest')  -> Just (f a, rest')

instance Alternative Parser where
  empty = Parser (const Nothing)
  Parser p <|> Parser q = Parser $ \s -> case p s of
    Nothing -> q s
    result  -> result

What each one means for parsing:

  • fmap transforms the result without consuming more input, such as turning digit characters into an Int.
  • <*> runs one parser, then the next on the leftover text, and combines the two results. Use it to describe a sequence.
  • <|> tries the left parser, and only if it fails, the right one. That is choice.
  • many and some come free from Alternative: zero or more, and one or more, repetitions.

A number parser is now a one-liner:

HASKELL
number :: Parser Int
number = read <$> some (satisfy isDigit)

A parser for "(1,2)" reads exactly like the format:

HASKELL
pair :: Parser (Int, Int)
pair = (,) <$> (char '(' *> number) <*> (char ',' *> number <* char ')')

The arrows *> and <* mean "run both, keep the right (or left) result". They are how you skip punctuation.

A runnable stand-in

In JavaScript a parser is a function from a string to null (failure) or { value, rest }. The combinators have the same names as the Haskell ones. Real Haskell gets <$>, <*> and <|> as operators from the type classes; here they are plain functions.

JS Building a parser library

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last line prints null: the parser failed at ;. Notice that the deeply nested bind calls are exactly what do notation hides in Haskell.

An expression grammar

Arithmetic with +, -, *, / and parentheses has a grammar that encodes precedence by layering:

TEXT
expr   = term   (("+" | "-") term)*
term   = factor (("*" | "/") factor)*
factor = number | "(" expr ")"

Multiplication binds tighter because term sits inside expr. In Haskell, each rule becomes a parser. The repeated tail is handled with a fold, which also makes the operators left-associative, so 10 - 3 - 2 is (10 - 3) - 2:

HASKELL
expr :: Parser Int
expr = term >>= rest
  where
    rest acc = (do op <- (char '+' *> pure (+)) <|> (char '-' *> pure (-))
                   t  <- term
                   rest (op acc t))
               <|> pure acc

factor :: Parser Int
factor = number <|> (char '(' *> expr <* char ')')

factor mentions expr and expr ends up mentioning factor: the parsers are mutually recursive, which Haskell's laziness allows.

JS Evaluating arithmetic while parsing

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Precedence comes out right: 1 + 2 * 3 is 7 and (1 + 2) * 3 is 9. Inputs that are only partly valid, such as 2 *, leave text over and are reported as errors, because run insists on consuming everything.

Better errors: from Maybe to a real parser type

Our Maybe parser says that parsing failed but not where or why. Production parsers track the position and the set of things that were expected. In real Haskell you would not write this yourself. The standard choices are:

  • megaparsec: the most popular. Good error messages, support for any input type, a Parsec monad with try for backtracking, plus helpers for lexing and for operator tables (Text.Megaparsec, Control.Monad.Combinators.Expr).
  • attoparsec: very fast, aimed at binary and network protocols; weaker errors.
  • parsec: the classic ancestor, still found in many codebases.
HASKELL
-- megaparsec sketch (read-only)
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L

type Parser = Parsec Void String

integer :: Parser Int
integer = L.lexeme space L.decimal

parens :: Parser a -> Parser a
parens = between (L.symbol space "(") (L.symbol space ")")

Its error messages look like 1:5: unexpected ')', expecting digit or '(', and they come for free.

Alternation <|> in megaparsec does not backtrack after a parser has consumed input. If two branches start with the same characters, wrap the first in try. Forgetting this is the most common surprise.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the simple Parser type String -> Maybe (a, String) return on success?

    Returning the rest of the input lets the next parser continue where this one stopped.
  2. 2. What does p <|> q do?

    <|> from Alternative is choice: the first successful parser wins.
  3. 3. How does the layered grammar (expr contains term contains factor) give * higher precedence than +?

    A term is fully parsed, including all its * and / operators, before expr sees the + or -.
  4. 4. In megaparsec, when do you need try?

    After a branch consumes input, megaparsec does not backtrack. try restores the input so the next alternative can run.

Summary

  • A parser is a function from input to a result plus the remaining input, or failure.
  • Functor transforms results, Applicative sequences parsers, Alternative offers choice, and many/some repeat.
  • A grammar translates directly into mutually recursive parsers; layering rules gives operator precedence.
  • Left-associative operators are parsed with a fold over (op operand)*.
  • Use megaparsec (or attoparsec for speed) in real projects for good error messages.
  • Remember try when alternatives share a prefix.

Next: JSON and Web Services.