**Note: **The transformation of the grammar is the first (optional) step for the creation of a parser of every kind: LL or LR or LALR. This will solve the ambiguity for LR and LALR, but for the LL parser, you’ll still need to remove epsilon production, remove left recursion and remove left factorization.

Teaching tool for all kinds of parsers: jsmachines.

In this post, only the transformation will be treated, but if you’re writing a parser, this article should provide some insight.

As you all know a context free grammar ( CFG ) is ambiguous if there is a string in the language that can be generated by two or more, parse trees. A CFG is unambiguous if every string generated has exactly one parse tree.

The parser generators can handle *only some* type of ambiguity, in particular the ambiguity generated by the priority and associativity of the operators. An example of the associativity problem is:

For this simple grammar, the string INT + INT + INT generates two parse trees.

Even if this kind of ambiguity is handled by a parser generator, I’m going to show you how to create an equivalent unambiguous grammar. Equivalent means that the new grammar will generate the same language as the old one. **It’s often the case that a string in the new grammar will have a different parse tree than the one in the old grammar.**

The transformation is composed of 3 steps:

- Find where the ambiguity is.
- Decide which parse tree is the correct one.
- Create an equivalent unambiguous grammar.

## Example left associativity

The grammar in the picture above is *Exp → Exp + Exp | INT . *We find where the ambiguity is by looking at the parse tree, and based on the left associativity rule, the right tree is the left one. This is because we want to sum the expression from left to right, as 1+2+3 = (1+2+3), and since the evaluation of the result from the tree is bottom-up, the left tree represents the calculation. We need to allow the first *Exp *in the production and block the second *Exp *with the introduction of a terminal. The rewritten grammar is:

*Exp → Exp + INT — —*for enforcing the left associativity.*Exp → INT — —*for producing the string*INT .*

## Example right associativity

Another example from algebra is the right associativity of the power operator: 1^2^3 = 1^(2^3) . The basic grammar is: *Exp → Exp ^ Exp | INT .*

The correct tree is the right one. The rewritten grammar is:

*Exp → INT ^ Exp — —*for enforcing the right associativity.*Exp → INT — —*for producing the string*INT .*

## Example no associativity

If we want to write a simple inequality for the *less than* the operator, there is no associativity since it’s allowed only a single operator. So a string like *INT < INT < INT* is not permitted. Below is the parse tree for the string in the grammar *Exp → Exp < Exp | INT *.

They are both incorrect. Since this is a toy example, we could rewrite the grammar as *Exp → INT< INT *. In a typical case, we need the application of the rule only once, so we need to introduce a new non-terminal; for example:

*Exp → Exp’ < Exp’**Exp’ → Exp’ + INT | INT*

## Example priority (precedence)

This is the case where some symbols have precedence over others, such as multiplication above sum. From the simple grammar: *Exp → Exp * Exp | Exp + Exp | INT *, it’s possible to find a string that produces two trees as: *INT + INT * INT *. But we all know that the product has precedence, so the correct tree is the right one.

In this case, we have to introduce a new non-terminal. It’s important to remember that the tree is evaluated bottom-up, so the priority in the grammar is inverted; in the first rule, there is the lowest priority.

*Exp → Exp + Term | Term**Term → Term * INT | INT*

Both the operators are left associative.

## CFG for arithmetic

The grammar for writing simple expressions is a classic in textbooks since it shows a mix of the cases above.

*Exp → Exp * Exp | Exp / Exp | Exp + Exp | Exp - Exp |Exp ^ Exp | (Exp) | -Exp | INT*

The order precedence from the lowest to the highest is:* + -* then ** / *then* *^ then unary minus and *()*. Also, the operator power has right associativity, while the unary minus has no associativity; all the others have left associativity. So the unambiguous grammar is (the names are changed for readability):

*A → A+ B| A - B | B**B → B * C | B / C | C**C → D ^ C | -D | D**D → ( A ) | INT*

## CFG for boolean

*F → F ∧ F | F ∨ F | ¬ F | ( F ) | atom*

The standard precedence order is: *∨ *then *∧ *then* ¬ *then* () . *The operators (and, or) are left associative. So the unambiguous grammar is:

*A → A ∨ B| B**B → B ∧ C | C*- C
*→ ¬ D | D* - D
*→ ( A ) | atom*

## Dangling else problem

This is the problem of determining, in a series of **if **terminating with an **else**, to which **if** the **else** is referring. The ambiguous grammar is:

*stmt → if expr then stmt | if expr then stmt else stmt | other*

The *other *represents the various statements of the grammar that are not relevant to this issue.

A string that generates a conflict is: *if E₁ then if E₂ then S₁ else S₂ .*

Where the *Eᵢ* represents a boolean expression and the *Sᵢ *represents a generic statement of the programming language. The two parse trees generated by the string:

In all programming languages, the first parse tree is the correct one. The idea behind it is “Match each else with the closest unmatched then”. Following this rule, we want to prevent the situation of the second tree: the statement appearing between a **then **and an **else **must be “matched”, expressed in another way, the interior statement must not end with an unmatched (open) **then**. A matched statement is either an **if-then-else** containing matched statements, or it’s any other kind of unconditional statement ( the not considered statement external to the grammar).

So in the new grammar, we will have matched and unmatched statements. To clarify the situation, it’s possible to list all the allowed productions:

*if expr then matched_stmt**if expr then open_stmt**if expr then matched_stmt else matched_stmt**if expr then matched_stmt else open_stmt*

The productions **not** allowed are:

*if expr then open_stmt else matched_stmt**if expr then open_stmt else open_stmt*

So now we can create the rules:

*matched_stmt → if expr then matched_stmt else matched_stmt | other**open_stmt → if expr then matched_stmt |if expr then open_stmt | if expr then matched_stmt else open_stmt*

And the first rule of the grammar is the one that allows us to create both kinds of statements:

*stmt → open_stmt | matched_stmt*

It’s possible to simplify the *open_stmt *rule by observing that it’s possible to merge the first two productions, so the grammar becomes:

*stmt → open_stmt | matched_stmt**matched_stmt → if expr then matched_stmt else matched_stmt | other**open_stmt → if expr then stmt | if expr then matched_stmt else open_stmt*

That’s all; I hope this post has been helpful.