Head Corner Parsing

Gertjan van Noord

Lehrstuhl für Computerlinguistik Universität des Saarlandes Im Stadtwald 15 D-6600 Saarbrücken 11, FRG vannoord@coli.uni-sb.de

Abstract I describe a head-driven parser for a class of grammars that handle discontinuous constituency by a richer notion of string combination than ordinary concatenation. The parser is a generalization of the left-corner parser and can be used for grammars written in powerful formalisms such as non-concatenative versions of UCG and HPSG.

1 Introduction

Although most constraint-based formalisms in computational linguistics assume that phrases are built by concatenation (eg. as in PATR II, GPSG, LFG and most versions of Categorial Grammar) this assumption is sometimes challenged by allowing more powerful operations to construct strings. For example, Pollard (1984) proposes several versions of ‘head wrapping’. In the analysis of the Australian free word-order language Guugu Yimidhirr, Mark Johnson uses a ‘combine’ predicate in a DCG-like grammar that corresponds to the union of words (Johnson, 1985). Mike Reape uses an operation called ‘sequence union’ to analyse Germanic semi-free word order constructions (Reape, 1989; Reape, 1990). Other examples outside the family of constraint-based formalisms include Tree Adjoining Grammars (Joshi et al., 1975; Vijay-Shankar and Joshi, 1988), versions of Categorial Grammar (Dowty, 1990) and references cited there, and some approaches within more traditional branches of generative grammar (Blevins, 1990).

The linguistic motivation for such alternative conceptions of string combination are so-called discontinuous constituency constructions. Furthermore, in formalisms that provide more powerful string operations it is much easier to define analyses in which the semantics is built compositionally. This in turn may simplify generation algorithms.

In the next section I describe the proposals by Pollard (1984); Johnson (1985) and Reape (1989). Based on work by Vijay-Shanker et al. (1987) I introduce the notion of Linear Context-free Rewriting systems, augmented with Feature structures (F-LCFRS). In F-LCFRS we abstract away from the actual construction of strings; we only require that these operations are linear and non-erasing. The three approaches mentioned previously are examples of F-LCFRS.

Most ‘standard’ parsing algorithms for constraint-based grammars (Matsumoto et al., 1983; Pereira and Shieber, 1987; Shieber, 1989; Haas, 1989; Gerdemann, 1991) are not applicable in general for F-LCFRS 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 (Kay, 1989). The parser is generalized in order to be applicable to any F-LCFR grammar. 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 F-LCFR grammars.

The algorithm is closely related to head-driven generators (van Noord, 1989; Calder et al., 1989; Shieber et al., 1989; van Noord, 1990; Shieber et al., 1990). 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 uninformative) schemata. More information usually implies less 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 special daughter called the head determines what kind of other daughters there may be. Therefore, it is also 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.

This chapter is organized as follows. Firstly I discuss the proposals for more powerful string operations, as presented by Pollard (1984), Johnson (1985) and Reape (1990). Then I define two restrictions on possible string combinations for constraint-based grammars, based on Vijay-Shanker et al. (1987). As an example I define 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, in which a parsing strategy for F-LCFR grammars is proposed. Some of its properties and possible modifications are discussed in the final section.

2 Beyond concatenation

2.1 Concatenative systems

In formalisms such as PATR II the string associated with a derivation is the sequence of terminal nodes of the corresponding derivation tree in left-to-right order. For example, the sentence

(1) Kim is easy to please

may be analyzed in some PATR grammar in a way that gives rise to the derivation tree in figure 1. Hence, the string associated with the derivation is the sequence

s_{2} kim [figure] [figure] vp_{3} is[figure] [figure] ap_{2} easy [figure] [figure] vp_{6} to[figure] [figure] please

Figure 1: PATR derivation tree

‘kim is easy to please’. Note though that in PATR this string is not (necessarily) part of the feature structures.

In sign-based approaches such as in UCG and HPSG the string does not have any special status but is part of an attribute of each feature structure (sign). The attribute is usually called ‘phon’, ‘string’, ‘graph’ or ‘orth’ (I will use ‘string’ in the following). Hence, the string associated with a construction is simply the value of the ‘string’ feature of the sign that is assigned to the construction. In UCG there is a condition called ‘adjacency’ condition, which says that signs can combine only if they are adjacent. In other words, the value of the ‘string’ feature of a mother node in a parse tree is always the concatenation of the ‘string’ features of the daughter nodes. Hence, the UCG parse tree for the foregoing example presumably would be someting like figure 2.

[figure: [ string : ⟨kim, is, easy, to, please⟩ ]; _{[ string : ⟨kim⟩ ]}; _{[ string : ⟨is, easy, to, please⟩ ]}; _{[ string : ⟨is⟩ ]}; _{[ string : ⟨easy, to, please⟩ ]}; _{[ string : ⟨easy⟩ ]}; _{[ string : ⟨to, please⟩ ]}; _{[ string : ⟨to⟩ ]}; _{[ string : ⟨please⟩ ]}]

Figure 2: UCG parse tree

The two approaches are formally equivalent, but the second approach has the advantage that it at least becomes easier to think of other ‘modes’ of combination of the value of the ‘string’ attribute. As an example consider

(2) Kim is an easy person to please

Suppose that there is linguistic motivation that in this sentence, as in sentence (1), the sequence ‘easy to please’ should be regarded as a (discontinuous) constituent. Such an analysis can not be defined directly in PATR or UCG. If no adjancency condition applied we could have a parse tree of ‘easy person to please’ as in figure 3. In the next three subsections I describe some proposals which allow such a direct implementation of discontinuous constituents.

Clearly it is possible to define such an analysis in PATR or UCG in an indirect way by the usual threading of information through intermediate nodes (remember that both systems are Turing equivalent). However, these threading techniques usually become rather complex and make it difficult to define a semantics which is compositional. Furthermore, it is easier to define generation algorithms if the semantics is built in a systematically constrained way. The semantic-head-driven generation strategy discussed in the previous chapter faces problems in case

[figure: [ string : ⟨an, easy, person, to, please⟩ ]; _{[ string : ⟨an⟩ ]}; _{[ string : ⟨easy, person, to, please⟩ ]}; _{[ string : ⟨person⟩ ]}; _{[ string : ⟨easy, to, please⟩ ]}; _{[ string : ⟨easy⟩ ]}; _{[ string : ⟨to, please⟩ ]}; _{[ string : ⟨to⟩ ]}; _{[ string : ⟨please⟩ ]}]

Figure 3: Discontinuous Constituency

