Elaborazione del linguaggio naturale
CFG: esercizi
Maria Teresa PAZIENZA
a.a. 2007-08
CFG
1. Scrivere una grammatica CFG, sul modello di quella
precedentemente introdotta, in grado di riconoscere le seguenti
frasi:
“Does America 487 have a first class section ? ”
“ Does America Airlines have a flight between 5 and 6 ?”
“ Is there an America airlines flight from Rome to London ?”
2. Produrre i parse-tree relativi alle frasi proposte
ESERCIZIO CFG 1
CFG: problemi
Data la seguente grammatica:
S
NP
Nom
VP
PP
->
->
->
->
->
NP VP
Pron | PropNoun | Det Nom
Noun Nom | Noun
Verb | Verb NP | Verb PP | Verb NP PP
Prep NP
1.
Aumentare la grammatica in modo da gestire i pronomi personali “he, she,
her, him” nel caso corretto. Es:
“He shot her” (corretto)
“Her shot he” (errato)
2.
Aumentare la grammatica in modo da gestire i seguenti patterns di
sottocategorizzazione:
•
Verbi senza NP: disappear
(“I disappear”)
•
Verbi con NP : find, leave, repeat
(“I find the flight”)
•
Verbi con due NP: give, bring
(“give me the book”)
ESERCIZIO CFG 3
Parsing: ricerca
Data la grammatica presentata nella lezione, scrivere lo sviluppo
dell’albero di parsing per le seguenti frasi:
“Book that flight”
“Does the TWA flight include a meal ?”
“Does the flight from Houston include a meal ?”
Utilizzando un parser top-down, depth-first, left-to-right
ESERCIZIO PARS 1
Parsing: left-corners
1. Determinare la tabella dei Left-Corners della seguente grammatica
S
S
NP
NP
NP
NP
PP
VP
VP
VP
2.
->
->
->
->
->
->
->
->
->
->
VP
NP VP
Det Noun
Poss Noun
Pron
NP PP
Prep NP
Verb
Verb NP
Verb PP NP
Det
Noun
Pron
Poss
Verb
Prep
Cong
->
->
->
->
->
->
->
an
elephant|tiger |pajamas|
I
my
shot
in
and
Data la frase “I shot a tiger”, scrivere gli stati prodotti da un parser :
1.
Top-down, depth-first, left-to-right
2.
Left Corner (ovvero con l’aggiunta del filtro bottom-up).
Quali miglioramenti ci sono ?
ESERCIZIO PARS 2
Parsing: ambiguità
Data la seguente grammatica:
S
S
NP
NP
NP
NP
NP
PP
VP
VP
VP
1.
2.
->
->
->
->
->
->
->
->
->
->
->
NP VP
VP
Det Noun
Poss Noun
NP Conj NP
Pron
NP PP
Prep NP
Verb
Verb NP
Verb NP PP
Det
Noun
Pron
Poss
Verb
Prep
Cong
->
->
->
->
->
->
->
an
elephant|tiger |pajamas|
I
my
shot
in
and
Verificare se le seguenti frasi sono sintatticamente ambigue:
-
“I shot an elephant in my pajamas”
-
“I shot an elephant and a tiger”
In caso di ambiguità costruire i relativi parse-tree e dire qual è il tipo di
ambiguità riscontrata
ESERCIZIO PARS 3
Parsing: ambiguità
3. Data la seguente grammatica:
S  NP VP
VP  Verb NP
VP  VP PP
VP  VP Conj VP
NP  NP PP
NP  NP CONJ NP
PP  Prep NP
PP  PP Conj PP
NP  Sally
NP  London
NP  Paris
NP April
Verb loves
P in
Conj  and
verificare se la frase “Sally loves London and Paris in April” è
ambigua. In caso positivo, scrivere tutti i possibili parse-tree
corretti e indicare la tipologia di ambiguità.
ESERCIZIO PARS 3
Parsing: Earley
Data la seguente grammatica:
S
S
NP
NP
VP
VP
Nom
Nom








NP VP
VP
Det Nom
PropN
Verb
Verb NP
Noun
Noun Nom
Noun  elephant | flight
Det  an |the
Verb  takes
Scrivere il processo di parsing completo secondo l’algoritmo di
Earley, per la seguente frase:
“An elephant takes the flight”
ESERCIZIO PARS 4
Suggerimenti per esercizi
Per la migliore comprensione degli argomenti svolti nelle
presentazioni NLP 4,5 si suggerisce di cimentarsi anche
con gli esercizi del libro
Speech and Language Processing, Prentice Hall, 2000,
autori: D.Jurafsky, J. H. Martin
In particolare:
Capitolo 9, esercizi n. 9.1, 9.2, 9.3, 9.5, 9.9, 9.10, 9.11
facoltativo
Capitolo 10, esercizi n. 10.1, 10.3, 10.4, 10.5, 10.6
ESERCIZIO 6