Re: POSIX and reduce/reduce conflicts

[Hans Aberg]

At 23:24 +0200 2002/04/08, Akim Demaille wrote:
>Paul> Also, when there is a reduce/reduce conflict, yacc must reduce
>Paul> by the grammar rule that occurs earliest in the input.
>
>So using the highest priority is a POSIX violation.  I guess it is
>time for POSIXLY_CORRECT_HARDER :)

If you mean token priority, that method is only used to resolve
reduce/shift conflicts; see for example the book by Dick Grune et. al.,
"Modern Compiler Design book", an excerpt:

=========================================================================
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.

(End-of-quote.)

This method then depends on the parsing algorithm, at least in the sense
that it has not been proven to be independent. On the question whether on
can do this purely from the language point of view, a reply in
comp.compilers gave:

>> To a grammar/precedence pair (G, P), find a definition language
>> L(G, P).  (Thus, independent of parsing algorithms.)
>
>Eelco Visser does something like this in his paper "Scannerless
>Generalized-LR Parsing" (section 4.1 "Disambiguation by Priorities"). He
>also has references to similar work (section 10 "Other Work", second-last
>paragraph).
>
>http://www.cs.uu.nl/~visser/publications/
>http://citeseer.nj.nec.com/visser97scannerles.html

  Hans Aberg