Albero della sintassi

Una sintassi , derivazione o albero di analisi è un termine dell'informatica teorica e della linguistica . Descrive una rappresentazione gerarchica della scomposizione di un testo. Gli alberi di sintassi vengono utilizzati sia come ausilio per la visualizzazione grafica del guasto e, sotto forma di una struttura dati , per visualizzare questo guasto per l'elaborazione della macchina, ad es. B. in un compilatore o traduttore .

I vari termini non sono usati in modo uniforme in letteratura. Solo l' albero di derivazione del termine , che si basa sul termine derivazione, è formalmente definito con precisione . Altri nomi per diversi tipi di alberi possono quindi essere definiti tecnicamente in modo più dettagliato, come descritto di seguito, se necessario.

A differenza dell'informatica, in cui le lingue possono essere definite anche in base alle possibilità tecniche, la linguistica trova prerequisiti più difficili quando si tratta di lingue naturali , principalmente perché l'ordine dei componenti di una frase può variare.

introduzione

Rappresentazione di un albero di derivazione

Nell'analisi (meccanica) di frasi in linguaggio naturale o testi formali (ad esempio programmi per computer), l' analisi lessicale (la scomposizione in token o simboli ) è spesso seguita da un riepilogo gerarchico dei simboli in parti correlate di frasi ( componenti ) o sezioni del Testo formale invece. Al contrario, questo può anche essere inteso come una dissezione del testo. Il risultato è un albero come quello mostrato a destra. Oltre alla forma grafica, vengono utilizzate anche rappresentazioni tra parentesi per gli alberi di sintassi:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Tecnicamente, l'albero a sinistra è anche chiamato albero di derivazione concreta , poiché mostra la struttura risultante esattamente utilizzando il testo concreto. In linguistica, tuttavia, sono comuni anche modelli che forniscono diversi livelli di rappresentazione (ad es . Struttura di superficie e profondità ).

Spesso i nodi dell'albero sono arricchiti di attributi (in linguistica si tratta principalmente di categorie morfologiche ). Questo ti dà un albero della sintassi attribuito con la grammatica attribuita associata . Mentre una grammatica libera dal contesto viene utilizzata nelle prime due rappresentazioni ad albero , la dipendenza dal contesto entra in gioco in queste ultime . Queste differenze si riflettono nella gerarchia di Chomsky . In questi casi, il termine analisi semantica viene utilizzato nella costruzione del compilatore .

Alberi di derivazione

Considera una grammatica priva di contesto . Un albero di derivazione per questo è un albero i cui nodi sono etichettati con simboli da (cioè simboli terminali e non terminali e la parola vuota ). L'albero è ordinato , i. H. i figli di ogni nodo hanno un ordine fisso e per l'etichettatura si applica quanto segue: ${\ Displaystyle G = \ sinistra (N, \ Sigma, P, S \ destra)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• La radice è etichettata con il simbolo di inizio . Questa proprietà a volte non è richiesta. Un albero che li soddisfa è chiamato albero di derivazione completo .${\ displaystyle S}$
• Se i figli di un nodo interno etichettato con sono etichettati con i simboli (in quell'ordine), la grammatica deve contenere la regola .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ to z_ {1} \ ldots z_ {m}}$
• Le foglie dell'albero sono etichettate con simboli .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Se una foglia è contrassegnata con , è l'unico successore del suo nodo predecessore.${\ displaystyle \ varepsilon}$

Solo i simboli non terminali possono essere usati come nodi interni e solo i simboli terminali o la parola vuota per le foglie.

Costruzione di alberi di derivazione

Possibili alberi / diagrammi di sintassi possono spesso essere facilmente creati per testi brevi seguendo le regole di produzione. Sono disponibili molti metodi meccanici per testi più lunghi .

Ad esempio, il diagramma della sintassi mostrato nell'introduzione include, tra le altre cose. si basano sulle seguenti regole:

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & NP \ VP \\ NP & \ rightarrow & {\ mathtt {John}} \\ NP & \ rightarrow & Det \ N \\ VP & \ rightarrow & V \ NP \\\ end {array}} \ quad \ quad {\ begin {array} {lll} V & \ rightarrow & {\ mathtt {hit}} \\ Det & \ rightarrow & {\ mathtt {the} } \\ N & \ rightarrow & {\ mathtt {ball}} \ end {array}}}$

