Parser Combinators

Haskell is famously good at parsing. Instead of regular expressions or parser generators, you build parsers as ordinary values, and combine small parsers into bigger ones with Functor, Applicative, and Monad operators. The standard libraries are:

• megaparsec — modern, fast, with excellent error messages (the usual choice today)
• parsec — the classic library, shipped with GHC
• attoparsec — very fast, for machine-generated formats

A megaparsec parser

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

type Parser = Parsec Void String

data Color = Color Int Int Int
  deriving (Show)

hexByte :: Parser Int
hexByte = do
  a <- hexDigitChar
  b <- hexDigitChar
  return (read ("0x" ++ [a, b]))

color :: Parser Color
color = char '#' *> (Color <$> hexByte <*> hexByte <*> hexByte) <* eof

keyValue :: Parser (String, Int)
keyValue = do
  key <- some letterChar
  space
  _ <- char '='
  space
  value <- L.decimal
  return (key, value)

main :: IO ()
main = do
  print (parse color "" "#ff8000")
  print (parse (keyValue `sepBy` (char ',' >> space)) "" "width = 80, height=24")
  putStr (either errorBundlePretty show (parse color "input" "#ff80zz"))

Right (Color 255 128 0)
Right [("width",80),("height",24)]
input:1:6:
  |
1 | #ff80zz
  |      ^
unexpected 'z'
expecting hexadecimal digit

• Parsec Void String is a parser over String input with no custom error type. For real input, parse Text.
• *> and <* run two parsers and keep the right or left result; <$> and <*> build a value from the pieces.
• some, many, sepBy, optional, and <|> (choice) combine parsers.
• errorBundlePretty shows the position and what was expected.

An arithmetic expression parser

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

type Parser = Parsec Void String

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

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

number :: Parser Integer
number = lexeme L.decimal

factor :: Parser Integer
factor = number <|> between (symbol "(") (symbol ")") expr

term :: Parser Integer
term = chainl factor ((*) <$ symbol "*" <|> div <$ symbol "/")

expr :: Parser Integer
expr = chainl term ((+) <$ symbol "+" <|> (-) <$ symbol "-")

chainl :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl p op = p >>= rest
  where
    rest x = (do f <- op; y <- p; rest (f x y)) <|> return x

main :: IO ()
main = do
  print (parse (space *> expr <* eof) "" "2 + 3 * 4")
  print (parse (space *> expr <* eof) "" "(2 + 3) * 4 - 10 / 2")
  print (either (const "parse error") show (parse (space *> expr <* eof) "" "2 +"))

Right 14
Right 15
"parse error"

Each grammar rule is a function, and precedence falls out of the structure: expr is made of terms, which are made of factors. The lexeme helper skips whitespace after every token. (The parser-combinators package provides a ready-made makeExprParser for operator tables.)

Parsing without a library

Text.ParserCombinators.ReadP in base is a small combinator library available everywhere, useful for scripts and exercises:

import Text.ParserCombinators.ReadP
import Data.Char (isDigit)

date :: ReadP (Int, Int, Int)
date = do
  y <- read <$> count 4 (satisfy isDigit)
  _ <- char '-'
  m <- read <$> count 2 (satisfy isDigit)
  _ <- char '-'
  d <- read <$> count 2 (satisfy isDigit)
  eof
  return (y, m, d)

main :: IO ()
main = do
  print (readP_to_S date "2026-09-29")
  print (readP_to_S date "2026-9-29")

[((2026,9,29),"")]
[]

readP_to_S returns every successful parse with the leftover input; an empty list means failure.