semantic heads are ‘displaced’, and this displacement is analyzed using threading. However, in this chapter I sketch a simple analysis of verb-second (an example of a displacement of semantic heads) by an operation similar to head wrapping which a head-driven generator processes without any problems (or extensions) at all.

2.2 More powerful string operations

2.2.1 Head wrapping

Pollard (1984) proposes a grammatical formalism called Head Grammar (HG). HG is a slightly more powerful formalism than context-free grammar. The extra power is available through head wrapping operations. A head wrapping operation manipulates strings which contain a distinguished element (its head). Such headed strings are a pair of an ordinary string, and an index (the pointer to the head), for example ⟨w_{1}w_{2}w_{3}w_{4}, 3⟩ is the string w_{1}w_{2}w_{3}w_{4} whose head is w_{3}. Ordinary grammar rules define operations on such strings. Such an operation takes n headed strings as its arguments and returns a headed string. A simple example is the operation which takes two headed strings and concatenates the first one to the left of the second one, and where the head of the second one is the head of the result (this shows that the operations subsume ordinary concatenation). The rule is labelled LC2 by Pollard:

LC2(⟨σ, j⟩, ⟨τ, i⟩) := ⟨στ, i⟩

The following example shows that head-wrapping operations are in general more powerful than concatenation. In this example the second argument is ‘wrapped’ around the first argument:

RL2(⟨σ, j⟩, ⟨t_{1} … t_{n}, i⟩) := ⟨t_{1} … t_{i}σt_{i+1} … t_{n}, i⟩

As an example, Pollard presents a rule for English auxiliary inversion:

S[+INV] → RL2(NP, V P [+AUX])

which may combine the noun phrase ‘Kim’ and the verb phrase ‘must go’ to yield ‘Must Kim go’, with head ‘must’.

The motivation Pollard presents for extending context-free grammars (in fact, GPSG), is of a linguistic nature. Especially so-called discontinuous constituencies can be handled by HG whereas they constitute typical puzzles for GPSG. Apart from the above mentioned subject-auxiliary inversion he discusses the analysis of ‘transitive verb phrases’ based on Bach (1979). The idea is that in sentences such as

(3) Sandy persuaded Kim to leave

‘persuaded’ + ‘to leave’ form a (VP) constituent, which then combines with the NP object (’Kim’) by a wrapping operation.

Yet another example of the use of head-wrapping in English are the analyses of the following sentences.

(4) a. Kim is much taller than Sandy

b. Kim is a much taller person than Sandy

(5) a. Kim is very easy to please

b. Kim is a very easy person to please

where in the first two cases ‘taller than Sandy’ is a constituent, and in the latter examples ‘easy to please’ is a constituent.

Breton and Irish are VSO languages, for which it has been claimed that the V and the O form a constituent. Such an analysis is readily available using head wrapping, thus providing a non-transformational account of McCloskey (1983).

Finally, Pollard also provides a wrapping analysis of Dutch cross-serial dependencies.

2.2.2 Johnson’s ‘combines’

Johnson (1985) discusses an extenstion of DCG in order to analyse the Australian free word-order language ‘Guugu Yimidhirr’. In ordinary DCG a category is associated with a pair indicating which location the constituent occupies. Johnson proposes that constituents in the extended version of DCG be associated with a set of such pairs. A constituent thus ‘occupies’ a set of continuous locations. The following is a sentence of Guugu Yimidhirr:

(6) Yarraga-aga-mu-n gudaa dunda-y biiba-ngun boy-GEN-mu-ERG do+ABS hit-PAST father-ERG The boy’s father hit the dog

In this sentence, the discontinuous constituent ‘Yarraga-aga-mu-n … biiba-ngun’ (boy’s father) is associated with the set of locations:

{[0, 1], [3, 4]}

Johnson notices that such expressions can be represented with bit vectors. In a grammar rule the sets of locations of the daughters of the rule are ‘combined’ to construct the set of locations associated with the daughters. The predicate combines(s_{1}, s_{2}, s) is true iff s is equal to the (bit-wise) union of s_{1} and s_{2}, and the (bit-wise) intersection of s_{1} and s_{2} is null (ie. s_{1} and s_{2} must be non-overlapping locations). Grammars which exclusively use this predicate, are permutationclosed. For Guugu Yimidhirr Johnson also proposes a concatenative rule for possesive noun constructions in which the possesive is identified by position rather than by inflectional markings. Apart from these constructions Guugu Yimidhirr is said to be permutation-closed (Johnson, quoting Haviland (1979)).

Earley deduction (Pereira and Warren, 1983) is used as a general proof procedure for such extended DCG grammars.

2.2.3 Sequence union

Reape (1989), and Reape (1990) discuss an operation called sequence union to analyze discontinuous constituents. The sequence union of two sequences s_{1} and s_{2} is the sequence s_{3} iff each of the elements in s_{1} and s_{2} occur in s_{3}, and moreover, the originial order of the elements in s_{1} and s_{2} is preserved. For example, the sequence union of the sequences ⟨a, b⟩ and ⟨c, d⟩ is any of the sequences:

⟨a, b, c, d⟩
⟨a, c, b, d⟩
⟨a, c, d, b⟩
⟨c, d, a, b⟩
⟨c, a, d, b⟩
⟨c, a, b, d⟩

[figure: es_{i} ihm_{j} jemand_{k} zu lesen_{i} versprochen_{j} hat_{k}; jemand_{k}; hat_{k}; es_{i} ihm_{j} zu lesen_{i} versprochen_{j}; ihm_{j}; versprochen_{j}; es_{i} zu lesen_{i}; es_{i}; zu lesen_{i}]

Figure 4: Parse tree of sequence union example

Reape presents an HPSG-style grammar (Pollard and Sag, 1987) for German and Dutch which uses the sequence union relation on word-order domains. The grammar handles several word-order phenomena in German and Dutch. Wordorder domains are sequences of signs. The phonology of a sign is the concatenation of the phonology of the elements of its word-order domain. In ‘rules’, the word-order domain of the mother sign is defined in terms of the word-order domains of its daughter signs. For example, in the ordinary case the word-order domain of the mother simply consists of its daughter signs. However, in specific cases it is also possible that the word-order domain of the mother is the sequence union of the word-order domains of its daughters.

The following German example by Reape clarifies the approach, where I use indices to indicate to which verb an object belongs.

(7) … es_{i} ihm_{j} jemand_{k} zu lesen_{i} versprochen_{j} hat_{k} … it him someone to read promised had (i.e. someome had promised him to read it)

