albero di analisi - Parse tree

Un albero di analisi o parsing albero o derivazione albero o albero di sintassi calcestruzzo è un radicato ordinata albero che rappresenta la sintattica struttura di una stringa secondo alcuni grammatica libera dal contesto . Il termine stesso albero di analisi è usato principalmente nella linguistica computazionale ; nella sintassi teorica, il termine albero di sintassi è più comune.

Gli alberi di sintassi concreti riflettono la sintassi del linguaggio di input, rendendoli distinti dagli alberi di sintassi astratti utilizzati nella programmazione di computer. A differenza dei diagrammi delle frasi di Reed-Kellogg utilizzati per insegnare la grammatica, gli alberi di analisi non utilizzano forme di simboli distinte per i diversi tipi di componenti .

Gli alberi di analisi sono generalmente costruiti sulla base della relazione di collegio elettorale delle grammatiche di collegio elettorale ( grammatiche della struttura della frase ) o della relazione di dipendenza delle grammatiche di dipendenza . Gli alberi di analisi possono essere generati per frasi in linguaggi naturali (vedi elaborazione del linguaggio naturale ), nonché durante l' elaborazione di linguaggi di computer, come i linguaggi di programmazione .

Un concetto correlato è quello di marcatore di frase o marcatore P , come usato nella grammatica generativa trasformazionale . Un marcatore di frase è un'espressione linguistica contrassegnata dalla struttura della frase. Questo può essere presentato sotto forma di albero o come espressione tra parentesi. I marcatori di frase vengono generati applicando le regole della struttura delle frasi e sono essi stessi soggetti a ulteriori regole di trasformazione. Un insieme di possibili alberi di analisi per una frase sintatticamente ambigua è chiamato "foresta di analisi".

Nomenclatura

Un albero di analisi è costituito da nodi e rami. Nella figura l'albero di analisi è l'intera struttura, partendo da S e finendo in ciascuno dei nodi foglia (John, ball, the, hit). In un albero di analisi, ogni nodo è un nodo radice , un nodo ramo o un nodo foglia . Nell'esempio sopra, S è un nodo radice, NP e VP sono nodi ramificati, mentre John, ball, the e hit sono tutti nodi foglia.

I nodi possono anche essere indicati come nodi padre e nodi figlio. Un nodo genitore è uno che ha almeno un altro nodo collegato da un ramo sotto di esso. Nell'esempio, S è un genitore sia di NP che di VP. Un nodo figlio è uno che ha almeno un nodo direttamente sopra di esso al quale è collegato da un ramo dell'albero. Sempre dal nostro esempio, hit è un nodo figlio di V.

Una funzione non terminale è una funzione (nodo) che è una radice o un ramo in quell'albero mentre una funzione terminale è una funzione (nodo) in un albero di analisi che è una foglia.

Alberi di analisi basati sulla circoscrizione

Gli alberi di analisi delle grammatiche elettorali basati sulla circoscrizione (= grammatiche della struttura della frase ) distinguono tra nodi terminali e non terminali. I nodi interni sono etichettati da categorie non terminali della grammatica, mentre i nodi foglia sono etichettati da categorie terminali . L'immagine sotto rappresenta un albero di analisi basato sul collegio elettorale; mostra la struttura sintattica della frase inglese John hit the ball :

L'albero di analisi è l'intera struttura, a partire da S e termina in ciascuno dei nodi foglia ( John , hit , the , ball ). Nell'albero vengono utilizzate le seguenti abbreviazioni:

• S per frase , la struttura di primo livello in questo esempio

• NP per sintagma nominale . Il primo (più a sinistra) NP, un singolo sostantivo "John", funge da soggetto della frase. Il secondo è l' oggetto della frase.

• VP per frase verbale , che funge da predicato

• V per verbo . In questo caso, è un verbo transitivo hit .

• D per determinante , in questo caso l' articolo determinativo "il"

• N per sostantivo

