Hi everyone, Here's another way to achieve left-recursion/associativity/precedence handling with PEGs, to appear in SLE 2015: https://drive.google.com/file/d/0B0O9lcl5dMLQSzJqUWFzbzl2X0U/view?usp=sharing
Algorithm 1 & 2 is what you're looking for. It's adapted from a technique developed here: http://chrisseaton.com/katahdin/ And the implementation: https://github.com/norswap/autumn I was going to wait until I had a nice user manual before making an announcement, but since the topic came up, this is a good a time as any :) Nicolas LAURENT On Tue, Sep 8, 2015 at 4:06 PM, Sérgio Medeiros <sqmedei...@gmail.com> wrote: > On Mon, Sep 7, 2015 at 6:27 PM, Nikita Nemkin <nik...@nemkin.ru> wrote: > > I wonder if someone could help me with a certain assertion made in this > > paper: http://arxiv.org/abs/1207.0443v3 (Medeiros, Mascarenhas, > > Ierusalimschy. "Left Recursion in Parsing Expression Grammars" v3). > > > > The last paragraph on p.14: > > > > > We could impose left-associativity as the default in case of a grammar > that > > > mixes left and right recursion just by changing k ≥ k' in rule lvar.4 > to k > k' > > > and by changing k < k' in rule lvar.5 to k ≤ k'. The disadvantage is > that this > > > makes specifying precedence levels with right-associative operators a > little > > > harder > > > > I can't see how it's supposed to work. Consider this grammar: > > > > E = E[1] "+" E[1] / "n" > > > > where [1] is precedence and the initial precedence is also 1. > > > > Default precedence check is "fail if current rule precedence <= memoized > > precedence," leading to right associative parse tree, as expected. > > > > Modified precedence check is "fail if current rule precedence < memoized > > precedence" and it does NOT lead to left associativity. Instead, > recursive > > E[1] invocation always fails due to precedence check, reducing the > grammar > > to E = "n" "+" "n" / "n". > > It seems that when you say "precedence check" you are referring to rule > lvar.5. I think the default precedence check (rule lvar.5 on page 15) is > "fail if current rule precedence < memoized precedence". > > I think the key point is that all left-recursive invocations of E (unless > the first one) > will occur after a right-recursive invocation of E. When this > left-recursive invocation > of E after a right-recursive one matches as much as possible we will have a > a right-associative '+'. The result would be E[E[n] + E[E[n] + E[n]]] > > The default semantics allows this, because rule lvar.4 can be used as long > as both > E's have the same precedence. > > By chaning rule lvar.4 as suggested the left-recursive E after a right > recursive E > only matches "n", which gives us a left-associative '+'. The result would > be E[E[E[n] + E[n]] + E[n]]. > > I hope this helps. > > Sérgio > > > > > _______________________________________________ > 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
