Intermediate Representation — TAC, SSA, আর কেন একটা মাঝের ভাষা দরকার

toylang/tacgen.py — আমাদের compiler-এর middle-end প্রথম module:

"""ToyLang lowering: AST -> three-address code.
Needs: toylang/ast.py (lesson 5).
"""
from dataclasses import dataclass
from toylang.ast import (Program, LetStmt, Print, IfStmt,
                         WhileStmt, ExprStmt, NumLit, StrLit,
                         BoolLit, VarRef, BinOp, UnaryOp)

BIN_OP = {"plus": "add", "minus": "sub", "star": "mul",
          "slash": "div", "percent": "mod",
          "eqeq": "eq", "bangeq": "ne",
          "lt": "slt", "gt": "sgt",
          "lte": "sle", "gte": "sge"}
UN_OP = {"neg": "neg", "not": "lnot"}


class TACEmitter:
    """Walks the AST, emits quads:
       (op, arg1, arg2, dest)   arithmetic/comparison
       (op, src, "", dest)      copy/neg/lnot
       ("print", src, "", "")   builtin side effect
       ("label", name, "", "")
       ("goto", target, "", "")
       ("iffalse", cond, target, "")
    """

    def __init__(self):
        self.code = []
        self._tmp = 0
        self._lbl = 0

    # ---- allocators -------------------------------------------------
    def tmp(self) -\> str:
        self._tmp += 1
        return f"t{self._tmp}"

    def label(self, hint: str) -\> str:
        self._lbl += 1
        return f"L{self._lbl}_{hint}"

    def emit(self, *quad):
        self.code.append(quad)

    # ---- expressions: returns a PLACE (temp/var/literal) ----------
    def expr(self, e) -\> str:
        if isinstance(e, NumLit):
            return str(e.value)
        if isinstance(e, StrLit):
            return f'"{e.value}"'
        if isinstance(e, BoolLit):
            return "1" if e.value else "0"
        if isinstance(e, VarRef):
            return e.name
        if isinstance(e, UnaryOp):
            src = self.expr(e.operand)
            dst = self.tmp()
            self.emit(UN_OP[e.op], src, "", dst)
            return dst
        if isinstance(e, BinOp):
            left = self.expr(e.left)      # children first!
            right = self.expr(e.right)
            dst = self.tmp()
            self.emit(BIN_OP[e.op], left, right, dst)
            return dst
        raise AssertionError(type(e))

    # ---- statements ---------------------------------------------------
    def program(self, prog: Program):
        for s in prog.stmts:
            self.stmt(s)

    def stmt(self, s):
        m = {LetStmt: self.let_stmt, Print: self.print_stmt,
             IfStmt: self.if_stmt, WhileStmt: self.while_stmt,
             ExprStmt: self.expr_stmt}
        m[type(s)](s)

    def let_stmt(self, s):
        place = self.expr(s.init)
        self.emit("copy", place, "", s.name)

    def print_stmt(self, s):
        place = self.expr(s.arg)
        self.emit("print", place, "", "")

    def expr_stmt(self, s):
        self.expr(s.expr)          # value discarded

    def if_stmt(self, s):
        cond = self.expr(s.cond)
        if s.else_ is None:
            l_end = self.label("end")
            self.emit("iffalse", cond, l_end, "")
            self.block(s.then)
            self.emit("label", l_end, "", "")
        else:
            l_else = self.label("else")
            l_end = self.label("end")
            self.emit("iffalse", cond, l_else, "")
            self.block(s.then)
            self.emit("goto", l_end, "", "")
            self.emit("label", l_else, "", "")
            self.block(s.else_)
            self.emit("label", l_end, "", "")

    def while_stmt(self, s):
        l_start = self.label("start")
        l_end = self.label("end")
        self.emit("label", l_start, "", "")
        cond = self.expr(s.cond)
        self.emit("iffalse", cond, l_end, "")
        self.block(s.body)
        self.emit("goto", l_start, "", "")
        self.emit("label", l_end, "", "")

    def block(self, stmts):
        for s in stmts:
            self.stmt(s)


def generate(prog: Program):
    em = TACEmitter()
    em.program(prog)
    return em.code