Per generare un albero di derivazione, le regole possono essere applicate passo dopo passo dalla radice sostituendo sistematicamente un non terminale sul lato sinistro della regola con i simboli sul lato destro fino a quando rimangono solo i terminali:

${\ displaystyle S \ \ Rightarrow \ NP \ VP \ \ Rightarrow \ {\ mathtt {John}} \ VP \ \ Rightarrow \ {\ mathtt {John}} \ V \ NP \ \ Rightarrow \ {\ mathtt {John \ hit }} \ NP \ \ Rightarrow \ {\ mathtt {John \ hit}} \ Det \ N \ Rightarrow \ {\ mathtt {John \ hit \ the}} \ N \ Rightarrow \ {\ mathtt {John \ hit \ the \ palla}}}$

Con ciascuno dei passaggi si disegna una parte dell'albero della sintassi dall'alto verso il basso. Ma puoi anche applicare le regole al contrario e iniziare con la frase scritta e poi costruire l'albero passo dopo passo dal basso verso l'alto.

Alberi di derivazione per grammatiche univoche e ambigue

Se c'è più di un albero di derivazione per una parola nel linguaggio di una grammatica, si parla di una grammatica ambigua , altrimenti di una non ambigua. Ad esempio, la seguente grammatica è ambigua

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & S \ S \\ S & \ rightarrow & a \ end {array}}}$

perché "aa a" può essere suddiviso in due modi diversi: "[aa] a" e "a [aa]". Tuttavia, solo una possibile classificazione consente la seguente grammatica

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & a \ S \\ S & \ rightarrow & a \ end {array}}}$

Nel caso di grammatiche ambigue, il numero di possibili alberi di derivazione per una stessa parola può aumentare notevolmente con la lunghezza della parola. In questo caso, gli alberi di derivazione non sono più una rappresentazione adeguata per la totalità delle possibili derivazioni. Nel caso dei linguaggi formali, la grammatica concreta (superficiale) è solitamente formulata in modo univoco. Le grammatiche astratte, d'altra parte, sono spesso ambigue, per cui l'unicità dell'albero di derivazione astratta risulta poi dal concreto nel corso dell'analisi.

Alberi di sintassi astratti

Per la rappresentazione degli alberi di sintassi come una struttura di dati in un computer, la designazione albero di sintassi astratto (AST) viene ora utilizzata in modo abbastanza uniforme. B. anche di alberi di derivazione astratti , alberi operatore o simili. si può parlare. Una connessione esatta tra albero di sintassi astratto e albero di derivazione concreta è mostrato in letteratura, ad es. T. indicato. Tuttavia, oltre a un ingrossamento dell'albero di derivazione, nella struttura sono inclusi anche i requisiti per un'ulteriore elaborazione, in modo che una derivazione formale diretta dalla grammatica di superficie sia di solito insoddisfacente come risultato.

La grammatica di superficie libera dal contesto è quindi opposta a una grammatica astratta , che in senso stretto è principalmente un tipo di dati algebrico . Gli alberi della sintassi sono quindi tecnicamente rappresentati come termini versatili . L'analisi è nella transizione tra termini grammaticali e algebrico-logici, in modo che qui si possa parlare fluentemente di non-terminali e tipi o di alberi e termini.

esempio

Albero di sintassi concreto (a sinistra) e astratto (a destra) per l'espressione ${\ displaystyle a \ times (b + 3)}$

L'illustrazione a lato mostra alberi di sintassi concreti e astratti per le seguenti grammatiche.

E :: E "+" T - espressione
  :: T
T :: T "*" F termine
  :: F
F :: fattore V
  :: N
  :: "(" E ")"
V - variabile
N - numero

