Greibach normal form

In computer science, to say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form::$A\; o\; alpha\; X$ or:$S\; o\; lambda$where "A" is a nonterminal symbol, α is a terminal symbol, "X" is a (possibly empty) sequence of nonterminal symbols not including the start symbol, "S" is the start symbol, and "λ" is the null string.

Observe that the grammar must be without left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. (Some definitions do not consider the second form of rule to be permitted, in which case a context-free grammar that can generate the null string cannot be so transformed.) This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton.

Given a grammar in GNF and a derivable string in the grammar with length "n", any top-down parser will halt at depth "n".

Greibach normal form is named after Sheila Greibach.

ee also

*Backus-Naur form
*Chomsky normal form
*Kuroda normal form

References

* John E. Hopcroft and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. "(See chapter 4.)"