Re: Can shift/reduce problems be eliminated?

Carl Cerecke <cdc@maxnet.co.nz>
31 Dec 2002 23:47:15 -0500

          From comp.compilers

Related articles
Can shift/reduce problems be eliminated? ashwin21_99@hotmail.com (Ashwin) (2002-12-30)
Re: Can shift/reduce problems be eliminated? clint@0lsen.net (Clint Olsen) (2002-12-31)
Re: Can shift/reduce problems be eliminated? vugluskr@unicorn.math.spbu.ru (2002-12-31)
Re: Can shift/reduce problems be eliminated? cdc@maxnet.co.nz (Carl Cerecke) (2002-12-31)
Re: Can shift/reduce problems be eliminated? gah@ugcs.caltech.edu (glen herrmannsfeldt) (2003-01-04)
Re: Can shift/reduce problems be eliminated? bonzini@gnu.org (2003-01-04)
Re: Can shift/reduce problems be eliminated? vugluskr@unicorn.math.spbu.ru (2003-01-04)
Re: Can shift/reduce problems be eliminated? cdc@maxnet.co.nz (Carl Cerecke) (2003-01-07)
Re: Can shift/reduce problems be eliminated? bje@redhat.com (Ben Elliston) (2003-01-07)
| List of all articles for this month |

From: Carl Cerecke <cdc@maxnet.co.nz>
Newsgroups: comp.compilers
Date: 31 Dec 2002 23:47:15 -0500
Organization: TelstraClear
References: 02-12-121
Keywords: parse, yacc
Posted-Date: 31 Dec 2002 23:47:15 EST

> [ ...
  > Reduce/reduce conflicts mean your grammar is
> ambiguous and two rules match the same input.
  > ...
> -John]


To be a bit nitpicky, a reduce/reduce conflict doesn't necessarily
indicate an ambiguity. The only thing you can be sure about (without
looking at the grammar) is that it is not LALR(1) (for yacc/bison).


For example, the bison grammar:


S: A 'a' 'b' | B 'a' 'c' ;
A: 'z' ;
B: 'z' ;


is definitely not ambiguous, but it needs two symbols of lookahead
to determine whether A -> z or B -> z should be reduced after seeing
a 'z'. Bison reports a reduce/reduce error.


The state with the problem looks like:


state 1


          A -> 'z' . (rule 3)
          B -> 'z' . (rule 4)


          'a' reduce using rule 3 (A)
          'a' [reduce using rule 4 (B)]
          $default reduce using rule 3 (A)


It should be clear that, if bison were LR(2), then this state would
have no conflict and look like:


state 1


          A -> 'z' . (rule 3)
          B -> 'z' . (rule 4)


          'a' 'b' reduce using rule 3 (A)
          'a' 'c' reduce using rule 4 (B)
          $default reduce using rule 3 (A)


The solution in this simple case is, of course, is to rewrite the
grammar. But sometimes it can be quite difficult to rewrite correctly.


<grumble>
I'm currently finishing off a parser for a rather large language with
many such tricky cases. The current version of my grammar "contains 147
shift/reduce conflicts and 232 reduce/reduce conflicts.", according
to bison, in a generated parser of over 2000 states. Beware of languages
designed by comittee!
</grumble>


Cheers,
Carl


Post a followup to this message

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