Greibach normal form

In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some non-terminals. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.

More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:

:$A\; \backslash to\; a\; A\_1\; A\_2\; \backslash cdots\; A\_n$

where $A$ is a nonterminal symbol, $a$ is a terminal symbol, and

$A\_1\; A\_2\; \backslash ldots\; A\_n$ is a (possibly empty) sequence of nonterminal symbols.

Observe that the grammar does not have left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form.{{cite journal | last=Greibach | first=Sheila | title=A New Normal-Form Theorem for Context-Free Phrase Structure Grammars |date=January 1965| journal=Journal of the ACM | volume=12| issue=1 | pages=42–52 | doi = 10.1145/321250.321254| s2cid=12991430 | doi-access=free }} Various constructions exist. Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word. For one such construction the size of the constructed grammar is O({{var|n}}⁴) in the general case and O({{var|n}}³) if no derivation of the original grammar consists of a single nonterminal symbol, where {{var|n}} is the size of the original grammar.{{cite journal | first1 = Norbert | last1 = Blum | first2 = Robert | last2 = Koch | title = Greibach Normal Form Transformation Revisited | journal = Information and Computation | volume = 150 | issue = 1 | year = 1999 | pages = 112–118 | citeseerx = 10.1.1.47.460 | doi=10.1006/inco.1998.2772| s2cid = 10302796 }} This conversion can be used to prove that every context-free language can be accepted by a real-time (non-deterministic) pushdown automaton, i.e., the automaton reads a letter from its input every step.

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