12.4.4 Heads and Head Finding

We suggested informally earlier that syntactic constituents could be associated with a lexical head; N is the head of an NP, V is the head of a VP. This idea of a head for each constituent dates back to Bloomfield (1914). It is central to such linguistic formalisms such as Head-Driven Phrase Structure Grammar (Pollard and Sag, 1994), and has become extremely popular in computational linguistics with the rise of lexicalized grammars (Ch. 14).

In one simple model of lexical heads, each context-free rule is associated with a head (Charniak, 1997; Collins, 1999). The head is the word in the phrase which is grammatically the most important. Heads are passed up the parse tree; thus each non-terminal in a parse-tree is annotated with a single word which is its lexical head. Fig. 12.12 shows an example of such a tree from Collins (1999), in which each non-terminal is annotated with its head. “Workers dumped sacks into a bin” is a shortened form of a WSJ sentence.

In order to generate such a tree, each CFG rule must be augmented to identify one right-hand-side constituent to be the head daughter. The headword for a node is then set to the headword of its head daughter. Choosing these head daughters is simple for textbook examples (NN is the head of NP) but is complicated and indeed controversial for most phrases. (Should the complementizer to or the verb be the head of an infinite verb-phrase?) Modern linguistic theories of syntax generally include a component that defines heads (see e.g., Pollard and Sag, 1994).

An alternative approach to head-finding is used in most practical computational systems. Instead of specifying head rules in the grammar itself, heads are identified dynamically in the context of trees for specific sentences. In other words, once a sentence is parsed, the resulting tree is walked to decorate each node with the appropriate head. Most current systems rely on a simple set of hand-written rules, such as a practical one for Penn Treebank grammars given in Collins (1999) but developed originally by Magerman (1995). For example their rule for finding the head of an NP is as follows Collins (1999, 238):

• If the last word is tagged POS, return last-word.

• Else search from right to left for the first child which is an NN, NNP, NNPS, NX, POS, or JJR.

• Else search from left to right for the first child which is an NP.

• Else search from right to left for the first child which is a $$, ADJP, or PRN.

• Else search from right to left for the first child which is a CD.

• Else search from right to left for the first child which is a JJ, JJS, RB or QP.

• Else return the last word

Selected other rules from their set are shown in Fig. 12.13. For example, for VP rules of the form $ VP \to Y_1 \cdots Y_n $, the algorithm would start from the left of $ Y_1 \cdots Y_n $ looking for the first $ Y_i $ of type TO; if no TOs are found it would search for the first $ Y_i $ of type VBD; if no VBDs are found it would search for a VBP, and so on. See Collins (1999) for more details.

| Parent Non-terminal | Direction | Priority List |

| --- | --- | --- |

| ADJP | Left | NNS QP NN $ ADVP JJ VBN VBG ADJP JJR NP JJS DT\nFW RBR RBS SBAR RB |

| ADVP | Right | RB RBR RBS FW ADVP TO CD JJR JJ IN NP JJS NN |

| PRN | Left | |

| PRT | Right | RP |

| QP | Left | $ IN NNS NN JJ RB DT CD NCD QP JJR JJS |

| S | Left | TO IN VP S SBAR ADJP UCP NP |

| SBAR | Left | WHNP WHPP WHADVP WHADJP IN DT S SQ SINV\nSBAR FRAG |

| VP | Left | TO VBD VBN MD VBZ VB VBG VBP VP ADJP NN NNS\nNP |

| Figure 12.13 Selected head rules from Collins (1999). The set of head rules is often | | |

12.5 GRAMMAR EQUIVALENCE AND NORMAL FORM

A formal language is defined as a (possibly infinite) set of strings of words. This suggests that we could ask if two grammars are equivalent by asking if they generate the same set of strings. In fact it is possible to have two distinct context-free grammars generate the same language.

