Hi Lowell,
Lowell Thomas wrote:
I am about to release version 5.0, and in
that release I am claiming that APG 5.0 parsers and PEG recognize the same
set of languages. This result, if true, is surprising to me, since APG
starts with a context-free grammar formalism and PEG makes a point of not.
The argument is heuristic, not mathematical, but the result looks almost
obvious on the face of it.
Equivalences of PEGs with other formalisms haven't been much discussed
on the list. Overall, backtracking top-down parsing methods with strict
priorities and greediness are good candidates---the TDPL formalism, upon
which PEGs were constructed, was defined in order to study such parsers
after all.
A good first test to check whether (a rather strong) equivalence might
hold would be to verify that the grammar corresponding to the PEG
A <- a A a / a
recognizes the same language as the PEG, namely {a^(2^n - 1) | n > 0}
(i.e. 2^n-1 consecutive `a' symbols, starting with 1, 3, 7, 15, etc.).
This example of a non context-free language seems to me like a good
start---if your parser recognizes any odd number of `a' tokens instead,
then it's not a PEG parser.
--
Hope that helps,
Sylvain
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
