Grammatica ad albero adiacente - Tree-adjoining grammar
Tree-adjoining grammar ( TAG ) è un formalismo grammaticale definito da Aravind Joshi . Le grammatiche adiacenti agli alberi sono in qualche modo simili alle grammatiche libere dal contesto , ma l'unità elementare di riscrittura è l'albero piuttosto che il simbolo. Mentre le grammatiche prive di contesto hanno regole per riscrivere i simboli come stringhe di altri simboli, le grammatiche adiacenti ad albero hanno regole per riscrivere i nodi degli alberi come altri alberi (vedere albero (teoria dei grafi) e albero (struttura dei dati) ).
Storia
TAG ha avuto origine dalle indagini di Joshi e dei suoi studenti sulla famiglia delle grammatiche aggiunte (AG), la "grammatica degli archi" di Zellig Harris . Gli AG gestiscono le proprietà esocentriche del linguaggio in modo naturale ed efficace, ma non hanno una buona caratterizzazione delle costruzioni endocentriche ; il contrario è vero per la riscrittura delle grammatiche o la grammatica della struttura delle frasi (PSG). Nel 1969, Joshi ha introdotto una famiglia di grammatiche che sfrutta questa complementarità mescolando i due tipi di regole. Poche regole di riscrittura molto semplici sono sufficienti per generare il vocabolario delle stringhe per le regole di aggiunta. Questa famiglia è distinta dalla gerarchia di Chomsky-Schützenberger ma la interseca in modi interessanti e linguisticamente rilevanti. Le stringhe centrali e le stringhe aggiunte possono anche essere generate da una grammatica delle dipendenze , evitando completamente i limiti dei sistemi di riscrittura.
Descrizione
Le regole in un TAG sono alberi con uno speciale nodo foglia noto come nodo del piede , che è ancorato a una parola. Ci sono due tipi di alberi di base in TAG: alberi iniziali (spesso rappresentati come " ") e alberi ausiliari (" "). Gli alberi iniziali rappresentano le relazioni di valenza di base, mentre gli alberi ausiliari consentono la ricorsione. Gli alberi ausiliari hanno il nodo radice (superiore) e il nodo del piede etichettati con lo stesso simbolo. Una derivazione inizia con un albero iniziale, che si combina tramite sostituzione o aggiunta . La sostituzione sostituisce un nodo di frontiera con un altro albero il cui nodo superiore ha la stessa etichetta. L'etichetta radice / piede dell'albero ausiliario deve corrispondere all'etichetta del nodo a cui è adiacente. L'adattamento può quindi avere l'effetto di inserire un albero ausiliario al centro di un altro albero.
Altre varianti di TAG consentono alberi multicomponente , alberi con più nodi di piede e altre estensioni.
Complessità e applicazione
Grammatiche albero-adiacente sono più potenti (in termini di debole capacità generativa ) rispetto grammatiche context-free , ma meno potente di sistemi lineari non contestuali riscrittura , indicizzati o sensibili al contesto grammatiche.
Un TAG può descrivere la lingua dei quadrati (in cui viene ripetuta una stringa arbitraria) e la lingua . Questo tipo di elaborazione può essere rappresentato da un automa pushdown incorporato . Le lingue con cubi (cioè stringhe triplicate) o con più di quattro stringhe di caratteri distinte di uguale lunghezza non possono essere generate da grammatiche ad albero adiacenti.
Per questi motivi, le grammatiche adiacenti ad albero sono spesso descritte come leggermente sensibili al contesto . Si ipotizza che queste classi grammaticali siano abbastanza potenti da modellare linguaggi naturali pur rimanendo analizzabili in modo efficiente nel caso generale.
Equivalenze
Vijay-Shanker e Weir (1994) dimostrano che le grammatiche indicizzate lineari , la grammatica categoriale combinatoria, le grammatiche albero-adiacenti e le grammatiche dell'intestazione sono formalismi debolmente equivalenti , in quanto definiscono tutte le stesse lingue di stringa.
Lessicalizzato
Le grammatiche lessicalizzate ad albero adiacente (LTAG) sono una variante di TAG in cui ogni albero elementare (iniziale o ausiliario) è associato a un elemento lessicale. Una grammatica lessicalizzata per l'inglese è stata sviluppata dall'XTAG Research Group dell'Institute for Research in Cognitive Science presso l'Università della Pennsylvania.
Appunti
Riferimenti
link esterno
- Il progetto XTAG , che utilizza un TAG per l'elaborazione del linguaggio naturale.
- Un tutorial su TAG
- Documentazione SemConst Una rapida indagine sulle problematiche di sintassi e interfaccia semantica all'interno del framework TAG.
- Il progetto TuLiPa La Tübingen Linguistic Parsing Architecture (TuLiPA) è un ambiente di parsing sintattico (e semantico) multi-formalismo, progettato principalmente per grammatiche adiacenti ad albero multicomponente con tuple di alberi
- Metagrammar Toolkit che fornisce diversi strumenti per modificare e compilare MetaGrammars in TAG. Include anche un'ampia copertura di Metagrammari francesi.
- LLP2 Un analizzatore grammaticale adiacente ad albero lessicalizzato che fornisce un ambiente grafico facile da usare (pagina in francese)