We know this:
* LL < PEG < LR < CF (yes?_
This isn’t strictly true; the lookahead capabilities of PEGs allow some
languages that are not context free to be matched (for instance, a^n b^n c^n,
using the grammar below). Conversely, there is a conjecture (to my knowledge as
yet unproven) that there exist some context free languages for which no PEG can
be devised (given that packrat parsing can match any PEG in linear time, but
there is no known linear-time algorithm for general-purpose CFG parsing).
a^n b^n c^n grammar:
S := &(A ‘c’) ‘a’+ B !.
A := ‘a’ A? ‘b’
B := ‘b’ B? ‘c’
PEG mailing list