Hi Juancarlo,
PEG is not contained in CFG. Consider the language { a^n b^n c^n | n >= 0
}. It is recognized by the PEG:
S <- &A a* B !.
A <- (a A b)?
B <- (b B c)?
So, clearly PEG is stronger than LL or LR, and PEG includes some languages
outside of CFG.
It is technically unknown whether PEGs include all CFGs. However, it is
unlikely, and certainly we don't know how to convert an arbitrary
context-free grammar into a parsing expression grammar. To do so would be a
great discovery!
Why? If you can parse CFGs in linear time, then you can multiply nxn binary
matrices in (nearly) n^2 time. The current best algorithm runs in n^2.373
time. On the other hand, PEGs are parseable in linear time.
In other words: there isn't a way to convert an arbitrary CFG into a PEG,
that we know of, and it is unlikely to be found by chance.
All the best,
Francisco Mota
On Mon, Jun 17, 2013 at 10:40 PM, Juancarlo Añez <[email protected]> wrote:
>
> A question that often arises in Web circles like Slashdot is what is the
> relation of PEG languages to other well known sets like LL, LR, or even CFG
> (and there's LSTAR and ALLSTAR).
>
> I think that a PEG grammar is not a CFG grammar in the strict sense
> because of PEG's rule/production ordering.
>
> My question is about the set of languages that can be parsed.
>
> Intuition tells me that the L(PEG) is larger than LL and LR, but I haven't
> found a proof for it.
>
> Cheers,
>
>
> --
> Juancarlo *Añez*
>
> _______________________________________________
> PEG mailing list
> [email protected]
> https://lists.csail.mit.edu/mailman/listinfo/peg
>
>
_______________________________________________
PEG mailing list
[email protected]
https://lists.csail.mit.edu/mailman/listinfo/peg
