edited by
1,491 views
2 votes
2 votes

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)$.
  1. $\text{1 & 2}$
  2. $\text{2 & 3}$
  3. $\text{1 & 3}$
  4. $\text{1, 2 & 3}$
edited by

2 Answers

1 votes
1 votes

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.

Related questions

0 votes
0 votes
1 answer
1
Mizuki asked Aug 31, 2018
445 views
For a grammar to be LR(k), it should have a PDA? Like a DPDA or just PDA in general?
8 votes
8 votes
2 answers
2
0 votes
0 votes
1 answer
4
Neeraj Mehta asked Dec 23, 2017
320 views
S- AaA- AbA- cWhich of the following item is present in LR(1) item with S'->. S, $a) A->. Ab,$b) A->. Ab,ac) A->. Ab,a/bd) None