What is packrat parsing?
algorithm, packrat-parsing, parsing
Solution
Packrat parsing is a way of providing asymptotically better performance for parsing expression grammars (PEGs); specifically for PEGs, linear time parsing can be guaranteed.
Essentially, Packrat parsing just means caching whether sub-expressions match at the current position in the string when they are tested -- this means that if the current attempt to fit the string into an expression fails then attempts to fit other possible expressions can benefit from the known pass/fail of subexpressions at the points in the string where they have already been tested.
Problem
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?