Hi Laurie, My implementation is what you called a "raw" PEG, and thus does not support left recursion at all.
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. Let me reason by analogy. In the evaluation of recursive functions, using eager/strict evaluations (applicative-order reduction) may result in non-termination where lazy/non-strict (normal-order reduction) would terminate. This would argue for always using normal-order reduction. However, we can reason much more easily about the space/time characteristics of applicative-order reduction, and that's what most programming languages implement. CFGs are like normal-order reduction, and PEGs are like applicative-order reduction. In order to use them safely, we must understand, and avoid, the dangerous cases like left recursion. The result is a tool which is easier to understand and use correctly. Take care, Dale On Tue, Apr 12, 2011 at 3:05 AM, Laurence Tratt <[email protected]> wrote: > On Mon, Apr 11, 2011 at 08:43:54AM -0500, Dale Schumacher wrote: > > Dear Dale, > >> Parsing Expression Grammars, part 3 (http://bit.ly/h9HoW1) extends the >> parser toolkit to support pipelines of tree-transforming parsers, >> bringing our capabilities to the level of OMeta [1]. >> >> [1] A. Warth and I. Piumarta. OMeta: an Object-Oriented Language for >> Pattern Matching. TR?2007?003, >> http://www.vpri.org/pdf/tr2007003_ometa.pdf, Viewpoints Research >> Institute, 2007. > > Out of (selfish) curiosity, does your parser implement Warth et al.'s left > recursive algorithm which is in OMeta these days? If so, does it suffer from > the same problem I noted in Section 5 of this paper: > > http://tratt.net/laurie/research/publications/html/tratt__direct_left_recursive_parsing_expression_grammars/ > > I looked at your description, but wasn't easily able to work this out one > way or the other. I'm asking partly because it would be interesting to see > if it's a fundamental problem with Warth et al.'s algorithm, or whether it > is implementation dependant. > > I should note, as I usually do, that not everyone thinks the problem I noted > is a problem (Alex doesn't, and I respect his reasons for doing so). > > 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 > _______________________________________________ PEG mailing list [email protected] https://lists.csail.mit.edu/mailman/listinfo/peg
