yacc

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:

where there is a shift-reduce conflict, perform the shift
where there is a reduce-reduce conflict, reduce by the grammar rule that appears earlier in the yacc specification

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.