We have seen

- top-down
- bottom-up

parsers. They both need a *stack*, a regime for updating the stack, and
*backtracking at choice points*.

In the limit both of these stack-oriented parsers uses EXPONENTIAL time to parse an input, i.e the upper-bound for the parse time for input symbols is given by some function , for some constants and ,

This behaviour comes to a large extent from the stack design. The stack can only represent the particular path, or parse-hypothesis, you have chosen, like a thread paid out behind you in a maze.

Better performance is achieved by using a more generous memory to
record everthing that has been discovered up to a particular point in
time. Instead of a *stack* we have some kind of multidimensional
*table*, with axes for string positions and for
categories. Instead of the limited window of the top of the stack we allow
access to any cell of the table.

Parsers making use of such a table are often called

They share a worst-case time for parsing which is *CUBIC*, rather than
exponential, ie. time to parse words can be guaranteed to be less than , for some constant .

We will look first at the simplest of all chartparsers