Projekt kompilatora - tabela symboli

Tablica symboli to ważna struktura danych tworzona i utrzymywana przez kompilatory w celu przechowywania informacji o występowaniu różnych bytów, takich jak nazwy zmiennych, nazwy funkcji, obiekty, klasy, interfejsy itp. Tablica symboli jest używana zarówno przez analizę, jak i syntezę części kompilatora.

Tabela symboli może służyć następującym celom w zależności od używanego języka:

Aby przechowywać nazwy wszystkich podmiotów w uporządkowanej formie w jednym miejscu.
Aby sprawdzić, czy została zadeklarowana zmienna.
Aby zaimplementować sprawdzanie typów, weryfikując przypisania i wyrażenia w kodzie źródłowym są semantycznie poprawne.
Określenie zakresu nazwy (rozdzielczość zakresu).

Tablica symboli to po prostu tablica, która może być liniowa lub tablica mieszająca. Przechowuje wpis dla każdej nazwy w następującym formacie:

<symbol name,  type,  attribute>

Na przykład, jeśli tablica symboli ma przechowywać informacje o następującej deklaracji zmiennej:

static int interest;

to powinien przechowywać wpis taki jak:

<interest, int, static>

Klauzula atrybutu zawiera wpisy związane z nazwą.

Realizacja

Jeśli kompilator ma obsłużyć niewielką ilość danych, to tablicę symboli można zaimplementować jako nieuporządkowaną listę, która jest łatwa do zakodowania, ale nadaje się tylko do małych tabel. Tablicę symboli można zaimplementować na jeden z następujących sposobów:

Lista liniowa (posortowana lub nieposortowana)
Drzewo wyszukiwania binarnego
Hash table

Spośród wszystkich, tablice symboli są najczęściej implementowane jako tablice skrótów, w których sam symbol kodu źródłowego jest traktowany jako klucz dla funkcji skrótu, a wartość zwracana jest informacją o symbolu.

Operacje

Tabela symboli, liniowa lub hash, powinna zapewniać następujące operacje.

wstawić()

Ta operacja jest częściej wykorzystywana przez fazę analizy, tj. Pierwszą połowę kompilatora, w której identyfikowane są tokeny, a nazwy są przechowywane w tabeli. Ta operacja służy do dodawania informacji w tablicy symboli o unikalnych nazwach występujących w kodzie źródłowym. Format lub struktura, w której przechowywane są nazwy, zależy od używanego kompilatora.

Atrybutem symbolu w kodzie źródłowym są informacje związane z tym symbolem. Te informacje zawierają wartość, stan, zakres i typ symbolu. Funkcja insert () przyjmuje symbol i jego atrybuty jako argumenty i przechowuje informacje w tablicy symboli.

Na przykład:

int a;

powinien zostać przetworzony przez kompilator jako:

insert(a, int);

lookup ()

Operacja lookup () służy do wyszukiwania nazwy w tablicy symboli w celu określenia:

jeśli symbol istnieje w tabeli.
jeśli jest zadeklarowany przed użyciem.
jeśli nazwa jest używana w zakresie.
jeśli symbol został zainicjowany.
jeśli symbol został zadeklarowany wiele razy.

Format funkcji lookup () różni się w zależności od języka programowania. Podstawowy format powinien pasować do następujących:

lookup(symbol)

Ta metoda zwraca 0 (zero), jeśli symbol nie istnieje w tablicy symboli. Jeśli symbol istnieje w tablicy symboli, zwraca atrybuty przechowywane w tablicy.

Zarządzanie zakresem

Kompilator obsługuje dwa typy tablic symboli: a global symbol table do których można uzyskać dostęp za pomocą wszystkich procedur i scope symbol tables które są tworzone dla każdego zakresu w programie.

Aby określić zakres nazwy, tabele symboli są ułożone w strukturę hierarchiczną, jak pokazano na poniższym przykładzie:

. . . 
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;
   }
. . .

Powyższy program można przedstawić w hierarchicznej strukturze tablic symboli:

Globalna tablica symboli zawiera nazwy jednej zmiennej globalnej (wartość int) i dwie nazwy procedur, które powinny być dostępne dla wszystkich węzłów potomnych pokazanych powyżej. Nazwy wymienione w tabeli symboli pro_one (i wszystkich jej tabelach podrzędnych) nie są dostępne dla symboli pro_two i jego tabel podrzędnych.

Ta hierarchia struktury danych tablicy symboli jest przechowywana w analizatorze semantycznym i za każdym razem, gdy konieczne jest wyszukanie nazwy w tablicy symboli, jest ona przeszukiwana przy użyciu następującego algorytmu:

najpierw będzie wyszukiwany symbol w bieżącym zakresie, tj. bieżącej tablicy symboli.
jeśli nazwa zostanie znaleziona, wyszukiwanie jest zakończone, w przeciwnym razie będzie przeszukiwane w tabeli symboli nadrzędnych do,
albo nazwa została znaleziona, albo została przeszukana globalna tablica symboli.