I've settled on a strategy that tries to expand out as much left recursion as possible, from left to right.
Some example parse trees: S -> SS / a with "aaaa" gives S(S(S(S(a), S(a)), S(a)), S(a)) S -> ST / a T -> S with "aaaa" gives S(S(S(S(a), T(S(a))), T(S(a))), T(S(a))) S -> S S T / S c / a / b T -> d with "abcd" gives S(S(a), S(S(b), c), T(d)) with "abcdabcdd gives S(S(S(a), S(S(b), c), T(d)), S(S(a), S(S(b), c), T(d)), T(d)) It goes left-to-right in the sense that it will try to expand the first left recursion it encounters. Once it can't keep going with that, it will try to expand out any other left-recursive invocations of the same variable later in the string, regardless of if they appear in the same production as the left recursive invocation. If one needs a right leaning tree with left recursion then now (with my system) it is no longer possible, i.e. left lean for left recursion is forced. A very high level description of my algorithm is that I group the parser stack into chunks representing continuations. When I detect left recursion, I copy of chunk of the top-most continuation on the stack, store it in the memo table, and then advance the topmost parser frame to the next production. When parsing of a variable is completed, all continuations stored in that variable's memo entry at that position are attempted in the order with which they were added into the memo table. Updating the results of a memo table entry (i.e. successfully parsing something) resets the memo entry's next continuation pointer to the first continuation added to the memo entry. The big trick is that if we are in the continuation of a variable (i.e. the size of the continuation stack > 1) and we detect a left recursive invocation of the same variable then instead of adding it to the memo entry for the variable at the current string position, we add it to the memo entry of the start of the current continuation's string position. Best Regards, Peter Goodman, http://ioreader.com 70 Winston Circle, Montreal, Quebec H9S 4X6 On Thu, Jan 6, 2011 at 4:21 PM, Peter Cashin <cashin.pe...@gmail.com> wrote: > Hi Peter & Alex: > Ah! Sorry Peter I didn't quite follow you at first... > Thanks to Alex I now think you have suggested a good solution. > So for my little balanced example it is "left first": > sum = sum '+' sum | int <=> sum = sum '+' int | int > "Left first" is also a "left to right" interpretation, so it has a good > rationale. > Thanks, > Peter. _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
