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
