# Shift-reduce and reduce-reduce conflicts

If there are conflicts in the `.info` file created by your grammar and BNFC, it means that the same program can have two potentially different meanings.

In case of a shift-reduce conflict, the question is whether to shift or whether to reduce. In case of a reduce-reduce conflicts there are two different rules that can be used to reduce the same handle.

Why are conflicts bad?

- Code generation depends on the rule that was used to reduce. So we need to make sure that the correct rule is used during parsing in order to be able to correctly generate code later.

- For efficiency reasons, the parsers generated by BNFC are determinstic. This is achieved by having the parser resolve conflicts generated by an ambigious grammar. But this means that the parser may reject programs even if they are legal according to the grammar. So if you cannot understand why the parser does not recognise a seemingly legal program, try to reduce the number of conflicts.

As a rule of thumb:

- If you have reduce-reduce conflicts, change the grammar to eliminate them.
- If you have shift-reduce conflicts, the parser chooses shift over reduce. Check in the `.info` file that this is the decision you want. If yes, your are ok. If not, change the grammar.

We will look now in more detail at how to do this.

## Required reading

Section 3.8 of [Implementing Programming Languages](http://www.cse.chalmers.se/edu/year/2012/course/DAT150/lectures/plt-book.pdf).

## How to make grammars unambiguous

The reason for conflicts is that the grammar is ambiguous. That is, the same program can have different parse trees. This is bad.

How can we make an ambiguous grammar unambiguous? Rouhly speaking, it depends on whether there are too many rules or whether there are not enough rules.

- Delete superfluous rules. Sometimes the ambiguity just comes from the presence of rules that are not needed.

- Add new rules and/or non-terminals. If two constructs have different meanings in the programming language they should be produced by different non-terminals.

## The example of arithmetic expressions (again)

Back in the first lecture about parsing and then again in the lecture on [shift-reduce parsing](https://hackmd.io/@alexhkurz/rk5PsF2EI), we looked at the grammar of arithmetic expressions. The first grammar one might come up with for arithmetic expressions could be

EAdd. Exp ::= Exp "+" Exp ;
EMul. Exp ::= Exp "*" Exp ;
EInt. Exp ::= Integer ;

Let us save this as [`expaddmult1.cf`](https://github.com/alexhkurz/compiler-construction-2022/blob/master/Sources/Expaddmult/expaddmult1.cf) and create a parser and `.info` file for it. Creating the parser, we get the warning

shift/reduce conflicts: 4

Let us look at [`ParExpaddmult1.info`](https://github.com/alexhkurz/compiler-construction-2022/blob/master/Sources/Expaddmult/ParExpaddmult.info). We find in there

state 7 contains 2 shift/reduce conflicts.
state 8 contains 2 shift/reduce conflicts.

and, leaving out some lines,

State 7

Exp -> Exp '+' Exp . (rule 2)
Exp -> Exp . '*' Exp (rule 3)

'*' shift, and enter state 5
(reduce using rule 2)

State 8

Exp -> Exp . '+' Exp (rule 2)
Exp -> Exp '*' Exp . (rule 3)

'+' shift, and enter state 6
(reduce using rule 3)

**Remark:** Look at `Exp -> Exp . '+' Exp (rule 2)`.
- Note the `.`
- `A -> B . C` means that the parser has parsed `B` and expects to parse `C` to then reduce according to `A -> B C`

This tells us the following about `State 7`. In State 7 the parser
- either parsed and `Exp + Exp` and wants to reduce according to (rule 2)
- or parsed an `Exp` and, in case there is a `*` in the input, wants to shift the `*`

**Exercise:** Parse `1+2*3` according to the rules of the grammar until the remaining input is `*3`.

**Question:** Should we reduce according to `Exp -> Exp + Exp` or should we shift the `*`?

In other words, there is a shift/reduce conflict here.

The bnfc/happy parser always **chooses the shift over the reduce**.

But we need to be careful. The grammar remains ambiguous and we need to be sure that the decision of bnfc/happy is the one that is compatible with the definition of the language.

**Exercise:** Which parse tree does the parser produce on input `1+2*3`?

**Exercise:** Which parse tree does the parser produce on input `1+2*3+4`?

**Question:** Are both parse trees the ones we want to get according to the usual definition of the meaning of arithmetic expressions?

**Question:** How can we resolve the ambiguity in the grammar?

A typical answer to the question is to allow the grammar to make distinctions it was not able to make before.

In this example, the problem arises from the fact that `+` and `*` need to be treated differently, but are not distinguishable by the rules of the grammar.

**Observation:** If we permute in the grammar above `+` and `*`, we obtain again the same grammar.

To break this symmetry, we distinguish between expressions that are additions and expressions that are multiplications in the grammar [`expaddmult2.cf`](https://github.com/alexhkurz/compiler-construction-2022/blob/master/Sources/Expaddmult/expaddmult2.cf):

EAdd. Exp ::= Exp "+" Exp1 ;
EMul. Exp1 ::= Exp1 "*" Exp2 ;
EInt. Exp2 ::= Integer ;

coercions Exp 2 ;

Note that now `Exp` produces sums and `Exp1` produces products. Computing bottom-up, this means that `*` is computed before `+`. Running this grammar through `bnfc`, we obtain a new parser in [`ParExpaddmult2.info`](https://github.com/alexhkurz/compiler-construction-2022/blob/master/Sources/Expaddmult/ParExpaddmult2.info) which has no conflicts anymore.

Let us look at one detail in particular. In the new parser we find the following

State 16

Exp -> Exp '+' Exp1 . (rule 4)
Exp1 -> Exp1 . '*' Exp2 (rule 6)

')' reduce using rule 4
'*' shift, and enter state 12
'+' reduce using rule 4

**Question:** How does State 16 of the new grammar compare to State 7 of the old grammar?

The new grammar is not ambiguous. The new grammar can correctly decide whether to shift or reduce by employing a so-called 1-symbol **look ahead**. (That is where the name LALR(1) for this type of grammar comes from: Look Ahead LR (1).)