ইন্টারমিডিয়েট রিপ্রেজেন্টেশন ও থ্রি-অ্যাড্রেস কোড

১ · Intermediate Representation কী ও কেন দরকার

Intermediate RepresentationIntermediate Representation (IR)সোর্স-ভাষার AST ও টার্গেট মেশিন কোডের মাঝামাঝি একটি রূপ — সোর্সের চেয়ে সরল ও উদার, কিন্তু নির্দিষ্ট টার্গেট মেশিন থেকে মোটামুটি স্বাধীন। (IR) হলো প্রোগ্রামের এমন একটি রূপ যা হাই-লেভেল সোর্স-ভাষার AST (M5-এর আউটপুট) এবং লো-লেভেল টার্গেট মেশিন কোডের (Computer Architecture কোর্সের ISA, M12/L52-এর চূড়ান্ত টার্গেট) ঠিক মাঝামাঝি — L05-এর পাইপলাইন-ওভারভিউয়ের ৪র্থ ধাপের সুনির্দিষ্ট বাস্তবায়ন, যা এতদিন পিছিয়ে রাখা হয়েছিল যতক্ষণ না দরকারি AST/সিমান্টিক-অ্যানালাইসিসের ভিত্তি (M5-M7) প্রস্তুত হয়।

IR কেন দরকার — L05-এর front-end/back-end বিভাজনের সুবিধা এখন বাস্তবে দেখা যাক: IR ইচ্ছাকৃতভাবে সোর্স ভাষার চেয়ে সরল ও অভিন্ন (optimize করা সহজ, M12/L53) কিন্তু কোনো নির্দিষ্ট টার্গেট মেশিন থেকে মোটামুটি স্বাধীন — একটি একক IR নীতিগতভাবে একাধিক ভিন্ন টার্গেট আর্কিটেকচারে অনুবাদযোগ্য। এটাই সরাসরি বাস্তব-জগতের প্রাসঙ্গিকতা — LLVM-এর মতো কম্পাইলার ইনফ্রাস্ট্রাকচার (L05-এ উল্লেখিত) ঠিক এভাবেই একাধিক সোর্স-ভাষা/টার্গেট-মেশিন কম্বিনেশন সমর্থন করে।

২ · থ্রি-অ্যাড্রেস কোড (3AC)

থ্রি-অ্যাড্রেস কোডThree-Address Code (3AC)একটি IR ফর্ম যেখানে প্রতিটি ইনস্ট্রাকশনে সর্বোচ্চ তিনটি অপারেন্ড/অ্যাড্রেস থাকে — সাধারণত result = operand1 OP operand2 আকারে। হলো এই কোর্সের ব্যবহৃত স্ট্যান্ডার্ড, কংক্রিট IR ফর্ম — এর সংজ্ঞায়ক বৈশিষ্ট্য: প্রতিটি ইনস্ট্রাকশনে সর্বোচ্চ তিনটি অপারেন্ড/অ্যাড্রেস থাকে — সাধারণত result = operand1 OP operand2 আকারে (এক ইনস্ট্রাকশনে ঠিক একটি অপারেশন, নেস্টেড সোর্স-এক্সপ্রেশনের বিপরীতে যেখানে অনেকগুলো অপারেশন একসাথে গাঁথা থাকতে পারে) — একটি সত্যিকারের সরল, অভিন্ন ইনস্ট্রাকশন আকৃতি, নেস্টেড সোর্স এক্সপ্রেশনের চেয়ে — সরাসরি motivation: সরল ইনস্ট্রাকশন পরবর্তী ধাপগুলোর (অপ্টিমাইজেশন, কোড জেনারেশন) জন্য যান্ত্রিকভাবে বিশ্লেষণ ও রূপান্তর করা সহজ করে তোলে।

৩ · ওয়ার্কড এক্সাম্পল — (a + b) * (c - d)

নেস্টেড সোর্স এক্সপ্রেশন (a + b) * (c - d)-কে 3AC-তে অনুবাদ করা যাক — প্রতিটি ইন্টারমিডিয়েট উপ-ফলাফলের জন্য একটি টেম্পোরারি ভ্যারিয়েবল চালু করে:

$$t_1 = a + b \qquad t_2 = c - d \qquad t_3 = t_1 \times t_2$$

সোর্স এক্সপ্রেশনে ঠিক ৩টি অপারেশন (একটি যোগ, একটি বিয়োগ, একটি গুণ) — এবং এখানে ঠিক ৩টি থ্রি-অ্যাড্রেস ইনস্ট্রাকশন তৈরি হলো, একটি সরাসরি এক-এক মিল যা স্পষ্টভাবে উল্লেখযোগ্য।

৪ · কোড: generate_3ac ও নিজে-এক্সিকিউট করে যাচাই

নিচের কোড সেলে generate_3ac একটি এক্সপ্রেশন AST (নেস্টেড টাপল, M5/L22-এর পার্স-ট্রি কাঠামোর পুনর্ব্যবহার) recursively হেঁটে 3AC ইনস্ট্রাকশন emit করে। এরপর execute_3ac সেই জেনারেটেড কোডটিই a, b, c, d-এর concrete মান দিয়ে চালিয়ে ফলাফল সরাসরি মূল এক্সপ্রেশনের সাথে মিলিয়ে দেখায়।

def generate_3ac(node, temp_counter):
    """একটি এক্সপ্রেশন AST (নেস্টেড টাপল) থেকে থ্রি-অ্যাড্রেস কোড emit করে।

    node আকৃতি: ("var", নাম)  অথবা  ("op", অপারেটর, বাম_নোড, ডান_নোড)
    রিটার্ন করে: (এই সাব-এক্সপ্রেশনের ফলাফল রাখা অপারেন্ড, ইনস্ট্রাকশন-লিস্ট, পরবর্তী temp_counter)
    """
    if node[0] == "var":
        return node[1], [], temp_counter

    _, op, left, right = node
    left_operand, left_instrs, temp_counter = generate_3ac(left, temp_counter)
    right_operand, right_instrs, temp_counter = generate_3ac(right, temp_counter)

    temp_name = f"t{temp_counter}"
    temp_counter += 1
    this_instr = (temp_name, left_operand, op, right_operand)

    all_instrs = left_instrs + right_instrs + [this_instr]
    return temp_name, all_instrs, temp_counter


# সোর্স এক্সপ্রেশন: (a + b) * (c - d)
ast = ("op", "*",
       ("op", "+", ("var", "a"), ("var", "b")),
       ("op", "-", ("var", "c"), ("var", "d")))

final_temp, instructions, _ = generate_3ac(ast, temp_counter=1)

print("জেনারেটেড থ্রি-অ্যাড্রেস কোড:")
for target, op1, op, op2 in instructions:
    print(f"  {target} = {op1} {op} {op2}")

expected = [("t1", "a", "+", "b"), ("t2", "c", "-", "d"), ("t3", "t1", "*", "t2")]
assert instructions == expected
print(f"\nহাতে-ডেরাইভ করা প্রত্যাশিত 3AC-এর সাথে হুবহু মিলেছে: {instructions == expected}")


def execute_3ac(instructions, env):
    """জেনারেটেড 3AC ইনস্ট্রাকশনগুলো ক্রমান্বয়ে এক্সিকিউট করে -- eval/exec ছাড়াই।"""
    env = dict(env)
    for target, op1, op, op2 in instructions:
        v1, v2 = env[op1], env[op2]
        if op == "+":
            env[target] = v1 + v2
        elif op == "-":
            env[target] = v1 - v2
        elif op == "*":
            env[target] = v1 * v2
        elif op == "/":
            env[target] = v1 / v2
        else:
            raise ValueError(f"অজানা অপারেটর: {op}")
    return env[final_temp]


sample_values = {"a": 3, "b": 5, "c": 10, "d": 4}
result_from_3ac = execute_3ac(instructions, sample_values)
direct_result = (sample_values["a"] + sample_values["b"]) * (sample_values["c"] - sample_values["d"])

print(f"\nনমুনা মান: {sample_values}")
print(f"3AC এক্সিকিউট করে ফলাফল      = {result_from_3ac}")
print(f"সরাসরি এক্সপ্রেশন ইভালুয়েট করে ফলাফল = {direct_result}")
assert result_from_3ac == direct_result
print(f"যাচাই: দুটো ফলাফল অভিন্ন -> {result_from_3ac == direct_result}")