Syntactic Parsing
Obiettivo
• Richiamo: Discussione della derivazione nelle
grammatiche context-free e relazione con gli
alberi
• Obiettivo di un parser: Costruire alberi a partire da
frasi
© F.M.Zanzotto
Outline
• Parsing Algorithms
–
–
–
–
© F.M.Zanzotto
Top down
Bottom Up
CYK
Early Algorithm / Chart Parsing
Parsing CF with Cocke-Younger-Kasami
(CYK) algorithm
Grammar in CNF*
---
----
----
----
----
----
----
----
----
S→AB|BC
A→BC|a
B→BB|CC|b
C→a
----
b
© F.M.Zanzotto
a
a
b
a
FMZ
*CNF Chomsky Normal Form
Parsing CF with Cocke-Younger-Kasami
(CYK) algorithm
Grammar in CNF
S
---
B
----
----
----
----
----
----
----
----
B
A,S
B
S
A,S
----
B
C,A
C,A
B
C,A
b
a
a
b
a
© F.M.Zanzotto
FMZ
S→AB|BC
A→BC|a
B→BB|CC|b
C→a
Parsing CF with Cocke-Younger-Kasami
(CYK) algorithm
input: a1 ... an.
Pn,n is the matrix of sets of symbols initially Pn,n =
For each i = 1 to n
For each unit production Rj → ai, set P1,j = {Rj}
For each i = 2 to n
For each j = 1 to n-i+1
For each k = 1 to i-1
For each production RA → RB RC
If RBPj,k and RC Pj+k,i-k then Pj,i = Pj,i  {RA}
If R1 P[1,n]
Then string is member of language
Else string is not member of language
© F.M.Zanzotto
FMZ
Parsing CF with Cocke-Younger-Kasami
(CYK) Limits
• CYK relies on Chomsky Normal Form
hence
• there is no freedom on the final structure
• a CYK parser has to be coupled with a tree
transformer
CYK is a very interesting theoretical result but
let us find a more flexible parser!!!
© F.M.Zanzotto
FMZ
Early Algorithm
© F.M.Zanzotto
Natural Language and its Models
• Formal Languages
Languages are artificially designed.
The Chomsky Level is choosen
Structural ambiguity is controlled and semantic is made
“clear”
• Natural Languages
– It is a social phenomenon... as such has to be studied
– It exists and evolves
– People use differently natural language (performance)
according to their language competence
© F.M.Zanzotto
FMZ
Observing natural language
.... La rivoluzione è la voce che corre sul web. ...
... Netto recupero anche per Iberia, mentre si riprende del 4,1%
anche British Airways.
... Nella tabella la chiusura degli indici dei titoli guida delle
principali piazze finanziarie del Vecchio Continente ...
... Mentre il professore spiega il modello climatico, Roberto e i
colleghi sperimentano l'influenza di diversi parametri sulle
previsioni meteorologiche. ...
© F.M.Zanzotto
FMZ
A sample Grammar (introspectively
produced)
S  NP VP | S SBAR | SBAR S
SBAR  CongSub S
S  S CongCoord S | S, S CongCoord S
NP  NP SBAR
VP  Verb NP
VP  Verb NP PP
NP  Art Noun | Art Adj Noun | Noun | NP PP
PP  Prep NP
© F.M.Zanzotto
FMZ
Observing natural language
Telefonia, la rivoluzione è la voce che corre sul web
Si chiama Voip, è una rivoluzione perché abbatte i costi delle telefonate ma arriverà solo quando sarà chiaro
come si potrà evitare che distrugga i bilanci delle telecom
Finisce così con l'avere un impatto contenuto il brusco tonfo segnato dalla fiducia degli investitori tedeschi,
con una flessione inattesa dell'indice Zew a marzo da 69,9 punti a quota 57,6. Il rimbalzo più deciso viene
messo a segno da Madrid (+1,45%), maggiormente penalizzata nelle scorse sessioni, dopo che anche le
banche d'affari consigliano di acquistarne i titoli. Hsbc, in particolare, ha ribadito l'indicazione di sovrappesare
le azioni spagnole giudicando improbabili grandi cambiamenti alle politiche economiche da parte del nuovo
governo socialista.
Tra i bancari, in progresso Credit Suisse (+1,7%). Mentre corre la spagnola Santander Central Hispano
(+1,8%). Nel comparto aereo, netto recupero anche per Iberia (+7,5%), mentre si riprende del 4,1% anche
British Airways. Virgin Express, la compagnia low cost di Richard Branson, termina invariata dopo la
formalizzazione con una lettera di intenti delle trattative di fusione con Sn Brussels Airlines (ex Sabena). Il
comparto non registra però nessuna fiammata sulle attese di consolidamento e Ryanair termina in calo del
2,39%, Klm avanza di un modesto 0,49%. Dopo le vendite delle ultime sedute, Air France rimbalza
dell'1,20%. Nel comparto petrolifero, è la spagnola Repsol (+1,42%) la blue chip più vivace, mentre Bp segna
un progresso dello 0,22%. Invariata Shell, giù dello 0,36% Royal Dutch. La francese Total cede lo 0,14%.
© F.M.Zanzotto
FMZ
Observations
• The sample grammar is insufficient!!
• NL is not completely captured!
• However, it is possible to think to a
camprehensive model? An NL model can cover all
natural language phenomena?
© F.M.Zanzotto
FMZ
Model Coverage
• A complete model can be hardly achieved
• Augmenting the coverage may imply also
augmenting the induced ambiguity of the model
• The model can cover partially a sentence.
• Partial analysis are also relevant
© F.M.Zanzotto
FMZ
Partial Analysis may be relevant...
... sai: questa cosa che è cosata all'improvviso, non so se è
una cosa che coserà, ma coso di sì, anche se, cosando le
solite cose, coso a cosare che le cose si cosino cosabilmente
e che le cose non cosino per sempre, che siano cosabili,
cosibili, soprattutto cosubili. Queste cose si stracosano
all'inizio, poi si cosano, si discosano, si supercosano, fino a
cosarsi di nuovo, e noi, in tutto questo, non ci possiamo
cosare nessuna cosa, anche se adesso io ti coso cose e tu mi
cosi cose, e tutti cosiamo le cose che ci cosiamo fino a
scosarci e ricosarci all'infinito...
© F.M.Zanzotto
FMZ
Model Ambiguity
• Genuine ambiguity
Time flies like an arrow
Flying planes can be dangerous
La vecchia porta la sbarra
• Model-induced Ambiguity
NP  Art Noun | Art Adj Noun | Noun | NP PP
Nella tabella la chiusura degli indici dei titoli guida delle
principali piazze finanziarie del Vecchio Continente
© F.M.Zanzotto
FMZ
Aim
• Build a formalism/model able to give the
possibility of reducing the unnecessary
interpretations
• Build a formalism (and an associated algorithm)
able to represent partial analysis
• We want the freedom to adopt bottom-up or topdown algorithms
© F.M.Zanzotto
FMZ
What we have done?
• CNF grammars and CYK:
– a bottom-up algorithm
– it stores partial analyses
• CFG and prolog:
– a top-down algorithm
– it does not store partial analysis
– many subtrees are recomputed in the different analyses
© F.M.Zanzotto
FMZ
Parsing CF with Cocke-Younger-Kasami
(CYK) algorithm
Grammar in CNF
S
---
B
----
----
----
----
----
----
----
----
B
A,S
B
S
A,S
----
B
C,A
C,A
B
C,A
b
a
a
b
a
© F.M.Zanzotto
FMZ
S→AB|BC
A→BC|a
B→BB|CC|b
C→a
Chart Parsing and Early Algorithm
FMZ
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
© F.M.Zanzotto
FMZ
Un esempio di WFST
SNP VP
VP  VP NP
VP  VP NP PP
NP  NP PP
PP  Prep NP
NP  Art Noun
NP
Noun
VP
Verb
NP
Art
Noun
Prep
Mario guarda l’ uomo con
© F.M.Zanzotto
FMZ
Art
il
Noun
microscopio
Chart Parsing
S  NP VP | S SBAR | SBAR S
• Making the chart WFST
active: representing a
state of the analysis
SBAR  CongSub S
S  S CongCoord S | S, S CongCoord S
NP  NP SBAR
VP  Verb NP
VP  Verb NP PP
NP  Art Noun | Art Adj Noun | Noun | NP PP
PP  Prep NP
NPNP•PP
PPPrep•NP
NP  Art Noun
NP
Noun
VP
Verb
NP
Art
Noun
Mario guarda l’ uomo con
© F.M.Zanzotto
FMZ
Art
Prep
il
Noun
microscopio
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.
© F.M.Zanzotto
FMZ
Chart Parsing
• Gli archi dell’active chart sono delle dotted
rules.
• E’ quindi possibile implementare strategie di
parsing:
– Bottom-up
– Top-down
– Ibride
© F.M.Zanzotto
FMZ
Chart Parsing: introduzione
• Definizione del formalismo
• Definizione della struttura dati in prolog
• Implementazione di una strategia di parsing
© F.M.Zanzotto
FMZ
Chart Parsing
• Dotted rule in prolog:
edge(V0,V1,Category,TOBEFOUND,FOUND_STRUCTURED)
• Rule:
rule(Mother,List_of_daughters)
• Lexicon:
word(Category,Word).
Un parser bottom-up
– esempio
© F.M.Zanzotto
FMZ
Bottom-up Chart Parsing (a)
parse(V0,Vn,String) :start_chart(V0,Vn,String).
% defined in chrtlib1.pl
start_chart(V0,V0,[]).
start_chart(V0,Vn,[Word|Words]) :V1 is V0+1,
foreach(word(Category,Word),
add_edge(V0,V1,Category,[],[Word,Category])),
start_chart(V1,Vn,Words).%
add_edge(V0,V1,Category,Categories,Parse) :edge(V0,V1,Category,Categories,Parse),!.
© F.M.Zanzotto
FMZ
Bottom-up Chart Parsing (b)
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])).
© F.M.Zanzotto
FMZ
BU Chart in action
in black real edges
in red add_edge
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])).
NP • Noun
Noun
© F.M.Zanzotto
Mario guarda l’ uomo con
FMZ
il ....
Bottom-up Chart Parsing (c)
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])).
© F.M.Zanzotto
FMZ
BU Chart in action
in black real edges
in red add_edge
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])).
NP Noun •
NP • Noun
Noun
© F.M.Zanzotto
Mario guarda l’ uomo con
FMZ
il ....
BU Chart in action
in black real edges
in red add_edge
S NP • VP
NP Noun •
Noun
© F.M.Zanzotto
Mario guarda l’ uomo con
FMZ
il ....
BU Chart in action
add_edge(V1,V2,Category1,[],Parse) :assert_edge(V1,V2,Category1,[],Parse),
in black real edges
in red add_edge
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])).
S NP • VP
VP  VP NP •
NP Noun •
VPVerb
Noun
Verb
© F.M.Zanzotto
Mario guarda l’ uomo con
FMZ
il ....
Bottom-up Chart Parsing (d)
foreach’s mistery
%
% foreach - for each X do Y
%
foreach(X,Y) :X,
do(Y),
fail.
foreach(X,Y) :true.
do(Y) :- Y,!.
© F.M.Zanzotto
FMZ
Where are we?
• NL is a phenomenon to be studied:
– building a model implies understanding how it behaves
– Performance makes things difficult
• A compentence model hardly explain all the
possible produced sentences
• Partial analyses are needed
– Charts are proposed as a good for storing partial and
competing analysis
© F.M.Zanzotto
FMZ
What’s next?
• The eternal struggle between coverage and
ambiguity.
• Feacture structures to empower the language of
representig grammatical rules
© F.M.Zanzotto
FMZ