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’



Aaron Moss


PEG mailing list

Reply via email to