There are two kinds of conflicts that can occur in an SLR(1) parsing table.
A shift-reduce conflict occurs in a state that requests both a shift action and a reduce action.
A reduce-reduce conflict occurs in a state that requests two or more different reduce actions.
SLR(1) parsers need to decide on an action. But, unlike LL(1) parsers, they do not make predictions. Instead, a decision is made based on what has already been read plus one lookahead token.
Like top-down parsers, you can avoid parsing conflicts in an SLR(1) parser by deferring a decision until more of the input has been seen.
For top-down parsers, you typically do that by left-factoring. For bottom-up parsers, you can get rid of conflicts by unfactoring!
Look at the following grammar, with start symbol S.
| S | → | e B b A |
| S | → | e A |
| A | → | a |
| A | → | ε |
| B | → | a |
| B | → | a D |
| D | → | b |
There is a parsing conflict. One of the states of the LR(0) finite-state machine is
|
On lookahead b, the parser has to consider the following possibilities.
Since LR(0) item B → a ⋅ D is in the state, the b might be the token generated by the D. So the parser should shift the b in anticipation of then reducing by D → b.
Because of the first production, token b can follow B. Since LR(0) item B → a ⋅ is in the state, the parser should reduce by B → a, anticipating that the lookahead b immediately follows B.
Here is the entire LR(0) finite-state machine, as created by Bison.
Grammar
0 $accept: S $end
1 S: 'e' B 'b' A
2 | 'e' A
3 A: 'a'
4 | /* empty */
5 B: 'a' D
6 | 'a'
7 D: 'b'
State 3 conflicts: 1 shift/reduce
state 0
0 $accept: . S $end
'e' shift, and go to state 1
S go to state 2
state 1
1 S: 'e' . B 'b' A
2 | 'e' . A
'a' shift, and go to state 3
$default reduce using rule 4 (A)
A go to state 4
B go to state 5
state 2
0 $accept: S . $end
$end shift, and go to state 6
state 3
3 A: 'a' .
5 B: 'a' . D
6 | 'a' .
'b' shift, and go to state 7
'b' [reduce using rule 6 (B)]
$default reduce using rule 3 (A)
D go to state 8
state 4
2 S: 'e' A .
$default reduce using rule 2 (S)
state 5
1 S: 'e' B . 'b' A
'b' shift, and go to state 9
state 6
0 $accept: S $end .
$default accept
state 7
7 D: 'b' .
$default reduce using rule 7 (D)
state 8
5 B: 'a' D .
$default reduce using rule 5 (B)
state 9
1 S: 'e' B 'b' . A
'a' shift, and go to state 10
$default reduce using rule 4 (A)
A go to state 11
state 10
3 A: 'a' .
$default reduce using rule 3 (A)
state 11
1 S: 'e' B 'b' A .
$default reduce using rule 1 (S)
But what if we expand out the rules for B in the first production, as follows.
| S | → | e a D b A |
| S | → | e a b A |
| S | → | e A |
| A | → | a |
| A | → | ε |
| D | → | b |
Now the conflict disappears! The reason is that no decision needs to be made whether to reduce by B → a. The parser just shifts the a and waits until later to decide what to do.
Here is the LR(0) finite-state machine for the unfactored grammar.
Grammar
0 $accept: S $end
1 S: 'e' 'a' D 'b' A
2 | 'e' 'a' 'b' A
3 | 'e' A
4 A: 'a'
5 | /* empty */
6 D: 'b'
state 0
0 $accept: . S $end
'e' shift, and go to state 1
S go to state 2
state 1
1 S: 'e' . 'a' D 'b' A
2 | 'e' . 'a' 'b' A
3 | 'e' . A
'a' shift, and go to state 3
$default reduce using rule 5 (A)
A go to state 4
state 2
0 $accept: S . $end
$end shift, and go to state 5
state 3
1 S: 'e' 'a' . D 'b' A
2 | 'e' 'a' . 'b' A
4 A: 'a' .
'b' shift, and go to state 6
$default reduce using rule 4 (A)
D go to state 7
state 4
3 S: 'e' A .
$default reduce using rule 3 (S)
state 5
0 $accept: S $end .
$default accept
state 6
2 S: 'e' 'a' 'b' . A
6 D: 'b' .
'a' shift, and go to state 8
'b' reduce using rule 6 (D)
$default reduce using rule 5 (A)
A go to state 9
state 7
1 S: 'e' 'a' D . 'b' A
'b' shift, and go to state 10
state 8
4 A: 'a' .
$default reduce using rule 4 (A)
state 9
2 S: 'e' 'a' 'b' A .
$default reduce using rule 2 (S)
state 10
1 S: 'e' 'a' D 'b' . A
'a' shift, and go to state 8
$default reduce using rule 5 (A)
A go to state 11
state 11
1 S: 'e' 'a' D 'b' A .
$default reduce using rule 1 (S)