Parsing

A parser for things is a function from strings to lists of pairs of things and strings!

Libraries

• Parsec
• attoparsec
• polyparse
• uu-parsing-lib
• trifecta
• Megaparsec

Attoparsec

• CPS is great! CPS is terrible!
• What’s in a parsing library
  • Parsec has an appealing API.
  • Parsec 3 is slower than Parsec 2.
  • Parsec’s API demands that all of a parser’s input be available at once.
• What’s in a parser? Attoparsec rewired
• A major upgrade to attoparsec: more speed, more power
  • 3rd generation attoparsec is much faster.
  • 0.11 -> 0.12
  • Up to x2 on micro-benchmarks.
  • Uses buffers and cursors (index into buffer).
    • Uses unsafe tricks to grow the buffer.
    • Remains resilent to programmer misuse via a “generation” tag.

Megaparsec

• The original Megaparsec 4.0.0 announcement
• Megaparsec 4 and 5
• Announcing Megaparsec 5
• Latest additions to Megaparsec
• Metaparsec tutorials

Other articles

• Parsec: “try a <|> b” considered harmful

Papers

• How to replace failure by a list of successes — A method for exception handling, backtracking, and pattern matching in lazy functional languages, 1985
• Monadic Parser Combinators, 1996
• Monadic Parsing in Haskell (Functional Pearl), 1998
• Parsec: Direct Style Monadic Parser Combinators for the Real World, 2001
• Combinator Parsing: A Short Tutorial, 2008. The genesis of uu-parsinglib.