Greibach Normal Form Conversion

A context-free grammar is in Greibach normal form (GNF) when every production has the form A → a A₁ A₂ … Aₖ: one leading terminal followed by zero or more nonterminals. If the language contains the empty string, many definitions allow a restricted S → ε production.

What the normal form guarantees

In a leftmost derivation, each GNF step emits exactly one terminal. A string of length n therefore has a leftmost derivation with n terminal-producing steps, apart from an allowed epsilon case. This property is useful in formal proofs and parsing constructions.

GNF does not require the grammar to be unambiguous. Conversion preserves the language but may change derivation structure and can increase grammar size substantially.

Prepare the grammar

1. Add a fresh start symbol if the original start symbol occurs on a right-hand side.
2. Remove useless symbols that cannot generate terminals or cannot be reached.
3. Eliminate epsilon productions while preserving an allowed start-symbol epsilon case.
4. Eliminate unit productions such as A → B.
5. Replace terminals that occur after the leading position with helper nonterminals when necessary.

Perform these steps with a tested algorithm. Removing a nullable production requires adding the appropriate alternatives where that nonterminal appears, and careless expansion can either lose strings or introduce new ones.

Order and substitute leading nonterminals

Order the nonterminals A₁, A₂, …, Aₙ. Process them so that a production for Aᵢ does not begin with an earlier nonterminal Aⱼ. When it does, substitute the alternatives of Aⱼ into that leading position.

Aᵢ → Aⱼ α
Aⱼ → β₁ | β₂

becomes

Aᵢ → β₁ α | β₂ α

Continue until leading symbols are terminals or direct left recursion appears. After ordered substitution and recursion removal, substitute remaining leading nonterminals until every alternative begins with a terminal.

Remove direct left recursion

For productions A → Aα₁ | … | Aαₘ | β₁ | … | βₙ, where the β alternatives do not begin with A, introduce a helper nonterminal that represents repetitions of α. The familiar left-recursion transformation must then be reconciled with the strict GNF shape through further substitutions.

Indirect left recursion is removed by the ordering step: substitute earlier nonterminals before handling direct recursion for the current one. Cycles and nullable symbols make this phase especially error-prone.

Verify syntax and language behavior

Check every production mechanically. The first symbol must be a terminal, and every remaining symbol must be a nonterminal. Then compare generated strings up to a useful bound, including the shortest strings and the empty string policy.

For classroom grammars, show each intermediate grammar rather than jumping to the final answer. The intermediate removal of epsilon, unit and recursive productions is where most language-changing mistakes occur.