FMZ, Giugno 2001 Parsing del linguaggio naturale Fabio Massimo Zanzotto Università di Tor Vergata.

FMZ, Giugno 2001

Parsing del linguaggio naturale

Fabio Massimo ZanzottoUniversità di Tor Vergata

FMZ, Giugno 2001

Parsing e linguaggio naturale

Lezione 1

FMZ, Giugno 2001

Il parsing

• Un esempio di programma– Come viene strutturato?– Come viene utilizzato

• Strutturare significa capire e poter utilizzare

FMZ, Giugno 2001

Analisi del testo di un programma

if (a>b) {

printf(“Hello World!”);

a++;

} else {

printf(“Bye Bye World!”);

}

FMZ, Giugno 2001


• In quale linguaggio è stato scritto?

• Come avete fatto a scoprirlo?

• Scriviamo un automa a stati finiti che almeno riconosca quell’ingresso.

FMZ, Giugno 2001

Automa a stati finiti

• QuintuplaV insieme dei simboli

Q insieme degli stati

insieme delle transizioni

q0 stato iniziale

F insieme degli stati finali

FMZ, Giugno 2001

Costruiamo l’automa

V = {if, else, a, b, (,),>, +, ;, printf(“Hello World!”), printf(“Bye Bye World!”),{, }}

FMZ, Giugno 2001


I problemi che vogliamo risolvere sono:

• Il “pezzo di codice” fa parte del linguaggio?

• Come posso utilizzare il “pezzo di codice”?– Dandogli “significato” per tradurlo in un

linguaggio più a basso livello.

FMZ, Giugno 2001

Da testo di un programma ad albero

if then else

if-statement

(a>b)


a++;

printf(“Bye Bye World!”);

FMZ, Giugno 2001

Il problema in generale

V insieme di simboliL V* il linguaggioEsiste un meccanismo che possa dire se dato un

lV* questo appartenga a L o non appartenga a L ?

Esiste un modo sintetico per esprimere L (ovvero diverso dall’enumerazione)?

Esiste la possibilità di assegnare una struttura all’elemento l in esame (se questo appartiene al linguaggio)?

FMZ, Giugno 2001

Digressione

• Chiusura di Kleene indicata con uno * sul nome dell’insieme

• Informale V* contiene tutte le concatenazioni possibili di elementi in V di qualsiasi lunghezza

Se Vi=tutte le stringhe di lunghezza i composte da elementi di V

Allora V*= Vi

FMZ, Giugno 2001


if (a>b) {


a++;

}

FMZ, Giugno 2001


if then

if-statement

(a>b)printf(“Hello World!”);

FMZ, Giugno 2001


REGOLE:

if-statement if condition instructions

if-statement

if condition instructions else instructions

FMZ, Giugno 2001

Il parser

PARSER

Regole

Testo Programma

FMZ, Giugno 2001

Il processo di generazione di codice macchina

• l’albero codice macchina

• l’albero permette di utilizzare il testo del programma

• la struttura esplicita il “significato” del testo del programma

• Strutturare == ““capire”” (per poi riutilizzare)

FMZ, Giugno 2001

Il parsing del linguaggio naturale

• Vogliamo rispondere ad Chi ha vinto lo scudetto?

• utilizzando le frasi:“La XYZ ha agguantato lo scudetto di campioni

d’Italia all’ultima giornata di campionato”

“La ZXY dopo una lunga rincorsa è rimasta delusa”

“La ZYX avrebbe potuto cucirsi sulle maglie il suo N scudetto”

FMZ, Giugno 2001


• Capire la “sintassi”

• Capire la “semantica”

• Capire la “pragmatica” (struttura del discorso)

• Capire == strutturare

FMZ, Giugno 2001

Esempio

la XYZ ha agguantato lo scudetto

S(

Subj(la XYZ),

VP(

Verb(ha agguantato),

Obj(lo scudetto)

)

)

FMZ, Giugno 2001

Esempio


S NP VPVP Verb NP NP Art NounNoun XYZNoun scudettoArt laArt loVerb ha agguantato

FMZ, Giugno 2001


Lezione 2

