Unable to fix/understand a simple "shift/reduce conflict" of bison

Question

I am trying to eliminate all conflicts in a Bison grammar file. I was unable to understand a source of conflicts of which there are several instances. I narrowed down the problem and created this small Bison file to illustrate the problem precisely as it occurs in the original file:

NOTE: Code changed since first posted.

  %token terminalA terminalB
  %token INTEGER
  %%
  START : startEntries
  startEntries:  terminalBLine
                 terminalALines //Optional
                 {
                 }
  terminalALines : terminalALine
                   | terminalALines terminalALine
                   | //To allow terminalALine to be not present at all.
  terminalALine :  terminalA INTEGER
  terminalBLine :  terminalB INTEGER
  %%

~
Running bison on the file outputs:

      bison -v -y test.y
      test.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]

Yes, I am aware of the -v option to review conficts. Relevant section in the .output file is:

State 4
2 startEntries: terminalBLine . terminalALines
terminalA  shift, and go to state 7
terminalA  [reduce using rule 5 (terminalALines)]
$default   reduce using rule 5 (terminalALines)
terminalALines  go to state 8
terminalALine   go to state 9

If I delete the commented line with the solo "|" then the conflict is resolved. But the absence of terminalALines is also valid input which I believe will not be possible if I delete the "|" line. If I move the commented line to the line after "terminalALine : terminalA INTEGER" it should serve the same purpose (?) but results in even more conflicts.

I have removed all error processing and action statements to focus on the core issue.

The prefix "terminal" as I realized after posting the question has no semantic connotations.

David Maze David Maze · Accepted Answer · 2019-12-19T11:46:03

Let's focus on the rules:

terminalALines : terminalALine
                   | terminalALines terminalALine
                   | //To allow terminalALine to be not present at all.
terminalALine :  terminalA INTEGER

Say my input is terminalA INTEGER.

terminalALines allows a recursive terminalALines. Also, terminalALines can be empty. So let's start by parsing an empty terminalALines, and recurse. Now, terminalALines can start with a terminalALines, which can be empty, so...

The error is more or less saying that, if it's trying to parse terminalALines and sees a terminalA token, it can't decide whether to recursively run the terminalALines rule again or to parse a single terminalALine out of it.

You can work around this by rearranging your rule to have the recursive case be second

terminalALines : terminalALine terminalALines
                   | // empty
terminalALine :  terminalA INTEGER

Now if you see terminalA, things are clear: you must parse out a terminalALine, then look for another terminalALines, which may or may not be empty.

Unable to fix/understand a simple "shift/reduce conflict" of bison

1 Answers