As mentioned in Section 2.3.3, the constraints reflected in a TFS can be expressed through descriptions. Without getting into explicit details about various description languages, this section presents the rationale behind the transformation of grammar rules into a representation usable in a programming environment (specifically, in Prolog). For this, the Attribute Logic Engine (ALE) will be used as the example parsing system.
ALE [Carpenter and Penn2001] is a phrase structure parsing system, supporting various formalisms, such as HPSG. Its grammar handling mechanism is built on foundations of the Prolog built-in DCG system, with the important difference of using descriptions of TFSs for representing categories, instead of Prolog terms.
There are two main components in the grammar handling mechanism: the lexicon and the grammar rules. The lexicon consists of lexical entries and lexical rules. Lexical rules are used to express the redundancies among lexical entries.
Of interest to the work presented in this thesis are the grammar rules. An example of a phrase rule in ALE is given in Figure 3.2.
 |
Using the descriptions presented in Figure 3.2 in an implementation would not be practical (not only for efficiency reasons, but also because types can be promoted, and Prolog variables, once instantiated, cannot be changed). Therefore, the grammar is first compiled into an internal, efficient, representation. The choice for the internal representation of each category in the grammar depends on the programming language that is chosen for the implementation. For the particular case of Prolog, the next section presents several encodings of TFSs.
Another reason for the off-line compilation of the grammar is the possibility of performing several optimizations. As it will be shown later in this thesis, an analysis of grammar rules carried out at compile-time results in a better indexing scheme, leading to faster parsing times.