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.
Orlando.
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
