KAL
Menu

Desain AST ?

Hierarki node AST, pohon ekspresi versus pohon pernyataan, dan tag jenis node.

Daftar isi

Topik ini membahas desain AST (Abstract Syntax Tree) sebagai representasi tengah antara parser dan modul semantik, IR, serta codegen. Pembaca memperoleh hierarki node AST untuk bahasa mini v1 yang ditetapkan sebagai kontrak stabil sepanjang sisa jalur, beserta pemformat diagnostik yang membantu inspeksi pohon. Setiap perubahan pada struktur class di sini berakibat pada modul 3 hingga 5, sehingga desain field tiap node dipertahankan sederhana dan eksplisit.

Apa itu AST#

AST adalah pohon sintaks abstrak yang mewakili struktur program tanpa detail sintaksis yang tidak relevan. Berbeda dari pohon derivasi penuh yang dihasilkan parser generator, AST hanya menyimpan node yang membawa makna semantik. Sebagai contoh, tanda kurung pada (1 + 2) hilang dari AST karena informasi pengelompokan sudah tertangkap oleh struktur pohon itu sendiri, yaitu 1 + 2 menjadi satu node Binary yang membungkus dua anak.

AST berperan sebagai kontrak antara front end (parser) dan back end (semantik, IR, codegen). Front end bertugas membangun AST yang sesuai kontrak, sedangkan back end bertugas mengonsumsi AST tanpa peduli detail sintaksis sumber. Pemisahan ini memungkinkan back end ditulis ulang tanpa menyentuh parser, dan sebaliknya. Pada jalur ini, AST didefinisikan pada topik desain-ast, dipakai oleh modul 3 (semantik), modul 4 (IR), dan modul 5 (codegen).

Hierarki node AST#

Bahasa mini v1 membagi AST menjadi tiga kelompok, yaitu Expr untuk ekspresi, Stmt untuk pernyataan, dan Program untuk unit kompilasi paling luar. Hierarki ini direpresentasikan sebagai dataclass Python, dengan kelas dasar Expr dan Stmt sebagai penanda jenis. Kelas turunan menyimpan field yang relevan untuk node itu, dan dataclass memberikan __init__, __eq__, dan __repr__ secara otomatis.

Tabel berikut merangkum node Expr beserta field-nya.

text Node Expr 
Binary(left, op, right)   Operasi biner: +, -, *, /, <, <=, >, >=, ==, !=
Unary(op, operand)        Operasi unary: - (negasi), ! (negasi bool)
Literal(value)            Nilai literal: int, float, str, bool, None
Variable(name)            Referensi variabel berdasarkan nama
Assign(name, value)       Penetapan ulang variabel
Logical(left, op, right)  Operator logika and dan or
Grouping(expression)      Ekspresi dalam tanda kurung

Tabel berikut merangkum node Stmt beserta field-nya.

text Node Stmt 
Let(name, initializer)     Deklarasi dan penetapan awal
Print(expression)          Cetak ekspresi ke keluaran standar
If(condition, then, else)  Percabangan, else boleh None
While(condition, body)      Perulangan
Block(statements)           Blok yang membuka scope baru
Expression(expression)      Pernyataan ekspresi, hasil dibuang

Node Program menyimpan statements: list[Stmt] dan menjadi akar pohon. Field else_branch pada If diberi nilai default None sehingga parser dapat membangun If tanpa cabang else secara alami. Field statements pada Block dan Program memakai field(default_factory=list) agar list baru dibuat per instansiasi, bukan satu list yang dipakai bersama.

Tag jenis node dan stabilitas kontrak#

Setiap node menyimpan informasi yang diperlukan tahap analisis semantik dan codegen, dan tidak lebih. Field op pada Binary, Unary, dan Logical menyimpan lexeme operator sebagai string, sehingga pesan error dan codegen dapat menyebut operator sumber tanpa menyimpan token lengkap. Field value pada Literal menyimpan nilai Python yang sudah dikonversi dari lexeme, yaitu int atau float untuk NUMBER, str untuk STRING, bool untuk true/false, dan None untuk nil.

Pilihan menyimpan lexeme (string) alih-alih objek Token penuh menjaga AST tetap ringan. Token penuh membawa informasi posisi sumber (line, column) yang berguna saat parsing, tetapi tidak lagi diperlukan setelah AST terbentuk. Modul 3 (semantik) dapat menambahkan informasi posisi sesuai kebutuhan lewat tabel samping, sehingga AST tetap stabil.

