Grammatica ad attributi
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 wikitesto]
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 wikitesto]
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 wikitesto]
- Riccardo Rosati, http://www.dis.uniroma1.it/~fiii/materiale_ausiello/slideLezione311008.pdf[collegamento interrotto], Università di Roma "La Sapienza"
| Controllo di autorità | GND (DE) 4003464-1 |
|---|
