In computer science and formal language theory, a context-free grammar is in Greibach normal form if the right-hand sides of all productions 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 (epsilon, ε) to be a member of the described language. The normal form bears the name of Sheila Greibach.
More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:
or
where A is a nonterminal symbol, α is a terminal symbol, is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and ε is the empty word.
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 empty word cannot be so transformed.) In particular, there is a construction ensuring that the resulting normal form grammar is of size at most O(n4), where n is the size of the original grammar. This conversion 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.
Famous quotes containing the words normal and/or form:
“Everyone in the full enjoyment of all the blessings of his life, in his normal condition, feels some individual responsibility for the poverty of others. When the sympathies are not blunted by any false philosophy, one feels reproached by one’s own abundance.”
—Elizabeth Cady Stanton (1815–1902)
“Which form of proverb do you prefer—”Better late than never,” or “Better never than late”?”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)