Developing efficient parsers is one of the long-standing goals of research in natural language processing. A particular area of grammar development in strong need of improvements in parsing times is that of typed feature structure grammars (TFSGs). With respect to parsing times, much simpler grammar formalisms such as context-free grammars (CFGs) also face the problem of slow parsing time when the size of the grammar increases significantly. While TFSGs are small compared to large-scale CFGs (in terms of the number of rules), the problematic parsing times are generated by the complex structure required to represent the categories in the grammar rules. For example, in HPSGs [Pollard and Sag1994] covering the English language, one category could incorporate thousands of feature values (while in CFGs, the categories are atomic).
For TFSG chart parsers, one of the most time-consuming operations is the retrieval of categories from the chart. This is a look-up process: the retrieved category should match a daughter description from the grammar. The size of the typed feature structures [Carpenter1992], combined with their complex structure, results in slow unification (matching) times, which leads to slow parsing times. Therefore, while retrieving categories from the chart, failing unifications should be avoided. Using indexing methods to search for categories in the chart is also motivated by the successful use of indexing in the retrieval/updating process in databases1.1.