We usually distinguish two kinds of grammar equivalence: weak equivalence and strong equivalence. Two grammars are strongly equivalent if they generate the same set of strings and if they assign the same phrase structure to each sentence (allowing merely for renaming of the non-terminal symbols). Two grammars are weakly equivalent if they generate the same set of strings but do not assign the same phrase structure to each sentence.

It is sometimes useful to have a normal form for grammars, in which each of the productions takes a particular form. For example a context-free grammar is in Chomsky Normal Form (CNF) (Chomsky, 1963) if it is $ \varepsilon $-free and if in addition each production is either of the form $ A \to B $ C or $ A \to a $. That is, the right-hand side of each rule either has two non-terminal symbols or one terminal symbol. Chomsky normal form grammars are binary branching, i.e. have binary trees (down to the prelexical nodes). We will make use of this binary branching property in the CKY parsing algorithm in Ch. 13.

Any grammar can be converted into a weakly-equivalent Chomsky normal form

grammar. For example, a rule of the form

$$ A\to B\;C\;D $$

can be converted into the following two CNF rules (Exercise 12.11 asks the reader to formulate the complete algorithm):

$$ \begin{array}{l}A\rightarrow B X\\ X\rightarrow C D\end{array} $$

Sometimes using binary branching can actually produce smaller grammars. For example the sentences that might be characterized as follows:

VP -> VBD NP PP*

are represented in the Penn Treebank by this series of rules:

VP $ \rightarrow $ VBD PP

VP $ \rightarrow $ VBD PP PP

VP $ \rightarrow $ VBD PP PP PP

VP $ \rightarrow $ VBD PP PP PP PP

...

but could also be generated by the following two-rule grammar:

(12.12)

VP $ \rightarrow $ VBD PP

VP $ \rightarrow $ VP PP

To generate a symbol A with a potentially infinite sequence of symbols B by using a rule of the form $ A \rightarrow A $ B is known as Chomsky-adjunction.

12.6 FINITE-STATE AND CONTEXT-FREE GRAMMARS

We argued in Sec. 12.1 that adequate models of grammar need to be able to represent complex interrelated facts about constituency, subcategorization, and dependency relations, and we implied that at the least the power of context-free grammars is needed to accomplish this. But why is it that we can't just use finite-state methods to capture these syntactic facts? The answer to this question is critical since, as we'll see in Ch. 13, there is a considerable price to be paid in terms of processing speed when one switches from regular languages to context-free ones.

There are two answers to this question. The first is mathematical; we'll show in Ch. 15 that given certain assumptions, that certain syntactic structures present in English (and other natural languages) make them not regular languages. The second answer is more subjective and has to do with notions of expressiveness; even when finite-state methods are capable of dealing with the syntactic facts in question, they often don't express them in ways that make generalizations obvious, lead to understandable formalisms, or produce structures of immediate use in subsequent semantic processing.

The mathematical objection will be discussed more fully in Ch. 15, but we’ll briefly review it here. We mentioned in passing in Ch. 2 that there is a completely equivalent

alternative to finite-state machines and regular expressions for describing regular languages, called regular grammars. The rules in a regular grammar are a restricted form of the rules in a context-free grammar because they are in right-linear or left-linear form. In a right-linear grammar, for example, the rules are all of the form $ A \to w * $ or $ A \to w * B $, that is the non-terminals either expand to a string of terminals or to a string of terminals followed by a non-terminal. These rules look an awful lot like the rules we've been using throughout this chapter, so what can't they do? What they can't do is express recursive center-embedding rules like the following, where a non-terminal is rewritten as itself, surrounded by (non-empty) strings:

$$ A\overset{*}{\Rightarrow}\alpha A\beta $$

In other words, a language can be generated by a finite-state machine if and only if the grammar that generates L that does not have any center-embedded recursions of this form (Chomsky, 1959; Bar-Hillel et al., 1961; Nederhof, 2000). Intuitively, this is because grammar rules in which the non-terminal symbols are always on either the right or left edge of a rule can be processed iteratively rather than recursively. Such center-embedding rules are needed to deal with artificial problems such as the language $ a^{n}b^{n} $, or for practical problems such as checking for correctly matching delimiters in programming and markup languages. It turns out that there are no slam-dunk examples of this for English, but examples like the following give a flavor of the problem.

