> Problem is, your idea does NOT work for mutually left-recursive
> productions, only directly left-recursive productions.
>
Excellent catch. I had worried a bit about mutual recursion, but the
one test I tried worked. Interestingly, looking at the trace, there is
another reasonable point to pin the error on, which is:
enter Top @ 0 : ""
enter Choice @ 0 : ""
enter One @ 0 : ""
lookup Choice @ 0 : "" -> error
enter Base @ 0 : ""
exit Base @ 0 with match
lookup Base @ 0 : "base" -> match
exit One @ 0 with match
enter One @ 0 : "base"
lookup Choice @ 0 : "base" -> error
lookup Base @ 0 : "base" -> match
exit One @ 0 with match
lookup One @ 0 : "base" -> match
exit Choice @ 0 with match
enter Choice @ 0 : "base"
lookup One @ 0 : "base" -> match *****
exit Choice @ 0 with match
lookup Choice @ 0 : "base" -> match
exit Top @ 0 with error
The idea here is that the problem is could also be pinned on choice
using a memory that was formed during it's first time around, in it's
second time around. If for example, we were to clear the memory of
[EMAIL PROTECTED] before reentering choice, I think things would work out as
well.
> In other words, all productions that are mutually left-
> recursive need to share some state for the same input position, which
> complicates your scheme considerably.
This is very true. I'm noodling on a reasonable way to track things
to that cleans this up without adding too much additional complexity,
but it may turn out that the better strategy is just rule rewriting
ala the current Rats!.
It is still interesting that we may get some increase in expressivness
(at the cost of n^2 worst case of course). I realized that my earlier
example to parse "S = [ab] S [ab] | a" was slightly incorrect, the
better one is:
S = E / a;
E = E a [ab] \
E E [ab] \
[ab];
By the way, thanks to all for very useful feedback.
-Jeremy
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
