# Debugging a grammar

To make a grammar unambiguous, the workflow is as follows.

1. Start with a grammar written in LBNF, in our case `cpp.cf` that sucessfully parses some testfile.
2. Find the rules in the `.info`-file that cause a conflict
3. Find the corresponding rules in `cpp.cf` that cause the conflict.
4. Change `cpp.cf`.
5. Check that the new `cpp.cf` still parses the testfile. Go to 2.

## Eliminating reduce-reduce conflicts

### Example 1: Rules in the grammar that already follow from others

**Solution:** Delete rules.

In more detail, if we have rules in the context-free grammar of the `.info`-file such as

A -> B
B -> C
A -> C

then there will be a reduce/reduce conflict: Reduce `C` to `A` or to `B`? The solution is to delete `A -> C`.

From a logical point of view, if you know "A implies B" and "B implies C", you don't need to also say "A implies C" as this follows already from the other two.

From a computational point of view, if you can reduce C to B and B to A, then you can also reduce C to A. It is true that this needs two steps then, but it is better to reduce C to A in two steps, than to introduce ambiguity into the grammar.

**Summary:** While shortcuts help us humans to parse more quickly, shortcuts are bad for search algorithms because they create choice points that cause backtracking. This phenomenon is not restricted to parsing, but relevant to all kind of search in the presence of choice. (Discuss: Why do shortcuts help humans but harm machines?)

### Example 2: Different rules that look the same to the parser

**Solution:** Name the corresponding non-terminals differently.

Let us look at a detailed example of how this can work.

Here is a snippet of a `.info`-file

-----------------------------------------------------------------------------
Info file generated by Happy Version 1.19.9 from ParCpp.y
-----------------------------------------------------------------------------

state 37 contains 2 shift/reduce conflicts and 25 reduce/reduce conflicts.
state 89 contains 1 shift/reduce conflicts and 26 reduce/reduce conflicts.
state 104 contains 1 reduce/reduce conflicts.
state 116 contains 1 shift/reduce conflicts and 18 reduce/reduce conflicts.
state 166 contains 1 shift/reduce conflicts.

This is a lot of reduce/reduce conflicts.

Let us go to state 37 to find out what might be the problem.

ListId -> Id . (rule 44)
ListId -> Id . '::' ListId (rule 45)
ListId -> Id . (rule 46)
ListId -> Id . ',' ListId (rule 47)

'!=' reduce using rule 46
(reduce using rule 44)

The last two lines tell us that there is a conflict between reducing with rule (44) and rule (46). Both rules are listed as part of the description of the state. We see that both rules look the same. How can we avoid this duplication?

Let us look at which rules in the grammar are responsible for this. This is not hard to find as there are only few rules containing `::` and `,`. This leads us to

separator nonempty Id "::" ;
separator nonempty Id "," ;

which in turn are called from (I am **not** advocating rules such as `Exp15::=[Id]` here, this example is purely illustrative):

ADecl. Arg ::= Type [Id] ;
EId. Exp15 ::= [Id] ;

The problem is clear. A list in `Arg` should be different from a list in `Exp` because the first should be separated by `,` and the second by `::`. But the grammar does not make this distinction.

Let us see how the this part of the BNF-grammar is translated by BNFC into a context-free grammar. We can see this if we go back to the `.info`-file and look at its grammar, which contains (amongst others) the rules

ListId -> Id (44)
ListId -> Id '::' ListId (45)
ListId -> Id (46)
ListId -> Id ',' ListId (47)

Arg -> Type ListId (37)
Exp15 -> ListId (67)

To make the grammar see the difference of the two kind of lists we replace in the BNF-grammar

separator nonempty Id "::" ;
separator nonempty Id "," ;

ADecl. Arg ::= Type [Id] ;
EId. Exp15 ::= [Id] ;

by

L1a. NameListId ::= Id ;
L1b. NameListId ::= Id "::" NameListId ;
L2a. ArgListId ::= Id ;
L2b. ArgListId ::= Id "," ArgListId ;

ADecl. Arg ::= Type ArgListId ;
EId. Exp15 ::= NameListId ;

Running BFNC/Happy again on this grammar gives

-----------------------------------------------------------------------------
Info file generated by Happy Version 1.19.9 from ParCpp.y
-----------------------------------------------------------------------------

state 38 contains 1 shift/reduce conflicts.
state 89 contains 1 shift/reduce conflicts.
state 118 contains 1 shift/reduce conflicts.
state 164 contains 1 shift/reduce conflicts.

from which see that all reduce/reduce conflicts have been eliminated.

**Summary:** If two non-terminals in your grammar have the same name but serve different roles, be suspicious. Consider nameing them differently.

#### Why does renaming work?

How does this work? After all it looks like there still might be a conflict in that we have two rules

L1a. NameListId ::= Id ;
L2a. ArgListId ::= Id ;

which look like we might get into a situation where we want to reduce `Id` to `NameListId` or to `ArgListId`. The answer is that since we read the input from left to right, when we have `Id` on the top of the stack, we already parsed the input on the left of `Id` and this means that, at least in this particular case, we we have enough information to make the decision. In more detail, the parser will be in one state if we should reduce by `L1a` and in another state if we need to reduce by `L1b`. In the `.info`-file this could look like this:

