8.1.1 Context free grammars with features

As a first example, let's see how extra arguments can be used to add features to context-free grammars.

Here's the DCG we worked with last week:

s --> np,vp. np --> det,n. vp --> v,np. vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. v --> [shoots].

Suppose we wanted to deal with sentences like ``She shoots him'', and ``He shoots her''. What should we do? Well, obviously we should add rules saying that ``he'', ``she'', ``him'', and ``her'' are pronouns:

pro --> [he]. pro --> [she]. pro --> [him]. pro --> [her].

Furthermore, we should add a rule saying that noun phrases can be pronouns:

np--> pro.

Up to a point, this new DCG works. For example:

s([she,shoots,him],[]). yes

But there's an obvious problem. The DCG will also accept a lot of sentences that are clearly wrong, such as ``A woman shoots she'', ``Her shoots a man'', and ``Her shoots she'':

s([a,woman,shoots,she],[]). yes s([her,shoots,a,man],[]). yes s([her,shoots,she],[]). yes

That is, the grammar doesn't know that ``she'' and ``he'' are subject pronouns and cannot be used in object position; thus ``A woman shoots she'' is bad because it violates this basic fact about English. Moreover, the grammar doesn't know that ``her'' and ``him'' are object pronouns and cannot be used in subject position; thus ``Her shoots a man'' is bad because it violates this constraint. As for ``Her shoots she'', this manages to get both matters wrong at once.

Now, it's pretty obvious what we have to do to put this right: we need to extend the DCG with information about which pronouns can occur in subject position and which in object position. The interesting question: how exactly are we to do this? First let's look at a naive way of correcting this, namely adding new rules:

s --> np_subject,vp. np_subject --> det,n. np_object --> det,n. np_subject --> pro_subject. np_object --> pro_object. vp --> v,np_object. vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. pro_subject --> [he]. pro_subject --> [she]. pro_object --> [him]. pro_object --> [her]. v --> [shoots].

Now this solution ``works''. For example,

?- s([her,shoots,she],[]). no

But neither computer scientists nor linguists would consider this a good solution. The trouble is, a small addition to the lexicon has led to quite a big change in the DCG. Let's face it: ``she'' and ``her'' (and ``he'' and ``him'') are the same in a lot of respects. But to deal with the property in which they differ (namely, in which position in the sentence they can occur) we've had to make big changes to the grammar: in particular, we've doubled the number of noun phrase rules. If we had to make further changes (for example, to cope with plural noun phrases) things would get even worse. What we really need is a more delicate programming mechanism that allows us to cope with such facts without being forced to add rules all the time. And here's where the extra arguments come into play. Look at the following grammar:

s --> np(subject),vp. np(_) --> det,n. np(X) --> pro(X). vp --> v,np(object). vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. pro(subject) --> [he]. pro(subject) --> [she]. pro(object) --> [him]. pro(object) --> [her]. v --> [shoots].

The key thing to note is that this new grammar contains no new rules. It is exactly the same as the first grammar that we wrote above, except that the symbol np is associated with a new argument, either (subject), (object), (_) and (X). A linguist would say that we've added a feature to distinguish various kinds of noun phrase. In particular, note the four rules for the pronouns. Here we've used the extra argument to state which pronouns can occur in subject position, and which occur in object position. Thus these rules are the most fundamental, for they give us the basic facts about how these pronouns can be used.

So what do the other rules do? Well, intuitively, the rule

np(X) --> pro(X).

uses the extra argument (the variable X) to pass these basic facts about pronouns up to noun phrases built out of them: because the variable X is used as the extra argument for both the np and the pronoun, Prolog unification will guarantee that they will be given the same value. In particular, if the pronoun we use is ``she'' (in which case X=subject), then the np wil, through its extra argument (X=subject), also be marked as being a subject np. On the other hand, if the pronoun we use is ``her'' (in which case X=object), then the extra argument np will be marked X=object too. And this, of course, is exactly the behaviour we want.

On the other hand, although noun phrases built using the rule

np(_) --> det,n.

also have an extra argument, we've used the anonymous variable as its value. Essentially this means can be either, which is correct, for expressions built using this rule (such as ``the man'' and ``a woman'') can be used in both subject and object position.

Now consider the rule

vp --> v,np(object).

This says that to apply this rule we need to use an noun phrase whose extra argument unifies with object. This can be either noun phrases built from object pronouns or noun phrases such as ``the man'' and ``a woman'' which have the anonymous variable as the value of the extra argument. Crucially, pronouns marked has having subject as the value of the extra argument can't be used here: the atoms object and subject don't unify. Note that the rule

s --> np(subject),vp.

works in an analogous fashion to prevent noun phrases made of object pronouns from ending up in subject position.

This works. You can check it out by posing the query:

?- s(X,[]).

As you step through the responses, you'll see that only acceptable English is generated.

But while the intuitive explanation just given is correct, what's really going on? The key thing to remember is that DCG rules are really are just a convenient abbreviation. For example, the rule

s --> np,vp.

is really syntactic sugar for

s(A,B) :- np(A,C), vp(C,B).

That is, as we learned in the previous lecture, the DCG notation is a way of hiding the two arguments responsible for the difference list representation, so that we don't have to think about them. We work with the nice user friendly notation, and Prolog translates it into the clauses just given.

Ok, so we obviously need to ask what

s --> np(subject),vp.

translates into. Here's the answer:

s(A,B) :- np(subject,A,C), vp(C,B).

As should now be clear, the name ``extra argument'' is a good one: as this translation makes clear, the (subject) symbol really is just one more argument in an ordinary Prolog rule! Similarly, our noun phrase DCG rules translate into

np(A,B,C) :- det(B,D), n(D,C). np(A,B,C) :- pro(A,B,C).

Note that both rules have three arguments. The first, A, is the extra argument, and the last two are the ordinary, hidden DCG arguments (the two hidden arguments are always the last two arguments).

Incidentally, how do you think we would use the grammar to list the grammatical noun phrases? Well, if we had been working with the DCG rule np --> det,n (that is, a rule with no extra arguments) we would have made the query

np(NP,[]).

So it's not too surprising that we need to pose the query

np(X,NP,[]).

when working with our new DCG. Here's what the response would be.

X = _2625 NP = [the,woman] ; X = _2625 NP = [the,man] ; X = _2625 NP = [a,woman] ; X = _2625 NP = [a,man] ; X = subject NP = [he] ; X = subject NP = [she] ; X = object NP = [him] ; X = object NP = [her] ; no

One final remark: don't be misled by this simplicity of our example. Extra arguments can be used to cope with some complex syntactic problems. DCGs are no longer the state-of-art grammar development tools they once were, but they're not toys either. Once you know about writing DCGs with extra arguments, you can write some fairly sophisticated grammars.