6.5 Top Down Parsing and Recognition

Now we discuss top-down parsing, and we will take care to remove the implementational inefficiency of our previous implementation: we won't use append/3, but will work with difference lists instead. As we shall see, this makes a huge difference to the performance. Whereas recognize_bottomup/1 is unusable for anything except very small sentences and grammars, our next parser and recognizer will easily handle examples that recognize_bottomup/1 finds difficult.

However we won't remove the deeper algorithmic inefficiency. The top-down algorithms are still naive in that they double work (as we have argued for our bottom-up recognizer in Section 6.4.2).

• 6.5.1 The General Idea

• 6.5.2 With Depth-First Search

• 6.5.3 With Breadth-First Search