In computer science, to say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form:
or
where A is a nonterminal symbol, α is a terminal symbol, X is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and λ is the null string. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their In Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr In Computer science, terminal and nonterminal symbols are those symbols that are used to construct production rules in a Formal grammar. In Computer science, terminal and nonterminal symbols are those symbols that are used to construct production rules in a Formal grammar.
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 null string cannot be so transformed. ) This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton. In Formal language theory, a context-free language is a language generated by some Context-free grammar. In Automata theory, a pushdown automaton (PDA is a finite automaton that can make use of a stack containing data
Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general Parse tree structures and then considering whether the known fundamental structures
Greibach normal form is named after Sheila Greibach. Sheila Greibach (1939- is a researcher in Formal languages Automata, Compiler theory in particular and Computer science in general
See also
References
- John E. In Computer science, Backus–Naur Form ( BNF) is a Metasyntax used to express Context-free grammars that is a formal way to describe Formal In Computer science, a Formal grammar is said to be in Chomsky normal form if all of its production rules are of the form A\rightarrow\ In Formal language theory, a grammar is in Kuroda normal form Iff all production rules are of the form AB &rarr CD or Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. (See chapter 4. )