# TOPIK 4 OPTIMASI KODE DAN GENERASI KODE OBJEK

TUJUAN
1. Memahami teknik optimasi kode dalam kompilasi.
2. Mempelajari proses pembuatan kode objek dari kode antara.
3. Mengimplementasikan teknik optimasi sederhana.

## TEORI
<div style="text-align: justify;">
Optimasi Generasi Kode adalah proses dimana pembangkit code compiler mengkonversi beberapa representasi intermediate kode sumber (source code) kedalam bentuk
kode mesin yang dengan mudah dapat dijalankan oleh mesin. Code generation merupakan tahapan terakhir pada proses kompilasi. Optimasi ini dilakukan oleh compiler pada tahap setelah kode telah diubah menjadi representasi internal, seperti Abstract Syntax Tree (AST) atau intermediate code, sebelum kode tersebut diterjemahkan menjadi kode objek atau kode mesin.

Optimasi kode dapat mencakup berbagai teknik, seperti menghapus kode yang tidak digunakan (dead code elimination), menyederhanakan ekspresi aritmatika, mengurangi jumlah instruksi, dan meminimalkan akses ke memori yang mahal. Tujuan utama dari optimasi kode adalah untuk membuat program berjalan lebih cepat dan menggunakan lebih sedikit sumber daya, yang sangat penting dalam aplikasi yang memerlukan performa tinggi atau yang berjalan pada perangkat dengan keterbatasan sumber daya.

Dalam konteks pengembangan perangkat lunak, optimasi kode seringkali dianggap sebagai langkah penting untuk memastikan perangkat lunak yang efisien dan handal. Namun, perlu diingat bahwa optimasi harus dilakukan dengan hati-hati, karena optimasi yang berlebihan dapat membuat kode menjadi lebih kompleks dan sulit dipahami atau dipelihara.

### Pengertian Generasi Kode Objek
Generasi kode objek adalah tahap dalam proses kompilasi di mana representasi menengah dari program (seperti Abstract Syntax Tree atau intermediate code) diterjemahkan menjadi kode mesin atau bytecode yang dapat dieksekusi oleh komputer atau mesin virtual. Kode objek ini adalah bentuk yang lebih rendah dan lebih dekat dengan bahasa mesin yang spesifik untuk arsitektur target tempat program akan dijalankan. Input pada generator code biasanya terdiri dari pohon parse (parse tree) atau abstract syntax tree. Pohon (tree) dikonversikan kedalam rentetan instruksi linear, biasanya dalam sebuah bahasa intermediate seperti three-address code.
Proses generasi kode objek melibatkan beberapa langkah penting, termasuk pengalokasian register, penjadwalan instruksi, dan penanganan memori. Setiap langkah ini dirancang untuk memastikan bahwa kode objek yang dihasilkan tidak hanya benar secara fungsional, tetapi juga efisien dalam hal kinerja eksekusi dan penggunaan sumber daya.

Generasi kode objek adalah salah satu tahap akhir dalam kompilasi, yang mengubah program dari bentuk yang mudah dipahami oleh manusia menjadi bentuk yang dapat dijalankan langsung oleh mesin. Hasil dari generasi kode objek biasanya adalah file biner, seperti file .exe pada Windows atau .out pada sistem Unix, yang siap untuk dijalankan oleh sistem operasi atau
prosesor.

**Peran Dalam Proses Kompilasi**

Generasi kode objek memainkan peran krusial dalam proses kompilasi sebagai salah satu tahap akhir yang mengubah representasi menengah program menjadi bentuk yang dapat dieksekusi oleh komputer atau mesin virtual. Setelah kode sumber melalui analisis leksikal, sintaksis, dan semantik, serta berbagai optimasi, generasi kode objek bertanggung jawab untuk menghasilkan kode yang efisien dan sesuai dengan arsitektur target.

### Optimasi Kode
Optimasi kode dalam kompilasi terbagi menjadi berbagai jenis, tergantung pada cakupan dan metode yang digunakan. Secara umum, optimasi dapat dikategorikan menjadi optimasi lokal dan optimasi global, masing-masing dengan karakteristik dan teknik tersendiri.

#### 1. Optimasi Lokal
Optimasi lokal adalah jenis optimasi yang diterapkan pada blok kode kecil, biasanya pada tingkat blok dasar (basic block). Blok dasar adalah urutan instruksi yang dieksekusi secara berurutan tanpa percabangan kecuali di akhir, dan tidak ada instruksi lain yang dapat masuk ke tengah blok tersebut. Optimasi lokal berfokus pada penyempurnaan kode dalam blok ini untuk meningkatkan efisiensi eksekusi tanpa memerlukan informasi dari luar blok.

Optimasi lokal bekerja dengan mengidentifikasi dan mengeliminasi inefisiensi dalam blok kode tertentu. Karena ruang lingkupnya terbatas, analisis dan transformasi yang dilakukan dalam optimasi lokal biasanya lebih sederhana dan cepat dibandingkan dengan optimasi global. Teknik-teknik optimasi lokal termasuk penyederhanaan ekspresi, penghapusan kode mati, dan penggantian variabel dengan konstanta.

Contoh: Penghapusan Kode Mati (Dead Code Elimination):
* Dead Code Elimination (DCE) adalah salah satu teknik optimasi lokal yang umum digunakan. Kode mati adalah instruksi atau blok kode yang tidak pernah digunakan atau mempengaruhi hasil akhir dari program. Menghapus kode mati dapat mengurangi ukuran program dan meningkatkan efisiensi eksekusi.
* Misalnya, jika sebuah variabel diberi nilai tetapi nilainya tidak pernah digunakan sebelum variabel tersebut diubah atau dihapus, instruksi yang memberikan nilai tersebut dapat dihapus tanpa mempengaruhi program

