Tabel Simbol

Struktur tabel simbol, scope bersarang, dan disiplin pencarian nama.

Daftar isi

Topik ini membahas tabel simbol (symbol table) sebagai tempat penyimpanan nama yang dideklarasikan dalam program, beserta struktur scope bersarang dan disiplin pencarian nama dari scope saat ini ke atas. Pembaca memperoleh class SymbolTable, Scope, dan Symbol untuk bahasa mini v1 yang dipakai ulang oleh resolver pada topik resolusi-scope dan pemeriksa tipe pada topik pemeriksaan-tipe. Antarmuka publiknya dipertahankan stabil sepanjang sisa modul, sehingga modul IR dapat menggunakan tabel simbol yang sama untuk melacak tipe tiap variabel.

Apa itu tabel simbol#

Tabel simbol adalah peta dari nama ke informasi yang melekat pada nama itu selama kompilasi. Setiap kali parser menemui let x = 1, sebuah entri untuk nama x dibuat pada tabel, berisi paling tidak posisi sumber dan tipe yang akan diisi belakangan oleh pemeriksa tipe. Setiap kali ekspresi print x ditemui, tabel ditanyai apakah x sudah dideklarasikan dan apa informasi yang melekat. Tanpa tabel simbol, modul semantik tidak dapat membedakan nama yang valid dari nama yang tak terdefinisi, dan modul IR tidak dapat membangun referensi yang konsisten ke variabel.

Tabel simbol disusun mengikuti struktur scope pada program. Satu blok { ... } membuka satu scope, dan tiap scope dapat menyimpan nama yang berbeda dari scope di luarnya. Karena nama yang sama boleh dipakai pada scope yang berbeda, struktur data untuk scope harus dirantai ke parent-nya, sehingga pencarian nama yang tidak ada pada scope saat ini dapat naik ke scope luar tanpa mengganggu isolasi antar scope. Struktur ini disebut scope chain dan menjadi inti mekanisme resolusi nama.

Struktur data#

Tiga class membentuk tabel simbol. Symbol menyimpan informasi yang melekat pada satu nama. Scope menyimpan kumpulan symbol pada satu lapis scope, serta rujukan ke parent. SymbolTable menjaga scope saat ini dan menyediakan operasi push, pop, define, dan resolve.

Class Symbol berupa dataclass dengan empat field wajib dan satu field opsional. Field name menyimpan lexeme identifier, kind menyimpan jenis (untuk v1 hanya "var"), declared_line dan declared_column menyimpan posisi deklarasi untuk diagnostik, dan type_hint menyimpan tipe yang akan diisi oleh pemeriksa tipe. Field type_hint diberi nilai default None sehingga deklarasi pada modul ini tetap sah sebelum pemeriksa tipe berjalan.

Class Scope sederhana: sebuah dictionary symbols: dict[str, Symbol] dan rujukan parent. Dictionary dipakai karena pemeriksaan nama pada satu scope sering dilakukan, sehingga akses rata-rata O(1) lebih sesuai daripada list. Pencarian ke parent dilakukan secara eksplisit oleh SymbolTable.resolve, bukan oleh scope sendiri, sehingga logika rantai terpusat di satu tempat.

Operasi dasar#

Empat operasi membentuk antarmuka SymbolTable. push() membuka scope baru dan menjadikannya scope saat ini. pop() menutup scope saat ini dan kembali ke parent, tetapi menolak menutup scope global. define(name, symbol) menambahkan symbol ke scope saat ini, dan menolak bila nama sudah ada pada scope yang sama, sehingga redeclarasi pada satu scope terdeteksi sejak awal. resolve(name) mencari symbol dari scope saat ini ke atas hingga scope global, dan mengembalikan None bila tidak ditemukan.

Disiplin define membedakan redeclarasi pada scope yang sama dari shadowing pada scope berbeda. Pada program let x = 1; { let x = 2; }, define pertama menempatkan x pada scope global, lalu push membuka scope baru, dan define kedua menempatkan x yang lain pada scope dalam. Kedua define berhasil karena berada pada scope yang berbeda, sehingga x di scope dalam menutup x di scope luar. Sebaliknya, let x = 1; let x = 2; pada scope yang sama ditolak oleh define sebelum resolver sempat memproses lebih jauh.

Berkas symbol_table.py#

