yacc shift/reduce conflict with empty rules

Question

test.y

%%
TOP :
    OPTIONS
  ;

OPTIONS :
    OPTION
  | OPTIONS OPTION
  ;

OPTION :
   /*no option is possible*/
  | 'C'
  ;
%%

yacc -v test.y

y.output contains the following

   0  $accept : TOP $end

   1  TOP : OPTIONS

   2  OPTIONS : OPTION
   3          | OPTIONS OPTION

   4  OPTION :
   5         | 'C'

0: shift/reduce conflict (shift 1, reduce 4) on 'C'
state 0
    $accept : . TOP $end  (0)
    OPTION : .  (4)

    'C'  shift 1
    $end  reduce 4

    TOP  goto 2
    OPTIONS  goto 3
    OPTION  goto 4


state 1
    OPTION : 'C' .  (5)

    .  reduce 5


state 2
    $accept : TOP . $end  (0)

    $end  accept


3: reduce/reduce conflict (reduce 1, reduce 4) on $end
3: shift/reduce conflict (shift 1, reduce 4) on 'C'
state 3
    TOP : OPTIONS .  (1)
    OPTIONS : OPTIONS . OPTION  (3)
    OPTION : .  (4)

    'C'  shift 1
    $end  reduce 1

    OPTION  goto 5


state 4
    OPTIONS : OPTION .  (2)

    .  reduce 2


state 5
    OPTIONS : OPTIONS OPTION .  (3)

    .  reduce 3


State 0 contains 1 shift/reduce conflict.
State 3 contains 1 shift/reduce conflict, 1 reduce/reduce conflict.


3 terminals, 4 nonterminals
6 grammar rules, 6 states

Why are there shift/reduce and reduce/reduce conflicts.

I have read how yacc parser works in the "How the Parser Works" section of http://dinosaur.compilertools.net/yacc/ but I don't understand how yacc deals with empty rules. Seems like it is trying to use the empty rule everywhere.

Question 1. How yacc deals with empty rules interms of the state machine and the "look ahead token" described in the link above.

Question 2. How I get rid of the conflicts and still maintain the "logic" of the grammar ?

Thanks for the help beforehand.

rici rici · Accepted Answer · 2017-05-23T17:12:12

Of course it is trying to use the empty rule "everywhere". It is doing what you told it to do.

What you say is that the non-terminal OPTIONS represents any positive number of OPTION non-terminals, and an OPTION nonterminal can be a C or empty.

Since an OPTION can be empty, there can be any number of them in the empty input. Two empty OPTIONs look exactly like 153 empty OPTIONs. What's more, there can be any number of empty OPTIONs between two C tokens.

So your grammar is ambiguous, and bison reports parsing conflicts.

If you wanted to define OPTIONS as any number of OPTIONs, including zero OPTIONs, then just say that:

options: %empty
       | options option
option : 'C'

yacc shift/reduce conflict with empty rules

1 Answers