(12.14) The luggage arrived.

(12.15) The luggage that the passengers checked arrived.

(12.16) The luggage that the passengers that the storm delayed checked arrived.

At least in theory, this kind of embedding could go on, although it gets increasingly difficult to process such examples and they are luckily fairly rare outside textbooks like this one. Ch. 15 will discuss this and related issues as to whether or not even context-free grammars are up to the task.

So is there no role for finite-state methods in syntactic analysis? A quick review of the rules used for noun-phrases in this chapter, as well as those used in the Penn treebank grammar, reveals that a considerable portion of them can be handled by finite-state methods. Consider the following rule for a noun group, the pre-nominal and nominal portions of a noun phrase:

$$ Nominal\rightarrow(Det)(Card)(Ord)(Quant)(AP)Nominal $$

Assuming we convert the pre-nominal elements of this rule into terminals, this rule is effectively right-linear and can be captured by a finite-state machine. Indeed, it is possible to automatically build a regular grammar which is an approximation of a given context-free grammar; see the references at the end of the chapter. Thus for many practical purposes where matching syntactic and semantic rules aren't necessary, finite-state rules are quite sufficient.

12.7 DEPENDENCY GRAMMARS

We have focused in this chapter on context-free grammars because many available treebanks and parsers produce these kinds of syntactic representation. But in a class of grammar formalisms called dependency grammars that are becoming quite important in speech and language processing, constituents and phrase-structure rules do not play any fundamental role. Instead, the syntactic structure of a sentence is described purely in terms of words and binary semantic or syntactic relations between these words. Dependency grammars often draw heavily from the work of Tesnière (1959), and the name dependency might have been used first by early computational linguist David Hays. But this lexical dependency notion of grammar is in fact older than the relatively recent phrase-structure or constituency grammars, and has its roots in the ancient Greek and Indian linguistic traditions. Indeed the notion in traditional grammar of “parsing a sentence into subject and predicate” is based on lexical relations rather than constituent relations.

Fig. 12.14 shows an example parse of the sentence I gave him my address, using the dependency grammar formalism of Järvinen and Tapanainen (1997) and Karlsson et al. (1995). Note that there are no non-terminal or phrasal nodes; each link in the parse tree holds between two lexical nodes (augmented with the special node). The links are drawn from a fixed inventory of around 35 relations, most of which roughly represent grammatical functions or very general semantic relations. Other dependency-based computational grammars, such as Link Grammar (Sleator and Temperley, 1993), use different but roughly overlapping links. The following table shows a few of the relations used in Järvinen and Tapanainen (1997):

As we will see in Ch. 14, one advantage of dependency formalisms is the strong

predictive parsing power that words have for their dependents. Knowing the identity of the verb is often a very useful cue for deciding which noun is likely to be the subject or the object. Dependency grammar researchers argue that one of the main advantages of pure dependency grammars is their ability to handle languages with relatively free word order. For example the word order in languages like Czech is much more flexible than in English; an object might occur before or after a location adverbial or a comp. A phrase-structure grammar would need a separate rule for each possible place in the parse tree that such an adverbial phrase could occur. A dependency grammar would just have one link-type representing this particular adverbial relation. Thus a dependency grammar abstracts away from word-order variation, representing only the information that is necessary for the parse.

There are a number of computational implementations of dependency grammars; Link Grammar (Sleator and Temperley, 1993) and Constraint Grammar (Karlsson et al., 1995) are easily-available broad-coverage dependency grammars and parsers for English. Dependency grammars are also often used for other languages. Hajič (1998), for example, describes the 500,000 word Prague Dependency Treebank for Czech which has been used to train probabilistic dependency parsers (Collins et al., 1999).