Greibach normal form

Summary

A context-free grammar is in Greibach normal form when the right side of each rule starts with a terminal letter followed only by nonterminals. Every context-free language without the empty word has a grammar in this form. With a special rule for the empty word, every context-free language has one. In such a grammar each derivation step produces exactly one letter of the word. This form turns a grammar into a pushdown automaton that reads one letter per move. It also shows that left recursion can always be removed.