Hi Peter: Thats looks as good as anything... consistent and thorough...
But I'm not sure I want to do all that... The LR implementation I am using does the simple cases and copes with indirection to be able to handle the classic numerical expression style LR rules... (which needs indirection) but anything more than that I think I prefer it to fail, it just gets beyond my intuition. Back to basics: a grammar is a neat succinct formal specification: but if you have to scratch your head to figure out what it actually says then it becomes less useful... Mixed LR/RR makes me feel like I need a cold towel around my head.... The big value of PEG is the ability to write a neat formal grammar specification that can also be directly executed as a top down parser... then we get sucked into LR because that is the tradition... hum... Ah, Roman seems to be saying exactly the same thing... good, I keep thinking maybe I'm just being too slow... Hi Roman, I should send your note a response, but the brief version is that I have been having the same thoughts, and I agree with you... In summary, I admire the maths, and its probably a superior solution, but its getting beyond me. On the practical engineering front I would love lots of people to use grammars instead of Regular expressions... but for that to happen we probably need a small fast portable engine that can be implemented in lots of different programming languages... if its too big, slow, or complex, then the objective will be lost... So lots of food for thought for me...... Cheers, Peter. On Sat, Jan 8, 2011 at 9:56 AM, Peter Goodman <peter.good...@gmail.com>wrote: > 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
