On Tue, Sep 8, 2015 at 5:43 PM, Nikita Nemkin <nik...@nemkin.ru> wrote:
> Hi Sérgio,
>
> thanks for your answer (and your awesome paper).
> The idea and the goal of precedence checks is very clear. I'm just
> missing one detail.
>
> I'm trying to make the grammar "E = E + E / n" left-associative without
> extra annotations, i.e. by defaulting ALL precedences to 1.
> Is this even possible with alternative "left biased" versions of
lvar.4/lvar.5 ?
>
> Following the example grammar on input "n+n":
>
> 1. top level E is entered, it seeds recursion memo table
> L = {(E, "n+n") -> fail}
> 2. top level E executes it's body, the left E fails and we only get n
> as a result.
> 3. top level E memoizes the resulting n with the default precedence 1:
> L = {(E, "n+n") -> ("+n",E[n], 1)}
> 4. HERE is the issue: top level E tries to grow the recursion bound,
> it executes it's body again, but the left E fails precedence check!
> All precedences are 1 and modified lvar.5 applies (k <= k')
> The bound doesn't grow and we're ruined before we even get to
> right recursive part.
Hi, Nikita.
I think you are right, the change in rules lvar.4 and lvar.5 suggested in
the paper is wrong, it seems to give a parser that always fails when trying
to increase the bound of a left-recursive rule. I am sorry about that. I
think
we thought the change was so simple that we did not implement/try it.
> It could work, if top level E started with a lower precision, like 0.
> But then, in a real
> multi-rule grammar it would mean manual precedence assignment...
>
> If left associativity is impossible without extra annotations (or
> tricky backstage
> precedence assignment algorithms), I'd rather make all precedences
explicit.
> The mechanism itself is fully general and really powerful.
If you always want left associativity, one way to achieve this is to
use a map M, where the keys are variables, and the associated value
is a suffix of the input or an index of the input.
The idea is to save in this map the input position X where you first used
variable V. You should keep this information in the map while tyring to
increase the bound of V. This should be done in rules lvar.1 and lvar.2
Given a variable V, to apply rule "lvar.4" in position Y you should see if Y
is not greater than map[V] (actually I think you only need to check
whether map[V] == Y). When Y is greather than map[V], this means
that you are trying to apply a right-recursive incarnation of V.
You should use L as it was used before the introduction of precedence
levels.
I am sending attached a draft of this new semantics.
I have tested it :-)
If you also want precedence levels, I think you should adapt rules
lvar.5 and lvar.4, so rule lvar.4 would be applied only when the condition
related to L and the condition related to M are satisfied. The condition
related to L is the same that appears on p.15 (Figure 3).
I hope this works well for you.
Sérgio
P.S.: I am sending this mail to the PEG list too.
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