Figure 4 shows a parse tree of this sentences where the nodes of the derivation tree are labelled by the string associated with that node. Note that strings are defined with respect to word-order domains. Sequence union is defined on such domains. The strings of the derivation tree are thus only indirectly related through the corresponding word-order domains. Linear precedence statements are defined with respect to word-order domains. These statements can be thought of either as well-formedness conditions on totally ordered sequences, or alternatively as constraints further limiting possible orders of a word-order domain. Note that order information is monotonic; the sequence union relation can not ‘change’ the order of two ordered items.

2.3 F-LCFRS

I will restrict the attention to a class of constraint-based formalisms, in which operations on strings are defined that are more powerful than concatenation, but which operations are restricted to be nonerasing, and linear. The resulting class of systems can be characterized as Linear Context-Free Rewriting Systems (LCFRS), augmented with feature-structures (F-LCFRS). For a discussion of the properties of LCFRS without feature-structures, see Vijay-Shanker et al. (1987) and Weir (1988). Note though that these properties do not carry over to the current system, because of the augmention with feature structures. The proposals discussed in the previous section can be seen as examples of F-LCFRS.

As in LCFRS, the operations on strings in F-LCFRS can be characterized as follows. First, derived structures will be mapped onto a string of words; i.e. each derived structure ‘knows’ which string it ‘dominates’. For example, each derived feature structure may contain an attribute ‘string’ whose value is a list of atoms representing the string it dominates. Furthermore, I will identify this string with the set of occurrences of words (or bag of words) in the string. I will write w(F) for the set of occurrences of words that the derived structure F dominates. Rules combine structures D_{1} … D_{n} into a new structure M. Nonerasure requires that the union of w applied to each daughter is a subset of w(M):

⋃_{i=1}^{n} w(D_{i}) ⊆ w(M)

Linearity requires that the difference of the cardinalities of these sets is a constant factor; i.e. a rule may only introduce a fixed number of words syncategorematically:

|w(M)| − | ⋃_{i=1}^{n} w(D_{i})| = c, c a constant

CF-based formalisms clearly fulfill this requirement, as do Head Grammars, grammars using sequence union, Johnson’s Australian grammar, and TAG’s. Unlike in the definition of LCFRS I do not require that these operations are operations in the strict sense, i.e. the operations do not have to be functional. Note that sequence union is relational; the others are functional. For a discussion of the consequences of this difference, refer to Reape (1991). I assume here furthermore that ⋃_{i=1}^{n} w(D_{i}) = w(M), for all rules other than lexical entries (i.e. all words are introduced on a terminal). Note though that a simple generalization of the algorithm presented below handles the general case (along the lines of Shieber et al. (1989); Shieber et al. (1990) by treating rules that introduce extra lexical material as non-chain-rules).

Furthermore, I will assume that each rule has a designated daughter, called the head. Although I will not impose any restrictions on the head, it will turn out that the parsing strategy to be proposed will be very sensitive to the choice of heads, with the effect that F-LCFRS’s in which the notion ‘head’ is defined in a systematic way (Pollard’s Head Grammars, Reape’s version of HPSG, Dowty’s version of Categorial Grammar), may be much more efficiently parsed than other grammars. The notion lexical head of a parse tree is defined recursively in terms of the head. The lexical head of a tree will be the lexical head of its head. The lexical head of a terminal will be that terminal itself. I will write the head of a definite clause as the leftmost daughter of that clause.

A grammar will be a set of definite clauses over a constraint language, following Höhfeld and Smolka (1988). The constraint language consists of path equations in the manner of PATR. Hence, instead of first-order terms we are using feature structures. The relation defined by the grammar will be the relation ‘sign’. I assume furthermore that no other recursive relations are being defined. Hence a grammar rule will be something like

sign(M):-sign(D_{1}) … sign(D_{n}), ϕ.

where ϕ are constraints on the variables. However, each nonunit rule may be associated with one extra relation-call. This extra relation is thought of as defining how the string of the mother node is built from the strings of the daughters. For example, to implement a simple grammar rule using concatenation, we may write

(8) sign(M):- sign(D_{1}),

sign(D_{2}),
concatenate strings(D_{1}, D_{2}, M)
ϕ.

where the relation ‘concatenate strings’ states that the string of the mother is the concatenation of the strings of the daughters. The extra relation should be defined in such a way that given the two instantiated daughter signs, the extra relation is guaranteed to terminate (assuming Prolog like procedural semantics).

Furthermore, each grammar should provide a definition of the predicates head/2 and string/2. The first one defines the relation between the mother sign of a rule and its head; the second one defines for a sign the string (as a list of atoms) associated with that sign.

In the meta-interpreter I use for a nonunit clause

sign(Mother):-sign(Head), sign(D_{1}) … sign(D_{n}), Call, ϕ.

the predicate rule/4:

rule(Head, Mother, ⟨D_{1} … D_{n}⟩, Call):-ϕ.

Unit clauses are represented as

lex(M):-ϕ.

I assume the meta interpreter has the predicate ‘call/1’ available which may be used as in Prolog.

3 A sample grammar

In this section I present a simple F-LCFR grammar for a (tiny) fragment of Dutch. As a caveat I want to stress that the purpose of the current section is to provide an example of possible input for the parser to be defined in the next section, rather than to provide an account that is completely satisfactory from a linguistic point of view.

There is only one parameterized, binary branching, rule in the grammar:

(9) sign([ \begin{matrix}syn : Syn \\ sc : T ail \\ sem : Sem) \end{matrix} ]_{M} :-

sign([ \begin{matrix}syn : Syn \\ sc : ⟨Arg|T ail⟩ \\ sem : Sem \end{matrix} ]_{H}),

sign(Arg), cb(M, H, Arg).

In this grammar rule, heads select arguments using a subcat list. Argument structures are specified lexically and are percolated from head to head. Syntactic features are shared between heads (hence I make the simplifying assumption that head = functor, which may have to be revised in order to treat modification). The relation ‘cb’ defines how the string of the mother is constructed from its daughters. In the grammar I use revised versions of Pollard’s head wrapping operations to analyse cross serial dependency and verb second constructions. For a linguistic background of these constructions and analyses, cf. Evers (1975), Koster (1975) and many others. The value of the attribute phon consists of three parts, to implement the idea of Pollard’s ‘headed strings’. The parts left and right represent the strings left and right of the head. The part head represent the head string. Hence, the string associated with such a term is the concatenation of the three arguments from left to right. The predicate cb is defined as follows:

(10) cb([ \begin{matrix}phon : Mphon \\ string : String \end{matrix} ] , [ phon : Hphon ] , [ \begin{matrix}phon : Aphon \\ rule : Rule \end{matrix} ]):-

