Interesting, thanks.. It seems to me that a parser with an implementation similar to Warth etal can handle nested left recursions without any problems, but it prunes left-left recursion as found in Peter Goodman's example. The expansion follows:
A = A a / B -- definition = B a* -- A recursion = (B b / A / C) a* -- B rule = (A / C) b* a* -- B recursion = C b* a* -- A left-left recursion pruned = (C c / B / d) b* c* -- C rule = (C c / d) b* c* -- B left-left recursion pruned = d c* b* a* -- C recursion The expansion of ordered choice may not always be the same as traditional choice, but assuming that does not matter here, then the full expansion, as shown by David-Sarah (thanks), generates: A = d (c | b | a)* Peter.
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
