Hi,
As we are talking about left recursion, I would like to say that
I updated my paper about left recursion in arXiv:
http://arxiv.org/abs/1207.0443
The previous version of the paper shows a conservative
extension of PEGs that handles direct and indirect left recursion.
This extended version discusses how to deal with
precedences and how to compile a left-recursive PEG to a
program in a low level parsing machine.
Sérgio
On Tue, Aug 13, 2013 at 6:56 AM, Matthew Goode <matt...@scratchy.org.nz>wrote:
> Hello
>
> Thanks for the input! (And to Alex too).
>
> There is much that I want to add to this project, but first I need to work
> on a few others (the one called Skeleton in particular, which is a code
> generator for creating code generators...)
>
> I'm not sure the problem with the option grouping - it's not a feature
> many people would need, but it serves a purpose that makes sense to me. I
> have to apologize for saying the algorithm uses rule rewriting - this is
> perhaps not a good way of explaining the process (it doesn't really rewrite
> anything). I will try and have an informal writeup of the method in a week
> or two and a more formal one later. I think there is a very nice proof of
> the method's robustness (though I may be wrong - gut feeling is it should
> be all good).
>
> The basic left-recursion handling is similar to the approaches I've seen
> described before.
>
> thanks again,
> Matthew
>
>
> On 13/08/13 11:50, Orlando Hill wrote:
>
> Looks great, Matthew!
>
> I would encourage you to keep refining things. Option grouping shouldn't
> be needed for specifying precedence levels, and the difference in generated
> code when using a multi-option pattern is going to confuse users.
>
> You mention "rewriting the pattern resolution on the right", so I
> imagine the way you're handling left-recursion is similar to the method I
> suggested back in 2007. I've already failed twice to describe that method
> on this mailing list, so I guess I'll have to get help in turning it into a
> published work that people will actually believe.
>
> Anyway, keep up the good work,
> Orlando
>
>
> On Mon, Aug 12, 2013 at 5:28 PM, Matthew Goode <matt...@scratchy.org.nz>wrote:
>
>> Hello, I'm pretty much ready to release a parser generator I've been
>> working on for a while. It is a packrat inspired parser (though can avoid
>> memorising), that handles left recursion indirectly and directly, and takes
>> into account option order with left recursion. So, the following
>>
>> e = { e "+" e } | {e "*" e } | NUMBER
>>
>> will parse "1+2*3+4" as (1+((2*3)+4) (if specified correctly - see
>> documentation). This seems to work okay with indirect recursion as well,
>> and with or without memorisation. It does use a tokenisation step, because
>> I liked that better, but that may change in future versions. It also has
>> extensions to PEG that allow it to match things like Fibonacci sequences...
>>
>> It can be found at http://scratchy.org.nz/austen.php
>>
>> (It is still a work in a progress, but for the most part is a well
>> matured tool - I've been working on and using it for years).
>>
>> Matthew
>>
>>
>> _______________________________________________
>> 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
>
>
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
