Hi all, Here is a description of an idea to handle left-recursion in PEGs.
https://github.com/orlandodarhill/peg-left-recursion Unfortunately, not all of the details are worked out. I'm not sure, when I might have time to finish it. Orlando. On Sat, Nov 13, 2010 at 2:06 PM, Repain Alex <alex.rep...@gmail.com> wrote: > 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
