Progettazione del compilatore - Tabella dei simboli

La tabella dei simboli è un'importante struttura di dati creata e mantenuta dai compilatori al fine di memorizzare informazioni sull'occorrenza di varie entità come nomi di variabili, nomi di funzioni, oggetti, classi, interfacce, ecc. parti di un compilatore.

Una tabella dei simboli può servire ai seguenti scopi a seconda della lingua in mano:

  • Per memorizzare i nomi di tutte le entità in una forma strutturata in un unico posto.

  • Per verificare se è stata dichiarata una variabile.

  • Per implementare il controllo del tipo, verificando che le assegnazioni e le espressioni nel codice sorgente siano semanticamente corrette.

  • Per determinare l'ambito di un nome (risoluzione dell'ambito).

Una tabella dei simboli è semplicemente una tabella che può essere lineare o hash. Mantiene una voce per ogni nome nel seguente formato:

<symbol name,  type,  attribute>

Ad esempio, se una tabella di simboli deve memorizzare informazioni sulla seguente dichiarazione di variabile:

static int interest;

quindi dovrebbe memorizzare la voce come:

<interest, int, static>

La clausola di attributo contiene le voci relative al nome.

Implementazione

Se un compilatore deve gestire una piccola quantità di dati, la tabella dei simboli può essere implementata come un elenco non ordinato, che è facile da codificare, ma è adatto solo per piccole tabelle. Una tabella dei simboli può essere implementata in uno dei seguenti modi:

  • Elenco lineare (ordinato o non ordinato)
  • Albero di ricerca binario
  • Tabella hash

Tra tutte, le tabelle dei simboli sono per lo più implementate come tabelle hash, dove il simbolo del codice sorgente stesso viene trattato come una chiave per la funzione hash e il valore restituito è l'informazione sul simbolo.

Operazioni

Una tabella dei simboli, lineare o hash, dovrebbe fornire le seguenti operazioni.

inserire()

Questa operazione è più frequentemente utilizzata dalla fase di analisi, cioè la prima metà del compilatore dove vengono identificati i token e vengono memorizzati i nomi nella tabella. Questa operazione viene utilizzata per aggiungere informazioni nella tabella dei simboli sui nomi univoci che si verificano nel codice sorgente. Il formato o la struttura in cui vengono memorizzati i nomi dipende dal compilatore in mano.

Un attributo per un simbolo nel codice sorgente è l'informazione associata a quel simbolo. Queste informazioni contengono il valore, lo stato, l'ambito e il tipo del simbolo. La funzione insert () accetta il simbolo ei suoi attributi come argomenti e memorizza le informazioni nella tabella dei simboli.

Per esempio:

int a;

dovrebbe essere elaborato dal compilatore come:

insert(a, int);

consultare()

L'operazione lookup () viene utilizzata per cercare un nome nella tabella dei simboli per determinare:

  • se il simbolo esiste nella tabella.
  • se è dichiarato prima di essere utilizzato.
  • se il nome è utilizzato nell'ambito.
  • se il simbolo è inizializzato.
  • se il simbolo è stato dichiarato più volte.

Il formato della funzione lookup () varia a seconda del linguaggio di programmazione. Il formato di base dovrebbe corrispondere al seguente:

lookup(symbol)

Questo metodo restituisce 0 (zero) se il simbolo non esiste nella tabella dei simboli. Se il simbolo esiste nella tabella dei simboli, restituisce i suoi attributi memorizzati nella tabella.

Gestione dell'ambito

Un compilatore mantiene due tipi di tabelle di simboli: a global symbol table accessibile da tutte le procedure e scope symbol tables che vengono creati per ogni ambito nel programma.

Per determinare l'ambito di un nome, le tabelle dei simboli sono disposte in una struttura gerarchica come mostrato nell'esempio seguente:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

Il programma di cui sopra può essere rappresentato in una struttura gerarchica di tabelle di simboli:

La tabella dei simboli globale contiene i nomi per una variabile globale (valore int) e due nomi di procedure, che dovrebbero essere disponibili per tutti i nodi figli mostrati sopra. I nomi menzionati nella tabella dei simboli pro_one (e tutte le sue tabelle figlie) non sono disponibili per i simboli pro_two e le relative tabelle figlie.

Questa gerarchia della struttura dei dati della tabella dei simboli è memorizzata nell'analizzatore semantico e ogni volta che un nome deve essere cercato in una tabella dei simboli, viene cercato utilizzando il seguente algoritmo:

  • prima verrà cercato un simbolo nell'ambito corrente, cioè la tabella dei simboli corrente.

  • se viene trovato un nome, la ricerca è completata, altrimenti verrà cercata nella tabella dei simboli padre fino a quando,

  • è stato trovato il nome o è stata cercata la tabella dei simboli globale per il nome.