Brute Force Parsing

Question

Which of the following can be said about the Exhaustive search parsing or brute force parsing ?

1. It is inefficient as the time taken is proportional to the length of the string.
2. The parser always terminates on the strings in the $L(G)$.
3. The parser always terminates on the strings not in $L(G)$.

• A. $\text{1 & 2}$
• B. $\text{2 & 3}$
• C. $\text{1 & 3}$
• D. $\text{1, 2 & 3}$

Answer 1

A) First statement is true as Exhaustive search parsing may grow exponentially with the length of the string making cost of method prohibitive.

Second is true as when it (parsing) gives a derivation of w i.e. w∈L(G), then it stops.

Third is false because when w∉L(G), the method will go on producing trial sentential forms indefinitely unless we stop it somehow.. Hence it never terminates if w cannot be generated by the grammar. It is one of the major flaw in this parsing technique which makes it inefficient.

Answer 2

A, as string not in L may not terminate.