Contributions

Indexing as a solution to improving parsing times for typed feature structure grammars is a research topic that has received little attention (and no direct attention for parsing) in the last few years in computational linguistics. This thesis is an argument in favour of the worthiness of deeper research in this area. The following contributions of this thesis prove the viability of such an argument:

Overview of existing work.

A review of the existing research on improving the retrieval component of TFSG parsing is conducted. The extensive investigation of literature on this topic identifies the strengths and weaknesses of existing methods; it reveals the lack of an 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.

Theoretical investigations.

A formalization of the static analysis of grammar rules for parsing is presented. A non-statistical approach to indexing TFS-based parsers is developed based on the static analysis. This approach does not preclude further statistical optimizations.

Preliminary evaluation.

The proposed indexing methods are integrated in a Prolog-implemented parser. A preliminary evaluation is conducted using a typed feature structure grammar.