Suppose that G = (V, T, S, P) is a context-free grammar that does not have any
rules of the form
A → λ,
or
A → B,
where A, B ∈ V. Then the exhaustive search parsing method can be made into an
algorithm which, for any w ∈ Σ * , either produces a parsing of w or tells us that
no parsing is possible.
Proof: For each sentential form, consider both its length and the number of
terminal symbols. Each step in the derivation increases at least one of these.
Since neither the length of a sentential form nor the number of terminal symbols
can exceed |w|, a derivation cannot involve more than 2|w| rounds, at which time
we either have a successful parsing or w cannot be generated by the grammar.
While the exhaustive search method gives a theoretical guarantee that
parsing can always be done, its practical usefulness is limited because the
number of sentential forms generated by it may be excessively large. Exactly
how many sentential forms are generated differs from case to case; no precise
general result can be established, but we can put some rough upper bounds on it.
If we restrict ourselves to leftmost derivations, we can have no more than |P|
sentential forms after one round, no more than |P| 2 sentential forms after the
second round, and so on. In the proof of Theorem 5.2, we observed that parsing
cannot involve more than 2|w| rounds; therefore, the total number of sentential
forms cannot exceed
This indicates that the work for exhaustive search parsing may grow
exponentially with the length of the string, making the cost of the method
prohibitive. Of course, Equation (5.2) is only a bound, and often the number of
sentential forms is much smaller. Nevertheless, practical observation shows that
exhaustive search parsing is very inefficient in most cases.
rules of the form
A → λ,
or
A → B,
where A, B ∈ V. Then the exhaustive search parsing method can be made into an
algorithm which, for any w ∈ Σ * , either produces a parsing of w or tells us that
no parsing is possible.
Proof: For each sentential form, consider both its length and the number of
terminal symbols. Each step in the derivation increases at least one of these.
Since neither the length of a sentential form nor the number of terminal symbols
can exceed |w|, a derivation cannot involve more than 2|w| rounds, at which time
we either have a successful parsing or w cannot be generated by the grammar.
While the exhaustive search method gives a theoretical guarantee that
parsing can always be done, its practical usefulness is limited because the
number of sentential forms generated by it may be excessively large. Exactly
how many sentential forms are generated differs from case to case; no precise
general result can be established, but we can put some rough upper bounds on it.
If we restrict ourselves to leftmost derivations, we can have no more than |P|
sentential forms after one round, no more than |P| 2 sentential forms after the
second round, and so on. In the proof of Theorem 5.2, we observed that parsing
cannot involve more than 2|w| rounds; therefore, the total number of sentential
forms cannot exceed
This indicates that the work for exhaustive search parsing may grow
exponentially with the length of the string, making the cost of the method
prohibitive. Of course, Equation (5.2) is only a bound, and often the number of
sentential forms is much smaller. Nevertheless, practical observation shows that
exhaustive search parsing is very inefficient in most cases.