Stabilitas kontrak berarti field tiap node tidak berubah sepanjang sisa jalur. Penambahan field baru diizinkan dengan nilai default, tetapi penggantian nama field atau perubahan tipe field akan memutus modul 3 hingga 5. Karena itu desain pada topik ini disusun lebih dulu, sebelum parser ditulis, agar parser menghasilkan node yang persis sesuai kontrak.

Pemformat diagnostik#

dataclass memberikan __repr__ default yang mencantumkan nama kelas dan field, sehingga repr(node) cukup untuk diagnostik baris tunggal. Untuk pohon yang dalam, keluaran default menjadi panjang, sehingga topik ini menyertakan pemformat pretty(node) yang menghasilkan pohon terindentasi. Kedua bentuk dipakai bergantian sesuai kebutuhan, yaitu repr untuk inspeksi cepat dan pretty untuk inspeksi struktur penuh.

Pemformat pretty tidak menambah informasi baru, hanya menampilkan informasi yang sudah disimpan field. Pemformat ditulis sebagai fungsi terpisah agar tetap berada di luar hierarki dataclass, sehingga penambahan node baru tidak menyentuh pemformat kecuali untuk menambah satu cabang elif. Pola ini dipakai ulang oleh parser pada topik recursive-descent agar keluaran demo tetap konsisten.

Berkas ast_nodes.py#

Berkas berikut adalah kontrak kanonis AST untuk bahasa mini v1. Struktur class yang didefinisikan di sini menjadi acuan tetap yang dipakai tahap analisis semantik, IR, dan codegen. Demo main() membangun satu AST kecil untuk program let x = 1 + 2 * 3 diikuti print x, lalu mencetak kedua bentuk diagnostik.

python ast_nodes.py 
"""Definisi node AST untuk bahasa mini v1.

Kontrak ini menjadi masukan modul semantik (modul 3), IR (modul 4),
dan codegen (modul 5). Setiap perubahan pada struktur class di sini
berakibat pada ketiga modul tersebut, sehingga field tiap node
dipertahankan stabil.

Hierarki:
  Expr
    Binary(left, op, right)
    Unary(op, operand)
    Literal(value)
    Variable(name)
    Assign(name, value)
    Logical(left, op, right)
    Grouping(expression)
  Stmt
    Let(name, initializer)
    Print(expression)
    If(condition, then_branch, else_branch)
    While(condition, body)
    Block(statements)
    Expression(expression)
  Program(statements)

Field `op` pada Binary, Unary, dan Logical menyimpan lexeme operator
sebagai string, sehingga pesan error dan codegen dapat menyebut
operator sumber. Field `value` pada Literal menyimpan nilai Python
yang sudah dikonversi dari lexeme (int, float, str, bool, None).
"""
from dataclasses import dataclass, field
from typing import Any


# ----- Expr -----
@dataclass
class Expr:
    """Akar hierarki ekspresi."""


@dataclass
class Binary(Expr):
    left: Expr
    op: str
    right: Expr


@dataclass
class Unary(Expr):
    op: str
    operand: Expr


@dataclass
class Literal(Expr):
    value: Any


@dataclass
class Variable(Expr):
    name: str


@dataclass
class Assign(Expr):
    name: str
    value: Expr


@dataclass
class Logical(Expr):
    left: Expr
    op: str  # "and" atau "or"
    right: Expr


@dataclass
class Grouping(Expr):
    expression: Expr


# ----- Stmt -----
@dataclass
class Stmt:
    """Akar hierarki pernyataan."""


@dataclass
class Let(Stmt):
    name: str
    initializer: Expr


@dataclass
class Print(Stmt):
    expression: Expr


@dataclass
class If(Stmt):
    condition: Expr
    then_branch: Stmt
    else_branch: Stmt | None = None


@dataclass
class While(Stmt):
    condition: Expr
    body: Stmt


@dataclass
class Block(Stmt):
    statements: list[Stmt] = field(default_factory=list)


@dataclass
class Expression(Stmt):
    expression: Expr


# ----- Program -----
@dataclass
class Program:
    statements: list[Stmt] = field(default_factory=list)


# ----- Pemformat diagnostik -----
def pretty(node: Any, indent: int = 0) -> str:
    """Format node AST sebagai pohon terindentasi untuk diagnostik."""
    lines: list[str] = []
    _emit(node, "  " * indent, lines)
    return "\n".join(lines) + "\n"


