Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking

The paper:

Bryan Ford's 2002 Masters Thesis is remarkable in that it breaks decades of compiler-construction dogma with some simple principles and a compelling alternative to the complexity of parsing with context-free grammars (CFGs). He reveals a forgotten class of grammars-- top-down parsing language (TDPL), and some extensions known as parsing-expression grammars (PEGS) -- that directly correspond to the parsers that implement them. His primary contribution, however, is applying modern functional programming techniques of laziness and algebraic data structures to make TDPL/PEG parsers computationally efficient.

The paper can be found here: http://bford.info/pub/lang/thesis.pdf

About our speaker:

Sean Cribbs is a Software Engineer at Basho Technologies, where he has contributed to many aspects of Riak, the distributed database and regularly hacks in Erlang, Python, Ruby and JavaScript. Prior to Basho, Sean was a freelance developer and consultant who also managed the development of the open-source Radiant web publishing system. Sean enjoys playing the piano in his free time.