I do not understand why the test grammar offered by Sylvain should not
recognize aaaaa (a^5).
A <- a A a / a
Here's my thinking:
a a a a a input
A 0. start symbol
a A a 1. try first choice
^
a(a A a)a 2. try first choice
^
a(a(a A a)a)a 3. try first choice
^
a(a(a(a A a)a)a)a 4. try first choice
^
a(a(a(a(a A a)a)a)a)a 5. try first choice
^
a(a(a(a(a(a A a)a)a)a)a)a 6. try first choice: fail
^
a(a(a(a(a(a)a)a)a)a)a 7. try second choice: fail
^
a(a(a(a(a)a)a)a)a 8. back up to choice in #5 and try second choice
^
a(a(a(a(a)a)a)a)a 9. turns out our choice in #4 was wrong
^
a(a(a(a)a)a)a 10. back up to choice in #4 and try second choice
^
a(a(a(a)a)a)a 11.
^
a(a(a(a)a)a)a 12. Looks like our choice in #3 was wrong
^
a(a(a)a)a 13. back up to choice #3 and try second choice
^
a(a(a)a)a 14.
^
a(a(a)a)a 15. End of parse: success
^
Please advise. Thank-you.
Cheers,
David
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Sylvain Schmitz
Sent: Monday, October 08, 2007 02:50
To: Lowell Thomas
Cc: peg@lists.csail.mit.edu
Subject: [PEG] A first test for PEG equivalence (was Equivalence of PEG and
APG 5.0)
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
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
