Eliminating $\varepsilon$-productions

An $\varepsilon$-production is a rule of the form $A\; \rightarrow\; \varepsilon$ for some non-terminal $A$ (this is also called an erasing rule for $A$). Usually the main motivation for removing this type of rule is that we need to apply some algorithm which only works for grammars with no $\varepsilon$-productions (such as the elimination of indirect left-recursion).

A non-terminal is said to be nullable if it can derive the empty string in one or more steps; that is, if $B$ is nullable, then there exists some derivation $B \; \rightarrow^*\; \varepsilon$. We need this concept, since the elimination of an erasing rule for a non-terminal will have a knock-on effect on every other non-terminal that can derive it.

In order to eliminate $\varepsilon$-productions from a grammar we perform the following:

For every nullable non-terminal $B$:

• For every production rule of the form: $C \; \rightarrow\; \alpha B \beta$ add in a new rule of the form $C \; \rightarrow\; \alpha \beta$, where $C$ is any non-terminal, and $\alpha$ and $\beta$ are any sequences of terminals or non-terminals.

ie. since we've removed the facility which allows $B$ to go to $\varepsilon$, we must compensate for this everywhere $B$ is used on the r.h.s of a production rule..