Hi
Yes, I seem to remember that Bryan Ford pointed out the “middle finder” grammar.
It is CF but not PEG:
s = x s x / x
i.e an odd number of x’s. There is a similar one for an even number.
I was interested to discover that this can be done with an extended PEG grammar.
Cheers,
Peter.
> On Oct 13, 2016, at 7:43 PM, Aaron Moss <[email protected]> wrote:
>
> 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
> [email protected] <mailto:[email protected]>
> https://lists.csail.mit.edu/mailman/listinfo/peg
> <https://lists.csail.mit.edu/mailman/listinfo/peg>
_______________________________________________
PEG mailing list
[email protected]
https://lists.csail.mit.edu/mailman/listinfo/peg
