Indexing Timeline

Indexing can be applied at several moments during parsing. While Sections 4.4 and 4.5 presents and comments on several approaches to indexing, this section outlines a general strategy for indexed parsing, with respect to what actions should be taken at each stage during parsing. This outline is also valid for other formalisms, such as CFGs, with appropriate simplification.

Three main stages can be identified during parsing. The first stage describes indexing actions that can be taken off-line (along with several other actions performed during compile time, as described in Section 3.2.1). The second and third stages refers to action performed at run time.

1. In the off-line phase, an analysis of grammar rules can be performed. The actual content of mothers and daughters may not be accessible, due to variables that will be instantiated during parsing. The ideal case for indexing would be having no variables - resulting in a CFG-like grammar, in which all indexing can be done at compile time. However, various sources of information, such as the type signature, appropriateness specifications, or general descriptions of mothers and daughters, can be analyzed and an appropriate indexing scheme can be specified. This phase of indexing may include determining:
   1. which daughters in which rules are sure not to unify with a specific mother, and
   2. what information can be extracted from categories during parsing that can constitute indexing keys.
   It is desirable to perform as much analysis as possible at this off-line stage, since the cost of any action taken during run time prolongs the parsing time.
2. During parsing, after a rule has been completed, all variables in a mother are instantiated. This offers the possibility of further investigating the mother's content and extracting supplemental information from the mother that contributes to the indexing keys. However, the choice of such investigative actions must be carefully studied, since it might burden the parsing process.
3. While completing a rule, for each daughter a matching edge is searched in the chart. At this moment, the daughter's Active External Variables are instantiated, therefore the entire content of the daughter can be accessed, and the information identified in stage (1b) can be extracted. Also in this stage, the unification between daughters and edges takes place.