October 14 2016 4:15 AM, "Peter Cashin" <cashin.pe...@gmail.com> wrote:
> 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.

## Advertising

That is also a PEL (parsing expression language, i.e. recognizable by a PEG),
you just have to rewrite it:
<S> = xx <S> / x
There is, as far as I know, no known examples of a CFL which cannot be
described by a PEG. The argument for "CF not-less-than PEG" instead relies on a
complexity result due to Lee[1] which says that a linear-time CFG parser would
imply the existence of an efficient O(m^2.333333...) algorithm for boolean
matrix multiplication. To the best of my knowledge, there is no proof that such
an algorithm cannot exist, but none has been found despite a mountain of work
on the subject.
So, the question "CF < PEG?" is currently open: neither a formal proof nor a
counter-example has been found.
[1] https://arxiv.org/abs/cs/0112018
Regards,
Ulrik Rasmussen
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg