| << Prev | - Up - |
We can perform non-naive parsing by using charts.
But the problem can be solved. We can perform non-naive parsing by using charts. In their simplest form, charts are essentially a record of what pieces of information we found and where (for example, that the initial string ``The robber'' is an np). Sophisticated parsing algorithms use the chart as a look-up table: they check whether they have already produced an analysis of a chunk of input. This saves them having to repeat needless work.
And the use of charts really does pay off: naive algorithms are exponential in the size of their input --- which, roughly speaking, means they may take an impossibly long time to run no matter how good the implementation is. The use of charts, however, turns context free parsing into a polynomial problem. That is, roughly speaking, it turns the problem of finding a parse into a problem that can be solved in reasonable time, for any CFG grammar.
We will study the idea of chart parsing later in the course: it is an idea of fundamental importance. But note well: chart parsing is not an idea we need to study instead of the various naive parsing strategies --- its something we need to study in addition to them. The various naive strategies (bottom-up, top-down, left corner,...) are importantly different, and we need to understand them. What is nice about chart parsing is that it is a general idea that can remove the naivete from all these approaches.
| << Prev | - Up - |