#### 2. Optimasi Global
Optimasi global adalah proses meningkatkan kinerja program dengan menganalisis dan memodifikasi kode yang mencakup lebih dari satu blok dasar, sering kali melibatkan seluruh fungsi atau prosedur. Berbeda dengan optimasi lokal, yang hanya mempertimbangkan instruksi dalam satu blok dasar, optimasi global memperhitungkan bagaimana data dan aliran kontrol bekerja di seluruh bagian program yang lebih luas. Ini memungkinkan optimasi yang lebih mendalam dan berdampak besar terhadap efisiensi keseluruhan program. Karena cakupan analisisnya yang luas, optimasi global sering kali membutuhkan lebih banyak waktu komputasi, namun hasil optimasi ini cenderung memberikan peningkatan performa yang signifikan dibandingkan dengan optimasi lokal saja.

Contoh: Pemindahan Kode Loop Invariants:
Loop Invariant Code Motion adalah salah satu teknik optimasi global yang efektif. Teknik ini melibatkan pemindahan ekspresi atau perhitungan yang hasilnya tidak berubah di setiap iterasi loop ke luar loop, sehingga menghindari pengulangan perhitungan yang tidak
perlu.

Sebagai contoh, pertimbangkan loop berikut:

for i in range(100): 
    x = 10 * 20 
    y = i + x 
print(y) 

Dalam kode di atas, ekspresi x = 10 * 20 menghasilkan nilai yang sama di setiap iterasi loop. Oleh karena itu, perhitungan ini dapat dipindahkan keluar dari loop, seperti berikut:

x = 10 * 20 
for i in range(100): 
    y = i + x 
    print(y)

Dengan memindahkan perhitungan ini keluar dari loop, kita mengurangi jumlah instruksi yang dieksekusi dalam loop, yang pada akhirnya meningkatkan efisiensi eksekusi.

**Teknik-Teknik Optimasi**
Optimasi kode melibatkan berbagai teknik yang dirancang untuk meningkatkan efisiensi eksekusi program. Teknik-teknik ini membantu mengurangi jumlah instruksi yang perlu dijalankan, meminimalkan penggunaan memori, dan mempercepat waktu komputasi. Beberapa teknik optimasi yang umum digunakan termasuk penyederhanaan ekspresi, penggabungan konstanta, dan pengurangan jumlah variabel.

**1. Penyederhanaan Ekspresi**

Penyederhanaan ekspresi adalah teknik optimasi yang berfokus pada mengidentifikasi dan mengurangi kompleksitas ekspresi dalam kode. Teknik ini bertujuan untuk menghilangkan perhitungan yang tidak perlu atau menyederhanakan operasi aritmatika agar lebih efisien. Penyederhanaan ekspresi melibatkan pengurangan jumlah operasi yang harus dilakukan dengan menggantikan ekspresi yang kompleks dengan yang lebih sederhana tetapi setara. Hal ini dapat dilakukan dengan mengganti operasi yang mahal dengan yang lebih murah atau dengan mengeliminasi operasi yang tidak diperlukan. Penyederhanaan ini sering kali bergantung pada sifat matematis dari ekspresi, seperti properti distributif, asosiatif, atau komutatif.
Contoh : Pertimbangkan ekspresi berikut

Dalam ekspresi ini, a * 1 selalu sama dengan a, dan a + 0 juga sama dengan a. Oleh karena itu, ekspresi tersebut dapat disederhanakan menjadi:

Dengan demikian, kita mengeliminasi dua operasi yang tidak perlu (* 1 dan + 0), yang membuat kode lebih efisien.

**2. Penggabungan Konstanta**
Penggabungan konstanta adalah teknik optimasi yang mengidentifikasi operasi dengan konstanta yang dapat dievaluasi pada waktu kompilasi, dan menggantinya dengan hasil perhitungan tersebut, sehingga mengurangi jumlah operasi yang harus dilakukan pada saat runtime.

Misalkan terdapat ekspresi berikut dalam kode:

Karena semua operand dalam ekspresi ini adalah konstanta, compiler dapat menggantinya dengan hasil yang telah dihitung:

Dengan penggabungan konstanta, kita menghindari dua operasi aritmatika (* dan +) saat runtime, membuat eksekusi kode lebih cepat.

**3. Generasi Kode Objek**
Generasi kode objek adalah tahap dalam proses kompilasi di mana representasi menengah dari program, seperti Abstract Syntax Tree (AST), diterjemahkan menjadi kode yang dapat dieksekusi oleh mesin atau mesin virtual. Tahap ini sangat penting karena menghubungkan pemrosesan tingkat tinggi dengan eksekusi perangkat keras atau lingkungan eksekusi yang dituju. Tahapan dalam Generasi Kode Objek :

- Pemilihan Instruksi: Langkah pertama dalam generasi kode objek adalah memilih instruksi dari set instruksi arsitektur target yang sesuai dengan operasi yang perlu dilakukan oleh program. Ini termasuk memilih instruksi yang optimal untuk operasi tertentu, seperti penambahan, pengurangan, atau pengendalian alur.
- Pengalokasian Register: Setelah instruksi dipilih, kompilator harus mengalokasikan register prosesor yang akan digunakan untuk menyimpan variabel sementara selama eksekusi program. Pengalokasian register yang efisien sangat penting untuk kinerja, karena akses register jauh lebih cepat dibandingkan akses memori utama.
- Penjadwalan Instruksi: Instruksi yang telah dipilih dan variabel yang telah dialokasikan pada register perlu dijadwalkan untuk eksekusi. Penjadwalan ini mempertimbangkan dependensi data dan aliran kontrol untuk memaksimalkan penggunaan sumber daya prosesor, seperti eksekusi paralel.
- Pengelolaan Memori: Kompilator juga bertanggung jawab untuk mengatur alokasi memori, termasuk penempatan data dan variabel di memori utama dan pengaturan stack serta heap.

**Hubungan antara AST dan Kode Objek:**
* Abstract Syntax Tree (AST) adalah representasi struktural dari program yang memodelkan elemen-elemen sintaksis dalam bentuk pohon. Setiap node dalam AST mewakili operasi atau struktur kontrol dalam program.
* Proses generasi kode objek memanfaatkan AST untuk memahami dan mengubah logika program menjadi kode mesin yang setara. Misalnya, node AST yang mewakili operasi penambahan akan diterjemahkan menjadi instruksi penambahan pada arsitektur target.
* AST menyediakan fondasi bagi kompilator untuk memahami struktur dan aliran logika dalam program, yang kemudian diterjemahkan menjadi urutan instruksi mesin yang ekivalen.

**Teknik-Teknik Generasi Kode**

**1. Generasi Kode Linier**
Generasi kode linier adalah metode sederhana di mana instruksi dihasilkan dalam urutan yang sama seperti aliran kontrol dalam program sumber. Setiap operasi dalam AST diterjemahkan secara langsung menjadi satu atau lebih instruksi dalam urutan linier, tanpa memperhitungkan optimasi yang mungkin dilakukan.

Contoh : Misalnya, untuk ekspresi a = b + c, generasi kode linier akan menghasilkan urutan instruksi berikut (dalam pseudocode):
<pre>LOAD b, R1 ; Muat nilai b ke register R1
ADD c, R1 ; Tambah nilai c ke R1
STORE R1, a ; Simpan hasil ke a</pre>

**2. Generasi Kode Terstruktur**

Generasi kode terstruktur melibatkan penerapan aturan dan optimasi untuk menghasilkan instruksi dengan mempertimbangkan struktur kontrol dan dependensi data. Kode yang dihasilkan biasanya lebih efisien karena mempertimbangkan optimasi seperti penggabungan instruksi dan pengalokasian register yang lebih baik.

Contoh: Jika ekspresi a = b + c berada di dalam loop, dan b dan c tidak berubah, generasi kode terstruktur mungkin menghasilkan kode yang melakukan perhitungan hanya sekali di luar loop, kemudian menyimpan hasilnya untuk digunakan kembali.
<pre>
LOAD b, R1 ; Muat nilai b ke register R1
ADD c, R1 ; Tambah nilai c ke R1
STORE R1, temp ; Simpan hasil ke temp
LOOP_START: ; Mulai loop
STORE temp, a ; Simpan hasil ke a
... ; Instruksi lain dalam loop
LOOP_END:
</pre>
Contoh : Transformasi AST menjadi Kode Objek

Anggaplah kita memiliki AST yang mewakili ekspresi x = (a + b) * c. Transformasi AST ini
menjadi kode objek bisa menghasilkan instruksi seperti berikut:
<pre>LOAD a, R1 ; Muat nilai a ke register R1
ADD b, R1 ; Tambah nilai b ke R1
MUL c, R1 ; Kalikan hasil dengan c
STORE R1, x ; Simpan hasil ke x</pre>

### Implementasi Optimasi Kode Dan Generasi Kode

Pada bahasaku teknik-teknik optimasi yang digunakan yaitu penyederhanaan ekspresi dan penggabungan konstanta, dan teknik yang digunakan untuk generasi kode adalah generasi kode linear. Berikut ini adalah kode program untuk Optimasi kode adan Generasi Kode dalam BahasaKu

1. **Langkah 1:** Definisikan Optimasi IR berikut ini di bawah kode pembangkit kode antara atau generate_ir()

   # ===== OPTIMASI IR (LANGKAH 1) =====
    def optimize_ir(self, ir):

        optimized = []

        for line in ir:
            parts = line.split()

            # pola: t0 = NUM OP NUM
            if len(parts) == 5 and parts[1] == '=' and parts[2].isdigit() and parts[4].isdigit():

                left = int(parts[2])
                op = parts[3]
                right = int(parts[4])

                if op == '+': result = left + right
                elif op == '-': result = left - right
                elif op == '*': result = left * right
                elif op == '/': result = left / right
                else:
                    optimized.append(line)
                    continue

                # replace with folded value
                new_line = f"{parts[0]} = {int(result)}"
                optimized.append(new_line)
                continue

            optimized.append(line)

        return optimized

**Langkah 2:** Selanjutnya definisikan generasi kode objek.

    # ===== GENERASI KODE OBJEK (MESIN REGISTER) =====
    def generate_object_code(self, ir):
        """
        Mesin semu berbasis 1 register (R0)
        Instruksi: LOAD, ADD, SUB, MUL, DIV, CONCAT, STORE, OUT, JZ, JMP, LABEL
        """

        for line in ir:
            parts = line.split()

            # LABEL: "L0:"
            if line.endswith(":"):
                label = parts[0][:-1]
                print(f"LABEL {label}")
                continue

            # PRINT: "PRINT x"
            if parts[0] == "PRINT":
                val = parts[1]
                print(f"LOAD {val}, R0")
                print("OUT")
                continue

            # IF_FALSE cond GOTO L0
            if parts[0] == "IF_FALSE":
                cond = parts[1]
                label = parts[3]
                print(f"LOAD {cond}, R0")
                print(f"JZ {label}")
                continue

            # GOTO L1
            if parts[0] == "GOTO":
                label = parts[1]
                print(f"JMP {label}")
                continue

            # ASSIGNMENT
            if len(parts) >= 3 and parts[1] == '=':
                dest = parts[0]
                expr = parts[2:]

                # Kasus 1 operand: x = 5, x = t0, x = "Raihana"
                if len(expr) == 1:
                    src = expr[0]
                    print(f"LOAD {src}, R0")
                    print(f"STORE R0, {dest}")
                    continue

                # Kasus operasi biner: t1 = a + b
                if len(expr) == 3:
                    left = expr[0]
                    op = expr[1]
                    right = expr[2]

                    print(f"LOAD {left}, R0")

                    if op == '+':
                        # Jika salah satu operand string, CONCAT
                        if left.startswith('"') or right.startswith('"'):
                            print(f"CONCAT {right}, R0")
                        else:
                            print(f"ADD {right}, R0")
                    elif op == '-':
                        print(f"SUB {right}, R0")
                    elif op == '*':
                        print(f"MUL {right}, R0")
                    elif op == '/':
                        print(f"DIV {right}, R0")

                    print(f"STORE R0, {dest}")
                    continue
                continue

