Re: Controlling the effects of precedence

[Hans Aberg]

At 00:48 +0200 2003/05/14, Frank Heckenbach wrote:
>> The traditional translated grammar is
>>     E -> E + T
>>     E -> T
>>     T -> T * F
>>     T -> F
>>     F -> I
>> It would perhaps be interesting to see how to extract this more compact
>> form as well.
>
>If you identify the equivalent symbols (E and E_11, E_12 and E_21,
>E_3 and E_22) and further substitute E_12 for `E_2 | E_3' in the E
>rule, you get:
>
>     E_1 -> E + E_12
>     E_2 -> E_12 * E_3
>     E_3 -> I
>     E -> E_1 | E_12
>     E_12 -> E_2 | E_3
>
>Now substitute E_1 into the E rule (where it's used exclusively),
>likewise E_2 into the E_12 rule
>
>     E -> E + E_12 | E_12
>     E_12 -> E_12 * E_3 | E_3
>     E_3 -> I
>
>And the result is just the traditional grammar (up to symbol
>renamings).

Good. Then I do not have to do it, at least on example level. :-)

>I'm not sure if every precedences can be expressed as a series of
>limitations on the parse tree -- at least bison defines them as
>relations between rules and look-ahead tokens -- but if you can do
>this, this method should work.

One has to go through the proof how the precedences are implemented. This
is how I eventually arrived at de description with the parse tree
limitations.

Here is a segment from the book by Dick Grune, "Modern Compiler Design":

=========================================================================
Another useful technique for resolving shift-reduce conflicts is the
use of precedences between tokens.  The word \*`precedence\*' is used here in
the traditional sense, in which, for example, the multiplication sign has a
higher precedence than the plus sign; the notion may be extended to other
tokens as well in parsers.
This method can be applied only if the reduce item in the conflict ends in a
token followed by at most one non-terminal, but many do.  In that case we have
the following situation which has a shift-reduce conflict on $t$:

$ P -> alpha dot t beta [[ ... ]] $     (the shift item)
$ Q -> gamma u R dot [[ ... t ... ]] $  (the reduce item)

where $R$ is either empty or one non-terminal.  Now, if the look-ahead is $t$,
we perform one of the following three actions:

1.
if symbol $u$ has a higher precedence than symbol $t$, we reduce;
this yields a node $Q$ containing $u$ and leaves $t$
outside of it to the right;

2.
if $t$ has a higher precedence than $u$, we shift;
this continues with the node for $P$ which will contain $t$
when recognized eventually, and leaves $u$ out of it
to the left;

3.
if both have equal precedence, we also shift (but see
Exercise {#Associativity}).

This method requires that the user of the parser generator supply
precedence information.
It allows considerable control over the resolution of shift-reduce
conflicts.
=====================================================================

One then has to work this definition backwards: A "reduce" means that the
reduce item is permitted in the derivation and a "shift" means that it is
prohibited. These are two possible derivations of yet another rule which is
not written out in the quote above, but which will appear in any
derivation. So if introducing that, that is roughly the way to arrive at
the picture I described.

  Hans Aberg