Re: left or right association for unary operators???

"Antonio López Torres" <news@ono.com> wrote:


>I would like to know if there is any diference between declaring
>NOT token as %left or %right in the next grammar and why if i
>declare as %token exists 2 shift/reduce conflicts.
>
>expr
> : expr
> | expr AND expr
> | expr OR expr
> | NOT expr
> | (expr)
> ;


Your parse generator probably use a token based precedence method, as
described in 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.
=====================================================================


If you have a grammar:


expr
      : value -- Obs! Not "expr", as you wrote above.
      | expr AND expr
      | expr OR expr
      | NOT expr
      | (expr)
      ;


and the parser sees the NOT, it will end up in a state (see books on
parsing, like Aho, Sethi & Ullman, "Compilers..." and the Parsing
Techniques book: <http://www.cs.vu.nl/~dick/PTAPG.html>):


expr -> NOT . expr -- Plus closure of . expr:
expr -> . value
expr -> . expr AND expr
expr -> . expr OR expr
expr -> . NOT expr
expr -> . (expr)


plus some lookahead data. When the next expr has been read one enters a state:


expr -> NOT expr .
expr -> expr . AND expr
expr -> expr . OR expr


plus some lookahead data. If the next token is AND, it is not possible for
the parser to uniquely determine whether to reduce or to shift, by the
example given by John Levine:
>[Without the precedence, expressions are ambiguous:
>
> NOT A AND B is it (NOT A) AND B or NOT (A AND B) ?
>
>-John]


Now look at the Grune description of token precedence above: We have u =
NOT, t = AND. As normally, precedence(NOT) > precedence(AND), that will
alone tell to reduce ("(NOT A) AND B"); reverse the precedence inequality
and you get a shift ("NOT (A AND B)").


If you want the associativity to come into play, it must be among tokens
of the same precedence. Normally NOT is given a unique precedence among
the token (but one can have, as in C/C++, both unary - and +). If we have
the input sequence NOT NOT expr, then after seeing the first NOT, we end
up in the state:


expr -> NOT expr .
expr -> NOT . expr -- Plus closure of . expr:
expr -> . value
expr -> . expr AND expr
expr -> . expr OR expr
expr -> . NOT expr
expr -> . (expr)


plus some lookahead information.


Here you have a new shift/reduce conflict, at least without the lookahead
info. In the Grune quote, t = u = NOT. If the associativity is left, one
should reduce, and if it is right, one should shift. Here, you do not want
to compute NOT NOT expr as (NOT NOT) expr, but you want to wait to get NOT
(NOT expr). Thus, you should shift. But (NOT NOT) expr is in principle
possible, if the value can also be a NOT token. I think though that a
LALR(1) algorithm sill discover that (NOT NOT) expr cannot appear by some
lookahead information, and remove it if NOT cannot be a value. Thus,
precedence associativity may not make any practical difference, even
though "right" is the correct one.


So that's it: Just jog through the above stuff, and you will find out why.


There is the problem with the token precedence stuff in the quote above,
and that it probably depends on the parse algorithm (LALR, LR, etc). One
can also make precedence declaration between rules, which is done in
        http://www.cs.uu.nl/people/visser/ftp/BSVV02.pdf
Then this does not depend on the parse algorithm, as it precedence is
described purely in terms of restrictions of parse trees.


Suc a rule based precedence is probably a much better method (I am looking
into a generalization now), but that is probably not how it is implemented
in the typical LR parser generator.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.math.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

Return to the comp.compilers page.
Search the comp.compilers archives again.