সরাসরি পর্বে যান
পর্ব ৪৯ · ৮৬-এর মধ্যে · মডিউল ৮

AST নকশা — node, visitor আর pretty printer

AST Design — Nodes, Visitors and a Pretty-Printer

Taught in Bangla, this lesson compares a parse tree with an AST by measuring both for the same program, then covers node design: fields, point versus span positions, mutability, structural equality and side tables. It builds a minimal-parentheses pretty-printer from four rules in in-page Python (Pyodide), sketches its correctness proof, walks trees with a visitor and with pattern matching, and turns parse-print round trips into a property-based test with random trees and shrinking that catches a planted bug.

এই পর্বে যা শিখবেন

  • Parse tree থেকে AST-এ কী বাদ যায়, কেন, আর একটি সত্যিকারের program-এ দুটির আকার মেপে তুলনা
  • AST node-এর নকশা: field, অবস্থান আর span, mutable বনাম immutable, structural equality, hashing আর side table
  • Visitor pattern আর pattern matching দিয়ে গাছে হাঁটা, আর কখন কোনটি সুবিধার
  • সবচেয়ে কম বন্ধনীর pretty printer-এর চারটি নিয়ম, তার সঠিকতার প্রমাণের রূপরেখা আর “কম”-এর অর্থ
  • Round trip-কে property-based test বানানো: এলোমেলো গাছ, shrinking, আর একটি ইচ্ছাকৃত bug ধরা

১ · AST বনাম parse tree — কী রাখব, কী ফেলব

রেস্তোরাঁয় অর্ডার নেওয়ার কথা ভাবুন। খদ্দের বলেন, “ভাই, ইয়ে… দুটো, না না, তিনটে পরোটা দিন, আর একটা ডিম ভাজি, ঝাল কম।” ওয়েটার স্লিপে লেখেন: পরোটা ×৩, ডিম ভাজি ×১ (ঝাল কম)। “ইয়ে”, “না না”, ভুল করে বলা “দুটো” স্লিপে নেই; রান্নাঘরের যা দরকার, শুধু সেটুকু আছে। কিন্তু খদ্দের ঠিক কী কী বলেছিলেন, তা স্লিপ থেকে আর হুবহু ফেরানো যায় না।

খদ্দেরের পুরো কথা হলো parse tree: ব্যাকরণের প্রতিটি নিয়ম-প্রয়োগ একটি node, প্রতিটি token একটি পাতা। ওয়েটারের স্লিপ হলো abstract syntax tree (AST): শুধু অর্থ। আর রান্নাঘর হলো compiler-এর বাকি অংশ (resolver, type checker, interpreter), যারা স্লিপ পড়েই কাজ করে।

পর্ব ৪৫-এ Haat-এর ব্যাকরণ EBNF-এ লেখা হয়েছিল, স্তরে স্তরে: expr → andExpr → eqExpr → relExpr → addExpr → mulExpr → unary → postfix → primary. ওই ব্যাকরণ ধরে একটি parse tree বানালে প্রতিটি নাম বা সংখ্যার ওপর এই নয়টি স্তরের একটি শিকল ঝুলে থাকে, যদিও অর্থের দিক থেকে সেগুলো কিছুই বলে না। Parse tree আর derivation-এর তত্ত্ব গণনার তত্ত্ব কোর্সের পর্ব ২৬-এ (Derivation আর parse tree) আছে; এখানে প্রশ্ন প্রকৌশলের: compiler-এর জন্য কোন গাছটি বানাব?

ছবি ৪৯.১ — (a + b) * c: parse tree বনাম AST

ওপরে পর্ব ৪৫-এর layered EBNF ধরে parse tree; একটানা শিকলগুলো একটি বাক্সে গুটিয়ে, বন্ধনীতে শিকলের node-সংখ্যা। নিচে Haat-এর AST.

(a + b) * c: parse tree (32 nodes) vs AST (5 nodes) Parse tree — ৩২টি node, গভীরতা ১৯ expr…mulExpr (৬) unary…primary (৩) unary…primary (৩) expr…addExpr (৫) mulExpr…(৪) mulExpr…(৪) *c () +ab AST — ৫টি node, গভীরতা ৩ Binary *Binary +Var c Var aVar b
ছবি ৪৯.১ — বেগুনি বাক্স ব্যাকরণের নিয়ম, হলুদ বাক্স token, সবুজ বাক্স AST node. Parse tree-তে ২৫টি নিয়ম-node আর ৭টি token-পাতা; বন্ধনী দুটি নিজেরাই পাতা। AST-এ বন্ধনী নেই: “যোগ আগে” কথাটি গাছের আকারেই লেখা, কারণ + আছে *-এর নিচে। সংখ্যাগুলো ল্যাবে পর্ব ৪৫-এর EBNF ধরে লেখা একটি parse-tree builder থেকে গোনা।

পুরো bazar.haat-এ পার্থক্যটি কত বড়? ল্যাবে মাপা হয়েছে (CPython 3.14.4; AST reference-এর parse থেকে, parse tree ওই EBNF-builder থেকে):

রূপআকারগভীরতা
উৎস-ফাইল৪৭৭ byte, ৪৩৫টি অক্ষর, ১৬ লাইন—
Token (EOF-সহ)১৩০টি—
Parse tree৪৩০টি node (৩০১টি নিয়ম + ১২৯টি token)২৯
AST, type-node বাদে৭২টি node (Program-সহ)৯
AST, type-node-সহ৭৭টি (৫টি TypeName)৯
গঠনে আলাদা subtree৭২টির মধ্যে ৫৭টি—

AST প্রায় ছয় ভাগের এক ভাগ। গভীরতা ৯: Program → FnDecl → Block → If → Block → Return → Binary - → Binary / → p বা 10. শেষ সারিটি অংশ ৭-এর বিষয়: ৭২টি subtree-র মাত্র ৫৭টি গঠনে আলাদা; যেমন price(2, 520) দুবার আছে, p আর total চারবার করে।

সংজ্ঞা ৪৯.১ — abstract syntax

একটি ভাষার abstract syntax হলো কয়েকটি গাছ-ধরনের (sort) একটি সংগ্রহ, যেমন Expr আর Stmt, যার প্রতিটির কয়েকটি constructor: Expr ::= Num(n) ∣ Var(x) ∣ Unary(op, Expr) ∣ Binary(op, Expr, Expr) ∣ Call(Expr, Expr*) ∣ … . এটি পর্ব ২৪-এর একটি recursive algebraic data type. Concrete syntax (লেখা) থেকে abstract syntax-এ যায় parser; উল্টো দিকে যায় pretty printer.

একটি ভালো abstract syntax দুটি শর্ত মানে: (১) অর্থে সম্পূর্ণ: অর্থ বদলায় এমন প্রতিটি পার্থক্য গাছে থাকে (a - (b - c) আর a - b - c আলাদা গাছ); (২) লেখায় উদাসীন: শুধু লেখার পার্থক্য গাছে থাকে না (((p)) আর p একই গাছ, ফাঁকা ঘর আর comment-ও বাদ)।

শর্ত (২)-এর একটি দাম আছে: comment আর ফাঁকা ঘর হারায়, তাই AST থেকে উৎস-লেখা হুবহু ফেরে না। Compiler-এর তাতে কিছু যায় আসে না, কিন্তু formatter আর editor-এর আসে। তাদের জন্য তৃতীয় এক ধরনের গাছ লাগে, অংশ ৭-এ দেখব।

২ · Node নকশা — field, অবস্থান, সমতা

Haat reference-এর ast_nodes.py-এ প্রতিটি node একটি Python dataclass; সব নিয়ম README-তে লেখা: line, col সবসময় শেষ দুটি field. Node-গুলো দুই পরিবারে, আর প্রতিটির “অবস্থান” কোথায় সেটিও ঠিক করা:

