Packrat Parsing

Over the past few days, I’ve taken a couple of looks back at parser generators, with an eye toward (possibly) resuming work on DGrok, my project to write a parser for the Delphi language.

Along the way, I ran across a term I wasn’t familiar with: packrat parsing. It claims to be a way to get the simplicity of a recursive-descent parser, together with the flexibility of an LL or LR parser like yacc. It also claims unlimited lookahead in linear time (at the cost of higher memory requirements).

Don’t know yet how promising packrat parsing will be — I’ve only read the first page or so of the paper — but it should at least be an interesting read.

Leave a Reply

Your email address will not be published. Required fields are marked *