Grammatiche in Prolog
Fabio Massimo Zanzotto
(slides di Andrea Turbati con aggiunte)
University of Rome “Tor Vergata”
Grammatica
• Prolog è in grado di interpretare direttamente una
grammatica scritta in DCG (definite cluase
grammar)
• La traduzione da una grammatica scritta in BNF
(Backus-Naur Form) in DCG è praticamente
immediata (è un semplice esercizio di riscrittura)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio BNF -> DCG
• BNF:
<s> ::= a b
<s> ::= a <s> b
• DCG
s --> [a], [b] .
s --> [a], s, [b] .
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Come Prolog interpreta la grammatica
• Prolog converte internamente una grammatica
scritta in DCG in regole prolog
• Esempio:
move --> step.
move --> step, move.
step --> [up] .
step --> [down] .
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Come Prolog interpreta la grammatica
move(List, Rest) :step(List, Rest).
move(List1, Rest),
step(List1, List2),
move(List2, Rest).
step([up|Rest], Rest).
step([down|Rest], Rest).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
esempio
• ?- s([a,a,b,b], []).
– true
• ?-s([a,a,b],[]).
– no
• ?-move([up,up,down],[]).
– yes
• ?-move([up,X,down],[]).
– X=up;
– X=down;
– no
• ?- s([a,a,b,b,c,d,e], [c,d,e]).
– true
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammar for Natural Language 1
sentence --> noun_phrase, verb_phrase.
verb_phrase --> verb, noun_phrase.
noun_phrase --> determiner, noun.
determiner --> [a].
determiner --> [the].
noun --> [cat].
noun --> [mouse].
verb --> [scares].
verb --> [hates].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammar for Natural Language 1
• Questa grammatica riconosce le frasi:
– [the, cat, scares, the, mouse].
– [the, mouse, hates, a, cat]
• Inoltre è in grado di generare le frasi o parti di
esse:
– ?-sentence([the, cat, X, the, mouse],[]).
• X = scares;
• X = hates;
• false
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammar for Natural Language 2
• Aggiungiamo i plurali alla nostra grammatica
noun --> [cats].
noun --> [mice].
verb --> [scare].
verb --> [hate].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammar for Natural Language 2
• Ora possiamo riconoscere anche:
– [the, mice, hate, the, cat].
• Ma purtroppo anche la seguente frase viene
accettata:
– [the, mice, hates, the, cat].
• Non abbiamo inserito in alcun modo
l’informazione del fatto che se il soggetto è
singolare anche il verbo lo deve essere
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Singolare/plurale
• Si potrebbe rimediare dividendo le regole in
singolari e plurali, ma questo produrrebbe troppe
regole (almeno il doppio)
• La soluzione migliore è quella di inserire un
parametro aggiuntivo nelle regole che indica il
numero (singolare o plurale) per avere la
dipendenza dal contesto
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammar for Natural Language 3
sentence(Number) --> noun_phrase(Number), verb_phrase(Number).
verb_phrase(Number) --> verb(Number), noun_phrase(_).
noun_phrase(Number) --> determiner(Number), noun(Number).
determiner(singular) --> [a].
determiner(_) --> [the].
noun(singular) --> [cat].
noun(singular) --> [mouse].
noun(plural) --> [cats].
noun(plural) --> [mice].
verb(singular) --> [scares].
verb(singular) --> [hates].
verb(plural) --> [scare].
verb(plural) --> [hate].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Come Prolog interpreta la grammatica
sentence(Number) --> noun_phrase(Number),
verb_phrase(Number).
Diventa
sentence(Number, List1, Rest):noun_phrase(Number, List1, List2),
verb_phare(Number, List2, Rest).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammar for Natural Language 3
• ?- sentence(plural, [the, mice, hate, the, cat],[]).
– true
• sentence(plular, [the, mice, hates, the, cat],[]).
– false
• sentence(X, [the, mouse, hates, the, cat],[]).
– X = singular
• sentence(singular, [the, What, hates, the, cat],[]).
– What = cat;
– What = mouse;
– false
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizi
• Scrivere un programma che, sfruttando la
grammatica 3, prende in ingresso una frase (NON
una lista) e restiuisca true o false se tale frase
rispetta la grammatica o meno
• Il programma appena realizzato deve funzionare
anche se nella frase ci sono variabili Prolog (
parole che hanno l’iniziale maiuscola ). In questo
caso deve restituire il valore che tali variabili
assumono affinché la grammatica sia rispettata, se
possibile
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
Semantica/Significato
University of Rome “Tor Vergata”
Grammatica
• Nella lezione scorsa abbiamo visto come usare le
DCG (definite clause grammar) in Prolog
• Abbiamo anche aggiunto un parametro alle regole
della grammatica per avere l’agreement
singolare/plurale
• Ora vedremo come generare gli alberi sintattici e
come associare il significato a ciò che analizziamo
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Come rappresentare un albero
noun_phrase
determiner
noun
the
cat
noun_phrase(determiner(the), noun(cat))
root(figli_separati_da_virgola)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammatica con alberi sintattici
• Dobbiamo modificare la grammatica per poter avere
gli alberi sintattici o parse tree
• Es:
sentence(Number) -->
noun_phrase(Number),
verb_phrase(Number).
diventa
sentence(Number, sentence(NP, VP)) -->
noun_phrase(Number, NP),
verb_phrase(Number, VP).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammatica con alberi sintattici
sentence(Number, sentence(NP, VP)) -->
noun_phrase(Number, NP),
verb_phrase(Number, VP).
verb_phrase(Number, verb_phrase(Verb, NP)) -->
verb(Number, Verb),
noun_phrase(_, NP).
noun_phrase(Number, noun_phrase(Det, Noun)) -->
determiner(Number, Det),
noun(Number, Noun).
© F.M.Zanzotto
determiner(singular, determiner(a)) --> [a].
determiner(_,determiner(the)) --> [the].
noun(singular, noun(cat)) --> [cat].
noun(singular, noun(mouse)) --> [mouse].
noun(plural, noun(cats)) --> [cats].
noun(plural, noun(mice)) --> [mice].
verb(singular, verb(scares)) --> [scares].
verb(singular, verb(hates)) --> [hates].
verb(plural, verb(scare)) --> [scare].
verb(plural, verb(hate)) --> [hate].
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammatica con alberi sintattici
• ?- sentence(singular, Tree, [a, cat, scares, the, mice
], []).
– Tree = sentence(noun_phrase(determiner(a), noun(cat)),
verb_phrase(verb(scares),
noun_phrase(determiner(the), noun(mice))))
• ?- sentence(singular, Tree, [a, X, scares, the, mice
], []).
– Tree = sentence(noun_phrase(determiner(a), noun(cat)),
verb_phrase(verb(scares),
noun_phrase(determiner(the), noun(mice))))
– X=cat
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Grammatica con alberi sintattici
• ?- sentence(Number,
sentence(noun_phrase(determiner(a),
noun(cat)), verb_phrase(verb(scares),
noun_phrase(determiner(the), noun(mice)))),
X, []).
– Number = singular,
– X = [a, cat, scares, the, mice]
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato
• Per avere il significato di una frase o lista di
comandi esistono due metodi:
– Ottenere l’albero sintattico o parse tree della frase e poi
parsare tale albero per ottenere il significato
– Parsare direttamente la frase di partenza per avere il
significato, senza passare per l’albero sintattico o parse
tree
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Usando il parse tree
move(move(Step)) --> step(Step).
move(move(Step, Move)) --> step(Step), move(Move).
step(step(up)) --> [up].
step(step(down)) --> [down].
meaning(move(Step, Move), Dist):meaning(Step, D1),
meaning(Move, D2),
Dist is D1 + D2.
meaning(step(Step), Dist):meaning(Step, Dist).
meaning(step(up), 1).
meaning(step(down), -1).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Usando il parse tree
• ?- move(Tree, [up,up,down, up, up], []),
meaning(Tree, Dist).
– Tree = move(step(up), move(step(up),
move(step(down), move(step(up), move(step(up)))))),
– Dist = 3
• ?- move(Tree, [up,up,down, up, X], []),
meaning(Tree, 1).
– Tree = move(step(up), move(step(up),
move(step(down), move(step(up),
move(step(down)))))),
– X = down
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Usando il parse tree
• ?- move(Tree, [up, up, X, Y, up], []),
meaning(Tree, 3).
– Tree = move(step(up), move(step(up), move(step(up),
move(step(down), move(step(up)))))),
– X = up,
– Y = down
– Tree = move(step(up), move(step(up),
move(step(down), move(step(up), move(step(up)))))),
– X = down,
– Y = up
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Non usando il parse tree
move2(D) --> step2(D).
move2(D) -->
step2(D1), move2(D2), {D is D1 + D2}.
step2(1) --> [up].
step2(-1) --> [down].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Non usando il parse tree
• move2(Dist, [up, up,down, up, up],[]).
– Dist = 3
• move2(3, [up, up,X, Y, up],[]).
– X = up, Y = down;
– X = down, Y = up;
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato del linguaggio naturale
• Data una frase cosa si intende con il suo
“significato”?
• Una volta estratto tale significato, cosa possiamo
farci?
• Come possiamo rappresentarlo?
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato del linguaggio naturale
• In Prolog il significato possiamo esprimerlo con i
termini.
• paints(john). Può voler dire che John dipinge
• likes(john, mary). Può voler indicare che a John
piace Mary
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato del linguaggio naturale
• Adottiamo lo stesso approccio del non usare il
parse tree (che in questo caso sarebbe l’albero
sintattico)
• Quindi associamo il significato direttamente nella
grammatica
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato del linguaggio naturale
sentence2(VP) -->
noun_phrase2(Actor),
verb_phrase2(Actor, VP).
noun_phrase2(Name) -->
properName(Name).
verb_phrase2(Actor, VP) -->
intrans_verb(Actor, VP).
verb_phrase2(Somebody, VP) -->
trans_verb(Somebody, Something, VP),
noun_phrase2(Something).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
properName(john) --> [john].
properName(mary) --> [mary].
intrans_verb(Actor, paints(Actor)) --> [paints].
trans_verb(Somebody, Something, likes(Somebody,
Something)) --> [likes].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato del linguaggio naturale
• ?- sentence2(Meaning, [john, paints], []).
– Meaning = paints(john)
• ?- sentence2(Meaning, [john, likes, mary], []).
– Meaning = likes(john, mary)
• sentence2(paints(john), [Who, paints], []).
– Who = john
• sentence2(likes(mary, john), [X, likes, Y], []).
– X = mary,
– Y = john.
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• Modificare la grammatica precedente per avere il
significato a partire dall’albero sintattico della
frase. Quindi una query dovrà restituire oltre al
significato anche l’albero sintattico
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato di “a”
• “a man paints” significa “esiste almeno un uomo
che dipinge”
• a ha il significato di esiste in First Order Logic
• There exists an X such that
X is a man and X paints
• exists( X, man(X) and paints(X))
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato di “a”
• exists(X, Property and Assertion)
• determiner(X, Prop, Assn, exists(X, Prop and
Assn)) --> [a].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato di “every”
• “every woman dances” significa che tutte le donne
danzano
• Every ha il significato di per ogni in First Order
Logic
• For all X
if X is a woman then X dances
• all(X, woman(X) => dances(X) )
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Significato di “every”
• all(X, Property => Assertion)
• determiner(X, Prop, Assn, all(X,
Prop=>Assn)) --> [every].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio di “a” e “every”
:- op( 100, xfy, and).
:- op( 150, xfy, =>).
sentence( S)  noun_phrase( X, Assn, S), verb_phrase( X, Assn).
noun_phrase( X, Assn, S) --> determiner( X, Prop, Assn, S), noun( X, Prop).
verb_phrase( X, Assn) --> intrans_verb( X, Assn).
determiner( X, Prop, Assn, all( X, Prop => Assn)) --> [every].
determiner( X, Prop, Assn, exists( X, Prop and Assn)) --> [a].
noun( X, man(X)) --> [man].
noun( X, woman(X)) --> [woman].
intrans_verb( X, paints(X)) --> [paints].
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempio di “a” e “every”
• ?- sentence(S, [a, man, paints], []).
– S = exists(_G530, man(_G530)and paints(_G530))
• ?- sentence(S, [every, woman, paints], []).
– S = all(_G1188, woman(_G1188)=>paints(_G1188)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Relative clauses
• “Every man that paints admires Monet” significa
che tutti gli uomini che dipingono ammirano
Monet, cioè che se uno è un uomo e dipinge allora
ammira Monet
• For all X,
if X is a man and paints
then X admires Monet
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Relative clauses
• all(X, man(X) and paints(X) =>
admires(X, Monet) ).
• all(X, Prop1 and Prop2 => Assn).
• rel_clause( X, Prop1, Prop1 and Prop2) -->
[that], verb_phrase( X, Prop2).
• noun_phrase( X, Assn, S) -->
determiner( X, Prop12, Assn, S),
noun( X, Prop1),
rel_clause( X, Prop1, Prop12).
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esempi conclusivi
• ?- sentence( M, [john,paints],[]).
– M = paints(john)
• ?- sentence( M, [a, man, paints], []).
– M = exists(_G526, man(_G526)and paints(_G526))
• ?- sentence( M, [every,man,that,paints,admires,monet],[]).
– M = all(_G895, man(_G895)and paints(_G895)=>admires(_G895, monet))
• ?- sentence( M, [annie,admires,every,man,that,paints],[]).
– M = all(_G306, man(_G306)and paints(_G306)=>admires(annie, _G306))
• ?- sentence( M,
[every,woman,that,admires,a,man,that,paints,likes,monet],[]).
– all(_G1215, woman(_G1215)and exists(_G1227, (man(_G1227)and
paints(_G1227))and admires(_G1215, _G1227))=>likes(_G1215, monet))
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica
University of Rome “Tor Vergata”
Esercizio
• Modificare la grammatica precedente affinchè
venga memorizzato in prolog il significato della
frase appena parsata in modo che sia possibile poi
effettuare delle query fruttando la conoscenza
appena aggiunta. Eventualmente gestire l’input
non tramite liste, ma tramite frasi (non [a, man,
paints], ma “a man paints”)
© F.M.Zanzotto
Logica per la Programmazione e la Dimostrazione Automatica