Indietro

ⓘ Grammatica ad attributi




                                     

ⓘ Grammatica ad attributi

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

                                     

1. Descrizione

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 dellintera espressione è nellattributo associato allintera espressione booleana.

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

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

                                     

2. Attributi sintetizzati ed ereditati

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 lalbero di parsing, mentre gli attributi ereditati servono a passare linformazione 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.