পরিবারNode আর fieldঅবস্থান কোথায়
ExpressionNum(value) Str(value) Bool(value) Var(name)literal বা নামটি নিজে
ExpressionUnary(op, operand) Binary(op, left, right)operator-এ
ExpressionCall(callee, args)callee-র শুরুতে
ExpressionLambda(params, ret, body)fn-এ
StatementLet(name, mutable, type, init) Assign(name, value) FnDecl(name, params, ret, body)নামে
StatementIf(cond, then, else_) While(cond, body) Return(value) Print(value)keyword-এ
StatementExprStmt(expr) Block(stmts) Program(stmts)প্রথম token, {, (নেই)

কয়েকটি সিদ্ধান্ত লক্ষ করুন। let আর var আলাদা node নয়, একটি Let আর একটি mutable ঘর: দুটির নিয়ম প্রায় এক, শুধু assignment-এর অনুমতিতে আলাদা (decision 19). else if-এর জন্যও আলাদা node নেই: If.else_ হয় None, নয় একটি Block, নয় আরেকটি If. বন্ধনীর কোনো node নেই। আর ফেরত type না লিখলে ret-এ UNIT বসে, None নয়, যাতে পরের ধাপকে দুটি ক্ষেত্র ভাবতে না হয়।

বিন্দু না span

Haat প্রতিটি node-এ একটি বিন্দু রাখে (source position): Binary-র ক্ষেত্রে operator-এর জায়গা। তাই 1:7: error: division by zero সরাসরি /-এর দিকে আঙুল তোলে। কিন্তু “এই পুরো expression-টি Bool, Int হওয়া উচিত ছিল” বলতে চাইলে শুরু আর শেষ দুটিই লাগে: একে বলে source span. Haat-এ শুরু বের করা যায় ast_nodes.start(e) দিয়ে (Binary-র বাঁ দিক আর Call-এর callee ধরে নিচে নামা), কিন্তু শেষ নয়। CPython-এর AST শুরু আর শেষ দুটিই রাখে; নিচে সত্যিকারের run (Python 3.14.4):

~/haat/ast $ cat py_ast.py
import ast, sys
print(sys.version.split()[0])
t = ast.parse("(a + b) * c", mode="eval")
print(ast.dump(t.body))
print(ast.unparse(t), "|", ast.unparse(ast.parse("a - (b - c)")), "|", ast.unparse(ast.parse("x = (((p)))")))
y = ast.parse('s = "চাল" + y').body[0].value.right
print(y.id, y.lineno, y.col_offset, y.end_col_offset)
b = ast.parse("total = price + fee").body[0].value
print(b.lineno, b.col_offset, b.end_lineno, b.end_col_offset, ast.get_source_segment("total = price + fee", b))
print(ast.parse("a+b") == ast.parse("a+b"), ast.dump(ast.parse("a+b")) == ast.dump(ast.parse("a + b")))
print(ast.compare(ast.parse("a+b"), ast.parse("a  +  b")), ast.compare(ast.parse("a+b"), ast.parse("a  +  b"), compare_attributes=True))
print(len("s = \"চাল\" + "), len("s = \"চাল\" + ".encode()))
~/haat/ast $ python -B py_ast.py
3.14.4
BinOp(left=BinOp(left=Name(id='a', ctx=Load()), op=Add(), right=Name(id='b', ctx=Load())), op=Mult(), right=Name(id='c', ctx=Load()))
(a + b) * c | a - (b - c) | x = p
y 1 18 19
1 8 1 19 price + fee
False True
True False
12 18

লাইন ২: (a + b) * c-এর Python AST-এও বন্ধনী নেই, Haat-এর মতোই। লাইন ৩: Python 3.9 থেকে আছে ast.unparse, Python-এর নিজের সবচেয়ে কম বন্ধনীর printer; x = (((p))) থেকে x = p. লাইন ৪ চমকপ্রদ: s = "চাল" + y-এ y-এর col_offset 18, কারণ Python এখানে UTF-8 byte গোনে (শেষ লাইন: y-এর আগে ১২টি অক্ষর, কিন্তু ১৮টি byte). Haat গোনে অক্ষর (decision 1). লাইন ৫: price + fee-এর span 1:8 থেকে 1:19, আর ast.get_source_segment সেই span দিয়ে মূল লেখা কেটে আনে। শেষের দুই লাইন সমতা নিয়ে, পরের অনুচ্ছেদের বিষয়।

সমতা: অবস্থানসহ না অবস্থান বাদে

দুটি গাছ কখন “সমান”? Structural equality বলে: একই ধরন আর প্রতিটি অংশ সমান হলে। Python dataclass নিজে থেকেই __eq__ বানায়, আর reference-এর node-এ line, col-ও তুলনায় ঢোকে। ফলে a+b আর a + b-এর গাছ সমান নয়, কারণ b-এর column আলাদা। Round trip-এর জন্য সেটি ভুল প্রশ্ন: আমরা জানতে চাই গঠন এক কি না। তিনটি উপায় আছে: (ক) অবস্থান বাদ দিয়ে তুলনার আলাদা function, (খ) অবস্থান-ছাড়া একটি লেখা (যেমন S-expression) তুলনা, (গ) অবস্থানের field-কে তুলনা থেকে বাদ রাখা: field(compare=False). এই পর্বের ব্রাউজারের কোড (গ) বেছে নিয়েছে; reference (খ) ব্যবহার করে তার পরীক্ষায়। Python নিজে উপরের run-এর শেষ লাইনগুলোতে আরেকটি পথ দেখায়: Python-এর ast node ==-এ পরিচয় (identity) তুলনা করে, তাই False; Python 3.14-এর ast.compare গঠন তুলনা করে, অবস্থান বাদ দিয়ে True, আর compare_attributes=True দিলে অবস্থানসহ False.

বদলানো যাবে কি না, আর hash

Reference-এর node immutable নয়: dataclass-এর default. কিন্তু resolver বা type checker কোনো node-এ কিছু লেখে না। Resolver তার ফল রাখে একটি আলাদা dict-এ, যার চাবি id(node): একে বলে side table. এতে গাছ একবার বানানোর পর কেউ বদলায় না, আর একই গাছের ওপর আলাদা বিশ্লেষণ পাশাপাশি চলতে পারে। চাবি id কেন, node নিজে নয়? কারণ eq=True কিন্তু frozen নয় এমন dataclass-এ Python __hash__-কে None করে দেয়: node dict-এর চাবি হতে পারে না (অংশ ৫-এর block এটি চালিয়ে দেখায়)। Frozen dataclass করলে hash পাওয়া যায়, তবে তখন args-এর মতো list ঘরকে tuple বানাতে হয়, আর অবস্থান তুলনায় থাকলে দুটি সমান-গঠনের node-এর hash আলাদা হবে।

সমতা আর hash একসঙ্গে বদলান। নিয়ম: a == b হলে hash(a) == hash(b) হতেই হবে। অবস্থান তুলনা থেকে বাদ দিলে hash থেকেও বাদ দিন (dataclass-এ compare=False field hash-এও ঢোকে না)। নইলে একটি set-এ “সমান” দুটি গাছ আলাদা জায়গায় বসবে, আর bug-টি শুধু মাঝে মাঝে দেখা দেবে।

৩ · সবচেয়ে কম বন্ধনীর pretty printer

Parser লেখা থেকে গাছ বানায়; pretty printer গাছ থেকে লেখা। Expression-এর ক্ষেত্রে আসল প্রশ্ন একটিই: বন্ধনী কোথায়? সব জায়গায় বন্ধনী দিলে নিরাপদ, কিন্তু ((qty * unit) - (p / 10)) কেউ পড়তে চায় না। একটিও না দিলে (a + b) * c হয়ে যায় a + b * c, অন্য অর্থ। Haat-এর haat.py fmt মাঝের পথ নেয়: ঠিক যতটুকু দরকার।

সংজ্ঞা ৪৯.২ — স্তর আর চারটি বন্ধনী-নিয়ম (reference-এর ast_print.py)

প্রতিটি expression e-র একটি স্তর L(e): Binary-র ক্ষেত্রে তার operator-এর precedence-স্তর (|| = 1, && = 2, == != = 3, < <= > >= = 4, + - = 5, * / % = 6), Unary-র ৭, আর বাকি সবকিছুর (literal, নাম, Call, Lambda) ৮। ধরুন N = {3, 4}, non-associative স্তরগুলো। Binary l op r, যেখানে p = L(op):

R1 (বাঁ): l-কে বন্ধনী দিন যদি L(l) < p, অথবা p ∈ N আর L(l) = p.
R2 (ডান): r-কে বন্ধনী দিন যদি L(r) ≤ p.
R3 (unary): op e-তে e-কে বন্ধনী দিন যদি L(e) < 7.
R4 (callee): f(…)-তে f-কে বন্ধনী দিন যদি L(f) < 8.

R1 আর R2-এর অসমতা লক্ষ করুন। বাঁ দিকে একই স্তর চলে (a - b - c, কারণ সব binary operator বাঁ-সংযোজী), ডান দিকে চলে না (a - (b - c)). ব্যতিক্রম তুলনা: (a < b) < c-তে বাঁ দিকেও বন্ধনী, কারণ বন্ধনী ছাড়া লেখাটি a < b < c, যা Haat-এ syntax error (decision 10). নিচের stepper চারটি নিয়ম কাজ করতে দেখায়; প্রতিটি আউটপুট পরের block চালিয়ে আর reference-এর fmt দিয়ে মেলানো।

1p = LEVEL[e.op]2R1: L(l) < p or (p in N and L(l) == p)3R2: L(r) <= p4R3: unary, L(e) < 75R4: callee, L(f) < 8
গাছ আর সিদ্ধান্ত
গাছ
p
বাঁ
ডান
  1. মূল node *, p = 6. বাঁ দিকের গাছ +, যার স্তর ৫। ৫ < ৬, তাই R1 বন্ধনী চায়: বন্ধনী ছাড়া a + b * c লিখলে * b-কে নিজের দিকে টেনে নিত।
  2. ডান দিক c. একটি নাম, স্তর ৮; ৮ ≤ ৬ মিথ্যা, তাই R2 বন্ধনী চায় না। ফল (a + b) * c.
  3. উল্টো গাছ (+ a (* b c)). p = 5. ডান দিকের *-এর স্তর ৬; ৬ ≤ ৫ মিথ্যা, তাই বন্ধনী নেই: a + b * c. কেউ a + (b * c) লিখে থাকলেও fmt বন্ধনী ফেলে দেয়, কারণ গাছে বন্ধনী নেই।
  4. একই স্তর ডান দিকে. (- a (- b c)): ডানের স্তর ৫ = p, আর R2-তে “≤”। বন্ধনী থাকে: a - (b - c). বন্ধনী ফেললে বাঁ-সংযোগের কারণে parser বানাত (- (- a b) c), অন্য মান।
  5. Non-associative তুলনা. (< (< a b) c): বাঁয়ের স্তর ৪ = p, আর ৪ ∈ N, তাই R1-এর দ্বিতীয় অংশ বন্ধনী দেয়: (a < b) < c. এই গাছ type checker পরে নাকচ করবে (Bool আর Int), কিন্তু fmt চলে শুধু parse-এর পরে, তাই printer-কে এটিও ঠিক ছাপতে হয়।
  6. Unary আর callee. - (স্তর ৭)-এর নিচে + (স্তর ৫): ৫ < ৭, তাই -(d + 1); নইলে -d + 1 মানে (+ (- d) 1). একইভাবে R4: callee যদি a ∣∣ b হয় (স্তর ১ < ৮), তাহলে (a ∣∣ b)("চাল"); বন্ধনী ছাড়া call শুধু b-কে ডাকত।

এবার নিজে চালিয়ে দেখুন। প্রথম block reference-এর ast_print.py-এর expression অংশ (LEVEL, level, quote, expr, wrap) আর S-expression dump (sexpr)-এর ছোট রূপ; class আর field-এর নাম ast_nodes.py-এর হুবহু। একটি পার্থক্য ইচ্ছাকৃত: line আর col এখানে compare=False, default 0, যাতে হাতে গাছ বানানো সহজ হয় আর == গঠন তুলনা করে। পরের তিনটি block এই block-এর নাম ব্যবহার করে।

from dataclasses import make_dataclass, field
POS = [("line", int, field(default=0, compare=False)), ("col", int, field(default=0, compare=False))]
for spec in "Num value|Str value|Bool value|Var name|Unary op operand|Binary op left right|Call callee args".split("|"):
    name, *fs = spec.split(); globals()[name] = make_dataclass(name, fs + POS)   # == ignores line, col
LEVEL = {"||": 1, "&&": 2, "==": 3, "!=": 3, "<": 4, "<=": 4, ">": 4, ">=": 4,
         "+": 5, "-": 5, "*": 6, "/": 6, "%": 6}
NONASSOC, UNARY_LEVEL, ATOM_LEVEL = {3, 4}, 7, 8
def quote(s): return '"' + s.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'
def level(e):
    if isinstance(e, Binary): return LEVEL[e.op]
    return UNARY_LEVEL if isinstance(e, Unary) else ATOM_LEVEL
def wrap(e, paren): return f"({expr(e)})" if paren else expr(e)
def expr(e):                                   # canonical source, minimal parentheses
    if isinstance(e, Num): return str(e.value)
    if isinstance(e, Str): return quote(e.value)
    if isinstance(e, Bool): return "true" if e.value else "false"
    if isinstance(e, Var): return e.name
    if isinstance(e, Unary): return e.op + wrap(e.operand, level(e.operand) < UNARY_LEVEL)
    if isinstance(e, Binary):
        p = LEVEL[e.op]
        lp = level(e.left) < p or (p in NONASSOC and level(e.left) == p)
        return f"{wrap(e.left, lp)} {e.op} {wrap(e.right, level(e.right) <= p)}"
    if isinstance(e, Call):
        return wrap(e.callee, level(e.callee) < ATOM_LEVEL) + "(" + ", ".join(map(expr, e.args)) + ")"
def sexpr(e):                                  # the `haat.py ast` view of an expression
    if isinstance(e, (Num, Str, Bool, Var)): return expr(e)
    if isinstance(e, Unary): return f"({e.op} {sexpr(e.operand)})"
    if isinstance(e, Binary): return f"({e.op} {sexpr(e.left)} {sexpr(e.right)})"
    return "(call " + " ".join(map(sexpr, [e.callee, *e.args])) + ")"
a, b, c = Var("a"), Var("b"), Var("c")
for t in [Binary("*", Binary("+", a, b), c), Binary("+", a, Binary("*", b, c)),
          Binary("-", a, Binary("-", b, c)), Binary("<", Binary("<", a, b), c),
          Unary("-", Binary("+", Var("d"), Num(1))), Call(Binary("||", a, b), [Str("চাল")])]:
    print(f"{expr(t):22} {sexpr(t)}")

আসল আউটপুট (ব্রাউজারের Python):

(a + b) * c            (* (+ a b) c)
a + b * c              (+ a (* b c))
a - (b - c)            (- a (- b c))
(a < b) < c            (< (< a b) c)
-(d + 1)               (- (+ d 1))
(a || b)("চাল")        (call (|| a b) "চাল")

বাঁ কলাম haat.py fmt-এর রূপ, ডান কলাম haat.py ast-এর রূপ। ল্যাবে এই ছয়টি expression-কে print(…);-এ মুড়ে reference দিয়ে চালিয়েছি: fmt ঠিক এই ছয় লাইন ছাপে (print( আর );-এর ভেতরে), আর ast ঠিক এই ছয়টি S-expression. quote string-এর \", \\ আর newline আবার escape করে, যাতে ছাপা লেখা আবার lexer-এ দেওয়া যায়। বাংলা অক্ষর যেমন আছে তেমনই থাকে।

Printer পরীক্ষা করতে একটি parser লাগে। দ্বিতীয় block একটি ছোট Pratt parser: পর্ব ৪৬-এর lexer আর পর্ব ৪৮-এর (Pratt parsing) parser-এর শুধু expression অংশ, এক লাইনের লেখার জন্য, string আর anonymous function ছাড়া। Binding power reference-এর মতো স্তরের দশগুণ (|| 10 … * 60), call 80, prefix 70; তুলনা-শিকলের নিয়মটি সে নিজের কাছে রাখে ((3, 4)), printer-এর NONASSOC থেকে নেয় না। অংশ ৬-এ এই আলাদা থাকার কারণ বুঝবেন।

OPS = sorted(LEVEL, key=len, reverse=True) + ["!", "(", ")", ","]     # longest match first
def tokenize(s):                       # (kind, text, col): one line, no strings, enough here
    toks, i = [], 0
    while i < len(s):
        j = i + 1
        if s[i].isalnum() or s[i] == "_":
            while j < len(s) and (s[j].isalnum() or s[j] == "_"): j += 1
            toks.append(("INT" if s[i].isdigit() else "NAME", s[i:j], i + 1))
        elif s[i] != " ":
            k = next(o for o in OPS if s.startswith(o, i)); j = i + len(k); toks.append((k, k, i + 1))
        i = j
    return toks + [("EOF", "", len(s) + 1)]
def start(e): return start(e.left if isinstance(e, Binary) else e.callee) if isinstance(e, (Binary, Call)) else (e.line, e.col)
def parse(s):                          # Pratt parser; binding power = 10 * LEVEL, call = 80
    toks, pos = tokenize(s), 0
    def nxt(): nonlocal pos; pos += 1; return toks[pos - 1]
    def expression(min_bp=0):
        left, last = prefix(), None
        while toks[pos][0] == "(" or 10 * LEVEL.get(toks[pos][0], -1) >= min_bp:
            k, _, col = nxt()
            if k == "(":                                       # postfix call f(a, b)
                args = [] if toks[pos][0] == ")" else [expression()]
                while toks[pos][0] == ",": nxt(); args.append(expression())
                nxt(); left = Call(left, args, *start(left)); continue
            if LEVEL[k] in (3, 4) and last == LEVEL[k]: raise SyntaxError(f"1:{col}: error: comparison operators cannot be chained")
            last = LEVEL[k]; left = Binary(k, left, expression(10 * last + 1), 1, col)
        return left
    def prefix():
        k, t, col = nxt()
        if k in ("-", "!"): return Unary(k, expression(70), 1, col)
        if k == "(": e = expression(); nxt(); return e
        if k == "INT": return Num(int(t), 1, col)
        return Bool(t == "true", 1, col) if t in ("true", "false") else Var(t, 1, col)
    return expression()
t = parse("(qty * unit - p / 10) * -f(a < b, (x < y) < z)"); print(sexpr(t), expr(t), t.right, sep=chr(10))

আসল আউটপুট (ব্রাউজারের Python):

(* (- (* qty unit) (/ p 10)) (- (call f (< a b) (< (< x y) z))))
(qty * unit - p / 10) * -f(a < b, (x < y) < z)
Unary(op='-', operand=Call(callee=Var(name='f', line=1, col=26), args=[Binary(op='<', left=Var(name='a', line=1, col=28), right=Var(name='b', line=1, col=32), line=1, col=30), Binary(op='<', left=Binary(op='<', left=Var(name='x', line=1, col=36), right=Var(name='y', line=1, col=40), line=1, col=38), right=Var(name='z', line=1, col=45), line=1, col=43)], line=1, col=26), line=1, col=25)

দ্বিতীয় লাইন: এখানে fmt ইনপুটের সঙ্গে হুবহু মিলেছে, কারণ ইনপুটে কোনো বাড়তি বন্ধনী ছিল না। তৃতীয় লাইন অবস্থান দেখায়: Unary - column 25-এ, Call column 26-এ (callee f-এর শুরু), প্রতিটি Binary তার operator-এ। Reference একই লেখা print(…);-এ মুড়ে পড়লে প্রতিটি column ঠিক ৬ বেশি দেয় (print(-এর ছয় অক্ষর), বাকি সব অক্ষরে অক্ষরে এক।

শুধু কয়েকটি উদাহরণ নয়: ল্যাবে একটি differential test-এ এই দুটি block-কে reference-এর সঙ্গে মিলিয়েছি। অংশ ৬-এর generator দিয়ে বানানো ২০,০০০টি এলোমেলো গাছ (১০টি seed, গভীরতা ৫ পর্যন্ত), প্রতিটি গাছ reference-এর class-এ রূপান্তর করে:

~/haat/ast $ python -B diff.py
trees 20000: fmt same 20000, sexpr same 20000, parse (with positions) same 20000

অর্থাৎ printer, S-expression আর parser (৬ column সরিয়ে নিলে অবস্থানসহ) তিনটিই ২০,০০০-এ ২০,০০০ বার reference-এর সমান।

৪ · Printer সঠিক আর “সবচেয়ে কম” — প্রমাণ আর পরীক্ষা

চারটি নিয়ম দেখতে সরল, কিন্তু দুটি দাবি আছে, আর দুটিই প্রমাণ চায়। এক: ছাপা লেখা parse করলে ঠিক আগের গাছ আসে। দুই: কোনো বন্ধনী বাড়তি নয়।

উপপাদ্য ৪৯.১ — printer-এর সঠিকতা

Lambda ছাড়া প্রতিটি expression-গাছ e-র জন্য parse(fmt(e)) ≅ e, যেখানে ≅ মানে অবস্থান বাদ দিয়ে structural equality.

প্রমাণের রূপরেখা (e-র গঠনের ওপর induction; parser-এর loop চলে যতক্ষণ পরের operator-এর binding power ≥ min_bp).

(১) Atom আর বন্ধনী। নাম বা literal এক token, সরাসরি একই node. বন্ধনী ভেতরে min_bp = 0 দিয়ে নতুন করে শুরু করে, তাই ভেতরের যেকোনো গাছ induction hypothesis অনুযায়ী ঠিক পড়া হয়, আর বাইরে থেকে পুরো বন্ধনী একটি atom-এর মতো (স্তর ৮)।

(২) Binary l op r, স্তর p. R1-এর পরে l হয় বন্ধনীতে মোড়া, নয় তার স্তর q ≥ p (আর p ∈ N হলে q > p). l পড়ার সময় তার শেষ operand পড়া হয় min_bp = 10q + 1 দিয়ে; op-এর binding power 10p < 10q + 1, তাই op l-এর ভেতরে ঢুকতে পারে না, l সেখানেই শেষ হয়। q = p আর p ∈ N হলে parser শিকল-error দিত; R1-এর দ্বিতীয় অংশ ঠিক সেটি আটকায়।

(৩) r পড়া হয় min_bp = 10p + 1 দিয়ে। R2-এর পরে r হয় মোড়া, নয় তার স্তর > p, তাই r-এর ওপরের প্রতিটি operator-এর binding power ≥ 10(p + 1) ≥ 10p + 1: সবগুলো r-এর ভেতরেই থাকে, কোনোটি বাইরে চলে যায় না।

(৪) Unary. Operand পড়া হয় min_bp = 70 দিয়ে, যা যেকোনো binary operator-এর (সর্বোচ্চ 60) চেয়ে বেশি। R3-এর পরে operand হয় মোড়া, নয় unary বা atom, তাই operand-এ কোনো binary operator ঢোকে না।

(৫) Call. Postfix ( লাগে ঠিক তার আগের সম্পূর্ণ prefix-এর গায়ে। R4-এর পরে callee হয় atom বা Call, নয়তো মোড়া; তাই ( পুরো callee-কেই ডাকে, তার একটি অংশকে নয়। ∎

উপপাদ্য ৪৯.২ — কোনো বন্ধনী বাড়তি নয়

fmt যে জোড়া বন্ধনী grouping-এর জন্য ছাপে (call-এর বন্ধনী নয়), তার যেকোনো একটি মুছলে লেখাটি হয় parse হয় না, নয় অন্য গাছ দেয়।

প্রমাণের রূপরেখা. প্রতিটি নিয়ম বন্ধনী দেয় ঠিক তখনই, যখন ভেতরের ওপরের operator বাইরের operator-এর কাছে “হেরে যেত”। R1, L(l) < p: বন্ধনী মুছলে op (বেশি শক্ত) l-এর শেষ operand ছিনিয়ে নেয়, গাছ বদলায়। R1, L(l) = p ∈ N: মুছলে দুটি তুলনা পাশাপাশি, শিকল-error. R2, L(r) < p: op r-এর প্রথম operand ছিনিয়ে নেয়। R2, L(r) = p: বাঁ-সংযোগ গাছকে বাঁয়ে হেলিয়ে দেয়, অথবা p ∈ N হলে শিকল-error. R3 আর R4: prefix বা call অন্য, ছোট অংশে লাগে। ∎

প্রমাণের রূপরেখা আত্মবিশ্বাস দেয়, পরীক্ষা দেয় নিশ্চয়তার দ্বিতীয় স্তর। ল্যাবে ৫০০০টি এলোমেলো গাছ ছাপিয়ে প্রতিটি grouping-বন্ধনী একটি একটি করে মুছে reference দিয়ে আবার parse করেছি:

~/haat/ast $ python -B minimal.py
trees 5000, grouping pairs 17437: removal -> error 3957, other tree 13480, same tree 0

১৭,৪৩৭ জোড়ার ৩৯৫৭টি মুছলে parse error (শিকল), ১৩,৪৮০টিতে অন্য গাছ, আর একই গাছ একবারও নয়। মনে রাখবেন “সবচেয়ে কম” এখানে স্থানীয় অর্থে: প্রতিটি বন্ধনী একা মুছলে ক্ষতি হয়। আর “অন্য গাছ” মানে সবসময় অন্য মান নয়: a + (b + c) আর a + b + c Int-এ একই মান দেয় (wrapping যোগ associative), তবু গাছ আলাদা, আর AST-এর কাজ গাছ রক্ষা করা, মান অনুমান করা নয়।

Statement-এর printer

পর্ব ৪৭-এর recursive descent parser যে statement-গুলো পড়ে, printer-কে সেগুলো আবার লিখতে হয়। Statement-এর নিয়ম বন্ধনীর চেয়ে সহজ, কিন্তু সিদ্ধান্ত অনেক: ৪ ঘর ইন্ডেন্টেশন, প্রতিটি block কয়েক লাইনে, খালি block {}, else if এক লাইনে জোড়া, -> Unit বাদ, comment নেই। একটি কঠিন ফাইলে reference-এর সত্যিকারের run:

~/haat/ast $ cat demo.haat
// ছাড়ের নিয়ম
fn label(t: Int) -> Str { if t >= 1000 { return "বড় \"অর্ডার\""; } else if t > 0 { return "ছোট"; } else { return "খালি"; } }
let add = fn(n: Int) -> (Int) -> Int { return fn(x: Int) -> Int { return x + n; }; };
fn log(msg: Str) -> Unit { print(msg); }
{ }
print(label(((1200))));
log(label(add(5)(-(2 - 3))));
~/haat/ast $ python -B haat.py fmt demo.haat
fn label(t: Int) -> Str {
    if t >= 1000 {
        return "বড় \"অর্ডার\"";
    } else if t > 0 {
        return "ছোট";
    } else {
        return "খালি";
    }
}
let add = fn(n: Int) -> (Int) -> Int {
    return fn(x: Int) -> Int {
        return x + n;
    };
};
fn log(msg: Str) {
    print(msg);
}
{}
print(label(1200));
log(label(add(5)(-(2 - 3))));

Comment গেছে, -> Unit গেছে, ((1200))-এর বন্ধনী গেছে, কিন্তু -(2 - 3)-এর বন্ধনী আছে (R3). add(5)(…)-এ দুটি call পরপর, বন্ধনী লাগেনি (R4, callee নিজেই একটি Call). আউটপুট আবার fmt-এ দিলে byte-এ byte-এ একই লেখা আসে (idempotence), আর দুটি ফাইল চালালে একই ফল: বড় "অর্ডার" আর ছোট. Reference-এর ১৩টি উদাহরণের মধ্যে যে ১২টি parse হয় (err_syntax.haat ছাড়া), তার ১২টিতেই একই দুই শর্ত সত্য।

৫ · গাছে হাঁটা — visitor বনাম pattern matching

AST বানানোর পর compiler-এর প্রায় প্রতিটি ধাপ একটি কাজ করে: গাছের প্রতিটি node-এ যায়, আর node-এর ধরন অনুযায়ী আলাদা কিছু করে। Resolver নাম খোঁজে, type checker type বের করে, interpreter মান হিসাব করে, compiler bytecode লেখে। “ধরন অনুযায়ী আলাদা কাজ” লেখার দুটি প্রচলিত ধাঁচ আছে।

Visitor pattern: প্রতিটি কাজ একটি class, আর প্রতিটি node-ধরনের জন্য তাতে একটি method: visit_Binary, visit_Var… . Gamma, Helm, Johnson আর Vlissides-এর Design Patterns (১৯৯৪) বইয়ে এর ক্লাসিক রূপ: প্রতিটি node-এর একটি accept(visitor), যা visitor.visitBinary(this) ডাকে। দুটি ধরন মিলিয়ে কোড বাছাই হয় বলে একে বলে double dispatch. Python-এ accept লাগে না: getattr(self, "visit_" + ধরনের নাম) দিয়ে নাম ধরেই method খোঁজা যায়, যেমন Python-এর নিজের ast.NodeVisitor করে। যে ধরনের জন্য method নেই, সেখানে generic শুধু সন্তানদের visit করে, তাই একটি visitor শুধু তার দরকারি node-গুলোর কথা লেখে।

Pattern matching: একটি function, ভেতরে একটি match, প্রতিটি node-ধরনের জন্য একটি case. Python 3.10 (PEP 634) থেকে match আছে; reference নিজে পুরোনো ধাঁচে isinstance-এর শিকল ব্যবহার করে, যা হাতে লেখা pattern matching. পর্ব ২৪-এ এর তত্ত্ব আর exhaustiveness দেখেছেন। নিচের stepper p - p / 10-এর গাছে একটি visitor-এর হাঁটা দেখায়; প্রতিটি মান পরের block-এর একটি instrumented কপি চালিয়ে নেওয়া।

  1. Binary-1:3
  2. Varp1:1
  3. Binary/1:7
  4. Varp1:5
  5. Num101:9
1visit(n): count, depth += 12getattr(visit_Binary) → নেই3Names.visit_Var(n) → seen4generic(n): visit children5depth(e): match … case
Census আর Names-এর অবস্থা
depth
kinds
max
seen
  1. মূল node. Visitor শুরু করে মূল থেকে: Binary -, অবস্থান 1:3 (operator). Census গোনে, depth ১। visit_Binary নামে কোনো method নেই, তাই generic চলে, যা field ধরে সন্তানদের visit করে: আগে left, পরে right.
  2. বাঁ সন্তান p. depth ২, max ২। Names visitor-এর visit_Var আছে, তাই সেটি ডাকা হয়: p@1 লেখা হয়। Var-এর কোনো সন্তান নেই।
  3. ডান সন্তান Binary /. আবার depth ২ (একই স্তর)। এই ক্রমকে বলে preorder traversal: আগে node নিজে, তারপর বাঁ থেকে ডানে সন্তানেরা। লেখায় / ৭ নম্বর column-এ, কিন্তু visit হলো তৃতীয়তে।
  4. p, আবার. depth ৩, max ৩। Names লেখে p@5: একই নাম, ভিন্ন অবস্থান। পর্ব ৫১-এর resolver ঠিক এভাবে প্রতিটি ব্যবহার আলাদা করে চেনে।
  5. 10. শেষ পাতা, depth ৩। Census-এর গোনা শেষ: Binary ২, Var ২, Num ১।
  6. ফল. মোট ৫টি node, গভীরতা ৩। একই গভীরতা depth(e)-ও দেয়, যা visitor নয়, একটি match: প্রতিটি case সন্তানদের depth নিয়ে ১ যোগ করে। দুই ধাঁচে একই হিসাব; পার্থক্য কোড কোথায় থাকে।
from dataclasses import fields, is_dataclass
class Visitor:                                   # dispatch like Python's ast.NodeVisitor
    def visit(self, n): return getattr(self, "visit_" + type(n).__name__, self.generic)(n)
    def generic(self, n):                        # no visit_X method: visit the children
        for f in fields(n):
            v = getattr(n, f.name)
            for c in (v if isinstance(v, list) else [v]):
                if is_dataclass(c): self.visit(c)
class Census(Visitor):                           # count nodes by class, track depth
    def __init__(self): self.kinds, self.depth, self.max = {}, 0, 0
    def visit(self, n):
        k = type(n).__name__; self.kinds[k] = self.kinds.get(k, 0) + 1
        self.depth += 1; self.max = max(self.max, self.depth)
        super().visit(n); self.depth -= 1
class Names(Visitor):                            # cares only about Var; the rest is generic
    def __init__(self): self.seen = []
    def visit_Var(self, n): self.seen.append(f"{n.name}@{n.col}")
def depth(e):                                    # the same depth, with pattern matching
    match e:
        case Unary(operand=o): return 1 + depth(o)
        case Binary(left=l, right=r): return 1 + max(depth(l), depth(r))
        case Call(callee=f, args=a): return 1 + max(map(depth, [f, *a]))
        case _: return 1
e = parse("price(2, 520) + delivery(price(2, 520))")
c = Census(); c.visit(e); n = Names(); n.visit(e)
print(c.kinds, "nodes:", sum(c.kinds.values()), "depth:", c.max, depth(e))
print(n.seen)
print(e.left == e.right.args[0], e.left is e.right.args[0], parse("a+b*c") == parse("a + (b * c)"))
try: hash(e)
except TypeError as err: print("hash:", err)

আসল আউটপুট (ব্রাউজারের Python):

{'Binary': 1, 'Call': 3, 'Var': 3, 'Num': 4} nodes: 11 depth: 4 4
['price@1', 'delivery@17', 'price@26']
True False True
hash: unhashable type: 'Binary'

bazar.haat-এর first-এর initializer: ১১টি node, গভীরতা ৪ (Binary → delivery-এর Call → price-এর Call → সংখ্যা), দুই পদ্ধতিতেই। তৃতীয় লাইনে তিনটি সত্য। e.left == e.right.args[0]: দুটি price(2, 520) গঠনে সমান (True), যদিও column আলাদা (1 আর 26), কারণ অবস্থান তুলনায় নেই। is False: মেমরিতে দুটি আলাদা object. আর a+b*c বনাম a + (b * c): একই গাছ। শেষ লাইন অংশ ২-এর দাবি প্রমাণ করে: eq আছে কিন্তু frozen নয়, তাই node hash করা যায় না।

কোন ধাঁচ কখন? নতুন একটি কাজ (যেমন একটি linter) যোগ করতে visitor সহজ: একটি নতুন class, পুরোনো কোড অস্পর্শিত। নতুন একটি node-ধরন (যেমন Haat-এ একটি Match) যোগ করতে হলে প্রতিটি visitor-এ একটি method লাগে, আর কোনটি ভুলে গেলেন তা generic চুপচাপ ঢেকে দেয়। Pattern matching-এ উল্টো ঝামেলা কম নয়, তবে যে ভাষায় compiler exhaustiveness যাচাই করে (Rust, OCaml, Haskell, বা Java 21-এর sealed interface-এর ওপর switch), সেখানে বাদ পড়া case-টি compile-এর সময়েই ধরা পড়ে। এই টানাপোড়েনের নাম expression problem (পর্ব ২৪)।

৬ · Round trip একটি property — এলোমেলো গাছ আর shrinking

পর্ব ৪৫-এ round-trip test দেখেছিলেন: হাতে বাছা কয়েকটি program-এ parse → fmt → parse. সেখানে একটি উপপাদ্যও ছিল: round trip থাকলে printer injective. এবার পরীক্ষাটিকে একটি property-based test বানাই: উদাহরণ হাতে না লিখে একটি generator হাজারটা এলোমেলো গাছ বানায়, আর প্রতিটিতে একটি বৈশিষ্ট্য (property) যাচাই হয়:

Property ৪৯.৩ — round trip আর idempotence

প্রতিটি গাছ t-র জন্য: (ক) parse(fmt(t)) ≅ t, আর (খ) fmt(parse(fmt(t))) = fmt(t). (ক) বলে printer অর্থ হারায় না; (খ) বলে formatter দুবার চালালে ফাইল আর বদলায় না।

লক্ষ করুন দিকটি: এখানে শুরু গাছ থেকে, লেখা থেকে নয়। এলোমেলো লেখা থেকে শুরু করলে বেশিরভাগই অবৈধ হতো, আর বৈধগুলোতেও বন্ধনী মানুষের বসানো। এলোমেলো গাছ সরাসরি এমন আকার বানায়, যা কোনো মানুষ হয়তো লিখত না: (< (&& 63 a) (! a))-এর মতো type-এর দিক থেকে অর্থহীন গাছও। Printer-কে সেগুলোও ঠিক ছাপতে হয়, কারণ fmt চলে type checker-এর আগে।

Property ভাঙলে প্রথম ব্যর্থ গাছটি সাধারণত বড় আর জটিল। তাই tool সেটিকে ছোট করে: গাছের বদলে একটি নাম, অথবা একটি সন্তান, অথবা একটি সন্তানকে ছোট করা, যতক্ষণ পরীক্ষা ব্যর্থ থাকে। একে বলে shrinking; QuickCheck (Koen Claessen আর John Hughes, ২০০০, Haskell) আর Python-এর Hypothesis-এর মতো tool এটি নিজেই করে। নিচের block-এ সবকিছু হাতে লেখা, ২৭ লাইনে।

import random
from dataclasses import replace
def gen(r, d):                                   # a random expression tree, depth <= d
    x = r.random()
    if d == 0 or x < 0.2: return r.choice([Var(r.choice("abcf")), Num(r.randrange(100)), Bool(x < 0.1)])
    if x < 0.35: return Unary(r.choice("-!"), gen(r, d - 1))
    if x < 0.85: return Binary(r.choice(list(LEVEL)), gen(r, d - 1), gen(r, d - 1))
    return Call(gen(r, d - 1), [gen(r, d - 1) for _ in range(r.randrange(3))])
def ok(t):                                       # the round-trip property for one tree
    try: return parse(expr(t)) == t and expr(parse(expr(t))) == expr(t)
    except SyntaxError: return False
def smaller(t):                                  # x itself, a child, or t with a smaller child
    kids = [(f.name, getattr(t, f.name)) for f in fields(t)]
    if t != Var("x"): yield Var("x")
    yield from (a for _, v in kids for a in (v if isinstance(v, list) else [v]) if is_dataclass(a))
    yield from (replace(t, **{k: s}) for k, v in kids if is_dataclass(v) for s in smaller(v))
def shrink(t):                                   # greedy: keep any smaller tree that still fails
    return next((shrink(s) for s in smaller(t) if not ok(s)), t)
def check(n=1500, seed=49):
    r = random.Random(seed); bad = [t for t in (gen(r, 4) for _ in range(n)) if not ok(t)]
    print(f"{n} trees, {len(bad)} failed", end="")
    if bad: s = shrink(bad[0]); print(f"; shrunk: {sexpr(s)} -> {expr(s)}", end="")
    print()
check()                                          # the printer as written
NONASSOC = set()                                 # plant a bug: the printer forgets rule 2
check()
NONASSOC = {3, 4}; check(seed=7)                 # fixed again; another seed

আসল আউটপুট (ব্রাউজারের Python):

1500 trees, 0 failed
1500 trees, 177 failed; shrunk: (> (< x x) x) -> x < x > x
1500 trees, 0 failed

প্রথম লাইন: সঠিক printer, seed 49, ১৫০০টি গাছ, একটিও ব্যর্থ নয়। দ্বিতীয় লাইনে printer-এর NONASSOC-কে খালি করে একটি bug বসানো হলো (R1-এর দ্বিতীয় অংশ মুছে যায়); parser-এর নিজের নিয়ম (3, 4) অক্ষত। ১৭৭টি গাছ ব্যর্থ, আর shrink-এর পরে সবচেয়ে ছোট উদাহরণ x < x > x: ঠিক সেই শিকল, যা Haat নিষেধ করে। তৃতীয় লাইনে bug সারানো, অন্য একটি seed-এ আবার ০। Parser আর printer যদি একই NONASSOC ভাগ করত, তাহলে bug বসালে দুটিই একসঙ্গে বদলাত, আর round trip হয়তো চুপ থাকত: পরীক্ষার দুই পক্ষের জ্ঞান আলাদা রাখাই এর শক্তি।

1t = gen(r, 4)  # 1500 বার2text = expr(t)3parse(text) == t ?4s = shrink(t)5NONASSOC = {3, 4}
গাছ আর অবস্থা
printer
গাছ
fmt
  1. সঠিক printer. Generator (seed 49) ১৫০০টি গাছ বানায়, গভীরতা ৪ পর্যন্ত। প্রতিটি ছাপা, আবার parse, তুলনা, আর দ্বিতীয়বার ছাপা: সব পাস।
  2. Bug বসানো. Printer-এর নকলে NONASSOC খালি: R1 আর তুলনা-শিকল চেনে না। ১৫০০টির ১৭৭টি ব্যর্থ; প্রথমটি তালিকার ৩ নম্বর (শূন্য থেকে গোনা) গাছ, ২৩টি node, গভীরতা ৫। তার ছাপা লেখায় 27 নম্বর column-এর <=-এ parser শিকল দেখে থামে।
  3. ছোট করা, ধাপ ১. Shrinker প্রথমে পুরো গাছকে x দিয়ে বদলে দেখে: সেটি পাস করে, তাই বাদ। তারপর সন্তানেরা: ১৪-node-এর ডান সন্তান এখনো ব্যর্থ, তাই এটিই নতুন গাছ; তার ভেতরের ৭-node-এর একটি subtree, (> (< false false) (+ b 62)), আরও ছোট আর এখনো ব্যর্থ।
  4. ছোট করা, ধাপ ২. এবার পাতাগুলো একে একে x: দুটি false বদলায়, কারণ বদলের পরেও পরীক্ষা ব্যর্থ। আকার একই (৭), কিন্তু গাছ সরলতর।
  5. সবচেয়ে ছোট. b + 62-এর জায়গায় x: (> (< x x) x), ৫টি node, ছাপা x < x > x, error 1:7-এ। এখান থেকে যেকোনো ছোট গাছ পাস করে, তাই shrinker থামে। Bug-এর কারণ এক নজরে বোঝা যায়।
  6. সারানো. NONASSOC = {3, 4} ফেরানো হলো। একই গাছ এখন (x < x) > x, round trip ঠিক; অন্য seed (7)-এ ১৫০০টিতে ০ ব্যর্থ। ভালো অভ্যাস: ছোট করা উদাহরণটি একটি স্থায়ী regression test হিসেবে রেখে দিন, যেমন reference রাখে print((a - (b - c)) * -(d + 1));.

সব bug এত সহজে ধরা পড়ে না। ল্যাবে একই ১৫০০টি গাছে আরও তিনটি bug বসিয়েছি (প্রতিটি একটি অসমতা বদলে):

Bugব্যর্থ (১৫০০-এর মধ্যে)ধরনShrink-এর ফল
R1-এ N বাদ১৭৭১৭৭টিই parse errorx < x > x
R2-তে ≤ বদলে <২৯৪১৮০ error, ১১৪ চুপচাপ অন্য গাছ(* x (* x x)) → x * x * x
R3-তে ৭ বদলে ৬১১২সবগুলো চুপচাপ অন্য গাছ(! (% x x)) → !x % x
R4-এ ৮ বদলে ৭১৫২সবগুলো চুপচাপ অন্য গাছ৫-node-এর একটি Call (অনুশীলন ১)

“চুপচাপ অন্য গাছ” বিপজ্জনক: program চলে, ভুল মান দেয়, কোনো error নেই। যেমন R3-এর bug-এ !(x % y) ছাপা হয় !x % y, যা Haat-এ (% (! x) y), একটি ভিন্ন গাছ। এমন bug শুধু golden file দিয়ে ধরতে হলে ঠিক সেই আকারের একটি উদাহরণ কাউকে লিখে রাখতে হতো।

৭ · AST-এর অন্য রূপ — arena, hash-consing আর lossless গাছ

Python-এর dataclass গাছ শেখার জন্য চমৎকার, কিন্তু একমাত্র রূপ নয়। বড় compiler তিনটি দিকে অন্যভাবে ভাবে।

Arena আর index. লক্ষ লক্ষ ছোট node আলাদা আলাদা object হলে মেমরি ছড়িয়ে থাকে, আর প্রতিটি pointer ৮ byte. বিকল্প: সব node একটি বড় array-তে, আর সন্তানের জায়গায় সংখ্যা (index). একে বলে arena allocation. p - p / 10-এর গাছ, Pratt parser যে ক্রমে node বানায় সেই ক্রমে:

indexkindকখcol
0Var"p"—1
1Var"p"—5
2Num10—9
3Binary /127
4Binary -033

মূল node সবার শেষে (৪), আর প্রতিটি সন্তানের index তার মা-বাবার চেয়ে ছোট, কারণ parser আগে সন্তান বানায়। ফলে index-এর ক্রমে একবার এগোলেই একটি post-order হাঁটা হয়, কোনো recursion ছাড়া। গাছ ছাড়তে একটিমাত্র array ছাড়লেই চলে। বাস্তবে rustc ব্যাপকভাবে arena ব্যবহার করে, আর Zig-এর compiler-এর AST, প্রকাশিত নকশা-আলোচনা অনুযায়ী, pointer-এর বদলে ৩২-বিট index-এর কয়েকটি সমান্তরাল array-তে থাকে।

Hash-consing. অংশ ১-এর টেবিলে ছিল: bazar.haat-এর ৭২টি subtree-র মাত্র ৫৭টি আলাদা। Hash-consing প্রতিটি নতুন node বানানোর আগে একটি টেবিলে খোঁজে, একই গঠন থাকলে পুরোনোটি ফেরত দেয়। তখন গাছটি আসলে একটি DAG, দুটি price(2, 520) একই object, আর সমতা যাচাই হয় একটি is-এ। দাম: node তখন অবশ্যই immutable, আর অবস্থান রাখা যায় না (দুটি price(2, 520)-এর column আলাদা)। তাই এই কৌশল সাধারণত type, SMT সূত্র বা optimizer-এর expression-এ দেখা যায়, parser-এর AST-এ কম; পর্ব ৬৫-এর common subexpression elimination একই ধারণার আত্মীয়।

Lossless গাছ. Formatter, refactoring আর editor-এর জন্য comment আর ফাঁকা ঘর হারানো চলে না। তাদের লাগে একটি lossless syntax tree: parse tree-র মতো প্রতিটি token থাকে, সঙ্গে প্রতিটি token-এর আগে-পরের ফাঁকা ঘর আর comment (“trivia”). এর ওপর থেকে একটি AST-এর মতো দৃশ্য তৈরি করা হয়। পর্ব ৮০-তে (Language tooling) এ বিষয়ে ফিরব।

আরও গভীরে: C#-এর Roslyn compiler, তার প্রকাশিত নকশা অনুযায়ী, দুই স্তরের গাছ রাখে: ভেতরে immutable “green” node, যা অবস্থান জানে না, শুধু নিজের দৈর্ঘ্য জানে, তাই একই subtree অনেক জায়গায় ভাগ করা যায়; বাইরে চাহিদামতো তৈরি “red” node, যা মা-বাবা আর অবস্থান জানে। এডিটরে একটি অক্ষর বদলালে শুধু বদলানো পথের green node নতুন হয়। rust-analyzer-এর rowan আর Swift-এর SwiftSyntax একই ধারণার আত্মীয় বলে পরিচিত। Pretty printing-এর তত্ত্বও পুরোনো: Derek Oppen-এর ১৯৮০ সালের algorithm থেকে Philip Wadler-এর “A prettier printer” পর্যন্ত, যার ধারণা আজকের অনেক code formatter-এ দেখা যায়।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় AST নিয়ে এমন প্রশ্ন প্রায়ই দেখা যায়:

  • Parse tree আর AST-এর পার্থক্য? Parse tree-তে প্রতিটি ব্যাকরণ-নিয়ম আর প্রতিটি token; AST-এ শুধু অর্থ, বন্ধনী আর মাঝের স্তর বাদ। (a + b) * c-এ ৩২ বনাম ৫টি node (Haat-এর EBNF ধরে)।
  • a * (b + c) - d-এর AST আঁকুন। মূলে -; বাঁয়ে * (a আর +(b, c)), ডানে d.
  • একটি printer কখন বন্ধনী দেবে? সন্তানের operator দুর্বল হলে; ডান দিকে একই স্তর হলেও (বাঁ-সংযোজী operator-এ); non-associative হলে বাঁয়েও।
  • Visitor pattern কী, কেন? প্রতিটি node-ধরনের জন্য একটি method; নতুন কাজ যোগ সহজ, নতুন node যোগ কঠিন (expression problem).
  • Parser কীভাবে পরীক্ষা করবেন? এলোমেলো গাছে parse(print(t)) = t, ব্যর্থ হলে shrink করে ছোট উদাহরণ।

৮ · AI-এর যুগে AST আর printer

“এই AST থেকে source লেখার একটি printer দাও” — AI assistant এটি সহজেই লেখে, আর ছোট উদাহরণে প্রায়ই ঠিক দেখায়। ভুল লুকিয়ে থাকে কিনারায়, যেখানে উপরের চারটি নিয়ম সূক্ষ্ম। এই বিষয়ে বারবার দেখা ভুল:

AI-এর ভুলকীভাবে ধরবেন
ডান দিকে একই স্তরে বন্ধনী ভুলে যাওয়া: a - (b - c) থেকে a - b - cএলোমেলো গাছে round trip; ছোট করা উদাহরণ regression test হিসেবে রাখা
এক ভাষার নিয়ম চাপানো: Python-এর মতো তুলনা-শিকল বৈধ ধরা, বা C-র precedence (যেখানে == আর &-এর ক্রম আলাদা) ধরে নেওয়াSpec-এর precedence টেবিল আর decision 10 পাশে রেখে, reference-এর fmt-এর সঙ্গে differential test
Unary আর call ভুলে যাওয়া: -(a + b)-কে -a + b, (f + g)(x)-কে f + g(x)Generator-এ Unary আর Call রাখা; শুধু binary নয়
সমতা-তুলনায় অবস্থান ঢুকিয়ে ফেলা, ফলে round trip সবসময় “ব্যর্থ”, বা উল্টো, শুধু লেখা তুলনা করে গাছ যাচাই না করাসমতার সংজ্ঞা লিখে রাখা; অবস্থান-বাদ তুলনা আর idempotence দুটিই যাচাই
Python-এর API বা version নিয়ে ভুল দাবি (যেমন কোন version-এ ast.unparse বা ast.compare এসেছে)নিজের Python-এ চালিয়ে দেখা, documentation-এর “Added in version” পড়া
নিজে বানানো আউটপুট: “এই printer এটি ছাপবে”নিজে চালানো; AI-কে আউটপুট অনুমান করতে নিষেধ করা

AI-কে printer লেখার যন্ত্র না বানিয়ে কঠিন উদাহরণ খোঁজার সঙ্গী বানান। যেমন:

আমি Haat নামের একটি শিক্ষণ-ভাষার pretty printer পরীক্ষা করছি (Python 3, শুধু standard library). নিয়ম: - precedence (নিচু থেকে উঁচু): || , && , == != , < <= > >= , + - , * / % , prefix - ! , call f(a) - সব binary operator বাঁ-সংযোজী; কিন্তু দুই তুলনা-স্তরই non-associative, তাই a < b < c একটি syntax error - printer সবচেয়ে কম বন্ধনী দেয় ১. S-expression আকারে ২০টি AST দাও, যেগুলো বন্ধনীর কিনারা ছোঁয় (ডান দিকে একই স্তর, তুলনা-শিকল, unary-র নিচে binary, call-এর callee হিসেবে binary). ২. প্রতিটির জন্য তোমার প্রত্যাশিত লেখা দাও, আর যেগুলোতে নিশ্চিত নও, "অনিশ্চিত" লেখো। ৩. Python বা C-র নিয়ম ধরে নেবে না; উপরের নিয়মে না থাকলে বলো "নিয়মে নেই"। ৪. কোনো কোড চালানোর ফল নিজে বানিয়ে লিখবে না; আমি reference-এর fmt দিয়ে মেলাব।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন।

প্র ০১Compiler কেন parse tree না রেখে AST বানায়, অথচ editor আর formatter কেন আবার parse tree-র মতো গাছ ফিরিয়ে আনে?

Compiler-এর পরের প্রতিটি ধাপ প্রশ্ন করে অর্থ নিয়ে: এই নামটি কোন ঘোষণা, এই expression-এর type কী, এই operation কোন instruction হবে। Parse tree-তে সেই উত্তরের চারপাশে প্রচুর গোলমাল: bazar.haat-এর ক্ষেত্রে ৪৩০টি node-এর বেশিরভাগ ব্যাকরণের স্তর-বিন্যাসের চিহ্ন, যা শুধু precedence বোঝাতে ব্যাকরণে ঢুকেছিল। Type checker যদি parse tree-তে চলত, তাকে প্রতিটি expr → andExpr → … → primary শিকল পার হতে হতো, আর ব্যাকরণ সামান্য বদলালেই (যেমন নতুন একটি precedence-স্তর) type checker-ও বদলাতে হতো। AST এই নির্ভরতা কেটে দেয়: ব্যাকরণ বদলায়, parser বদলায়, কিন্তু AST একই থাকলে পরের সব ধাপ অপরিবর্তিত। এ কারণেই ব্যাকরণকে বলা হয় concrete syntax আর AST-কে abstract syntax; দ্বিতীয়টি ভাষার আসল কাঠামো।

Editor-এর প্রশ্ন আলাদা। একটি formatter ফাইল নতুন করে সাজায়, কিন্তু comment ফেলে দিলে ব্যবহারকারী ক্ষিপ্ত হবেন। একটি refactoring tool একটি নাম বদলায়, বাকি ফাইলের প্রতিটি অক্ষর অক্ষত রেখে। এখানে “লেখায় উদাসীনতা” গুণ নয়, দোষ। তাই এই tool-গুলো lossless গাছ রাখে, যেখানে প্রতিটি token আর তার আশেপাশের ফাঁকা ঘর ও comment আছে। Roslyn, rust-analyzer আর SwiftSyntax-এর মতো প্রকল্প এই ধরনের গাছকে কেন্দ্রে রেখেছে বলে তাদের নকশা-আলোচনা থেকে জানা যায়।

মাঝের পথও আছে। Go-র gofmt (২০০৯ সালে Go-র সঙ্গেই আসে) একটি সাধারণ AST-এ কাজ করে, আর comment-গুলো আলাদা তালিকায় রেখে অবস্থান দেখে আবার বসায়; এতে কিছু কোণার ক্ষেত্রে জটিলতা থাকে, কিন্তু compiler আর formatter একই parser ভাগ করতে পারে। Haat-এর fmt সবচেয়ে সরল পথ নিয়েছে: comment ফেলে দেয়, যা শেখার জন্য ঠিক, কিন্তু একটি সত্যিকারের formatter-এর জন্য নয়।

মূল উপলব্ধি: গাছের নকশা নির্ভর করে কে গাছটি পড়বে তার ওপর। অর্থের প্রশ্নের জন্য AST, লেখা ফেরানোর প্রশ্নের জন্য lossless গাছ; অনেক আধুনিক tool দুটিকে একসঙ্গে রাখে, একটির ওপর আরেকটির দৃশ্য বানিয়ে।

প্র ০২AST-এর node বদলানো যাবে কি না — resolver আর type checker তাদের ফল node-এর ভেতরে লিখবে, না আলাদা টেবিলে?

সবচেয়ে সোজা পথ: প্রতিটি Var-এ একটি binding ঘর আর প্রতিটি expression-এ একটি type ঘর রাখা, যা resolver আর checker ভরবে। অনেক শিক্ষণ-compiler তাই করে, আর পড়তে সহজ। সমস্যা ধীরে ধীরে দেখা দেয়। প্রথমত, node-এর ধরন তখন সময়ের ওপর নির্ভর করে: parser-এর পরে type খালি, checker-এর পরে ভরা, আর কোনো function জানে না সে কোন অবস্থার গাছ পেয়েছে। দ্বিতীয়ত, একই গাছের ওপর দুটি বিশ্লেষণ পাশাপাশি চালানো, বা একটি বিশ্লেষণ বাতিল করে আবার চালানো (editor-এ প্রতিটি কী-চাপে) কঠিন হয়, কারণ পুরোনো ফল গাছেই লেগে থাকে।

Haat reference দ্বিতীয় পথ নিয়েছে: resolver-এর ফল একটি Resolution, যার uses আর decls dict-এর চাবি id(node), অর্থাৎ একটি side table. গাছ parser-এর পরে কেউ বদলায় না; প্রতিটি পরের ধাপ গাছ আর প্রয়োজনীয় টেবিল দুটিই হাতে পায়। id-কে চাবি করার একটি সূক্ষ্মতা আছে: Python-এ object বেঁচে থাকা পর্যন্তই তার id অনন্য, তাই গাছটি বাঁচিয়ে রাখতে হয়, আর গাছের একটি কপি বানালে টেবিল আর মেলে না। বড় compiler সাধারণত প্রতিটি node-কে একটি স্থায়ী সংখ্যা দেয় আর সেটিকে চাবি করে; rustc-এর HIR-এ প্রতিটি node-এর একটি ID থাকে, যা এই ধারণার পরিচিত উদাহরণ।

অন্য প্রান্তে আছে পুরো immutable গাছ আর “নতুন গাছ বানানো” ধাঁচ: একটি pass পুরোনো গাছ পড়ে নতুন গাছ ফেরত দেয়, যেমন পর্ব ৫৫-এর desugaring. Python-এর ast.NodeTransformer মাঝামাঝি: সে node বদলাতে বা নতুন node ফেরত দিতে দুটিই দেয়। Immutable গাছের সুবিধা হলো ভাগ করা: অপরিবর্তিত subtree নতুন গাছেও একই object থাকে, Roslyn-এর green node-এর মতো। দাম হলো প্রতিটি ছোট পরিবর্তনে মূল পর্যন্ত পথটি নতুন করে বানানো।

মূল উপলব্ধি: AST-কে parser-এর পরে স্থির রাখুন, আর বিশ্লেষণের ফল রাখুন আলাদা, স্পষ্ট টেবিলে। এতে প্রতিটি ধাপের ইনপুট আর আউটপুট পরিষ্কার, পরীক্ষা সহজ, আর একই গাছে কয়েকটি বিশ্লেষণ নিরাপদে চলে।

প্র ০৩Visitor pattern আর pattern matching — ইতিহাস কী শেখায়, আর একটি নতুন compiler কোনটি দিয়ে শুরু করবে?

ML (১৯৭০-এর দশক) আর পরে Haskell-এ AST-এর ওপর কাজ মানেই pattern matching: case e of Binary(op, l, r) => …. Compiler-লেখকদের মধ্যে একটি প্রচলিত কথা আছে যে ML পরিবারের ভাষা compiler লেখার জন্যই যেন বানানো, আর এর বড় কারণ এই ধাঁচ: data type আর তার ওপর match, সঙ্গে compiler-এর exhaustiveness যাচাই। Object-oriented ভাষায় এই সুবিধা ছিল না। ১৯৯৪ সালে Design Patterns বইয়ের visitor সেই ফাঁক পূরণ করল: accept আর visitX দিয়ে double dispatch, যাতে node-এর class না বদলে নতুন কাজ যোগ করা যায়। দীর্ঘদিন Java আর C++-এর compiler আর tool এভাবে লেখা হয়েছে; ANTLR-এর মতো parser generator এখনো visitor-এর কাঠামো তৈরি করে দেয়।

গত কয়েক বছরে mainstream ভাষাগুলো pattern matching নিয়েছে: Python 3.10-এ match (PEP 634), Java-তে record (Java 16), sealed class (Java 17) আর Java 21-এ switch-এ pattern (JEP 441), C#-এ ধাপে ধাপে pattern. Java 21-এ sealed interface-এর ওপর switch হলে compiler বলে দেয় কোনো permitted subclass বাদ পড়েছে কি না, অর্থাৎ ML-এর exhaustiveness যাচাই এখন Java-তেও পাওয়া যায়। Python-এর match এই যাচাই করে না; সেখানে type checker (যেমন mypy) কিছু ক্ষেত্রে সাহায্য করতে পারে।

দুই ধাঁচের পার্থক্য expression problem-এর দুই দিক। Visitor-এ নতুন কাজ যোগ সহজ, নতুন node-ধরন কঠিন; আর Python-এর মতো নাম ধরে খোঁজা visitor-এ ভুলে যাওয়া visit_X চুপচাপ generic-এ চলে যায়, যা একটি নীরব bug. Pattern matching-এ কাজটি এক জায়গায় পড়া যায়, আর exhaustiveness-যাচাই থাকলে নতুন node যোগ করলে compiler প্রতিটি অসম্পূর্ণ match দেখিয়ে দেয়। Haat-এর ক্ষেত্রে, যেখানে node-এর তালিকা প্রায় স্থির আর কাজ (resolver, checker, interpreter, compiler, printer) বাড়তে থাকে, দুটিই চলে।

মূল উপলব্ধি: ভাষা যদি sum type আর exhaustiveness যাচাই দেয়, pattern matching দিয়ে শুরু করুন; না দিলে visitor একটি পরীক্ষিত বিকল্প। যেটিই নিন, “কোনো node-ধরন বাদ পড়ল কি না” প্রশ্নের একটি যান্ত্রিক উত্তর রাখুন: compiler-এর যাচাই, নয়তো একটি পরীক্ষা যা প্রতিটি node-ধরন অন্তত একবার চালায়।

প্র ০৪এলোমেলো গাছে round trip কতটা শক্ত পরীক্ষা? ১৫০০টি গাছে ০ ব্যর্থ মানে কি printer নির্ভুল?

Property-based testing-এর জনপ্রিয়তা আসে Koen Claessen আর John Hughes-এর QuickCheck (২০০০, Haskell) থেকে: একটি property লিখুন, tool হাজার উদাহরণ বানাবে, আর ব্যর্থ হলে ছোট করে দেখাবে। পরে Erlang, Scala, Python (Hypothesis) সহ বহু ভাষায় এর রূপ এসেছে। Parser আর printer-এর জোড়া এর জন্য প্রায় আদর্শ, কারণ property-টি স্বাভাবিক (একটি অন্যটির বিপরীত), আর কোনো প্রত্যাশিত আউটপুট হাতে লিখতে হয় না।

কিন্তু “০ ব্যর্থ” একটি নমুনার কথা, প্রমাণ নয়। প্রথম প্রশ্ন generator-এর বিতরণ। এই পর্বের generator গভীরতা ৪-এ থামে, Str আর Lambda বানায় না, আর প্রতিটি সন্তান স্বাধীনভাবে বাছে। ফলে "a\"b"-এর মতো escape-ওয়ালা string-এর bug এই পরীক্ষা কখনো ধরবে না। বসানো bug-এর টেবিলে R3-এর bug ১৫০০-এর ১১২টিতে ধরা পড়েছে; যদি generator unary কম বানাত, হয়তো একটিতেও নয়। তাই generator নিজেও পরীক্ষার যোগ্য: কোন ধরনের node কতবার আসে, গুনে দেখা।

দ্বিতীয় প্রশ্ন oracle-এর অন্ধ জায়গা। Round trip ধরে না, যদি parser আর printer একই ভুল ধারণা ভাগ করে: দুজনেই যদি --কে ডান-সংযোজী ভাবে, তাহলে printer ঠিক সেই অনুযায়ী বন্ধনী দেবে, round trip পাস, অথচ ভাষাটি ভুল। এ কারণেই এই পর্বে parser-এর তুলনা-নিয়ম printer-এর NONASSOC থেকে আলাদা রাখা, আর আলাদা করে reference-এর সঙ্গে ২০,০০০ গাছে differential test, যা অন্য একটি স্বাধীন বাস্তবায়নকে oracle বানায়।

তৃতীয়ত, shrinking-এর গুণমান। এই পর্বের greedy shrinker list-এর ভেতরে ঢোকে না, তাই R4-এর bug-এ পাওয়া উদাহরণ পুরোপুরি ছোট নয় (অনুশীলন ১)। Hypothesis-এর মতো tool shrinking-কে আরও সাধারণভাবে করে, তবু তারাও সবসময় “সবচেয়ে ছোট” নিশ্চিত করে না।

মূল উপলব্ধি: Property test সংখ্যার জোরে অপ্রত্যাশিত আকারের ভুল ধরে, কিন্তু generator যা বানায় না আর oracle যা দেখে না, তা নিয়ে চুপ থাকে। প্রমাণের রূপরেখা, differential test আর কয়েকটি হাতে বাছা regression test মিলিয়েই আস্থা আসে।

প্র ০৫প্রতিটি node-এ অবস্থান রাখা: একটি বিন্দু যথেষ্ট, না span লাগবে? আর line:col, না ফাইলের শুরু থেকে offset?

Haat একটি বিন্দু রাখে, আর সেটি ভেবেচিন্তে বাছা: Binary-র ক্ষেত্রে operator, Call-এর ক্ষেত্রে callee-র শুরু। এতে division by zero সরাসরি / দেখায়, আর wrong argument count দেখায় callee. কিন্তু আধুনিক diagnostic আরও চায়: rustc আর Clang-এর মতো compiler ভুলের পুরো অংশ ^~~~~ দিয়ে দাগায়, আর type mismatch-এ পুরো expression-টি। তার জন্য span লাগে, শুরু আর শেষ। Clang-এর AST node-গুলো getSourceRange() দিয়ে এমন একটি পরিসর দেয়; CPython-এর ast চারটি সংখ্যা রাখে (lineno, col_offset, end_lineno, end_col_offset), যা অংশ ২-এর run-এ দেখেছেন।

কী গুনবেন, সেটিও সিদ্ধান্ত। CPython-এর col_offset UTF-8 byte গোনে: s = "চাল" + y-এ y-এর offset 18, যদিও তার আগে ১২টি অক্ষর। Haat অক্ষর (code point) গোনে, তাই একই জায়গা হতো column 13. দুটিই যুক্তিসংগত: byte দিয়ে ফাইলে সরাসরি লাফ দেওয়া যায়, অক্ষর দিয়ে মানুষের চোখের সঙ্গে মেলে। ভুল হলো না জেনে মেশানো: editor এক রকম গোনে, compiler আরেক রকম, আর বাংলা লেখার লাইনে লাল দাগ ভুল জায়গায় পড়ে। পর্ব ২১-এ এই পার্থক্য বিস্তারিত।

মেমরির প্রশ্নও আছে। প্রতিটি node-এ দুটি পূর্ণসংখ্যা Python-এ বড় কিছু নয়, কিন্তু লক্ষ node-এর C++ compiler-এ প্রতিটি byte গোনে। তাই বড় compiler প্রায়ই একটি ছোট সংখ্যা রাখে, ফাইলের (বা সব ফাইল জুড়ে) offset, আর লাইনের শুরুগুলোর একটি টেবিল থেকে দরকার হলে line ও column বের করে। Span-এর জন্য শুরুর offset আর দৈর্ঘ্য রাখলেই চলে, যেমন Roslyn-এর green node শুধু দৈর্ঘ্য জানে আর অবস্থান হিসাব করে মা-বাবার কাছ থেকে।

মূল উপলব্ধি: অবস্থান AST-এর সবচেয়ে মূল্যবান “বাড়তি” তথ্য, আর তার নকশা তিন প্রশ্নের উত্তর: বিন্দু না span, কী গুনবেন (byte, অক্ষর, UTF-16 unit), আর কীভাবে সংকুচিত রাখবেন। উত্তর spec-এ লিখুন, আর বাংলা লেখাসহ ফাইলে পরীক্ষা করুন।

অনুশীলন

প্রথমটিতে কোড লিখতে হবে; বাকিগুলো ভুল খোঁজা ও প্রমাণ, আউটপুট অনুমান আর নকশা।

  1. Shrinker উন্নত করুন (বাস্তবায়ন): অংশ ৬-এর smaller একটি Call-এর args list-এর ভেতরে কিছু ছোট করে না। ল্যাবে R4-এর bug (callee-র সীমা ৮-এর বদলে ৭) বসালে seed 49-এ ১৫০০-এর ১৫২টি গাছ ব্যর্থ হয়, আর বর্তমান shrinker থামে (call (! x) (- true (&& b 24)) b)-এ। smaller-কে বাড়ান, যাতে সে (ক) একটি argument মুছে আর (খ) একটি argument-কে ছোট করে চেষ্টা করে। চার block চালানোর পরে আপনার কোড চালিয়ে দেখুন।

    পুরোনো smaller-কে রেখে তার পরে list-এর জন্য নতুন প্রার্থী যোগ করুন:

    old_smaller = smaller
    def smaller(t):
        yield from old_smaller(t)
        for k, v in [(f.name, getattr(t, f.name)) for f in fields(t)]:
            if isinstance(v, list):
                for i in range(len(v)):
                    yield replace(t, **{k: v[:i] + v[i + 1:]})          # drop one argument
                    yield from (replace(t, **{k: v[:i] + [s] + v[i + 1:]}) for s in smaller(v[i]))

    old_smaller-এর ভেতরের recursive ডাক global নাম smaller খোঁজে, তাই সেটিও নতুন রূপটিই ডাকে। ল্যাবে R4-এর bug-সহ চালিয়ে পাওয়া ফল: ১৫২টি ব্যর্থ, আর shrink-এর পরে (call (! x)), ছাপা !x(), যা parse হয় (! (call x)): একটি unary-কে ডাকা হচ্ছিল, কিন্তু বন্ধনী না থাকায় call চলে গেছে x-এর গায়ে। ছোট উদাহরণে কারণটি স্পষ্ট। প্রতিটি প্রার্থী আগের চেয়ে কম node-এর, অথবা একই আকারে একটি অ-x পাতা কম, তাই shrinking অবশ্যই থামে।

  2. ভুল খুঁজুন আর প্রমাণ করুন: একজন প্রোগ্রামার ভাবলেন, “+ আর * associative, তাই ডান দিকে একই স্তরে বন্ধনী লাগে না”, আর R2 বদলে লিখলেন level(e.right) < p. (ক) এই printer (* x (* x x))-কে কী ছাপবে, আর reference সেই লেখা কোন গাছ হিসেবে পড়বে? (খ) প্রমাণ করুন যে এই printer round trip ভাঙে। (গ) ভুলটি কেন “শুধু বিয়োগ আর ভাগে সমস্যা” নয়?

    (ক) ডান দিকের *-এর স্তর ৬, আর ৬ < ৬ মিথ্যা, তাই বন্ধনী নেই: x * x * x. বাঁ-সংযোগের কারণে parser পড়ে (* (* x x) x). ল্যাবে এই bug-এর shrink ঠিক এই উদাহরণে থেমেছে; ১৫০০-এর ২৯৪টি ব্যর্থ (১৮০টি parse error, ১১৪টি চুপচাপ অন্য গাছ)।

    (খ) প্রমাণ. (১) t = (* x (* x x)). (২) ভুল printer লেখে fmt(t) = x * x * x. (৩) Haat-এর সব binary operator বাঁ-সংযোজী, তাই parse(x * x * x) = (* (* x x) x). (৪) এটি t নয়, কারণ মূলের বাঁ সন্তান t-তে একটি Var, আর এখানে একটি Binary. তাই parse(fmt(t)) ≠ t, round trip ভাঙে। ∎ (পর্ব ৪৫-এর উপপাদ্য দিয়েও: t আর (* (* x x) x) দুটির fmt একই, তাই fmt injective নয়।)

    (গ) কারণ AST-এর কাজ গাছ রক্ষা করা, মান নয়। x * (x * x) আর x * x * x Haat-এ একই মান দেয় (wrapping গুণ associative), কিন্তু পরের ধাপগুলো গাছ দেখে: bytecode-এর ক্রম, error-এর অবস্থান, আর একটি formatter যে ফাইল পড়ে তা বদলে দিলে ব্যবহারকারী তা “অর্থ না বদলানো” মনে করেন না। তুলনার স্তরে (non-associative) একই ভুল আরও খারাপ: a < (b < c) হয়ে যায় a < b < c, যা syntax error. আর Str-এর + associative হলেও == নয়।

  3. আউটপুট অনুমান করুন: নিচের প্রতিটি S-expression একটি print(…);-এর ভেতরের AST. haat.py fmt প্রতিটির জন্য কী ছাপবে? তারপর বলুন (ছ)-এর গাছে কয়টি node আর গভীরতা কত।
    (ক) (- (- a))           (খ) (call (call f 1) 2)
    (গ) (! (== a b))         (ঘ) (== (< a b) (< c d))
    (ঙ) (/ (- x) (% y z))    (চ) (&& (|| (&& a b) (&& c d)) e)
    (ছ) (- a (+ b (* c d)))

    ল্যাবে প্রতিটি অতিরিক্ত বন্ধনীসহ লিখে reference-এর fmt দিয়ে চালানো (আর ফলের ast মূলের সঙ্গে হুবহু মেলে):

    print(--a);
    print(f(1)(2));
    print(!(a == b));
    print(a < b == c < d);
    print(-x / (y % z));
    print((a && b || c && d) && e);
    print(a - (b + c * d));

    (ক) ভেতরের Unary-র স্তর ৭, ৭ < ৭ মিথ্যা, তাই বন্ধনী নেই: --a; Haat-এ -- কোনো token নয়, তাই এটি দুটি MINUS. (খ) callee একটি Call (স্তর ৮), R4 বন্ধনী চায় না। (গ) == (৩) < ৭: বন্ধনী থাকে। (ঘ) দুই পাশে স্তর ৪, বাইরে ৩: ৪ > ৩, কোথাও বন্ধনী নেই; দুই আলাদা স্তরের তুলনা মেশানো বৈধ (decision 10). (ঙ) বাঁয়ে Unary (৭ ≥ ৬): বন্ধনী নেই; ডানে % (৬ ≤ ৬): বন্ধনী আছে। (চ) বাইরের &&-এর বাঁয়ে || (১ < ২): বন্ধনী; ভেতরের && দুটি ||-এর চেয়ে শক্ত, তাই বন্ধনী নেই। (ছ) ডানে + (৫ ≤ ৫): বন্ধনী; তার ভেতরে * (৬ > ৫): বন্ধনী নেই। (ছ)-এর গাছে ৭টি node (৩টি Binary, ৪টি Var), গভীরতা ৪: - → + → * → c.

  4. নকশা করুন — Haat-এর node-এ span: বাজারঘরের দল চায় type error-এ পুরো expression দাগানো হোক (^~~~~~)। প্রস্তাব: প্রতিটি node-এ end_line, end_col যোগ। (ক) কোন node-এর শেষ parser কোথা থেকে জানবে? (খ) start(e) কি তখনো লাগবে? (গ) কোন পরীক্ষাগুলো বদলাতে হবে, আর round trip-এর সমতায় কী ঘটবে? (ঘ) একটি সস্তা বিকল্প প্রস্তাব করুন।

    (ক) প্রতিটি node-এর শেষ = তার শেষ token-এর শেষ: literal আর নামের ক্ষেত্রে সেই token-এর column + দৈর্ঘ্য; Binary-র শেষ = ডান সন্তানের শেষ; Unary-র = operand-এর শেষ; Call-এর = বন্ধ )-এর পরে; Block-এর = }; Let, Return, Print, ExprStmt-এর = ;. তাই parser-কে “সর্বশেষ গ্রহণ করা token” মনে রাখতে হবে (reference-এর missing-; নিয়ম, decision 24, ইতিমধ্যে আগের token দেখে)। একটি সূক্ষ্মতা: বন্ধনীতে মোড়া expression (a + b)-এর span-এ বন্ধনী ঢুকবে কি না, সিদ্ধান্ত নিতে হবে; AST-এ বন্ধনী নেই, তাই সাধারণত ভেতরের অংশই span, আর মোড়ানো বন্ধনীর span আলাদা রাখা হয় না।

    (খ) শুরু তখনো আলাদা জিনিস: Binary-র অবস্থান operator (division by zero দেখানোর জন্য), কিন্তু span-এর শুরু বাঁ সন্তানের শুরু। তাই দুটি রাখা যায়: line, col (প্রধান বিন্দু) আর start/end (span), অথবা span-এর শুরু start(e) দিয়ে আগের মতো হিসাব।

    (গ) Error-এর বার্তা না বদলালে golden file অক্ষত; caret-সহ নতুন রূপ এলে err_*.out বদলাতে হবে (পর্ব ৫০)। Node-এর repr লম্বা হবে, তাই যে পরীক্ষা repr তুলনা করে, তা বদলাবে। Round trip-এ আরও দুটি field তুলনা থেকে বাদ দিতে হবে (compare=False), নইলে fmt-এর পরে span বদলে যাওয়ায় সব পরীক্ষা ব্যর্থ হবে।

    (ঘ) সস্তা বিকল্প: node-এ কিছু না বদলে, diagnostic দেওয়ার মুহূর্তে একটি ছোট function গাছ হেঁটে শুরু (start(e)) আর শেষ (ডানতম পাতা বা বন্ধ বন্ধনী) বের করবে, আর token-এর তালিকা থেকে দৈর্ঘ্য নেবে। মেমরি বাঁচে, কিন্তু প্রতিটি error-এ কিছু বাড়তি হিসাব; error বিরল, তাই প্রায়ই এটি যথেষ্ট। (এই উত্তরের কোনো কোড চালানো হয়নি; এটি নকশা।)

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি parser-printer জোড়ার property-based round-trip পরীক্ষা যে ক্রমে চলে, সেভাবে সাজান (▲▼ চেপে সরান)

  1. Seed দিয়ে একটি এলোমেলো AST বানানো
  2. Printer দিয়ে গাছটি লেখায় রূপান্তর
  3. সেই লেখা আবার parse করা
  4. অবস্থান বাদ দিয়ে দুটি গাছ তুলনা
  5. অমিল হলে গাছটি shrink করে সবচেয়ে ছোট ব্যর্থ উদাহরণ খোঁজা
  6. ছোট উদাহরণটি স্থায়ী regression test হিসেবে রাখা

Haat-এ print((a < b) == (c < d)); লেখা ফাইলে haat.py fmt কী ছাপে?

  • ইনপুটের মতোই, দুটি বন্ধনী-জোড়াসহ
  • print(a < b == (c < d));
  • print(a < b == c < d);
  • comparison operators cannot be chained error

Haat-এর সবচেয়ে কম বন্ধনীর printer AST (- a (- b c)) আর (- (- a b) c)-কে কীভাবে ছাপে?

  • দুটিই a - b - c
  • a - (b - c) আর a - b - c
  • a - (b - c) আর (a - b) - c
  • (a - b) - c আর a - (b - c)

Python-এ @dataclass (eq=True, frozen নয়) দিয়ে বানানো একটি AST node-এর ওপর hash(node) ডাকলে কী হয়?

  • Object-এর id থেকে একটি hash ফেরে
  • Field-গুলো থেকে hash হিসাব হয়
  • সবসময় 0 ফেরে
  • TypeError: unhashable type

একটি compiler-এ AST-এর node-ধরন প্রায় স্থির, কিন্তু নতুন বিশ্লেষণ (linter, metric, optimizer) প্রায়ই যোগ হয়। Visitor pattern এখানে কেন সুবিধার?

  • নতুন কাজ যোগ করতে পুরোনো node বা visitor বদলাতে হয় না
  • Visitor গাছের node-সংখ্যা কমিয়ে দেয়
  • Visitor সবসময় pattern matching-এর চেয়ে দ্রুত চলে
  • বাদ পড়া node-ধরন compiler নিজে ধরিয়ে দেয়

একটি parser আর একটি printer দুজনেই ভুল করে বিয়োগকে ডান-সংযোজী ধরে (একই ভুল ধারণা থেকে লেখা)। এলোমেলো গাছে round-trip পরীক্ষা parse(print(t)) = t কী দেখাবে?

  • প্রতিটি বিয়োগে parse error
  • বেশিরভাগ বিয়োগের গাছে অমিল
  • সব পরীক্ষা পাস, ভুলটি ধরা পড়ে না
  • Shrinking ভুলটিকে x - x - x-এ ছোট করে দেখাবে

Haat program let first = price(2, 520) + delivery(price(2, 520)); (লাইন ১০) parse করলে, AST-এর Binary + node আর বাঁয়ের Call node-এর অবস্থান কোথায়? (let column 1-এ, price column 13-এ, + column 27-এ)

  • Binary 10:13, Call 10:13
  • Binary 10:27, Call 10:13
  • Binary 10:27, Call 10:18
  • দুটিই 10:5, Let-এর নামের জায়গায়

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. AST রাখে অর্থ, parse tree রাখে লেখা: বন্ধনী, ; আর ব্যাকরণের মাঝের স্তর বাদ; bazar.haat-এ ৪৩০ বনাম ৭২টি node.
  2. Node নকশার প্রশ্ন: field, অবস্থান (বিন্দু না span, byte না অক্ষর), mutable না immutable, আর সমতায় অবস্থান থাকবে কি না; বিশ্লেষণের ফল side table-এ।
  3. সবচেয়ে কম বন্ধনীর চার নিয়ম: বাঁয়ে L(l) < p বা non-associative-এ সমান, ডানে L(r) ≤ p, unary-তে L < 7, callee-তে L < 8.
  4. Visitor নতুন কাজ যোগ সহজ করে, pattern matching (exhaustiveness-সহ) নতুন node যোগ নিরাপদ করে: expression problem-এর দুই দিক।
  5. Round trip-কে property বানান: এলোমেলো গাছ, অবস্থান-বাদ তুলনা, idempotence, shrinking; আর parser ও printer-এর জ্ঞান আলাদা রাখুন।

পরের পর্বে: Parser-এর error recovery আর ভালো diagnostic: panic mode, synchronising token, cascade এড়ানো, আর একবারে কয়েকটি ভুল, প্রতিটি সঠিক অবস্থানে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান