Typed Feature Structures can be employed in various areas of Computational Linguistics, or Natural Language Processing, such as parsing, question-answering, information retrieval, etc. Since the focus of this thesis is on parsing with Typed Feature Structures, this chapter begins with a short overview of HPSG, a representative unification-based grammar formalism using typed feature structures. HPSG is also the formalism of the grammar used in the experimental evaluation in Chapter 7 (although the indexing methods introduced in this thesis are not limited to parsing with HPSG). After introducing the HPSG formalism, this chapter concludes with an extensive presentation of various implementational aspects of Typed Feature Structure Grammars, presentation that also introduces a new classification of the instances of variables used in TFSGs.
Unification-based grammars (UBGs), as suggested by their name, are grammar formalisms where unification is the only information-combining operation [Shieber1986]. More specifically, entities are represented by feature structures, and UBGs allow information carried by such entities to be combined only through unification.
Some particular properties differentiate UBGs from simpler formalisms, such as CFGs. According to [Shieber1986], UBGs are:
In the following section, the HPSG formalism is introduced. It is not the purpose of this work to extensively present unification-based formalisms; wide-coverage surveys of UBGs can be found in [Shieber1986] and [Brown and Miller1996].
This chapter also introduces a new classification of the instances of variables used in descriptions, based on what type of structure sharing they create. The use of variables to share structure is a powerful characteristic of TFSGs.