Grammatica ad attributi

Da Wikipedia, l'enciclopedia libera.

In teoria dei linguaggi formali, una grammatica ad attributi è una grammatica formale che associa un significato alle regole di produzione. È un'estensione del formalismo delle grammatiche libere dal contesto, ed ha applicazioni in informatica, in particolare è usata nella traduzione di un programma guidata dalla sintassi.

Descrizione[modifica | modifica sorgente]

Ogni simbolo può avere uno o più attributi, ciascuno dei quali "contiene" un valore, analogamente alle variabili di un linguaggio di programmazione imperativo. Ad ogni regola di produzione è possibile associare una o più operazioni, dette azioni semantiche; le azioni semantiche possono anche leggere e modificare i valori degli attributi. La sequenza delle azioni semantiche associata ad una regola di produzione è detta regola semantica.

Il valore di un attributo rappresenta il significato che si intende associare a un certo simbolo. Il valore è calcolato dalle azioni semantiche esattamente come un programma calcola il risultato di una computazione. I valori calcolati possono essere usati per qualunque tipo di elaborazione.
Per esempio, si consideri una grammatica che definisce le espressioni booleane con i terminali vero e falso e gli operatori AND, NAND. Si può associare un attributo ad ogni simbolo, e calcolare con le azioni semantiche i valori degli attributi dei simboli non terminali, svolgendo le operazioni logiche analoghe a quelle individuate dalle produzioni:

E -> and { E.attr = and.attr; }
E -> nand { E.attr = nand.attr; }
E -> term { E.attr = term.attr; }
and -> E1 AND E2 { and.attr = E1.attr && E2.attr; }
nand -> E1 NAND E2 { nand.attr = ! (E1.attr && E2.attr); }
term -> vero { term.attr = true; }
term -> falso { term.attr = false; }

Il valore dell'intera espressione è nell'attributo associato all'intera espressione booleana.

Le grammatiche ad attributi possono essere usate anche per tradurre l'albero sintattico direttamente in codice macchina.

Un punto di forza delle grammatiche ad attributi è che possono trasportare informazioni da qualsiasi parte nell'albero astratto della sintassi da qualsiasi altra parte, in una maniera controllata e formale.

Attributi sintetizzati ed ereditati[modifica | modifica sorgente]

Gli attributi sono divisi in due gruppi: attributi sintetizzati ed ereditati. Gli attributi sintetizzati sono i risultati delle regole di valutazione degli attributi, e possono inoltre utilizzare i valori degli attributi ereditati. Gli attributi ereditati sono passati secondo un cammino discendente a partire dai nodi genitori.

In alcuni approcci, gli attributi sintetizzati sono usati per passare informazioni semantiche su per l'albero di parsing, mentre gli attributi ereditati servono a passare l'informazione semantica giù e oltre. Per esempio, quando si costruisce un tool per la traduzione dei linguaggi, come ad esempio un compilatore, può essere usata per assegnare valori semantici ai costrutti sintattici. Inoltre, è possibile convalidare controlli semantici associati con una grammatica, rappresentando le regole di un linguaggio non esplicitamente impartite dalla sintassi.

Bibliografia[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica