এই পর্বে যা শিখবেন
- Attribute, semantic rule আর syntax-directed definition (SDD) কী, আর একটি ছোট expression grammar-এ মান, type আর code-এর নিয়ম লেখা
- Synthesized আর inherited attribute-এর পার্থক্য, S-attributed আর L-attributed SDD, আর কোনটি কোন parser-এ এক হাঁটায় হিসাব হয়
- Attribute-নির্ভরতার গ্রাফ বানিয়ে topological ক্রমে হিসাব, চক্র ধরা, আর কেন যেকোনো বৈধ ক্রম একই ফল দেয়
- SDD আর translation scheme-এর পার্থক্য, আর attribute দিয়ে three-address code ও stack code বানানো
- হাতে লেখা resolver আর type checker-এর ভেতরে কোন attribute লুকিয়ে আছে, আর বাস্তব tool-এ attribute grammar
১ · ব্যাকরণের গায়ে হিসাব জোড়া — attribute কী
বাজারঘরের একটি অর্ডার স্লিপ ভাবুন। প্রতিটি লাইনে পণ্য, পরিমাণ আর একক দাম; লাইনের দাম = পরিমাণ × একক দাম, আর স্লিপের মোট = সব লাইনের দামের যোগফল। এই সংখ্যাগুলো নিচ থেকে ওপরে ওঠে: আগে লাইন, পরে মোট। কিন্তু স্লিপের মাথায় লেখা থাকে খদ্দেরের সদস্য-কার্ড, আর প্রতিটি লাইনের ছাড় হিসাব করতে কার্ডের হার লাগে। এই তথ্য ওপর থেকে নিচে নামে। ক্যাশিয়ার কোন সংখ্যা আগে লিখবেন, তা নিয়ে কোনো বাঁধা নিয়ম নেই; শুধু শর্ত একটি: প্রতিটি সংখ্যা লেখার আগে যে সংখ্যাগুলো তার দরকার, সেগুলো তৈরি থাকতে হবে।
স্লিপের ঘরগুলো হলো attribute grammar-এর attribute; “লাইনের দাম = পরিমাণ × দাম” এর মতো সূত্রগুলো semantic rule; লাইনের দাম আর মোট synthesized attribute; কার্ডের ছাড়ের হার inherited attribute; আর “কোনটি আগে লাগবে” তালিকাটি একটি dependency graph.
এই মডিউলে Haat-এর মাঝের অংশ তৈরি হচ্ছে। পর্ব ৫১-এ resolver প্রতিটি নামকে তার ঘোষণার সঙ্গে জুড়েছে, পর্ব ৫২-তে (Type checker বাস্তবায়ন) পর্ব ৩৪-এর typing rule একটি recursive pass হয়ে কোডে বসছে। এই পর্বে এক পা পিছিয়ে একটি প্রশ্ন: এই pass-গুলো কি একই ছাঁচের? উত্তর হ্যাঁ, আর ছাঁচটির নাম attribute grammar. ধারণাটি পুরোনো: Edgar Irons ১৯৬১ সালে ALGOL 60-এর জন্য একটি “syntax-directed” compiler-এর বর্ণনা দেন বলে পরিচিত, আর Donald Knuth ১৯৬৮ সালের “Semantics of context-free languages” প্রবন্ধে এর formal রূপ দেন। ইতিহাসের সংক্ষেপ গণনার তত্ত্ব কোর্সের পর্ব ২৬-এ (Derivation আর parse tree) আছে; এখানে আমরা এটি বানাব আর চালাব।
একটি syntax-directed definition হলো একটি context-free grammar, যার প্রতিটি grammar-চিহ্ন X-এর কয়েকটি attribute (যেমন X.val, X.type), আর প্রতিটি production A → X1 … Xn-এর সঙ্গে কয়েকটি semantic rule, প্রতিটি এই আকারের: b = f(c1, …, ck). এখানে c-গুলো এই production-এর চিহ্নগুলোর attribute, আর b হয় (ক) A-র একটি attribute, তখন b synthesized, নয়তো (খ) কোনো Xi-এর একটি attribute, তখন b inherited.
একটি নির্দিষ্ট গাছে প্রতিটি node-এর প্রতিটি attribute একটি করে attribute instance. SDD বলে কোন instance কোন instance থেকে আসে; কোন ক্রমে হিসাব হবে, তা বলে না।
এই পর্বের চলমান উদাহরণ Haat-এর expression-এর একটি টুকরো: সংখ্যা, নাম আর চারটি operator. নিয়মগুলো AST-এর ওপর লেখা, কারণ precedence আর associativity পর্ব ৪৮-এর parser ইতিমধ্যে গাছের আকারে বসিয়ে দিয়েছে। Knuth-এর মূল সংজ্ঞা parse tree-এর ওপর, কিন্তু একই কৌশল abstract syntax-এও চলে, আর compiler-এ সেটিই স্বাভাবিক।
| Production | Semantic rule |
|---|---|
| E → num | E.val = num.lexval; E.type = Int; E.code = [CONST num] |
| E → id | E.val = E.env(id).val; E.type = E.env(id).type; E.code = [LOAD id] |
| E → E1 op E2 | E1.env = E.env; E2.env = E.env; E.val = E1.val op E2.val; E.type = Int, যদি E1.type = E2.type = Int; E.code = E1.code ‖ E2.code ‖ [OP] |
টেবিলে চারটি attribute: val, type আর code synthesized (বাঁ দিকের E-র), env inherited (ডান দিকের E1, E2-এর)। ‖ মানে তালিকা জোড়া। E1.env = E.env-এর মতো নিয়ম কিছুই হিসাব করে না, শুধু মান হাতবদল করে; একে বলে copy rule. বড় attribute grammar-এর নিয়মের বড় অংশই এমন, তাই অনেক tool এগুলো নিজে থেকে বসিয়ে দেয়। ভাগ / Haat-এর মতো শূন্যের দিকে কাটে, C-র মতো।
২ · Synthesized attribute — নিচ থেকে ওপরে
প্রথমে শুধু synthesized attribute. 1040 - 1040 / 10 (বাজারঘরের ১০% ছাড়, price(2, 520)-এর হিসাব) গাছে পাঁচটি node: দুটি Binary আর তিনটি সংখ্যা। কোনো নাম নেই, তাই env-এর দরকার নেই। প্রতিটি node-এর মান তার সন্তানদের মান থেকে আসে, তাই সন্তানেরা আগে, node নিজে পরে: ঠিক postorder traversal. নিচের প্রতিটি মান অংশ ৪-এর evaluator এই গাছে চালিয়ে নেওয়া; reference-এ print(1040 - 1040 / 10); চালালে আসে 936.
1E → num : val = n, type = Int2 code = [CONST n]3E → E1 / E2 : val = E1.val / E2.val4E → E1 - E2 : val = E1.val - E2.val5type = Int যদি E1, E2 দুটিই Int6code = E1.code ‖ E2.code ‖ [OP]
| node | |
| val | |
| type | |
| code |
- বাঁ দিকের পাতা. Postorder শুরু হয় সবচেয়ে বাঁয়ের পাতা থেকে: সংখ্যা 1040. তার তিনটি attribute কোনো কিছুর ওপর নির্ভর করে না, শুধু token-এর লেখার ওপর; তাই সঙ্গে সঙ্গে হিসাব হয়।
- ডান subtree-র বাঁ পাতা. ডান দিকে আছে
1040 / 10; তার Binary node-এর আগে তার সন্তানেরা। দ্বিতীয় 1040-ও একই নিয়মে: val 1040, type Int. - সংখ্যা 10. তিনটি পাতাই শেষ। লক্ষ করুন, এ পর্যন্ত কোনো Binary node-এর কিছুই জানা নেই।
- Binary
/. দুই সন্তানের val তৈরি, তাই 1040 / 10 = 104; দুই সন্তানই Int, তাই type Int; code দুই সন্তানের code জুড়ে শেষেDIV. - মূল Binary
-. বাঁয়ে 1040, ডানে 104: val 936. Code-এ পাঁচটি instruction: দুই 1040, 10,DIV,SUB. Reference-এরdis-এ ঠিক এই ক্রম আসে (সেখানে লেখাCONST 0 ; 1040, কারণ constant-গুলো একটি পুলে থাকে)। - ফল মূলের attribute-এ. পুরো গাছের অর্থ এখন মূল node-এর তিনটি synthesized attribute-এ: 936, Int আর ৫টি instruction. Reference-এর
runএকই 936 ছাপে।
যে SDD-তে সব attribute synthesized, তাকে বলে S-attributed definition. উপপাদ্য: S-attributed SDD-তে যেকোনো গাছের সব attribute একটি postorder হাঁটায় হিসাব হয়।
প্রমাণের রূপরেখা. (১) প্রতিটি নিয়ম b = f(c1, …, ck)-এ b মূল-চিহ্ন A-র attribute, আর c-গুলো A-র সন্তানদের attribute বা token-এর লেখা (inherited কিছু নেই)। (২) Postorder-এ একটি node-এ পৌঁছানোর আগে তার সব সন্তানের subtree শেষ হয়। (৩) গাছের উচ্চতা ধরে induction: পাতার attribute শুধু token-এর ওপর নির্ভর করে; একটি ভেতরের node-এ পৌঁছালে induction অনুযায়ী তার সব সন্তানের attribute তৈরি, তাই তার নিয়মের সব উৎস তৈরি। ∎
এ কারণেই S-attributed SDD bottom-up parser-এর সবচেয়ে প্রিয় সঙ্গী: LR parser একটি production-এর reduce করে ঠিক তখন, যখন তার সব সন্তান তৈরি, আর stack-এ সন্তানদের পাশে তাদের মান রাখা যায়। yacc / Bison-এর semantic action এই ধাঁচের: $1, $3 সন্তানদের মান, $$ মা-বাবার। নিচের টুকরোটি শুধু চেহারা দেখানোর জন্য (উদাহরণ, চালানো হয়নি); LR parsing-এর তত্ত্ব গণনার তত্ত্বের পর্ব ৩৯-এ আর generator-এর ব্যবহার পর্ব ৪০-এ।
expr : expr '-' term { $$ = $1 - $3; }
| term { $$ = $1; }
;
term : term '/' NUM { $$ = $1 / $3; }
| NUM { $$ = $1; }
;
৩ · Inherited attribute — ওপর থেকে নিচে, বাঁ থেকে ডানে
এবার গাছে একটি নাম ঢোকান: p - p / 10. p-এর মান আর type গাছের ভেতরে নেই; আছে ঘোষণায়, গাছের বাইরে। সেই খবর মূল থেকে প্রতিটি পাতায় নামিয়ে দেয় inherited attribute env, অর্থাৎ নাম থেকে (type, মান)-এর একটি খাতা, পর্ব ১৫-এর environment. নিচের ছবিতে দুই দিকের প্রবাহ একসঙ্গে।
ছবি ৫৩.১ — p - p / 10-এর গাছে দুই দিকের attribute
হলুদ ঘর inherited env, ড্যাশ দেওয়া তির ওপর থেকে নিচে; সবুজ ঘর synthesized val, ভরাট তির নিচ থেকে ওপরে (type-ও একই পথে ওঠে; এখানে সবখানে Int). মূলের env = {p ↦ 1040 : Int} বাইরে থেকে আসে।
env-কে চারটি সন্তানে পৌঁছে দেয়; দুটি Var p তা থেকে 1040 পড়ে। Num 10-এর env-ও হিসাব হয়, যদিও কেউ সেটি পড়ে না: নিয়ম নিয়ম। প্রতিটি মান অংশ ৪-এর evaluator-এর আসল আউটপুট।Inherited attribute-এর আরও দুটি পরিচিত চেহারা আছে। এক, প্রত্যাশিত type: let x: Int = e;-এ checker e-র কাছে বার্তা পাঠায় “এখানে Int চাই”, অর্থাৎ Int নিচে নামে; এটি bidirectional type checking-এর checking দিক। দুই, function-এর ফেরত type: return e;-কে জানতে হয় সে কোন function-এর ভেতরে। Haat reference-এর typechecker.py-তে এটি self.ret, যা function() ঢোকার সময় বসায় আর বেরোনোর সময় আগের মান ফেরায়: একটি inherited attribute, হাতে লেখা।
Let-শিকল: বাঁ ভাইয়ের ফল ডান ভাইয়ের ইনপুট
Statement-এর তালিকায় খবর শুধু ওপর-নিচ নয়, বাঁ থেকে ডানেও যায়: let q = 2;-এর পরের statement জানে q আছে। নিয়ম দুটি: Si.env.out = Si.env.in + {নাম ↦ E}, আর Si+1.env.in = Si.env.out. প্রথমটি synthesized, দ্বিতীয়টি inherited, আর দুটি মিলে একটি শিকল। নিচের প্রতিটি মান অংশের পরের block (let_chain অংশ) চালিয়ে নেওয়া।
1let q = 2;2let p = q * 520;3print(p - p / 10);
| env.in | |
| E | |
| env.out |
- S1, শুরু. প্রথম statement-এর
env.inবাইরে থেকে আসে: খালি।2-এর synthesized ফল (Int, 2); তাইenv.out= {q: Int 2}. - S2 পায় S1-এর ফল.
env.in= S1-এরenv.out.q * 520-এর ভেতরেenvনামেq-এর পাতা পর্যন্ত, সেখানে 2 পড়া হয়; 2 × 520 = 1040. নতুন খাতায় p যোগ হয়। - S3, বাঁ operand.
p - p / 10. Recursive descent আগে প্রথম term পড়ে: p → 1040. তারপর E′ (বাকি অংশ) ডাকা হয়left = 1040নিয়ে: বাঁ ভাইয়ের ফল ডান ভাইয়ের inherited attribute. - S3, ডান operand. E′ দেখে
-, পরের term পড়ে:p / 10= 104 (এখানেও একই কৌশল, T′-এরleft= 1040). তারপর নতুনleft= 1040 - 104 = 936, আর লাইন শেষ বলে ε-নিয়ম: E′.syn = E′.left. - Print. 936 ছাপা হয়; reference-এর
run-ও 936 দেয়।printকিছু ঘোষণা করে না, তাই তারenv.out=env.in. - যদি S3 আগে আসত?
printদ্বিতীয় লাইনে,let pতৃতীয়তে: শিকলে তখন p নেই, আর সরল নিয়ম বলত “undefined variable”. কিন্তু reference বলে'p' is used before its declaration, দুটি ব্যবহারেই (2:7, 2:11). কারণ Haat-এর নিয়ম (decision 16) পুরো block-এর ঘোষণা আগে জানতে চায়: ডান দিকের খবর, যা শুধু বাঁ থেকে ডানের শিকল দেয় না।
একটি SDD L-attributed, যদি প্রতিটি production A → X1 … Xn-এ প্রতিটি Xi-এর প্রতিটি inherited attribute শুধু (ক) A-র inherited attribute আর (খ) X1 … Xi−1-এর (বাঁ দিকের ভাইদের) attribute-এর ওপর নির্ভর করে; আর A-র synthesized attribute-এর ক্ষেত্রে কোনো চক্র না থাকে। প্রতিটি S-attributed SDD L-attributed.
উপপাদ্য: L-attributed SDD-র সব attribute একটি বাঁ থেকে ডানে depth-first হাঁটায় হিসাব হয়: visit(N) = {প্রতিটি সন্তান Xi-এর জন্য বাঁ থেকে: Xi-এর inherited হিসাব, তারপর visit(Xi)}; শেষে N-এর synthesized হিসাব।
প্রমাণের রূপরেখা. Xi-এর inherited হিসাবের মুহূর্তে A-র inherited আগেই তৈরি (মা-বাবা visit-এর আগে সেটি দিয়েছে), আর X1 … Xi−1-এর visit শেষ, তাই তাদের সব attribute তৈরি; শর্ত (ক)-(খ) বলে এর বাইরে কিছু লাগে না। সব সন্তান শেষ হলে A-র synthesized নিয়মের উৎস তৈরি। গাছের উচ্চতা ধরে induction. ∎
এই হাঁটা হুবহু একটি recursive descent parser: প্রতিটি nonterminal একটি function, inherited attribute হলো parameter, synthesized attribute হলো return value. তাই L-attributed SDD parse করার সময়েই হিসাব হয়ে যায়, আলাদা গাছ না বানিয়েও।
পরীক্ষার খাতায় L-attributed-এর সবচেয়ে পরিচিত উদাহরণ C-ধাঁচের ঘোষণা float x, y, z (Haat-এর নয়, তবে ধারণাটি একই): D → T L { L.in = T.type }, T → float { T.type = float }, L → L1 , id { L1.in = L.in; addtype(id, L.in) }, L → id { addtype(id, L.in) }. Type বাঁ ভাই T থেকে L-এ যায়, তারপর L-এর শিকল ধরে নিচে নামে, আর প্রতিটি id-র কাছে পৌঁছে symbol table-এ লেখা হয়। Annotated parse tree-তে তিনটি L-node-এরই L.in = float. তালিকাটি left-recursive, তাই সবচেয়ে নিচের L-এ থাকে প্রথম id (x); বাঁ থেকে ডানে হাঁটায় addtype চলে x, y, z ক্রমে। addtype একটি side effect, যার মানে অংশ ৫-এ পরিষ্কার হবে।
Left recursion সরালে inherited attribute লাগে কেন
Top-down parser E → E - T-এর মতো left recursion সইতে পারে না; তত্ত্ব আর রূপান্তর গণনার তত্ত্বের পর্ব ৩৮-এ। রূপান্তরের পরে grammar হয় E → T E′, E′ → - T E′ ∣ ε. গাছ এখন ডান দিকে ঝোঁকে, অথচ বিয়োগ বাঁ-সংযোজী: 20 - 5 - 3 = (20 - 5) - 3 = 12. সমাধান: E′-কে একটি inherited attribute left দিন, “এ পর্যন্ত বাঁ দিকের ফল”:
| Production | Semantic rule |
|---|---|
| E → T E′ | E′.left = T.syn; E.syn = E′.syn |
| E′ → - T E′1 | E′1.left = E′.left - T.syn; E′.syn = E′1.syn |
| E′ → ε | E′.syn = E′.left |
E′1.left নির্ভর করে মা-বাবার inherited (E′.left) আর বাঁ ভাই T-এর ওপর: শর্ত মানে, তাই L-attributed. নিচের block ঠিক এই নিয়ম চালায়, সঙ্গে Haat-এর type নিয়ম আর error-এর অবস্থান। এটি reference-এর parser.py (expression অংশ) আর typechecker.py-এর binary()-এর একটি ছোট রূপ, তবে এক হাঁটায়। তুলনার জন্য একটি “ভুল” রূপও আছে (left_assoc=False): সেখানে E′ শুধু synthesized, বাকি লাইনের ফল আগে, তারপর বিয়োগ।
import re
div = lambda a, b: abs(a) // abs(b) * (1 if (a < 0) == (b < 0) else -1)
OPS = {"+": int.__add__, "-": int.__sub__, "*": int.__mul__, "/": div}
def parse(src, env, errs, left_assoc=True): # inherited = parameters, synthesized = return value
toks, pos = [(m.group(), m.start() + 1) for m in re.finditer(r"\w+|\S", src)] + [("$", 0)], 0
def eat(): nonlocal pos; pos += 1; return toks[pos - 1]
def F(env): # F -> num | id | ( E ) synthesized (type, val, col)
t, col = eat()
if t == "(": a = E(env); eat(); return a
if t.isdigit(): return ("Int", int(t), col)
if t in env: return (*env[t], col)
errs.append(f"1:{col}: error: undefined variable '{t}'"); return (None, None, col)
def combine(op, l, r): # the semantic rule of X -> X op Y
for t, v, col in (l, r):
if t not in (None, "Int"): errs.append(f"1:{col}: error: type mismatch: expected Int, found {t}")
ok = l[0] == r[0] == "Int" and None not in (l[1], r[1]) and (op, r[1]) != ("/", 0)
return ("Int", OPS[op](l[1], r[1]) if ok else None, l[2])
def rest(left, ops, sub, env): # E' -> op T E' | ε with E'.left inherited
if toks[pos][0] not in ops: return left # ε: E'.syn = E'.left
op, _ = eat()
if left_assoc: return rest(combine(op, left, sub(env)), ops, sub, env) # E'1.left = left op T
return combine(op, left, rest(sub(env), ops, sub, env)) # synthesized only
T = lambda env: rest(F(env), "*/", F, env)
E = lambda env: rest(T(env), "+-", T, env)
return E(env)
env = {"p": ("Int", 1040), "ok": ("Bool", True)}
for src in ["20 - 5 - 3", "100 / 10 / 5", "p - p / 10", "ok - ok / 10", "(q + 1) * 2"]:
errs = []; good = parse(src, env, errs); wrong = parse(src, env, [], left_assoc=False)
print(f"{src:13} L-attributed: {good[1]!s:5} right-recursive: {wrong[1]!s:5}",
*sorted(errs, key=lambda m: int(m.split(":")[1])))
env = {} # a let-chain: S(i+1).env = S(i).env + {name: E}
for stmt in ["let q = 2", "let p = q * 520", "print(p - p / 10)"]:
name, e = stmt[4:].split(" = ") if stmt.startswith("let") else (None, stmt[6:-1])
t, v, _ = parse(e, env, [])
print(f"env in: {env} -> {stmt}: {t} {v}"); env = {**env, name: (t, v)} if name else envআসল আউটপুট (ব্রাউজারের Python):
20 - 5 - 3 L-attributed: 12 right-recursive: 18
100 / 10 / 5 L-attributed: 2 right-recursive: 50
p - p / 10 L-attributed: 936 right-recursive: 936
ok - ok / 10 L-attributed: None right-recursive: None 1:1: error: type mismatch: expected Int, found Bool 1:6: error: type mismatch: expected Int, found Bool
(q + 1) * 2 L-attributed: None right-recursive: None 1:2: error: undefined variable 'q'
env in: {} -> let q = 2: Int 2
env in: {'q': ('Int', 2)} -> let p = q * 520: Int 1040
env in: {'q': ('Int', 2), 'p': ('Int', 1040)} -> print(p - p / 10): Int 936
প্রথম দুই লাইনে inherited attribute-এর কারণ স্পষ্ট: 20 - 5 - 3 সঠিকভাবে 12, আর শুধু-synthesized রূপ দেয় 18, কারণ সে 20 - (5 - 3) হিসাব করে; ভাগে আরও খারাপ, 2-এর বদলে 50. তৃতীয় লাইনে দুটিই 936, কারণ / নিচের স্তরে, তাই ভুলটি লুকিয়ে থাকে; একটি পরীক্ষায় শুধু এমন উদাহরণ থাকলে ভুল ধরা পড়ত না। চতুর্থ লাইনে দুটি type error, অবস্থান 1:1 আর 1:6. Reference একই expression print(…);-এ মুড়ে পড়লে প্রতিটি column ঠিক ৬ বেশি দেয়: 3:7 আর 3:12, বার্তা অক্ষরে অক্ষরে এক। আর (q + 1) * 2-এ reference-এর 1:8: error: undefined variable 'q'. Error-এর পরে type থাকে Int, মান থাকে অজানা (None), যাতে একটি ভুল থেকে আরও ভুলের ঢল না নামে, reference-এর মতোই। শেষ তিন লাইন stepper-এর let-শিকল: প্রতিটি statement-এর env.in আগেরটির env.out.
কয়েকটি উদাহরণে মিল যথেষ্ট নয়। ল্যাবে একটি differential test চালিয়েছি: seed 53 দিয়ে ৩০০০টি এলোমেলো expression (সংখ্যা ০–৫৯, p, k, Bool ok, বন্ধনী, চারটি operator, গভীরতা ৪ পর্যন্ত), প্রতিটি reference-এ let p = 1040; let k = 7; let ok = true;-এর পরে print(…);-এ মুড়ে check আর run, আর ব্রাউজারের parse-এ:
~/haat/attr $ python -B diff_b2.py
expressions 3000: same 3000 (values 1404, static errors 1590, division by zero 6); skipped big 0
৩০০০-এ ৩০০০: ১৪০৪টিতে একই মান, ১৫৯০টিতে একই error-তালিকা (অবস্থানসহ, ক্রমসহ), আর ৬টিতে দুই পক্ষই শূন্য দিয়ে ভাগ ধরেছে। প্রথম চেষ্টায় অবশ্য মেলেনি: p / ok * 19 - 31 / 0-এর মতো expression-এ ব্রাউজারের কোড type error-এর আগেই শূন্য দিয়ে ভাগে থেমে যাচ্ছিল। Attribute-এর ভাষায়, val-এর নিয়ম সব ক্ষেত্রে সংজ্ঞায়িত ছিল না; সারানো হয়েছে “ভাগফল শূন্য হলে val অজানা” নিয়মে।
যেখানে বাঁ থেকে ডানের শিকল যথেষ্ট নয়
Stepper-এর শেষ ধাপটি গুরুত্বপূর্ণ। Haat-এর দুটি নিয়ম ডান দিকের খবর চায়। Decision 16: একটি block-এ x কোথাও ঘোষিত হলে, ঘোষণার আগে x-এর ব্যবহার error, বাইরে x থাকলেও। Decision 17: top-level function ঘোষণার আগেই ডাকা যায়। দুটির জন্যই একটি block-এর সব ঘোষণার তালিকা লাগে, যা একটি synthesized attribute (নিচ থেকে ওপরে, পুরো তালিকা জুড়ে), আর তারপর সেটি inherited হয়ে প্রতিটি statement-এ নামে। এমন SDD L-attributed নয়, কারণ Si-এর inherited নির্ভর করে ডান ভাই Sj (j > i)-এর ওপর। সমাধান দুই হাঁটা, আর reference ঠিক তাই করে: resolver.py-র declared_names(stmts) আগে block-এর সব নাম জোগাড় করে pending-এ রাখে, আর program() প্রথম loop-এ সব FnDecl ঘোষণা করে, দ্বিতীয় loop-এ দেহ দেখে। typechecker.py-র program()-এও একই দুই loop.
৪ · নির্ভরতার গ্রাফ আর হিসাবের ক্রম
S-attributed-এ postorder, L-attributed-এ বাঁ থেকে ডানে হাঁটা। কিন্তু সাধারণ SDD-তে? সাধারণ উত্তর আসে গ্রাফ থেকে। একটি গাছের জন্য attribute dependency graph বানান: প্রতিটি attribute instance একটি vertex, আর প্রতিটি নিয়ম b = f(c1, …, ck)-এর জন্য প্রতিটি cj থেকে b-তে একটি edge. তারপর গ্রাফটিকে topological sort করুন, আর সেই ক্রমে নিয়ম চালান। এখানে পদ্ধতি Kahn-এর algorithm: যার কোনো অপেক্ষা নেই, সে সারিতে; সারি থেকে একটি বের করে হিসাব, আর তার ওপর নির্ভরশীলদের অপেক্ষা এক কমানো। Topological sort-এর পূর্ণ আলোচনা DSA কোর্সের পর্ব ৪২-এ।
নিচের block একটি সাধারণ evaluator: অংশ ১-এর টেবিলের নিয়মগুলো RULES-এ, প্রতিটি “লক্ষ্য, উৎস, function” আকারে (0 = node নিজে, 1, 2 = সন্তান)। evaluate গাছের node-গুলোকে preorder-এ নম্বর দেয় (Bin0, Var1 …), প্রতিটি নিয়ম থেকে instance আর edge বানায়, Kahn চালায়, আর সব instance শেষ না হলে চক্রের কথা বলে। শেষে একটি ইচ্ছাকৃত ভুল নিয়ম: বাঁ সন্তানের env নাকি মা-বাবার type-এর ওপর নির্ভর করে।
from collections import deque; from types import SimpleNamespace
N = lambda prod, *kids, lex=None: SimpleNamespace(prod=prod, kids=list(kids), lex=lex) # a tree node
div = lambda a, b: abs(a) // abs(b) * (1 if (a < 0) == (b < 0) else -1) # C-style: toward zero
cp = lambda n, x: x # a copy rule: hand the value on unchanged
OPS = {"+": (int.__add__, "ADD"), "-": (int.__sub__, "SUB"), "*": (int.__mul__, "MUL"), "/": (div, "DIV")}
RULES = { # (target, sources, f): 0 = this node, 1 and 2 = children
"Num": [("0.val", [], lambda n: int(n.lex)), ("0.type", [], lambda n: "Int"), ("0.code", [], lambda n: [f"CONST {n.lex}"])],
"Var": [("0.val", ["0.env"], lambda n, e: e[n.lex][1]), ("0.type", ["0.env"], lambda n, e: e[n.lex][0]),
("0.code", [], lambda n: [f"LOAD {n.lex}"])],
"Bin": [("1.env", ["0.env"], cp), ("2.env", ["0.env"], cp), ("0.val", ["1.val", "2.val"], lambda n, a, b: OPS[n.lex][0](a, b)),
("0.type", ["1.type", "2.type"], lambda n, a, b: "Int" if a == b == "Int" else "error"),
("0.code", ["1.code", "2.code"], lambda n, a, b: a + b + [OPS[n.lex][1]])]}
def evaluate(root, env0): # dependency graph of attribute instances + Kahn's algorithm
nodes, users = [], {}
def walk(n): n.id = len(nodes); nodes.append(n); [walk(c) for c in n.kids]
walk(root); at = lambda n, r: ((n if r[0] == "0" else n.kids[int(r[0]) - 1]).id, r[2:])
rules = {at(n, t): ([at(n, s) for s in ss], f, n) for n in nodes for t, ss, f in RULES[n.prod]}
val = {(0, "env"): env0} # the root's inherited attribute comes from outside
need = {t: sum(s not in val for s in ss) for t, (ss, f, n) in rules.items()}
for t, (ss, f, n) in rules.items(): [users.setdefault(s, []).append(t) for s in ss]
ready, order = deque(t for t in rules if need[t] == 0), []
while ready:
t = ready.popleft(); ss, f, n = rules[t]
val[t] = f(n, *[val[s] for s in ss]); order.append(f"{nodes[t[0]].prod}{t[0]}.{t[1]}")
for u in users.get(t, []):
need[u] -= 1
if need[u] == 0: ready.append(u)
if len(order) < len(rules): raise ValueError(f"circular: {len(rules) - len(order)} of {len(rules)} never ready")
return val, order
e = N("Bin", N("Var", lex="p"), N("Bin", N("Var", lex="p"), N("Num", lex="10"), lex="/"), lex="-")
val, order = evaluate(e, {"p": ("Int", 1040)})
print(len(order), "rules:", *order); print(val[0, "val"], val[0, "type"], val[0, "code"])
RULES["Bin"].append(("1.env", ["0.type"], cp)) # a bad rule: the left child's env needs the type
try: evaluate(e, {"p": ("Int", 1040)})
except ValueError as err: print(err)আসল আউটপুট (ব্রাউজারের Python):
19 rules: Var1.env Bin2.env Var1.code Var3.code Num4.val Num4.type Num4.code Var1.val Var1.type Var3.env Num4.env Bin2.code Var3.val Var3.type Bin0.code Bin2.val Bin2.type Bin0.val Bin0.type
936 Int ['LOAD p', 'LOAD p', 'CONST 10', 'DIV', 'SUB']
circular: 10 of 19 never ready
১৯টি নিয়ম চলেছে (মূলের env বাইরে থেকে দেওয়া, তাই মোট instance ২০)। ক্রমটি postorder নয়: Var1.env আর Bin2.env সবার আগে, তারপর ছড়ানো পাতাগুলো, আর Bin0.code আসে Bin2.val-এরও আগে। তবু ফল একই: 936, Int, আর LOAD p, LOAD p, CONST 10, DIV, SUB, যা reference-এর dis-এ let p = 1040; print(p - p / 10);-এর LOAD_GLOBAL 0 ; p, LOAD_GLOBAL 0 ; p, CONST 1 ; 10, DIV, SUB-এর সঙ্গে হুবহু এক ক্রমে। শেষ লাইনে ভুল নিয়মটি দুটি Binary node-এই বসেছে, তাই দুটি চক্র: Var1.env → Var1.type → Bin0.type → Var1.env আর একই রকম ডান দিকে। ১৯-এর ১০টি instance কখনো তৈরি হয় না; evaluator চুপচাপ ভুল মান না দিয়ে থামে।
1need[t] = তৈরি নয় এমন উৎসের সংখ্যা2ready = need শূন্য এমন সব3t = ready.popleft(); val[t] = f(…)4t-এর প্রতিটি user u: need[u] -= 15need[u] == 0 হলে ready-তে u6সব হলো? না হলে চক্র
| এইমাত্র হলো | |
| ready | |
| অপেক্ষায় | |
| মোট হলো |
- শুরু. মূলের
envবাইরে থেকে দেওয়া, তাই যেসব নিয়ম শুধু সেটি চায় (Var1.env,Bin2.env) আর যারা কিছুই চায় না (দুটিVar.code,Num4-এর তিনটি) তারা সারিতে: ৭টি। বাকি ১২টি অপেক্ষায়। - প্রথম দুটি বের হলো.
Var1.envহলেVar1.valআরVar1.type-এর অপেক্ষা শূন্য;Bin2.envহলেVar3.envআরNum4.env-এর। চারজন সারির পেছনে যোগ হলো; অপেক্ষায় এখন ৮টি। - পাঁচটি পাতা. সারির ক্রমে
Var1.code,Var3.codeআরNum4-এর তিনটি। শেষটি,Num4.code, হলেBin2.code-এর দুটি উৎসই তৈরি, তাই সে সারিতে ঢোকে। - Env তলায়.
Var1.val= 1040,Var3.envহলো, ফলেVar3.val,Var3.typeসারিতে;Bin2.codeহলেBin0.code-ও। লক্ষ করুন,Num4.env-ও হিসাব হলো, যদিও কেউ সেটি পড়ে না। - Code মূলে আগে পৌঁছায়.
Var3.val,Var3.type-এর পরেBin0.code: পাঁচটি instruction তৈরি, অথচ মূলের val এখনো অজানা। Code কোনো env চায় না বলে সে আগে দৌড়ায়। - শেষ.
Bin2.val= 104, তারপরBin0.val= 936,Bin0.type= Int. সারি খালি, আর হিসাব হওয়া নিয়ম ১৯ = মোট নিয়ম ১৯: গ্রাফে চক্র নেই। কম হলে বাকিগুলো চক্রে আটকে আছে।
একই গ্রাফ চোখে দেখতে নিচের JavaScript block-টি চালান। এটি নিয়মগুলো “লক্ষ্য<উৎস” আকারে Python block-এর একই ক্রমে নেয়, একই Kahn চালায়, প্রতিটি instance-কে তার “স্তরে” (দীর্ঘতম নির্ভরতা-পথের দৈর্ঘ্য) বসিয়ে আঁকে (হলুদ inherited, সবুজ synthesized), তারপর ভুল নিয়মটি বসিয়ে দেখে কোনগুলো আটকায়। ছবি চওড়া হলে পাশে টেনে দেখুন।
// p - p / 10: প্রতিটি attribute instance-এর নিয়ম "লক্ষ্য<উৎস", Python block-এর একই ক্রমে
const R = ["Var1.env<Bin0.env", "Bin2.env<Bin0.env", "Bin0.val<Var1.val Bin2.val", "Bin0.type<Var1.type Bin2.type",
"Bin0.code<Var1.code Bin2.code", "Var1.val<Var1.env", "Var1.type<Var1.env", "Var1.code<", "Var3.env<Bin2.env",
"Num4.env<Bin2.env", "Bin2.val<Var3.val Num4.val", "Bin2.type<Var3.type Num4.type", "Bin2.code<Var3.code Num4.code",
"Var3.val<Var3.env", "Var3.type<Var3.env", "Var3.code<", "Num4.val<", "Num4.type<", "Num4.code<"];
function kahn(rules, given) { // ফেরত: ক্রম, প্রতিটির স্তর, আর আটকে থাকা
const deps = new Map(rules.map(r => [r.split("<")[0], r.split("<")[1].split(" ").filter(Boolean)]));
const need = new Map(), users = new Map(), order = [], level = new Map([[given, 0]]);
for (const [t, ss] of deps) {
need.set(t, ss.filter(s => s !== given).length);
ss.forEach(s => users.set(s, [...(users.get(s) || []), t]));
}
const ready = [...deps.keys()].filter(t => need.get(t) === 0);
while (ready.length) {
const t = ready.shift(); order.push(t);
level.set(t, 1 + Math.max(-1, ...deps.get(t).map(s => level.get(s))));
for (const u of users.get(t) || []) { need.set(u, need.get(u) - 1); if (need.get(u) === 0) ready.push(u); }
}
return { deps, order, level, stuck: [...deps.keys()].filter(t => !order.includes(t)) };
}
const g = kahn(R, "Bin0.env"), rows = [], pos = new Map(), W = 92, H = 58;
for (const [t, l] of g.level) (rows[l] = rows[l] || []).push(t);
rows.forEach((row, y) => row.forEach((t, x) => pos.set(t, [10 + x * W, 14 + y * H])));
let svg = "";
for (const [t, ss] of g.deps) for (const s of ss) {
const [x1, y1] = pos.get(s), [x2, y2] = pos.get(t);
svg += `<line x1="${x1 + 40}" y1="${y1 + 24}" x2="${x2 + 40}" y2="${y2}" stroke="#64748b"/>`;
}
for (const [t, [x, y]] of pos) svg += `<rect x="${x}" y="${y}" width="82" height="24" rx="5" fill="${t.endsWith("env") ? "#fef3c7" : "#dcfce7"}" stroke="#334155"/><text x="${x + 41}" y="${y + 16}">${t}</text>`;
document.getElementById("g").innerHTML = `<svg width="${10 + Math.max(...rows.map(r => r.length)) * W}" height="${rows.length * H}" font-size="12" text-anchor="middle">${svg}</svg>`;
console.log(`${g.deps.size + 1}টি instance, ${[...g.deps.values()].flat().length}টি edge, ${rows.length}টি স্তর`);
console.log("স্তরে স্তরে:", rows.map(r => r.length).join(" + "));
console.log("Kahn-এর ক্রম:", g.order.slice(0, 7).join(" "), "…", g.order.at(-1));
const bad = kahn(R.map(r => r.replace(/^(Var[13])\.env<Bin(\d)\.env$/, "$1.env<Bin$2.type")), "Bin0.env");
console.log(`ভুল নিয়মে: ${bad.order.length}টি হিসাব হলো, ${bad.stuck.length}টি চক্রে আটকে →`, bad.stuck.join(" "));আসল আউটপুট (ব্রাউজারের JavaScript), গ্রাফের ছবির নিচে:
20টি instance, 20টি edge, 6টি স্তর
স্তরে স্তরে: 6 + 3 + 5 + 2 + 2 + 2
Kahn-এর ক্রম: Var1.env Bin2.env Var1.code Var3.code Num4.val Num4.type Num4.code … Bin0.type
ভুল নিয়মে: 9টি হিসাব হলো, 10টি চক্রে আটকে → Var1.env Bin0.val Bin0.type Var1.val Var1.type Var3.env Bin2.val Bin2.type Var3.val Var3.type
২০টি instance, ২০টি edge, ৬টি স্তর: প্রথম স্তরে মূলের env আর পাঁচটি নির্ভরতাহীন নিয়ম, শেষ স্তরে Bin0.val আর Bin0.type. দীর্ঘতম পথ Bin0.env → Bin2.env → Var3.env → Var3.val → Bin2.val → Bin0.val: এর চেয়ে কম ধাপে মূলের মান জানা অসম্ভব, যত প্রসেসরই থাকুক। এক স্তরের instance-গুলো পরস্পর-স্বাধীন, তাই সমান্তরালে হিসাব করা যেত। ভুল নিয়মে Python-এর মতোই ৯টি হলো আর ১০টি আটকাল, আর আটকানোদের তালিকা দেখায় ঠিক কোন দুটি চক্র।
একটি গাছের dependency graph-এ চক্র না থাকলে প্রতিটি attribute instance-এর মান অনন্য, আর যেকোনো topological ক্রমে নিয়ম চালালে একই মান আসে।
প্রমাণের রূপরেখা. (১) চক্রহীন গ্রাফে প্রতিটি vertex-এর একটি “গভীরতা” আছে: তার কাছে আসা দীর্ঘতম পথের দৈর্ঘ্য (JavaScript block-এর স্তর)। (২) গভীরতা ধরে induction: গভীরতা ০-এর instance-এর মান আসে token বা বাইরের ইনপুট থেকে, তাই নির্দিষ্ট। (৩) গভীরতা d-র instance b = f(c1, …, ck)-এর প্রতিটি c-র গভীরতা d-র কম, তাই induction অনুযায়ী তাদের মান নির্দিষ্ট, আর f একটি function বলে b-র মানও নির্দিষ্ট। (৪) যেকোনো topological ক্রম b-কে তার সব c-র পরে চালায়, তাই ঠিক এই মানই পায়। ∎ (শর্ত: f-গুলো pure. Side effect থাকলে ক্রম গুরুত্বপূর্ণ হয়ে ওঠে, অংশ ৫-এ দেখবেন।)
একটি নির্দিষ্ট গাছে চক্র খোঁজা সহজ: Kahn নিজেই বলে দেয়। কঠিন প্রশ্ন grammar-এর স্তরে: কোনো গাছে কি চক্র হতে পারে? Knuth-এর প্রবন্ধেই এই circularity যাচাইয়ের একটি algorithm ছিল (পরে ১৯৭১ সালের একটি সংশোধনীতে ঠিক করা হয় বলে উল্লেখ পাওয়া যায়), আর Jazayeri, Ogden ও Rounds ১৯৭৫ সালে দেখান যে সাধারণ ক্ষেত্রে এই সমস্যা স্বভাবতই exponential সময়ের বলে পরিচিত। তাই বাস্তব tool সাধারণত ছোট কিন্তু দ্রুত-যাচাইযোগ্য শ্রেণিতে কাজ করে: S-attributed ⊂ L-attributed ⊂ ordered attribute grammar (Uwe Kastens, ১৯৮০) ⊂ চক্রহীন।
| কৌশল | কীভাবে | কোথায় দেখবেন |
|---|---|---|
| গ্রাফ-চালিত (data-driven) | পুরো গ্রাফ বানিয়ে topological ক্রম, এই পর্বের evaluate | শেখানো আর ছোট গাছ; সব instance হিসাব হয়, দরকার না থাকলেও |
| হাঁটা-ভিত্তিক (pass-based) | আগে থেকে ঠিক করা এক বা কয়েকটি হাঁটা: postorder, বাঁ থেকে ডানে DFS | yacc-এর $$, recursive descent, হাতে লেখা compiler-এর pass |
| চাহিদা-চালিত (demand-driven) | কেউ একটি attribute চাইলে তবেই হিসাব, ফল memoization-এ রাখা | JastAdd-এর মতো tool, আর editor-এর ভেতরের বিশ্লেষণ |
তৃতীয় কৌশলটি আসলে পর্ব ১৯-এর call-by-need: Num4.env-এর মতো অদরকারি instance কখনো হিসাব হয় না, আর চক্রে পড়লে “নিজেকে চাইতে গিয়ে নিজেকে পাওয়া” দিয়ে ধরা যায়।
৫ · SDD বনাম translation scheme — three-address code বানানো
এ পর্যন্ত নিয়মগুলো pure: কোনো মান বদলায় না, কিছু ছাপে না। Code generation-এ কিন্তু দুটি জিনিস স্বাভাবিকভাবে side effect চায়: নতুন অস্থায়ী নাম (t1, t2) বানানো, আর instruction “ছাপা”। এখানে দুই ধাঁচ আলাদা হয়ে যায়।
SDD (pure)
প্রতিটি নিয়ম শুধু মান হিসাব করে। Temp-এর নম্বরও একটি attribute: inherited n (পরের খালি নম্বর) আর synthesized n_out, বাঁ সন্তানের n_out ডান সন্তানের n. ক্রম গ্রাফ ঠিক করে।
Translation scheme (SDT)
Production-এর ভেতরে নির্দিষ্ট জায়গায় { … } কাজ, যা parser বা হাঁটা ঠিক সেখানে পৌঁছালে চলে: E → E1 op E2 { E.addr = newtemp(); emit(…) }. ক্রম লেখাতেই বাঁধা; global counter আর output চলে।
Translation scheme-এ ক্রমটিই অর্থ। কাজটি শেষে বসলে (postfix scheme) সন্তানদের code আগে বেরোয়, ঠিক postorder; একটি stack machine-এর জন্য এটুকুই যথেষ্ট। নিচের block তিনটি রূপ পাশাপাশি চালায়: pure SDD, translation scheme আর postfix stack code. Three-address code-এর বিস্তারিত পর্ব ৬২-তে (Intermediate representation — three-address code আর control flow graph); এখানে শুধু তার attribute-ভিত্তিক জন্ম।
def sdd(e, n): # pure attributes: inherited n = next temp number; synthesized (addr, code, n_out)
if isinstance(e, str): return e, [], n # a name or a number is its own address
if e[0] == "call": # ("call", f, [args])
code, addrs = [], []
for a in e[2]: addr, c, n = sdd(a, n); code += c; addrs.append(addr)
t = f"t{n}"; return t, code + [f"param {a}" for a in addrs] + [f"{t} = call {e[1]}, {len(addrs)}"], n + 1
op, l, r = e
la, lc, n = sdd(l, n) # left child first: its n_out ...
ra, rc, n = sdd(r, n) # ... is the right child's inherited n
t = f"t{n}"; return t, lc + rc + [f"{t} = {la} {op} {ra}"], n + 1
code, temps = [], 0 # a translation scheme: actions + globals
def newtemp():
global temps; temps += 1; return f"t{temps}"
def scheme(e): # E -> E1 op E2 { E.addr = newtemp(); emit(E.addr '=' E1.addr op E2.addr) }
if isinstance(e, str): return e
op, l, r = e; la = scheme(l); ra = scheme(r)
t = newtemp(); code.append(f"{t} = {la} {op} {ra}"); return t
NAMES = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV"}
def postfix(e): # emit after both children: postorder = stack code
if isinstance(e, str): return [("CONST " if e.isdigit() else "LOAD ") + e]
return postfix(e[1]) + postfix(e[2]) + [NAMES[e[0]]]
e = ("-", ("*", "qty", "unit"), ("/", "p", "10"))
addr, tac, _ = sdd(e, 1); print("sdd: ", " ; ".join(tac), " addr =", addr)
scheme(e); print("scheme:", " ; ".join(code)); print("stack: ", " ; ".join(postfix(e)))
first = ("+", ("call", "price", ["2", "520"]), ("call", "delivery", [("call", "price", ["2", "520"])]))
addr, tac, n = sdd(first, 1); print(*tac, f"first = {addr}", sep="\n"); print("temps used:", n - 1)আসল আউটপুট (ব্রাউজারের Python):
sdd: t1 = qty * unit ; t2 = p / 10 ; t3 = t1 - t2 addr = t3
scheme: t1 = qty * unit ; t2 = p / 10 ; t3 = t1 - t2
stack: LOAD qty ; LOAD unit ; MUL ; LOAD p ; CONST 10 ; DIV ; SUB
param 2
param 520
t1 = call price, 2
param 2
param 520
t2 = call price, 2
param t2
t3 = call delivery, 1
t4 = t1 + t3
first = t4
temps used: 4
প্রথম দুই লাইন অক্ষরে অক্ষরে এক: pure SDD আর global newtemp()-ওয়ালা scheme একই three-address code দেয়, কারণ দুটিই বাঁ সন্তান আগে দেখে। Pure রূপে সেই “আগে”-টি লেখা আছে attribute-এ (n-এর শিকল); scheme-এ লেখা আছে কোডের ক্রমে। তৃতীয় লাইনের stack code-এর ক্রম reference-এর dis-এর সঙ্গে মেলে (let qty = 2; let unit = 520; let p = 1040; print(qty * unit - p / 10);-এ LOAD_GLOBAL ×২, MUL, LOAD_GLOBAL, CONST, DIV, SUB; run দেয় 936). শেষ অংশে bazar.haat-এর লাইন ১০-এর initializer: call-এর জন্য প্রচলিত param আর call f, n রূপ, চারটি temp. Argument-গুলো বাঁ থেকে ডানে, আর বাইরের +-এর বাঁ দিক আগে, Haat-এর decision 12 অনুযায়ী; reference-এর dis-এও price-এর call আগে, delivery-এর পরে।
1leaf: addr = নাম, code = [], n_out = n2la, lc, n = sdd(left, n)3ra, rc, n = sdd(right, n)4t = "t" + n; emit t = la op ra5n_out = n + 1
| node | |
| n (inh) | |
| addr | |
| n_out |
- পাতা. মূল ডাকা হয় n = 1 দিয়ে; সেটি বাঁ সন্তান
qty * unit-এ, আর সেখান থেকেqty-তে নামে। একটি নামের ঠিকানা সে নিজেই, code খালি, n বদলায় না।unit-ও তাই। qty * unit. দুই সন্তান শেষ, n এখনো 1. তাই t = t1, একটি instruction, আরn_out= 2.p / 10. এর inherited n আসে বাঁ ভাইয়েরn_outথেকে: 2. তাই t2. এটিই L-attributed শর্তের “বাঁ ভাইয়ের attribute”.- মূল
-. বাঁয়ের code ‖ ডানের code ‖ নতুন লাইন t3 = t1 - t2;n_out= 4, অর্থাৎ ৩টি temp. মূলেরaddrt3: পুরো expression-এর মান সেখানে। - তিন রূপ. Scheme একই তিন লাইন দেয়; postfix stack code সাতটি instruction, reference-এর
dis-এর ক্রমে। একই গাছ, একই হাঁটা, ভিন্ন attribute.
Short-circuit: jump-এর ঠিকানাও inherited
Arithmetic-এ সব তথ্য নিচ থেকে ওঠে। কিন্তু a && b-এর code-এ একটি প্রশ্ন আছে যা নিচের node একা জানে না: “a মিথ্যা হলে কোথায় লাফ দেব?” Compiler-এর পাঠ্যবইয়ের প্রচলিত সমাধান: Bool expression B-কে দুটি inherited attribute দিন, B.true আর B.false (দুটি label). নিয়ম: B → B1 && B2-এ B1.true = একটি নতুন label (যেখানে B2 শুরু), B1.false = B.false, B2.true = B.true, B2.false = B.false. লক্ষ্য-ঠিকানা ওপর থেকে নামে, code নিচ থেকে ওঠে। Haat reference মান-ভিত্তিক একটি সরল রূপ নেয়; let a = true; let b = false; print(a && b);-এর dis (সত্যিকারের run, ফল false):
4 LOAD_GLOBAL 0 ; a
5 JUMP_IF_FALSE 8
6 LOAD_GLOBAL 1 ; b
7 JUMP 9
8 CONST 1 ; false
9 PRINT
এখানে 8 আর 9 লাফের ঠিকানা, যা &&-এর code বানানোর সময় তখনো জানা নেই। compiler.py আগে খালি লাফ বসায় আর পরে ঠিকানা ভরে দেয়, যাকে বলে backpatching: inherited ঠিকানা আগে থেকে জানা না থাকলে এক হাঁটায় কাজ সারার কৌশল। পুরো আলোচনা পর্ব ২৭ আর পর্ব ৬২-তে।
৬ · হাতে লেখা pass-এর ভেতরের attribute grammar
Haat reference কোনো attribute-grammar tool ব্যবহার করে না; প্রতিটি অংশ হাতে লেখা Python. তবু ভেতরে তাকালে attribute সর্বত্র। নিয়মটি মনে রাখার মতো: একটি recursive function-এর parameter হলো inherited attribute, তার return value হলো synthesized attribute, আর id(node)-চাবির একটি dict হলো attribute-এর ভান্ডার (পর্ব ৪৯-এর side table).
| ফাইল আর জায়গা | Attribute | ধরন |
|---|---|---|
resolver.py: self.scopes | দৃশ্যমান নামের খাতা (env) | inherited (stack-এ push/pop) |
resolver.py: declared_names(), pending | block-এর সব ঘোষণা | synthesized, তারপর inherited: দুই হাঁটা (decision 16) |
resolver.py: self.nslots | পরের খালি slot | শিকল-বাঁধা counter, temp-নম্বরের মতো |
resolver.py: uses, decls | নামের ব্যবহার → Binding | side table-এ রাখা attribute |
typechecker.py: expr()-এর return | expression-এর type | synthesized |
typechecker.py: self.ret | ঘেরা function-এর ফেরত type | inherited |
typechecker.py: always_returns() | “সব পথ return করে” | synthesized Bool (decision 21) |
compiler.py: expr()-এর emit | bytecode | postfix translation scheme |
হাতে লেখা compiler সাধারণত এক বা কয়েকটি attribute-এর জন্য একটি pass লেখে, প্রতিটি একটি visitor বা একটি recursive function. কোন attribute কোন pass-এ যাবে, সেটি নির্ধারণ করে নির্ভরতা: type-এর জন্য resolver-এর Binding লাগে, তাই resolver আগে; bytecode-এর জন্য slot লাগে, তাই compiler পরে। অর্থাৎ pass-এর ক্রম আসলে attribute-নির্ভরতার গ্রাফের একটি মোটা দাগের topological sort. পর্ব ৫২-এর (Type checker বাস্তবায়ন) checker আর পর্ব ৫৪-এর (অন্য semantic check) বিশ্লেষণগুলোকেও এভাবে পড়া যায়।
Tool-এর জগতে কয়েকটি নাম জেনে রাখুন (বিস্তারিত দাবি নয়, শুধু পরিচয়)। yacc আর Bison S-attributed ধাঁচ দেয়, সঙ্গে নিয়মের মাঝখানে কাজ বসানোর সুবিধা (mid-rule action). ANTLR-এ একটি নিয়মের parameter আর return value লেখা যায়, যা L-attributed ধাঁচ। Lund University-র JastAdd আর University of Minnesota-র Silver পূর্ণ attribute-grammar ভিত্তিক compiler-নির্মাণ ব্যবস্থা হিসেবে পরিচিত।
আরও গভীরে: সাধারণ attribute grammar-এ মান হয় সংখ্যা, type বা তালিকা। Reference attribute grammar-এ (Görel Hedin-এর ২০০০ সালের কাজের সঙ্গে যুক্ত বলে উল্লেখ পাওয়া যায়) মান হতে পারে গাছের অন্য একটি node, যেমন একটি নামের ব্যবহার থেকে সরাসরি তার ঘোষণার node; এতে name resolution আর symbol table-কে আলাদা কাঠামো ছাড়াই লেখা যায়। JastAdd এর ওপর চাহিদা-চালিত হিসাব আর memoization দেয়, আর কিছু ক্ষেত্রে চক্রযুক্ত attribute-ও fixpoint পর্যন্ত হিসাব করতে পারে বলে তার নথিতে বলা আছে। ১৯৮০-এর দশকে Thomas Reps ও Tim Teitelbaum-এর Synthesizer Generator-এর মতো editor-নির্মাণ ব্যবস্থায় incremental attribute evaluation গুরুত্ব পায়: একটি অক্ষর বদলালে শুধু প্রভাবিত instance-গুলো নতুন করে হিসাব, যে ধারণা আজকের language server-এর incremental বিশ্লেষণের পূর্বসূরি।
পরীক্ষা ও ইন্টারভিউতে: (১) “Synthesized আর inherited attribute-এর পার্থক্য উদাহরণসহ লিখুন” — synthesized সন্তান থেকে (E.val), inherited মা-বাবা বা বাঁ ভাই থেকে (env, E′.left). (২) “প্রতিটি S-attributed SDD কি L-attributed?” — হ্যাঁ, inherited না থাকলে শর্ত আপনা থেকেই মানে। (৩) “E → T E′ grammar-এ 9 - 5 - 2-এর annotated parse tree আঁকুন” — E′.left শিকল 9 → 4 → 2, উত্তর 2. (৪) “a * b + c-এর three-address code দিন” — t1 = a * b, t2 = t1 + c. (৫) “Dependency graph-এ চক্র থাকলে কী হয়?” — কোনো বৈধ হিসাব-ক্রম নেই; SDD ওই গাছের জন্য অর্থহীন।
৭ · AI-এর যুগে attribute grammar
“এই grammar-এর জন্য three-address code বানানোর SDD লিখে দাও” — AI assistant এমন প্রশ্নে দ্রুত সুন্দর টেবিল দেয়, আর পাঠ্যবইয়ের উদাহরণে প্রায়ই ঠিক থাকে। ভুল আসে কিনারায়। এই বিষয়ে বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
Left recursion সরানোর পরে শুধু synthesized নিয়ম: 20 - 5 - 3 = 18 | বিয়োগ আর ভাগের শিকল দিয়ে পরীক্ষা; শুধু +, * বা precedence-মেশানো উদাহরণ ভুল লুকায় |
| “L-attributed” বলা, অথচ একটি inherited নিয়ম ডান ভাইয়ের ওপর নির্ভর করে | প্রতিটি inherited নিয়মের উৎস একে একে মিলিয়ে দেখা: মা-বাবার inherited বা বাঁ ভাই ছাড়া কিছু আছে কি? |
Side effect-ওয়ালা কাজ (newtemp, emit) এমন জায়গায় বসানো, যেখানে ক্রম বদলে যায় | Scheme-টি চালিয়ে pure SDD-র ফলের সঙ্গে তুলনা |
এক ভাষার নিয়ম সবখানে চাপানো: Python-এর // (নিচের দিকে কাটা) ধরে Haat বা C-র ভাগ হিসাব | ঋণাত্মক সংখ্যায় reference বা আসল compiler চালানো (-7 / 2) |
| Tool নিয়ে বানানো দাবি: কোনো flag, directive বা “JastAdd-এর এই syntax” | Tool-এর নিজের documentation আর একটি ছোট সত্যিকারের run |
| Annotated tree-র মান নিজে বানিয়ে লেখা | Evaluator বা reference চালিয়ে মান মেলানো; AI-কে অনুমান করতে নিষেধ করা |
AI-কে SDD লেখার যন্ত্র না বানিয়ে পর্যালোচকের কাজ দিন:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন।
প্র ০১Knuth ১৯৬৮ সালে attribute grammar-এর formal রূপ দিলেন; তার আগে compiler কীভাবে “অর্থ” জুড়ত, আর নতুন কাঠামোটি কী যোগ করল?
১৯৫০-এর দশকের শেষ আর ১৯৬০-এর দশকের শুরুতে, FORTRAN আর ALGOL-এর কালে, context-free grammar (BNF) ভাষার রূপ লেখার মানদণ্ড হয়ে উঠছিল, কিন্তু অর্থের কোনো সমান মানের লেখা ছিল না। Compiler-লেখকেরা parser-এর ভেতরে কোড গুঁজে দিতেন: একটি নিয়ম মিললে একটি নির্দিষ্ট কাজ চলবে। Edgar Irons-এর ১৯৬১ সালের ALGOL 60 compiler-এর বর্ণনাকে প্রায়ই “syntax-directed” ধারণার প্রথম দিকের স্পষ্ট রূপ ধরা হয়: অনুবাদ চলে syntax-এর কাঠামো ধরে। কিন্তু এভাবে অর্থ আটকে থাকত parser-এর কাজের ক্রমে; কোন কাজ কখন চলবে, তা নির্ভর করত parsing পদ্ধতির ওপর।
Knuth-এর অবদান দুই দিকে। প্রথমত, তিনি অর্থকে ক্রম থেকে আলাদা করলেন: নিয়মগুলো শুধু বলে কোন মান কোন মান থেকে আসে, আর ক্রম আসে নির্ভরতা থেকে। এতে একই সংজ্ঞা LL, LR বা পুরো গাছের ওপর হাঁটা, যেকোনো পদ্ধতিতে চালানো যায়। দ্বিতীয়ত, তিনি inherited attribute-কে synthesized-এর সমান মর্যাদা দিলেন, আর দেখালেন যে দুটি মিলিয়ে এমন অর্থ লেখা যায় যা শুধু একটি দিয়ে খুব জটিল হয়ে যায়: তাঁর পরিচিত উদাহরণ ছিল ভগ্নাংশসহ বাইনারি সংখ্যার মান (যেমন 1101.01), যেখানে প্রতিটি অঙ্কের ওজন তার অবস্থান থেকে আসে, আর সেই অবস্থান ওপর থেকে নামে। সঙ্গে এল প্রথম কঠিন প্রশ্ন: নিয়মগুলোতে চক্র আছে কি না, আর সেটি কীভাবে যাচাই করা যায়।
পরের দুই দশকে এই কাঠামো থেকে ধারণার একটি পরিবার জন্মায়: L-attributed শ্রেণি (Lewis, Rosenkrantz আর Stearns-এর ১৯৭০-এর দশকের কাজের সঙ্গে যুক্ত), Kastens-এর ordered attribute grammar, আর পাঠ্যবইয়ের syntax-directed translation অধ্যায়, যা আজও compiler-কোর্সের পরিচিত অংশ। আজকের হাতে লেখা compiler সরাসরি attribute-grammar notation ব্যবহার না করলেও তাদের pass-গুলো এই ভাষাতেই সবচেয়ে পরিষ্কার ব্যাখ্যা করা যায়।
মূল উপলব্ধি: Attribute grammar-এর মূল কথা “কী হিসাব হবে” আর “কোন ক্রমে হবে” আলাদা করা। এই বিচ্ছেদ থেকেই আসে একই সংজ্ঞার নানা বাস্তবায়ন, চক্র-যাচাই আর নির্ভরতার ভিত্তিতে pass সাজানোর চিন্তা।
প্র ০২বাস্তব compiler-এর বেশিরভাগ কেন attribute-grammar tool দিয়ে না লিখে হাতে লেখা pass দিয়ে লেখা হয়?
প্রথম কারণ নিয়ন্ত্রণ। একটি বড় production compiler-এ type checking-এর সঙ্গে জড়িয়ে থাকে overload resolution, template বা generic-এর instantiation, implicit conversion, আর হাজারো বিশেষ ক্ষেত্র। এসব কাজ প্রায়ই নির্দিষ্ট ক্রমে আর নির্দিষ্ট cache-সহ করতে হয়, যাতে বড় কোডবেসে গতি থাকে। হাতে লেখা কোডে ক্রম, মেমরি আর ত্রুটি-বার্তার প্রতিটি শব্দ নিজের হাতে; একটি generator-এর ভেতরে সেই নিয়ন্ত্রণ কম, বা আলাদা করে শিখতে হয়।
দ্বিতীয় কারণ ত্রুটি-বার্তা আর error recovery. পর্ব ৫০-এ দেখেছেন, ভালো diagnostic দিতে parser আর checker-কে অনেক সময় নিয়ম “ভেঙে” এগোতে হয়: ভুল type পেয়েও None দিয়ে চালিয়ে যাওয়া, একটি ভুলের ঢল আটকানো। Pure attribute-নিয়মে এই আংশিক অবস্থা প্রকাশ করা যায়, যেমন এই পর্বের block-এ None দিয়ে করা হয়েছে, কিন্তু প্রতিটি নিয়মে তা মাথায় রাখতে হয়।
তৃতীয় কারণ সংস্কৃতি আর tooling. Debugger, profiler আর সাধারণ প্রোগ্রামারের পরিচিত ভাষায় লেখা কোড দলের সবাই পড়তে ও বদলাতে পারে; একটি বিশেষ DSL-এর জন্য আলাদা জ্ঞান আর build-ধাপ লাগে। অন্যদিকে attribute-grammar ব্যবস্থার সুবিধাও বাস্তব: নির্ভরতা স্বয়ংক্রিয়ভাবে সাজানো, অপ্রয়োজনীয় হিসাব বাদ, আর ভাষায় নতুন অংশ যোগ করলে আগের নিয়মে হাত না দেওয়া। JastAdd-এর মতো ব্যবস্থার পেছনের গবেষণায় এই modularity-কে বড় যুক্তি হিসেবে দেখানো হয়, আর গবেষণা-ভাষা বা domain-specific ভাষার জন্য এমন tool-এ লেখা compiler-এর কথা পাওয়া যায়।
মাঝের পথটিই সবচেয়ে প্রচলিত: হাতে লেখা কোড, কিন্তু attribute-এর ভাষায় ভাবা। এই পর্বের টেবিল দেখিয়েছে, Haat reference-এর প্রতিটি pass আসলে কয়েকটি attribute আর তাদের নির্ভরতা।
মূল উপলব্ধি: Attribute grammar একটি tool হিসেবে যতটা, চিন্তার কাঠামো হিসেবে তার চেয়ে বেশি টিকে আছে। কোন মান কোথা থেকে আসে, তা স্পষ্ট লিখলে হাতে লেখা pass-ও সাজানো আর পরীক্ষাযোগ্য হয়।
প্র ০৩Recursive descent parser-এ inherited attribute মানে parameter — তাহলে Pratt parser-এর loop কোথায় এই ছবিতে বসে?
Left recursion সরানো grammar E → T E′, E′ → op T E′ ∣ ε-এর L-attributed SDD-তে E′-এর একটি inherited attribute left: এ পর্যন্ত বাঁ দিকের ফল। এই পর্বের block-এ rest(left, …) function নিজেকে ডাকে নতুন left দিয়ে, আর ডাকটি function-এর শেষ কাজ: একটি tail call. Tail recursion-কে loop-এ রূপান্তর করলে left হয়ে যায় একটি local variable, যা প্রতিটি পাকে নতুন মান পায়: while next is op: left = combine(op, left, T()). ঠিক এটিই পর্ব ৪৮-এর Pratt parser-এর loop-এর হৃদয়, যেখানে left নামের variable-টি বাঁ দিকের গাছ বা মান ধরে রাখে।
অর্থাৎ Pratt parsing L-attributed হিসাবের একটি দক্ষ বাস্তবায়ন: inherited attribute একটি পরিবর্তনশীল local variable হয়ে গেছে, আর synthesized attribute হলো loop শেষে ফেরত দেওয়া মান। Binding power-এর তুলনা নতুন কিছু যোগ করে না attribute-এর দিক থেকে; সেটি শুধু ঠিক করে কোন token-এ loop থামবে, অর্থাৎ গাছের আকার।
এই দৃষ্টিভঙ্গির একটি ব্যবহারিক লাভ আছে। কেউ Pratt loop “সরল” করতে গিয়ে recursion-কে ডান দিকে সরালে (প্রথমে বাকিটা parse, তারপর জোড়া), ঠিক এই পর্বের left_assoc=False-এর ভুলটি ঘটে: বিয়োগ আর ভাগ ডান-সংযোজী হয়ে যায়। Attribute-এর ভাষায় ভুলটি এক বাক্যে ধরা যায়: inherited attribute-কে synthesized বানানো হয়েছে। পরীক্ষা করার উপায়ও একই: বাঁ-সংযোজী operator-এর তিন-পদের শিকল।
মূল উপলব্ধি: Parameter, accumulator আর loop variable একই ধারণার তিনটি পোশাক: বাঁ দিক থেকে আসা তথ্য, যা inherited attribute হিসেবে সংজ্ঞায়িত। এটি চিনতে পারলে parser-এর associativity bug খুঁজে পাওয়া সহজ হয়।
প্র ০৪Pure SDD আর translation scheme দুটিই একই three-address code দিল। তাহলে কোনটি কখন বেছে নেবেন?
Pure SDD-তে প্রতিটি মানের উৎস স্পষ্ট লেখা, এমনকি temp-নম্বরেরও (n আর n_out-এর শিকল)। এর তিনটি সুবিধা আছে। এক, উপপাদ্য ৫৩.৩ অনুযায়ী যেকোনো বৈধ ক্রমে একই ফল, তাই হিসাব সমান্তরালে বা চাহিদা অনুযায়ী করা যায়। দুই, প্রতিটি নিয়ম আলাদা করে পরীক্ষা করা যায়, কোনো global অবস্থা ছাড়া। তিন, একটি subtree আবার হিসাব করলে একই ফল আসে, যা incremental compiler বা editor-এর জন্য গুরুত্বপূর্ণ।
কিন্তু দাম আছে। Code-কে তালিকা হিসেবে জুড়তে হয় (lc + rc + […]), যা বড় function-এ বারবার কপি করে; বাস্তবে এর জন্য বিশেষ তালিকা-কাঠামো লাগে। আর counter-এর মতো জিনিস প্রতিটি নিয়মে হাতবদল করতে হয়, যা লেখা ঝামেলার আর ভুলপ্রবণ: একটি নিয়মে n_out ভুলে গেলে দুটি ভিন্ন expression একই temp পায়।
Translation scheme বাস্তবের কাছাকাছি: একটি emit buffer আর একটি global counter, আর গাছে একবার হাঁটা। Haat reference-এর compiler.py ঠিক এমন: expr() আগে সন্তানদের জন্য নিজেকে ডাকে, তারপর emit. শর্ত একটি: হাঁটার ক্রম স্থির আর জানা থাকতে হবে, কারণ এখন ক্রমই অর্থ। ক্রম বদলালে (যেমন ডান সন্তান আগে) ফল বদলায়: temp-গুলোর নম্বর বদলাবে, আর side effect-ওয়ালা কোডে instruction-এর ক্রমও, যা Haat-এর বাঁ থেকে ডানে মূল্যায়নের নিয়ম (decision 12) ভাঙতে পারে।
অনেক compiler দুটি মেলায়: বিশ্লেষণ (type, scope) pure বা প্রায়-pure, আর code generation একটি ভালোভাবে সংজ্ঞায়িত হাঁটার translation scheme.
মূল উপলব্ধি: যেখানে ক্রম-স্বাধীনতা আর পুনরায় হিসাব দরকার, সেখানে pure SDD; যেখানে একবারের দক্ষ output দরকার আর হাঁটার ক্রম স্থির, সেখানে translation scheme. দুটির ফল মিলিয়ে দেখা একটি ভালো পরীক্ষা।
প্র ০৫Haat-এর use-before-declaration (decision 16) আর hoisting (decision 17) কেন একটি L-attributed SDD দিয়ে এক হাঁটায় লেখা যায় না, আর অন্য ভাষাগুলো কী বেছে নিয়েছে?
L-attributed শর্ত বলে, একটি statement-এর inherited তথ্য আসতে পারে শুধু ওপর থেকে বা বাঁ দিকের ভাইদের কাছ থেকে। Decision 16 চায় যে let p-এর আগে ব্যবহৃত p একটি নির্দিষ্ট error দিক, বাইরে আরেকটি p থাকলেও। তার মানে, আগের statement-কে জানতে হবে যে পরে একই block-এ p ঘোষিত হবে: ডান দিকের তথ্য। Decision 17-এ একটি top-level function ঘোষণার আগেই ডাকা যায়, আবারও ডান দিকের তথ্য। তাই দুটির জন্যই block-এর ঘোষণার তালিকা আগে synthesized হতে হয়, তারপর inherited হয়ে নামতে হয়: দুই হাঁটা। Reference-এর declared_names() আর program()-এর প্রথম loop এই প্রথম হাঁটা।
ভাষাগুলো এখানে নানা পথ নিয়েছে। C ঐতিহ্যগতভাবে এক হাঁটার compiler-এর কথা ভেবে নকশা করা: নাম ব্যবহারের আগে ঘোষণা চাই, তাই function prototype বা forward declaration লাগে; একটি ব্যবহারে যে ঘোষণা দেখা যায় তা শুধু আগের লেখা থেকে। এটি প্রায় খাঁটি L-attributed নকশা। Java-তে একটি class-এর method-গুলো একে অপরকে ক্রম না মেনে ডাকতে পারে, যা দুই হাঁটার নকশা। JavaScript-এর let আর const একটি block-এর ভেতরে “temporal dead zone” রাখে: নামটি পুরো block-এ জানা, কিন্তু ঘোষণার আগে ব্যবহার runtime error; Haat-এর decision 16 এর static রূপ। Python-এ একটি function-এর ভেতরে কোনো নামে কোথাও assignment থাকলে সেটি পুরো function-এ local ধরা হয়, তাই আগে পড়লে UnboundLocalError আসে: এটিও পুরো দেহ আগে দেখার ফল।
দুই হাঁটার দাম কম, কিন্তু আছে: আরেকটি traversal, আর ঘোষণার তালিকা রাখার মেমরি। বিনিময়ে প্রোগ্রামার ক্রম নিয়ে কম ভাবেন, আর পারস্পরিক recursion সহজ হয়।
মূল উপলব্ধি: একটি scope-নিয়ম কত হাঁটায় যাচাই করা যায়, তা attribute-নির্ভরতা দেখেই বলা যায়। ভাষা-নকশার এমন ছোট সিদ্ধান্ত compiler-এর কাঠামো ঠিক করে দেয়।
অনুশীলন
প্রথমটিতে কোড লিখতে হবে; বাকিগুলো শ্রেণিবিন্যাস ও ভুল খোঁজা, trace আর নকশা।
-
Evaluator বাড়ান (বাস্তবায়ন): অংশ ৪-এর
RULES-এ unary minus-এর জন্য একটি production"Neg"যোগ করুন (একটি সন্তান): সন্তানেরenv= মা-বাবার; val = −(সন্তানের val); type = Int যদি সন্তান Int, নইলে "error"; code = সন্তানের code ‖ [NEG]. তারপর-(p / 10)-এর গাছ বানিয়ে{"p": ("Int", 1040)}দিয়ে চালান। কয়টি নিয়ম চলবে, আর ফল কী?RULES["Neg"] = [("1.env", ["0.env"], cp), ("0.val", ["1.val"], lambda n, a: -a), ("0.type", ["1.type"], lambda n, a: "Int" if a == "Int" else "error"), ("0.code", ["1.code"], lambda n, a: a + ["NEG"])] e = N("Neg", N("Bin", N("Var", lex="p"), N("Num", lex="10"), lex="/")) val, order = evaluate(e, {"p": ("Int", 1040)}) print(len(order), val[0, "val"], val[0, "type"], val[0, "code"])ল্যাবে চালানো ফল:
15 -104 Int ['LOAD p', 'CONST 10', 'DIV', 'NEG']. গাছে চারটি node, নিয়ম ৪ (Neg) + ৫ (Bin) + ৩ (Var) + ৩ (Num) = ১৫. Reference-এlet p = 1040; print(-(p / 10));চালালে আসে -104, আরdis-এLOAD_GLOBAL 0 ; p,CONST 1 ; 10,DIV,NEG: একই ক্রম। (অংশ ৪-এর block-এর শেষের ভুল নিয়মটি বাদ দিয়ে, বা block আবার চালিয়ে, এটি চালান; নইলে Bin-এর চক্র থেকে যাবে।) -
শ্রেণি চিনুন আর ভুল খুঁজুন: তিনটি SDD-র কোনটি S-attributed, কোনটি L-attributed, কোনটি কোনোটিই নয়? (ক) E → E1 + T { E.val = E1.val + T.val }. (খ) D → T L { L.in = T.type }, L → L1 , id { L1.in = L.in }. (গ) A → B C { B.in = C.syn; A.syn = B.syn }. তারপর এই দাবির ভুল দেখান: “E → T E′, E′ → - T E′1 { E′.syn = T.val - E′1.syn }, E′ → ε { E′.syn = 0 }, E.val = T.val - E′.syn (প্রথম পদ আলাদা) — এটি বিয়োগ ঠিক হিসাব করে।”
(ক) শুধু synthesized: S-attributed (তাই L-attributed-ও)। (খ) L.in মা-বাবার নয়, বাঁ ভাই T-এর attribute থেকে; L1.in মা-বাবার inherited থেকে: L-attributed, কিন্তু S-attributed নয়। (গ) B.in নির্ভর করে ডান ভাই C-র ওপর: L-attributed নয়। চক্র নেই বলে গ্রাফ-চালিত evaluator এটি চালাতে পারে (আগে C, তারপর B), কিন্তু এক বাঁ-থেকে-ডানে হাঁটায় নয়।
দাবির ভুল, প্রতি-উদাহরণ দিয়ে প্রমাণ. (১)
20 - 5 - 3নিন। (২) ভেতরের E′ (- 3অংশ): E′.syn = 3 - 0 = 3. (৩) বাইরের E′ (- 5 …): E′.syn = 5 - 3 = 2. (৪) E.val = 20 - 2 = 18. (৫) কিন্তু Haat-এ বিয়োগ বাঁ-সংযোজী, সঠিক মান (20 - 5) - 3 = 12 (reference-এরrunদেয় 12). তাই দাবি মিথ্যা। ∎ নিয়মটি আসলে 20 - (5 - (3 - 0)) হিসাব করে, অংশ ৩-এরleft_assoc=False-এর মতো। সমাধান সেখানকার inheritedleft. -
Trace করুন: AST (- (+ (* a b) (* c d)) e), অর্থাৎ
a * b + c * d - e-এর জন্য অংশ ৫-এর pure SDD (sdd, শুরু n = 1) কোন three-address code দেবে, মূলের addr কী, কয়টি temp লাগবে? আর postfix stack code কী?বাঁ থেকে ডানে, সন্তান আগে:
t1 = a * b(n_out 2),t2 = c * d(3),t3 = t1 + t2(4),t4 = t3 - e(5). মূলের addr t4, temp ৪টি। Stack code:LOAD a, LOAD b, MUL, LOAD c, LOAD d, MUL, ADD, LOAD e, SUB, ৯টি instruction. দুটিই ল্যাবেsddআরpostfixচালিয়ে মেলানো। লক্ষ করুন,eএকটি নাম, তাই তার জন্য কোনো temp লাগে না: পাতার addr সে নিজেই। -
নকশা করুন — missing return একটি attribute হিসেবে: Haat-এর decision 21 (একটি non-Unit function-এর প্রতিটি পথে return) একটি synthesized Bool attribute
returnsদিয়ে লিখুন: Return, Block, If (else-সহ ও ছাড়া), While, আর statement-তালিকার নিয়ম। কোন inherited attribute এর সঙ্গে লাগবে? তারপর বলুন নিচের কোন function-গুলো reference-এ error দেবে:fee(if-else দুই শাখায় return),half(while true { return n / 2; }),pick(একটি plain block-এর ভেতরে else-if শিকল, তিন শাখায় return),bad(else ছাড়া if).নিয়ম (synthesized, নিচ থেকে ওপরে): Return.returns = true; Block.returns = তার তালিকার returns; তালিকা S1 … Sn-এর returns = কোনো একটি Si.returns সত্য; If-এ else থাকলে returns = then.returns ∧ else.returns, না থাকলে false; While.returns = false (শর্ত যা-ই হোক); বাকি statement false. এটি reference-এর
always_returns()-এর হুবহু রূপ, আর পুরোটাই syntactic: শর্তের মান দেখা হয় না।সঙ্গে লাগে inherited
ret(ঘেরা function-এর ফেরত type): একটি Unit function-এ returns-যাচাই বাদ, আর প্রতিটিreturn e;-এ e-র type মেলাতে হয়; reference-এ এটিself.ret. ল্যাবে চারটি function একটি ফাইলে রেখেcheckচালানো হয়েছে; ফল:4:4: error: missing return: not every path of function 'half' returns Int 10:4: error: missing return: not every path of function 'bad' returns Intfeeআরpickঠিক আছে (pick-এ block-এর returns তার ভেতরের If থেকে ওঠে, আর else-if শিকলের প্রতিটি স্তরে else আছে)।halfব্যর্থ, কারণ While কখনো গোনা হয় না, এমনকিwhile true-ও; এটি সচেতন নকশা, যাতে নিয়মটি সরল আর অনুমানযোগ্য থাকে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি গাছের ওপর গ্রাফ-চালিত attribute evaluation যে ক্রমে চলে, সেভাবে সাজান (▲▼ চেপে সরান)
- Parser দিয়ে গাছ (AST বা parse tree) বানানো
- প্রতিটি node-এর প্রতিটি attribute-এর জন্য একটি instance তৈরি
- প্রতিটি semantic rule থেকে উৎস থেকে লক্ষ্যে edge যোগ
- Topological sort চালানো, সব instance না এলে চক্রের error
- সেই ক্রমে প্রতিটি নিয়মের function চালিয়ে মান বসানো
- মূলের synthesized attribute থেকে ফল (মান, type, code) পড়া
SDD-র নিয়ম E → E1 + T { E.val = E1.val + T.val } আর E1.env = E.env. এখানে val আর env কোন ধরনের attribute?
- val inherited, env synthesized
- val synthesized, env inherited
- দুটিই synthesized
- দুটিই inherited
Production A → B C D-র কোন semantic rule একটি SDD-কে L-attributed হতে দেয় না?
- C.in = B.syn + 1
- D.in = f(A.in, C.syn)
- A.syn = B.syn + D.syn
- B.in = D.syn
Left recursion সরানো grammar E → T E′, E′ → - T E′ ∣ ε-এ কেউ শুধু synthesized নিয়ম লিখলেন: E′.syn = T.val - E′₁.syn, E′ → ε-এ 0, আর E.val = T.val - E′.syn. 20 - 5 - 3-এর জন্য E.val কত হবে?
- 12
- 22
- 18
- 0
Temp-নম্বর বাঁ থেকে ডানে বসানো একটি SDD a * b + c-এর জন্য কোন three-address code দেয়?
t1 = a * b,t2 = t1 + ct1 = a * b,t2 = c,t3 = t1 + t2t1 = b + c,t2 = a * t1t1 = a * b + c
একটি গাছের attribute dependency graph-এ Kahn-এর algorithm চালানোর পরে ১৯টি instance-এর মধ্যে মাত্র ৯টির মান পাওয়া গেল, সারি খালি। এর অর্থ কী?
- অন্য একটি সারির ক্রমে চালালে সব ১৯টি হবে
- বাকি ১০টি কেউ ব্যবহার করে না, তাই বাদ গেছে
- গ্রাফে চক্র আছে; ওই গাছের জন্য SDD-র কোনো বৈধ হিসাব-ক্রম নেই
- Postorder হাঁটায় চালালে সব হবে
yacc বা Bison-এর expr : expr '-' term { $$ = $1 - $3; } নিয়মটি কোন ধাঁচের attribute হিসাব?
- Inherited attribute, ওপর থেকে নিচে
- Synthesized attribute, LR parser-এর reduce-এর সময় হিসাব
- Recursive descent-এর parameter
- চক্রযুক্ত attribute, fixpoint পর্যন্ত হিসাব
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- SDD = grammar + semantic rule: নিয়ম বলে কোন মান কোন মান থেকে; ক্রম বলে না। মূল-চিহ্নের attribute synthesized, সন্তানের attribute inherited.
- S-attributed একটি postorder হাঁটায় (LR-এর reduce, yacc-এর
$$); L-attributed একটি বাঁ থেকে ডানে DFS-এ (recursive descent: inherited = parameter, synthesized = return value). - Left recursion সরালে বাঁ-সংযোগ রাখতে inherited
leftলাগে; নইলে20 - 5 - 3= 18. - সাধারণ ক্ষেত্রে dependency graph আর topological sort; চক্রহীন হলে যেকোনো বৈধ ক্রম একই মান দেয়, চক্র থাকলে কোনো ক্রম নেই।
- Code-ও একটি attribute: pure SDD-তে temp-নম্বর শিকল-বাঁধা, translation scheme-এ global counter আর emit; হাতে লেখা pass আসলে কয়েকটি attribute আর তাদের নির্ভরতা।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৫৪ · অন্য semantic check — definite assignment, unreachable code আর exhaustivenessপরবর্তী পর্বtype-এর বাইরের static বিশ্লেষণ আর তাদের আপস।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্ব১৪টি মডিউলের পুরো মানচিত্র।
- পর্ব ৩৪ · Typing rule আর type judgmentভিত্তিযে নিয়মগুলো type attribute হিসাব করে।
- পর্ব ৫১ · Symbol table আর name resolutionআগের ধাপenv attribute-এর আসল বাস্তবায়ন।
- গণনার তত্ত্ব · পর্ব ২৬ · Derivation আর parse treeতত্ত্বparse tree আর attribute grammar-এর ইতিহাস।
- গণনার তত্ত্ব · পর্ব ৩৮ · LL(1), FIRST আর FOLLOWতত্ত্বleft recursion সরানো আর top-down parsing.
- DSA · পর্ব ৪২ · Topological sort আর DAGপাশের ট্র্যাকKahn-এর algorithm আর চক্র খোঁজা।