Greibach normal form

Imagine a rule that every sentence you speak must begin with an actual word, never with a placeholder you will fill in later. That way, every time you open your mouth, something concrete comes out and the listener makes real progress understanding you. Greibach normal form (GNF) imposes this discipline on a grammar: every rule must start by producing a real terminal symbol, so each derivation step consumes one symbol of output.

A grammar is in GNF if every rule has the form A -> a alpha, where a is a single terminal and alpha is a (possibly empty) string of variables only. So the right-hand side always begins with one terminal, followed by zero or more nonterminals — never another terminal in the middle, never a leading variable. Every context-free language without the empty string has a grammar in GNF; the conversion typically goes through CNF first, then removes left recursion and substitutes rules so that every right-hand side leads with a terminal. Because each step of a leftmost derivation now outputs exactly one terminal, a string of length n is derived in exactly n steps.

GNF matters as a bridge to top-down parsing and to a clean pushdown-automaton construction. The 'one terminal per step' property guarantees a terminal is consumed at each move, which prevents the infinite spinning that left recursion causes and lets a PDA read the next input symbol while expanding the leftmost variable — that is essentially predictive, top-down parsing. The honest caveat: converting to GNF can blow up the grammar substantially (the removal of left recursion and the rule substitutions can multiply rules by a large factor, often worse than CNF) and, like all normal-form conversions, it rewrites the parse trees, so attached meaning must be reattached.