E :: E "+" E
  :: E "*" E
  :: V
  :: N

tipo E = aggiungi (E, E);
        mul (E, E);
        var (V);
        num (N)

La grammatica concreta in questo esempio deve regolare l' ordine in cui gli operatori vengono applicati alle espressioni (parziali), ovvero il punto prima del trattino e le espressioni parziali della stessa priorità devono essere raggruppate da sinistra a destra. Viene offerta anche la possibilità di creare un riepilogo diverso con le espressioni tra parentesi. Insieme a certi terminali (qui "(", ")", "+", "*") queste sono semplicemente proprietà della superficie sintattica che non giocano più un ruolo nell'analisi successiva e nell'ulteriore elaborazione. In particolare, la distinzione tra diversi tipi di espressioni (qui E, T e F) e le parole chiave può essere completamente eliminata, come si può vedere dall'albero della sintassi astratto, che è anche molto più vicino al "contenuto" del espressione. Inoltre, a causa di questi dettagli superficiali, gli alberi di derivazione del calcestruzzo non solo diventano rapidamente confusi, ma occupano anche più spazio di archiviazione del necessario come struttura dati nel computer a causa dei loro dettagli. Ciò si riflette anche nel runtime e nella complessità dei programmi che successivamente elaboreranno l'albero di derivazione. Per ragioni tecniche, la scomposizione di un testo di origine non è quindi solitamente rappresentata da uno specifico albero di derivazione.

Rappresentazione di alberi di sintassi astratti

Oltre alla rappresentazione grafica come albero (operatore) mostrato nell'esempio, gli alberi di sintassi astratti sono anche tecnicamente annotati come termini , ad es. B.: mul(var('a'), add(var('b'), num(3))).

Grammatica astratta

Mentre gli alberi di sintassi astratti sono strutture di dati e tipi algebrici assumono il ruolo di grammatica in essi, in letteratura, specialmente in relazione ai calcoli, spesso viene fornita solo una grammatica grossolana e ambigua, che, come mostrato nell'esempio sopra, ha il stessa struttura dei termini ma contengono ancora parole chiave. Questa forma consente una piacevole scrittura di alberi di sintassi astratti, che spesso è molto vicina alla sorgente effettiva. Di solito si sottolinea nell'introduzione che le parentesi possono essere utilizzate per disambiguare. Un albero di sintassi astratto per l'esempio precedente verrebbe quindi effettivamente a * (b + 3)scritto come. Nel contesto di questa letteratura, tuttavia, l'attenzione è sempre sul termine: come accennato, i confini tra grammatica e algebra vengono sfumati giocando con la forma.

Un tipico esempio sono le espressioni nel lambda calcolo , la cui grammatica astratta è spesso solo scritta come. La stessa tecnica viene utilizzata anche per grammatiche estese. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

letteratura

• Ingo Wegener : informatica teorica . Un'introduzione orientata all'algoritmo. BG Teubner, Stoccarda, ISBN 3-519-02123-4 , 6.1 Esempi di linguaggi privi di contesto e alberi di sintassi, p. 147-148 . 
• Uwe Schöning : Informatica teorica - in poche parole . 5a edizione. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Alberi di sintassi, p. 15-17 . 
• Juraj Hromkovič : informatica teorica . Linguaggi formali, prevedibilità, teoria della complessità, algoritmi, comunicazione e crittografia. 3a edizione. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Grammatiche libere dal contesto e automi a pulsante, p. 378 . 
• Hans Zima: Compiler I . Analisi. Bibliographisches Institut, Mannheim / Vienna / Zurigo 1982, ISBN 3-411-01644-2 , 4.3 Alberi astratti e loro attribuzione, p. 216-229 . 
• Stefan Müller : Teoria grammaticale. Dalla grammatica trasformazionale agli approcci basati sui vincoli. 2a edizione. Language Science Press, Berlino 2018, ISBN 978-3-96110-074-3 , cap. 2 ( langsci-press.org ). 

Prove individuali

1. ↑ Müller (2018), p. 59 s.