**Langkah 3:** Perbaiki fungsi run, menjadi seperti berikut. Simpan program BahasaKu.py.

    def run(self):
        print("="*60)
        print("TAHAP 1: PARSING")
        ast = self.parse_program()
        print("Parsing berhasil")

        print("="*60)
        print("POHON AST")
        self.print_ast(ast)
 
        print("="*60)
        print("TAHAP 2: SEMANTIC CHECKING")
        for stmt in ast:
            self.check_semantics(stmt)
        print("Semantic OK")
    
        ir = []
        temp_count = [0]
        label_count = [0]
        
        for stmt in ast:
            self.generate_ir(stmt, ir, temp_count, label_count)
        
        print("="*60)
        print("TAHAP 3: INTERMEDIATE CODE (Sebelum Optimasi)")
        for line in ir:
            print(line)
        optimized_ir = self.optimize_ir(ir)

        print("="*60)
        print("TAHAP 4: OPTIMIZED INTERMEDIATE CODE")
        for line in optimized_ir:
            print(line)

        print("="*60)
        print("TAHAP 5: GENERASI KODE OBJEK")
        self.generate_object_code(optimized_ir)
   
        print("="*60)
        print("TAHAP 6: EKSEKUSI")
        for stmt in ast:
            self.execute_statement(stmt)

Berikut ini adalah kode program BahasaKu secara lengkap

import sys

# ===== AST NODE CLASSES =====
class ASTNode: pass

class NumberNode(ASTNode):
    def __init__(self, value): self.value = value

class StringNode(ASTNode):
    def __init__(self, value): self.value = value

class VarNode(ASTNode):
    def __init__(self, name): self.name = name

class BinOpNode(ASTNode):
    def __init__(self, left, op, right):
        self.left = left
        self.op = op
        self.right = right

class AssignNode(ASTNode):
    def __init__(self, name, expr):
        self.name = name
        self.expr = expr

class PrintNode(ASTNode):
    def __init__(self, expr): self.expr = expr

class IfNode(ASTNode):
    def __init__(self, condition, if_block, elif_blocks=None, else_block=None):
        self.condition = condition
        self.if_block = if_block
        self.elif_blocks = elif_blocks or []
        self.else_block = else_block


