Greibach normal form
In formal language theory, a context-free grammar is in Greibach normal form if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word 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:
or
where is a nonterminal symbol, is a terminal symbol,
is a sequence of nonterminal symbols not including the start symbol, is the start symbol, and ε is the empty word.
Observe that the grammar does not have left recursions.
Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. 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 in the general case and O if no derivation of the original grammar consists of a single nonterminal symbol, where is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a real-time 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, any top-down parser will halt at depth.
