This thesis presented an investigation of possible improvements in parsing times for typed feature structure grammars by means of indexing. A review of the existing research on improving TFSG parsing times revealed a lack of an integrated approach to indexing, as well as of a thorough analysis of the grammar rules in TFS-based parsers that can lead to the development of more efficient parsers. A theoretical framework to support a static analysis of grammar rules was set up, and an indexing strategy based on the static analysis was proposed.
The indexing method proposed here is suitable for several classes of unification-based grammars. The index keys are determined statically and are based on an a priori analysis of grammar rules. A major advantage of such indexing methods is the elimination of the lengthy training processes needed by statistical methods. Although a non-statistical method, indexing through the static analysis of grammar rules can be combined with methods based on statistical evidence of mother-daughter unifications.
The preliminary experimental evaluation carried out over several unification-based grammars demonstrates that indexing through static analysis is a promising optimization for typed feature structure grammars. The improvements in parsing time are comparable to those of statistically optimized parsers, while their set-up time is significantly lower.