def _emit(node: Any, pad: str, lines: list[str]) -> None:
    if isinstance(node, Program):
        lines.append(f"{pad}Program")
        for s in node.statements:
            _emit(s, pad + "  ", lines)
    elif isinstance(node, Block):
        lines.append(f"{pad}Block")
        for s in node.statements:
            _emit(s, pad + "  ", lines)
    elif isinstance(node, Let):
        lines.append(f"{pad}Let {node.name!r}")
        _emit(node.initializer, pad + "  ", lines)
    elif isinstance(node, Print):
        lines.append(f"{pad}Print")
        _emit(node.expression, pad + "  ", lines)
    elif isinstance(node, If):
        lines.append(f"{pad}If")
        lines.append(f"{pad}  kondisi:")
        _emit(node.condition, pad + "    ", lines)
        lines.append(f"{pad}  maka:")
        _emit(node.then_branch, pad + "    ", lines)
        if node.else_branch is not None:
            lines.append(f"{pad}  jika_tidak:")
            _emit(node.else_branch, pad + "    ", lines)
    elif isinstance(node, While):
        lines.append(f"{pad}While")
        lines.append(f"{pad}  kondisi:")
        _emit(node.condition, pad + "    ", lines)
        lines.append(f"{pad}  badan:")
        _emit(node.body, pad + "    ", lines)
    elif isinstance(node, Expression):
        lines.append(f"{pad}ExprStmt")
        _emit(node.expression, pad + "  ", lines)
    elif isinstance(node, Binary):
        lines.append(f"{pad}Binary {node.op!r}")
        _emit(node.left, pad + "  ", lines)
        _emit(node.right, pad + "  ", lines)
    elif isinstance(node, Logical):
        lines.append(f"{pad}Logical {node.op!r}")
        _emit(node.left, pad + "  ", lines)
        _emit(node.right, pad + "  ", lines)
    elif isinstance(node, Unary):
        lines.append(f"{pad}Unary {node.op!r}")
        _emit(node.operand, pad + "  ", lines)
    elif isinstance(node, Grouping):
        lines.append(f"{pad}Grouping")
        _emit(node.expression, pad + "  ", lines)
    elif isinstance(node, Assign):
        lines.append(f"{pad}Assign {node.name!r}")
        _emit(node.value, pad + "  ", lines)
    elif isinstance(node, Literal):
        lines.append(f"{pad}Literal {node.value!r}")
    elif isinstance(node, Variable):
        lines.append(f"{pad}Variable {node.name!r}")
    else:
        lines.append(f"{pad}{node!r}")


def main() -> None:
    # Membangun satu AST untuk program:
    #   let x = 1 + 2 * 3
    #   print x
    program = Program(statements=[
        Let(name="x", initializer=Binary(
            left=Literal(value=1),
            op="+",
            right=Binary(
                left=Literal(value=2),
                op="*",
                right=Literal(value=3),
            ),
        )),
        Print(expression=Variable(name="x")),
    ])
    print("=== repr default (diagnostik baris tunggal) ===")
    print(repr(program))
    print()
    print("=== pretty (pohon terindentasi) ===")
    print(pretty(program), end="")


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 ast_nodes.py. Bagian pertama adalah repr(program) yang menampilkan seluruh pohon dalam satu baris, sedangkan bagian kedua adalah pretty(program) yang memecah pohon menjadi baris-baris terindentasi. Kedua bentuk dihasilkan oleh struktur class yang sama, sehingga pemformat tidak menambah informasi baru, hanya menampilkan informasi yang sudah disimpan field.

text Keluaran 
=== repr default (diagnostik baris tunggal) ===
Program(statements=[Let(name='x', initializer=Binary(left=Literal(value=1), op='+', right=Binary(left=Literal(value=2), op='*', right=Literal(value=3)))), Print(expression=Variable(name='x'))])

=== pretty (pohon terindentasi) ===
Program
  Let 'x'
    Binary '+'
      Literal 1
      Binary '*'
        Literal 2
        Literal 3
  Print
    Variable 'x'

Ringkasan#

  • AST terdiri atas tiga kelompok, yaitu Expr untuk ekspresi, Stmt untuk pernyataan, dan Program sebagai akar pohon.
  • Field op pada Binary, Unary, dan Logical menyimpan lexeme operator sebagai string, dan field value pada Literal menyimpan nilai Python yang sudah dikonversi dari lexeme.
  • dataclass memberikan __repr__ default yang berguna untuk diagnostik baris tunggal, sedangkan pemformat pretty(node) menghasilkan pohon terindentasi untuk inspeksi struktur.
  • Kontrak ini stabil sepanjang modul 3 hingga 5, sehingga penambahan field baru diperbolehkan dengan nilai default, tetapi penggantian nama atau tipe field akan memutus back end.

Referensi#