addressalign-toparrow-leftarrow-rightbackbellblockcalendarcameraccwchatcheckchevron-downchevron-leftchevron-rightchevron-small-downchevron-small-leftchevron-small-rightchevron-small-upchevron-upcircle-with-checkcircle-with-crosscircle-with-pluscrosseditemptyheartexportfacebookfolderfullheartglobegmailgoogleimageimagesinstagramlinklocation-pinmagnifying-glassmailminusmoremuplabelShape 3 + Rectangle 1outlookpersonplusprice-ribbonImported LayersImported LayersImported Layersshieldstartickettrashtriangle-downtriangle-uptwitteruseryahoo

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:

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.

Join or login to comment.

  • Ethan G.

    Hey everyone,

    I wasn't able to get a food sponsor for tonight. If you're the type of person who likes to eat dinner, you might want to do that before hand.

    I apologize for the late notice, and I'll make sure this is taken care of better for the next meetup!

    August 20, 2014

21 went

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy