Haskell Parser Combinators Guide — Parsec, Attoparsec, and Megaparsec

In this tutorial, you will learn about Haskell Parser Combinators Guide. We cover key concepts, practical examples, and best practices to help you master this topic.

Haskell parser combinators like Parsec build modular parsers from small primitive parsers using combinators -- (<|>) for choice, many for zero-or-more, and token for character matching -- with Attoparsec for high-performance streaming and Megaparsec for excellent error messages.

Basic Parsec

import Text.Parsec
import Text.Parsec.String (Parser)

-- Parse a single digit
digit :: Parser Char
digit = oneOf "0123456789"

-- Parse a number (one or more digits)
number :: Parser Int
number = do
    digits <- many1 digit
    return $ read digits

-- Parse addition
addition :: Parser Int
addition = do
    x <- number
    spaces
    char '+'
    spaces
    y <- number
    return $ x + y

Combinators

-- Choice: (<|>) tries first, if fails tries second
color :: Parser String
color = string "red" <|> string "green" <|> string "blue"

-- Repetition
many p    -- zero or more
many1 p   -- one or more
optional p -- zero or one

-- Between
-- between open close p parses p between open and close
parens = between (char '(') (char ')')
braces = between (char '{') (char '}')

-- Example: (123)
parsed = parse (parens number) "" "(123)"

Expression Parsing

import Text.Parsec
import Text.Parsec.Expr
import Text.Parsec.Token

expr :: Parser Int
expr = buildExpressionParser operators term

operators = [
    [Prefix (char '-' >> return negate)],
    [Infix (char '*' >> return (*)) AssocLeft,
     Infix (char '/' >> return div) AssocLeft],
    [Infix (char '+' >> return (+)) AssocLeft,
     Infix (char '-' >> return (-)) AssocLeft]
    ]

term :: Parser Int
term = number <|> parens expr

-- Usage: parse expr "" "2+3*4" = Right 14

JSON Parser Example

{-# LANGUAGE OverloadedStrings #-}
import Data.Attoparsec.Text
import Data.Text (Text)

jsonValue :: Parser Value
jsonValue = object <|> array <|> string' <|> number' <|> bool <|> null'

object = do
    char '{'
    pairs <- sepBy pair (char ',')
    char '}'
    return $ Object pairs

pair = do
    key <- stringLiteral
    char ':'
    val <- jsonValue
    return (key, val)

array = between (char '[') (char ']') $
    sepBy jsonValue (char ',')

Common Mistakes

1. Left Recursion

expr = expr <|> term never terminates. Use chainl1 or buildExpressionParser with proper associativity.

2. Not handling whitespace

Always parse optional whitespace between tokens: lexeme, spaces, or pipe through a token layer.

3. Overlapping choices

string "if" <|> string "ifx" never matches "ifx" because "if" succeeds first. Order choices from most specific.

Practice Questions

1. What does (<|>) do in parsing? Choice combinator: try the first parser, if it fails try the second. Like alternation in grammars.

2. What is the difference between many and many1? many p matches zero or more occurrences (always succeeds). many1 p requires at least one match.

3. How do you handle operator precedence? Use buildExpressionParser with a table of operators grouped by precedence level, ordered from lowest to highest.

FAQ

{{< faq question="Which parser library should I use?" >}} Megaparsec for good error messages and general use. Attoparsec for high-performance streaming. Parsec for compatibility (older code). {{< /faq >}}

{{< faq question="What is the difference between lexing and parsing?" >}} Lexing tokenizes input into tokens. Parsing builds an AST from tokens. Most combinator libraries skip separate lexing. {{< /faq >}}

{{< faq question="How do I make parsers fast?" >}} Avoid Backtracking (try). Use commit points. For large input, use Attoparsec which works on Text/ByteString. {{< /faq >}}

What's Next

Now learn about concurrency in Haskell.