Berkas berikut berisi class Symbol, Scope, dan SymbolTable untuk bahasa mini v1. Demo main() membangun satu scope global, lalu satu scope dalam yang melakukan shadowing terhadap x di scope luar. Setelah scope dalam ditutup, resolve untuk x kembali menemukan symbol di scope global, sedangkan resolve untuk y (yang hanya ada di scope dalam) mengembalikan None. Berkas ini menjadi aset kanonis yang dipakai ulang oleh topik resolusi-scope dan pemeriksaan-tipe.

python symbol_table.py

"""Tabel simbol dengan scope bersarang untuk bahasa mini v1.

Antarmuka publik:
    SymbolTable().define(name, symbol) -> Symbol
    SymbolTable().resolve(name) -> Symbol | None
    SymbolTable().push() / pop() untuk membuka dan menutup scope.

Symbol menyimpan nama, jenis, dan posisi deklarasi. Scope dirantai ke
parent sehingga resolve() mencari dari scope saat ini ke atas sampai
scope global. Field type_hint pada Symbol sengaja dibiarkan None pada
modul ini. Pemeriksa tipe pada topik pemeriksaan-tipe yang mengisinya.
"""
from dataclasses import dataclass


@dataclass
class Symbol:
    """Satu entri pada tabel simbol."""
    name: str
    kind: str                    # "var" untuk bahasa mini v1
    declared_line: int
    declared_column: int
    type_hint: str | None = None  # diisi oleh type checker; None bila belum


class SemanticError(Exception):
    """Error semantik dasar dengan pesan yang dapat ditampilkan."""


class Scope:
    """Satu lapis scope yang dirantai ke parent-nya."""

    def __init__(self, parent: "Scope | None" = None) -> None:
        self.parent = parent
        self.symbols: dict[str, Symbol] = {}


class SymbolTable:
    """Tabel simbol dengan kumpulan scope bersarang."""

    def __init__(self) -> None:
        self.root = Scope()
        self.current = self.root
        self.depth = 0

    def push(self) -> Scope:
        """Buka scope baru, jadikan scope saat ini."""
        self.current = Scope(parent=self.current)
        self.depth += 1
        return self.current

    def pop(self) -> None:
        """Tutup scope saat ini, kembali ke parent."""
        if self.current.parent is None:
            raise SemanticError("tidak dapat menutup scope global")
        self.current = self.current.parent
        self.depth -= 1

    def define(self, name: str, symbol: Symbol) -> Symbol:
        """Tambahkan symbol ke scope saat ini. Gagal bila nama sudah ada."""
        if name in self.current.symbols:
            existing = self.current.symbols[name]
            raise SemanticError(
                f"nama {name!r} sudah dideklarasikan pada "
                f"{existing.declared_line}:{existing.declared_column}"
            )
        self.current.symbols[name] = symbol
        return symbol

    def resolve(self, name: str) -> Symbol | None:
        """Cari symbol dari scope saat ini ke atas. None bila tidak ada."""
        scope: Scope | None = self.current
        while scope is not None:
            if name in scope.symbols:
                return scope.symbols[name]
            scope = scope.parent
        return None


def main() -> None:
    st = SymbolTable()
    # Scope global: deklarasi x dan pi.
    st.define("x", Symbol("x", "var", declared_line=1, declared_column=5))
    st.define("pi", Symbol("pi", "var", declared_line=2, declared_column=5,
                           type_hint="float"))

    print(f"depth awal            : {st.depth}")
    print(f"resolve 'x'  (global) : {st.resolve('x')}")
    print(f"resolve 'pi' (global) : {st.resolve('pi')}")

    # Masuk blok dalam.
    st.push()
    print(f"depth setelah push    : {st.depth}")
    st.define("y", Symbol("y", "var", declared_line=3, declared_column=9))
    # Shadowing: x di scope dalam menutup x di scope luar.
    st.define("x", Symbol("x", "var", declared_line=3, declared_column=9))

    print(f"resolve 'x'  (dalam)  : {st.resolve('x')}")
    print(f"resolve 'y'  (dalam)  : {st.resolve('y')}")
    print(f"resolve 'pi' (naik)   : {st.resolve('pi')}")
    print(f"resolve 'z'  (tidak ada) : {st.resolve('z')}")

    # Cek redeclarasi pada scope yang sama.
    try:
        st.define("y", Symbol("y", "var", declared_line=4, declared_column=9))
    except SemanticError as e:
        print(f"redeclare 'y'        : {e}")

    # Tutup scope dalam.
    st.pop()
    print(f"depth setelah pop     : {st.depth}")
    print(f"resolve 'x'  (global) : {st.resolve('x')}")
    print(f"resolve 'y'  (tidak ada) : {st.resolve('y')}")


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 symbol_table.py. Setelah push, scope dalam memuat y dan x yang menutup x global. Pemanggilan resolve('x') pada scope dalam mengembalikan symbol x yang berada di scope dalam, bukan di scope global. Pemanggilan resolve('pi') naik ke scope global dan menemukan symbol pi dengan type_hint='float'. Setelah pop, resolve('x') kembali ke symbol global, sedangkan resolve('y') mengembalikan None karena scope dalam sudah ditutup.

