Building the Index

The indexing method introduced in this section follows the general strategy outlined in Section 4.3. Each mother is inserted as an edge in the indexed chart only in positions specified by that mother's indexing scheme (which is the list of matching daughters' index keys). When completing a rule, a matching edge is searched for each daughter only in the chart entry labeled with an index key compatible with that daughter's index key.

The structure of the index can be determined at compile-time. The first step is to create a list containing the descriptions of all rules' mothers in the grammar. Then, for each mother description, a list $L(Mother)=\{(R_i,D_j)\vert \textrm{ daughters that can match }Mother\}$ is created, where each element of the list $L$ represents the rule number $R_i$ and daughter position $D_j$ inside rule $R_i$ ( $1 \leq j \leq arity(R_i)$) of a category that can match with $Mother$.

For UBGs it is not possible to determine the exact list of matches between daughters and mothers, since there are sometimes infinitely many possible variants of daughters in a given signature. However, it is possible to rule out MGSats of daughters that are incompatible (with respect to unification) with a certain $Mother$ before parsing. For the 17 mothers in the grammar used for the experiments presented in Chapter 7, the number of matching daughters statically determined before parsing ranges from 30 (the total number of daughters in the grammar) to 2. This compromise pays off with its simplicity, which is reflected in the time spent managing the index.

During run-time, each time an edge (representing a rule's mother) is added to the chart, its category is inserted into the corresponding hash entries associated with the positions $(R_i,D_j)$ from the list $L(Mother)$ (the number of entries where $Mother$ is inserted is equal to the cardinality of $L(Mother)$). The entry associated to the key $(R_i,D_j)$ will contain only categories (based on $MGSat(Mother)$) that can possibly unify with the daughter at position $(R_i,D_j)$ in the grammar.

It should be mentioned at this point that only daughters $D_i$ with $i \geq 2$ are searched for in the chart (and consequently, indexed). As described in Section 4.1.3, whenever an edge is added to the chart, all rules are visited in a failure-driven loop. The rules of which the first (leftmost) daughter unifies with the edge are then traversed left to right, starting with the second daughter.