Thank-you. My analysis went wrong at step #12. In step #12, I determined that the choice I made in step #3 was wrong. However, in step #11, I had determined that #3 was correct. Step #12 (which is a continuation of the decision in #2) can't go back and tell #3 to try a different choice because #3 will always choose "aAa" over just plain "a". Step #2 has the choice of "aAa" or "a", but it can't choose "aAa" on the condition that the next parse of "A" choose the second choice over the first.
Thanks for the help. Cheers, David -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Christophe Grand Sent: Monday, October 15, 2007 14:15 Cc: peg@lists.csail.mit.edu Subject: Re: [PEG] A first test for PEG equivalence (was Equivalence of PEGand APG 5.0) 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 _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