wrap(Rule, Hphon, Aphon, Mphon),
phon string(Mphon, String).

Here, the values of the attribute phon associated with the two daughters of the rule are to be combined by the wrap predicate. Several versions of this predicate will be defined below. The value of ‘string’ of the mother node is defined with respect to its ‘phon’ value by the predicate phon string. This predicate is defined in terms of the predicate append/3. As an abbreviation I write A · B for C such that append(A, B, C). The definitions of both predicates follow:

(11) phon string([ \begin{matrix}left : L \\ head : H \\ right : R \end{matrix} ] , L · H · R).

append(⟨⟩, X, X).

append(⟨H|T ⟩, L_{1}, ⟨H|L⟩):-

append(T, L_{1}, L)

There are a few versions of the predicate wrap to illustrate the idea that different string operations can be defined. Each version of the predicate will be associated with an atomic identifier to allow lexical entries to subcategorize for their arguments under the condition that a specific version of this predicate be used. The purpose of this feature is similar to the ‘order’ feature found in UCG (Zeevat et al., 1987). For example, a verb may select an object to its left, and an infinite verb phrase which has to be raised. For simple (left or right) concatenation the predicate is defined as follows:

(12) wrap(left, [ \begin{matrix}left : L \\ head : H \\ right : R \end{matrix} ] , [ \begin{matrix}left : ArgL \\ head : ArgH \\ right : ArgR \end{matrix} ] , [ \begin{matrix}left : ArgL · ArgH · ArgR · L \\ head : H \\ right : R \end{matrix} ]).

wrap(right, [ \begin{matrix}left : L \\ head : H \\ right : R \end{matrix} ] , [ \begin{matrix}left : ArgL \\ head : ArgH \\ right : ArgR \end{matrix} ] , [ \begin{matrix}left : L \\ head : H \\ right : R · ArgL · ArgH · ArgR \end{matrix} ]).

In the first case the string associated with the argument is appended to the left of the string left of the head; in the second case this string is appended to the right of the string right of the head. Lexical entries for intransitive verbs such as ‘ontwaakt’ (wakes up) are defined as follows:

(13) [ \begin{matrix}syn : v \\ sc : ⟨[ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Subj \\ rule : left \end{matrix} ]⟩ \\ phon : [ \begin{matrix}left : ⟨⟩ \\ head : ⟨ontwaakt⟩ \\ right : ⟨⟩ \end{matrix} ] \\ sem : ontwaakt(Subj) \\ string : ⟨ontwaakt⟩ \end{matrix} ]

I assume that lexical entries also specify that their string-value is functionally dependent of the phon value. Furthermore, the values of the left and right attributes of phon are the empty list. Henceforth, I will not specify the value of string explicitly, but assume that each lexical entry extends

[ \begin{matrix}phon : [ \begin{matrix}left : ⟨⟩ \\ head : Head \\ right : ⟨⟩ \end{matrix} ] \\ string : Head \end{matrix} ] .

Hence, bitransitive verbs such as ‘vertelt’ (tells) are abbreviated as follows:

(14) [ \begin{matrix}syn : v \\ sc : ⟨[ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Obj \\ rule : left \end{matrix} ] , [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Iobj \\ rule : left \end{matrix} ] , [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Subj \\ rule : left \end{matrix} ]⟩ \\ phon : [ head : ⟨vertelt⟩ ] \\ sem : vertelt(Subj, Iobj, Obj) \end{matrix} ]

A different version of this lexical entry selects an sbar to the right:

(15) [ \begin{matrix}syn : v \\ sc : ⟨[ \begin{matrix}syn : comp \\ sc : ⟨⟩ \\ sem : Obj \\ rule : right \end{matrix} ] , [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Iobj \\ rule : left \end{matrix} ] , [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Subj \\ rule : left \end{matrix} ]⟩ \\ phon : [ head : ⟨vertelt⟩ ] \\ sem : vertelt(Subj, Iobj, Obj) \end{matrix} ]

Proper nouns such as ‘Arie’ are simply defined as:

(16) [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ phon : [ head : ⟨arie⟩ ] \\ sem : arie \end{matrix} ]

For the sake of the example I assume several other np’s to have such a definition.

The choice of datastructure for the value of the attribute phon allows a simple definition of the verb raising (vr) version of the wrap predicate that may be used for Dutch cross serial dependencies:

(17) wrap(vr, [ \begin{matrix}left : ⟨⟩ \\ head : H \\ right : ⟨⟩ \end{matrix} ] , [ \begin{matrix}left : ArgL \\ head : ArgH \\ right : ArgR \end{matrix} ] , [ \begin{matrix}left : ArgL \\ head : H \\ right : ArgH · ArgR \end{matrix} ]).

Here the head and right string of the argument are appended to the right, whereas the left string of the argument is appended to the left. A raising verb, eg. ‘hoort’ (hears) is defined as:

(18) [ \begin{matrix}syn : v \\ sc : ⟨[ \begin{matrix}syn : inf \\ sc : ⟨[ sem : InfSubj ]⟩ \\ sem : Obj \\ rule : vr \end{matrix} ] , [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : InfSubj \\ rule : left \end{matrix} ] , [ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Subj \\ rule : left \end{matrix} ]⟩ \\ phon : [ head : ⟨hoort⟩ ] \\ sem : hoort(Subj, Obj) \end{matrix} ]

In this entry ‘hoort’ selects — apart from its np-subject — two objects, a np and a vp (with category inf). The inf still has an element in its subcat list; this element is controlled by the np (this is performed by the sharing of InfObj). To derive the subordinate phrase

(19) dat Jan Arie Bob leugens hoort vertellen (that Jan hears that Arie tells lies to Bob)

the main verb ‘hoort’ first selects the infinitival ‘bob leugens vertellen’. These two strings are combined into ‘bob leugens hoort vertellen’ (using the vr version of the wrap predicate). After the selection of the object, resulting in ‘arie bob leugens hoort vertellen’, the subject is selected resulting in the string ‘jan arie bob leugens hoort vertellen’. This string is selected by the complementizer, resulting in ‘dat jan arie bob leugens hoort vertellen’. The argument structure will be instantiated as dat(hoort(jan,vertelt(arie,bob,leugens))).

In Dutch main clauses, there usually is no overt complementizer; instead the finite verb occupies the first position (in yes-no questions), or the second position (right after the topic; ordinary declarative sentences). In the following analysis an empty complementizer selects an ordinary (finite) v; the resulting string is formed by the following definition of wrap:

