Elaborazione del linguaggio naturale Analisi sintattica: parsingCHAOSMaria Teresa PAZIENZAa.a. 2007-08

SommarioStrumenti per la Sintassi

IntroduzioneContext-Free Grammar (CFG)DefinizioneCFG per la sintassiLimiti e problemiParsingParsing a costituentiParsing Top-DownParsing Bottom-UpParsing misto (left-corner)Chart parsingProgrammazione dinamicaAlgoritmo di EarleyParsing a dipendenzeCenniConversioneParser EvaluationChaos

CHAOS: A robust syntactic parser for Italian and for EnglishCHAOS is a modular and lexicalized syntactic and semantic parser for Italian and for English. The system implements a modular and lexicalised approach to the syntactic parsing problem.

It is based on the notion of eXtended Dependency Graph (XDG) that is considered as a useful representation mechanism in a shallow parsing approach, thus supporting the representation of alternative syntactic interpretation.The system offers a collection of modules for designing parsing architectures.

The overall system is seen as a JAVA library offering a standard representation for modules implemented in different programming languages.

CHAOS: eXtended Dependency Graph example

CHAOS: eXtended Dependency Graph exampleXDG is a mixture of dependencies and constituents.

It is a dependency graph whose nodes C are constituents and whose edges ICD are the grammatical dependencies among constituents.

Each node is a complete tree whose nodes are feature structures.

The XDG formalism efficiently models the syntactic ambiguity.

CHAOS: A robust syntactic parser for Italian and for EnglishThe pool of modules consists of:

a tokenizer, TOK, matching words from character streams a yellow page look-up module YP, that matches named entities existing in catalogues a morphologic analyser MOA that attaches (possibly ambiguous) syntactic categories and morphological interpretations to each word a named entities matcher NER, that recognizes complex named entities according to special purpose grammars a rule-based part-of-speech tagger POSa POS disambiguation module PMF that resolves potential conflicts among the results of the POS tagger and the morphologic analyser a chunker CHKa verb argument detector VSAa shallow syntactic analyser SSA

Chaos: Parsing sintattico ITDipend. Verbali Dipend. non verbaliCostituente complessoTesta verbale della fraseXDG (grafo costituenti-dipendenze) costituenti : chunks Icd : inter-chunks dependeciesLanalisi viene rappresentata in una struttura unica:plausibilit

Chaos: Parsing sintattico ITApproccio ibrido:COSTITUENTI + DIPENDENZE

Vengono identificati i chunks (particolare tipo di costituenti)Vengono identificate le dipendenze

Vantaggi:Il raggruppamento in chunks facilita lanalisi a dipendenzeLanalisi a dipendenze consente di gestire long distance dependecies ed altri fenomeniLutilizzo della plausibilit (certezza nellidentificare la dipendenza) permette di gestire lambiguitTre moduli fondamentali:Chunker : identifica i chunksVerb Shallow Analyzer (VSA) : identifica le dipendenze verbali principaliSyntactic Shallow Analyzer (SSA) : identifica altre dipendenze

Chaos: Parsing sintattico ITCHAOS Chunker [/data/KB/it/Chunker]ChunkI chunk sono un particolare tipo di costituentiNucleo non ricorsivo di sintagmi Non essendoci ricorsivit, i chunk possono essere riconosciuti da FSAInformazione pregressa necessaria:MorfologiaPOS tagging

Come funziona il Chaos Chunker:Basato su prototipi di chunk in PrologAnalizza le parole da sinistra a destra, raggruppandole nel chunk pi lungo possibile riconosciuto applicando le regoleIndividua:Governatore: parola che veicola il significato del chunkTesta sintattica (head): parola che lega il chunk al resto della frase

Chaos: Parsing sintattico ITCHAOS Chunker [/data/KB/it/Chunker]Come identificare un chunk ? Nella pratica, il chunk il pi grande costituente possibile che lascia la frase aperta a tutte le ammissibili interpretazioni sintattiche.

ESEMPI:[Il bel gatto] mangia il topo Il bel gatto chunk in quanto la sequenza DET-ADJ-NC lunica aggregazione possibile, ovvero lADJ legato sempre come specificazione dellNC in tutte le frasi italiane [Il gatto] [del vicino] magia il topoIl gatto del vicino un costituente, ma non un chunk, in quanto la sequenza DET-NC-PREP-NC non lunica interpretazione sintattica possibile. Ovvero esistono sequenze di questo tipo in cui PREP-NC non sono specificazioni di NC, ma di un altro elemento della frase, ad esempio: Il gatto nel prato mangia, nel prato specifica mangia[Il gatto] [interessato] al topoIl gatto interessato non un chunk, in quanto la sequenza DET-NC-ADJ non garantisce tutte le interpretazioni sintattiche possibili. Ovvero, il PREP-NC seguente in alcuni casi specifica DET-NC (es.Il gatto interessato al topo), in altri ADJ (Il gatto interessato del vicino)

