Practical Natural Language Processing

To tell the truth the practicality of what is given here is moot. However it is the basis for practical systems. We will demonstrate the ideas outlined earlier within a very narrow context. That will allow someone to "talk" to a blocks world agent. We begin with simple grammars. Fortunately Prolog makes certain kinds of grammar very easy to write.

Definite Clause Grammars (DCGs)

Grammars use production rules that describe how to construct complex objects from simpler ones (and conversely how to break up complex things into simpler ones). Rather than give a precise definition of a grammar at this point we give an example of a definite clause grammar which parses many simple English sentences.

 Sentence  -->  Noun_Phrase , Verb_Phrase

Noun_Phrase --> Determiner, Noun

Verb_Phrase -->  Verb
Verb_Phrase -->  Verb, Noun_Phrase

Noun --> cat
Noun --> mouse
Noun --> dream

Determiner -->  the
Determiner --> a

Verb --> sleeps
Verb --> sleep
Verb --> chases

One can see that this grammar parses sentences such as

The mouse sleeps.
The cat chases a mouse

Unfortunately it also parses

The mouse sleep

which is ungrammatical and

The mouse chases a cat.
The dream sleeps

The first of which is implausible and the second of which while poetic is possibly meaningless. What can we do about this. Well the ungrammatical stuff can be handled by

Augmented DCGs

Once again we illustrate the idea with an example in which we modify the earlier DCG to cope with the two problem sentences.

 Sentence(Type, Number)  -->  Noun_Phrase(Number) , Verb_Phrase(Type, Number)

Noun_Phrase(Number) --> Determiner(Number), Noun(Number)

Verb_Phrase(intransitive) -->  Verb(intransitive)
Verb_Phrase(transitive) -->  Verb(transitive), Noun_Phrase(Any)

Noun(sing) --> cat
Noun(plur) --> cats
Noun(sing) --> mouse
Noun(plur) --> mice
Noun(sing) --> dream

Determiner(_) -->  the
Determiner(sing) --> a

Verb(intransitive, sing) --> sleeps
Verb(intransitive, plur) --> sleep
Verb(transitive, sing) --> chases

We still get "the dream sleeps" and "a mouse chases the cats", but some of the nonsense is gone. (Note that I we introduce pronouns we will have a problem with "I sleeps" but you can guess that one uses person as well as number to deal with that.)

Semantics

How do we deal with the nonsense sentences such as the famous Chomsky sentence?

Curious green dreams sleep furiously.

The first step is to assign a semantics to each sentence. With this in hand we might be able to determine on the basis of some knowledge that the system has been given that dreams are not coloured and don't sleep. Once again we can augment the DCG, but this time in a different way.

 Sentence(intransitive, Number, Semantics)  -->  Noun_Phrase(Number, SemN) , Verb(intransitive, Number, SemV),
                                                                 {Semantics = SemV(SemN)}.
 Sentence(transitive, Number, Semantics, Number) --> Noun_Phrase(Number, SemN1) , Verb(transitive, Number),
                                                           Noun_Phrase(_, SemN2), {Semantics = SemV(SemN1, SemN2)}.
 

Noun_Phrase(Number, Semantics) --> Determiner(Number, SemD), Noun(Number, SemN),
			{Semantics = SemD(SemN)}

Verb(Type, SemV) -->  Verb(Type, SemV)


Noun(sing, cat) --> cat
Noun(plur, cats) --> cats
Noun(sing, mouse) --> mouse
Noun(plur, mice) --> mice
Noun(sing, dream) --> dream

Determiner(Number, the) -->  the
Determiner(sing, a) --> a

Verb(intransitive, sing, sleep) --> sleeps
Verb(intransitive, plur, sleep) --> sleep
Verb(transitive, sing, chase) --> chases

Putting it all together

If you think this looks a little like Prolog you are on the right track. In fact most Prologs support DCGs

If we were to assemble all the pieces we have above or something like them we could translate sentences to their semantics represented as logical expressions ad then try to prove them. The linked example does this in a very simple case.

Return to UG AI home page

Last Changed: 20 November 1995