## 9.8. Handling Parsing Conflicts by Unfactoring

### Types of conflicts

There are two kinds of conflicts that can occur in an SLR(1) parsing table.

1. A shift-reduce conflict occurs in a state that requests both a shift action and a reduce action.

2. A reduce-reduce conflict occurs in a state that requests two or more different reduce actions.

### Unfactoring

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

 A → a⋅ B → a⋅ D B → a⋅

On lookahead b, the parser has to consider the following possibilities.

1. Since LR(0) item Ba 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 Db.

2. Because of the first production, token b can follow B. Since LR(0) item Ba is in the state, the parser should reduce by Ba, 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 Ba. 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)
```