What is packrat parsing?

Question

I know and use bison/yacc. But in parsing world, there's a lot of buzz around packrat parsing.

What is it? Is it worth studing?

Answer 1

I guess you'll know a lot more if you read the linked articles on this page and the Parsing expression grammar page on wikipedia.

Answer 2

Packrat parsing is a novel and practical method for implementing linear-time parsers for grammars defined in Top-Down Parsing Language (TDPL).

One of the top entries of a quick google search.

Answer 3

Pyparsing is a pure-Python parsing library that supports packrat parsing, so you can see how it is implemented. Pyparsing uses a memoizing technique to save previous parse attempts for a particular grammar expression at a particular location in the input text. If the grammar involves retrying that same expression at that location, it skips the expensive parsing logic and just returns the results or exception from the memoizing cache.

There is more info here at the FAQ page of the pyparsing wiki, which also includes links back to Bryan Ford's original thesis on packrat parsing.