FMZ, Giugno 2001


• Concetti importanti:– “capire” = strutturare

– strutturare permette poi di utilizzare

• Strutturare richiede:– Comprendere se una data sequenza di caratteri

appartiene o meno ad un linguaggio

– Costruire la struttura l che appartiene al linguaggio

FMZ, Giugno 2001

Il problema in generale

V insieme di simboliL V* il linguaggioEsiste un meccanismo che possa dire se dato un

lV* questo appartenga a L o non appartenga a L ?

Esiste un modo sintetico per esprimere L (ovvero diverso dall’enumerazione)?

Esiste la possibilità di assegnare una struttura all’elemento l in esame (se questo appartiene al linguaggio)?

FMZ, Giugno 2001

Digressione

• Chiusura di Kleene indicata con uno * sul nome dell’insieme

• Informale V* contiene tutte le concatenazioni possibili di elementi in V di qualsiasi lunghezza

Se Vi=tutte le stringhe di lunghezza i composte da elementi di V

Allora V*= Vi

FMZ, Giugno 2001


• Modelliamo una parser che possa interpretare le seguenti frasi:“La XYZ ha agguantato lo scudetto di

campioni d’Italia all’ultima giornata di campionato”

“La ZXY dopo una lunga rincorsa è rimasta delusa”

“La ZYX avrebbe potuto cucirsi sulle maglie il suo N scudetto”

FMZ, Giugno 2001

Un parser

• Regole: quelle fornite della grammatica precedente

• Parser (cioè il processore): il motore inferenziale del prolog

FMZ, Giugno 2001

Un parser

• Cominciamo con il costruire un riconoscitore in prolog

• Costruiamo poi un riconoscitore che fornisca la struttura

FMZ, Giugno 2001

Esempio


S NP VPVP Verb NP NP Art NounNoun XYZNoun scudettoArt laArt loVerb ha agguantato

FMZ, Giugno 2001

Un parser

• Esempio1

• Esempio2

• Esempio3

FMZ, Giugno 2001

Prolog: uno zucchero sintattico

• Formalismo DCG– a(A,B) --> c(D),e(I,K).

viene espanso in a(A,B,A0,AN) :- c(D,E,A0,A1),e(I,K,A1,AN).

– a(A,B) --> [a,b].viene espanso in a(A,B,A0,AN) :-

‘C’(A0,a,A1),‘C’(A1,b,AN).

Built-in‘C’([X|A],X,A).

FMZ, Giugno 2001

Linguaggi naturali vs linguaggi formali

La XYZ ha agguantato lo scudetto di campioni d’Italia all’ultima giornata di campionato

S NP VPVP Verb NPVP Verb NP PPNP Art Noun NP NounNP NP PPPP Prep NP

FMZ, Giugno 2001

I problemi dei parser costruiti

• Talvolta non terminano (ricorrenza sinistra)NP NP PP

• Perché funzionano solo in maniera top-down

FMZ, Giugno 2001

Strategie di parsing

• Top-down

• Bottom-up

FMZ, Giugno 2001

Strategie di parsing

• Applichiamole ad un esempio La XYZ ha agguantato lo scudetto di campioni d’Italia all’ultima

giornata di campionato

S NP VPVP Verb NPVP Verb NP PPNP Art Noun NP NounNP NP PPPP Prep NP

FMZ, Giugno 2001


Lezione 3

FMZ, Giugno 2001

Richiami

• Strategie di parsing:– Top-down (es. le regole DCG e il prolog)– Bottom-up

FMZ, Giugno 2001

Limiti del parsing the linguaggio naturale

• Notare l’ambiguità sull’esempio (PP-attachment)• Altri esempi di ambiguità:

Mario guarda l’uomo con la bandieraMario guarda l’uomo con il cannocchialeMario guarda l’uomo con il microscopioLa vecchia porta la sbarraGianna mi ha prestato la borsetta di pelle di

LeonordoGianna mi ha prestato la borsetta di pelle di

leopardo

FMZ, Giugno 2001

Linguaggi naturali vs linguaggi formali

• Costruire l’interpretazione al fine di far emergere l’ambiguità

