Abstract:How good is this parser? Well, it's pretty easy to understand --- but performance-wise it's awful. Our English grammar is pretty basic --- but the query
recognize_bottomup([jules,believed,the,robber,who,shot,marsellus,fell]).will make Prolog hesitate, and
recognize_bottomup([jules,believed,the,robber,who,shot,the,robber,who,shot,marsellus,fell]).is painfully slow. In fact, this parser is so bad, it's useful --- it acts as a grim warning of how badly things can be done. We'll see in later lectures that we can do a
lot better. Moreover, it's useful to try and understand
why it is so awful. For it is bad in two quite distinct ways: at the level of
implementation and at the level of
↗algorithm .