Parsing del linguaggio naturale
Fabio Massimo Zanzotto
Università 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
Analisi del testo di un
programma
• 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
• Quintupla
V insieme dei simboli
Q insieme degli stati
d 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
Analisi del testo di un
programma
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-statement
if
then
(a>b)
else
printf(“Bye Bye World!”);
printf(“Hello World!”);
a++;
FMZ, Giugno 2001
Il problema in generale
V
insieme di simboli
L  V*
il linguaggio
Esiste un meccanismo che possa dire se dato un
lV* 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
Da testo di un programma ad
albero
if (a>b) {
printf(“Hello World!”);
a++;
}
FMZ, Giugno 2001
Da testo di un programma ad
albero
if-statement
then
if
(a>b)
printf(“Hello World!”);
FMZ, Giugno 2001
Da testo di un programma ad
albero
REGOLE:
if-statement  if condition instructions
if-statement 
if condition instructions else instructions
FMZ, Giugno 2001
Il parser
Testo
Programma
PARSER
Regole
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
Il parsing del linguaggio naturale
• 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
la XYZ ha agguantato lo scudetto
S  NP VP
VP  Verb NP
NP  Art Noun
Noun  XYZ
Noun  scudetto
Art  la
Art  lo
Verb  ha agguantato
FMZ, Giugno 2001
Parsing e linguaggio naturale
Lezione 2
FMZ, Giugno 2001
Parsing e linguaggio naturale
• 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 simboli
L  V*
il linguaggio
Esiste un meccanismo che possa dire se dato un
lV* 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
Il parsing del linguaggio naturale
• 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
la XYZ ha agguantato lo scudetto
S  NP VP
VP  Verb NP
NP  Art Noun
Noun  XYZ
Noun  scudetto
Art  la
Art  lo
Verb  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 VP
VP  Verb NP
VP  Verb NP PP
NP  Art Noun
NP  Noun
NP  NP PP
PP  Prep NP
FMZ, Giugno 2001
I problemi dei parser costruiti
• Talvolta non terminano (ricorrenza sinistra)
NP  NP PP
• Perché funzionano solo in maniera topdown
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 VP
VP  Verb NP
VP  Verb NP PP
NP  Art Noun
NP  Noun
NP  NP PP
PP  Prep NP
FMZ, Giugno 2001
Parsing e linguaggio naturale
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 bandiera
Mario guarda l’uomo con il cannocchiale
Mario guarda l’uomo con il microscopio
La vecchia porta la sbarra
Gianna mi ha prestato la borsetta di pelle di
Leonordo
Gianna 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 Rules
A 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],[Categ
ory2])),
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
Il parsing del linguaggio naturale
• 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