Jeremy,
So, I just hacked up your suggestion in Rats! --- thankfully, almost
all the necessary code was already written, so it was easy.
Problem is, your idea does NOT work for mutually left-recursive
productions, only directly left-recursive productions.
To illustrate, here's my example input grammar:
module xtc.parser.Foo;
option main(Top), verbose;
public Node Top = Choice !_ ;
generic Choice = One / Two ;
generic One = Choice "one" / Base ;
generic Two = Choice "two" / Base ;
String Base = "base" ;
And here is the execution trace on input "baseonetwo", indented for
readability:
enter Top @ 0 : ""
enter Choice @ 0 : ""
enter One @ 0 : ""
lookup Choice @ 0 : "" -> error
enter Base @ 0 : ""
exit Base @ 0 with match
lookup Base @ 0 : "base" -> match
exit One @ 0 with match
enter One @ 0 : "base"
lookup Choice @ 0 : "base" -> error *****
lookup Base @ 0 : "base" -> match
exit One @ 0 with match
lookup One @ 0 : "base" -> match
exit Choice @ 0 with match
enter Choice @ 0 : "base"
lookup One @ 0 : "base" -> match
exit Choice @ 0 with match
lookup Choice @ 0 : "base" -> match
exit Top @ 0 with error
bar:1:0: top expected
The problem occurs in the line marked with *****. At this point, the
Choice production should produce a match on the One production
matching the Base production. However, the memoized result is the
error marker from the first iteration of your do/while loop. Hence,
there's only a look-up, which fails. Everything afterwards doesn't
really matter anymore.
Now, if Choice would simply ignore the memoized result and try again,
it would pull up the match from One and the parser would progress
correctly. In other words, all productions that are mutually left-
recursive need to share some state for the same input position, which
complicates your scheme considerably.
Robert
On Sep 3, 2007, at 2:45 PM, Jeremy Bruestle wrote:
I'm missing something: the first iteration forces a base case, in my
example no characters with null as the semantic value. With Bryan's
condition, that's it; no more recursion. But my point is that I need
to try the recursive case now.
Robert
Actually, my bad again, the return should be "return prev", but given
that, the logic is as follows:
On the first entry into the loop body, cur = -1
Now:
memory[key] = cur; // Memorized version is now -1, no match
prev = cur; // Prev is also -1
cur = do_pase(rule, position);
The do_parse calls the actual matcher, none of the recursive calls
work (since memorized version is currently -1), but the null match
does work, resulting in a return of 0 (since null match has length 0).
Now, cur = 0, prev = -1, thus cur != -1 && cur > prev thus we go
around the loop again.
Now:
memory[key] = cur; // Memorized version is null match
prev = cur; // Prev is now 0
cur = do_pase(rule, position);
This time, the recursive calls work (the memorized version is the
empty match), and since all of your cases do actually match real
values the new match that results is cur > 0, thus once again cur !=
-1 && cur > prev, and so on. When at some point there is no
additional left recursive matches, so we fall though to the lowest
rule, the null rule, which of course matches (since it always does).
At this point, we return cur = 0 again, which will fail the loop
condition, exiting, and the return to the original caller will the the
*previous* match, which was the longest recursive match.
I checked the 'only null' case and the 'non-recursive' case and they
seem to work fine as well.
I think that's all correct now.
-Jeremy
_______________________________________________
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
