Disambiguating rules

yacc uses ``disambiguating rules'' so that it can produce a parser when shift-reduce or reduce-reduce conflicts occur. The two default disambiguating rules are:

Rule 1 means reductions are deferred in favor of shifts when there is a choice. Rule 2 gives the user further control over the behavior of the parser when there are reduce-reduce conflicts; these should be avoided whenever possible.

In general, when it is possible to apply disambiguating rules to a grammar to produce a correct parser, it is also possible to write equivalent grammar rules without the ambiguities.

yacc always reports the number of shift-reduce and reduce-reduce conflicts resolved by the two disambiguating rules. The conflict messages of yacc are best understood by examining the y.output file. Here is an example that describes the conflicts that arise from an if-else construct, a common source of ambiguity in programming language grammars:

   23: shift-reduce conflict (shift 45, reduce 18) on ELSE

state 23

stat : IF ( cond ) stat\_ (18) stat : IF ( cond ) stat\_ELSE stat

ELSE shift 45 . reduce 18

The first line describes the conflict, giving the state and the input symbol. The state description gives the grammar rules active in the state and the parser actions. In state 23, the parser has seen input corresponding to:
   IF  (  cond  )  stat
Two grammar rules are active at this time, and so the parser can do one of two things. If the input symbol is ELSE, it will shift into state 45. State 45 will have the following line as part of its description, indicating that ELSE has been shifted to arrive at this state.
   stat  :  IF  (  cond  )  stat  ELSE\_stat
In state 23, the default action (designated by a dot, (.) ) will be performed if the input symbol is something other than ELSE. In that case, the parser reduces by grammar rule 18:
   stat  :  IF  '('  cond  ')'  stat
The fact that the action that occurs when ELSE is read appears first in y.output indicates that the shift is the favored action.

Users who encounter unexpected shift-reduce conflicts will probably want to look at the verbose output to decide whether the default actions are appropriate.

Next topic: Precedence
Previous topic: Ambiguity and conflicts

© 2003 Caldera International, Inc. All rights reserved.
SCO OpenServer Release 5.0.7 -- 11 February 2003