On Tue, Apr 12, 2011 at 09:01:33AM -0500, Dale Schumacher wrote: Dear Dale,
> My implementation is what you called a "raw" PEG, and thus does not support > left recursion at all. OK - thanks for the information. > As your paper notes, in modifying PEGs to support left recursion "In > essence, the parser turns from (recursive) top-down in normal operation to > (iterative) bottom-up when left-recursion is detected." This mixed-model of > parsing strategy can lead to very confusing behavior. In your conclusion, > you pose the question, "are PEGs really suited to allowing left-recursion?" > > My answer to that question is "NO". There is probably a theoretical > argument to be made regarding the composability of PEGs, but I don't have > the academic inclination to pursue that angle. Rather, I appeal to the > inherent ability for non-experts to reason about the behavior of PEGs. The > deterministic nature of prioritized choice makes it much easier to look at > a PEG and understand how it will operate. Left recursion is _an error_ in > a PEG, much like infinite recursion in a function definition. This is definitely a reasonable position to take. The problem is then that PEGs without left recursion can be quite annoying to use. Certainly, some of the grammars I normally use are typically described in a left-recursive fashion, and rewriting them would destroy the link to the original; that's enough to prevent me adopting PEGs for many situations where I currently use an Earley parser. Of course, just because something's annoying doesn't mean that a good way to solve that annoyingness must exist - if life has taught me anything, it's that the universe doesn't always provide nice, neat answers :) Yours, Laurie -- http://tratt.net/laurie/ -- Personal http://fetegeo.org/ -- Free text geocoding http://convergepl.org/ -- The Converge programming language _______________________________________________ PEG mailing list [email protected] https://lists.csail.mit.edu/mailman/listinfo/peg