(20) wrap(v2, [ \begin{matrix}left : ⟨⟩ \\ head : ⟨⟩ \\ right : ⟨⟩ \end{matrix} ] , [ \begin{matrix}left : L \\ head : H \\ right : R \end{matrix} ] , [ \begin{matrix}left : ⟨⟩ \\ head : H \\ right : L · R \end{matrix} ]).

The ‘empty’ finite complementizer is defined as:

(21) [ \begin{matrix}syn : comp \\ sc : ⟨[ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : Obj \\ rule : v2 \end{matrix} ]⟩ \\ phon : [ head : ⟨⟩ ] \\ sem : dat(Obj) \end{matrix} ]

whereas an ordinary complementizer, eg. ‘dat’ (that) is defined as:

(22) [ \begin{matrix}syn : comp \\ sc : ⟨[ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : Obj \\ rule : right \end{matrix} ]⟩ \\ phon : [ head : ⟨dat⟩ ] \\ sem : dat(Obj) \end{matrix} ]

Note that this analysis captures the special relationship between complementizers and (fronted) finite verbs in Dutch. The sentence

(23) Hoort Arie Jan Bob vertellen dat Claire ontwaakt? (hears Arie Jan Bob tell that Claire wakes up? i.e. Does Arie hear that Jan tells Bob that Claire wakes up?)

is derived as in figure 5 (where the head of a string is represented in capitals).

What remains to be done is to define the two grammar specific predicates head/2 and string/2. These are simply defined as follows:

(24) head([ \begin{matrix}syn : Syn \\ sem : Sem \end{matrix} ] , [ \begin{matrix}syn : Syn \\ sem : Sem \end{matrix} ]).

string([ string : String ] , String).

v2: HOORT arie jan bob vertellen dat claire ontwaakt ϵ [figure]  [figure] left: arie jan bob HOORT vertellen dat claire ontwaakt left: jan bob HOORT vertellen dat claire ontwaakt vr: bob HOORT vertellen dat claire ontwaakt HOORT [figure]  [figure] left: bob VERTELLEN dat claire ontwaakt right: VERTELLEN dat claire ontwaakt VERTELLEN [figure]  [figure] right: DAT claire ontwaakt DAT[figure] [figure] left: claire ONTWAAKT ONTWAAKT [figure] [figure] CLAIRE [figure]  [figure] BOB [figure]  [figure] JAN [figure]  [figure] ARIE

Figure 5: Deriving ‘Hoort Arie Jan Bob vertellen dat Claire ontwaakt’

4 The head corner parser

This section describes the head-driven parsing algorithm for the type of grammars described above. The parser is a generalization of Kay’s head-driven parser, which in turn is a modification of a left-corner parser. The parser, which may be called a ‘head-corner’ parser,^{1} proceeds in a bottom-up way. Because the parser proceeds from head to head it is easy to use powerful top-down predictions based on the usual head feature percolations, and subcategorization requirements that heads require from their arguments. In fact, the motivation for this approach to parsing discontinuous constituency is already hinted at by Mark Johnson (Johnson, 1985):

My own feeling is that the approach that would bring the most immediate results would be to adopt some of the “head driven” aspects of Pollard’s (1984) Head Grammars. In his conception, heads contain as lexical information a list of the items they subcategorize for. This strongly suggests that one should parse according to a “head-first” strategy: when one parses a sentence, one looks for its verb first, and then, based on the lexcial form of the verb, one looks for the other arguments in the clause. Not only would such an approach be easy to implement in a DCG framework, but given the empirical fact that the nature of argument np’s in a clause is strongly determined by that clause’s verb, it seems a very reasonable thing to do.

It is clear from the context that Johnson believes this strategy especially useful for non-configurational languages.

In left-corner parsers (Matsumoto et al., 1983) the first step of the algorithm is to select the left-most word of a phrase. The parser then proceeds by proving that this word indeed can be the left-corner of the phrase. It does so by selecting a rule whose leftmost daughter unifies with the category of the word. It then parses other daughters of the rule recursively and then continues by connecting the mother category of that rule upwards, recursively. The left-corner algorithm can be generalized to the class of grammars under consideration if we start with the lexical head of a phrase, instead of its leftmost word. Furthermore the head corner predicate then connects smaller categories upwards by unifying them with the head of a rule. The first step of the algorithm consists of the prediction step: which lexical entry is the lexical head of the phrase? The first thing to note is that the words introduced by this lexical entry should be part of the input string, because of the nonerasure requirement. Therefore we use the bag of words as a ‘guide’ (Dymetman et al., 1990) as in a left-corner parser, but we change the way in which lexical entries ‘consume the guide’. For the moment I assume that the bag of words is simply represented with the string, but I introduce a better datastructure for bags in the next section. Hence to get things going I define the predicate start parse/1 as follows:

1This name is due to Pete Whitelock.

(25) start parse(Sign):- string(Sign, String),

parse(Sign, String, ⟨⟩).

Furthermore in most linguistic theories it is assumed that certain features are shared between the mother and the head. I assume that the predicate head/2 defines these feature percolations; for the grammar of the foregoing section this predicate was defined as:

(26) head([ \begin{matrix}syn : Syn \\ sem : Sem \end{matrix} ] , [ \begin{matrix}syn : Syn \\ sem : Sem \end{matrix} ]).

As we will proceed from head to head these features will also be shared between the lexical head and the top-goal; hence we can use this definition to restrict lexical lookup by top-down prediction. ^{2} The first step in the algorithm is defined as:

(27) parse(Goal, P_{0}, P):- predict head(Goal, Lex, P_{0}, P_{1}),

head corner(Lex, Goal, P_{1}, P).

predict head(Goal, Lex, P_{0}, P):-

head(Goal, Lex),
lex(Lex),
string(Lex, W ords),
subset(W ords, P_{0}, P).

Instead of taking the first word from the current input string, the parser may select a lexical entry dominating a subset of the words occuring in the input string, provided this lexical entry can be the lexical head of the current goal. The predicate subset(L_{1}, L_{2}, L_{3}) is true in case L_{1} is a subset of L_{2} with complement L_{3}. Later we will improve on the indexing of lexical entries.

The second step of the algorithm, the head corner part, is identical to the left corner part of the left-corner parser, but instead of selecting the leftmost daughter of a rule the head-corner parser selects the head of a rule. Remember that nonunit rules are represented as:

rule(Head, Mother, Ds, Call)

where Head is the head of the rule, Mother is the mother node, Ds is a list of daughter nodes and Call is the call to the extra relation.

2In the general case we need to compute the transitive closure of (restrictions of (Shieber, 1985)) possible mother-head relationships.

(28) head corner(X, X, P, P).

