| << Prev | - Up - | Next >> |
The algorithm needlessly repeats work.
There is, however, a deeper problem. What we have just discussed is a naive bottom-up recognizer --- but its naivete has nothing to do with its implementation.It has an inefficiency you will find in many different kinds of parsers/recognizers namely The algorithm needlessly repeats work.
Consider the sentence ``The robber knew Vincent shot Marsellus'' As we have already mentioned, this sentence is locally ambiguous. In particular, the first part of the string, ``The robber knew Vincent'' is a sentence. Now, our naive bottom-up algorithm will find that this string is a sentence --- and then discover that there are more words in the input. Hence, in this case, s is not the right analysis. Thus our parser will backtrack and it will undo and forget all the useful work it has done. For example, while showing that ``The robber knew Vincent'' is a sentence, the parser has to show that ``The robber'' is an np. Great! This is dead right! And we need to know this to get the correct analysis! But then, when it backtracks, it undoes all this work. So when it finally hits on the right way of analyzing ``The robber knew Vincent shot Marsellus'' , it will once again demonstrate that ``The robber'' is an NP. If lots of backtracking is going on, it may end up showing this simple fact over and over and over again.
It is for this reason that we call the algorithm described above `naive'. The poor implementation is easily corrected --- our top-down parser won't have it --- but this deeper problem is harder to solve.
| << Prev | - Up - | Next >> |