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:
“Love brings to light the lofty and hidden characteristics of the lover—what is rare and exceptional in him: to that extent it can easily be deceptive with respect to what is normal in him.”
—Friedrich Nietzsche (1844–1900)
“What is a novel if not a conviction of our fellow-men’s existence strong enough to take upon itself a form of imagined life clearer than reality and whose accumulated verisimilitude of selected episodes puts to shame the pride of documentary history?”
—Joseph Conrad (1857–1924)