text Keluaran

depth awal            : 0
resolve 'x'  (global) : Symbol(name='x', kind='var', declared_line=1, declared_column=5, type_hint=None)
resolve 'pi' (global) : Symbol(name='pi', kind='var', declared_line=2, declared_column=5, type_hint='float')
depth setelah push    : 1
resolve 'x'  (dalam)  : Symbol(name='x', kind='var', declared_line=3, declared_column=9, type_hint=None)
resolve 'y'  (dalam)  : Symbol(name='y', kind='var', declared_line=3, declared_column=9, type_hint=None)
resolve 'pi' (naik)   : Symbol(name='pi', kind='var', declared_line=2, declared_column=5, type_hint='float')
resolve 'z'  (tidak ada) : None
redeclare 'y'        : nama 'y' sudah dideklarasikan pada 3:9
depth setelah pop     : 0
resolve 'x'  (global) : Symbol(name='x', kind='var', declared_line=1, declared_column=5, type_hint=None)
resolve 'y'  (tidak ada) : None

Disiplin pencarian dan antarmuka publik#

Pencarian pada resolve bergerak dari scope saat ini ke parent. Karena itu, nama yang dideklarasikan pada scope dalam tidak pernah bocor ke scope luar, sedangkan nama di scope luar tetap terlihat dari scope dalam selama belum di-shadow. Sifat ini cocok dengan semantik bahasa mini v1, di mana blok membuka scope baru dan deklarasi di dalam blok berakhir saat blok ditutup.

Antarmuka publik SymbolTable sengaja dipertahankan kecil. Empat operasi push, pop, define, dan resolve cukup untuk diperlukan resolver, pemeriksa tipe, dan codegen. Bila modul IR perlu melacak nama ke alamat slot pada stack, modul itu dapat menambahkan field pada Symbol (dengan nilai default) tanpa mengubah operasi yang sudah ada. Hal ini sejalan dengan kebijakan stabilitas AST pada topik desain-ast, di mana penambahan field baru diizinkan selama field lama tidak diganti nama atau diubah tipenya.

Kesalahan umum#

Beberapa kesalahan sering muncul saat tabel simbol ditulis. Pertama, mencari nama hanya pada scope saat ini tanpa naik ke parent, sehingga variabel global tidak terlihat dari dalam blok. Kedua, menggunakan satu dictionary untuk semua scope, sehingga shadowing tidak mungkin terjadi dan redeclarasi pada scope berbeda keliru ditandai sebagai error. Ketiga, lupa memanggil pop setelah push sehingga kedalaman scope terus tumbuh dan pemulihan setelah error menjadi tidak seimbang. Ketiga kasus ini menyebabkan resolver melaporkan nama valid sebagai tak terdefinisi, atau menerima nama yang seharusnya ditolak.

Ringkasan#

Tabel simbol memetakan nama ke informasi yang melekat, dengan struktur scope bersarang yang dirantai ke parent.
Tiga class Symbol, Scope, dan SymbolTable menyediakan empat operasi publik: push, pop, define, dan resolve.
define menolak redeclarasi pada scope yang sama, sedangkan resolve mencari dari scope saat ini ke atas, sehingga shadowing pada scope berbeda diperbolehkan.
Field type_hint pada Symbol dibiarkan kosong pada modul ini dan akan diisi oleh pemeriksa tipe, sehingga satu entri dapat dipakai bersama oleh resolver, pemeriksa tipe, dan codegen.

Referensi#

Symbol table — Wikipedia — Ringkasan konseptual tabel simbol, scope chain, dan operasi dasar yang dipakai compiler.
Crafting Interpreters — Bob Nystrom — Bab “Statements and State” menjelaskan environment berlapis yang merepresentasikan scope pada interpreter.
Compilers: Principles, Techniques, and Tools — Wikipedia — Bab “Symbol Tables” membahas representasi scope bersarang dan disiplin pencarian nama.