class BahasaKu:
    def __init__(self, code):
        self.code = code
        self.line_nr = 0
        self.returned_token = None
        self.token_feed = self.tokens()
        self.vars = {}

        self.KEYWORDS = ['cetak', 'if', 'elif', 'else', 'end']
        self.OPERATORS = ['=', '+', '-', '*', '/', '==', '!=', '<', '>', '<=', '>=']
        self.SYMBOLS = ['(', ')', ':']

    def raise_error(self, msg):
        raise ValueError(f"Baris {self.line_nr}: {msg}")

    def reset_tokenizer(self):
        """Reset tokenizer agar bisa dipanggil ulang"""
        self.line_nr = 0
        self.returned_token = None
        self.token_feed = self.tokens()

    def tokens(self):
        for line in self.code.splitlines():
            self.line_nr += 1
            line = line.strip()

            if line == '':
                yield ('NEWLINE',)
                continue

            i = 0
            tokens = []
            while i < len(line):
                ch = line[i]

                if ch.isspace():
                    i += 1
                    continue

                if ch in '"\'':
                    quote = ch
                    i += 1
                    start = i
                    while i < len(line) and line[i] != quote:
                        i += 1
                    if i >= len(line):
                        self.raise_error("String tidak ditutup")
                    tokens.append(('STR', line[start:i]))
                    i += 1
                    continue

                if i + 1 < len(line) and line[i:i+2] in ['==','!=','<=','>=']:
                    tokens.append(line[i:i+2])
                    i += 2
                    continue

                if ch in "=+-*/()<>:":
                    tokens.append(ch)
                    i += 1
                    continue

                if ch.isdigit() or (ch == '.' and i+1 < len(line) and line[i+1].isdigit()):
                    start = i
                    has_dot = False

                    if ch == '.':
                        has_dot = True
                        i += 1

                    while i < len(line) and line[i].isdigit():
                        i += 1

                    if i < len(line) and line[i] == '.':
                        if has_dot:
                            self.raise_error("Angka tidak valid: terlalu banyak titik desimal")
                        has_dot = True
                        i += 1

                        if i < len(line) and line[i].isdigit():
                            while i < len(line) and line[i].isdigit():
                                i += 1

                    tokens.append(line[start:i])
                    continue

                if ch.isalpha() or ch == '_':
                    start = i
                    while i < len(line) and (line[i].isalnum() or line[i] == '_'):
                        i += 1
                    tokens.append(line[start:i])
                    continue

                self.raise_error(f"Token tidak sah: {ch}")

            for t in tokens:
                if isinstance(t, tuple):
                    yield t
                    continue
                if t in self.KEYWORDS:
                    yield ('KEY', t)
                elif t in self.OPERATORS:
                    yield ('OP', t)
                elif t in self.SYMBOLS:
                    yield ('SYM', t)
                elif t.replace('.', '', 1).isdigit():
                    yield ('NUM', float(t) if '.' in t else int(t))
                else:
                    yield ('IDF', t)

            yield ('NEWLINE',)

    def next_token(self):
        if self.returned_token is not None:
            tok = self.returned_token
            self.returned_token = None
            return tok

        try:
            return next(self.token_feed)
        except StopIteration:
            return None

    def return_token(self, tok):
        if tok:
            self.returned_token = tok


    # ===== PARSER =====
    def parse_program(self):
        statements = []
        tok = self.next_token()
        while tok:
            if tok[0] == 'NEWLINE':
                tok = self.next_token()
                continue
            self.return_token(tok)
            stmt = self.parse_statement()
            if stmt:
                statements.append(stmt)
            tok = self.next_token()
        return statements

    def parse_statement(self):
        tok = self.next_token()
        if tok is None or tok[0] == 'NEWLINE':
            return None
        if tok == ('KEY','cetak'):
            return self.parse_print()
        elif tok == ('KEY','if'):
            self.return_token(tok)
            return self.parse_if()
        elif tok[0] == 'IDF':
            self.return_token(tok)
            return self.parse_assignment()
        elif tok == ('KEY','end'):
            return None
        else:
            self.raise_error(f"Pernyataan tidak dikenal: {tok}")

    def parse_print(self):
        expr = self.parse_expression()
        if expr is None:
            self.raise_error("Diharapkan ekspresi setelah cetak")
        return PrintNode(expr)

    def parse_assignment(self):
        tok = self.next_token()
        name = tok[1]
        if self.next_token() != ('OP','='):
            self.raise_error("Diharapkan '='")
        expr = self.parse_expression()
        return AssignNode(name, expr)

    def parse_if(self):
        self.next_token()  # consume 'if'
        cond_tokens = []
        t = self.next_token()
        while t and t[0] != 'NEWLINE':
            cond_tokens.append(t)
            t = self.next_token()

        condition = self.parse_expression_from_tokens(cond_tokens)
        if_block = self.capture_block()

        elif_blocks = []
        while True:
            nxt = self.next_token()
            if nxt == ('KEY','elif'):
                cond_toks = []
                t = self.next_token()
                while t and t[0] != 'NEWLINE':
                    cond_toks.append(t)
                    t = self.next_token()
                elif_cond = self.parse_expression_from_tokens(cond_toks)
                elif_body = self.capture_block()
                elif_blocks.append((elif_cond, elif_body))
            else:
                self.return_token(nxt)
                break

        else_block = None
        nxt = self.next_token()
        if nxt == ('KEY','else'):
            if self.next_token()[0] != 'NEWLINE':
                self.raise_error("Diharapkan akhir baris setelah else")
            else_block = self.capture_block()
        else:
            self.return_token(nxt)

        if self.next_token() != ('KEY','end'):
            self.raise_error("Diharapkan 'end'")
        return IfNode(condition, if_block, elif_blocks, else_block)

    def capture_block(self):
        block = []
        nxt = self.next_token()
        while nxt and nxt not in [('KEY','elif'), ('KEY','else'), ('KEY','end')]:
            if nxt[0] == 'NEWLINE':
                nxt = self.next_token()
                continue
            self.return_token(nxt)
            stmt = self.parse_statement()
            if stmt:
                block.append(stmt)
            nxt = self.next_token()
        self.return_token(nxt)
        return block

    def parse_expression_from_tokens(self, tokens):
        old_feed = self.token_feed
        old_ret = self.returned_token

        def feed():
            for x in tokens:
                yield x
            yield ('NEWLINE',)

        self.token_feed = feed()
        self.returned_token = None
        expr = self.parse_expression()
        self.token_feed = old_feed
        self.returned_token = old_ret
        return expr


    # ===== EXPRESSION PARSER =====
    def parse_expression(self):

        def parse_factor():
            t = self.next_token()
            if t is None: return None
            if t[0] == 'NUM': return NumberNode(t[1])
            if t[0] == 'STR': return StringNode(t[1])
            if t[0] == 'IDF': return VarNode(t[1])
            if t == ('SYM','('):
                expr = parse_expr()
                if self.next_token() != ('SYM',')'):
                    self.raise_error("Diharapkan ')'")
                return expr
            self.return_token(t)
            return None

        def parse_term():
            left = parse_factor()
            while True:
                t = self.next_token()
                if t and t[0] == 'OP' and t[1] in ('*','/'):
                    op = t[1]
                    right = parse_factor()
                    left = BinOpNode(left, op, right)
                else:
                    self.return_token(t)
                    return left

        def parse_expr():
            left = parse_term()
            while True:
                t = self.next_token()
                if t and t[0] == 'OP' and t[1] in ('+','-'):
                    op = t[1]
                    right = parse_term()
                    left = BinOpNode(left, op, right)
                else:
                    self.return_token(t)
                    return left

        left = parse_expr()
        t = self.next_token()
        if t and t[0] == 'OP' and t[1] in ('==','!=','<','>','<=','>='):
            return BinOpNode(left, t[1], self.parse_expression())
        self.return_token(t)
        return left
    
    # ===== SEMANTIC CHECK =====
    def check_semantics(self, node):
        if isinstance(node, AssignNode):
            self.check_semantics(node.expr)
            # store type info
            if isinstance(node.expr, NumberNode):
                self.vars[node.name] = 'number'
            elif isinstance(node.expr, StringNode):
                self.vars[node.name] = 'string'
            elif isinstance(node.expr, VarNode):
                self.vars[node.name] = self.vars[node.expr.name]
            else:
                self.vars[node.name] = 'unknown'
            return

        if isinstance(node, VarNode):
            if node.name not in self.vars:
                self.raise_error(f"Variabel '{node.name}' digunakan sebelum diassign")
            return

        if isinstance(node, PrintNode):
            self.check_semantics(node.expr)
            return

        if isinstance(node, BinOpNode):
            self.check_semantics(node.left)
            self.check_semantics(node.right)
            # cek tipe operasi
            l_type = self.get_node_type(node.left)
            r_type = self.get_node_type(node.right)
            if node.op in ['+','-','*','/']:
                if (l_type == 'string' or r_type == 'string') and node.op != '+':
                    self.raise_error(f"Operator '{node.op}' tidak boleh untuk string")
                if node.op == '+' and ((l_type == 'string' and r_type != 'string') or (r_type == 'string' and l_type != 'string')):
                    self.raise_error(f"Operator '+' tidak boleh menggabungkan string dan number")
            return

        if isinstance(node, IfNode):
            self.check_semantics(node.condition)
            for cond, blk in node.elif_blocks:
                self.check_semantics(cond)
                for s in blk: self.check_semantics(s)
            if node.else_block:
                for s in node.else_block: self.check_semantics(s)
            for s in node.if_block:
                self.check_semantics(s)
            return

    def get_node_type(self, node):
        if isinstance(node, NumberNode):
            return 'number'
        if isinstance(node, StringNode):
            return 'string'
        if isinstance(node, VarNode):
            return self.vars[node.name]
        if isinstance(node, BinOpNode):
            l_type = self.get_node_type(node.left)
            r_type = self.get_node_type(node.right)
            if node.op in ['+','-','*','/']:
                if l_type == 'number' and r_type == 'number':
                    return 'number'
                if node.op == '+' and l_type == 'string' and r_type == 'string':
                    return 'string'
                return 'unknown'
        return 'unknown'
    
    # ===== EXECUTION =====
    def eval_expression(self,node):
        if isinstance(node, NumberNode): return node.value
        if isinstance(node, StringNode): return node.value
        if isinstance(node, VarNode): return self.vars[node.name]
        if isinstance(node, BinOpNode):
            l = self.eval_expression(node.left)
            r = self.eval_expression(node.right)
            if node.op == '+':
                if isinstance(l,str) or isinstance(r,str):
                    return str(l) + str(r)
                return l + r
            if node.op == '-': return l - r
            if node.op == '*': return l * r
            if node.op == '/': return l / r
            if node.op == '==': return l == r
            if node.op == '!=': return l != r
            if node.op == '<': return l < r
            if node.op == '>': return l > r
            if node.op == '<=': return l <= r
            if node.op == '>=': return l >= r

    def execute_statement(self,node):
        if isinstance(node, AssignNode):
            self.vars[node.name] = self.eval_expression(node.expr)
        elif isinstance(node, PrintNode):
            print(self.eval_expression(node.expr))
        elif isinstance(node, IfNode):
            if self.eval_expression(node.condition):
                for s in node.if_block: self.execute_statement(s)
            else:
                for cond, blk in node.elif_blocks:
                    if self.eval_expression(cond):
                        for s in blk: self.execute_statement(s)
                        return
                if node.else_block:
                    for s in node.else_block: self.execute_statement(s)


    # ===== PRINT AST =====
    def print_ast(self, node, indent=0):
        pad = "  " * indent

        if isinstance(node, list):
            print(f"{pad}[List]")
            for item in node:
                self.print_ast(item, indent + 1)
            return
        # tuple (used in elif_blocks)
        if isinstance(node, tuple):
            print(f"{pad}(Tuple)")
            print(f"{pad}  condition:")
            self.print_ast(node[0], indent + 2)
            print(f"{pad}  block:")
            self.print_ast(node[1], indent + 2)
            return

        if isinstance(node, ASTNode):
            print(f"{pad}{node.__class__.__name__}")
            for key, value in vars(node).items():
                print(f"{pad}  {key}:")
                self.print_ast(value, indent + 2)
            return

        print(f"{pad}{repr(node)}") 
    # ===== Pembangkit Kode Antara =====
    def generate_ir(self, node, ir, temp_count, label_count):

        # NUMBER
        if isinstance(node, NumberNode):
            return str(node.value)

        # STRING
        if isinstance(node, StringNode):
            return f'"{node.value}"'

        # VARIABLE
        if isinstance(node, VarNode):
            return node.name

        # BINOP
        if isinstance(node, BinOpNode):
            left = self.generate_ir(node.left, ir, temp_count, label_count)
            right = self.generate_ir(node.right, ir, temp_count, label_count)
            temp = f"t{temp_count[0]}"
            temp_count[0] += 1
            ir.append(f"{temp} = {left} {node.op} {right}")
            return temp

        # ASSIGN
        if isinstance(node, AssignNode):
            value = self.generate_ir(node.expr, ir, temp_count, label_count)
            ir.append(f"{node.name} = {value}")
            return

        # PRINT
        if isinstance(node, PrintNode):
            value = self.generate_ir(node.expr, ir, temp_count, label_count)
            ir.append(f"PRINT {value}")
            return

        # IF
        if isinstance(node, IfNode):
            cond = self.generate_ir(node.condition, ir, temp_count, label_count)

            label_else = f"L{label_count[0]}"
            label_end  = f"L{label_count[0] + 1}"
            label_count[0] += 2

            ir.append(f"IF_FALSE {cond} GOTO {label_else}")

            # IF block
            for s in node.if_block:
                self.generate_ir(s, ir, temp_count, label_count)

            ir.append(f"GOTO {label_end}")
            ir.append(f"{label_else}:")

            # ELIF blocks
            for cond_node, blk in node.elif_blocks:
                cond_val = self.generate_ir(cond_node, ir, temp_count, label_count)
                next_label = f"L{label_count[0]}"
                label_count[0] += 1

                ir.append(f"IF_FALSE {cond_val} GOTO {next_label}")
                for s in blk:
                    self.generate_ir(s, ir, temp_count, label_count)
                ir.append(f"GOTO {label_end}")
                ir.append(f"{next_label}:")

            # ELSE block
            if node.else_block:
                for s in node.else_block:
                    self.generate_ir(s, ir, temp_count, label_count)

            ir.append(f"{label_end}:")
            return
        # ===== OPTIMASI IR (LANGKAH 1) =====
    def optimize_ir(self, ir):

        optimized = []

        for line in ir:
            parts = line.split()

            # pola: t0 = NUM OP NUM
            if len(parts) == 5 and parts[1] == '=' and parts[2].isdigit() and parts[4].isdigit():

                left = int(parts[2])
                op = parts[3]
                right = int(parts[4])

                if op == '+': result = left + right
                elif op == '-': result = left - right
                elif op == '*': result = left * right
                elif op == '/': result = left / right
                else:
                    optimized.append(line)
                    continue

                # replace with folded value
                new_line = f"{parts[0]} = {int(result)}"
                optimized.append(new_line)
                continue

            optimized.append(line)

        return optimized
    
    
    # ===== GENERASI KODE OBJEK (MESIN REGISTER) =====
    def generate_object_code(self, ir):
        """
        Mesin semu berbasis 1 register (R0)
        Instruksi: LOAD, ADD, SUB, MUL, DIV, CONCAT, STORE, OUT, JZ, JMP, LABEL
        """

        for line in ir:
            parts = line.split()

            # LABEL: "L0:"
            if line.endswith(":"):
                label = parts[0][:-1]
                print(f"LABEL {label}")
                continue

            # PRINT: "PRINT x"
            if parts[0] == "PRINT":
                val = parts[1]
                print(f"LOAD {val}, R0")
                print("OUT")
                continue

            # IF_FALSE cond GOTO L0
            if parts[0] == "IF_FALSE":
                cond = parts[1]
                label = parts[3]
                print(f"LOAD {cond}, R0")
                print(f"JZ {label}")
                continue

            # GOTO L1
            if parts[0] == "GOTO":
                label = parts[1]
                print(f"JMP {label}")
                continue

            # ASSIGNMENT
            if len(parts) >= 3 and parts[1] == '=':
                dest = parts[0]
                expr = parts[2:]

                # Kasus 1 operand: x = 5, x = t0, x = "Raihana"
                if len(expr) == 1:
                    src = expr[0]
                    print(f"LOAD {src}, R0")
                    print(f"STORE R0, {dest}")
                    continue

                # Kasus operasi biner: t1 = a + b
                if len(expr) == 3:
                    left = expr[0]
                    op = expr[1]
                    right = expr[2]

                    print(f"LOAD {left}, R0")

                    if op == '+':
                        # Jika salah satu operand string, CONCAT
                        if left.startswith('"') or right.startswith('"'):
                            print(f"CONCAT {right}, R0")
                        else:
                            print(f"ADD {right}, R0")
                    elif op == '-':
                        print(f"SUB {right}, R0")
                    elif op == '*':
                        print(f"MUL {right}, R0")
                    elif op == '/':
                        print(f"DIV {right}, R0")

                    print(f"STORE R0, {dest}")
                    continue
                continue

    
    # ===== RUN =====
    def run(self):
        print("="*60)
        print("TAHAP 1: PARSING")
        ast = self.parse_program()
        print("Parsing berhasil")

        print("="*60)
        print("POHON AST")
        self.print_ast(ast)
 
        print("="*60)
        print("TAHAP 2: SEMANTIC CHECKING")
        for stmt in ast:
            self.check_semantics(stmt)
        print("Semantic OK")
    
        ir = []
        temp_count = [0]
        label_count = [0]
        
        for stmt in ast:
            self.generate_ir(stmt, ir, temp_count, label_count)
        
        print("="*60)
        print("TAHAP 3: INTERMEDIATE CODE (Sebelum Optimasi)")
        for line in ir:
            print(line)
        optimized_ir = self.optimize_ir(ir)

        print("="*60)
        print("TAHAP 4: OPTIMIZED INTERMEDIATE CODE")
        for line in optimized_ir:
            print(line)

        print("="*60)
        print("TAHAP 5: GENERASI KODE OBJEK")
        self.generate_object_code(optimized_ir)
   
        print("="*60)
        print("TAHAP 6: EKSEKUSI")
        for stmt in ast:
            self.execute_statement(stmt)


if __name__=='__main__':
    if len(sys.argv) < 2:
        print("Usage: python bahasaku.py <file.bk>")
        sys.exit(1)
    with open(sys.argv[1],'r') as f:
        program = BahasaKu(f.read())
        program.run()

**Langkah 4:** Buat program untuk uji coba kode program tersebut dan beri nama dengan test.bhs

x = 1 * 2
y = 3
b = (x + y)*4
cetak b

**Langkah 5:** Jalankan program dengan command prompt, posisikan folder BahasaKu.py dan test.bhs dalam 1 folder selanjutnya ketikan cmd pada address bar lalu tekan Enter pada keyboard, akan tampil jendela command prompt.
**Langkah 6:** Pada jendela command prompt ketikan `python Bahasaku.py test.bhs` lalu tekan Enter untuk menjalankan program.
Berikut adalah outpunya

============================================================
TAHAP 1: PARSING
Parsing berhasil
============================================================
POHON AST
[List]
  AssignNod============================================================
TAHAP 1: PARSING
Parsing berhasil
============================================================
POHON AST
[List]
  AssignNode
    name:
      'x'
    expr:
      BinOpNode
        left:
          NumberNode
            value:
              1
        op:
          '*'
        right:
          NumberNode
            value:
              2
  AssignNode
    name:
      'y'
    expr:
      NumberNode
        value:
          3
  AssignNode
    name:
      'b'
    expr:
      BinOpNode
        left:
          BinOpNode
            left:
              VarNode
                name:
                  'x'
            op:
              '+'
            right:
              VarNode
                name:
                  'y'
        op:
          '*'
        right:
          NumberNode
            value:
              4
  PrintNode
    expr:
      VarNode
        name:
          'b'
