Packrat Parsing

A packrat parser provides the power and flexibility of top-down parsing with backtracking and unlimited lookahead, but nevertheless guarantees linear parse time. Any language defined by an LL(k) or LR(k) grammar can be recognized by a packrat parser, in addition to many languages that conventional linear-time algorithms do not support.

Packrat Parsing: Simple, Powerful, Lazy, Linear Time

Posted April 19, 2006 9:48 AM