এই পর্বে যা শিখবেন
- Compiler-এর প্রতিটি ধাপের ইনপুট, আউটপুট আর মাঝের data structure নাম ধরে বলতে পারা
- ধাপ (phase) আর pass-এর পার্থক্য, আর front, middle, back end ভাগের হিসাব (m + n)
- সত্যিকারের Clang-এর token dump, AST dump, LLVM IR, assembly আর symbol table পড়তে পারা
- যেকোনো error দেখে বলা, কোন ধাপ সেটি ধরেছে, আর কোন ভুল কোনো static ধাপই ধরতে পারে না
- “প্রতিটি ধাপ অর্থ রাখলে পুরো compiler অর্থ রাখে” দাবিটি প্রমাণ করা, আর optimizer-এর ভুল ধরার উপায় জানা
১ · রেস্তোরাঁর রান্নাঘর — কেন compiler ধাপে ধাপে কাজ করে
পুরান ঢাকার একটি ব্যস্ত রেস্তোরাঁর কথা ভাবুন। ওয়েটার টেবিল থেকে অর্ডার শুনে একটি স্লিপে লেখেন। ক্যাশ কাউন্টার স্লিপটি পড়ে দেখেন: সব আইটেম মেনুতে আছে তো, দাম ঠিক তো? তারপর রান্নাঘরের প্রধান স্লিপটিকে ভাগ করে দেন: কাবাব যায় শিকের চুলায়, ভাত যায় ডেকচিতে। সবশেষে পরিবেশনকারী প্লেট সাজিয়ে টেবিলে দেন। কেউ একাই সব কাজ করেন না; প্রত্যেকে আগের জনের হাতে পাওয়া জিনিস একটু বদলে পরের জনকে দেন।
অর্ডার স্লিপ হলো compiler-এর মাঝের ডেটা। ওয়েটারের হাতের লেখা পড়ে শব্দ চেনা হলো lexer-এর কাজ; “২ প্লেট কাচ্চি, ১টি বোরহানি” বাক্যটির গঠন বোঝা parser-এর কাজ; মেনুতে আইটেম আছে কি না আর পরিমাণ সংখ্যায় লেখা কি না দেখা semantic analysis; রান্নাঘরের প্রধানের ভাগ-বাটোয়ারা হলো IR আর optimization; আর নির্দিষ্ট চুলার জন্য রেসিপি লেখা হলো code generation. একটি ধাপে ভুল ধরা পড়লে স্লিপ আর সামনে যায় না।
আগের পর্বে, পর্ব ০৪-এ (অনুবাদক — compiler, interpreter, transpiler আর JIT), compiler-কে বাইরে থেকে দেখেছিলেন: ইনপুট একটি program, আউটপুট আরেকটি program, আর শর্ত হলো অর্থ বদলানো চলবে না। এই পর্বে compiler-এর ঢাকনা খুলব। C-র toolchain-এর চার ধাপ (preprocess, compile, assemble, link) আপনি C প্রোগ্রামিং কোর্সের পর্ব ০৩-এ দেখে থাকতে পারেন; সেখানে “compile” ছিল একটি বাক্স। আজ সেই বাক্সের ভেতরের ধাপগুলো দেখব।
একটি ধাপ হলো compiler-এর একটি যুক্তিগত কাজ, যার একটি নির্দিষ্ট ইনপুট-রূপ আর আউটপুট-রূপ আছে। এই রূপগুলোকে আমরা ভাষা হিসেবেই দেখব: token-এর সারিও একটি ভাষা, AST-ও একটি ভাষা, IR-ও একটি ভাষা। তাহলে পুরো compiler হলো কয়েকটি ছোট অনুবাদকের শিকল।
ধরুন L0 source language আর Ln target language. মাঝে L1, …, Ln−1 কয়েকটি মাঝের রূপ। ধাপ Pi একটি function, যা Li−1-এর একটি program নেয় আর হয় Li-এর একটি program দেয়, নয়তো error দিয়ে থেমে যায়। তখন compiler
C = Pn ∘ Pn−1 ∘ … ∘ P1.
এখানে ∘ মানে function জোড়া দেওয়া: (g ∘ f)(x) = g(f(x)), অর্থাৎ আগে f, তারপর g. ধাপ Pi সঠিক বলব, যদি সে যে program গ্রহণ করে তার প্রতিটির জন্য ⟦Pi(p)⟧Li = ⟦p⟧Li−1. ⟦p⟧L মানে ভাষা L-এর নিয়মে p-এর অর্থ, অর্থাৎ কোন ইনপুটে কী আউটপুট বা কোন runtime error.
এই সংজ্ঞাটি তিনটি কারণে কাজের। এক, প্রতিটি ধাপ আলাদা করে লেখা, পরীক্ষা আর বদলানো যায়। দুই, প্রতিটি ধাপের ভুলের ধরন আলাদা, তাই কোন ধাপ error দিল দেখেই ভুলের ধরন বোঝা যায়। তিন, অংশ ৭-এ দেখবেন, প্রতিটি ধাপ সঠিক হলে পুরো শিকলও সঠিক, আর এই সরল ফলের ওপরেই পৃথিবীর একমাত্র বড় মাপের প্রমাণিত C compiler দাঁড়িয়ে আছে।
শব্দের ব্যবহার: এই কোর্সে compiler-এর একটি কাজকে বলব “ধাপ” (phase). “Pass” মানে program-এর পুরো একটি রূপের ওপর দিয়ে compiler-এর একবার হেঁটে যাওয়া; অংশ ৭-এ দুটির পার্থক্য পরিষ্কার হবে। “পর্ব” শব্দটি শুধু এই কোর্সের lesson-এর জন্য।
২ · ধাপগুলোর মানচিত্র — কে কী নেয়, কী দেয়
নিচের ছবিতে একটি সাধারণ compiler-এর পুরো পথ। বাক্সগুলো ধাপ, আর তীরের পাশের লেখা হলো এক ধাপ থেকে পরের ধাপে যাওয়া ডেটা। বাক্সের রং দেখায় কোন ধাপ front end (নীল), middle end (হলুদ) আর back end (সবুজ)-এর অংশ।
ছবি ৫.১ — compiler-এর ধাপ আর তাদের মাঝের ডেটা
ওপর থেকে নিচে পড়ুন: প্রতিটি তীরের পাশে সেই data structure, যা এক ধাপ পরের ধাপের হাতে দেয়।
এবার প্রতিটি ধাপকে একটি টেবিলে রাখি। শেষ কলামটি বলে, এই কোর্সে Haat-এর জন্য সেই ধাপটি কোন পর্বে বানাবেন।
| ধাপ | ইনপুট → আউটপুট | মূল data structure | কী ধরনের ভুল ধরে | Haat-এ |
|---|---|---|---|---|
| Lexical analysis (lexer) | অক্ষর → token | Token(kind, text, line, col) | অচেনা অক্ষর, শেষ না হওয়া string | পর্ব ৪৬ |
| Syntax analysis (parser) | token → AST | গাছ: Binary, Call, If … | ব্যাকরণ: ; নেই, বন্ধনী মেলেনি | পর্ব ৪৭–৫০ |
| Name resolution | AST → AST + নামের সংযোগ | symbol table, scope-এর শিকল | অঘোষিত নাম, একই scope-এ দুবার ঘোষণা | পর্ব ৫১ |
| Type checking | AST → type-সহ AST | type-এর পরিবেশ Γ | Int-এর জায়গায় Bool, ভুল argument সংখ্যা | পর্ব ৫২–৫৪ |
| IR generation | AST → IR | three-address code, CFG, bytecode | (ভুল ধরে না; শুধু নামায়) | পর্ব ৫৫, ৫৮, ৬২ |
| Optimization | IR → IR | SSA, dataflow-এর তথ্য | (warning দিতে পারে, যেমন অব্যবহৃত মান) | পর্ব ৬৩–৬৮ |
| Code generation | IR → assembly | instruction-এর তালিকা, register map | (সাধারণত কিছু না) | পর্ব ৬৯–৭৩ |
| Assembler, linker | assembly → object file → executable | symbol আর relocation-এর তালিকা | অনুপস্থিত বা দুবার সংজ্ঞায়িত symbol | পর্ব ৭৪ |
খেয়াল করুন, ভুল ধরার কাজ প্রায় সবটাই প্রথম দিকের ধাপে। এর কারণ সহজ: কোনো program-এর ভুল যত তাড়াতাড়ি ধরা যায়, ততই ভালো, আর পরের ধাপগুলো ধরে নেয় যে তাদের ইনপুট ইতিমধ্যে যাচাই-করা। Optimizer যদি প্রতিবার নিজে যাচাই করত “এই নামটি ঘোষিত তো?”, তাহলে একই কাজ দুবার হতো। তত্ত্বের দিকটি, অর্থাৎ token-কে regular expression আর automaton দিয়ে বর্ণনা করা, গণনার তত্ত্ব কোর্সের পর্ব ২২-এ (Lexical analysis) আছে; grammar আর parsing-এর তত্ত্ব সেই কোর্সের মডিউল ৭-এ। এখানে আমরা সেই তত্ত্ব দিয়ে জিনিস বানাব।
৩ · একটি Haat statement, প্রতিটি ধাপে
এবার একটি ছোট Haat program নিয়ে পুরো পথটি হাঁটি। ফাইল order.haat:
// বাজারঘর: একটি অর্ডার
let qty = 2;
print(qty * 520 + 60);
নিচের stepper-এর প্রতিটি প্যানেলের লেখা কোর্সের Haat reference বাস্তবায়নের সত্যিকারের আউটপুট (CPython 3.14.4-এ চালানো): python haat.py tokens order.haat, তারপর ast, check, dis আর vm. শুধু শেষ প্যানেলের stack-এর ছবিটি bytecode ধরে ধরে একটি ছোট script দিয়ে মেলানো।
- Source
order.haatঅক্ষর - Lexer
tokensশব্দ - Parser
astগাছ - Checker
checkনাম, type - Compiler
disbytecode - VM
vmচালানো
// বাজারঘর: একটি অর্ডার let qty = 2; print(qty * 520 + 60);
3:1 PRINT print 3:6 LPAREN ( 3:7 IDENT qty 3:11 STAR * 3:13 INT 520 3:17 PLUS + 3:19 INT 60 3:21 RPAREN ) 3:22 SEMI ; 4:1 EOF
(program (let qty 2) (print (+ (* qty 520) 60)))
ok resolver: qty → let, global slot 0, ঘোষণা 2:5 checker: qty : Int, qty * 520 : Int, (qty * 520) + 60 : Int, print(Int) ঠিক
== <main> (arity 0, locals 0) == 0 CONST 0 ; 2 1 DEFINE_GLOBAL 0 ; qty 2 LOAD_GLOBAL 0 ; qty 3 CONST 1 ; 520 4 MUL 5 CONST 2 ; 60 6 ADD 7 PRINT 8 CONST 3 ; () 9 RETURN
CONST 2 [2]
DEFINE_GLOBAL 0 [] qty = 2
LOAD_GLOBAL 0 [2]
CONST 520 [2, 520]
MUL [1040]
CONST 60 [1040, 60]
ADD [1100]
PRINT [] আউটপুট: 1100
- Source. Compiler-এর কাছে এটি শুধু অক্ষরের একটি লম্বা সারি; লাইন ভাঙাও একটি অক্ষর। প্রথম লাইনটি comment, আর তাতে বাংলা লেখা থাকলেও কোনো সমস্যা নেই।
- Lexer. লাইন ৩-এর অক্ষরগুলো ৯টি token-এ ভাগ হলো, শেষে ফাইল-শেষের চিহ্ন EOF: প্রতিটির একটি শ্রেণি (kind), আসল লেখা (lexeme) আর অবস্থান line:col. Comment আর ফাঁকা ঘর হারিয়ে গেছে, তাই লাইন ২-এর token শুরু 2:1-এ। পুরো ফাইলে EOF-সহ ১৫টি token; এখানে শুধু লাইন ৩-এর গুলো।
- Parser. token-এর সমতল সারি এখন একটি গাছ:
*গাছের নিচের দিকে, কারণ এটি+-এর চেয়ে শক্ত করে বাঁধে। বন্ধনী আর;গাছে নেই; তাদের কাজ ছিল শুধু গঠন বোঝানো। এই গাছই abstract syntax tree. - Semantic analysis. Name resolution খুঁজে পায়, লাইন ৩-এর
qtyহলো 2:5-এ ঘোষিতlet-টি, যা global slot 0-এ থাকবে। Type checker নিচ থেকে ওপরে type বসায়: সব Int, আরprintInt ছাপতে পারে। কোনো ভুল নেই, তাই শুধুok. (ধূসর লাইনগুলো ব্যাখ্যা, CLI-র আউটপুট নয়।) - Bytecode compiler. গাছটি post-order-এ হাঁটা হলো: আগে বাঁ সন্তান, তারপর ডান, তারপর operator. ফলে গাছ থেকে একটি সমতল নির্দেশের তালিকা, একটি stack machine-এর জন্য। এটিই Haat-এর IR-এর প্রথম রূপ: bytecode.
- VM. stack-এ 2 আর 520 উঠল,
MULদুটি নামিয়ে 1040 রাখল, তারপর 60 যোগ করে 1100, আরPRINTসেটি ছাপল। শেষেরCONST ()আরRETURNশুধু main-এর শেষ চিহ্নিত করে।python haat.py run(tree-walking interpreter)-ও 1100 দেয়।
এবার একই পথ নিজের হাতে লিখে চালান, ব্রাউজারের ভেতরের Python-এ (Pyodide). নিচের দুটি block মিলে একটি ছোট্ট পাঁচ-ধাপের pipeline: শুধু Int, Bool নাম, + - * / আর বন্ধনী। Reference-এর পুরো কোড অনেক বড়; এটি শুধু ধাপগুলোর কাঠামো দেখানোর জন্য। প্রথম block-এ front end: lexer একটি regular expression দিয়ে, parser একটি ছোট Pratt parser (পর্ব ৪৮-এ বিস্তারিত), আর checker নাম ও type দেখে।
import re
class HaatError(Exception): pass
def lex(src): # phase 1: characters -> tokens
toks = []
for m in re.finditer(r"\s*(?:(\d+)|([A-Za-z_]\w*)|([-+*/()])|(\S))", src):
num, name, op, bad = m.groups(); col = m.start(m.lastindex) + 1
if bad: raise HaatError(f"1:{col}: error: unexpected character '{bad}'")
toks.append(("INT", int(num), col) if num else ("NAME", name, col) if name else (op, op, col))
return toks + [("EOF", "", len(src) + 1)]
BP = {"+": 50, "-": 50, "*": 60, "/": 60} # binding power: * / bind tighter
def parse(toks, min_bp=0): # phase 2: tokens -> AST (Pratt)
kind, val, col = toks.pop(0)
if kind == "(":
left = parse(toks)
if toks.pop(0)[0] != ")": raise HaatError(f"1:{col}: error: expected ')'")
elif kind in ("INT", "NAME"): left = (kind, val, col)
else: raise HaatError(f"1:{col}: error: expected expression")
while toks[0][0] in BP and BP[toks[0][0]] >= min_bp:
op, _, c = toks.pop(0)
left = (op, left, parse(toks, BP[op] + 1), c)
return left
def check(e, env): # phase 3: names and types
if e[0] == "INT": return "Int"
if e[0] == "NAME":
if e[1] not in env: raise HaatError(f"1:{e[2]}: error: undefined variable '{e[1]}'")
return env[e[1]]
for side in e[1:3]:
if (t := check(side, env)) != "Int":
raise HaatError(f"1:{side[2]}: error: type mismatch: expected Int, found {t}")
return "Int"
toks = lex("qty * 520 + 60")
print("tokens:", [t[1] for t in toks])
ast = parse(toks)
print("AST: ", ast)
print("type: ", check(ast, {"qty": "Int", "paid": "Bool"}))আসল আউটপুট (ব্রাউজারের Python):
tokens: ['qty', '*', 520, '+', 60, '']
AST: ('+', ('*', ('NAME', 'qty', 1), ('INT', 520, 7), 5), ('INT', 60, 13), 11)
type: Int
শেষের '' হলো EOF token. AST-এর প্রতিটি tuple-এর শেষ সংখ্যা column: * আছে column 5-এ, + column 11-এ। বাইরের node +, আর তার বাঁ সন্তান *-এর node, ঠিক reference-এর (+ (* qty 520) 60)-এর মতো। এই গঠন এসেছে binding power থেকে: *-এর ৬০ বড় বলে সে +-এর (৫০) আগে নিজের ডান operand নিয়ে নেয়। Checker-এর পরিবেশে paid একটি Bool; পরের block-এ এটি দিয়ে একটি type error বানাব।
দ্বিতীয় block-এ back end আর পুরো pipeline: gen AST থেকে stack code লেখে, run একটি ছোট stack VM, আর pipeline ধাপগুলো পরপর চালায় এবং মনে রাখে কোন ধাপে থামল। এটি আগের block-এর function ব্যবহার করে (আগেরটি না চালালে নিজে থেকেই আগে চলবে)।
OPS = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}
def gen(e): # phase 4: AST -> stack code
if e[0] == "INT": return [("CONST", e[1], e[2])]
if e[0] == "NAME": return [("LOAD", e[1], e[2])]
return gen(e[1]) + gen(e[2]) + [(OPS[e[0]], None, e[3])]
def run(code, values): # phase 5: a tiny stack VM
st = []
for op, arg, col in code:
if op == "CONST": st.append(arg)
elif op == "LOAD": st.append(values[arg])
else:
b, a = st.pop(), st.pop()
if op == "DIV":
if b == 0: raise HaatError(f"1:{col}: runtime error: division by zero")
q = abs(a) // abs(b); st.append(q if (a >= 0) == (b >= 0) else -q)
else: st.append(a + b if op == "ADD" else a - b if op == "SUB" else a * b)
return st.pop()
def pipeline(src, values={"qty": 2, "paid": True}):
env = {k: "Bool" if isinstance(v, bool) else "Int" for k, v in values.items()}
phase = "lexer"
try:
toks = lex(src); phase = "parser"
ast = parse(toks); phase = "checker"
check(ast, env); phase = "VM"
code = gen(ast)
return f"{len(code)} instructions -> {run(code, values)}"
except HaatError as e:
return f"stopped in {phase}: {e}"
print([op if a is None else f"{op} {a}" for op, a, _ in gen(parse(lex("qty * 520 + 60")))])
for src in ["qty * 520 + 60", "qty @ 520", "qty * (520 + 60", "qtty * 520",
"qty * paid", "520 / (qty - 2)"]:
print(f"{src:16} {pipeline(src)}")আসল আউটপুট (ব্রাউজারের Python):
['LOAD qty', 'CONST 520', 'MUL', 'CONST 60', 'ADD']
qty * 520 + 60 5 instructions -> 1100
qty @ 520 stopped in lexer: 1:5: error: unexpected character '@'
qty * (520 + 60 stopped in parser: 1:7: error: expected ')'
qtty * 520 stopped in checker: 1:1: error: undefined variable 'qtty'
qty * paid stopped in checker: 1:7: error: type mismatch: expected Int, found Bool
520 / (qty - 2) stopped in VM: 1:5: runtime error: division by zero
প্রথম লাইনের stack code reference-এর LOAD_GLOBAL, CONST, MUL, CONST, ADD অংশের সঙ্গে হুবহু মেলে। তারপর ছয়টি ইনপুট, ছয়টি আলাদা পরিণতি। @ কোনো token-ই নয়, তাই lexer থামায়। ( খোলা কিন্তু বন্ধ হয়নি: অক্ষরগুলো সব চেনা, কিন্তু গঠন ভাঙা, তাই parser. qtty একটি বৈধ নাম, কিন্তু কোথাও ঘোষিত নয়; আর qty * paid গঠনে নিখুঁত, কিন্তু Bool দিয়ে গুণ চলে না: দুটিই checker-এর কাজ। শেষটি সব static ধাপ পার হয়েছে, কারণ qty - 2-এর মান চলার আগে জানা নেই (এই ছোট pipeline-এ); শূন্য দিয়ে ভাগ ধরা পড়ল চলার সময়, VM-এ। Error-এর format reference-এর মতোই: line:col: error: ….
৪ · সত্যিকারের Clang-এর front end — token আর AST
খেলনা pipeline দেখা হলো; এবার একটি শিল্প-মানের compiler-এর ভেতরে তাকাই। সব কিছু সত্যিকারের run: PyPI-র ziglang 0.17.1 প্যাকেজ (MIT licence), যার সঙ্গে আসে Clang 22.1.8 (LLVM-এর Apache-2.0 with LLVM exception licence). নিচে zig মানে python -m ziglang. C ফাইলটি Haat-এর bazar.haat-এর প্রথম অংশের C রূপ:
#include <stdio.h>
int price(int qty, int unit) {
int p = qty * unit;
if (p >= 1000) return p - p / 10;
return p;
}
int delivery(int total) {
return total >= 1000 ? 0 : 60;
}
int main(void) {
int first = price(2, 520) + delivery(price(2, 520));
printf("%d\n", first);
return 0;
}~/haat $ zig version
0.17.1
~/haat $ zig cc --version
clang version 22.1.8
~/haat $ zig cc -O2 bazar.c -o bazar.exe
~/haat $ ./bazar.exe
996
Haat-এর মতোই 996. এবার ধাপে ধাপে থামাই। zig cc হলো Clang-এর driver: সে নিজে অনুবাদ করে না, বরং ঠিক করে কোন ধাপের জন্য কোন অংশ ডাকবে। আসল C front end চলে clang -cc1 নামে। প্রথমে preprocessor দিয়ে #include খুলে bazar.i বানাই (১৭ লাইন থেকে ১৮৮ লাইন), তারপর সেই ফাইলে সরাসরি front end চালাই:
~/haat $ zig cc -target x86_64-linux-musl -E bazar.c -o bazar.i
~/haat $ zig clang -cc1 -triple x86_64-linux-musl -dump-tokens bazar.i
… stdio.h-এর হাজারখানেক token, তারপর লাইন ১০:
return 'return' Loc=<bazar.c:10:5>
identifier 'total' Loc=<bazar.c:10:12>
greaterequal '>=' Loc=<bazar.c:10:18>
numeric_constant '1000' Loc=<bazar.c:10:21>
question '?' Loc=<bazar.c:10:26>
numeric_constant '0' Loc=<bazar.c:10:28>
colon ':' Loc=<bazar.c:10:30>
numeric_constant '60' Loc=<bazar.c:10:32>
semi ';' Loc=<bazar.c:10:34>
(প্রতিটি লাইনের [StartOfLine], [LeadingSpace] চিহ্ন বাদ দিয়ে ফাঁকা ঘর মিলিয়েছি; বাকিটা হুবহু।) Haat-এর tokens-এর সঙ্গে মিলিয়ে দেখুন: শ্রেণি, lexeme আর অবস্থান, তিনটিই আছে। একটি সূক্ষ্ম জিনিস: bazar.i ফাইলে লাইনটি আসলে অনেক নিচে, তবু Clang বলছে bazar.c:10:5. Preprocessor ফাইলে লাইন-চিহ্ন রেখে দেয়, আর lexer সেগুলো পড়ে আসল ঠিকানা মনে রাখে। অবস্থানের এই হিসাব পুরো pipeline জুড়ে টেনে নিতে হয়, নইলে শেষ ধাপের error বা debugger আপনাকে সঠিক লাইন দেখাতে পারত না।
এবার AST. -ast-dump পুরো ফাইলের গাছ দেখায়; -ast-dump-filter=delivery শুধু একটি function-এর:
~/haat $ zig clang -cc1 -triple x86_64-linux-musl -fsyntax-only -ast-dump -ast-dump-filter=delivery bazar.i
Dumping delivery:
FunctionDecl <bazar.c:9:1, line:11:1> line:9:5 used delivery 'int (int)'
|-ParmVarDecl <col:14, col:18> col:18 used total 'int'
`-CompoundStmt <col:25, line:11:1>
`-ReturnStmt <line:10:5, col:32>
`-ConditionalOperator <col:12, col:32> 'int'
|-BinaryOperator <col:12, col:21> 'int' '>='
| |-ImplicitCastExpr <col:12> 'int' <LValueToRValue>
| | `-DeclRefExpr <col:12> 'int' lvalue ParmVar 'total' 'int'
| `-IntegerLiteral <col:21> 'int' 1000
|-IntegerLiteral <col:28> 'int' 0
`-IntegerLiteral <col:32> 'int' 60
(প্রতিটি node-এর পাশের মেমরি-ঠিকানা, যেমন 0x1b16e77b138, বাদ দিয়েছি; প্রতিবার চালালে সেগুলো বদলায়।) তিনটি জিনিস খেয়াল করুন। এক, Clang-এর AST-এ type আগেই বসানো: প্রতিটি expression-এর পাশে 'int'. Clang-এ parser আর semantic analysis (Clang-এর ভাষায় “Sema”) একসঙ্গে চলে; parser একটি node বানানো মাত্র Sema সেটি যাচাই করে type বসায়। তাই ছবি ৫.১-এর মতো আলাদা ধাপ এখানে একটি pass-এ মেশানো। দুই, DeclRefExpr মানে name resolution-এর ফল: total নামটি ParmVar 'total'-এর সঙ্গে জোড়া লেগেছে। তিন, লেখায় যা নেই, গাছে তা আছে: ImplicitCastExpr <LValueToRValue> মানে “এই variable-এর ঘর থেকে মানটি পড়া”; C-তে এই কাজটি লেখা থাকে না, কিন্তু অর্থে আছে, তাই semantic analysis সেটি গাছে স্পষ্ট করে বসায়। -fsyntax-only মানে front end-এর পরেই থামা, কোনো কোড না বানানো।
৫ · Middle end আর back end — LLVM IR থেকে x86-64 আর RISC-V
Front end-এর কাজ শেষ হলে Clang AST থেকে LLVM-এর IR বানায়। LLVM IR দেখতে assembly-র মতো, কিন্তু কোনো নির্দিষ্ট CPU-র নয়: register অসীম, নাম %3, %4; আর প্রতিটি নামে মান বসে ঠিক একবার। শেষ শর্তটির নাম SSA (static single assignment), পর্ব ৬৩-এ এর পুরো গল্প। নিচের stepper-এ একটি function, delivery, পুরো পথ পার হয়; প্রতিটি প্যানেল সত্যিকারের run থেকে নেওয়া।
~/haat $ zig cc -target x86_64-linux-musl -O0 -g0 -fno-sanitize=undefined -S -emit-llvm bazar.c -o o0.ll
~/haat $ zig cc -target x86_64-linux-musl -O2 -g0 -S -emit-llvm bazar.c -o o2.ll
~/haat $ zig cc -target x86_64-linux-musl -O2 -g0 -fomit-frame-pointer -fno-asynchronous-unwind-tables -S bazar.c -o x86.s
~/haat $ zig cc -target riscv64-linux-musl -O2 -g0 -fomit-frame-pointer -fno-asynchronous-unwind-tables -S bazar.c -o rv.s
~/haat $ wc -l o0.ll o2.ll x86.s rv.s
80 o0.ll
56 o2.ll
68 x86.s
74 rv.s
- C
bazar.csource - IR -O0
o0.llসরল অনুবাদ - IR -O2
o2.lloptimizer-এর পরে - x86-64
x86.sback end ১ - RISC-V
rv.sback end ২
int delivery(int total) {
return total >= 1000 ? 0 : 60;
}
define dso_local i32 @delivery(i32 noundef %0) #0 {
%2 = alloca i32, align 4
store i32 %0, ptr %2, align 4
%3 = load i32, ptr %2, align 4
%4 = icmp sge i32 %3, 1000
%5 = zext i1 %4 to i64
%6 = select i1 %4, i32 0, i32 60
ret i32 %6
}
define dso_local noundef range(i32 0, 61) i32
@delivery(i32 noundef %0) local_unnamed_addr #0 {
%2 = icmp sgt i32 %0, 999
%3 = select i1 %2, i32 0, i32 60
ret i32 %3
}
delivery:
xorl %ecx, %ecx
cmpl $1000, %edi
movl $60, %eax
cmovgel %ecx, %eax
retq
delivery: slti a0, a0, 1000 neg a0, a0 andi a0, a0, 60 ret
- C source. একটি তুলনা আর দুটি সম্ভাব্য ফল: total ≥ 1000 হলে ডেলিভারি ফ্রি (0), নইলে 60 টাকা। Front end এটিকে আগের অংশের AST-এ পরিণত করেছে।
- সরল অনুবাদ (-O0). IR generation গাছের প্রতিটি node হুবহু নামিয়েছে: parameter-এর জন্য stack-এ একটি ঘর (
alloca), সেখানে রাখা আর আবার পড়া, তুলনাicmp sge(signed ≥), তারপরselect, যা দুটি মানের একটি বেছে নেয়। লাল দাগের%5কোথাও ব্যবহার হয় না; -O0 এমন অপ্রয়োজনীয় কাজও রেখে দেয়। - Optimizer-এর পরে (-O2). stack-এর ঘর উধাও: parameter
%0সরাসরি ব্যবহার। অব্যবহৃত%5মুছে গেছে (dead code elimination).≥ 1000হয়েছে> 999, একই অর্থ, LLVM-এর পছন্দের রূপ। আর optimizer প্রমাণ করে লিখে রেখেছে, ফল সবসময় 0 থেকে 60-এর মধ্যে:range(i32 0, 61). - x86-64 back end. একই IR থেকে Intel/AMD-এর নির্দেশ। ecx-এ 0, eax-এ 60; তুলনার পরে
cmovge(“≥ হলে সরানো”) eax-এ 0 বসায়। কোনো jump নেই, তাই CPU-কে কোন দিকে যাবে আন্দাজ করতে হয় না। parameter এসেছে%edi-তে আর ফল%eax-এ: এটি x86-64-এর calling convention. - RISC-V back end. একই IR, অন্য কৌশল, কারণ RISC-V-এর base ISA-তে
cmovনেই।sltiলেখে total < 1000 হলে 1, নইলে 0;negসেটিকে −1 (সব বিট 1) বা 0 বানায়;andi … 60দিলে ফল 60 বা 0. total = 936 হলে: 1 → −1 → 60, ঠিক bazar-এর ডেলিভারি চার্জ। Front end আর middle end একই রেখে শুধু back end বদলানো: এটিই retargetable compiler.
(Assembly থেকে .cfi_* নির্দেশ আর ফাঁকা মন্তব্য বাদ দিয়েছি।) একটি সতর্কতা নিজের run থেকেই: প্রথমবার -fno-sanitize=undefined ছাড়া -O0-এ IR বানিয়ে দেখি price-এর ভেতরে @llvm.smul.with.overflow আর @__ubsan_handle_mul_overflow-এর মতো call. অর্থাৎ zig cc debug build-এ নিজে থেকে undefined behavior-এর পাহারাদার (UBSan) চালু করে, যা সাধারণ clang-এর default নয়। একই “Clang” হলেও driver-এর default flag আলাদা হতে পারে, তাই কোনো আউটপুট উদ্ধৃত করার সময় পুরো কমান্ড লিখুন।
price() — optimizer যা যা করল
price-এ একটি if আছে, তাই এর IR-এ একাধিক basic block. -O0-এ function-টি ২৪টি নির্দেশ (চারটি alloca, অনেক load/store), -O2-এ ৮টি:
define dso_local range(i32 -2147483648, 2147483548) i32 @price(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
%3 = mul nsw i32 %1, %0
%4 = icmp sgt i32 %3, 999
br i1 %4, label %5, label %8
5: ; preds = %2
%6 = udiv i32 %3, 10
%7 = sub nsw i32 %3, %6
br label %8
8: ; preds = %2, %5
%9 = phi i32 [ %7, %5 ], [ %3, %2 ]
ret i32 %9
}
define dso_local noundef i32 @main() local_unnamed_addr #1 {
%1 = tail call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(1) @.str, i32 noundef 996)
ret i32 0
}
চারটি জিনিস পড়ুন। (১) φ নির্দেশ: block 8-এ দুটি পথ এসে মেলে; phi বলে “block 5 থেকে এলে %7 (ছাড়ের পরের দাম), block 2 (শুরুর block) থেকে এলে %3 (মূল দাম)”. এটিই SSA-র φ-function. (২) sdiv হয়ে গেছে udiv: -O0-এ ছিল signed ভাগ। এই block-এ পৌঁছানো মানে p > 999, অর্থাৎ ধনাত্মক; ধনাত্মক সংখ্যায় signed আর unsigned ভাগের ফল এক, আর unsigned ভাগ সস্তা। Optimizer পথের শর্ত থেকে মানের সীমা জেনে নিয়েছে। (৩) nsw: “no signed wrap”, অর্থাৎ C-তে signed overflow undefined behavior, তাই optimizer ধরে নিতে পারে গুণে overflow হবে না। Haat-এ overflow wrap করে, তাই Haat-এর compiler এই চিহ্ন বসাতে পারবে না। (৪) main-এ শুধু 996: price আর delivery main-এর ভেতরে বসানো হয়েছে (inlining), তারপর সব মান ধ্রুবক বলে পুরো হিসাব build-এর সময়েই শেষ (constant folding).
price-এর x86-64 assembly-তে আরেকটি পুরোনো কৌশল দেখা যায়: 10 দিয়ে ভাগের কোনো div নির্দেশ নেই!
price:
movl %edi, %eax
imull %esi, %eax
cmpl $1000, %eax # imm = 0x3E8
jl .LBB0_2
movl %eax, %ecx
movl $3435973837, %edx # imm = 0xCCCCCCCD
imulq %rcx, %rdx
shrq $35, %rdx
subl %edx, %eax
.LBB0_2:
retq
p / 10-এর বদলে (p × 3435973837) >> 35. কারণ 3435973837 / 235 ≈ 0.10000000000582, আর যেকোনো ৩২-বিট unsigned p-এর জন্য এই গুণ-আর-shift ঠিক ⌊p / 10⌋ দেয়। যেমন p = 1040: 1040 × 3435973837 = 3573412790480, আর তাকে 235 (34359738368) দিয়ে ভাগ করে নিচে নামালে 104. ভাগ নির্দেশ বহু CPU-তে গুণের চেয়ে কয়েক গুণ ধীর, তাই ধ্রুবক দিয়ে ভাগকে গুণে বদলানো একটি strength reduction. এই পদ্ধতির পরিচিত বিবরণ Torbjörn Granlund আর Peter Montgomery-র ১৯৯৪ সালের গবেষণাপত্রে (PLDI). RISC-V-এর assembly-তে একই ধ্রুবক অন্যভাবে তৈরি হয় (lui আর addi দিয়ে), কারণ RISC-V-এর নির্দেশে বড় ধ্রুবক একবারে ধরে না।
Object file — symbol আর ফাঁকা ঠিকানা
Assembler-এর পরে bazar.o. Zig-এর নিজের objdump এই সংস্করণে ELF ফাইল পড়ে না (“TODO dump elf file” বলে), তাই ELF-এর symbol table আর relocation পড়ার একটি ২৭ লাইনের Python script (syms.py) লিখে নিয়েছি:
~/haat $ zig cc -target x86_64-linux-musl -O2 -g0 -fomit-frame-pointer -fno-asynchronous-unwind-tables -c bazar.c -o bazar.o
~/haat $ python syms.py bazar.o
SYMBOL BIND TYPE SECTION SIZE
price GLOBAL FUNC .text 30
delivery GLOBAL FUNC .text 17
main GLOBAL FUNC .text 22
printf GLOBAL NOTYPE UNDEF 0
RELOCATIONS in .text
offset 0x0042 R_X86_64_32 -> .rodata.str1.1+0
offset 0x004e R_X86_64_PLT32 -> printf-4
তিনটি function এই ফাইলে আছে (.text section, আকার byte-এ), কিন্তু printf UNDEF: “আমার দরকার, কিন্তু আমার কাছে নেই।” দুটি relocation হলো ফাঁকা রাখা জায়গা: main-এর ভেতরে offset 0x4e-এ printf-এর ঠিকানা আর 0x42-এ "%d\n" string-এর ঠিকানা। Linker এগুলো পূরণ করবে; পূর্ণ গল্প পর্ব ৭৪-এ (Linking আর loading). আর ৩০ byte-এর price ঠিক আগের assembly-র দশটি নির্দেশ।
৬ · কোন ভুল কোন ধাপে ধরা পড়ে
অংশ ৩-এর ছোট pipeline-এ দেখেছিলেন, প্রতিটি ধাপের নিজের ধরনের ভুল আছে। এবার একই কথা দুটি সত্যিকারের বাস্তবায়নে: Haat reference আর Clang. সব error হুবহু সত্যিকারের run থেকে; Clang-এর গুলো zig clang -cc1 -triple x86_64-linux-musl -fsyntax-only eN.c দিয়ে, linker-এরটি zig cc দিয়ে পুরো build করে।
- Lexerঅক্ষর
- Parserগঠন
- Semanticনাম, type
- Linkersymbol
- Runtimeচলার সময়
Haat: print(qty @ 520); 2:11: error: unexpected character '@' C: return "Bazarghor; e1.c:2:12: warning: missing terminating '"' character e1.c:2:12: error: expected expression
Haat: let qty = 2 (লাইন ১) 1:12: error: expected ';' after variable declaration C: int p = qty * unit (লাইন ২) e2.c:2:23: error: expected ';' at end of declaration
Haat: print(qtty * 520); 2:7: error: undefined variable 'qtty' C: int p = qty * untt; e3.c:2:19: error: use of undeclared identifier 'untt'; did you mean 'unit'?
Haat: print(qty * true); 2:13: error: type mismatch: expected Int, found Bool C: int *p = qty * unit; e4.c:2:10: error: incompatible integer to pointer conversion initializing 'int *' with an expression of type 'int' [-Wint-conversion]
C: int discount(int p); // শুধু ঘোষণা return discount(1040); ld.lld: error: undefined symbol: discount >>> referenced by e5.c:3 >>> e5.o:(main) Haat-এ linker নেই: সব নাম check-এই মেলানো।
Haat: let qty = 0; print(520 / qty); 2:11: runtime error: division by zero check বলেছিল: ok. কোনো static ধাপ qty-এর মান চলার আগে দেখে না।
- Lexical ভুল. Haat-এ
@কোনো token-এর অংশ নয়, তাই lexer প্রথম ভুলেই থামে (reference-এর নিয়ম)। Clang-এর lexer শেষ না হওয়া string দেখে একটি warning দেয়, তারপর parser আর কোনো expression খুঁজে পায় না। একটি ধাপের ভুল প্রায়ই পরের ধাপে আরেকটি error হয়ে দেখা দেয়; তাই সবসময় প্রথম error-টি আগে পড়ুন। - Syntax ভুল. দুজনেই একই কাজ করে: আগের token-এর ঠিক পরের column দেখায়। Haat-এ
2শেষ হয়েছে column 11-এ, তাই 1:12. Clang তার নিচে একটি;বসানোর পরামর্শও দেখায় (এখানে ছাঁটা)। - Name resolution.
qttyআরunttদুটিই বৈধ token, ব্যাকরণেও ঠিক; ধরা পড়ে শুধু symbol table-এ খুঁজে না পেলে। Clang আরও এগিয়ে কাছাকাছি বানানের একটি নাম খুঁজে প্রস্তাব দেয় (-cc1দিয়ে চালালে; আমাদেরzig ccrun-এ এই প্রস্তাব আসেনি)। - Type checking. Haat-এ Int আর Bool মেশানো যায় না, কোনো স্বয়ংক্রিয় রূপান্তর নেই। C-তে int থেকে pointer-এ রূপান্তর পুরোনো C-তে শুধু warning ছিল; সাম্প্রতিক Clang এটিকে default-ভাবে error করে, আর তার নাম এখনো
-Wint-conversion. একই ভুল কোন version-এ warning আর কোনটিতে error, তা version ধরে যাচাই করুন। - Link ভুল.
discount-এর ঘোষণা আছে, তাই compiler সন্তুষ্ট; কিন্তু সংজ্ঞা কোনো object file-এ নেই, তাই LLVM-এর linkerld.lldথামায়। (দ্বিতীয়>>>লাইনের লম্বা cache-পথ ছোট করেছি।) C-তে আলাদা ফাইল আলাদাভাবে compile হয় বলে এই ভুল একমাত্র linker-ই দেখতে পায়। - Runtime ভুল. সব static ধাপ পার,
checkবলেছে ok; তবু চালালে error. Haat-এ এর ফল নির্দিষ্ট: একটি runtime error, আগের আউটপুট থেকে যায়। C-তে int-কে শূন্য দিয়ে ভাগ undefined behavior; কোনো নিশ্চিত error-এর প্রতিশ্রুতি নেই।
শেষ ধাপটি একটি গভীর সত্য দেখায়। কোনো static ধাপ কি সব শূন্য-দিয়ে-ভাগ চালানোর আগে ধরতে পারত? সাধারণভাবে না: “এই program কি কখনো শূন্য দিয়ে ভাগ করবে?” একটি অ-তুচ্ছ আচরণগত প্রশ্ন, আর Rice-এর theorem বলে এমন প্রশ্ন সব program-এর জন্য নিখুঁতভাবে কোনো algorithm দিয়ে সিদ্ধান্ত করা যায় না (গণনার তত্ত্ব কোর্সের পর্ব ৫৩)। তাই compiler-এর static ধাপগুলো ইচ্ছা করে রক্ষণশীল: কিছু ভুল ধরে, বাকিগুলো runtime-এর জন্য রেখে দেয়, অথবা (type system-এর মতো) কিছু ঠিক program-কেও বাতিল করে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় compiler-এর ধাপ নিয়ে এই ধরনের প্রশ্ন খুব আসে:
- Compiler-এর ধাপগুলো কী কী, প্রতিটির আউটপুট কী? Lexer (token), parser (parse tree/AST), semantic analysis (type-সহ AST, symbol table), IR generation (three-address code), optimization (ভালো IR), code generation (target code); symbol table আর error handler সব ধাপের সঙ্গী।
int 2x = 5;-এর ভুল কোন ধাপের? Lexer2x-কে একটি সংখ্যা-জাতীয় token বানায়; নামের জায়গায় সংখ্যা দেখে parser থামে। Clang 22.1.8 বলেexpected identifier or '('. এমন প্রশ্নে নির্দিষ্ট compiler-এ চালিয়ে দেখাই সবচেয়ে নিরাপদ।- Phase আর pass-এর পার্থক্য? Phase একটি যুক্তিগত কাজ; pass হলো পুরো program-এর ওপর দিয়ে একবার পড়া, যাতে এক বা একাধিক phase থাকতে পারে।
- Front end আর back end ভাগ কেন? m ভাষা আর n যন্ত্রের জন্য m·n-এর বদলে m + n অংশ; নতুন ভাষা বা নতুন CPU আনা সহজ।
- Symbol table কোন ধাপে তৈরি হয়? Lexer বা parser-এর সময় শুরু হতে পারে, তবে নাম আর type-এর তথ্য ভরে semantic analysis; পরের সব ধাপ তা পড়ে।
৭ · তিন ভাগ, অনেক pass — নকশার যুক্তি আর একটি প্রমাণ
m × n থেকে m + n
ধরুন বাজারঘরের একটি দল ৪টি ভাষা (C, C++, Rust, Haat) আর ৩টি CPU (x86-64, ARM, RISC-V)-এর জন্য compiler চায়। প্রতিটি জোড়ার জন্য আলাদা compiler লিখলে লাগে ৪ × ৩ = ১২টি। মাঝখানে একটি সাধারণ IR রাখলে লাগে ৪টি front end আর ৩টি back end, মোট ৭টি অংশ, আর optimizer একটিই, সবার জন্য। সাধারণভাবে m·n বনাম m + n.
m ≥ 2 আর n ≥ 2 হলে m + n ≤ m·n.
প্রমাণ. (১) m·n − m − n = (m − 1)(n − 1) − 1. (২) m ≥ 2 আর n ≥ 2 বলে m − 1 ≥ 1 আর n − 1 ≥ 1, তাই (m − 1)(n − 1) ≥ 1. (৩) অতএব m·n − m − n ≥ 0, অর্থাৎ m + n ≤ m·n; সমান হয় শুধু m = n = 2 হলে। ∎
লাভটা শুধু সংখ্যায় নয়। নতুন একটি ভাষা আনলে শুধু একটি front end লিখলেই সে সব CPU-তে চলে, আর optimizer-এর সব উন্নতি বিনা খরচে পায়: Rust আর Swift ঠিক এভাবে LLVM ব্যবহার করে। আবার নতুন একটি CPU আনলে একটি back end লিখলেই সব ভাষা সেখানে চলে। ধারণাটি পুরোনো: ১৯৫৮ সালে UNCOL (Universal Computer Oriented Language) নামে একটি সাধারণ মাঝের ভাষার প্রস্তাব আসে, যা তখন বাস্তবে সফল হয়নি; পরে JVM-এর bytecode, LLVM IR আর WebAssembly এই স্বপ্নের নানা রূপ বাস্তব করেছে।
Phase আর pass
Phase যুক্তির ভাগ; pass বাস্তবায়নের ভাগ। একটি pass মানে program-এর পুরো একটি রূপের ওপর দিয়ে একবার হাঁটা। Clang-এ parser আর semantic analysis একটি pass-এ মেশানো (অংশ ৪); আবার LLVM-এর optimizer একটি phase হলেও ভেতরে শত শত ছোট pass. LLVM-এর pass manager-কে নিজের কাজের হিসাব ছাপতে বলা যায়:
~/haat $ zig clang -cc1 -triple x86_64-linux-musl -O2 -emit-llvm -o out.ll -fdebug-pass-manager bazar.i > dpm.txt 2>&1
~/haat $ grep -c "Running pass" dpm.txt
281
~/haat $ grep "Running pass" dpm.txt | grep -c " on price "
77
~/haat $ grep "Running pass" dpm.txt | grep " on price " | sed 's/Running pass: //; s/ on price.*//' | sort -u | wc -l
45
~/haat $ grep "Running pass" dpm.txt | grep " on price " | head -5
Running pass: EntryExitInstrumenterPass on price (29 instructions)
Running pass: LowerExpectIntrinsicPass on price (29 instructions)
Running pass: SimplifyCFGPass on price (29 instructions)
Running pass: SROAPass on price (29 instructions)
Running pass: EarlyCSEPass on price (9 instructions)
মাত্র ১৭ লাইনের একটি ফাইলে -O2-এ মোট ২৮১ বার কোনো না কোনো pass চলেছে; শুধু price-এর ওপর ৭৭ বার, ৪৫টি আলাদা pass, কয়েকটি বারবার (যেমন InstCombinePass, SimplifyCFGPass). খেয়াল করুন, SROAPass (stack-এর ঘরকে SSA মানে বদলানো) চলার পরেই নির্দেশ ২৯ থেকে ৯-এ নেমেছে। এই সংখ্যাগুলো এই একটি run-এর, Clang 22.1.8-এ; অন্য version-এ তালিকা বদলায়।
নিচের JavaScript block-এ “pass” ধারণাটি নিজে চালিয়ে দেখুন। প্রতিটি pass একটি function: AST নেয়, AST দেয়। Middle end মানে এমন pass-এর একটি তালিকা। একই AST চারটি আলাদা তালিকা দিয়ে চালানো হলো, আর প্রতিবার stack code আর ফল ছাপা হলো:
// A pass is a function AST -> AST; a middle end is a list of passes.
const N = v => ({k: "num", v}), V = n => ({k: "var", n}), B = (op, l, r) => ({k: "bin", op, l, r});
const calc = (op, a, b) => op === "+" ? a + b : op === "-" ? a - b : a * b;
function fold(e) { // pass: constant folding
if (e.k !== "bin") return e;
const l = fold(e.l), r = fold(e.r);
if (l.k === "num" && r.k === "num") return N(calc(e.op, l.v, r.v));
return B(e.op, l, r);
}
function dropZero(e) { // pass: x + 0 -> x
if (e.k !== "bin") return e;
const l = dropZero(e.l), r = dropZero(e.r);
if (e.op === "+" && r.k === "num" && r.v === 0) return l;
return B(e.op, l, r);
}
function gen(e) { // back end: AST -> stack code
if (e.k === "num") return [`CONST ${e.v}`];
if (e.k === "var") return [`LOAD ${e.n}`];
return [...gen(e.l), ...gen(e.r), {"+": "ADD", "-": "SUB", "*": "MUL"}[e.op]];
}
function run(code, env) { // stack VM
const st = [];
for (const ins of code) { const [op, arg] = ins.split(" ");
if (op === "CONST") st.push(Number(arg));
else if (op === "LOAD") st.push(env[arg]);
else { const b = st.pop(), a = st.pop(); st.push(calc({ADD: "+", SUB: "-", MUL: "*"}[op], a, b)); }
}
return st.pop();
}
const ast = B( // Haat: qty * (24 * 60) + (60 - 60)
"+", B("*", V("qty"), B("*", N(24), N(60))), B("-", N(60), N(60)));
for (const passes of [[], [fold], [fold, dropZero], [dropZero, fold]]) {
const code = gen(passes.reduce((e, p) => p(e), ast));
console.log(`${passes.map(p => p.name).join(" > ") || "no pass"}: ${code.length} instr, qty=2 -> ${run(code, {qty: 2})}\n ${code.join("; ")}`);
}আসল আউটপুট (ব্রাউজারের JavaScript):
no pass: 9 instr, qty=2 -> 2880
LOAD qty; CONST 24; CONST 60; MUL; MUL; CONST 60; CONST 60; SUB; ADD
fold: 5 instr, qty=2 -> 2880
LOAD qty; CONST 1440; MUL; CONST 0; ADD
fold > dropZero: 3 instr, qty=2 -> 2880
LOAD qty; CONST 1440; MUL
dropZero > fold: 5 instr, qty=2 -> 2880
LOAD qty; CONST 1440; MUL; CONST 0; ADD
চারবারই ফল 2880, তাই প্রতিটি তালিকা অর্থ রেখেছে; কিন্তু কোডের আকার আলাদা। fold 24 × 60-কে 1440 আর 60 − 60-কে 0 বানাল। তারপর dropZero “+ 0” মুছে দিল: ৯টি নির্দেশ থেকে ৩টি। শেষ লাইনটি সবচেয়ে শিক্ষণীয়: একই দুটি pass উল্টো ক্রমে চালালে কাজ হয় না। dropZero আগে চলার সময় সে (60 − 60) দেখেছে, “0” দেখেনি; শূন্যটি জন্মেছে পরে, fold-এর হাতে। একে বলে phase-ordering সমস্যা; LLVM-এ InstCombinePass বারবার চলার একটি কারণ এটিই। (JavaScript-এর সংখ্যা ৬৪-বিট Int নয়; এত ছোট মানে তাতে পার্থক্য হয় না।)
একটি প্রমাণ — ধাপ সঠিক হলে শিকলও সঠিক
সংজ্ঞা ৫.১-এর C = Pn ∘ … ∘ P1-এর প্রতিটি ধাপ Pi সঠিক হলে, C যে source program p গ্রহণ করে তার প্রতিটির জন্য ⟦C(p)⟧Ln = ⟦p⟧L0.
প্রমাণ (k-এর ওপর induction). p0 = p আর pk = Pk(pk−1) লিখি; C p-কে গ্রহণ করে মানে কোনো ধাপ error দেয়নি, তাই সব pk সংজ্ঞায়িত। দাবি: প্রতিটি k-এর জন্য ⟦pk⟧Lk = ⟦p0⟧L0.
(১) ভিত্তি k = 0: দুই দিক একই জিনিস।
(২) ধাপ: k − 1-এর জন্য দাবি সত্য ধরি। Pk সঠিক, তাই ⟦pk⟧Lk = ⟦Pk(pk−1)⟧Lk = ⟦pk−1⟧Lk−1.
(৩) induction-এর অনুমানে ⟦pk−1⟧Lk−1 = ⟦p0⟧L0; তাই k-এর জন্যও সত্য।
(৪) k = n নিলে pn = C(p), অর্থাৎ ⟦C(p)⟧Ln = ⟦p⟧L0. ∎
প্রমাণটি সরল, কিন্তু এর দুটি পরিণতি বড়। প্রথমত, compiler-এর সঠিকতা ধাপে ধাপে যাচাই করা যায়; পুরো compiler একবারে প্রমাণ করতে হয় না। দ্বিতীয়ত, উল্টোটাও সত্য: একটি মাত্র ভুল ধাপ পুরো শিকলকে ভুল করে, তা বাকিরা যত নিখুঁতই হোক। C-র মতো ভাষায়, যেখানে undefined behavior আছে, “=” চিহ্নের বদলে বসে “⊆”: target-এর আচরণ source-এর অনুমোদিত আচরণগুলোর একটি অংশ হলেই চলে। ⊆ সম্পর্কটিও transitive (A ⊆ B আর B ⊆ C হলে A ⊆ C), তাই একই প্রমাণ খাটে।
আরও গভীরে: উপপাদ্য ৫.৩-এর যন্ত্রে-যাচাই-করা রূপই CompCert, Xavier Leroy-র নেতৃত্বে তৈরি একটি C compiler, যার প্রতিটি pass-এর অর্থ-রক্ষা Coq proof assistant-এ প্রমাণ করা আর তারপর প্রমাণগুলো জোড়া দেওয়া (মূল গবেষণা ২০০৬ সাল থেকে; Communications of the ACM-এ ২০০৯ সালের প্রবন্ধ)। ২০১১ সালে Xuejun Yang, John Regehr ও সহকর্মীরা Csmith নামের একটি এলোমেলো C program-জেনারেটর দিয়ে GCC আর LLVM-এ কয়েকশো আগে-অজানা bug পান, কিন্তু CompCert-এর প্রমাণিত অংশে কোনো ভুল-কোড bug পাননি। এর উল্টো দিকে আছে “nanopass” ধারা: Dipanwita Sarkar, Oscar Waddell আর R. Kent Dybvig (২০০৪) দেখান, compiler-কে অনেক ছোট, এক-কাজের pass-এ ভাগ করলে পড়া আর পরীক্ষা করা সহজ হয়; পরে Chez Scheme-এর compiler এই কাঠামোয় নতুন করে লেখা হয়। পর্ব ৪৪-এ verified compiler নিয়ে আরও আসবে।
৮ · CPython-এর নিজের pipeline, আর কোর্সের মানচিত্র
Interpreter-এর ভেতরেও একই ধাপ থাকে, শুধু শেষ ধাপে যন্ত্রের কোড না বানিয়ে নিজের VM চালায়। CPython-এর প্রতিটি ধাপ standard library দিয়ে আলাদা করে দেখা যায়, আর ব্রাউজারের Pyodide-এ সেগুলো সত্যিই চলে। CPython 3.9 থেকে এর parser একটি PEG parser (PEP 617); bytecode আর AST-এর খুঁটিনাটি version ভেদে বদলায়, তাই নিচের block প্রথমে version ছাপে।
import ast, dis, io, symtable, sys, tokenize
src = "total = qty * 520 + 24 * 60\n"
print("CPython", sys.version.split()[0])
# 1. tokenizer: characters -> tokens
toks = tokenize.generate_tokens(io.StringIO(src).readline)
print([f"{tokenize.tok_name[t.type]}:{t.string}" for t in toks if t.string.strip()])
# 2. parser: tokens -> AST
tree = ast.parse(src)
print(ast.dump(tree.body[0].value))
# 3. symbol table: which names are assigned, which are only read
for s in symtable.symtable(src, "<bazar>", "exec").get_symbols():
print("symbol", s.get_name(), "assigned" if s.is_assigned() else "read only")
# 4. compiler (+ optimizer) -> bytecode
dis.dis(compile(tree, "<bazar>", "exec"))আসল আউটপুট (ব্রাউজারের Python):
CPython 3.14.2
['NAME:total', 'OP:=', 'NAME:qty', 'OP:*', 'NUMBER:520', 'OP:+', 'NUMBER:24', 'OP:*', 'NUMBER:60']
BinOp(left=BinOp(left=Name(id='qty', ctx=Load()), op=Mult(), right=Constant(value=520)), op=Add(), right=BinOp(left=Constant(value=24), op=Mult(), right=Constant(value=60)))
symbol total assigned
symbol qty read only
0 RESUME 0
1 LOAD_NAME 0 (qty)
LOAD_CONST 0 (520)
BINARY_OP 5 (*)
LOAD_CONST 2 (1440)
BINARY_OP 0 (+)
STORE_NAME 1 (total)
LOAD_CONST 1 (None)
RETURN_VALUE
ব্রাউজারের Pyodide-এ CPython 3.14.2 চলেছে; ল্যাপটপের CPython 3.14.4-এও প্রথম লাইনের version ছাড়া বাকি আউটপুট হুবহু একই এসেছে। চারটি ধাপ পরপর: tokenizer ৯টি token দিয়েছে (লাইন-শেষ আর ফাইল-শেষের token ফিল্টারে বাদ); parser একটি গাছ, যেখানে 24 * 60 তখনো একটি BinOp; symbol table জানিয়েছে total-এ মান বসে আর qty শুধু পড়া হয়, যা থেকে compiler ঠিক করে কোন নামের জন্য কোন নির্দেশ (LOAD_NAME, STORE_NAME) লাগবে। আর bytecode-এ 24 * 60 নেই, আছে সরাসরি 1440: AST-এর পরে, bytecode বানানোর পথে CPython-এর optimizer constant folding করেছে। qty * 520 ভাঁজ হয়নি, কারণ qty-এর মান চলার আগে জানা নেই। Haat reference-এর tokens → ast → check → dis ঠিক এই চারটি ধাপের মতো।
কোর্সের বাকি পথ এই ধাপগুলোর ওপরেই সাজানো। Haat reference-এর প্রতিটি কমান্ড একটি ধাপের ফল দেখায়, আর প্রতিটি মডিউল একটি বা দুটি ধাপ বানায়:
| ধাপ | Haat reference | CLI | মডিউল ও পর্ব |
|---|---|---|---|
| Lexer | lexer.py | tokens | মডিউল ৮, পর্ব ৪৬ |
| Parser, AST | parser.py, ast_nodes.py | ast, fmt | মডিউল ৮, পর্ব ৪৭–৫০ |
| Name resolution, type checking | resolver.py, typechecker.py | check | মডিউল ৯, পর্ব ৫১–৫৫ (তত্ত্ব: মডিউল ৩ আর ৬) |
| Tree-walking interpreter | interp.py | run | মডিউল ১০, পর্ব ৫৬–৫৭ |
| Bytecode compiler, VM | compiler.py, vm.py | dis, vm | মডিউল ১০, পর্ব ৫৮–৬১ |
| IR, SSA, optimizer | (কোর্সে বানাবেন) | — | মডিউল ১১, পর্ব ৬২–৬৮ |
| Code generation, linking, GC | (কোর্সে বানাবেন) | — | মডিউল ১২, পর্ব ৬৯–৭৫ |
| Tooling (LSP, formatter), ক্যাপস্টোন | — | — | মডিউল ১৩, পর্ব ৮০–৮১ |
“ধাপে ভাগ করা compiler” ধারণা প্রায় compiler-এর সমান পুরোনো। John Backus-এর দলের প্রথম FORTRAN compiler (IBM 704, ১৯৫৭) কয়েকটি আলাদা ভাগে (section) সাজানো ছিল, আর তখনই উল্লেখযোগ্য optimization করত, যাতে প্রোগ্রামাররা হাতে লেখা assembly ছেড়ে আসতে রাজি হন। ১৯৭০-এর দশকে মেমরি কম থাকায় অনেক compiler এক pass-এ কাজ সারত; Niklaus Wirth-এর Pascal-এর নকশায় এক-pass compile করার সুবিধা মাথায় রাখা হয়েছিল বলে প্রায়ই বলা হয়। Alfred Aho, Ravi Sethi আর Jeffrey Ullman-এর ১৯৮৬ সালের বই Compilers: Principles, Techniques, and Tools (মলাটের ছবির জন্য “Dragon Book”; ২০০৬ সালের সংস্করণে Monica Lam যোগ দেন) এই ধাপের তালিকাকে শিক্ষার মানদণ্ড বানায়। আর Chris Lattner ২০০০ সালে University of Illinois-এ LLVM শুরু করেন (Vikram Adve-র সঙ্গে ২০০৪ সালের মূল গবেষণাপত্র); Apple ২০০৭ সালে Clang প্রকল্প শুরু করে।
৯ · AI-এর যুগে compiler pipeline বোঝা
“Compiler-এর ছয়টি phase-এর নাম” ধরনের প্রশ্নে AI assistant চমৎকার মুখস্থ উত্তর দেয়। সমস্যা শুরু হয় নির্দিষ্ট প্রশ্নে: “এই error কোন ধাপের?”, “Clang এই কোডের কী IR বানাবে?”, “এই optimization কি নিরাপদ?” তখন AI প্রায়ই আত্মবিশ্বাসী কিন্তু ভুল উত্তর দেয়। এই বিষয়ে বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
বানানো flag বা pass, যেমন এমন একটি -emit-… option বা LLVM pass-এর নাম, যা কোনো version-এ নেই | clang --help, -fdebug-pass-manager চালিয়ে আসল তালিকা দেখা, version লিখে |
| “Clang এই assembly বানায়” বলে এমন কোড দেখানো, যা আসল আউটপুটের সঙ্গে মেলে না (ভুল register, ভুল ক্রম) | নিজে -S বা -emit-llvm চালিয়ে মেলানো, target আর -O লেভেল লিখে |
| এক compiler-এর আচরণ সবার ঘাড়ে চাপানো, যেমন “int থেকে pointer-এ রূপান্তর শুধু warning” | নির্দিষ্ট compiler ও version-এ চালানো; একটি run-এর ফল সব version-এর নিয়ম নয় |
Optimization “ঠিক আছে” বলা, যা অর্থ বদলায়, যেমন x / x-কে 1 বানানো | দুটি রূপ অনেক ইনপুটে, বিশেষ করে 0, ঋণাত্মক আর সীমার মানে চালিয়ে মেলানো (differential testing) |
Precedence বা associativity ভুল করা parser, যেমন a - b - c-কে a - (b - c) | AST ছাপিয়ে দেখা, আর reference-এর ast কমান্ডের সঙ্গে মেলানো |
| Undefined behavior-এর ফলকে নিশ্চিত বলা, যেমন “C-তে শূন্য দিয়ে ভাগে সবসময় crash” | ভাষার standard দেখা; UB মানে কোনো প্রতিশ্রুতি নেই |
AI-কে pipeline বোঝার সঙ্গী বানাতে সাধারণ ব্যাখ্যা না চেয়ে এমন প্রশ্ন করুন, যার উত্তর আপনি নিজে চালিয়ে যাচাই করতে পারেন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন।
প্র ০১মাঝখানে একটি সাধারণ IR রাখলেই কি সব সমস্যার সমাধান? তাহলে Rust বা Swift কেন LLVM IR-এর আগে নিজের আলাদা IR রাখে?
m + n-এর হিসাব সুন্দর, কিন্তু এর একটি লুকানো শর্ত আছে: সাধারণ IR-কে এতটা নিচু স্তরের হতে হয়, যাতে সব ভাষা সেখানে নামতে পারে। নিচে নামার সময় ভাষার নিজস্ব জ্ঞান হারিয়ে যায়। ১৯৫৮ সালের UNCOL প্রস্তাব ব্যর্থ হয়েছিল অনেকটা এই কারণেই: সব ভাষা আর সব যন্ত্রের জন্য একটি ভাষা খুঁজে পাওয়া তখন কঠিন ছিল, আর যা পাওয়া যেত, তা কারও জন্য ভালো ছিল না।
LLVM IR সফল হয়েছে C-ধাঁচের ভাষার জন্য: pointer, integer, function call, branch, এই স্তরে বেশিরভাগ ভাষা নামতে পারে। কিন্তু ধরুন Rust-এর borrow checker. “এই reference-এর lifetime কত” প্রশ্নটি LLVM IR-এ জিজ্ঞেস করার উপায় নেই, কারণ সেখানে শুধু pointer আছে, ownership নেই। তাই rustc আগে নিজের HIR আর MIR বানায়, borrow checking আর Rust-নির্দিষ্ট optimization সেখানে করে, তারপর LLVM IR-এ নামে। Swift-এর SIL, GHC (Haskell)-এর Core আর STG একই কারণে আছে: প্রতিটি ভাষার উঁচু স্তরের অর্থ (generic, closure, laziness) নিয়ে কাজ করতে উঁচু স্তরের IR লাগে।
ফলে বাস্তবের ছবি “একটি IR” নয়, বরং IR-এর একটি সিঁড়ি: ভাষা-নির্দিষ্ট উঁচু IR, তারপর সাধারণ মাঝের IR, তারপর যন্ত্র-নির্দিষ্ট নিচু IR (LLVM-এর ভেতরে SelectionDAG আর MachineInstr). Chris Lattner-এর নেতৃত্বে তৈরি MLIR (প্রায় ২০১৯ সাল থেকে) এই সিঁড়িটিকেই একটি কাঠামো বানিয়েছে, যেখানে অনেক “dialect” পাশাপাশি থাকে আর ধাপে ধাপে নিচে নামে। Haat-এও এই কোর্সে দুটি স্তর দেখবেন: stack VM-এর bytecode (পর্ব ৫৮) আর three-address code ও SSA (পর্ব ৬২–৬৩)।
মূল উপলব্ধি: সাধারণ IR ভাগ করার খরচ কমায়, কিন্তু প্রতিটি নিচে-নামা কিছু অর্থ মুছে দেয়। ভালো compiler তাই প্রতিটি প্রশ্নের উত্তর সেই স্তরে খোঁজে, যেখানে উত্তরের জন্য দরকারি তথ্য এখনো বেঁচে আছে।
প্র ০২এক pass-এর compiler না অনেক pass-এর? দ্রুত compile আর ভালো কোডের মধ্যে আপস কোথায়?
এক pass-এর compiler source একবার পড়ে আর পড়তে পড়তেই কোড লেখে। এর সুবিধা স্পষ্ট: পুরো program মেমরিতে রাখতে হয় না, আর compile খুব দ্রুত। ১৯৬০ আর ৭০-এর দশকে কম্পিউটারের মেমরি এত কম ছিল যে পুরো AST রাখাই বিলাসিতা; তাই অনেক compiler এক বা অল্প কয়েকটি pass-এ কাজ সারত। এর ছাপ ভাষার নকশায়ও পড়েছে: Pascal-এ নাম ব্যবহারের আগে ঘোষণা করতে হয়, আর C-তে একটি function অন্য function-কে ডাকার আগে তার ঘোষণা (prototype) দেখতে চায়। এক pass-এ পড়া compiler পরে আসা ঘোষণার খবর জানে না, তাই ভাষাই লেখককে আগে ঘোষণা করতে বলে। (ঐতিহাসিক কারণ নিয়ে লেখকদের মতভেদ আছে; এটি একটি প্রচলিত ব্যাখ্যা।)
অসুবিধা হলো optimization. price-এর sdiv-কে udiv বানাতে optimizer-কে জানতে হয়েছে যে এই block-এ পৌঁছানো মানে p > 999; main-এ 996 বসাতে পুরো function-এর ভেতর দেখতে হয়েছে। এগুলো পুরো program-এর রূপ হাতে না থাকলে করা যায় না। LLVM-এর -O2 এই ছোট ফাইলে ২৮১ বার pass চালিয়েছে।
আজও দুই ধারাই বেঁচে আছে। Fabrice Bellard-এর Tiny C Compiler (TCC) প্রায় এক pass-এ খুব দ্রুত compile করে, কিন্তু কোডের মান সাধারণ। Go ভাষার নকশায় দ্রুত build একটি প্রকাশ্য লক্ষ্য ছিল, তাই unused import-কে error বানানো আর সরল dependency নিয়ম রাখা হয়েছে। অন্যদিকে release build-এ মানুষ কয়েক মিনিট অপেক্ষা করতে রাজি, যদি program দ্রুত চলে। JIT compiler (পর্ব ৬১) এই আপসকে চলার সময় নিয়ে যায়: প্রথমে দ্রুত, সরল কোড; পরে যে অংশ বারবার চলে, শুধু তার জন্য ধীরে ভালো কোড।
এখানে একটি সূক্ষ্মতা: বেশি pass মানেই ধীর নয়। nanopass ধারার compiler অনেক ছোট pass চালায়, কিন্তু প্রতিটি সরল আর দ্রুত; পরে Chez Scheme-এর বাণিজ্যিক compiler-ও এই কাঠামোয় নতুন করে লেখা হয় (Andrew Keep আর Dybvig-এর ২০১৩ সালের প্রতিবেদন), অর্থাৎ ধারণাটি শুধু শিক্ষার খেলনা নয়। ধীরতা আসে pass-এর সংখ্যা থেকে নয়, প্রতিটি pass কত ভারী analysis করে তা থেকে।
মূল উপলব্ধি: pass-এর সংখ্যা একটি নকশার সিদ্ধান্ত, যা মেমরি, compile-সময়, কোডের মান আর এমনকি ভাষার নিয়মকেও প্রভাবিত করে। “Development-এ দ্রুত build, release-এ ভালো কোড” এই আপসেরই রোজকার রূপ।
প্র ০৩-O0-এ program ঠিক চলে, -O2-এ ভুল ফল দেয়। দোষ কার, compiler-এর না program-এর? কীভাবে নিশ্চিত হবেন?
অভিজ্ঞতা বলে, বেশিরভাগ ক্ষেত্রে দোষ program-এর। C আর C++-এ undefined behavior আছে, আর optimizer ধরে নেয় এমন কিছু ঘটে না। price-এর IR-এ mul nsw দেখেছেন: “no signed wrap”. Optimizer এই প্রতিশ্রুতির ওপর ভর করে তুলনা সরল করতে পারে, loop-এর সীমা হিসাব করতে পারে। Program যদি সত্যিই overflow ঘটায়, -O0-এ হয়তো wrap করা মান পাবেন, -O2-এ সম্পূর্ণ অন্য কিছু; দুটিই C-র নিয়মে “অনুমোদিত”, কারণ UB-এর কোনো নির্দিষ্ট ফল নেই। এই পর্বে দেখেছেন, zig cc debug build-এ নিজে থেকেই UBSan চালু করে; এমন sanitizer দিয়ে চালালে এই ধরনের ভুল চলার সময় ধরা পড়ে।
তবে compiler-ও ভুল করে। ২০১১ সালে Csmith প্রকল্প এলোমেলো কিন্তু UB-মুক্ত C program বানিয়ে GCC আর LLVM-এ কয়েকশো আগে-অজানা bug খুঁজে পায়, যার অনেকগুলো ছিল optimizer-এর “ভুল কোড” bug: compiler নিঃশব্দে এমন কোড বানাত, যার অর্থ source থেকে আলাদা। পদ্ধতিটি ছিল differential testing: একই program বিভিন্ন compiler আর বিভিন্ন -O লেভেলে চালিয়ে ফল মেলানো; অমিল মানে কোথাও ভুল।
নিশ্চিত হওয়ার পথ তাই কয়েক ধাপের। (১) UBSan আর AddressSanitizer দিয়ে চালান; কিছু ধরা পড়লে আগে program ঠিক করুন। (২) দুটি আলাদা compiler (GCC আর Clang) আর কয়েকটি -O লেভেলে ফল মেলান। (৩) সমস্যাটি সবচেয়ে ছোট program-এ নামিয়ে আনুন; C-Reduce-এর মতো tool এই কাজ স্বয়ংক্রিয়ভাবে করে। (৪) তারপরও শুধু একটি compiler-এর একটি লেভেলে ভুল এলে, এবং program-এ কোনো UB না থাকলে, সম্ভবত compiler-এর bug; তখন ছোট উদাহরণসহ রিপোর্ট করুন।
Haat-এর নকশা এই সমস্যার একটি বড় অংশ এড়ায়: overflow wrap করে, শূন্য দিয়ে ভাগ নির্দিষ্ট runtime error, মূল্যায়নের ক্রম বাঁ থেকে ডানে। তাই Haat-এর সব বাস্তবায়ন (interpreter, VM, পরের RISC-V back end) একই ইনপুটে হুবহু একই আউটপুট দিতে বাধ্য, আর differential testing সরাসরি কাজ করে।
মূল উপলব্ধি: “optimizer ভুল করেছে” বলার আগে প্রমাণ করুন program-এ UB নেই। আর যে ভাষার অর্থ পুরোপুরি নির্দিষ্ট, সেখানে compiler-এর প্রতিটি ধাপ যাচাই করা অনেক সহজ।
প্র ০৪ভালো error message বানানো কোন ধাপের কাজ? Compiler-এর diagnostic কেন এত গুরুত্বপূর্ণ হয়ে উঠেছে?
Error message দেখতে একটি লাইন, কিন্তু তার পেছনে পুরো pipeline-এর সহযোগিতা লাগে। প্রথমত, অবস্থান: lexer প্রতিটি token-এর line:col রাখে, parser সেটি AST-এর node-এ বসায়, semantic analysis সেটি থেকে error-এর জায়গা দেখায়। অংশ ৪-এ দেখেছেন, Clang preprocessor-এর পরেও bazar.c:10:5 মনে রেখেছে। এই হিসাব কোথাও হারালে error ভুল লাইন দেখায়, আর debugger ভুল জায়গায় থামে (debug তথ্যও একই উৎস থেকে আসে)।
দ্বিতীয়ত, কোথায় থামবেন: একটি ভুলের পরেই থেমে গেলে ব্যবহারকারীকে বারবার compile করতে হয়। তাই parser “error recovery” করে: কয়েকটি token ফেলে দিয়ে একটি নিরাপদ জায়গা থেকে আবার শুরু করে (Haat reference-এর panic-mode নিয়ম; পর্ব ৫০)। কিন্তু খারাপ recovery এক ভুল থেকে কুড়িটি ভুয়া error বানায়। অংশ ৬-এ Clang-এর একটি lexer warning-এর পরে parser-এর error দেখেছেন; এমন শিকল সাধারণ।
তৃতীয়ত, পরামর্শ: “did you mean 'unit'?” দিতে symbol table-এ কাছাকাছি বানানের নাম খুঁজতে হয়, আর “;” বসানোর পরামর্শ দিতে parser-কে জানতে হয় কোন token প্রত্যাশিত ছিল। Clang ২০০৭ সাল থেকে পরিষ্কার, রঙিন, পরামর্শ-সহ diagnostic-কে নিজের বড় শক্তি হিসেবে তুলে ধরে, আর এর প্রতিযোগিতায় GCC-র মেসেজও পরের বছরগুলোতে অনেক উন্নত হয়েছে। Elm আর Rust-এর সম্প্রদায় error message-কে ভাষার “ব্যবহারকারী-ইন্টারফেস” হিসেবে দেখে।
আজ diagnostic শুধু terminal-এ সীমিত নয়। Editor-এর লাল দাগ আসে language server (LSP) থেকে, যা compiler-এর front end-ই অন্যভাবে চালায়, প্রতিটি কী-চাপের পরে (পর্ব ৮০)। তাই front end-কে দ্রুত, আংশিক ভুল ফাইলেও কাজ করতে সক্ষম, আর incremental হতে হয়।
মূল উপলব্ধি: ভালো diagnostic কোনো একক ধাপের কাজ নয়; lexer-এর অবস্থান রাখা থেকে semantic analysis-এর পরামর্শ পর্যন্ত পুরো front end-এর নকশার ফল। AI-এর যুগেও এটি গুরুত্বপূর্ণ, কারণ AI নিজেও compiler-এর মেসেজ পড়েই কোড ঠিক করে।
প্র ০৫CPython বা একটি JavaScript engine-এর pipeline কি একটি C compiler-এর মতোই? সীমারেখা কোথায়?
Front end প্রায় একই। CPython-এ tokenizer, তারপর PEG parser (৩.৯ থেকে), তারপর AST, তারপর symbol table; অংশ ৮-এর block-এ প্রতিটি নিজের চোখে দেখেছেন। তারপর CPython-এর compiler AST থেকে bytecode বানায়, আর পথে একটি optimizer কাজ করে: 24 * 60-কে 1440 বানানো তারই কাজ। পার্থক্য আসে শেষে: কোনো CPU-র machine code লেখা হয় না, বরং CPython-এর নিজের VM bytecode চালায়। অর্থাৎ back end-এর জায়গায় একটি interpreter.
JavaScript engine-গুলোতে ছবিটি আরও স্তরে ভাগ। V8-এর মতো engine প্রথমে source থেকে bytecode বানিয়ে একটি interpreter-এ চালায়, আর যে function বারবার চলে, তাকে এক বা একাধিক স্তরের optimizing JIT compiler machine code-এ অনুবাদ করে; কোন স্তরের নাম কী আর কয়টি স্তর, তা engine আর version ভেদে বদলায়। অর্থাৎ middle end আর back end চলার সময় কাজ করে, আর চলার সময়ের তথ্য (কোন type আসলে আসছে) ব্যবহার করে। CPython 3.13-এ একটি পরীক্ষামূলক JIT যোগ হয়েছে (PEP 744), যা default-ভাবে বন্ধ।
সীমারেখা তাই “compiler বনাম interpreter” নয়, বরং প্রতিটি ধাপ কখন চলে: build-এর সময় না চলার সময়। Clang সব ধাপ build-এর সময় চালায়। CPython front end আর bytecode compiler চালায় program শুরুর সময় (আর .pyc ফাইলে ফল রেখে দেয়), VM চালায় চলার সময়। JIT engine back end-কেও চলার সময় নিয়ে যায়। প্রতিটি পছন্দের দাম আছে: চলার সময় compile করলে শুরু ধীর, কিন্তু আসল ডেটা দেখে optimize করা যায়।
Haat-এর reference এই সীমারেখার দুই দিকেই দাঁড়িয়ে: run AST সরাসরি চালায় (tree-walking), vm আগে bytecode বানায়। কোর্সের শেষ দিকে একটি RISC-V back end যোগ করলে Haat-এর একটি পুরো AOT compiler-ও হবে, আর তিনটির আউটপুট মেলানো যাবে।
মূল উপলব্ধি: ধাপগুলো সব ভাষার বাস্তবায়নে প্রায় একই; ভিন্নতা হলো কোন ধাপ কখন আর কোথায় চলে। এই প্রশ্নটি করলেই “Python interpreted না compiled” ধরনের বিতর্ক সহজ হয়ে যায়।
অনুশীলন
প্রথমটিতে কোড লিখতে হবে; বাকিগুলো হিসাব, প্রমাণ আর ভুল খোঁজা।
-
Pipeline বাড়ান (বাস্তবায়ন): অংশ ৩-এর ছোট pipeline-এ দুটি কাজ করুন। (ক)
pipeline("qty 520")এখন কোনো error ছাড়াই1 instructions -> 2দেয়: parserqtyপড়ে থেমে যায় আর বাকি token উপেক্ষা করে। এটি ঠিক করুন। (খ) Haat-এর%operator যোগ করুন (C-র মতো: ফলের চিহ্ন dividend-এর চিহ্ন)। কোন কোন ধাপ বদলাতে হলো, আর কোনটি বদলাতে হলো না?(ক) parse-এর পরে দেখুন সব token শেষ হয়েছে কি না:
def parse_all(toks): ast = parse(toks) if toks[0][0] != "EOF": raise HaatError(f"1:{toks[0][2]}: error: unexpected token after expression") return astআর
pipeline-এparse(toks)-এর বদলেparse_all(toks).(খ) চারটি জায়গা: lexer-এর regex-এ
[-+*/%()]; parser-এরBP-তে"%": 60(*আর/-এর সমান);OPS-এ"%": "MOD"; আর VM-এMOD: শূন্য হলে একই runtime error, নইলে শূন্যের দিকে কাটা ভাগফল q থেকেa - b * q. Checker বদলাতে হয়নি, কারণ সে শুধু বলে “দুই পাশে Int চাই”, যা%-এর জন্যও সত্য। এগুলো চালিয়ে পাওয়া ফল:qty 520 stopped in parser: 1:5: error: unexpected token after expression 0 - 7 % 3 5 instructions -> -1 520 % qty 3 instructions -> 0 17 % (qty - 2) stopped in VM: 1:4: runtime error: division by zero0 - 7 % 3= 0 − (7 % 3) = −1, আর Haat reference-এprint(0 - 7 % 3);চালালেও −1. (এই ছোট pipeline-এ unary-নেই, তাই-7 % 3লিখলে parser থামবে।) একটি নতুন operator প্রায় প্রতিটি ধাপ ছোঁয়, কিন্তু প্রতিটিতে মাত্র এক-দুই লাইন: ধাপে ভাগ করার সুবিধা এটিই। -
ভুল খুঁজুন (optimization): একজন Haat-এর optimizer-এ দুটি নতুন নিয়ম যোগ করতে চান: (১)
x / x→1, (২)e * 0→0, যেখানে e যেকোনো expression. কোনটি উপপাদ্য ৫.৩-এর অর্থে “সঠিক ধাপ” নয়? প্রতিটির জন্য একটি পাল্টা উদাহরণ দিন, আর কোন শর্তে নিয়মটি নিরাপদ হয় বলুন।দুটিই ভুল। (১)
let x = 0; print(x / x);: Haat-এ এর অর্থ2:9: runtime error: division by zero(reference-এ চালানো), কিন্তু নিয়মটি লাগালে program 1 ছাপবে। অর্থ বদলেছে, তাই ধাপটি সঠিক নয়। নিরাপদ শুধু তখন, যখন optimizer প্রমাণ করতে পারে x ≠ 0 (যেমন অংশ ৫-এ LLVM পথের শর্ত থেকে p > 999 জেনেছিল)।(২)
fn f(x: Int) -> Int { return 100 / x; }আরprint(f(0) * 0);: reference বলে1:34: runtime error: division by zero, কারণ বাঁ থেকে ডানে মূল্যায়নে আগেf(0)চলে। নিয়মটি লাগালে 0 ছাপা হবে।eযদি এমন কিছু হয় যা error দিতে পারে, চিরকাল চলতে পারে (Haat-এwhileদিয়ে), বা ভবিষ্যতে কোনো দেখা-যায় এমন কাজ করে, তাহলে তাকে মুছে ফেলা চলে না। নিরাপদ শর্ত: e একটি ধ্রুবক বা variable (যার পড়া সবসময় সফল; reference-এর decision 18-এর “not initialized yet” ক্ষেত্রটিও বাদ রাখতে হবে)।শিক্ষা: “গণিতে সত্য” আর “program-এর অর্থে সত্য” এক নয়। প্রতিটি optimization নিয়মের জন্য প্রশ্ন করুন: কোন ইনপুটে, কোন runtime error বা side effect-এ দুই রূপ আলাদা আচরণ করবে?
-
Output আর ধাপ অনুমান করুন (trace): Haat program
print(10 - 4 / 3 * 2);-এর জন্য বলুন: (ক) EOF-সহ কয়টি token, (খ) AST-এর S-expression, (গ) Haat VM-এর bytecode (main-এর শেষ দুটি নির্দেশসহ), (ঘ) আউটপুট। তারপর reference দিয়ে মেলান।(ক)
print ( 10 - 4 / 3 * 2 ) ;= ১১টি token, EOF-সহ ১২টি (tokens১২ লাইন ছাপে)।(খ)
/আর*একই স্তরের, বাঁ-সংযোজী, আর--এর চেয়ে শক্ত:(program (print (- 10 (* (/ 4 3) 2))))(গ) post-order হাঁটা:
0 CONST 0 ; 10 1 CONST 1 ; 4 2 CONST 2 ; 3 3 DIV 4 CONST 3 ; 2 5 MUL 6 SUB 7 PRINT 8 CONST 4 ; () 9 RETURN(ঘ) 4 / 3 শূন্যের দিকে কেটে 1, তারপর 1 × 2 = 2, 10 − 2 = 8. reference-এর
vmঠিক 8 ছাপে। খেয়াল করুন, Haat compiler-এ constant folding নেই, তাই সব ধ্রুবক হলেও VM চলার সময় হিসাব করে; Clang -O2-এ এখানে সরাসরি 8 বসাত। -
ধাপ চিনুন আর গুনুন: (ক) নিচের প্রতিটি মেসেজ কোন ধাপের:
4:9: error: unexpected character '#';ld.lld: error: undefined symbol: tax;3:24: runtime error: 'k' is not initialized yet;error: use of undeclared identifier 'totl';2:13: error: expected ';' after print statement. (খ) একটি দল ৫টি ভাষা আর ৪টি CPU-র জন্য compiler চায়। সাধারণ IR ছাড়া আর সহ কয়টি অংশ লাগবে? পরে একটি নতুন CPU এলে দুই ক্ষেত্রে কয়টি নতুন অংশ লিখতে হবে?(ক) প্রথমটি lexer (অচেনা অক্ষর); দ্বিতীয়টি linker (সংজ্ঞা কোনো object file-এ নেই); তৃতীয়টি runtime: Haat-এ hoisted function কোনো top-level variable-এর
letচলার আগেই সেটি পড়লে এই error (reference-এর decision 18; যেমন লাইন ১-এprint(f());, লাইন ২-এlet k = 5;, লাইন ৩-এfn f() -> Int { return k; }, যা reference-এ চালিয়ে এই মেসেজই পাওয়া যায়); চতুর্থটি semantic analysis (name resolution); পঞ্চমটি parser (syntax).(খ) IR ছাড়া ৫ × ৪ = ২০টি compiler; IR সহ ৫ + ৪ = ৯টি অংশ (আর একটি সাধারণ optimizer). নতুন CPU এলে: IR ছাড়া ৫টি নতুন compiler (প্রতিটি ভাষার জন্য একটি), IR সহ মাত্র ১টি নতুন back end. দাবি ৫.২ অনুযায়ী m, n ≥ 2 হলে m + n কখনো m·n-এর বেশি নয়।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি compiler-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Lexical analysis — অক্ষর থেকে token
- Syntax analysis — token থেকে AST
- Semantic analysis — নাম আর type যাচাই
- IR generation — AST থেকে মাঝের ভাষা
- Optimization — IR থেকে ভালো IR
- Code generation — IR থেকে assembly
C compiler বলল: error: use of undeclared identifier 'untt'. কোন ধাপ এই ভুল ধরেছে?
- Lexical analysis
- Syntax analysis
- Semantic analysis (name resolution)
- Linker
৫টি ভাষা আর ৪টি CPU-র জন্য compiler বানাতে মাঝখানে একটি সাধারণ IR রাখলে কয়টি front end আর back end লাগে?
- ২০টি
- ৯টি
- ৫টি
- ৬টি
Haat program print(qty @ 520); চালালে reference বাস্তবায়ন 2:11: error: unexpected character '@' দেয়। কোন ধাপ থেমেছে?
- Lexer
- Parser
- Type checker
- VM, চলার সময়
LLVM IR-এ %9 = phi i32 [ %7, %5 ], [ %3, %2 ] নির্দেশটি কী করে?
- %7 আর %3 যোগ করে %9-এ রাখে
- মেমরির ঠিকানা %5 থেকে মান পড়ে
- %7 আর %3-এর মধ্যে যেকোনো একটি এলোমেলোভাবে বেছে নেয়
- নিয়ন্ত্রণ কোন আগের block থেকে এসেছে, সেই অনুযায়ী %7 বা %3 বেছে নেয়
Compiler-এর “phase” আর “pass”-এর সম্পর্ক নিয়ে কোন কথাটি ঠিক?
- প্রতিটি phase ঠিক একটি pass, দুটি একই জিনিস
- Phase একটি যুক্তিগত কাজ; এক pass-এ কয়েকটি phase থাকতে পারে, আবার এক phase বহু pass-এ ভাগ হতে পারে
- Pass শুধু optimizer-এ থাকে, front end-এ থাকে না
- যত বেশি pass, কোড তত ভালো, ক্রম কোনো ব্যাপার নয়
একটি x86-64 object file-এর symbol table-এ লেখা: printf GLOBAL NOTYPE UNDEF 0. এর অর্থ কী?
- printf এই ফাইলেই আছে, কিন্তু খালি
- compiler printf খুঁজে পায়নি, তাই compile ব্যর্থ
- ফাইলটি printf ব্যবহার করে, কিন্তু সংজ্ঞা অন্য কোথাও; linker সেটি জুড়বে
- optimizer printf মুছে ফেলেছে
একটি compiler-এর প্রতিটি ধাপ নিজে সঠিক (অর্থ রাখে) প্রমাণিত। পুরো compiler সম্পর্কে কী বলা যায়?
- পুরো compiler-ও সঠিক, কারণ সমান অর্থের শিকল জোড়া দিলে অর্থ একই থাকে
- কিছুই বলা যায় না, পুরো compiler আলাদা করে প্রমাণ করতে হবে
- ধাপগুলো যেকোনো ক্রমে চালালেও compiler সঠিক থাকবে
- শুধু optimization ছাড়া (-O0) সঠিক
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Compiler হলো ধাপের শিকল: অক্ষর → token → AST → নাম ও type-সহ AST → IR → ভালো IR → assembly → object file → executable.
- Front end ভাষা বোঝে, middle end IR-এ optimize করে, back end যন্ত্র বোঝে; সাধারণ IR থাকলে m·n-এর বদলে m + n অংশ।
- Phase যুক্তির ভাগ, pass বাস্তবায়নের ভাগ; pass-এর ক্রমও ফল বদলায়।
- ভুলের ঠিকানা: অক্ষর → lexer, গঠন → parser, নাম ও type → semantic analysis, অনুপস্থিত সংজ্ঞা → linker, মানের ওপর নির্ভরশীল ভুল → runtime.
- প্রতিটি ধাপ অর্থ রাখলে পুরো compiler অর্থ রাখে (উপপাদ্য ৫.৩); দাবি যাচাই করুন আসল tool-এর আউটপুট আর differential testing দিয়ে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৬ · ভাষা নকশার লক্ষ্য আর আপস — readability, safety, performanceপরবর্তী পর্বHaat-এর প্রতিটি নকশা-সিদ্ধান্তের যুক্তি, আর overflow, null ও bounds check-এর আপস।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্ব১৪টি মডিউলের পুরো মানচিত্র।
- C প্রোগ্রামিং · পর্ব ০৩ · টুলচেইনভিত্তিpreprocess, compile, assemble আর link — ব্যবহারকারীর চোখে।
- গণনার তত্ত্ব · পর্ব ২২ · Lexical analysisতত্ত্বtoken-এর regular expression, automaton আর lexer generator.
- Computer Architecture · পর্ব ৩১ · C থেকে assemblyপাশের ট্র্যাকcompiler-এর বানানো assembly CPU-র দিক থেকে পড়া।