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 | ε