On 9/5/07, Orlando Hill <[EMAIL PROTECTED]> wrote: > Peter Cashin wrote: > > One nagging worry: my working definition of a deterministic > > grammar/parse is that there can only be one match for any rule from > > any given position... which fits with PEG and pack-rat memos.. but > > left recursion breaks this definition... Any suggestions? > No, left recursion doesn't break it but I can see how you might think that. > > Here's an example. > > E <- E '+' V > / V > V <- 'a' > > E is left recursive so we break it into left and non-left parts. > > E <- E_nonleft E_left* # This is the looping part > > E_nonleft <- V > > E_left <- left_hand_side '+' V # left_hand_side given as argument > > Obviously, E and E_nonleft can only give one match per position. > > What I might have glossed over is that, the results of E_left are being > memoized at the position they were evaluated at. This is different to > how Jeremy was doing it which was to memoize everything at the position > of the original E. > > So, each of E, E_nonleft and E_left will only be evaluated a maximum of > n times and will always give the same result. It's an implementation > detail as to whether you think of E_left as joining its left hand side > with its other results or whether that is done by E or whatever > indirectly recursive part may have called it. >
Ah, after that description, I was able to more fully follow your original discussion. In addition, I realized that the algorithm I mentioned last night (posting on mailing lists too late I guess) has a number of problems. At any rate, I'm convinced now that rewriting is the way to go, and I see how it can be done in a way that makes sense for mutual recursion. -Jeremy _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
