Just Parsing Through
SETUP - You should have a basic understanding of Haskell (what data types, functions and type classes are) and have a working GHC installation. Clone and build these exercises
The default tool that many programmers immediately reach for when they wish to parse data (but don't want to deal with tools like Lex and Yacc) is regular expressions.
Of course, whenever you mention regular expressions, someone will bring up Jamie Zawinski. And now you have two problems.
However, regular expressions have many problems:
- They aren't composable
- They're typically represented as Strings rather than code making them harder to debug
- Often only interpreted at runtime leading to runtime failures (no static type checking!)
- They can't be used to parse HTML
The preferred approach in functional programming languages (also available in non-functional languages as well!) is parser combinators, which provide a way of writing your parser in code, thus being able to use all your existing tooling to do so.
In this workshop we will build up our own Parser Combinator library from scratch (and hopefully make sense of the dreaded M-word whilst we're at it!) and improve upon it, to see that there is nothing mystical about parsing in data.
Outline/Structure of the Workshop
- Write a basic parser from scratch (with motivating examples)
- This includes covering the Functor/Applicative/Monad (+Alternative) hierarchy
- Investigate how to optimise it:
- Better error messages
- Alternative implementations
- Understand how parser combinators work
- Be able to use parser combinator libraries
- Gain an appreciation for the Functor/Applicative/Monad typeclasses
Beginner to intermediate level developers that want to know how to write and use parser combinators.
Prerequisites for Attendees
You should have a basic understanding of Haskell (what data types, functions and type classes are) and have a working GHC installation. Clone and build these exercises
(You can use another language other than Haskell if you prefer, but I may not be able to assist you if you run into any problems.)
Unlike many (most?) Haskell developers, I didn't undertake my rite of passage of writing a Monad tutorial. Instead, I decided to write (but alas never finish) my own parser combinator library. This was after I basically ended up really learning Haskell by extending and maintaining the graphviz library for Haskell (and trying to deal with the ever changing non-standard that is the DOT language).