context-free grammar is tedious. We therefore deal with this matter very briefly.
Nevertheless, Greibach normal form has many theoretical and practical
consequences.
Definition 6.5
A context-free grammar is said to be in Greibach normal form if all productions
have the form
A → ax,
where a ∈ T and x ∈ V *
If we compare this with Definition 5.4, we see that the form A → ax is
common to both Greibach normal form and s-grammars, but Greibach normal
form does not carry the restriction that the pair (A, a) occur at most once. This
additional freedom gives Greibach normal form a generality not possessed by sgrammars.
If a grammar is not in Greibach normal form, we may be able to rewrite it in
this form with some of the techniques encountered above. Here are two simple
examples.
Example 6.9
The grammar
is not in Greibach normal form. However, using the substitution given by
Theorem 6.1, we immediately get the equivalent grammar
Nevertheless, Greibach normal form has many theoretical and practical
consequences.
Definition 6.5
A context-free grammar is said to be in Greibach normal form if all productions
have the form
A → ax,
where a ∈ T and x ∈ V *
If we compare this with Definition 5.4, we see that the form A → ax is
common to both Greibach normal form and s-grammars, but Greibach normal
form does not carry the restriction that the pair (A, a) occur at most once. This
additional freedom gives Greibach normal form a generality not possessed by sgrammars.
If a grammar is not in Greibach normal form, we may be able to rewrite it in
this form with some of the techniques encountered above. Here are two simple
examples.
Example 6.9
The grammar
is not in Greibach normal form. However, using the substitution given by
Theorem 6.1, we immediately get the equivalent grammar