head corner(Small, Big, P_{0}, P):-

rule(Small, Mid, Others, Call),
parse list(Others, P_{0}, P_{1}),
call(Call),
head corner(Mid, Big, P_{1}, P).

parse list([], P, P).

parse list([H|T], P_{0}, P):-

parse(H, P_{0}, P_{1}),
parse list(T, P_{1}, P).

4.0.1 Example.

To parse the sentence ‘dat jan ontwaakt’, the head corner parser will proceed as follows. The first call to parse is:

?- parse([ \begin{matrix}syn : comp \\ sc : ⟨⟩ \\ string : ⟨dat, jan, ontwaakt⟩ \end{matrix} ] , ⟨dat, jan, ontwaakt⟩, ⟨⟩).

The prediction step selects the lexical entry ‘dat’. The next goal is to show that this lexical entry is the lexical head of the top goal; furthermore the string that still has to be covered is now ⟨jan, ontwaakt⟩. Leaving details out the head corner clause looks as :

?- head corner([ \begin{matrix}syn : comp \\ sc : ⟨[ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : Sem \\ rule : right \end{matrix} ]⟩ \\ phon : [ \begin{matrix}left : ⟨⟩ \\ head : ⟨dat⟩ \\ right : ⟨⟩ \end{matrix} ] \\ string : ⟨dat⟩ \\ sem : dat(Sem) \end{matrix} ] ,

[ \begin{matrix}syn : comp \\ sc : ⟨⟩ \\ string : ⟨dat, jan, ontwaakt⟩ \end{matrix} ] ,

⟨jan, ontwaakt⟩, ⟨⟩).

The category of dat has to be matched with the head of a rule. Notice that dat subcategorizes for a v with rule feature right. Hence the right version of the wrap predicate applies, and the next goal is to parse the v for which this complementizer subcategorizes, with input ‘jan, ontwaakt’:

?- parse([ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : Sem \\ rule : right \end{matrix} ] , ⟨jan, ontwaakt⟩, P).

Lexical lookup selects the word ontwaakt from this string. The word ontwaakt has to be shown to be the head of this v node, by the head corner predicate:

?- head corner([ \begin{matrix}syn : v \\ sc : ⟨[ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : Subj \\ rule : left \end{matrix} ]⟩ \\ phon : [ \begin{matrix}left : ⟨⟩ \\ head : ⟨ontwaakt⟩ \\ right : ⟨⟩ \end{matrix} ] \\ sem : ontwaakt(Subj) \\ string : ⟨ontwaakt⟩ \end{matrix} ] ,

[ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : Sem \\ rule : right \end{matrix} ] , ⟨jan⟩, P).

This time the left combination rule applies and the next goal consists in parsing a np (for which ontwaakt subcategorizes) with input string jan. This goal succeeds with an empty output string. Hence the argument of the rule has been found successfully and hence we need to connect the mother of the rule up to the v node. This succeeds trivially, instantiating the head corner call above to:

?- head corner([ \begin{matrix}syn : v \\ sc : ⟨[ \begin{matrix}syn : n \\ sc : ⟨⟩ \\ sem : jan \\ rule : left \end{matrix} ]⟩ \\ phon : [ \begin{matrix}left : ⟨⟩ \\ head : ⟨ontwaakt⟩ \\ right : ⟨⟩ \end{matrix} ] \\ sem : ontwaakt(jan) \\ string : ⟨ontwaakt⟩ \end{matrix} ] ,

[ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : ontwaakt(jan) \\ phon : [ \begin{matrix}left : ⟨jan⟩ \\ head : ⟨ontwaakt⟩ \\ right : ⟨⟩ \end{matrix} ] \\ string : ⟨jan, ontwaakt⟩ \\ rule : right \end{matrix} ] , ⟨jan⟩, ⟨⟩).

and therefore we now have found the v for which dat subcategorizes, instantiating the parse goal above to:

?- parse([ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : ontwaakt(jan) \\ phon : [ \begin{matrix}left : ⟨jan⟩ \\ head : ⟨ontwaakt⟩ \\ right : ⟨⟩ \end{matrix} ] \\ string : ⟨jan, ontwaakt⟩ \\ rule : right \end{matrix} ] , ⟨jan, ontwaak⟩, ⟨⟩).

Hence the next goal is to connect the complementizer with an empty subcat list up to the topgoal; again this succeeds trivially. Hence we obtain the instantiated version of the first head corner call:

?- head corner([ \begin{matrix}syn : comp \\ sc : ⟨[ \begin{matrix}syn : v \\ sc : ⟨⟩ \\ sem : ontwaakt(jan) \\ rule : right \end{matrix} ]⟩ \\ phon : [ \begin{matrix}left : ⟨⟩ \\ head : ⟨dat⟩ \\ right : ⟨⟩ \end{matrix} ] \\ sem : dat(Sem_{2}) \end{matrix} ] ,

[ \begin{matrix}syn : comp \\ sc : ⟨⟩ \\ sem : dat(ontwaakt(jan)) \end{matrix} ] , ⟨jan, ontwaakt⟩, ⟨⟩).

and the first call to parse will succeed, yielding:

?- parse([ \begin{matrix}syn : comp \\ sc : ⟨⟩ \\ sem : dat(ontwaakt(jan)) \\ phon : [ \begin{matrix}left : ⟨⟩ \\ head : ⟨dat⟩ \\ right : ⟨jan, ontwaakt⟩ \end{matrix} ] \\ string : ⟨dat, jan, ontwaakt⟩ \end{matrix} ] , ⟨dat, jan, ontwaakt⟩, ⟨⟩).

The flow of control of the parsing process for this example is shown in figure 6. In this picture, the integers associated with the arrows indicate the order of the

comp[] comp[] dat,comp[v] [figure] [figure]v[] v[] ontwaakt, v[n] [figure] [figure]n jan

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

Figure 6: Parsing ‘dat jan ontwaakt’

steps of the parsing process. Predict steps are indicated with a framed integer, head corner steps are indicated with a bold face integer, and recursive parse steps are indicated with a slanted integer. The nodes represent (some of) the information available at the moment this step is performed.

A slightly more complex example is shown in figure 7, for the sentence (29) Hoort Arie Bob sla bestellen?

5 Discussion and Extensions

5.1 Sound and Complete.

The algorithm as it is defined is sound and complete in the usual depth-first, backtrack search sense. Clearly the parser may enter an infinite loop (in case non branching rules are defined that may feed themselves or in case a grammar makes a heavy use of empty categories). However, in case the parser does terminate one can be sure that it has found all solutions.

