10   Feature Based Grammar

10.2.1   Syntactic Agreement

Consider the following contrasts:

In English, nouns are usually morphologically marked as being singular or plural. The form of the demonstrative also varies: this (singular) and these (plural). Examples (6b) and (7b) show that there are constraints on the use of demonstratives and nouns within a noun phrase: either both are singular or both are plural. A similar constraint holds between subjects and predicates:

Here we can see that morphological properties of the verb co-vary with syntactic properties of the subject noun phrase. This co-variance is called agreement. If we look further at verb agreement in English, we will see that present tense verbs typically have two inflected forms: one for third person singular, and another for every other combination of person and number:

We can make the role of morphological properties a bit more explicit as illustrated in runs and run. These representations indicate that the verb agrees with its subject in person and number. (We use "3" as an abbreviation for 3rd person, "SG" for singular and "PL" for plural.)

Let's see what happens when we encode these agreement constraints in a context-free grammar. We will begin with the simple CFG in (10).

s → np vp
np → Det n
vp → v

Det → 'this'
n → 'dog'
v → 'runs'

Example (10) allows us to generate the sentence this dog runs; however, what we really want to do is also generate these dogs run while blocking unwanted strings such as *this dogs run and *these dog runs. The most straightforward approach is to add new non-terminals and productions to the grammar:

S_SG → NP_SG VP_SG
S_PL → NP_PL VP_PL
NP_SG → Det_SG N_SG
NP_PL → Det_PL N_PL
VP_SG → V_SG
VP_PL → V_PL

Det_SG → 'this'
Det_PL → 'these'
N_SG → 'dog'
N_PL → 'dogs'
V_SG → 'runs'
V_PL → 'run'

It should be clear that this grammar will do the required task, but only at the cost of duplicating our previous set of productions.

10.2.2   Using Attributes and Constraints

We spoke informally of linguistic categories having properties; for example, that a noun has the property of being plural. Let's make this explicit:

N[num=pl]

In (12), we have introduced some new notation which says that the category N has a feature called num (short for 'number') and that the value of this feature is pl (short for 'plural'). We can add similar annotations to other categories, and use them in lexical entries:

Det[num=sg] → 'this'
Det[num=pl]  → 'these'
N[num=sg] → 'dog'
N[num=pl] → 'dogs'
V[num=sg] → 'runs'
V[num=pl] → 'run'

Does this help at all? So far, it looks just like a slightly more verbose alternative to what was specified in (11). Things become more interesting when we allow variables over feature values, and use these to state constraints:

S → NP[num=?n] VP[num=?n]

NP[num=?n] → Det[num=?n] N[num=?n]

VP[num=?n] → V[num=?n]

We are using "?n" as a variable over values of num; it can be instantiated either to sg or pl. Its scope is limited to individual productions. That is, within (14a), for example, ?n must be instantiated to the same constant value; we can read the production as saying that whatever value NP takes for the feature num, VP must take the same value.

In order to understand how these feature constraints work, it's helpful to think about how one would go about building a tree. Lexical productions will admit the following local trees (trees of depth one):

(15)

a. b.

(16)

a. b.

Now (14b) says that whatever the num values of N and Det are, they have to be the same. Consequently, (14b) will permit (15a) and (16a) to be combined into an NP as shown in (17a) and it will also allow (15b) and (16b) to be combined, as in (17b). By contrast, (18a) and (18b) are prohibited because the roots of their constituent local trees differ in their values for the num feature.

(17)

a. b.

(18)

a. b.

Production (14c) can be thought of as saying that the num value of the head verb has to be the same as the num value of the VP mother. Combined with (14a), we derive the consequence that if the num value of the subject head noun is pl, then so is the num value of the VP's head verb.

(19)

The grammar in listing 10.1 illustrates most of the ideas we have introduced so far in this chapter, plus a couple of new ones.

>>> nltk.data.show_cfg('grammars/feat0.fcfg')
% start S
# ############################
# Grammar Rules
# ############################
# S expansion rules
S -> NP[NUM=?n] VP[NUM=?n]
# NP expansion rules
NP[NUM=?n] -> N[NUM=?n]
NP[NUM=?n] -> PropN[NUM=?n]
NP[NUM=?n] -> Det[NUM=?n] N[NUM=?n]
NP[NUM=pl] -> N[NUM=pl]
# VP expansion rules
VP[TENSE=?t, NUM=?n] -> IV[TENSE=?t, NUM=?n]
VP[TENSE=?t, NUM=?n] -> TV[TENSE=?t, NUM=?n] NP
# ############################
# Lexical Rules
# ############################
Det[NUM=sg] -> 'this' | 'every'
Det[NUM=pl] -> 'these' | 'all'
Det -> 'the' | 'some'
PropN[NUM=sg]-> 'Kim' | 'Jody'
N[NUM=sg] -> 'dog' | 'girl' | 'car' | 'child'
N[NUM=pl] -> 'dogs' | 'girls' | 'cars' | 'children'
IV[TENSE=pres,  NUM=sg] -> 'disappears' | 'walks'
TV[TENSE=pres, NUM=sg] -> 'sees' | 'likes'
IV[TENSE=pres,  NUM=pl] -> 'disappear' | 'walk'
TV[TENSE=pres, NUM=pl] -> 'see' | 'like'
IV[TENSE=past, NUM=?n] -> 'disappeared' | 'walked'
TV[TENSE=past, NUM=?n] -> 'saw' | 'liked'

