| - Up - | Next >> |
This recognizer is badly implemented.
By this stage of your Prolog career, it should be quite clear to you why this recognizer is badly implemented. We made heavy use of append/3 to subdivide lists into the required pattern. This is very inefficient. If you examine a trace, you will see the the program spends most of its time trying out different ways of putting lists together. The time it devotes to the key recognition steps is comparatively small.
It's worth emphasizing that this implementation inefficiency has nothing to do with the basic idea of bottom-up recognition/parsing. For a start, there are many nice Prolog implementations of fairly simple bottom-up parsers --- in particular, what are known as shift-reduce parsers --- that are much better than this. Moreover, soon we will be discussing naive top-down parsing/recognition. If this is implemented using append/3, the result is just as inefficient as what we have just seen. But we are going to take care to avoid this implementation inefficiency there. We'll be using difference lists instead, and as we'll see, the result is a lot faster.
| - Up - | Next >> |