Comment by fanf2

It is important to distinguish between PEG and packrat.

PEG is a model for recognizers, distinct from traditional grammers whose theoretical model is usually based on generating strings rather than recognising them. (Yes this is a bit backwards.) The most distinctive feature of PEGs is the ordered choice operator - traditional context-free grammars and regexes use unordered choice, but ordered choice is a closer model of how recursive descent parsers work in practice. Ordered choice naturally leads to implementations that have less backtracking than common regex matchers, e.g. Lpeg.

Packrat parsers are based on a clever non-backtracking PEG matching algorithm. They spend O(n) memory to get O(n) parsing time, so they are reliably fast but not good for long inputs. They are also effective in a pure, lazy setting like Haskell.

Lpeg is a PEG parser but not a packrat parser.