5.2 Minimality.

A parser is called minimal iff it returns one solution for each possible derivation. As it stands the parser is not minimal in this sense. In fact, if the same word occurs more than once in the input string then we may find a solution several times. The problem comes about because a list is not an appropriate data structure for bags. For example, removing an element from a bag should not be non deterministic, but it is if we use lists (in Prolog this problem may be repaired using the cut). It is straightforward to encode bags with a more appropriate data structure such as the one found in some Prolog libraries, which we will adopt with slight modifications. ^{3}

An empty bag is represented by the constant ‘bag’. A nonempty bag consists of three parts: an element, a (representation of a) number indicating how often this element occurs in the bag, and the rest of the bag. Furthermore the bag is ordered in such a way that an element precedes another element in the bag iff it precedes that element in some standard order. For example, in Prolog the bag {a, b, a, a, b, c} is represented as:

     bag(a,3,bag(b,2,bag(c,1,bag)))

For clarity I sometimes write such a bag as:

⟨a/3, b/2, c/1⟩

and use the usual list notation.

The parser is modified as follows. The predicate which calls the parser will contain an extra predicate, list to bag/2, which encodes a list as a bag. Furthermore this bag is given as the input argument to parse/3; the output argument is the empty bag, the constant bag. comp[] comp[] comp[v] [figure] [figure]v[] v[] v[n] v[n,n] hoort,v[inf,n,n] [figure] [figure]inf[] inf[] bestellen,inf[n] [figure] [figure] n sla [figure] [figure] n bob [figure] [figure] n arie

3For example in the file ‘bags.pl’ of the Quintus library, by Richard O’Keefe.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22]

Figure 7: Parsing ‘Hoort Arie Bob sla bestellen’ (30) start parse(Sign):-

string(Sign, String),

list to bag(String, Bag),
parse(Sign, Bag, bag).

The ‘subset’ predicate is now defined for such bags, and for this reason it is called ‘subbag’.

(31) %subbag(+SubBag, +T otalBag,?ComplementBag). subbag(⟨⟩, Bag, Bag). subbag(⟨El/0|R⟩, Bag, Rest):-

subbag(R, Bag, Rest).

subbag(⟨El/s(X)|R⟩, ⟨El/s(Y)|R2⟩, Rest):-

subbag(⟨El/X|R⟩, ⟨El/Y |R2⟩, Rest).

subbag(⟨El/s(I)|R), ⟨X/Y |Bag⟩, ⟨X/Y |Rest⟩):-

subbag(⟨El/s(I)|R⟩, Bag, Rest).

This definition of the predicate ‘subbag’ is deterministic given the first two arguments, and given the fact that the elements of the bag are always constants. The modified version of the parser is minimal.

5.3 Efficiency.

The parser is quite efficient if the notion ‘syntactic head’ implies that much syntactic information is shared between the head of a phrase and its mother. In this case the prediction step in the algorithm will be much better at ‘predicting’ the head of the phrase. If on the other hand the notion ‘head’ does not imply such feature percolations, then the parser must predict the head randomly from the input string as no top-down information is available.

The efficiency of the parser can be improved by common logic programming and parsing techniques. Firstly, it is possible to compile the grammar rules, lexical entries and parser a bit further by (un)folding. Secondly it is possible to integrate well-formed and ill-formed subgoal tables in the parser, following the technique described by Matsumoto et al. (1983). The usefulness of this technique strongly depends on the actual grammars that are being used.

5.3.1 Indexing of lexical entries

It is possible to use a more clever indexing of lexical entries. Firstly, it is possible to extract the elements from the lexicon that can be used to parse some given sentence, before the parser starts properly. That is, for each sentence the parser first selects those lexical entries that possibly could be used in the analysis of that sentence. The parsing algorithm proper then only takes these lexical entries into account when it searches the lexicon in the prediction step.

Furthermore, we can get rid of the subbag/3 predicate in the predict clause. Given the precompilation step mentioned above, we can use a slightly different representation of bags where the elements of the bag are not explicitly mentioned, but are implicitly represented by the position in the bag. To make this work we also allow bags where elements occur zero times. For example, given the sentence ‘a b b c a a’, the corresponding bag will simply be:

⟨3, 2, 1⟩

Furthermore, the bag that consists of two a’s is given the representation

⟨2, 0, 0⟩

with respect to that sentence. The idea is that each lexical entry which has been found to be a possible candidate for a given sentence is asserted as a clause lex(Node,InBag,OutBag) where the subbag predicate is already partially evaluated. For example, given the sentence ‘a b b c a a’ the indexing step of the parser may find that the lexical entries ‘a’, ‘b’ and ‘c’ are applicable. These entries are then asserted as:

(32) lex(ANode, ⟨s(A), B, C⟩, ⟨A, B, C⟩). lex(BNode, ⟨A, s(B), C⟩, ⟨A, B, C⟩). lex(CNode, ⟨A, B, s(C)⟩, ⟨A, B, C⟩).

The guide is instantiated as follows. The in-part will simply be the bag representation shown above. More precisely:

⟨s(s(s(0))), s(s(0)), s(0)⟩

and the out-part now simply is:

⟨0, 0, 0⟩

The ‘predict head’ clause is re-defined as:

(33) predict head(Goal, Lex, P_{0}, P):- head(Goal, Lex),

lex(Lex, P_{0}, P).

5.3.2 ‘Order-monotonic’ grammars

In some grammars the string operations that are defined are not only monotonic with respect to the words they dominate, but also with respect to the order constraints that are defined between these words (‘order-monotonic’). For example in Reape’s sequence union operation the linear precedence constraints that are defined between elements of a daughter are by definition part of the linear precedence constraints of the mother. Note though that the analysis of verb second in the foregoing section uses a string operation that does not satisfy this restriction. For grammars that do satisfy this restriction it is possible to extend the top-down prediction possibilities by the incorporation of an extra clause in the ‘head corner’ predicate which will check that the phrase that has been analysed up to that point can become a substring of the top string. To this purpose, the input string is percolated through the parser as an extra argument. Each time a rule has applied the parser checks whether the string derived up to that point can be a subsequence of the complete string. This is achieved using the subseq/2 predicate. In that case the revised ‘head corner’ clause looks as follows:

(34) head corner(Sign, Sign, P, P, String).

head corner(Small, Big, P_{0}, P, String):-

rule(Small, Mid, Others, Call),
parse rest(Others, P_{0}, P_{1}, String),
call(Call),
string(Mid, Sub),
subseq(Sub, String),
head corner(Mid, Big, P_{1}, P, String).

subseq(⟨⟩, Seq).

