Greibach normal form
Encyclopedia
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 recursion
s.
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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
theory, a context-free grammar
Context-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
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
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
.
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 recursion
Left recursion
In computer science, left recursion is a special case of recursion.In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s ‘alternatives’ either immediately or through some other non-terminal definitions rewrites to r again.- Definition :"A...
s.
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
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
can be accepted by a non-deterministic pushdown automaton
Pushdown automaton
In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...
.
Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser
Top-down parsing
Top-down parsing is a type of parsing strategy where in one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar...
will halt at depth n.