consideration.
Exhaustive search parsing has serious flaws. The most obvious one is its
tediousness; it is not to be used where efficient parsing is required. But even
when efficiency is a secondary issue, there is a more pertinent objection. While
the method always parses a w ∈ L(G), it is possible that it never terminates for
strings not in L(G). This is certainly the case in the previous example; with w =
abb, the method will go on producing trial sentential forms indefinitely unless
we build into it some way of stopping.
The problem of nontermination of exhaustive search parsing is relatively
easy to overcome if we restrict the form that the grammar can have. If we
examine Example 5.7, we see that the difficulty comes from the productions S →
λ; this production can be used to decrease the length of successive sentential
forms, so that we cannot tell easily when to stop. If we do not have any such
productions, then we have many fewer difficulties. In fact, there are two types of
productions we want to rule out, those of the form A → λ as well as those of the
form A → B. As we will see in the next chapter, this restriction does not affect
the power of the resulting grammars in any significant way.
Example 5.8
The grammar
satisfies the given requirements. It generates the language in Example 5.7
without the empty string.
Given any w ∈ {a,b} + , the exhaustive search parsing method will always
terminate in no more than |w| rounds. This is clear because the length of the
sentential form grows by at least one symbol in each round. After |w| rounds we
have either produced a parsing or we know that
.
The idea in this example can be generalized and made into a theorem for
context-free languages in general.
Theorem 5.2
Exhaustive search parsing has serious flaws. The most obvious one is its
tediousness; it is not to be used where efficient parsing is required. But even
when efficiency is a secondary issue, there is a more pertinent objection. While
the method always parses a w ∈ L(G), it is possible that it never terminates for
strings not in L(G). This is certainly the case in the previous example; with w =
abb, the method will go on producing trial sentential forms indefinitely unless
we build into it some way of stopping.
The problem of nontermination of exhaustive search parsing is relatively
easy to overcome if we restrict the form that the grammar can have. If we
examine Example 5.7, we see that the difficulty comes from the productions S →
λ; this production can be used to decrease the length of successive sentential
forms, so that we cannot tell easily when to stop. If we do not have any such
productions, then we have many fewer difficulties. In fact, there are two types of
productions we want to rule out, those of the form A → λ as well as those of the
form A → B. As we will see in the next chapter, this restriction does not affect
the power of the resulting grammars in any significant way.
Example 5.8
The grammar
satisfies the given requirements. It generates the language in Example 5.7
without the empty string.
Given any w ∈ {a,b} + , the exhaustive search parsing method will always
terminate in no more than |w| rounds. This is clear because the length of the
sentential form grows by at least one symbol in each round. After |w| rounds we
have either produced a parsing or we know that
.
The idea in this example can be generalized and made into a theorem for
context-free languages in general.
Theorem 5.2