CIS341 Lab Exercises 2006

Updated February 20th 2006.

Partial solutions now available: Q3, Q4, Q5.

Definite Clause Grammars

1. Save the file dcg.txt as dcg.pl in a directory of your choice.
2. Run dcg.pl with the following inputs:
   1. The cat chased the dog.
   2. The cat chased.
   3. The dog barked.
   4. The dog barked the cat.
   Remember strings of words have to be entered as Prolog lists, and you need a second empty list (for reasons explained in the lectures) e.g.:

   s([the, dog, barked], []).

   Modify the grammar rules so that Prolog does not return 'Yes' for examples (2) and (4) (but still does for (1) and (3)).

3. Modify the grammar rules in dcg.pl so they can handle the following sentences:
   1. The black cat chased the white dog.
   2. The white dog ran from the black cat.
   3. The dog barked at the cat.
   4. The ugly white dog ran from the big black cat.
   5. The dog in the kennel barked at the cat in the hat.
   (Try the examples one at a time, don't try to write all the new rules at once.)
   
4. Start a new Prolog session. Download the file dcg2.txt and save it as dcg2.pl.
   This DCG makes use of a variable Num to handle number agreement.
   Extend or modify the rules to match the following examples:
   1. The dog barks.
   2. The dogs bark.
   3. * The dog bark.
   4. * The dogs barks.
   5. Some dogs bark.
   6. Some dog barks.
   7. * Some dogs barks.
   8. The dog barks at the cat in the kennel.
   9. Some dogs chase some cats in the garden.
   NB: the asterisk "*" means that the sentence is bad and should *not* be generated by the gramar.
5. (optional) Download the file dcgtree.txt and save it as a Prolog file.
   This DCG uses an extra argument to build a "tree" structure as a labelled bracketed string, as it parses the input sentences. For example the query:

   ? - s(Tree, [the,dog,barked],[]).

   returns

   Tree = s(np(det(the), n(dog)),vp(v(barked))) ;

   Run this DCG with a few examples (adding extra lexical rules if necessary) and make sure you understand how these structures are licensed by the grammatical rules.
   Try extending the rules to handle all the examples in the previous exercises.

6. Advanced, for project students

   After Chomsky published his approach to formal grammars of natural language in 1957, it was thought for about 20 years that context-free grammars were not sufficient to handle so-called unbounded dependencies as in the following examples, and that special operations called transformations were needed.

   1. Who does John think Mary met at the party?
   2. The man Peter says John thinks Mary met is a famous aviator
   The issue here is that an "argument" of the verb met does not appear in its normal place following the verb. It looks as if we need rules like

   clause --> np tv

   which only apply in particular contexts; but even specifying these contexts is difficult enough, as the "gap" can be at an arbitrary depth of nesting away from the noun phrase which realises the "understood" argument.

   In the late 1970s Gerald Gazdar of Sussex University developed a technique for handling examples like these using unification to propagate the information that a gap is required, and there is a well-known implementation described in Pereira and Shieber's Prolog for Natural Language Processing. A modified version of their grammar is here. The following sample rules illustrate how it works:

   s(Gap) --> np(nogap), vp(Gap).

   np(nogap) --> det, n, optrel.

   np(gap(np)) --> [].

   vp(Gap) --> tv, np(Gap).

   optrel --> relpron, vp(nogap).

   optrel --> relpron, s(gap(np)).

   A relative clause consists of a pronoun followed by a sentence missing an NP - the missing NP can be the subject, leaving a VP on its own, or the object, resulting in a transitive verb phrase with no NP.

   Exercises
   1. Download the sample grammar and try it out with the test sentences, using spy or trace.
   2. Add features from previous exercises so you can process sentences like:
      • The big black dog chased the cat that slept in the kennel in the garden
      • The farmer chased the dogs that bark at his sheep
      • *The farmer chased the dog that bark at his sheep
   3. Apply the techniques from dcgtree.txt to build "tree structures" of sentences including relative clauses.
   4. Extend the grammar to handle questions such as
      • Which cat did the dog bark at?
      • Who did the cat think the dog chased?