Eliminating Left Factor in Compiler
In this class, We discuss Eliminating Left Factor in Compiler.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of context-free grammar. Click Here.
We take an example and understand left factoring.
Example:
Eliminating Left Factoring: is a process of factoring out common prefixes.
A – αβ1 | αβ2
The above grammar had confusion.
After finding the input symbol alpha, we had two options.
We can go with β1 or β2.
Both the productions have a common prefix α.
The above grammar we call non-deterministic grammar.
Eliminating left factoring from the grammar is also called eliminating non-determinism.
How to eliminate left factoring?
Take out the common prefix and add a new production shown below.
A – αA’
A’ – β1 | β2
Example:
The below example grammar from dangling else example.
STMT – if (E) then STMT | if (E) then STMT else STMT
After eliminating left factoring.
STMT – if (E) then STMT S’
S’ – else STMT | ε