Grammatiche in Prolog Fabio Massimo Zanzotto (slides di Andrea Turbati con aggiunte)

Grammatiche in Prolog

Fabio Massimo Zanzotto

(slides di Andrea Turbati con aggiunte)

© F.M.Zanzotto Logica per la Programmazione e la Dimostrazione Automatica

University of Rome “Tor Vergata”

• 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)

Grammatica



• BNF:

<s> ::= a b

<s> ::= a <s> b

• DCGs --> [a], [b] .

s --> [a], s, [b] .

Esempio BNF -> DCG



• Prolog converte internamente una grammatica scritta in DCG in regole prolog

• Esempio:move --> step.

move --> step, move.

step --> [up] .

step --> [down] .

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).




• ?- 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

esempio



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].

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




• Aggiungiamo i plurali alla nostra grammatica

noun --> [cats].

noun --> [mice].

verb --> [scare].

verb --> [hate].




• 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




• 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

Singolare/plurale



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].




sentence(Number) --> noun_phrase(Number), verb_phrase(Number).

Diventa

sentence(Number, List1, Rest):-

noun_phrase(Number, List1, List2),

verb_phare(Number, List2, Rest).




• ?- 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




• 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

Esercizi

Semantica/Significato



• 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

Grammatica



noun_phrase(determiner(the), noun(cat))

root(figli_separati_da_virgola)

Come rappresentare un albero

noun_phrase

catthe

determiner noun



• 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).

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).


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].



• ?- 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




• ?- 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]




• 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

Significato



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).

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




• ?- 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




move2(D) --> step2(D).

move2(D) -->

step2(D1), move2(D2), {D is D1 + D2}.

step2(1) --> [up].

step2(-1) --> [down].

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;

Non usando il parse tree



• Data una frase cosa si intende con il suo “significato”?

• Una volta estratto tale significato, cosa possiamo farci?

• Come possiamo rappresentarlo?

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




• 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




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).




properName(john) --> [john].

properName(mary) --> [mary].

intrans_verb(Actor, paints(Actor)) --> [paints].

trans_verb(Somebody, Something, likes(Somebody, Something)) --> [likes].



• ?- 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.




• 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

Esercizio



• “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 thatX is a man and X paints

• exists( X, man(X) and paints(X))

Significato di “a”



• exists(X, Property and Assertion)

• determiner(X, Prop, Assn, exists(X, Prop and Assn)) --> [a].

Significato di “a”



• “every woman dances” significa che tutte le donne danzano

• Every ha il significato di per ogni in First Order Logic

• For all Xif X is a woman then X dances

• all(X, woman(X) => dances(X) )

Significato di “every”



• all(X, Property => Assertion)

• determiner(X, Prop, Assn, all(X, Prop=>Assn)) --> [every].

Significato di “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].

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)

Esempio di “a” e “every”



• “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

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).

Relative clauses



• ?- 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))

Esempi conclusivi



• 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”)

Esercizio

Grammatiche in Prolog Fabio Massimo Zanzotto (slides di Andrea Turbati con aggiunte)

Documents

Transcript of Grammatiche in Prolog Fabio Massimo Zanzotto (slides di Andrea Turbati con aggiunte)