You must not forget that each rule is a function depending _only_ of the
current position (for a given input string).
We can write a result matrix. First, the easy cells:
a a a a a $
a 1 1 1 1 1 X
aAa X
A X
Then you can fill the other cells using a spreadsheet-like formulas:
- A(n) := if aAa(n) != X then aAa(n) else a(n)
- aAa(n) := if a(n) != X and A(n + a(n)) != X and a(n + 1 + A(n + 1)) !=
X then A(n + 1) + 2 else X
(given that if a(n) != X then a(n) = 1, it can be simplified to:
- aAa(n) := if a(n) != X and A(n + 1) != X and a(n + A(n + 1)) != X then
a(n) + A(n + a(n)) + a(n + A(n + a(n))) else X)
(n is the position in the input string)
Now we can fill the matrix:
a a a a a $
a 1 1 1 1 1 X
aAa 3 X 3 X X X
A 3 1 3 1 1 X
Hence with the input a^5 only a^3 is matched.
On a longer matrix:
a a a a a a a $
a 1 1 1 1 1 1 1 X
aAa 7 5 3 X 3 X X X
A 7 5 3 1 3 1 1 X
a^7 is totally matched.
Christophe Grand
David Mercer a écrit :
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.
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