State 38

NameListId -> Id . (rule 45)
NameListId -> Id . '::' NameListId (rule 46)

'!=' reduce using rule 45

and

State 89

ArgListId -> Id . (rule 47)
ArgListId -> Id . ',' ArgListId (rule 48)

'!=' reduce using rule 47

Even though these two states look similar, they are reached by a different parsing history. And it is this history that contains the knowledge about whether to reduce by (45) or (47).

## Shift-reduce conflicts

Going back to the `.info`-file

-----------------------------------------------------------------------------
Info file generated by Happy Version 1.19.9 from ParCpp.y
-----------------------------------------------------------------------------

state 38 contains 1 shift/reduce conflicts.
state 89 contains 1 shift/reduce conflicts.
state 118 contains 1 shift/reduce conflicts.
state 164 contains 1 shift/reduce conflicts.

we see that there are still shift/reduce conflicts. Shift reduce conflicts can be benign, but we need to convince ourselves of this.

In case of a shift/reduce conflict, the parser always shifts. But we need to check that this is what we really want **in all of the states listed as having a conflict**.

### Example 3

Looking again at state 38 in the `.info`-file we find

State 38

NameListId -> Id . (rule 45)
NameListId -> Id . '::' NameListId (rule 46)
Exp15 -> Id . '<' Type '>' Id (rule 59)
Exp15 -> Id . '(' ListExp ')' (rule 67)

[...]
'<' shift, and enter state 144
(reduce using rule 45)

To understand whether this is what we want we need to have a closer look at

NameListId -> Id . (rule 45)
Exp15 -> Id . '<' Type '>' Id (rule 59)

The question is whether to reduce using (45) or whether to shift in order to later reduce using (59).

**Notation:** The `.` in `Exp15 -> Id . '<' Type '>' Id` indicates that in State 38 we already read `Id` and are about to read `'<' Type '>' Id`.

**Notation:** The `'<'` in `shift, and enter state 144` is the so-called look-ahead. It means that we are going to `shift, and enter state 144` if the next symbol in the input is a `<`.

It should be clear now that this particular shift/reduce conflict is benign and should be resolved by shifting.

### Example 4

Let us look at the following partial description of state with a shift/reduce conflict.

State 153

Exp1 -> Exp . '<<' Exp (rule 82)
Exp1 -> Exp '::' Exp . (rule 83)

'<<' shift, and enter state 112
(reduce using rule 83)

The problem is here that even though `<<` and `::` have different meaning, they are both produced by the same non-terminal `Exp1`.

Another way to understand this, is to look at

A :: B << C

Should this be parsed as `(A :: B) << C` or as `A :: (B << C)`?

To answer this question you need to use your knowledge of C++. If you come to the conclusion that only `(A :: B) << C` is correct, then we need to reduce with (83) instead of shifting the `<<`. In other words, in our example, the parser makes a wrong decision in State 153.

A solution is be to introduce a new non-terminal for the syntactic category of items separated by `::`. In this example we can replace the rule in the `.cf`-file

EQe. Exp1 ::= Exp "::" Exp ;

by

QConstBase. QConst ::= Id ;
QConstRec. QConst ::= Id "::" QConst;
EQe. Exp1 ::= QConst ;

**Warning**: I am not proposing that this should be part of a correct grammar for C++. The correctness of grammar rules cannot be judged in isolation. I am merely illustrating a method of how to eliminate shift-reduce conflicts here.

**Remark:** Do you see that this is also the method that was used to produce the grammar `Calc.cf` for the Calculator example in the BNFC tutorial?

### The Dangling Else

The [dangling else](https://en.wikipedia.org/wiki/Dangling_else) (good Wikepedia article) is an example of a benign shift-reduce conflict. To illustrate it, we can look at the following grammar in BNF

Exp ::= ExpIf | ExpIfElse | C | D | ...
ExpBool ::= A | B | ...
ExpIf ::= "if" ExpBool "then" Exp
ExpIfElse ::= "if" ExpBool "then" Exp "else" Exp

(Note that in the grammar we chose to make if-then-else an expression (as in our langauge LambdaNat we have seen last semester in Programming Languages), not a statement, as, for example, in C++ or [F#](https://fsharpforfunandprofit.com/posts/expressions-vs-statements/).)

**Activity:** How many ways are there to parse

if A then if B then C else D

**Activity:** Study the example ["I saw the astronomer with my glasses"](https://github.com/alexhkurz/compiler-construction-2021/blob/master/Sources/The_tourist_saw_the_astronomer_with_the_telescope.pdf) and explain how the ambiguity of this sentence is structurally analogous to that of the dangling else.

## Homework

By following through what I explain in this lecture with your own `Cpp.cf` file do the following exercises.

**Exercise:** Can you eliminate all reduce/reduce conflicts in your `Cpp.cf`?

**Exercise:** Are all the shift-reduce conflicts in your `Cpp.cf` benign?