subseq(⟨H|T ⟩, ⟨H|T_{2}⟩):-

subseq(T, T_{2}).

subseq(⟨H|T ⟩, ⟨H_{2}|T_{2}⟩):-

subseq(⟨H|T ⟩, T_{2}).

5.3.3 Delaying the extra constraint

In some cases it is very useful to delay the constraint which defines the operations on strings until the parser is finished. For example, if the constraints are disjunctive then it may be useful to wait as long as possible before a choice in a certain direction is to be made. The important information for the parser is percolated anyway through the bag of words; the actual order of the words has (usually) not much influence on other choices of the parser. Hence a lot of uninteresting non determinism (from the parser’s point of view) can thus be delayed. In practice this increased the efficiency of the parser for some grammars by a factor 3. Clearly this technique is incompatible with the improvement suggested above for order-monotonic grammars.

Acknowledgements

This research was supported by SFB 314, Project N3 BiLD. I am grateful to Mike Reape for useful comments.

References

Emmon Bach. Control in Montague grammar. Linguistic Inquiry, 10:515–553, 1979.

James Blevins. Derived constituent structure, 1990. Ms. University of Texas at Austin & MCC.

Jonathan Calder, Mike Reape, and Henk Zeevat. An algorithm for generation in unification categorial grammar. In Fourth Conference of the European Chapter of the Association for Computational Linguistics, pages 233–240, Manchester, 1989.

David Dowty. Towards a minimalist theory of syntactic structure. In Proceedings of the Symposium on Discontinuous Constituency, ITK Tilburg, 1990.

Marc Dymetman, Pierre Isabelle, and Francois Perrault. A symmetrical approach to parsing and generation. In Proceedings of the 13th International Conference on Computational Linguistics (COLING), Helsinki, 1990.

Arnold Evers. The Transformational Cycle in Dutch and German. PhD thesis, Rijksuniversiteit Utrecht, 1975.

Dale Douglas Gerdemann. Parsing and Generation of Unification Grammars. PhD thesis, University of Illinois at Urbana-Champaign, 1991. Cognitive Science technical report CS-91-06 (Language Series).

Andrew Haas. A parsing algorithm for unification grammar. Computational Linguistics, 15(4), 1989.

J. Haviland. Guugu yimidhirr. In R. Dixon and B.Blake, editors, Handbook of Australian Languages. Benjamins Amsterdam, 1979.

Markus Höhfeld and Gert Smolka. Definite relations over constraint languages. Technical report, 1988. LILOG Report 53; to appear in Journal of Logic Programming.

Mark Johnson. Parsing with discontinuous constituents. In 23th Annual Meeting of the Association for Computational Linguistics, Chicago, 1985.

A.K. Joshi, L.S. Levy, and M. Takahashi. Tree adjunct grammars. Journal Computer Systems Science, 10(1), 1975.

Martin Kay. Head driven parsing. In Proceedings of Workshop on Parsing Technologies, Pittsburgh, 1989.

Jan Koster. Dutch as an SOV language. Linguistic Analysis, 1, 1975.

Y. Matsumoto, H. Tanaka, H. Hirakawa, H. Miyoshi, and H. Yasukawa. BUP: a bottom up parser embedded in Prolog. New Generation Computing, 1(2), 1983.

J. McCloskey. A VP in a VSO language? In Gerald Gazdar, Ewan Klein, and Geoffrey K. Pullum, editors, Order, Concord and Constituency. Foris, 1983.

Fernando C.N. Pereira and Stuart M. Shieber. Prolog and Natural Language Analysis. Center for the Study of Language and Information Stanford, 1987.

Fernando C.N. Pereira and David Warren. Parsing as deduction. In 21st Annual Meeting of the Association for Computational Linguistics, Cambridge Massachusetts, 1983.

Carl Pollard and Ivan Sag. Information Based Syntax and Semantics, Volume 1. Center for the Study of Language and Information Stanford, 1987.

Carl Pollard. Generalized Context-Free Grammars, Head Grammars, and Natural Language. PhD thesis, Stanford, 1984.

Mike Reape. A logical treatment of semi-free word order and bounded discontinuous constituency. In Fourth Conference of the European Chapter of the Association for Computational Linguistics, UMIST Manchester, 1989.

Mike Reape. Getting things in order. In Proceedings of the Symposium on Discontinuous Constituency, ITK Tilburg, 1990.

Mike Reape. Parsing bounded discontinuous constituents: Generalisations of some common algorithms. In Proceedings of the first CLIN dag. OTS RUU Utrecht, 1991. to appear.

Stuart M. Shieber, Gertjan van Noord, Robert C. Moore, and Fernando C.N. Pereira. A semantic-head-driven generation algorithm for unification based formalisms. In 27th Annual Meeting of the Association for Computational Linguistics, Vancouver, 1989.

Stuart M. Shieber, Gertjan van Noord, Robert C. Moore, and Fernando C.N. Pereira. Semantic-head-driven generation. Computational Linguistics, 16(1), 1990.

Stuart M. Shieber. Using restriction to extend parsing algorithms for complexfeature-based formalisms. In 23th Annual Meeting of the Association for Computational Linguistics, Chicago, 1985.

Stuart M. Shieber. Parsing and Type Inference for Natural and Computer Languages. PhD thesis, Menlo Park, 1989. Technical note 460.

Gertjan van Noord. BUG: A directed bottom-up generator for unification based formalisms. Working Papers in Natural Language Processing, Katholieke Universiteit Leuven, Stichting Taaltechnologie Utrecht, 4, 1989.

Gertjan van Noord. An overview of head-driven bottom-up generation. In Robert Dale, Chris Mellish, and Michael Zock, editors, Current Research in Natural Language Generation. Academic Press, 1990.

K. Vijay-Shankar and A. Joshi. Feature structure based tree adjoining grammar. In Proceedings of the 12th International Conference on Computational Linguistics (COLING), Budapest, 1988.

K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. Characterizing structural descriptions produced by various grammatical formalisms. In 25th Annual Meeting of the Association for Computational Linguistics, Stanford, 1987.

David J. Weir. Characterizing Mildly Context-Sensitive Grammar Formalisms. PhD thesis, Department of Computer and Information Science, University of Pennsylvania, 1988.

Henk Zeevat, Ewan Klein, and Jo Calder. Unification categorial grammar. In Nicholas Haddock, Ewan Klein, and Glyn Morrill, editors, Categorial Grammar, Unification Grammar and Parsing. Centre for Cognitive Science, University of Edinburgh, 1987. Volume 1 of Working Papers in Cognitive Science.