Hi Ulrik

Thank you, good to know.

I had missed that PEL formulation (very neat now that you point it out).

Cheers,
Peter.


> On Oct 14, 2016, at 3:08 AM, Ulrik Rasmussen <ul...@utr.dk> wrote:
> 
> 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.
> 
> 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


_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg

Reply via email to