Progettazione del compilatore - Analisi semantica

Abbiamo imparato come un parser costruisce alberi di analisi nella fase di analisi della sintassi. Il semplice parse-tree costruito in quella fase è generalmente inutile per un compilatore, poiché non contiene alcuna informazione su come valutare l'albero. Le produzioni della grammatica contestuale, che fa le regole della lingua, non si adattano al modo in cui interpretarle.

Per esempio

E → E + T

La produzione di CFG di cui sopra non ha alcuna regola semantica associata e non può aiutare a dare un senso alla produzione.

Semantica

La semantica di un linguaggio fornisce significato ai suoi costrutti, come i token e la struttura della sintassi. La semantica aiuta a interpretare i simboli, i loro tipi e le loro relazioni tra loro. L'analisi semantica giudica se la struttura della sintassi costruita nel programma sorgente deriva o meno un significato.

CFG + semantic rules = Syntax Directed Definitions

Per esempio:

int a = “value”;

non dovrebbe generare un errore in fase di analisi lessicale e sintattica, in quanto è lessicalmente e strutturalmente corretto, ma dovrebbe generare un errore semantico poiché il tipo di assegnazione è diverso. Queste regole sono stabilite dalla grammatica della lingua e valutate in analisi semantica. Le seguenti attività dovrebbero essere eseguite nell'analisi semantica:

• Risoluzione dell'ambito
• Controllo del tipo
• Controllo associato ad array

Errori semantici

Abbiamo menzionato alcuni degli errori semantici che l'analizzatore semantico dovrebbe riconoscere:

• Tipo mancata corrispondenza
• Variabile non dichiarata
• Uso improprio dell'identificatore riservato.
• Dichiarazione multipla di variabile in un ambito.
• Accesso a una variabile fuori ambito.
• Mancata corrispondenza dei parametri effettivi e formali.

Attributo grammaticale

La grammatica degli attributi è una forma speciale di grammatica libera dal contesto in cui alcune informazioni aggiuntive (attributi) vengono aggiunte a uno o più dei suoi non terminali per fornire informazioni sensibili al contesto. Ogni attributo ha un dominio di valori ben definito, come intero, float, carattere, stringa ed espressioni.

La grammatica degli attributi è un mezzo per fornire semantica alla grammatica libera dal contesto e può aiutare a specificare la sintassi e la semantica di un linguaggio di programmazione. La grammatica degli attributi (se vista come un albero sintetico) può trasmettere valori o informazioni tra i nodi di un albero.

Example:

E → E + T { E.value = E.value + T.value }

La parte destra del CFG contiene le regole semantiche che specificano come deve essere interpretata la grammatica. Qui, i valori dei non terminali E e T vengono sommati e il risultato viene copiato nel non terminale E.

Gli attributi semantici possono essere assegnati ai loro valori dal loro dominio al momento dell'analisi e valutati al momento dell'assegnazione o delle condizioni. In base al modo in cui gli attributi ottengono i propri valori, possono essere ampiamente suddivisi in due categorie: attributi sintetizzati e attributi ereditati.

Attributi sintetizzati

Questi attributi ottengono valori dai valori degli attributi dei loro nodi figli. Per illustrare, ipotizza la seguente produzione:

S → ABC

Se S sta prendendo valori dai suoi nodi figli (A, B, C), allora si dice che sia un attributo sintetizzato, poiché i valori di ABC sono sintetizzati in S.

Come nel nostro esempio precedente (E → E + T), il nodo padre E ottiene il suo valore dal suo nodo figlio. Gli attributi sintetizzati non prendono mai valori dai nodi principali o da qualsiasi nodo di pari livello.

Attributi ereditati

A differenza degli attributi sintetizzati, gli attributi ereditati possono assumere valori da genitori e / o fratelli. Come nella seguente produzione,

S → ABC

A può ottenere valori da S, B e C. B può assumere valori da S, A e C. Allo stesso modo, C può assumere valori da S, A e B.

Expansion : Quando un non terminale viene espanso ai terminali secondo una regola grammaticale

Reduction: Quando un terminale viene ridotto al suo non terminale corrispondente in base alle regole grammaticali. Gli alberi della sintassi vengono analizzati dall'alto verso il basso e da sinistra a destra. Ogni volta che si verifica una riduzione, applichiamo le sue corrispondenti regole semantiche (azioni).

L'analisi semantica utilizza le traduzioni orientate alla sintassi per eseguire le attività di cui sopra.

L'analizzatore semantico riceve AST (Abstract Syntax Tree) dalla sua fase precedente (analisi della sintassi).

L'analizzatore semantico allega le informazioni sugli attributi con AST, che sono chiamate AST attribuito.

Gli attributi sono due valori di tupla, <nome attributo, valore attributo>

Per esempio:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Per ogni produzione, alleghiamo una regola semantica.

SDT attribuito a S.

Se un SDT utilizza solo attributi sintetizzati, viene chiamato SDT attribuito a S. Questi attributi vengono valutati utilizzando SDT attribuiti a S che hanno le loro azioni semantiche scritte dopo la produzione (lato destro).

Come illustrato sopra, gli attributi negli SDT attribuiti a S vengono valutati nell'analisi bottom-up, poiché i valori dei nodi padre dipendono dai valori dei nodi figli.

SDT attribuito a L.

Questa forma di SDT utilizza attributi sia sintetizzati che ereditati con la restrizione di non prendere valori dai fratelli di destra.

Negli SDT attribuiti a L, un non terminale può ottenere valori dai suoi nodi padre, figlio e fratello. Come nella produzione successiva

S → ABC

S può assumere valori da A, B e C (sintetizzati). A può assumere valori solo da S. B può assumere valori da S e A. C può ottenere valori da S, A e B. Nessun non terminale può ottenere valori dal fratello alla sua destra.

Gli attributi negli SDT attribuiti a L vengono valutati in base al modo di analisi approfondito e da sinistra a destra.

Possiamo concludere che se una definizione è attribuita a S, allora è anche attribuita a L poiché la definizione con attribuzione a L include definizioni attribuite a S.