CIS341 Lab Exercises 2005
Updated March 8th 2005.
Partial solutions now available:
Definite Clause Grammars
- Save the file
dcg.txt as dcg.pl in a directory of your choice.
- Run dcg.pl with the following inputs:
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.:
- The cat chased the dog.
- The cat chased.
- The dog barked.
- The dog barked the cat.
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)).
Modify the grammar rules in dcg.pl so they can handle the following
(Try the examples one at a time, don't try to write all the new rules at once.)
- The black cat chased the white dog.
- The white dog ran from the black cat.
- The dog barked at the cat.
- The ugly white dog ran from the big black cat.
- The dog in the kennel barked at the cat in the hat.
- 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:
NB: the asterisk "*" means that the sentence is bad and should *not* be generated by the gramar.
The dog barks.
The dogs bark.
* The dog bark.
* The dogs barks.
Some dogs bark.
Some dog barks.
- * Some dogs barks.
The dog barks at the cat in the kennel.
Some dogs chase some cats in the garden.
Download the file
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],).
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.
- 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.
The issue here is that an "argument" of the verb met does not appear in its normal place following
It looks as if we need rules like
- Who does John think Mary met at the party?
- The man Peter says John thinks Mary met is a famous aviator
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.
- clause --> np tv
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.
Download the sample grammar and try it out with the test sentences,
using spy or trace.
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
- Apply the techniques from
to build "tree structures" of sentences including relative clauses.
- Extend the grammar to handle questions such as
- Which cat did the dog bark at?
- Who did the cat think the dog chased?