Natural language parsing is still inefficient. There are two important reasons for this. Natural language contains many ambiguities which lead to a large search space for parsers. On the other hand the complex structure of natural language is problematic; natural language parsers usually are based on grammars of which the formal power goes beyond the context-free grammars. Both observations imply that efficient algorithms that have been developed for e.g. programming languages, such as LR(1), can not be used as such.
To obtain a parsing algorithm for a class of grammars beyond the context-free grammars, the usual strategy is to generalize an efficient algorithm for context-free grammars to this more powerful class. The problem with this approach is that in the course of the generalization the efficiency may disappear, both in terms of the worst-case and average-case performance.
It might be fruitful therefore to investigate processing techniques which can be motivated from a linguistic point of view. In such a strategy algorithms are developed which are based on the typical properties of the grammars that are actually used. Even if such techniques have a worst-case performance that is comparable to the performance of conventional strategies, it is worthwhile to consider these techniques if they improve upon the average case behavior.
As an example consider head-driven parsing for unification grammars. In such unification grammars the information a constituent contains is usually percolated upward from its head. For example, the agreement features of a noun phrase are determined by the head of that noun phrase, the noun. Furthermore a head of a constituent determines what kinds of other constituent it governs. For example, the head of a verb phrase, the verb, determines what kind of objects the verb phrase contains. If the verb is a bi-transitive then the verb phrase might contain two noun phrases. In head-corner parsing this flow of information is mimicked by the parser. Rather than parsing from left to right, the head-corner parser parses from the head outward in both directions. As the parser starts off from the head the information about the constituents to be expected left and right of the head is available in time to reduce search space.
Head-corner parsing has first been suggested as an interesting approach to natural language parsing in [2]. Some results have been obtained both for context-free grammars [4,5], unification grammars [1] and non-concatenative grammatical formalisms [6,7].
This paper describes a head-corner parser for Tree Adjoining Grammars. In order to define a head-driven parser for TAGs, it is necessary to define a version of TAGs in which all elementary trees are `headed' trees. In the next section I define such headed TAGs.
In section 3 I present the head-corner parser for headed LTAGs. The head-corner parser will be presented as a definite clause specification. Such a definite clause program provides an abstract and declarative specification of the parser. It is possible to implement parsers on the basis of this specification.