Grammatiche in Prolog

Fabio Massimo Zanzotto(slides di Andrea Turbati con aggiunte)

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

Grammatica con alberi sintatticideterminer(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 paintsthen 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

Documents

Transcript of Grammatiche in Prolog

Linguaggi Formali Compilazione: Grammatiche

Sistema esperto in Prolog con ragionamento incerto

Prolog è un buon linguaggio per risolvere CSP?risolvere CSP? Prolog … · 2008. 3. 10. · Prolog spinge a scrivere programmi basati su Standard Backtracking meno efficienti di

Linguaggi Regolari e Linguaggi Liberi - Unicamcomputerscience.unicam.it/tesei/updown/linguaggiregolarilinguaggiliberi.pdfGrammatiche regolari Le grammatiche in cui le produzioni sono

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

Lo sviluppo di un programma in Prolog · 2010. 2. 3. · pJ:'efeJ:'isce(peJ:'sona,auto) . J:'egala(peJ:'sona,auto). utile dannoso symbol. palestra biJ:'ra cioccolata abbiamo creato

Un percorso scolastico in ottica CLIL verso il ... · Un percorso scolastico in ottica CLIL ... video, libri di testo come grammatiche, ... delle scuole DSD di Udine e di Prato.

Grammatiche locali per il riconoscimento automatico e la ...€¦ · e 3.2. 1166. GRAMMATICHE LOCALI PER IL RICONOSCIMENTO AUTOMATICO E LA CLASSIFICAZIONE DI FAQ. JADT 2010: 10 .

XML e DTD. –il "PROLOG contiene: dichiarazione della versione di XML; commenti (facoltativi); dichiarazione del DOCUMENT TYPE. –il "DOCUMENT INSTANCE.

UNA SUGGESTIONE: HAL 9000 VS ALEXA DI COSA PARLEREMO …€¦ · Dalle espressioni regolari alle grammatiche regolari passando per gli automi a stati finiti Grammatiche context-free

Alfabeti Linguaggi Automi Grammatiche e Compilatori A cura del prof. Ionta Silvio a.s. 2005.

3.2 - Programmazione logica e Prolog.

“Applicazione”? Linguistica teorica e grammatiche scolastiche · 50% delle relazioni sintattiche in gran parte dei testi (Colombo 2012). ... Vedi anche Mereu 2004: 147. Bresnan

Il Linguaggio Prolog - spazioinwind.libero.itspazioinwind.libero.it/fanciullimassimiliano/files/universita/... · espr1 is espr2 dove espr1 è una variabile o un numero edespr2 è

Esecuzione dei programmi Prolog Liste ed operatori aritmetici Fabio Massimo Zanzotto.

Fondamenti di Intelligenza Artificiale M Progetti/Tesi ... · scelta (usando Drools, Prolog o altri ambienti di sviluppo) • Implementazione della Risoluzione • Sviluppo di un

9. LINGUAGGI FORMALI E GRAMMATICHE DI CHOMSKYfiii/materiale_schaerf/9-Linguaggi.pdf · Le Grammatiche di Chomsky Def. Una grammatica formale è un sistema G = caratterizzato

Programma per la traduzione automatica di codice Stips-Like in codice Prolog, in accordo con la formualzione di Kowalski Facoltà di Ingegneria – Università

Il primo passo: I basilari del Prolog Fabio Massimo Zanzotto (slides realizzate da Andrea Turbati)

Sistemi Esperti in Prolog