Sintassi e parsing
Note di studio complete. Fonti:
tln/6 - Parte 1 - Lezione 06/lezione-04-Syntax01-TLN-INFO-2526.pdf(52 pp.),
tln/7 - Parte 1 - Lezione 07/lezione-04-Syntax02-TLN-INFO-2526.pdf(85 pp.),
tln/8 - Parte 1 - Lezione 08/lezione-04-Syntax03-TLN-INFO-2526.pdf(71 pp.).
Riferimenti ai capitoli intln/references.md.
1. Perche’ la sintassi e le ambiguita’ (Syntax01)
La sintassi descrive come le parole si combinano in sintagmi e frasi. Due rappresentazioni:
- Costituenti: albero di sintagmi annidati (S -> NP VP; NP -> Det N…). Il costituente e’ un gruppo
che si comporta come unita’ (test di sostituzione, movimento, coordinazione). - Dipendenze: grafo di archi testa -> dipendente con etichette (nsubj, obj, det, amod…).
Piu’ vicina ai ruoli semantici; standard Universal Dependencies (UD).
Ambigue sintattiche centrali (domande d’esame):
- PP attachment: Ho visto l’uomo con il telescopio — il PP con il telescopio si attacca al verbo
(strumento: ho usato il telescopio) o al nome (l’uomo che ha il telescopio)? Classico problema
risolto statisticamente (preferenze lessicali testa-preposizione-testa). - Ambigue della coordinazione: old men and women — old modifica solo men o entrambi?
Struttura[old [men and women]]vs[[old men] and women]. - Altre: attaccamento di relative, portata della negazione, garden path.
2. Grammatiche libere dal contesto (CFG)
G = (N, Sigma, P, S): non-terminali, terminali, produzioni, simbolo iniziale.
Esempio giocattolo (stile simple-sem.fcfg usata nel corso e nel progetto 2):
S -> NP VP
NP -> Det N | Det N PP | PROPN
VP -> V NP | V NP PP | V
PP -> P NP
Det -> 'il' | 'la' | ...
N -> 'cane' | 'uomo' | ...
- Derivazione: riscritture da S; albero di derivazione = struttura; frase = foglie.
- Grammatica ambigua se una frase ha due alberi (PP attachment = due derivazioni!).
- Forma normale di Chomsky (CNF): produzioni solo
A -> B CoA -> w. Ogni CFG si converte
in CNF (binarizzazione + eliminazione epsilon/unitarie). Il progetto 2 chiede di costruire G1
direttamente in CNF ispirandosi asimple-sem.fcfg. - Weak vs strong equivalence: stessa lingua generata vs stessi alberi assegnati.
3. CKY (Syntax02, domanda d’esame)
Algoritmo CKY (Cocke-Kasami-Younger): parsing bottom-up per grammatiche in CNF, DP sulla tabella
triangolare T[i,j] = non-terminali che derivano la sottostringa w_i..w_j.
per i: T[i,i] = { A : A -> w_i }
per lunghezza 2..n:
per i, per k in [i, j):
se B in T[i,k], C in T[k+1,j] e A -> B C: aggiungi A a T[j... ] (T[i,j])
accetta se S in T[1,n]
- Complessita’: O(n^3 * |P|) (domanda d’esame: cubica in N, lunghezza dell’input).
- Con backpointer si ricostruisce l’albero (o la foresta di tutti gli alberi).
- Versione probabilistica: PCKY con
P(A -> B C)e max invece di esistenza (cfr. §4).
Anatomia di un parser (domanda d’esame): componenti tipiche — grammatica, lessico/tag,
strategia di ricerca (bottom-up/top-down), tabella/chart (memoization), disambiguazione
(probabilita’ o euristiche), valutazione.
4. PCFG (domanda d’esame)
Probabilistic CFG: ogni produzione ha P(A -> alpha), con somma 1 per ogni testa A.
Probabilita’ di un albero = prodotto delle produzioni usate; di una frase = somma su tutti gli alberi.
Stima MLE da treebank (conteggi). Parsing: CKY probabilistico (max) o inside-outside (EM per
grammatiche non annotate). Problema: indipendenza contestuale troppo forte (una NP soggetto come
una NP oggetto) -> parent annotation / lexicalization (Collins, Charniak).
5. Parsing a dipendenze (Syntax03)
Cinque algoritmi per il parsing delle dipendenze (domanda d’esame: elencare i 5):
- Chart Eisner (projective, DP O(n^3)).
- MST / graph-based (McDonald: maximum spanning tree su grafo completo, non-projective).
- Transition-based arc-standard / arc-eager (MALT, Nivre: shift-reduce con classificatore, lineare).
- Transition-based con beam / stack-LSTM (estensioni neurali con ricerca).
- Doubly-projective / pseudo-projective o biaffine neurale (Dozat-Manning: scorer biaffine
su BiLSTM, stato dell’arte pre-LLM).
Transition-Based Parser / MALT (domanda d’esame: come funziona?):
sistema a stati (stack, buffer, archi) + azioni (SHIFT, LEFT-ARC, RIGHT-ARC, REDUCE);
un classificatore (SVM/MLP) predice l’azione dallo stato; parsing lineare greedy (o con beam).
Esempio: I Jedi non possono avere figli -> avere -nsubj-> Jedi, Jedi -det-> I, avere -obj-> figli
(slide del progetto 3.A: cercare regolarita’ con udpipe/spaCy/Stanza/Tint).
Valutazione: UAS (testa giusta), LAS (testa+etichetta giuste).
6. Treebank e PARSEVAL (domande d’esame)
- Treebank: corpus con alberi sintattici annotati (PTB inglese, TUT/VIT italiano, UD multilingua).
Servono per training (MLE delle PCFG, classificatori delle transizioni) e valutazione. - PARSEVAL: metrica su costituenti — precision/recall/F1 sui parentesi (bracket) del parse
rispetto al gold; ignora in genere POS e punteggiatura; crossing brackets come errore grave.
7. Collegamenti con l’esame
- Domande dirette: PP attachment e coordinazione; CKY + complessita’; PCFG; 5 algoritmi dipendenze;
MALT; costituenti vs dipendenze; PARSEVAL; treebank; anatomia di un parser. - Progetto 2 (IT->IT-YO) = CFG in CNF + CKY + riscrittura dell’albero (SVX -> XSV).
- Progetto 3.A usa parser a dipendenze per estrarre regolarita’.
Fonti slide (pdftotext): Syntax01 ~888 righe (costituenti, ambiguita’); Syntax02 ~996 (CKY, PCFG);
Syntax03 ~1350 (dipendenze, MALT, valutazione). File grammaticali: tln/9 - .../simple-sem.fcfg,
simple-sem-it-02.fcfg.