Hi Orlando, I've found some PEG-list archive about your algorithm suggestion (here => http://www.mail-archive.com/peg@lists.csail.mit.edu/msg00096.html). Do you have a more proper document about it ? I would be interested in seeing your solution and what is the gap with Wrath et al.'s work.
2010/11/12 Orlando Hill <orlandodarh...@gmail.com> > A few others have pointed out flaws in Warth's algorithm. > > http://tratt.net/laurie/research/publications/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf > Yes, I had a talk with Laurence Tratt recently, only to find my algorithm had also some associativity problems. He tackled a different problem from mine, and I have a real interest in his work. > > Maybe, it's no better but, I still have a feeling the algorithm I > hand-wavingly suggested, three years ago, actually works. It really > seemed like it handled indirect left-recursion, allowed > left-associative trees and maintained a linear runtime. In hindsight, > I could have got help in trying to formalize and publish it. > > Anyway, I'm interested to hear what progress you've made. > > Orlando. > > On Fri, Nov 12, 2010 at 6:33 PM, Repain Alex <alex.rep...@gmail.com> > wrote: > > Hi PEG list, > > > > As an intern, I worked this summer in a japanese laboratory, on > > left-recursion support for packrat parsers. One of the questions we had a > > hard time dealing with was the following : > > > > Since the original definition of PEG grammars doesn't take in account the > > grammars with left-recursive rules (directly or indirectly), what is the > > behaviour we expect from a PEG parser, when dealing with those grammars ? > > > > The first and intuitive solution is to avoid these rules, but a lot of > work > > has been produced on the subject, including Wrath et al.'s paper [1] > (which > > might be the most acknowledged), and today it seems we want to be able to > > handle left-recursive grammars. But this can reveal itself quite tricky. > > Take for instance the following grammar : > > > > S <- A | B > > A <- S a | a > > B <- S b | b > > > > which is an indirectly left-recursive grammar. In a CFG context, this > > grammar would represent the langage (a|b)+ . What about this in the PEG > > context ? > > > > My guess is that, despites the fact that PEGs impose the concept of > ordered > > choice, the expected behaviour of this grammar is to recognize the very > same > > (a|b)+ langage, through a PEG parser - say for instance a packrat parser. > > Still, I would like to be sure of it, and if anybody has a CLEAR idea of > > what SHOULD happen with a correct support for left-recursion, I'm eager > to > > hear about it. Is there only a real convention for a correct behaviour ? > > > > My actual situation is the following : during my internship this summer, > I > > started to doubt about the capacity for Wrath et al.'s algorithm to > handle > > every type of left-recursive grammars. For instance, the above grammar, > when > > passed to a Packrat parser with Wrath et al.'s enhancement, doesn't > > recognize (a|b)+, but only a subset of this langage. That is not the > > behaviour I expected, and thus I started working on a new algorithm able > to > > take into account complex left-recursion cases. Yet, if my vision of how > a > > parser behaves "correctly" is altered in some way, my work here could be > > just good for the trash bin. > > > > Thanks for your help. > > Alex > > > > P.S. : if someone is interested in my work, or in examples of strange > > behaviour with Wrath et al.'s, I can provide them, one-to-one (to avoid > > attached files on the mailing lists). > > > > [1] Packrat Parsers Can Support Left Recursion, Alessandro Warth, James > R. > > Douglass, and Todd Millstein (2008) > > > > > > _______________________________________________ > > 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