Chaos: Parsing sintattico ITCHAOS Chunker [/data/KB/it/Chunker]Prototipi Prolog per il riconoscimento di semplici chunk aggettivali:

constituent_class([_cst1], 'Agg', _mor, 1, 1):-adjective(_cst1),common_morfology(_cst1, _mor).

constituent_class([_cst1, _cst2], 'Agg', _mor, 1, 2):-adverb(_cst1),adjective(_cst2),common_morfology(_cst1, _cst2, _mor).

constituent_class([_cst1, _cst2, _cst3], 'Agg', _mor, 1, 1):-adjective(_cst1),coordinative_conjunction(_cst2),\+(comma(_cst2)),adjective(_cst3),common_morfology(_cst1, _cst3, _mor).ADJADJCOORDADJADVADJ

Chaos: Parsing sintattico ITCHAOS Chunker [/data/KB/it/Chunker]COMPLEX CONSTITUENT (chunk)SIMPLE CONSTITUENT (sotto-costituenti del chunk)governorhead

Chaos: Parsing sintattico ITCHAOS ChunkTypes in IT AggChunk aggettivaliAvvChunk avverbialeCongCoChunk coordinativoCongSubChunk subordinativoNomChunk nominalePrepChunk preposizionaleVerFinChunk verbale finitoVerGerChunk verbale gerundivoVerInfChunk verbale infinitoVerPartChunk verbale participioVerPredChunk verbale predicativo aggettivaleVerNomChunk verbale nominaleVerPrepChunk verbale preposizionale?Chunk sconosciuti

Chaos: Parsing sintattico ITCHAOS VSA [/data/KB/it/SubcatLexicon]Identifica le dipendeze (icd) verbali allinterno della strutturaUtilizza un lessico di patterns di sottocategorizzazione verbale (LIFUV.lex)1844 sottocategorizzazioniCodificate manualmente ed apprese automaticamente da corporaUna dipendenza ricavata dal lessico ha plausibilit=1pattern(accrescere,[[(oggetto,Post)]]).pattern(accucciare,[[]]).pattern(accumulare,[[(su,Post)],[(oggetto,Post)],[(oggetto,Post)]]).pattern(acquisire,[[(oggetto,Post),(a,Post)],[(oggetto,Post)]]).pattern(acquistare,[[(in,Post)],[(oggetto,Post),(da,Post)]]).pattern(adagiare,[[(su,Post)],[(oggetto,Post),(su,Post)]]).pattern(addolcire,[[(oggetto,Post)],[(oggetto,Post)]]).

Chaos: Parsing sintattico ITCHAOS SSA [/data/KB/it/SSG]Identifica le dipendeze (icd) che non sono state identificate dallVSA:Modificatori verbali: espressioni temporali / spaziali Modificatori nominali: sintagmi preposizionali / specificatori aggettivali Come funziona:E un parser specifico basato su una grammatica discontinuaConsente di trovare dipendenze tra chunk non adiacenti (gap) anche long distance dependenciesAmbiguit: pi dipendenze possono essere prodotte per uno stesso chunkViene utilizzata la pausibilit per modellare lambiguitPOS tagging

Chaos: Parsing sintattico ITCHAOS ICDs Types (VSA+SSA) Grammatical Subject V_Sog Grammatical ObjectV_Obj Indirect ObjectV_NP Verb Preposition Modifier V_PP Verb Adverb Modifier V_Adv gruppo Nominale NominaleNP_NP gruppo Nominale Preposizionale NP_PP gruppo Preposizionale Preposizionale PP_PP gruppo Nominale Aggettivo NP_Adj gruppo Nominale Participio NP_VPart gruppo Preposizionale Aggettivo PP_Adj gruppo Preposizionale Participio PP_VPart gruppo Aggettivo Preposizionale Adj_PP gruppo Avverbio Preposizionale Adv_PPCongiunzione coordinativa tra costituentix_Cong_xgruppo Costituente Congiunzionex_Conggruppo Costituente Subordinatax_Subgruppo Verbo Congiunzione SubordinativaV_CSub

Chaos: ValutazioneUtilizzare :Le misure per i parser a costituenti per valutare i chunkLe misure per i parser a dipendenze per valutare gli ICDNon considerare le plausibilit nella valutazione Esempio: GOLD:CHAOS:Chunks:Prec = 5/5 = 1Rec = 5/5 = 1Lab Prec = 4/5= 0.8Lab Rec = 4/5= 0.8ICD:Prec = 1/5 = 0.2Rec = 1/3 =0.3

Progetto : NoteCostrutti frasali complessi in Chaos:Congiunzione

Progetto : NoteCostrutti frasali complessi in Chaos:Subordinazione

*******************