Chart Parsers

We have seen

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 $n$ input symbols is given by some function $\alpha c^n$, for some constants $c$ and $\alpha$,

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

\begin{displaymath}\left.\parbox[c]{1in}{TABULAR  or CHART} \right\} \mbox{parsers}\end{displaymath}

They share a worst-case time for parsing which is CUBIC, rather than exponential, ie. time to parse $n$ words can be guaranteed to be less than $\alpha n^3$, for some constant $\alpha$.

We will look first at the simplest of all chartparsers

Martin Emms 2019-03-21