============================================================
TAHAP 2: SEMANTIC CHECKING
Semantic OK
============================================================
TAHAP 3: INTERMEDIATE CODE (Sebelum Optimasi)
t0 = 1 * 2
x = t0
y = 3
t1 = x + y
t2 = t1 * 4
b = t2
PRINT b
============================================================
TAHAP 4: OPTIMIZED INTERMEDIATE CODE
t0 = 2
x = t0
y = 3
t1 = x + y
t2 = t1 * 4
b = t2
PRINT b
============================================================
TAHAP 5: GENERASI KODE OBJEK
LOAD 2, R0
STORE R0, t0
LOAD t0, R0
STORE R0, x
LOAD 3, R0
STORE R0, y
LOAD x, R0
ADD y, R0
STORE R0, t1
LOAD t1, R0
MUL 4, R0
STORE R0, t2
LOAD t2, R0
STORE R0, b
LOAD b, R0
OUT
============================================================
TAHAP 6: EKSEKUSI
20


**Penjelasan kode program**

Program BahasaKu mengimplementasikan proses generasi kode objek berdasarkan Intermediate Representation (IR) yang dihasilkan dari Abstract Syntax Tree (AST) program sumber. Pada BahasaKu, setiap pernyataan dalam kode sumber terlebih dahulu diterjemahkan menjadi bentuk IR tiga-alamat (three-address code), seperti t0 = x + y atau PRINT b. Representasi ini digunakan sebagai jembatan antara kode tingkat tinggi dan instruksi mesin.

