Preprocessing steps for predictive parsing are,
- Removing the left recursion from the grammar
- Performing left factoring on the resultant grammar
- Removing ambiguity from the grammar
Removing the left recursion from the Grammar
Given
grammar,
B → B
and B
B → B
or
B → (B)
| true | false
Let the given grammar be,
B → B
and B | true
B → B
or B | false
B →(B)
Therefore, the given grammar in left recursive, removing
left recursion from the grammar
Performing Left Factoring on the resultant grammar
For the
grammar,
A → Aα
| B
The
productions are
A
→ βA'
A' → A'
| ε
Therefore we have,
B → true B’
B’ → and B B’| ε
B’ → false B’
B’ → or BB’ | ε
B → (B)
i.e., B → true B’ | and d BB’ | false B’ | or BB’ | (B) | ε
The above
grammar contains repetitions of the symbol, therefore, performing left
factoring on it.
Removing Ambiguity from the Grammar
We know that for the grammar
B → β𝜆1
| β𝜆2 | β𝜆3 …….. | β𝜆v | α
We have the
productions
B → 𝜆1
| 𝜆2 | 𝜆3 ……… 𝜆v
Therefore
B → B1B0 |
(B) | ε
B0 → true |
and B | false | or B