Ogni nodo nell'albero è un nodo radice , un nodo ramo o un nodo foglia . Un nodo radice è un nodo che non ha rami sopra di esso. All'interno di una frase, c'è sempre un solo nodo radice. Un nodo di diramazione è un nodo padre che si connette a due o più nodi figlio. Un nodo foglia, tuttavia, è un nodo terminale che non domina altri nodi nell'albero. S è il nodo radice, NP e VP sono nodi ramificati e John (N), hit (V), the (D) e ball (N) sono tutti nodi foglia. Le foglie sono i segni lessicali della frase. Un nodo padre è uno che ha almeno un altro nodo collegato da un ramo sotto di esso. Nell'esempio, S è un genitore sia di N che di VP. Un nodo figlio è uno che ha almeno un nodo direttamente sopra di esso al quale è collegato da un ramo di un albero. Dall'esempio, hit è un nodo figlio di V. A volte vengono utilizzati anche i termini madre e figlia per questa relazione.

Alberi di analisi basati sulla dipendenza

Gli alberi di analisi basati sulle dipendenze delle grammatiche delle dipendenze vedono tutti i nodi come terminali, il che significa che non riconoscono la distinzione tra categorie terminali e non terminali. Sono in media più semplici degli alberi di analisi basati sulla circoscrizione perché contengono meno nodi. L'albero di analisi basato sulle dipendenze per la frase di esempio sopra è il seguente:

Questo albero di analisi non ha le categorie frasali (S, VP e NP) viste nella controparte basata sul collegio elettorale sopra. Come l'albero basato sul collegio elettorale , la struttura costitutiva è riconosciuta. Qualsiasi sottoalbero completo dell'albero è un costituente. Quindi questo albero di analisi basato sulla dipendenza riconosce il sostantivo soggetto John e la frase del sostantivo oggetto la palla come costituenti proprio come fa l'albero di analisi basato sul collegio elettorale.

La distinzione tra circoscrizione e dipendenza è di vasta portata. Se la struttura sintattica aggiuntiva associata agli alberi di analisi basati sul collegio elettorale sia necessaria o utile è una questione di dibattito.

Marcatori di frasi

I marcatori di frase, o marcatori P, furono introdotti nella prima grammatica generativa trasformazionale , sviluppata da Noam Chomsky e altri. Un marcatore di frase che rappresenta la struttura profonda di una frase viene generato applicando regole di struttura della frase . Quindi, questa applicazione può subire ulteriori trasformazioni.

I marcatori di frase possono essere presentati sotto forma di alberi (come nella sezione precedente sugli alberi di analisi basati sul collegio elettorale ), ma sono spesso dati invece sotto forma di "espressioni tra parentesi", che occupano meno spazio nella memoria. Ad esempio, un'espressione tra parentesi corrispondente all'albero basato sul collegio elettorale sopra riportato può essere qualcosa del tipo:

${\displaystyle [_{S}\ [_{\mathit {N}}\ John]\ [_{\mathit {VP}}\ [_{V}\ hit]\ [_{\mathit {NP}} \ [_{\mathit {D}}\ il]\ [_{N}\ palla]]]]}$

Come per gli alberi, la costruzione precisa di tali espressioni e la quantità di dettagli mostrati possono dipendere dalla teoria applicata e dai punti che l'autore della query desidera illustrare.

Guarda anche

Appunti

Riferimenti

link esterno

• Editor dell'albero della sintassi
• Costruttore di alberi linguistici
• phpSyntaxTree – Sito di disegno di alberi di analisi online
• phpSyntaxTree (Unicode) – Sito di disegno dell'albero di analisi online (versione migliorata che supporta Unicode)
• rSyntaxTree Versione migliorata di phpSyntaxTree in Ruby con grafica Unicode e vettorizzata
• Qtree – Pacchetto LaTeX per disegnare alberi di analisi
• Sintassi TreeForm Software di disegno dell'albero
• Introduzione visiva a Parse Trees Introduzione e trasformazione
• Introduzione all'analisi delle dipendenze di OpenCourseOnline (Christoper Manning)
• Tag costituenti Penn Treebank II