Notice that a syntactic category can have more than one feature; for example, v[tense=pres, num=pl]. In general, we can add as many features as we like.

Notice also that we have used feature variables in lexical entries as well as grammatical productions. For example, the has been assigned the category Det[num=?n]. Why is this? Well, you know that the definite article the can combine with both singular and plural nouns. One way of describing this would be to add two lexical entries to the grammar, one each for the singular and plural versions of the. However, a more elegant solution is to leave the num value underspecified and letting it agree in number with whatever noun it combines with.

A final detail about 10.1 is the statement %start S. This a "directive" that tells the parser to take s as the start symbol for the grammar.

In general, when we are trying to develop even a very small grammar, it is convenient to put the productions in a file where they can be edited, tested and revised. We have saved 10.1 as a file named 'feat0.fcfg' in the NLTK data distribution, and it can be accessed using nltk.data.load().

We can inspect the productions and the lexicon using the commands print g.earley_grammar() and pprint(g.earley_lexicon()).

Next, we can tokenize a sentence and use the nbest_parse() function to invoke the Earley chart parser.

>>> tokens = 'Kim likes children'.split()
>>> from nltk.parse import load_earley
>>> cp = load_earley('grammars/feat0.fcfg', trace=2)
>>> trees = cp.nbest_parse(tokens)
          |.K.l.c.|
