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