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’ Regards, Aaron Moss
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
