Desain Penyusun - Tabel Simbol

Tabel simbol adalah struktur data penting yang dibuat dan dipelihara oleh penyusun untuk menyimpan informasi tentang terjadinya berbagai entitas seperti nama variabel, nama fungsi, objek, kelas, antarmuka, dll. Tabel simbol digunakan baik oleh analisis maupun sintesis. bagian dari sebuah kompilator.

Tabel simbol dapat melayani tujuan berikut tergantung pada bahasa yang digunakan:

• Untuk menyimpan nama semua entitas dalam formulir terstruktur di satu tempat.

• Untuk memverifikasi apakah variabel telah dideklarasikan.

• Untuk menerapkan pemeriksaan tipe, dengan memverifikasi tugas dan ekspresi dalam kode sumber sudah benar secara semantik.

• Untuk menentukan ruang lingkup nama (resolusi lingkup).

Tabel simbol hanyalah tabel yang dapat berupa tabel linier atau tabel hash. Itu memelihara entri untuk setiap nama dalam format berikut:

<symbol name,  type,  attribute>

Misalnya, jika tabel simbol harus menyimpan informasi tentang deklarasi variabel berikut:

static int interest;

maka itu harus menyimpan entri seperti:

<interest, int, static>

Klausa atribut berisi entri yang terkait dengan nama.

Penerapan

Jika kompiler akan menangani sejumlah kecil data, maka tabel simbol dapat diimplementasikan sebagai daftar tidak berurutan, yang mudah untuk dikodekan, tetapi hanya cocok untuk tabel kecil saja. Tabel simbol dapat diimplementasikan dengan salah satu cara berikut:

• Daftar linier (diurutkan atau tidak diurutkan)
• Pohon Pencarian Biner
• Tabel hash

Di antara semuanya, tabel simbol sebagian besar diimplementasikan sebagai tabel hash, di mana simbol kode sumber itu sendiri diperlakukan sebagai kunci untuk fungsi hash dan nilai yang dikembalikan adalah informasi tentang simbol tersebut.

Operasi

Tabel simbol, baik linier atau hash, harus menyediakan operasi berikut.

memasukkan()

Operasi ini lebih sering digunakan oleh fase analisis, yaitu paruh pertama compiler di mana token diidentifikasi dan nama disimpan dalam tabel. Operasi ini digunakan untuk menambahkan informasi dalam tabel simbol tentang nama unik yang muncul di kode sumber. Format atau struktur di mana nama-nama tersebut disimpan bergantung pada kompiler yang ada.

Atribut untuk simbol dalam kode sumber adalah informasi yang terkait dengan simbol itu. Informasi ini berisi nilai, status, cakupan, dan tipe tentang simbol. Fungsi insert () mengambil simbol dan atributnya sebagai argumen dan menyimpan informasi dalam tabel simbol.

Sebagai contoh:

int a;

harus diproses oleh kompilator sebagai:

insert(a, int);

Lihatlah()

operasi lookup () digunakan untuk mencari nama dalam tabel simbol untuk menentukan:

• jika simbol itu ada di tabel.
• jika dideklarasikan sebelum digunakan.
• jika nama digunakan dalam ruang lingkup.
• jika simbol diinisialisasi.
• jika simbol dideklarasikan beberapa kali.

Format fungsi lookup () bervariasi sesuai dengan bahasa pemrograman. Format dasar harus sesuai dengan yang berikut:

lookup(symbol)

Metode ini mengembalikan 0 (nol) jika simbol tidak ada di tabel simbol. Jika simbol ada di tabel simbol, ia mengembalikan atributnya yang disimpan di tabel.

Manajemen Lingkup

Kompiler memelihara dua jenis tabel simbol: a global symbol table yang dapat diakses oleh semua prosedur dan scope symbol tables yang dibuat untuk setiap cakupan dalam program.

Untuk menentukan ruang lingkup suatu nama, tabel simbol disusun dalam struktur hierarki seperti yang ditunjukkan pada contoh di bawah ini:

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

Program di atas dapat direpresentasikan dalam struktur hierarki tabel simbol:

Tabel simbol global berisi nama untuk satu variabel global (nilai int) dan dua nama prosedur, yang harus tersedia untuk semua node turunan yang ditunjukkan di atas. Nama-nama yang disebutkan dalam tabel simbol pro_one (dan semua tabel anaknya) tidak tersedia untuk simbol pro_two dan tabel anaknya.

Hierarki struktur data tabel simbol ini disimpan di penganalisis semantik dan setiap kali nama perlu dicari di tabel simbol, ia dicari menggunakan algoritma berikut:

• pertama sebuah simbol akan dicari dalam lingkup saat ini, yaitu tabel simbol saat ini.

• jika nama ditemukan, maka pencarian selesai, jika tidak akan dicari di tabel simbol induk sampai,

• baik nama ditemukan atau tabel simbol global telah dicari untuk namanya.