• Differenze– Linguaggi formali: Si decide il modello che

deve essere rispettato dai locutori. In genere, questo modello non è ambiguo.

– Linguaggi naturali: il modello deve spiegare una fenomenologia preesistente

FMZ, Giugno 2001

Linguaggi naturali

• Problemi intrinseci:– Ambiguità (“genuina” oppure introdotta dal

modello) – Copertura

FMZ, Giugno 2001

(Prima) Stratificazione del regole di parsing

• Livello di interpretazione morfosintattico

• Livello di interpretazione sintattico

FMZ, Giugno 2001

Stratificazione

• Costruzione di un dizionario

• Evidenziare la necessità di feature aggiuntive– Genere/Numero

FMZ, Giugno 2001

Chart Parser

FMZ, Giugno 2001

Limiti del parser DCG (con interprete prolog)

• Implementa solo una strategia top-down

• La struttura della frase viene assegnata solo se completamente riconosciuta.

• Le strutture parziali riconosciute vengono utilizzate solo nella derivazione di cui fanno parte

FMZ, Giugno 2001

Chart Parsing: introduzione

• Definizione del formalismo

• Definizione della struttura dati in prolog

• Implementazione di una strategia di parsing

FMZ, Giugno 2001

Chart parsing: la struttura dati

• Well Formed Substring Table WFST

• La struttura dati è un grafo i cui – Nodi sono i connettori – Archi sono le ragioni per cui i connettori sono

connessi tra loro

FMZ, Giugno 2001

Un esempio di WFST

• Albero vs WFST della frase:Mario guarda l’uomo con il microscopio

FMZ, Giugno 2001

Chart parsing

• Estende l’idea del WFST per permettere di rappresentare goal e ipotesi. La struttura risultante è quella degli active chart

• Il concetto principale è quello delle Dotted RulesA B.C

I simboli a destra del punto sono quelli che sono stati confermati mentre quelli a sinistra sono quelli da confermare.

FMZ, Giugno 2001

Chart Parsing

• Gli archi dell’active chart sono delle dotted rules.

• E’ quindi possibile implementare strategie di parsing:– Bottom-up– Top-down – Ibride

FMZ, Giugno 2001

Chart Parsing

• Dotted rule in prolog:

add_edge(V0,V1,Category,TOBEFOUND,FOUND)

• Un parser bottom-up– esempio

FMZ, Giugno 2001

parse(V0,Vn,String) :-start_chart(V0,Vn,String). % defined in chrtlib1.pl

%add_edge(V0,V1,Category,Categories,Parse) :-

edge(V0,V1,Category,Categories,Parse),!.%add_edge(V1,V2,Category1,[],Parse) :-

assert_edge(V1,V2,Category1,[],Parse),foreach(rule(Category2,[Category1|Categories]),

add_edge(V1,V1,Category2,[Category1|Categories],[Category2])),foreach(edge(V0,V1,Category2,[Category1|Categories],Parses),

add_edge(V0,V2,Category2,Categories,[Parse|Parses])).

add_edge(V0,V1,Category1,[Category2|Categories],Parses) :-

assert_edge(V0,V1,Category1,[Category2|Categories],Parses),foreach(edge(V1,V2,Category2,[],Parse),

add_edge(V0,V2,Category1,Categories,[Parse|Parses])).

FMZ, Giugno 2001


• Parsing sintattico

• Esempi di frasi e loro analisi sintattica

• Formalizzazione semi-intuitiva delle regole utilizzate.

• Limite dell’ambiguità e della copertura

FMZ, Giugno 2001

Gerarchia dei linguaggi

• Come il problema è stato formalizzato?

• Linguaggi regolari– Automi a stati finiti e loro limiti

• Linguaggi context-free

• Linguaggi context-sensitive

• Problema della calcolabilità

FMZ, Giugno 2001 Parsing del linguaggio naturale Fabio Massimo Zanzotto Università di Tor Vergata.

Documents

Transcript of FMZ, Giugno 2001 Parsing del linguaggio naturale Fabio Massimo Zanzotto Università di Tor Vergata.