Processing queue 0
Predictor |> . . .| [0:0] S[] -> * NP[NUM=?n] VP[NUM=?n] {}
Predictor |> . . .| [0:0] NP[NUM=?n] -> * N[NUM=?n] {}
Predictor |> . . .| [0:0] NP[NUM=?n] -> * PropN[NUM=?n] {}
Predictor |> . . .| [0:0] NP[NUM=?n] -> * Det[NUM=?n] N[NUM=?n] {}
Predictor |> . . .| [0:0] NP[NUM='pl'] -> * N[NUM='pl'] {}
Scanner   |[-] . .| [0:1] 'Kim'
Scanner   |[-] . .| [0:1] PropN[NUM='sg'] -> 'Kim' *
Processing queue 1
Completer |[-] . .| [0:1] NP[NUM='sg'] -> PropN[NUM='sg'] *
Completer |[-> . .| [0:1] S[] -> NP[NUM=?n] * VP[NUM=?n] {?n: 'sg'}
Predictor |. > . .| [1:1] VP[NUM=?n, TENSE=?t] -> * IV[NUM=?n, TENSE=?t] {}
Predictor |. > . .| [1:1] VP[NUM=?n, TENSE=?t] -> * TV[NUM=?n, TENSE=?t] NP[] {}
Scanner   |. [-] .| [1:2] 'likes'
Scanner   |. [-] .| [1:2] TV[NUM='sg', TENSE='pres'] -> 'likes' *
Processing queue 2
Completer |. [-> .| [1:2] VP[NUM=?n, TENSE=?t] -> TV[NUM=?n, TENSE=?t] * NP[] {?n: 'sg', ?t: 'pres'}
Predictor |. . > .| [2:2] NP[NUM=?n] -> * N[NUM=?n] {}
Predictor |. . > .| [2:2] NP[NUM=?n] -> * PropN[NUM=?n] {}
Predictor |. . > .| [2:2] NP[NUM=?n] -> * Det[NUM=?n] N[NUM=?n] {}
Predictor |. . > .| [2:2] NP[NUM='pl'] -> * N[NUM='pl'] {}
Scanner   |. . [-]| [2:3] 'children'
Scanner   |. . [-]| [2:3] N[NUM='pl'] -> 'children' *
Processing queue 3
Completer |. . [-]| [2:3] NP[NUM='pl'] -> N[NUM='pl'] *
Completer |. [---]| [1:3] VP[NUM='sg', TENSE='pres'] -> TV[NUM='sg', TENSE='pres'] NP[] *
Completer |[=====]| [0:3] S[] -> NP[NUM='sg'] VP[NUM='sg'] *
Completer |[=====]| [0:3] [INIT][] -> S[] *

Observe that the parser works directly with the underspecified productions given by the grammar. That is, the Predictor rule does not attempt to compile out all admissible feature combinations before trying to expand the non-terminals on the left hand side of a production. However, when the Scanner matches an input word against a lexical production that has been predicted, the new edge will typically contain fully specified features; e.g., the edge [PropN[num = sg] → 'Kim', (0, 1)]. Recall from Chapter 7 that the Fundamental (or Completer) Rule in standard CFGs is used to combine an incomplete edge that's expecting a nonterminal B with a following, complete edge whose left hand side matches B. In our current setting, rather than checking for a complete match, we test whether the expected category B will unify with the left hand side B' of a following complete edge. We will explain in more detail in Section 10.3 how unification works; for the moment, it is enough to know that as a result of unification, any variable values of features in B will be instantiated by constant values in the corresponding feature structure in B', and these instantiated values will be used in the new edge added by the Completer. This instantiation can be seen, for example, in the edge [np[num=sg] → PropN[num=sg] •, (0, 1)] in 10.2, where the feature num has been assigned the value sg.

Finally, we can inspect the resulting parse trees (in this case, a single one).

>>> for tree in trees: print tree
(S[]
  (NP[NUM='sg'] (PropN[NUM='sg'] Kim))
  (VP[NUM='sg', TENSE='pres']
    (TV[NUM='sg', TENSE='pres'] likes)
    (NP[NUM='pl'] (N[NUM='pl'] children))))

10.2.3   Terminology

So far, we have only seen feature values like sg and pl. These simple values are usually called atomic — that is, they can't be decomposed into subparts. A special case of atomic values are boolean values, that is, values that just specify whether a property is true or false of a category. For example, we might want to distinguish auxiliary verbs such as can, may, will and do with the boolean feature aux. Then our lexicon for verbs could include entries such as (20). (Note that we follow the convention that boolean features are not written f +, f - but simply +f, -f, respectively.)

V[tense=pres, +aux=+] → 'can'
V[tense=pres, +aux=+] → 'may'

V[tense=pres, -aux -] → 'walks'
V[tense=pres, -aux -] → 'likes'

We have spoken informally of attaching "feature annotations" to syntactic categories. A more general approach is to treat the whole category — that is, the non-terminal symbol plus the annotation — as a bundle of features. Consider, for example, the object we have written as (21).

n[num=sg]

The syntactic category n, as we have seen before, provides part of speech information. This information can itself be captured as a feature value pair, using pos to represent "part of speech":

[pos=N, num=sg]

In fact, we regard (22) as our "official" representation of a feature-based linguistic category, and (21) as a convenient abbreviation. A bundle of feature-value pairs is called a feature structure or an attribute value matrix (AVM). A feature structure that contains a specification for the feature pos is a linguistic category.

In addition to atomic-valued features, we allow features whose values are themselves feature structures. For example, we might want to group together agreement features (e.g., person, number and gender) as a distinguished part of a category, as shown in (23).

In this case, we say that the feature agr has a complex value.

There is no particular significance to the order of features in a feature structure. So (23) is equivalent to (23).

Once we have the possibility of using features like agr, we can refactor a grammar like 10.1 so that agreement features are bundled together. A tiny grammar illustrating this point is shown in (25).

s → np[agr=?n] vp[agr=?n]
np[agr=?n] → PropN[agr=?n]
vp[tense=?t, agr=?n] → Cop[tense=?t, agr=?n] Adj
Cop[tense=pres,  agr=[num=sg, per=3]] → 'is'
PropN[agr=[num=sg, per=3]] → 'Kim'
Adj → 'happy'

10.2.4   Exercises

1. ☼ What constraints are required to correctly parse strings like I am happy and she is happy but not *you is happy or *they am happy? Implement two solutions for the present tense paradigm of the verb be in English, first taking Grammar (11) as your starting point, and then taking Grammar (25) as the starting point.

2. ☼ Develop a variant of grammar 10.1 that uses a feature count to make the distinctions shown below:

   (26)

   a. The boy sings. b. *Boy sings.

   (27)

   a. The boys sing. b. Boys sing.

   (28)

   a. The boys sing. b. Boys sing.

   (29)

   a. The water is precious. b. Water is precious.

3. ◑ Develop a feature-based grammar that will correctly describe the following Spanish noun phrases:

   (30)

   un cuadro hermos-o INDEF.SG.MASC picture beautiful-SG.MASC 'a beautiful picture'

   (31)

   un-os cuadro-s hermos-os INDEF-PL.MASC picture-PL beautiful-PL.MASC 'beautiful pictures'

   (32)

   un-a cortina hermos-a INDEF-SG.FEM curtain beautiful-SG.FEM 'a beautiful curtain'

   (33)

   un-as cortina-s hermos-as INDEF-PL.FEM curtain beautiful-PL.FEM 'beautiful curtains'

4. ◑ Develop a wrapper for the earley_parser so that a trace is only printed if the input string fails to parse.

10.3.1   Feature Structures in Python

Feature structures are declared with the FeatStruct() constructor. Atomic feature values can be strings or integers.

>>> fs1 = nltk.FeatStruct(TENSE='past', NUM='sg')
>>> print fs1
[ NUM   = 'sg'   ]
[ TENSE = 'past' ]

A feature structure is actually just a kind of dictionary, and so we access its values by indexing in the usual way. We can use our familiar syntax to assign values to features:

>>> fs1 = nltk.FeatStruct(PER=3, NUM='pl', GND='fem')
>>> print fs1['GND']
fem
>>> fs1['CASE'] = 'acc'

We can also define feature structures that have complex values, as discussed earlier.

>>> fs2 = nltk.FeatStruct(POS='N', AGR=fs1)
>>> print fs2
[       [ CASE = 'acc' ] ]
[ AGR = [ GND  = 'fem' ] ]
[       [ NUM  = 'pl'  ] ]
[       [ PER  = 3     ] ]
[                        ]
[ POS = 'N'              ]
>>> print fs2['AGR']
[ CASE = 'acc' ]
[ GND  = 'fem' ]
[ NUM  = 'pl'  ]
[ PER  = 3     ]
>>> print fs2['AGR']['PER']
3

An alternative method of specifying feature structures is to use a bracketed string consisting of feature-value pairs in the format feature=value, where values may themselves be feature structures:

>>> nltk.FeatStruct("[POS='N', AGR=[PER=3, NUM='pl', GND='fem']]")
[AGR=[GND='fem', NUM='pl', PER=3], POS='N']

10.3.2   Feature Structures as Graphs

Feature structures are not inherently tied to linguistic objects; they are general purpose structures for representing knowledge. For example, we could encode information about a person in a feature structure:

>>> person01 = nltk.FeatStruct(name='Lee', telno='01 27 86 42 96', age=33)

It is sometimes helpful to view feature structures as graphs; more specifically, directed acyclic graphs (DAGs). (35) is equivalent to the AVM (34).

(35)

The feature names appear as labels on the directed arcs, and feature values appear as labels on the nodes that are pointed to by the arcs.

Just as before, feature values can be complex:

(36)

When we look at such graphs, it is natural to think in terms of paths through the graph. A feature path is a sequence of arcs that can be followed from the root node. We will represent paths as tuples. Thus, ('address', 'street') is a feature path whose value in (36) is the string "rue Pascal".

Now let's consider a situation where Lee has a spouse named "Kim", and Kim's address is the same as Lee's. We might represent this as (37).

(37)

However, rather than repeating the address information in the feature structure, we can "share" the same sub-graph between different arcs:

(38)

In other words, the value of the path ('ADDRESS') in (38) is identical to the value of the path ('SPOUSE', 'ADDRESS'). DAGs such as (38) are said to involve structure sharing or reentrancy. When two paths have the same value, they are said to be equivalent.

>>> fs = nltk.FeatStruct("""[NAME='Lee', ADDRESS=(1)[NUMBER=74, STREET='rue Pascal'],
...                         SPOUSE=[NAME='Kim', ADDRESS->(1)]]""")
>>> print fs
[ ADDRESS = (1) [ NUMBER = 74           ] ]
[               [ STREET = 'rue Pascal' ] ]
[                                         ]
[ NAME    = 'Lee'                         ]
[                                         ]
[ SPOUSE  = [ ADDRESS -> (1)  ]           ]
[           [ NAME    = 'Kim' ]           ]

This is similar to more conventional displays of AVMs, as shown in (39).

The bracketed integer is sometimes called a tag or a coindex. The choice of integer is not significant. There can be any number of tags within a single feature structure.

>>> fs1 = nltk.FeatStruct("[A='a', B=(1)[C='c'], D->(1), E->(1)]")

It is standard to think of feature structures as providing partial information about some object, in the sense that we can order feature structures according to how general they are. For example, (41a) is more general (less specific) than (41b), which in turn is more general than (41c).

This ordering is called subsumption; a more general feature structure subsumes a less general one. If FS₀ subsumes FS₁ (formally, we write FS₀ ⊑ FS₁), then FS₁ must have all the paths and path equivalences of FS₀, and may have additional paths and equivalences as well. Thus, (37) subsumes (38), since the latter has additional path equivalences.. It should be obvious that subsumption only provides a partial ordering on feature structures, since some feature structures are incommensurable. For example, (42) neither subsumes nor is subsumed by (41a).

So we have seen that some feature structures are more specific than others. How do we go about specializing a given feature structure? For example, we might decide that addresses should consist of not just a street number and a street name, but also a city. That is, we might want to merge graph (43b) with (43a) to yield (43c).

(43)

a. b. c.

Merging information from two feature structures is called unification and is supported by the unify() method.

>>> fs1 = nltk.FeatStruct(NUMBER=74, STREET='rue Pascal')
>>> fs2 = nltk.FeatStruct(CITY='Paris')
>>> print fs1.unify(fs2)
[ CITY   = 'Paris'      ]
[ NUMBER = 74           ]
[ STREET = 'rue Pascal' ]

>>> print fs2.unify(fs1)
[ CITY   = 'Paris'      ]
[ NUMBER = 74           ]
[ STREET = 'rue Pascal' ]

For example, the result of unifying (41b) with (41c) is (41c).

Unification between FS₀ and FS₁ will fail if the two feature structures share a path π, but the value of π in FS₀ is a distinct atom from the value of π in FS₁. This is implemented by setting the result of unification to be None.

>>> fs0 = nltk.FeatStruct(A='a')
>>> fs1 = nltk.FeatStruct(A='b')
>>> fs2 = fs0.unify(fs1)
>>> print fs2
None

Now, if we look at how unification interacts with structure-sharing, things become really interesting. First, let's define (37) in Python:

>>> fs0 = nltk.FeatStruct("""[NAME=Lee,
...                           ADDRESS=[NUMBER=74,
...                                    STREET='rue Pascal'],
...                           SPOUSE= [NAME=Kim,
...                                    ADDRESS=[NUMBER=74,
...                                             STREET='rue Pascal']]]""")

What happens when we augment Kim's address with a specification for city? (Notice that fs1 includes the whole path from the root of the feature structure down to city.)

>>> fs1 = nltk.FeatStruct("[SPOUSE = [ADDRESS = [CITY = Paris]]]")

(47) shows the result of unifying fs0 with fs1:

By contrast, the result is very different if fs1 is unified with the structure-sharing version fs2 (also shown as (38)):

>>> fs2 = nltk.FeatStruct("""[NAME=Lee, ADDRESS=(1)[NUMBER=74, STREET='rue Pascal'],
...                           SPOUSE=[NAME=Kim, ADDRESS->(1)]]""")

Rather than just updating what was in effect Kim's "copy" of Lee's address, we have now updated both their addresses at the same time. More generally, if a unification involves specializing the value of some path π, then that unification simultaneously specializes the value of any path that is equivalent to π.

As we have already seen, structure sharing can also be stated using variables such as ?x.

>>> fs1 = nltk.FeatStruct("[ADDRESS1=[NUMBER=74, STREET='rue Pascal']]")
>>> fs2 = nltk.FeatStruct("[ADDRESS1=?x, ADDRESS2=?x]")
>>> print fs2
[ ADDRESS1 = ?x ]
[ ADDRESS2 = ?x ]
>>> print fs2.unify(fs1)
[ ADDRESS1 = (1) [ NUMBER = 74           ] ]
[                [ STREET = 'rue Pascal' ] ]
[                                          ]
[ ADDRESS2 -> (1)                          ]

10.3.4   Exercises

1. ☼ Write a function subsumes() which holds of two feature structures fs1 and fs2 just in case fs1 subsumes fs2.

2. ◑ Consider the feature structures shown in Listing 10.3.

   [XX]	NOTE: This example is somewhat broken -- nltk doesn't support reentrance for base feature values. (See email ~7/23/08 to the nltk-users mailing list for details.)

   fs1 = nltk.FeatStruct("[A = (1)b, B= [C ->(1)]]") fs2 = nltk.FeatStruct("[B = [D = d]]") fs3 = nltk.FeatStruct("[B = [C = d]]") fs4 = nltk.FeatStruct("[A = (1)[B = b], C->(1)]") fs5 = nltk.FeatStruct("[A = [D = (1)e], C = [E -> (1)] ]") fs6 = nltk.FeatStruct("[A = [D = (1)e], C = [B -> (1)] ]") fs7 = nltk.FeatStruct("[A = [D = (1)e, F = (2)[]], C = [B -> (1), E -> (2)] ]") fs8 = nltk.FeatStruct("[A = [B = b], C = [E = [G = e]]]") fs9 = nltk.FeatStruct("[A = (1)[B = b], C -> (1)]")

   Listing 10.3 (featstructures.py)

   Work out on paper what the result is of the following unifications. (Hint: you might find it useful to draw the graph structures.)

   1. fs1 and fs2
   2. fs1 and fs3
   3. fs4 and fs5
   4. fs5 and fs6
   5. fs7 and fs8
   6. fs7 and fs9

   Check your answers using Python.

3. ◑ List two feature structures that subsume [A=?x, B=?x].

4. ◑ Ignoring structure sharing, give an informal algorithm for unifying two feature structures.

10.4.1   Subcategorization

In Chapter 7, we proposed to augment our category labels to represent different kinds of verb. We introduced labels such as iv and tv for intransitive and transitive verbs respectively. This allowed us to write productions like the following:

vp → iv
vp → tv np

Although we know that iv and tv are two kinds of v, from a formal point of view iv has no closer relationship with tv than it does with np. As it stands, iv and tv are just atomic nonterminal symbols from a CFG. This approach doesn't allow us to say anything about the class of verbs in general. For example, we cannot say something like "All lexical items of category v can be marked for tense", since bark, say, is an item of category iv, not v. A simple solution, originally developed for a grammar framework called Generalized Phrase Structure Grammar (GPSG), stipulates that lexical categories may bear a subcat feature whose values are integers. This is illustrated in a modified portion of 10.1, shown in (50).

VP[TENSE=?t, NUM=?n] -> V[SUBCAT=0, TENSE=?t, NUM=?n]
VP[TENSE=?t, NUM=?n] -> V[SUBCAT=1, TENSE=?t, NUM=?n] NP
VP[TENSE=?t, NUM=?n] -> V[SUBCAT=2, TENSE=?t, NUM=?n] Sbar

V[SUBCAT=0, TENSE=pres, NUM=sg] -> 'disappears' | 'walks'
V[SUBCAT=1, TENSE=pres, NUM=sg] -> 'sees' | 'likes'
V[SUBCAT=2, TENSE=pres, NUM=sg] -> 'says' | 'claims'

V[SUBCAT=0, TENSE=pres, NUM=pl] -> 'disappear' | 'walk'
V[SUBCAT=1, TENSE=pres, NUM=pl] -> 'see' | 'like'
V[SUBCAT=2, TENSE=pres, NUM=pl] -> 'say' | 'claim'

V[SUBCAT=0, TENSE=past, NUM=?n] -> 'disappeared' | 'walked'
V[SUBCAT=1, TENSE=past, NUM=?n] -> 'saw' | 'liked'
V[SUBCAT=2, TENSE=past, NUM=?n] -> 'said' | 'claimed'

When we see a lexical category like v[subcat 1], we can interpret the subcat specification as a pointer to the production in which v[subcat 1] is introduced as the head daughter in a vp production. By convention, there is a one-to-one correspondence between subcat values and the productions that introduce lexical heads. It's worth noting that the choice of integer which acts as a value for subcat is completely arbitrary — we could equally well have chosen 3999, 113 and 57 as our two values in (50). On this approach, subcat can only appear on lexical categories; it makes no sense, for example, to specify a subcat value on vp.

In our third class of verbs above, we have specified a category s-bar. This is a label for subordinate clauses such as the complement of claim in the example You claim that you like children. We require two further productions to analyze such sentences:

S-BAR -> Comp S
Comp -> 'that'

The resulting structure is the following.

(52)

An alternative treatment of subcategorization, due originally to a framework known as categorial grammar, is represented in feature-based frameworks such as PATR and Head-driven Phrase Structure Grammar. Rather than using subcat values as a way of indexing productions, the subcat value directly encodes the valency of a head (the list of arguments that it can combine with). For example, a verb like put that takes np and pp complements (put the book on the table) might be represented as (53):

This says that the verb can combine with three arguments. The leftmost element in the list is the subject np, while everything else — an np followed by a pp in this case — comprises the subcategorized-for complements. When a verb like put is combined with appropriate complements, the requirements which are specified in the subcat are discharged, and only a subject np is needed. This category, which corresponds to what is traditionally thought of as vp, might be represented as follows.

Finally, a sentence is a kind of verbal category that has no requirements for further arguments, and hence has a subcat whose value is the empty list. The tree (55) shows how these category assignments combine in a parse of Kim put the book on the table.

(55)

10.4.2   Heads Revisited

We noted in the previous section that by factoring subcategorization information out of the main category label, we could express more generalizations about properties of verbs. Another property of this kind is the following: expressions of category v are heads of phrases of category vp. Similarly (and more informally) ns are heads of nps, as (i.e., adjectives) are heads of aps, and ps (i.e., adjectives) are heads of pps. Not all phrases have heads — for example, it is standard to say that coordinate phrases (e.g., the book and the bell) lack heads — nevertheless, we would like our grammar formalism to express the mother / head-daughter relation where it holds. Now, although it looks as though there is something in common between, say, v and vp, this is more of a handy convention than a real claim, since v and vp formally have no more in common than v and Det.

X-bar syntax (cf. [Jacobs & Rosenbaum, 1970], [Jackendoff, 1977]) addresses this issue by abstracting out the notion of phrasal level. It is usual to recognize three such levels. If n represents the lexical level, then n' represents the next level up, corresponding to the more traditional category Nom, while n'' represents the phrasal level, corresponding to the category np. (The primes here replace the typographically more demanding horizontal bars of [Jacobs & Rosenbaum, 1970]). (56) illustrates a representative structure.

(56)

The head of the structure (56) is n while n' and n'' are called (phrasal) projections of n. n'' is the maximal projection, and n is sometimes called the zero projection. One of the central claims of X-bar syntax is that all constituents share a structural similarity. Using x as a variable over n, v, a and p, we say that directly subcategorized complements of the head are always placed as sisters of the lexical head, whereas adjuncts are placed as sisters of the intermediate category, x'. Thus, the configuration of the p'' adjunct in (57) contrasts with that of the complement p'' in (56).

(57)

The productions in (58) illustrate how bar levels can be encoded using feature structures.

s → n[bar=2] v[bar=2]
n[bar=2] → Det n[bar=1]
n[bar=1] → n[bar=1] p[bar=2]
n[bar=1] → n[bar=0] p[bar=2]

10.4.3   Auxiliary Verbs and Inversion

Inverted clauses — where the order of subject and verb is switched — occur in English interrogatives and also after 'negative' adverbs:

However, we cannot place just any verb in pre-subject position:

Verbs that can be positioned initially in inverted clauses belong to the class known as auxiliaries, and as well as do, can and have include be, will and shall. One way of capturing such structures is with the following production:

S[+inv] -> V[+AUX] NP VP

That is, a clause marked as [+inv] consists of an auxiliary verb followed by a vp. (In a more detailed grammar, we would need to place some constraints on the form of the vp, depending on the choice of auxiliary.) (64) illustrates the structure of an inverted clause.

(64)

10.4.4   Unbounded Dependency Constructions

Consider the following contrasts:

The verb like requires an np complement, while put requires both a following np and pp. Examples (65) and (66) show that these complements are obligatory: omitting them leads to ungrammaticality. Yet there are contexts in which obligatory complements can be omitted, as (67) and (68) illustrate.

That is, an obligatory complement can be omitted if there is an appropriate filler in the sentence, such as the question word who in (67a), the preposed topic this music in (67b), or the wh phrases which card/slot in (68). It is common to say that sentences like (67) – (68) contain gaps where the obligatory complements have been omitted, and these gaps are sometimes made explicit using an underscore:

So, a gap can occur if it is licensed by a filler. Conversely, fillers can only occur if there is an appropriate gap elsewhere in the sentence, as shown by the following examples.

The mutual co-occurence between filler and gap leads to (67) – (68) is sometimes termed a "dependency". One issue of considerable importance in theoretical linguistics has been the nature of the material that can intervene between a filler and the gap that it licenses; in particular, can we simply list a finite set of strings that separate the two? The answer is No: there is no upper bound on the distance between filler and gap. This fact can be easily illustrated with constructions involving sentential complements, as shown in (72).

Since we can have indefinitely deep recursion of sentential complements, the gap can be embedded indefinitely far inside the whole sentence. This constellation of properties leads to the notion of an unbounded dependency construction; that is, a filler-gap dependency where there is no upper bound on the distance between filler and gap.

A variety of mechanisms have been suggested for handling unbounded dependencies in formal grammars; we shall adopt an approach due to Generalized Phrase Structure Grammar that involves something called slash categories. A slash category is something of the form y/xp; we interpret this as a phrase of category y that is missing a sub-constituent of category xp. For example, s/np is an s that is missing an np. The use of slash categories is illustrated in (73).

(73)

The top part of the tree introduces the filler who (treated as an expression of category np[+wh]) together with a corresponding gap-containing constituent s/np. The gap information is then "percolated" down the tree via the vp/np category, until it reaches the category np/np. At this point, the dependency is discharged by realizing the gap information as the empty string e immediately dominated by np/np.

Do we need to think of slash categories as a completely new kind of object in our grammars? Fortunately, no, we don't — in fact, we can accommodate them within our existing feature-based framework. We do this by treating slash as a feature, and the category to its right as a value. In other words, our "official" notation for s/np will be s[slash=NP]. Once we have taken this step, it is straightforward to write a small grammar for analyzing unbounded dependency constructions. 10.4 illustrates the main principles of slash categories, and also includes productions for inverted clauses. To simplify presentation, we have omitted any specification of tense on the verbs.

>>> nltk.data.show_cfg('grammars/feat1.fcfg')
% start S
# ############################
# Grammar Rules
# ############################
S[-INV] -> NP  S/NP
S[-INV]/?x -> NP VP/?x
S[+INV]/?x -> V[+AUX] NP VP/?x
S-BAR/?x -> Comp S[-INV]/?x
NP/NP ->
VP/?x -> V[SUBCAT=1, -AUX] NP/?x
VP/?x -> V[SUBCAT=2, -AUX] S-BAR/?x
VP/?x -> V[SUBCAT=3, +AUX] VP/?x
# ############################
# Lexical Rules
# ############################
V[SUBCAT=1, -AUX] -> 'see' | 'like'
V[SUBCAT=2, -AUX] -> 'say' | 'claim'
V[SUBCAT=3, +AUX] -> 'do' | 'can'
NP[-WH] -> 'you' | 'children' | 'girls'
NP[+WH] -> 'who'
Comp -> 'that'

The grammar in Listing 10.4 contains one gap-introduction production, namely

s[-inv] → np s/np

In order to percolate the slash feature correctly, we need to add slashes with variable values to both sides of the arrow in productions that expand s, vp and np. For example,

vp/?x → v s-bar/?x

says that a slash value can be specified on the vp mother of a constituent if the same value is also specified on the s-bar daughter. Finally, (76) allows the slash information on np to be discharged as the empty string.

np/np →

Using 10.4, we can parse the string who do you claim that you like into the tree shown in (77).

(77)

10.4.5   Case and Gender in German

Compared with English, German has a relatively rich morphology for agreement. For example, the definite article in German varies with case, gender and number, as shown in Table 10.2.

Table 10.2:

Morphological Paradigm for the German definite Article

Subjects in German take the nominative case, and most verbs govern their objects in the accusative case. However, there are exceptions like helfen that govern the dative case:

The grammar 10.5 illustrates the interaction of agreement (comprising person, number and gender) with case.

>>> nltk.data.show_cfg('grammars/german.fcfg')
% start S
# Grammar Rules
S -> NP[CASE=nom, AGR=?a] VP[AGR=?a]
NP[CASE=?c, AGR=?a] -> PRO[CASE=?c, AGR=?a]
NP[CASE=?c, AGR=?a] -> Det[CASE=?c, AGR=?a] N[CASE=?c, AGR=?a]
VP[AGR=?a] -> IV[AGR=?a]
VP[AGR=?a] -> TV[OBJCASE=?c, AGR=?a] NP[CASE=?c]
# Lexical Rules
# Singular determiners
# masc
Det[CASE=nom, AGR=[GND=masc,PER=3,NUM=sg]] -> 'der'
Det[CASE=dat, AGR=[GND=masc,PER=3,NUM=sg]] -> 'dem'
Det[CASE=acc, AGR=[GND=masc,PER=3,NUM=sg]] -> 'den'
# fem
Det[CASE=nom, AGR=[GND=fem,PER=3,NUM=sg]] -> 'die'
Det[CASE=dat, AGR=[GND=fem,PER=3,NUM=sg]] -> 'der'
Det[CASE=acc, AGR=[GND=fem,PER=3,NUM=sg]] -> 'die'
# Plural determiners
Det[CASE=nom, AGR=[PER=3,NUM=pl]] -> 'die'
Det[CASE=dat, AGR=[PER=3,NUM=pl]] -> 'den'
Det[CASE=acc, AGR=[PER=3,NUM=pl]] -> 'die'
# Nouns
N[AGR=[GND=masc,PER=3,NUM=sg]] -> 'hund'
N[CASE=nom, AGR=[GND=masc,PER=3,NUM=pl]] -> 'hunde'
N[CASE=dat, AGR=[GND=masc,PER=3,NUM=pl]] -> 'hunden'
N[CASE=acc, AGR=[GND=masc,PER=3,NUM=pl]] -> 'hunde'
N[AGR=[GND=fem,PER=3,NUM=sg]] -> 'katze'
N[AGR=[GND=fem,PER=3,NUM=pl]] -> 'katzen'
# Pronouns
PRO[CASE=nom, AGR=[PER=1,NUM=sg]] -> 'ich'
PRO[CASE=acc, AGR=[PER=1,NUM=sg]] -> 'mich'
PRO[CASE=dat, AGR=[PER=1,NUM=sg]] -> 'mir'
PRO[CASE=nom, AGR=[PER=2,NUM=sg]] -> 'du'
PRO[CASE=nom, AGR=[PER=3,NUM=sg]] -> 'er' | 'sie' | 'es'
PRO[CASE=nom, AGR=[PER=1,NUM=pl]] -> 'wir'
PRO[CASE=acc, AGR=[PER=1,NUM=pl]] -> 'uns'
PRO[CASE=dat, AGR=[PER=1,NUM=pl]] -> 'uns'
PRO[CASE=nom, AGR=[PER=2,NUM=pl]] -> 'ihr'
PRO[CASE=nom, AGR=[PER=3,NUM=pl]] -> 'sie'
# Verbs
IV[AGR=[NUM=sg,PER=1]] -> 'komme'
IV[AGR=[NUM=sg,PER=2]] -> 'kommst'
IV[AGR=[NUM=sg,PER=3]] -> 'kommt'
IV[AGR=[NUM=pl, PER=1]] -> 'kommen'
IV[AGR=[NUM=pl, PER=2]] -> 'kommt'
IV[AGR=[NUM=pl, PER=3]] -> 'kommen'
TV[OBJCASE=acc, AGR=[NUM=sg,PER=1]] -> 'sehe' | 'mag'
TV[OBJCASE=acc, AGR=[NUM=sg,PER=2]] -> 'siehst' | 'magst'
TV[OBJCASE=acc, AGR=[NUM=sg,PER=3]] -> 'sieht' | 'mag'
TV[OBJCASE=dat, AGR=[NUM=sg,PER=1]] -> 'folge' | 'helfe'
TV[OBJCASE=dat, AGR=[NUM=sg,PER=2]] -> 'folgst' | 'hilfst'
TV[OBJCASE=dat, AGR=[NUM=sg,PER=3]] -> 'folgt' | 'hilft'

As you will see, the feature objcase is used to

specify the case that the verb governs on its object.

10.4.6   Exercises

1. ☼ Modify the grammar illustrated in (50) to incorporate a bar feature for dealing with phrasal projections.

2. ☼ Modify the German grammar in 10.5 to incorporate the treatment of subcategorization presented in 10.4.1.

3. ◑ Extend the German grammar in 10.5 so that it can handle so-called verb-second structures like the following:

   (79)

   Heute sieht der hund die katze.

4. ★ Morphological paradigms are rarely completely regular, in the sense of every cell in the matrix having a different realization. For example, the present tense conjugation of the lexeme walk only has two distinct forms: walks for the 3rd person singular, and walk for all other combinations of person and number. A successful analysis should not require redundantly specifying that 5 out of the 6 possible morphological combinations have the same realization. Propose and implement a method for dealing with this.

5. ★ So-called head features are shared between the mother and head daughter. For example, tense is a head feature that is shared between a vp and its head v daughter. See [Gazdar et al, 1985] for more details. Most of the features we have looked at are head features — exceptions are subcat and slash. Since the sharing of head features is predictable, it should not need to be stated explicitly in the grammar productions. Develop an approach that automatically accounts for this regular behavior of head features.