An Example

Figure 4.1 presents an intuitive example for a very simple context-free grammar:
$S~\rightarrow~VP~NP$
$VP~\rightarrow~V~NP$
$NP~\rightarrow~N$
$NP~\rightarrow~ART~N$.

For the input string ``Ducks eat flies'', when looking for a matching $NP$ in the chart to complete a rule such as $VP~\rightarrow~V~NP$, the non-indexed parser first attempts to match the daughter category $NP$ with edges $V$ and $N$ stored in the chart. Only after these attempts fail is the right match found. The indexed parser never attempts the matches $NP = N$ and $NP = V$, since its searches will always be limited to a list containing compatible categories.

Figure 4.1: A simple example of indexed chart parsing. In this example, an entry $(P,j)$ found in the chart location $chart[i]$ represents an edge labeled with the part of speech $P$ and spanning from position $i$ to position $j$ in the input string.

This example illustrates a ``perfect index'' (as the one described in Section 7.4.2). In a ``perfect'' index, all attempted unification between a daughter and all edges in the set selected by the daughter's key would be successful. Unfortunately, TFSs contain a large amount of information, not all of which is accessible before parsing, therefore a ``perfect'' index is unlikely for TFSGs. However, as it will be shown in the preliminary evaluation presented in Chapter 7, even if not all possible failed unifications are avoided, indexing can still improve parsing times.