Head-driven parsing for TAGs

This section shows how the head-corner parser might be applicable for lexicalized and constraint-based versions of TAGs. An auxiliary tree will correspond to a headed rule, i.e. chain-rule. Initial trees, on the other hand, will correspond to non-chain-rules.

Firstly, I show how initial and auxiliary trees are encoded in $\cal {R}$($\cal {L}$). Given these data-structures, I define the adjunction operation. Furthermore I discuss how the unification of bottom and top feature structures comes about at the end of a derivation. In order to prevent spurious ambiguities I then define `normal form' derivations. This allows the parser to implement the unification of bottom and top feature structures in an incremental manner.

An important reduction of the search space is possible, because it is not possible during a TAG derivation to change the order of words, once this order has been established. Thus, TAG derivations exhibit a certain monotonicity with respect to the order of the words. Therefore, an important reduction of the search space is obtained by checking at various moments during the parse whether the structure obtained yields a subsequence of the string to be parsed.

Although it is possible to present the head-corner parser for TAG simply as an instantiation of the algorithm presented in the previous section, it is somewhat more easier to understand the parser, if we change various parts of the head-corner parser directly, to exhibit more clearly what is going on.