Orlando:
Ah yes, that is just sublime.
So, the new definition:- a Deterministic grammar/parse has only one
match (or fails) to the right of any given start position, or to the
left of its end position.
And yes, it remains linear speed.
Very good, thank you,
Peter.
On 05/09/2007, at 10:46 PM, Orlando Hill 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.
Orlando.
_______________________________________________
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
