Greibach normal form

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computer science and 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 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 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 \to \alpha A_1 A_2 \cdots A_n

or

S \to \varepsilon

where A is a nonterminal symbol, \alpha is a terminal symbol, A_1 A_2 \ldots A_n 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 does not have left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form.[1] 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(n4) in the general case and O(n3) if no derivation of the original grammar consists of a single nonterminal symbol, where n is the size of the original grammar.[2] 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.

See also[edit]

Notes[edit]

  1. ^ Greibach, Sheila (January 1965). "A New Normal-Form Theorem for Context-Free Phrase Structure Grammars". Journal of the ACM 12 (1). 
  2. ^ Blum, Norbert; Koch, Robert (1999). "Greibach Normal Form Transformation Revisited". Information and Computation 150 (1): 112–118. CiteSeerX: 10.1.1.47.460. 

References[edit]

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