Program ini terdiri dari beberapa komponen utama yang bekerja berurutan, dimulai dari pembentukan AST, pembuatan IR, optimasi, hingga akhirnya menghasilkan kode objek. Proses optimasi dilakukan melalui fungsi optimize_ir, yang mendeteksi operasi aritmatika dengan konstanta—misalnya 1 * 2—dan menggantinya dengan hasil akhirnya. Teknik ini dikenal sebagai constant folding (penggabungan konstanta), yang merupakan bentuk optimasi lokal karena hanya bekerja pada satu instruksi tanpa melihat keseluruhan program.

Setelah IR dioptimasi, langkah selanjutnya adalah generasi kode objek melalui fungsi generate_object_code. Pada tahap ini, setiap instruksi IR diterjemahkan menjadi instruksi mesin semu yang menyerupai assembly, seperti LOAD, ADD, MUL, STORE, dan OUT. Proses ini dilakukan secara linear, artinya instruksi dihasilkan dalam urutan yang sama seperti aliran program tanpa penjadwalan atau pengalokasian register yang kompleks.
OUTPUT:

LOAD 2, R0
STORE R0, t0
LOAD t0, R0
STORE R0, x
LOAD 3, R0
STORE R0, y
LOAD x, R0
ADD y, R0
STORE R0, t1
LOAD t1, R0
MUL 4, R0
STORE R0, t2
LOAD t2, R0
STORE R0, b
LOAD b, R0
OUT

Output dari program di atas merupakan serangkaian instruksi mesin semu yang menggambarkan tahap akhir proses kompilasi, yaitu generasi kode objek. Pada tahap ini, representasi menengah program (IR yang dihasilkan dari AST) diterjemahkan menjadi instruksi tingkat rendah yang dapat dieksekusi oleh mesin virtual BahasaKu.

Program sumber yang dikompilasi adalah:

x = 1 * 2
y = 3
b = (x + y) * 4
cetak b

Generasi kode objek menerjemahkan perhitungan tersebut menjadi instruksi langkah-demi-langkah yang menunjukkan bagaimana mesin menghitung nilai akhir. Setiap instruksi mewakili proses komputasi nyata yang dilakukan oleh mesin, seperti memuat nilai, melakukan operasi aritmatika, menyimpan hasil, dan mencetak output.

Melalui instruksi tersebut, mesin:

1. Menghitung 1 * 2 dan menyimpannya sebagai x
2. Menetapkan nilai 3 ke y
3. Menghitung (x + y) * 4 dan menyimpannya sebagai b
4. Mencetak nilai b (hasil akhirnya 20)

Instruksi-instruksi berikut menunjukkan bagaimana nilai b dihitung dan dicetak:
1. LOAD 2, R0
Instruksi ini memuat nilai konstanta 2 ke dalam register R0 (register kerja utama).
2. STORE R0, t0
Nilai 2 di R0 disimpan ke variabel sementara t0.
Ini adalah hasil dari ekspresi 1 * 2 yang sudah dioptimasi menjadi 2.
3. LOAD t0, R0
Memuat kembali nilai t0 (yaitu 2) ke register R0.
4. STORE R0, x
Menyimpan nilai pada R0 ke variabel x.
Artinya ekspresi x = 1 * 2 sudah selesai dihitung.
5. LOAD 3, R0
Memuat konstanta 3 ke register R0.
6. STORE R0, y
Nilai pada R0 (3) disimpan ke variabel y, sesuai pernyataan y = 3.
7. LOAD x, R0
Memuat nilai x (2) dari memori ke R0 sebagai persiapan operasi berikutnya.
8. ADD y, R0
Menambahkan nilai y (3) ke R0.
R0 berubah dari 2 → 5.
Ini adalah hasil operasi x + y.
9. STORE R0, t1
Menyimpan hasil tadi (5) ke variabel sementara t1.
10. LOAD t1, R0
Memuat nilai t1 (5) kembali ke R0.
11. MUL 4, R0
Mengalikan R0 dengan 4, menghasilkan 5 * 4 = 20.
12. STORE R0, t2
Menyimpan hasil perkalian (20) ke variabel sementara t2.
13. LOAD t2, R0
Memuat nilai t2 (20) ke R0.
14. STORE R0, b
Menyimpan nilai R0 ke variabel b.
Dengan ini ekspresi b = (x + y) * 4 selesai dihitung.
15. LOAD b, R0
Memuat nilai b (20) ke R0 untuk dicetak.
16. OUT
Instruksi untuk mencetak isi register R0 ke layar.
</div>