Re: PEG conventions for left-recursion ?
2010-11-13 13:06:49 GMT
I've found some PEG-list archive about your algorithm suggestion
(here => http://www.mail-archive.com/peg <at> 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.
A few others have pointed out flaws in Warth's algorithm.
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.
On Fri, Nov 12, 2010 at 6:33 PM, Repain Alex <alex.repain <at> 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  (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.
> 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).
>  Packrat Parsers Can Support Left Recursion, Alessandro Warth, James R.
> Douglass, and Todd Millstein (2008)
> PEG mailing list
> PEG <at> lists.csail.mit.edu
_______________________________________________ PEG mailing list PEG <at> lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg