Abstract: 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
» Algorithmic Problems).