Programming Paradigms CSI2120
Jochen Lang
EECS, University of Ottawa Canada
Logic Programming in Prolog
• Language Processing
– Context free grammars
– Parse trees
– Definite clause grammars (DCG)
CSI2120: Programming Paradigms
Grammar of (Simple) English Sentences
• (Simple) English sentences consist of a noun phrase followed by a verb phrase
• Context free grammar rule
sentence noun_phrase,verb_phrase
– which reads: sentence can take the form of noun_phrase followed by verb_phrase
• As a tree
sentence
noun_phrase verb_phrase the man eats a tomato
CSI2120: Programming Paradigms
Parse Tree
•
Decomposing the whole structure gives us a parse tree
– For the sentence from before: sentence
noun_phrase verb_phrase determiner noun verb
noun_phrase
the
man eats CSI2120: Programming Paradigms
determiner noun
a tomato
Analyzing a Sentence in Prolog
• We use a structure where we always work on the head of the list and return the rest for further analysis
• Queries of the type:
?- sentence([the,man,eats,a,tomato],[]).
sentence(X,Z) :-
noun_phrase(X,Y), verb_phrase(Y,Z).
noun_phrase(X,Z) :-
determiner(X,Y), noun(Y,Z).
verb_phrase(X,Z) :-
verb(X,Z).
verb_phrase(X,Z) :-
verb(X,Y), noun_phrase(Y,Z).
CSI2120: Programming Paradigms
Vocabulary
• Need a vocabulary to store all words and their classification • Example:
determiner([the|Z],Z).
determiner([a|Z],Z).
noun([tomato|Z],Z).
noun([bird|Z],Z).
noun([man|Z],Z).
noun([cat|Z],Z).
verb([eats|Z],Z).
verb([sings|Z],Z).
verb([loves|Z],Z).
CSI2120: Programming Paradigms
Example
• Can ask if something can be parsed as a sentence ?- sentence([the,man,eats,a,tomato],[]). true
?-
sentence([the,man,eats,a,tomato],[a,tomato]).
true
3 ?-
sentence([the,man,eats,a,tomato],[tomato]).
false.
CSI2120: Programming Paradigms
Notation DCG
(definite clause grammar)
• Prolog has a built-in operator which hides the extra (two) list parameters form us
• An equivalent program to before can be written as follows sentence –> noun_phrase, verb_phrase. noun_phrase –> determiner, noun.
verb_phrase –> verb.
verb_phrase –> verb, noun_phrase.
determiner –> [the].
determiner –> [a].
noun –> [tomato].
and so on
CSI2120: Programming Paradigms
Arguments in DCG
• For example, want to distinguish between singular and plural form for noun and verbs
sentence –> sentence(_).
sentence(X) –> noun_phrase(X), verb_phrase(X). noun_phrase(X) –> determiner(X), noun(X). verb_phrase(X) –> verb(X).
verb_phrase(X) –> verb(X), noun_phrase(_). determiner(_) –> [the].
determiner(singular) –> [a].
noun(singular) –> [tomato].
noun(plural) –> [tomatos].
verb(plural) –> [eat].
verb(singular) –> [eats]. … and so on
CSI2120: Programming Paradigms
Explicitly Constructing a Parsetree
• Add an extra argument to hold the result of the parsing in a parse tree
sentence(PT) –> sentence(_,PT).
sentence(X,sentence(NP,VP)) –>
noun_phrase(X,NP), verb_phrase(X,VP).
noun_phrase(X,noun_phrase(D,N)) –>
determiner(X,D), noun(X,N).
verb_phrase(X,verb_phrase(V)) –> verb(X,V).
verb_phrase(X,verb_phrase(VP,NP)) –> verb(X,VP),
noun_phrase(_,NP).
determiner(_,determiner(the)) –> [the]. noun(singular,noun(tomato)) –> [tomato]. noun(plural,noun(tomatos)) –> [tomatos]. verb(singular,verb(eats)) –> [eats]. verb(plural,verb(eat)) –> [eat]. … and so on
CSI2120: Programming Paradigms
Example
?- sentence(T,[the, cats, eat, the, bird],[]).
T = sentence(noun_phrase(determiner(the),
noun(cats)), verb_phrase(verb(eat),
noun_phrase(determiner(the), noun(bird))))
– Our predicates do not perform pretty printing but this could be easily added for printing T, e.g.
T = sentence(
noun_phrase(determiner(the),
noun(cats)),
verb_phrase(verb(eat),
CSI2120: Programming Paradigms
noun_phrase(determiner(the),
noun(bird))))
Simplify the Dictionary
• We can change rules for each word into rules for classes of words and note all our vocabulary as simple facts.
determiner(X,determiner(Y)) –> [Y],
{isDeterminer(Y,X)}.
noun(X,noun(Y)) –> [Y], {isNoun(Y,X)}. verb(X,verb(Y)) –> [Y], {isVerb(Y,X)}. isDeterminer(the,_). isDeterminer(a,singular). isNoun(tomato,singular). isNoun(tomatos,plural). isVerb(eats,singular). isVerb(eat,plural). … and so on
– Notetheuseof{}toexcludetheextralistparameters
– Notethe[Y]fortheprocessedargument(theheadofthelist)
CSI2120: Programming Paradigms
Another DCG Example: An Elevator
• Other problems can be expressed in a DCG
– Forexample:Keepingtrackofthelevelanelevatorisat
displacement(L) –> motion(L).
displacement(L) –> motion(L1), displacement(L2),
{L is L1+L2}.
motion(1) –> [up].
motion(-1) –> [down].
• Query
?- displacement(L,[up,up,up,up,down,down,up],X). L = 1, X = [up, up, up, down, down, up] ;
L = 2, X = [up, up, down, down, up] ;
… and so on
L = 3, X = [] ;
CSI2120: Programming Paradigms
Summary
• Language Processing
– Context free grammars
– Parse trees
– Definite clause grammars (DCG)
CSI2120: Programming Paradigms