3 Jun 2003 00:37:33 -0400

Related articles |
---|

left or right association for unary operators??? news@ono.com (Antonio López Torres) (2003-05-29) |

Re: left or right association for unary operators??? haberg@matematik.su.se (2003-06-03) |

From: | haberg@matematik.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 3 Jun 2003 00:37:33 -0400 |

Organization: | Mathematics |

References: | 03-05-213 |

Keywords: | parse |

Posted-Date: | 03 Jun 2003 00:37:32 EDT |

"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/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.