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 <a3m...@uwaterloo.ca> 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
> PEG@lists.csail.mit.edu <mailto:PEG@lists.csail.mit.edu>
> https://lists.csail.mit.edu/mailman/listinfo/peg 
> <https://lists.csail.mit.edu/mailman/listinfo/peg>
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

Reply via email to