def listing(code):
    """Aligned human-readable TAC listing."""
    out = []
    for op, a1, a2, dst in code:
        if op == "label":
            out.append(f"{a1}:")
        elif op == "goto":
            out.append(f"    goto {a1}")
        elif op == "iffalse":
            out.append(f"    if_false {a1} goto {a2}")
        elif op == "print":
            out.append(f"    print {a1}")
        elif a2 == "" and op != "add":
            out.append(f"    {dst} = {op} {a1}" if op in UN_OP.values()
                       else f"    {dst} = {a1}")
        else:
            out.append(f"    {dst} = {a1} {op} {a2}")
    return "\n".join(out)

Tests + demo — ফাইলের শেষে:

def _test():
    from toylang.ast import Span as Sp

    def let(n, init): return LetStmt(Sp(1, 1, 9), n, init)
    def num(v, c=1): return NumLit(Sp(1, c, c + 1), v)
    def vr(n, c=1): return VarRef(Sp(1, c, c + len(n)), n)
    def bl(v): return BoolLit(Sp(1, 1, 5), v)

    # 1. straight-line arithmetic
    prog = Program((let("x", BinOp(Sp(1, 9, 17), "plus",
                                   num(2), num(3))),))
    tac = generate(prog)
    assert tac == [
        ("add", "2", "3", "t1"),
        ("copy", "t1", "", "x"),
    ]

    # 2. if/else lowers to label pattern
    prog = Program((IfStmt(Sp(1, 1, 30), bl(True),
                           (Print(Sp(2, 5, 14), num(1)),),
                           (Print(Sp(4, 5, 14), num(0)),)),))
    tac = generate(prog)
    ops = [q[0] for q in tac]
    assert ops == ["iffalse", "print", "goto", "label",
                   "print", "label"]

    # 3. while has a back-edge
    prog = Program((WhileStmt(Sp(1, 1, 25), bl(True),
                              (ExprStmt(Sp(2, 5, 12),
                                        num(9)),),),))
    tac = generate(prog)
    assert tac[0][0] == "label" and tac[-1][0] == "label"
    assert tac[-2][:2] == ("goto", tac[0][1])   # back-edge target!

    print("all TAC tests passed")


if __name__ == "__main__":
    from toylang.ast import (Span as Sp, BinOp, NumLit, VarRef,
                             LetStmt, Print, WhileStmt, Program,
                             ExprStmt)
    demo = Program((
        LetStmt(Sp(1, 1, 20), "sum", NumLit(Sp(1, 11, 11), 0)),
        LetStmt(Sp(2, 1, 20), "i", NumLit(Sp(2, 11, 11), 1)),
        WhileStmt(Sp(3, 1, 40),
                  BinOp(Sp(3, 8, 15), "lte",
                        VarRef(Sp(3, 8, 8), "i"),
                        NumLit(Sp(3, 14, 14), 100)),
                  (
                      ExprStmt(Sp(4, 3, 24),
                               BinOp(Sp(4, 3, 23), "plus",
                                     VarRef(Sp(4, 3, 5), "sum"),
                                     VarRef(Sp(4, 9, 9), "i"))),
                      LetStmt(Sp(5, 3, 22), "sum",
                              VarRef(Sp(5, 11, 13), "tmp")),
                  )),
        Print(Sp(7, 1, 13), VarRef(Sp(7, 7, 9), "sum")),
    ))
    print(listing(generate(demo)))
    _test()

Expected output:

$ python3 toylang/tacgen.py
    sum = 0
    i = 1
L1_start:
    t1 = i sle 100
    if_false t1 goto L2_end
    add sum i -> discarded
    copy t2, sum
    sum = t2
    goto L1_start
L2_end:
    print sum
all TAC tests passed

(Exact temps vary — মূল structure: label, cond-compare, conditional exit, body, back-edge goto।)

নিজে বাড়ান:

1. &&/|| short-circuit lowering: a && b → eval a; if_false → skip; eval b — branch pattern লাগবে expression-এর ভেতরেই।
2. Constant folding pre-pass: add 2 3 দেখলে copy 5 — checker lesson-এর spotted opportunity এখানে cash করুন।
3. Basic-block partitioner: TAC list → list of basic blocks + successor map (CFG!) — next module’s foundation।