Overview

This chapter is organized as follows. Firstly I discuss the proposals for more powerful string operations, as presented by [67], [38], [72], [106] and [1]. Then I define two restrictions on possible string combinations for constraint-based grammars, based on [107]. The combination of strings is restricted to be linear (non-copying) and non-erasing). Next, I define, as an example of such a grammar, a simple grammar for Dutch, in which strings are combined by a technique quite similar to Pollard's head wrapping. The main part of the chapter is section 4.4, in which a parsing strategy for linear and non-erasing grammars is proposed. Most `standard' parsing algorithms for constraint-based grammars [55,64,84,25,24] are not applicable in general for non-concatenative grammars because in these algorithms the assumption that phrases are constructed by concatenation is `built-in'. I describe a head-driven parsing algorithm, based on the head-driven parser by Martin Kay [46]. The parser is generalized in order to be applicable to any grammar that employs linear and non-erasing operations on strings. The disadvantages Kay noted for his parser do not carry over to this generalized version, as redundant search paths for CF-based grammars turn out to be genuine parts of the search space for this enlarged class of grammars.

The algorithm is closely related to head-driven generators as discussed in the previous chapter. The algorithm proceeds in a bottom-up, head-driven fashion, which provides for bottom-up and top-down filtering in a simple and straightforward way. In modern linguistic theories very much information is defined in lexical entries, whereas rules are reduced to very general (and very un-informative) schemata. More information usually implies a reduction of the search space, hence it is sensible to parse bottom-up, in order to obtain useful information as soon as possible. Furthermore, in many linguistic theories, a `head' of a construction plays an important role. For example, heads of a construction determine what other parts the construction may have. Furthermore, heads carry the features associated with the construction as a whole (such as case, agreement). The notion `head' plays an important role in grammatical theories as diverse as Government and Binding, (Xbar theory, [37]); Generalized Phrase Structure Grammar (the head-feature convention, [23]); and Head-driven Phrase Structure Grammar, where the name of the theory reflects the importance of the notion `head'. Given the importance of the notion `head', it is sensible to start with the head, in order to know what else you have to look for next. As the parser proceeds from head to head it is furthermore possible to use powerful top-down predictions based on the usual head feature percolations.

In section 4.5 I show how the head-driven parser can be put to use for another instantiation of constraint-based grammars in which string operations are restricted to be linear and non-erasing: constraint-based and lexical versions of Tree Adjoining Grammars.

Some of the properties and possible modifications of the head-corner parser are discussed in section  4.6.