(Apologies for duplicates, I accidentally replied to you instead of the
list)
On 2017-05-14 05:08, Juancarlo Añez wrote:
I seem to recall that it is proven that there are PEG grammars that
have no CFG
equivalent (to be verified), so the proposition would be PEG+LEFT > CFG.
I haven't seen that mentioned in the papers I've read.
There is an example of such a grammar in [1, p. 471]. It is defined
using the GTDPL formalism which is equivalent in expressive power to PEG.
Basically, they give a grammar which recognizes the non-CFL 0^n 1^n 2^n
for any n >= 1.
From a high level:
1. Use lookahead to check that input has prefix
0^n 1^n 2 for some n >= 1
2. Consume all 0 symbols
3. Consume remainder of the form 1^m 2^m for some m >= 1
Since the middle string of 1's is matched in its entirety by (1) and
(2), we must have m = n.
I haven't tested it, but the following PEG should do the trick:
S <- &Prefix '0'* Suffix
Prefix <- '0' Prefix '1' / '2'
Suffix <- '1' Suffix '2' / eps
Cheers,
Ulrik
[1] Aho and Ullman, "The Theory of Parsing, Translation and Compiling",
1972
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
