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

Pratt parsing — expression-এর precedence আর associativity

Pratt Parsing — Precedence and Associativity of Expressions

Taught in Bangla, this lesson builds Haat's full expression parser with Pratt's method: prefix and infix handler tables, binding powers from the reference, and one loop driven by min_bp. Steppers trace a long expression, and in-page Python (Pyodide) blocks print S-expressions matching the reference. It explains unary at 70 and call at 80, anonymous functions, the guard that rejects chained comparisons, expression error messages, and shows Pratt, precedence climbing and a layered grammar give the same trees.

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

  • Pratt parser-কে prefix আর infix handler-এর দুটি টেবিল হিসেবে দেখা, আর Haat-এর প্রতিটি token কোন টেবিলে কোন binding power নিয়ে বসে, তা বলতে পারা
  • একটি বড় expression-এর প্রতিটি expression(min_bp) ডাক হাতে trace করা, আর গাছটি কেন ঠিক সেই আকার নেয় তা ব্যাখ্যা করা
  • Unary operator, call-এর শিকল, বন্ধনী আর anonymous function Pratt loop-এ কীভাবে বসে, আর তাদের binding power বদলালে কী ভাঙে
  • Non-associative তুলনার পাহারা বাস্তবায়ন, তার সঠিকতার যুক্তি, আর expression-এর error message ও তার অবস্থান
  • Pratt, precedence climbing আর স্তরভাগ করা grammar যে একই ভাষা ও একই গাছ দেয়, তা যুক্তি আর differential fuzzing দিয়ে দেখানো

১ · পর্ব ২৬-এর loop থেকে Haat-এর পুরো expression

হাটের কথা ভাবুন। একজন খদ্দের দুই দোকানের মাঝখানে দাঁড়িয়ে; বাঁয়ের দোকানদার ডাকছেন, ডানের দোকানদারও ডাকছেন। খদ্দের যাবেন যাঁর ডাক বেশি জোরালো। দুজনের ডাক সমান হলে হাটের নিয়ম ঠিক করে: “আগে যিনি ডেকেছেন, তাঁর কাছে” (বাঁ দিক)। আর কিছু দোকানের ক্ষেত্রে হাট-কমিটির কড়া নিয়ম: একই সারির দুই দোকান একই খদ্দেরকে ডাকতে পারবে না, ডাকলে জরিমানা।

Expression a - b * c-এ b হলো সেই খদ্দের। বাঁয়ের - তাকে ৫০ জোরে টানে, ডানের * ৬০ জোরে, তাই b যায় গুণের কাছে: (- a (* b c)). এই “জোর” হলো binding power. সমান জোর মানে associativity-র প্রশ্ন, আর হাট-কমিটির নিষেধ হলো Haat-এর non-associative তুলনা: a < b < c লিখলে জরিমানা, অর্থাৎ syntax error.

পর্ব ২৬-এ (Expression আর evaluation order) এই loop-এর মূল রূপ বানিয়েছিলেন: সংখ্যা আর চারটি পাটিগণিতের operator, আর rbp = lbp + 1 নিয়ম কেন বাঁ-সংযোগ দেয় তার প্রমাণ। পর্ব ০১-এ একটি ছোট রূপ এক ঝলক দেখেছিলেন। আর তত্ত্বের দিক, অর্থাৎ binding power-এর টেবিল কেন একটি স্তরভাগ করা grammar-এর সমান কাজ করে, আছে গণনার তত্ত্ব কোর্সের পর্ব ৪২-এ (Grammar নকশা)। সেগুলো আবার শেখাব না। এই পর্বে সেই loop-কে একটি সত্যিকারের ভাষার পুরো expression-এর parser বানাব, যা পর্ব ৪৭-এর (Recursive descent parser) statement parser-এর ভেতরে বসবে। নতুন যা যা লাগবে:

  • সব ধরনের শুরু: সংখ্যা, string, true/false, নাম, বন্ধনী, unary - আর !, এমনকি একটি পুরো anonymous function fn(x: Int) -> Int { … }.
  • Postfix operator: function call f(a, b), যা একটি গাছের পরে বসে, আর শিকল বাঁধে: make_adder(5)(10).
  • Non-associativity: দুই স্তরের তুলনাই শিকল বাঁধতে পারে না (reference README-এর spec decision 10).
  • Error: ঠিক reference-এর মেসেজ আর অবস্থান, যেমন expected expression আর expected ')' after arguments.
সংজ্ঞা ৪৮.১ — Pratt parser-এর দুই টেবিল

একটি Pratt parser দুটি টেবিল দিয়ে সম্পূর্ণ বর্ণিত। (১) prefix টেবিল P: যে token দিয়ে একটি expression শুরু হতে পারে, তার জন্য একটি handler, যা কোনো বাঁ-পাশ ছাড়াই একটি গাছ বানায়। Pratt ১৯৭৩ সালে একে বলেছিলেন nud (null denotation, “বাঁয়ে কিছু নেই এমন অবস্থায় token-টির অর্থ”)। (২) infix টেবিল I: যে token একটি তৈরি গাছের পরে বসে তাকে বাড়াতে পারে, তার জন্য একটি left binding power lbp আর একটি handler, যা বাঁয়ের গাছ হাতে নিয়ে বড় গাছ বানায়। এর নাম led (left denotation).

Binary operator-এর handler ডান operand পড়ে একটি সীমা rbp দিয়ে। Postfix operator-এর (যেমন call) কোনো rbp নেই, কারণ তার ডানে কোনো operand নেই, আছে নিজের বন্ধনী।

Haat-এর সব token দুই টেবিলে এভাবে বসে। সংখ্যাগুলো reference README-এর “Precedence and binding powers” টেবিল আর parser.py-র INFIX, PREFIX_BP, CALL_BP থেকে হুবহু নেওয়া:

TokenPrefix ভূমিকা (nud)Infix/postfix ভূমিকা (led)lbp / rbp
INT STRING TRUE FALSE IDENTপাতা (leaf): Num, Str, Bool, Varনেই—
MINUS (-)Unary("-", …), operand পড়ে সীমা 70-এবিয়োগ, Binary50 / 51
BANG (!)Unary("!", …), সীমা 70নেই—
LPAREN (()বন্ধনী: ভেতরে সীমা 0, তারপর )call: Call(callee, args)80 / —
FNanonymous function: Lambdaনেই—
|| · &&নেইBinary, বাঁ-সংযোগী10/11 · 20/21
== != · < <= > >=নেইBinary, non-associative30/31 · 40/41
+ · * / %নেইBinary, বাঁ-সংযোগী50/51 · 60/61

খেয়াল করুন দুটি token দুই টেবিলেই আছে: - (শুরুতে negation, মাঝে বিয়োগ) আর ( (শুরুতে বন্ধনী, মাঝে call). একই চিহ্নের দুই অর্থ আলাদা করতে Pratt parser-এর কোনো বাড়তি কৌশল লাগে না: parser কোন টেবিল দেখবে, তা ঠিক করে তার অবস্থান, অর্থাৎ বাঁয়ে ইতিমধ্যে একটি গাছ আছে কি না। Recursive descent-এর ভাষায় এটি একটি ছোট lookahead সিদ্ধান্ত।

২ · Algorithm, ধাপে ধাপে — একটি বড় expression-এর প্রতিটি সিদ্ধান্ত

Algorithm ৪৮.১ — expression(min_bp)

ইনপুট: token-এর সারি আর একটি সীমা min_bp (শুরুতে 0). আউটপুট: একটি AST, অথবা অবস্থানসহ একটি syntax error.

(১) পরের token prefix টেবিলে না থাকলে error expected expression, সেই token-এর অবস্থানে। থাকলে token-টি খরচ হয় আর তার handler চলে (Haat-এ prefix()); ফল left. last_cmp = কিছু না।
(২) পরের token t দেখা হয়, খরচ না করে।
(৩) t যদি ( হয় আর 80 ≥ min_bp: argument-গুলো পড়ে left = Call(left, args); তারপর আবার ধাপ ২.
(৪) t infix টেবিলে না থাকলে, বা lbp(t) < min_bp হলে: left ফেরত যায়, ডাক শেষ।
(৫) t একটি তুলনা আর last_cmp = lbp(t) হলে: error comparison operators cannot be chained, t-এর অবস্থানে।
(৬) t খরচ হয়; right = expression(rbp(t)); left = Binary(t, left, right); last_cmp = lbp(t); তারপর আবার ধাপ ২.

Pratt-এর আসল ১৯৭৩ সালের প্রবন্ধে প্রতিটি token-এর সঙ্গে মূলত একটি সংখ্যা (বাঁ দিকের শক্তি) থাকত, আর ডান দিকের সীমা লেখা থাকত handler-এর কোডে; lbp আর rbp পাশাপাশি টেবিলে লেখার রীতি পরে জনপ্রিয় হয়েছে, আর Haat-এর reference সেটিই মানে। এবার -a * f(b, c) + d < e && !g-এ algorithm চালাই। প্রতিটি ধাপের সংখ্যা ল্যাবে instrument করা parser-এর সত্যিকারের trace থেকে নেওয়া, আর শেষ গাছ reference-এর haat.py ast-এর সঙ্গে মেলানো।

1def expression(min_bp):2    left = prefix()      # nud3    while True:4        '(' and 80 >= min_bp: call5        lbp < min_bp: return left6        chained compare: fail7        right = expression(rbp)8        left = Binary(op, left, right)
ডাকের স্তূপ আর সিদ্ধান্ত
ডাক
পরের token
সিদ্ধান্ত
  1. শুরু. expression(0), সংক্ষেপে E(0). প্রথম token -; বাঁয়ে কোনো গাছ নেই, তাই এটি prefix টেবিলের negation. তার operand পড়া হবে সীমা 70 দিয়ে, অর্থাৎ নতুন ডাক E(70).
  2. Unary কত দূর যায়. E(70) পড়ে a, তারপর দেখে *: lbp 60, যা 70-এর চেয়ে কম। এই ডাক গুণকে নিতে পারে না, তাই শুধু a ফেরত দেয়। ফল (- a): minus কেবল a-কে ধরেছে।
  3. গুণ. E(0)-তে ফিরে আবার *: 60 ≥ 0, তাই বাঁধা হয়। *-এর rbp 61, তাই ডান পাশের জন্য নতুন ডাক E(61).
  4. Call, postfix হিসেবে. E(61) prefix হিসেবে পড়ে নাম f. পরের token (, যা এখন infix টেবিলের call: 80 ≥ 61, তাই call হয়। প্রতিটি argument (b, c) পড়া হয় নতুন E(0) দিয়ে, কারণ বন্ধনীর ভেতরে সীমা নতুন করে শুরু।
  5. যোগ. E(61) দেখে + (50 < 61), তাই (call f b c) ফেরত। E(0) গুণের গাছ শেষ করে, তারপর + বাঁধে (50 ≥ 0) আর ডানে E(51) ডাকে। E(51) পড়ে d আর থামে <-এ (40 < 51).
  6. তুলনা. E(0) দেখে <: 40 ≥ 0. এটি তুলনা, তাই ধাপ ৫-এর পাহারা: last_cmp এখন 50 (শেষে বাঁধা হয়েছিল +), 40 নয়, তাই কোনো শিকল নেই। E(41) পড়ে e, থামে &&-এ (20 < 41). last_cmp হয় 40.
  7. যুক্তির AND আর !. &&: 20 ≥ 0, বাঁধা; ডানে E(21). E(21)-এর প্রথম token !, আবার prefix: তার operand E(70) পড়ে g, তারপর EOF. ফল (! g).
  8. শেষ. EOF কোনো টেবিলে নেই, তাই প্রতিটি খোলা ডাক ফেরত দেয়। মোট ১০টি expression ডাক হয়েছে (দুটি argument-এর জন্য)। গাছটি reference-এর python -B haat.py ast-এর আউটপুটের সঙ্গে হুবহু এক: (&& (< (+ (* (- a) (call f b c)) d) e) (! g)).

একই গাছ ছবিতে। প্রতিটি operator-এর পাশে তার lbp; যত বেশি শক্তি, গাছে তত নিচে। ছবির ডান পাশে লেখা কোন ডাক কোন অংশটি বানিয়েছে।

ছবি ৪৮.১ — -a * f(b, c) + d < e && !g-এর AST আর binding power

নীল: binary operator আর তার lbp; সবুজ: prefix operator (70); বেগুনি: call (80); ধূসর: পাতা।

AST of -a * f(b, c) + d < e && !g with binding powers && < ! + e g * d - call a f b c 20 · E(0) 40 · E(0) 70 50 60 80 · E(61) → (call f b c) নিচে = বেশি শক্ত বাঁধন
ছবি ৪৮.১ — মূলের && সবচেয়ে দুর্বল (20), তাই সবার শেষে বাঁধা হয়েছে, আর সবচেয়ে ওপরে বসেছে। Call (80) আর prefix - (70) সবচেয়ে নিচে। E(0) মানে expression(0) ডাক, যে মূলের তিনটি binary node বানিয়েছে; call বানিয়েছে E(61), অর্থাৎ গুণের ডান পাশের ডাক।

এই algorithm-এর সময় কত লাগে? একটি সহজ কিন্তু জরুরি দাবি।

উপপাদ্য ৪৮.২ — Pratt parser রৈখিক সময়ে চলে

n-টি token-এর ইনপুটে Algorithm ৪৮.১ মোট O(n) কাজ করে, আর থামে।

প্রমাণ. (১) প্রতিটি expression ডাক ধাপ ১-এ অন্তত একটি token খরচ করে, নয়তো error দিয়ে থামে; token কখনো ফেরত যায় না। তাই ডাকের সংখ্যা ≤ n. (২) loop-এর প্রতিটি পাক (ধাপ ২–৬) হয় একটি token খরচ করে (call-এর ( বা একটি operator), নয়তো ধাপ ৪-এ ফেরত দিয়ে loop শেষ করে। তাই সব ডাক মিলিয়ে পাকের সংখ্যা ≤ n + (ডাকের সংখ্যা) ≤ 2n. (৩) প্রতিটি পাকে কাজ ধ্রুবক (একটি টেবিল-খোঁজা আর একটি node বানানো)। (৪) তাই মোট কাজ O(n), আর token শেষ হলে (EOF কোনো টেবিলে নেই) সব ডাক ফেরত দেয়। ∎

খেয়াল করুন, প্রমাণে recursion-এর গভীরতা নিয়ে কিছু বলা হয়নি। - - - - a বা দশ হাজার স্তরের বন্ধনীতে recursion-এর গভীরতাও n পর্যন্ত যায়; CPython-এর নিজস্ব recursion সীমা (সাধারণত ১০০০) সেখানে আগে ফুরিয়ে যেতে পারে। এটি গতির নয়, stack-এর প্রশ্ন, আর বাস্তব compiler-গুলো এজন্য বন্ধনীর গভীরতার একটি সীমা রাখে বা loop-এ লেখে।

৩ · ব্রাউজারে Haat-এর পূর্ণ expression parser

এবার নিজে বানিয়ে চালান। নিচের তিনটি block মিলে Haat-এর সব expression-এর parser; চতুর্থটি অংশ ৭-এর পরীক্ষা। Block-গুলো একটি namespace ভাগ করে (পরেরটি আগে চালালে আগেরগুলো নিজে থেকে আগে চলে)। নামগুলো reference-এর মতো: Token(kind, text, line, col), UPPER_CASE token kind, AST-এর class আর field ast_nodes.py-র হুবহু, আর parser-এর method peek, advance, expect, fail, expression, prefix, function_rest. এগুলো পর্ব ৪৭-এর parser-এর নামের সঙ্গেও মেলে; সেখানে ExprStandIn নামে যে ধার-করা expression অংশ ছিল, এই পর্বের expression আর prefix তার জায়গায় বসানো যায়।

প্রথম block: AST-এর class, একটি ছোট regex-ভিত্তিক lexer (পুরো lexer পর্ব ৪৬-এর বিষয়, reference-এর lexer.py), আর token-এর কার্সর। Column গোনা হয় অক্ষর ধরে, byte ধরে নয় (decision 1), কারণ Python-এর string-এর index নিজেই code point গোনে।

import re; from dataclasses import make_dataclass
class HaatError(Exception): pass
Token = make_dataclass("Token", ["kind", "text", "line", "col"], frozen=True)
for spec in ("Num value|Str value|Bool value|Var name|Unary op operand|Binary op left right|Call "
             "callee args|Lambda params ret body|Param name type|Return value|ExprStmt expr|Block stmts"
             ).split("|"):                         # class and field names as in ast_nodes.py
    name, *fs = spec.split(); globals()[name] = make_dataclass(name, fs + ["line", "col"])
KIND = dict(zip("== != <= >= && || -> + - * / % < > ! = ( ) { } , ; :".split(), "EQ_EQ BANG_EQ LT_EQ "
    "GT_EQ AND_AND OR_OR ARROW PLUS MINUS STAR SLASH PERCENT LT GT BANG EQ LPAREN RPAREN LBRACE "
    "RBRACE COMMA SEMI COLON".split()))
KEYWORDS = "let var fn if else while return true false print".split()
LEX = re.compile(r'(?P<NL>\n)|(?P<SKIP>[ \t\r]+|//.*)|(?P<IDENT>[A-Za-z_][A-Za-z0-9_]*)|(?P<INT>[0-9]+)'
                 r'|(?P<STRING>"(?:\\["\\n]|[^"\\\n])*")|(?P<OP>[=!<>]=|&&|\|\||->|[-+*/%<>!=(){},;:])|.')
def tokenize(src):                                 # a short regex lexer; the full one is lexer.py
    toks, line, bol = [], 1, 0                     # bol = index where the current line begins
    for m in LEX.finditer(src):
        k, t, col = m.lastgroup, m.group(), m.start() - bol + 1
        if k == "NL": line, bol = line + 1, m.end()
        elif k is None: raise HaatError(f"{line}:{col}: error: unexpected character '{t}'")
        elif k != "SKIP": toks.append(Token(KIND[t] if k == "OP" else t.upper() if t in KEYWORDS else k, t, line, col))
    return toks + [Token("EOF", "", line, len(src) - bol + 1)]
class Parser:                                      # token cursor; the Pratt part is the next block
    def __init__(p, toks): p.toks, p.pos = toks, 0
    def peek(p): return p.toks[p.pos]
    def advance(p): t = p.peek(); p.pos += t.kind != "EOF"; return t
    def fail(p, msg, at=None):
        line, col = at or (p.peek().line, p.peek().col); raise HaatError(f"{line}:{col}: error: {msg}")
    def expect(p, kind, msg):                      # a missing ';' is reported just after the previous token
        if p.peek().kind == kind: return p.advance()
        q = p.toks[p.pos - 1]; p.fail(msg, (q.line, q.col + len(q.text)) if kind == "SEMI" else None)
    def items(p, item, msg):                       # [ item { "," item } ] ")"
        out = [] if p.peek().kind == "RPAREN" else [item()]
        while p.peek().kind == "COMMA": p.advance(); out.append(item())
        p.expect("RPAREN", msg); return out
print(*tokenize('f(b, c) <= -1 && "x\\n"'), sep="\n")

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

Token(kind='IDENT', text='f', line=1, col=1)
Token(kind='LPAREN', text='(', line=1, col=2)
Token(kind='IDENT', text='b', line=1, col=3)
Token(kind='COMMA', text=',', line=1, col=4)
Token(kind='IDENT', text='c', line=1, col=6)
Token(kind='RPAREN', text=')', line=1, col=7)
Token(kind='LT_EQ', text='<=', line=1, col=9)
Token(kind='MINUS', text='-', line=1, col=12)
Token(kind='INT', text='1', line=1, col=13)
Token(kind='AND_AND', text='&&', line=1, col=15)
Token(kind='STRING', text='"x\\n"', line=1, col=18)
Token(kind='EOF', text='', line=1, col=23)

-1 দুটি token, MINUS আর INT: Haat-এর integer literal-এ চিহ্ন থাকে না, minus সবসময় parser-এর কাজ। <= একটি token (দুই অক্ষরের মিল আগে)। String token তার উদ্ধৃতি আর escape হুবহু রাখে (decision 5); অর্থ বের করা parser-এর দায়িত্ব। Parser class-এ এখনো শুধু কার্সর: peek দেখে, advance খরচ করে কিন্তু EOF পেরোয় না, আর expect missing ;-কে আগের token-এর ঠিক পরে জানায় (decision 24). items কমা দিয়ে আলাদা তালিকা পড়ে, যা call-এর argument আর lambda-র parameter দুই জায়গাতেই লাগবে।

দ্বিতীয় block: এই পর্বের হৃদয়, reference-এর parser.py-র expression আর prefix-এর একই যুক্তি। INFIX টেবিলের প্রতিটি সারি (operator, lbp, rbp); NONASSOC_BP হলো সেই দুই স্তর, যেখানে শিকল নিষেধ।

INFIX = {"OR_OR": ("||", 10, 11), "AND_AND": ("&&", 20, 21),       # kind: (op, lbp, rbp)
         "EQ_EQ": ("==", 30, 31), "BANG_EQ": ("!=", 30, 31), "LT": ("<", 40, 41),
         "LT_EQ": ("<=", 40, 41), "GT": (">", 40, 41), "GT_EQ": (">=", 40, 41),
         "PLUS": ("+", 50, 51), "MINUS": ("-", 50, 51),
         "STAR": ("*", 60, 61), "SLASH": ("/", 60, 61), "PERCENT": ("%", 60, 61)}
NONASSOC_BP, PREFIX_BP, CALL_BP = {30, 40}, 70, 80
PREFIX_START = {"INT", "STRING", "TRUE", "FALSE", "IDENT", "LPAREN", "MINUS", "BANG", "FN"}
unescape = lambda s: re.sub(r'\\(.)', lambda m: "\n" if m[1] == "n" else m[1], s[1:-1])
class Parser(Parser):
    def expression(p, min_bp=0):                   # the loop: infix and postfix tokens ("led")
        left, last_cmp = p.prefix(), None
        while True:
            t = p.peek()
            if t.kind == "LPAREN" and CALL_BP >= min_bp:            # call: postfix, bp 80
                p.advance(); args, s = p.items(p.expression, "expected ')' after arguments"), left
                while isinstance(s, (Binary, Call)): s = s.left if isinstance(s, Binary) else s.callee
                left = Call(left, args, s.line, s.col); continue    # positioned at callee's start
            if t.kind not in INFIX or INFIX[t.kind][1] < min_bp: return left
            op, lbp, rbp = INFIX[t.kind]
            if lbp in NONASSOC_BP and last_cmp == lbp: p.fail("comparison operators cannot be chained")
            p.advance(); left = Binary(op, left, p.expression(rbp), t.line, t.col); last_cmp = lbp
    def prefix(p):                                 # tokens that may START an expression ("nud")
        t = p.peek(); k = t.kind
        if k not in PREFIX_START: p.fail("expected expression")
        p.advance()
        if k == "INT": return Num(int(t.text), t.line, t.col)
        if k == "STRING": return Str(unescape(t.text), t.line, t.col)
        if k in ("TRUE", "FALSE"): return Bool(k == "TRUE", t.line, t.col)
        if k == "IDENT": return Var(t.text, t.line, t.col)
        if k in ("MINUS", "BANG"): return Unary(t.text, p.expression(PREFIX_BP), t.line, t.col)
        if k == "FN": return Lambda(*p.function_rest("expected '(' after 'fn'"), t.line, t.col)  # next block
        e = p.expression(); p.expect("RPAREN", "expected ')' after expression"); return e
for src in ["-a * b", "a < b < c", "a + * b", "f(1, )", "(a + b"]:
    try: print(f"{src:10} -> {Parser(tokenize(src)).expression()}")
    except HaatError as err: print(f"{src:10} -> {err}")

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

-a * b     -> Binary(op='*', left=Unary(op='-', operand=Var(name='a', line=1, col=2), line=1, col=1), right=Var(name='b', line=1, col=6), line=1, col=4)
a < b < c  -> 1:7: error: comparison operators cannot be chained
a + * b    -> 1:5: error: expected expression
f(1, )     -> 1:6: error: expected expression
(a + b     -> 1:7: error: expected ')' after expression

প্রথম লাইন পড়ুন বাইরে থেকে ভেতরে: বাইরের node গুণ (column 4), তার বাঁয়ে Unary (column 1), যার ভেতরে a. অর্থাৎ (* (- a) b). প্রতিটি node-এর অবস্থান reference-এর নিয়মে: Binary তার operator-এ, Unary তার চিহ্নে। পরের চারটি লাইন চারটি ভিন্ন error, প্রতিটি reference-এর মেসেজ আর column-সহ: দ্বিতীয় <-এ শিকল (column 7); +-এর পরে * কোনো expression শুরু করতে পারে না (column 5); কমার পরে )-ও না (column 6); আর ইনপুট শেষ হয়ে গেছে অথচ বন্ধনী খোলা, তাই error EOF-এর অবস্থানে (column 7). লক্ষ করুন, prefix handler ভুল token খরচ করার আগেই থামে, তাই error সেই token-এর জায়গায় পড়ে।

কোডের তিনটি সিদ্ধান্ত reference থেকে সরাসরি নেওয়া। (১) Call loop-এর ভেতরে, infix-এর আগে দেখা হয়, binding power 80; এর অর্থ অংশ ৪-এ। (২) Call-এর অবস্থান callee-র শুরু, অর্থাৎ f(1)(2)-এর দুটি call-ই f-এর জায়গায় (reference-এর ast_nodes.start): একটি call-এর ভুল জানাতে গেলে ব্যবহারকারী আঙুল রাখেন function-এর নামে, বন্ধনীতে নয় (decision 24). (৩) last_cmp একটি local variable: প্রতিটি expression ডাকের নিজের। অংশ ৫-এ দেখবেন কেন এটুকুই যথেষ্ট।

৪ · Unary, call আর anonymous function — শক্তির সংখ্যা কেন এমন

৪.১ Prefix 70: গুণের চেয়ে শক্ত, call-এর চেয়ে দুর্বল

Prefix - আর ! তাদের operand পড়ে expression(70) দিয়ে। 70 সব binary operator-এর lbp-র (সর্বোচ্চ 60) চেয়ে বড়, তাই operand-টি কোনো binary operator গিলে ফেলতে পারে না। আবার 70 call-এর 80-র চেয়ে ছোট, তাই call operand-এর ভেতরেই থাকে। Reference দিয়ে চালানো কয়েকটি উদাহরণ (haat.py ast-এর সত্যিকারের আউটপুট):

HaatASTকেন
-2 * -3(* (- 2) (- 3))দুটি minus-ই কেবল নিজের সংখ্যা ধরে
- -a আর --aদুটিই (- (- a))-- Haat-এ কোনো token নয়; C-তে এটি decrement
!!ok(! (! ok))prefix নিজেকে ডাকতে পারে
-f(x)(- (call f x))80 ≥ 70: call আগে বাঁধে
!g(1) == h(== (! (call g 1)) h)30 < 70: তুলনা বাইরে
-(a + b) * c(* (- (+ a b)) c)বন্ধনী prefix টেবিলে, সীমা নতুন করে 0

দ্বিতীয় সারিটি ভাষাভেদে আলাদা: C17-এ --a একটি decrement, কারণ C-র lexer সবচেয়ে লম্বা মিল নিয়ে ---কে একটি token বানায়। Haat-এর lexer-এর তালিকায় -- নেই, তাই এখানে দুটি MINUS. একই লেখা, ভিন্ন lexer, ভিন্ন গাছ।

৪.২ Call একটি postfix operator, binding power 80

Call দেখতে এক অদ্ভুত operator: f-এর পরে একটি (, ভেতরে তালিকা, শেষে ). Pratt-এর দৃষ্টিতে ( একটি infix-জাতীয় token যার lbp 80, কিন্তু ডানে একটি operand-এর বদলে সে নিজের তালিকা পড়ে আর নিজের ) খোঁজে। Handler শেষে loop-এর শুরুতে ফেরে (continue), তাই পরের ( আবার call হয়: শিকল নিজে থেকেই বাঁ থেকে বাঁধে। Haat-এ function first-class (পর্ব ০৯ আর পর্ব ১৭), তাই call-এর ফল নিজেই একটি function হতে পারে, আর শিকল বাস্তব কাজে লাগে:

~/haat $ cat m1.haat
fn make_adder(n: Int) -> (Int) -> Int {
    return fn(x: Int) -> Int { return x + n; };
}
print(make_adder(5)(10));
print(-make_adder(1)(2) * 3);
~/haat $ python -B haat.py ast m1.haat | tail -2
  (print (call (call make_adder 5) 10))
  (print (* (- (call (call make_adder 1) 2)) 3)))
~/haat $ python -B haat.py run m1.haat
15
-9

(সত্যিকারের run, Haat reference, CPython 3.14.4.) দ্বিতীয় লাইনের গাছটি তিনটি শক্তির খেলা: call (80) সবচেয়ে ভেতরে, তারপর minus (70), তারপর গুণ (60). make_adder(1)(2) = 3, minus দিয়ে −3, তিন দিয়ে গুণ −9. নিচের stepper এই গাছটি ধাপে ধাপে বানায়।

  1. Token10টিEOF বাদে
  2. prefix -E(70)operand
  3. call80 ≥ 70দুবার
  4. গুণE(0)60
Token-এর সারিcolumn
-  make_adder  (  1  )  (  2  )  *  3
1  2           12 13 14 15 16 17 19 21
MINUS IDENT LPAREN INT RPAREN
LPAREN INT RPAREN STAR INT
E(0) → prefixnegation
E(0): প্রথম token -, বাঁয়ে কিছু নেই
      → Unary-এর operand = E(70)
E(70): prefix make_adder → Var (1:2)
E(70)-এর loopপ্রথম call
পরের token (: call, 80 ≥ 70
argument: E(0) → 1
left = (call make_adder 1)   অবস্থান 1:2
E(70)-এর loopদ্বিতীয় call
আবার (: call, 80 ≥ 70
left = (call (call make_adder 1) 2)
অবস্থান এখনো 1:2, callee-র শুরু
ফেরা আর গুণE(70) → E(0)
E(70): * lbp 60 < 70 → ফেরত
Unary: (- (call (call make_adder 1) 2))
E(0): * 60 ≥ 0 → বাঁধা, ডানে E(61) = 3
(* (- (call (call make_adder 1) 2)) 3)
যদি CALL_BP = 65 হতোbug
-f(x)          → (call (- f) x)
!is_vip(name)  → (call (! is_vip) name)
৩০০০টি এলোমেলো expression-এর ২৭৮টিতে
গাছ বদলে যায়
  1. Token. EOF বাদে ১০টি token. make_adder শুরু column 2-এ, প্রথম ( column 12-এ। - আর নামের মাঝে ফাঁক না থাকলেও এরা দুটি আলাদা token.
  2. Prefix. E(0)-এর প্রথম token -, তাই negation; operand পড়া হবে E(70)-এ। E(70)-এর prefix পড়ে নাম make_adder, একটি Var, অবস্থান 1:2.
  3. প্রথম call. E(70)-এর loop দেখে (. Call-এর শক্তি 80, যা সীমা 70-এর চেয়ে বেশি, তাই call এখানে, minus-এর ভেতরে হয়। Argument 1 পড়া হয় নতুন E(0) দিয়ে। Call node-এর অবস্থান callee-র শুরু, 1:2.
  4. শিকল. Call handler শেষে loop-এর শুরুতে ফেরে, আবার ( দেখে, আবার call. নতুন callee হলো আগের call-টি: (call (call make_adder 1) 2). কোনো বিশেষ নিয়ম লাগেনি; loop-ই বাঁ-সংযোগ দেয়।
  5. ফেরা. এবার *: 60 < 70, তাই E(70) পুরো call-শিকল ফেরত দেয়, minus তাকে মোড়ে। E(0)-তে * বাঁধা হয়, ডানে 3. Reference-এর ast ঠিক এই গাছ দেয়, আর চালালে ছাপে −9.
  6. ভুল সংখ্যা হলে. ধরুন কেউ call-কে prefix-এর চেয়ে দুর্বল রাখলেন (65). তখন -f(x)-এর অর্থ হয়ে যায় “-f-কে x দিয়ে ডাকা”, যা অর্থহীন। ল্যাবে এই bug বসিয়ে অংশ ৭-এর ৩০০০টি এলোমেলো expression চালালে ২৭৮টিতে গাছ বদলেছে।

৪.৩ Anonymous function: prefix টেবিলের সবচেয়ে বড় handler

fn দিয়ে শুরু হলে prefix handler একটি পুরো anonymous function পড়ে: parameter-এর তালিকা, ঐচ্ছিক ফেরত-type আর একটি block. Block-এর ভেতরে statement, যা পর্ব ৪৭-এর recursive descent-এর এলাকা; তাই এখানে Pratt আর recursive descent পরস্পরকে ডাকে: expression → function_rest → statement → আবার expression. Lambda তৈরি হওয়ার পর সে loop-এ ফেরে এক সাধারণ বাঁ-গাছ হিসেবে, তাই তার পরেই একটি call বসতে পারে: fn(n: Int) -> Int { return n * 2; }(21). Reference এটি চালিয়ে ছাপে 42 (সত্যিকারের run). আবার fn(x: Int) -> Int { return x; } + 1-ও parser-এর কাছে বৈধ: (+ (lambda …) 1). ভুলটি ধরে type checker: 1:7: error: type mismatch: expected Int, found (Int) -> Int. Parser গঠন দেখে, অর্থ দেখে না।

তৃতীয় block এই অংশটুকু যোগ করে, আর reference-এর ast_print.sexpr-এর মতো S-expression ছাপে। জায়গা বাঁচাতে এখানে lambda-র ভেতরে শুধু return statement, আর type শুধু চারটি মূল নাম; পূর্ণ statement পর্ব ৪৭-এ, function type (Int) -> Int reference-এর parse_type-এ।

class Parser(Parser):                              # fn(x: T, ...) -> R { return e; ... }
    def function_rest(p, lparen_message):         # the same name and argument as parser.py
        p.expect("LPAREN", lparen_message); ps = p.items(p.param, "expected ')' after parameters")
        ret = p.parse_type() if p.peek().kind == "ARROW" and p.advance() else "Unit"
        lb, body = p.expect("LBRACE", "expected '{' before function body"), []
        while p.peek().kind == "RETURN":          # only return statements here; all of them: 47
            r = p.advance(); body.append(Return(p.expression(), r.line, r.col)); p.expect("SEMI", "expected ';' after return")
        p.expect("RBRACE", "expected '}' at end of block"); return ps, ret, Block(body, lb.line, lb.col)
    def param(p):
        n = p.expect("IDENT", "expected parameter name")
        p.expect("COLON", f"expected ':' and a type after parameter '{n.text}'")
        return Param(n.text, p.parse_type(), n.line, n.col)
    def parse_type(p):                             # Int Bool Str Unit (function types: parser.py)
        t = p.expect("IDENT", "expected a type")
        return t.text if t.text in ("Int", "Bool", "Str", "Unit") else p.fail(f"unknown type '{t.text}'", (t.line, t.col))
def sexpr(n, ind=0):                               # the S-expression text of ast_print.sexpr
    e, pad = lambda m: sexpr(m, ind), "\n" + "  " * (ind + 1)
    match n:
        case Num(): return str(n.value)
        case Var(): return n.name
        case Str(): return '"' + n.value.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'
        case Bool(): return "true" if n.value else "false"
        case Unary(): return f"({n.op} {e(n.operand)})"
        case Binary(): return f"({n.op} {e(n.left)} {e(n.right)})"
        case Call(): return "(call " + " ".join(map(e, [n.callee, *n.args])) + ")"
        case Lambda():
            ps = " ".join(f"({q.name} {q.type})" for q in n.params)
            return f"(lambda ({ps}) {n.ret}{pad}{sexpr(n.body, ind + 1)})"
        case Block(): return "(block" + "".join(pad + sexpr(s, ind + 1) for s in n.stmts) + ")"
        case Return(): return f"(return {e(n.value)})"
        case ExprStmt(): return f"(expr {e(n.expr)})"
SRC = ('apply(fn(p: Int) -> Int { return p - p / 10; }, qty * unit) + delivery(total)(zone)\n'
       '    >= limit && !is_vip(name == "রহিম\\n");')
p = Parser(tokenize(SRC)); t = p.peek(); e = p.expression(); p.expect("SEMI", "expected ';' after expression")
print("(program\n  " + sexpr(ExprStmt(e, t.line, t.col), 1) + ")")

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

(program
  (expr (&& (>= (+ (call apply (lambda ((p Int)) Int
    (block
      (return (- p (/ p 10))))) (* qty unit)) (call (call delivery total) zone)) limit) (! (call is_vip (== name "রহিম\n"))))))

ল্যাবে একই দুই লাইন একটি ফাইলে রেখে reference চালিয়েছি: python -B haat.py ast demo.haat-এর আউটপুট এর সঙ্গে অক্ষরে অক্ষরে এক, ইন্ডেন্টেশন আর লাইন ভাঙাসহ। গাছে সব কিছু আছে: lambda একটি argument, তার শরীরে বাজারঘরের ১০% ছাড়, delivery(total)(zone) একটি call-শিকল, >= যোগের চেয়ে দুর্বল, ! একটি call-কে মোড়ে, আর বাংলা string-এর \n escape আবার লেখা হয়েছে। দ্বিতীয় লাইনের শুরুর ফাঁকা ঘর গাছে কোনো চিহ্ন রাখে না।

৫ · Non-associative তুলনা — পাহারাদার কোথায় দাঁড়ায়

C17, Java 21 আর JavaScript-এ a < b < c বৈধ আর মানে (a < b) < c: প্রথমে একটি true/false (C-তে 1/0), তারপর সেটিকে c-এর সঙ্গে তুলনা। Python 3.14-এ একই লেখার অর্থ a < b and b < c, b একবারই হিসাব হয়। Rust এটিকে syntax error করে (RFC 0558), আর rustc-এর মেসেজ প্রায় হুবহু Haat-এর মতো: “comparison operators cannot be chained”. Haat Rust-এর পথে: decision 10 বলে দুই তুলনা-স্তরই non-associative. বাস্তবায়নের প্রশ্ন: Pratt loop-এ এই নিষেধ কোথায় বসবে?

উত্তর: যে loop স্তরে প্রথম তুলনাটি বাঁধা হয়েছে, ঠিক সেখানে। a < b-এর ডান পাশ পড়ার ডাক E(41) দ্বিতীয় < দেখে শুধু থামে (40 < 41), কারণ তার কাছে এটি “আমার চেয়ে দুর্বল একটি operator”. দ্বিতীয় <-কে তুলবে বাইরের ডাক, আর সেখানেই last_cmp মনে রাখে যে এই স্তরে একটু আগে একটি 40-এর তুলনা বাঁধা হয়েছে।

1left, last_cmp = prefix(), None2op, lbp, rbp = INFIX[t.kind]3if lbp < min_bp: return left4if lbp in {30, 40} and last_cmp == lbp: fail5right = expression(rbp)6last_cmp = lbp
যে ডাক কাজ করছে
ইনপুট
ডাক
last_cmp
  1. প্রথম তুলনা. E(0) পড়ে a, দেখে <: lbp 40 ≥ 0. এটি তুলনা, তাই পাহারা জিজ্ঞেস করে: last_cmp কি 40? না, এখনো কিছুই বাঁধা হয়নি (None). বাঁধা চলবে।
  2. ভেতরের ডাক কিছু টের পায় না. ডান পাশ E(41) পড়ে b, তারপর দ্বিতীয় <: 40 < 41, তাই সে শুধু b ফেরত দেয়। তার নিজের last_cmp None, আর সে কোনো error দেয় না। শিকল ধরার দায়িত্ব তার নয়।
  3. মনে রাখা. E(0) গাছ বানায় (< a b), আর লিখে রাখে last_cmp = 40: “এই স্তরে একটি 40-এর তুলনা হয়ে গেছে।”
  4. পাহারা বাজে. E(0) আবার < দেখে: 40 ≥ 0, তুলনা, আর last_cmp = 40. শর্ত সত্য, তাই error, দ্বিতীয় operator-এর অবস্থানে: শুধু expression-এ 1:7, আর print(a < b < c);-এর ভেতরে reference বলে 1:13. Token খরচের আগেই থামে বলে অবস্থান ঠিক থাকে।
  5. ভিন্ন স্তর মেশানো চলে. a < b == c < d: E(0)-তে == (30) আসে last_cmp 40 থাকা অবস্থায়, অমিল, তাই বৈধ। তার ডান পাশ E(31)-এর নিজের last_cmp থাকে, সেখানে c < d প্রথম তুলনা। ফল (== (< a b) (< c d)), reference-এর সঙ্গে এক।
  6. বন্ধনী পাহারা পেরোয়. (a < b) < c-এ ভেতরের তুলনা বন্ধনীর আলাদা ডাকে হয়েছে; বাইরের E(0)-র last_cmp None. Parser গ্রহণ করে। কিন্তু a, b, c Int হলে type checker বলে 4:8: error: type mismatch: expected Int, found Bool (সত্যিকারের run, decision 11: < শুধু Int-এ)। লেখক বন্ধনী দিয়ে ইচ্ছা স্পষ্ট করেছেন, তাই এটি আর syntax-এর প্রশ্ন নয়।

এই ছোট পাহারা কি সত্যিই ঠিক সেই expression-গুলো বাতিল করে, যেগুলো spec বাতিল করতে বলে? Spec-এর ভাষা পর্ব ৪৫-এর EBNF: eqExpr = relExpr [ ( "==" | "!=" ) relExpr ], অর্থাৎ বন্ধনী ছাড়া একই স্তরে বড়জোর একটি তুলনা।

উপপাদ্য ৪৮.৩ — পাহারা ঠিক শিকলগুলোই ধরে

কোনো token-সারিতে বন্ধনী আর call-এর argument-এর বাইরে একই expression ডাকের loop-এ পরপর বাঁধা দুটি operator-কে বলি “একই স্তরের প্রতিবেশী”। দাবি: Algorithm ৪৮.১ ধাপ ৫-এ error দেয় ঠিক তখনই, যখন দুটি একই-স্তরের তুলনা (দুটিই 30 বা দুটিই 40) প্রতিবেশী, আর এটি ঠিক EBNF-এর [ … ] নিয়ম ভাঙার শর্ত।

প্রমাণের রূপরেখা. (১) একটি ডাক E(m)-এর loop-এ পরপর বাঁধা operator-গুলোর lbp কখনো বাড়ে না: op1-এর ডান পাশ E(lbp1+1) lbp1-এর চেয়ে বেশি শক্তির সব operator খেয়ে ফেলে, তাই loop-এ পরের যেটি আসে, তার lbp ≤ lbp1. (২) তাই কোনো তুলনা c1 বাঁধার পরে একই loop-এ পরের operator হয় একই স্তরের (lbp সমান), নয়তো দুর্বলতর। last_cmp ঠিক শেষ বাঁধা operator-এর lbp ধরে রাখে, তাই পাহারা বাজে ঠিক যখন পরপর দুটির lbp একই আর সেটি 30 বা 40. (৩) উল্টো দিক: দুটি একই-স্তরের তুলনা যদি একই loop-এ প্রতিবেশী না হয়, তবে একটি অন্যটির ডান-পাশের ডাকে বা বন্ধনীর ভেতরে আছে, যেখানে last_cmp আলাদা variable; তাই কোনো error নেই, আর EBNF-ও তখন তাদের আলাদা relExpr-এ পড়ে। (৪) স্তরভাগ করা grammar-এ একটি eqExpr-এর ভেতরে বন্ধনী ছাড়া দ্বিতীয় == আসা মানেই একই loop-এ প্রতিবেশী হওয়া। দুই দিক মিলিয়ে দাবি প্রমাণিত। ∎

ধাপ (১)-ই আসল কৌশল। এর একটি ফল: reference last_cmp হালনাগাদ করে প্রতিটি binary operator-এর পরে, কিন্তু শুধু তুলনার পরে করলেও ফল একই হতো। কারণ একটি তুলনার পরে একই loop-এ যা আসে, তার lbp ≤ 40; মাঝে একটি দুর্বলতর operator (যেমন &&, 20) এলে তার পরে আর কোনো 40 আসতেই পারে না, কারণ a < b && c < d-এর দ্বিতীয় < &&-এর ডান-পাশের ডাকে পড়ে। তবু প্রতিবার হালনাগাদ করলে নিয়মটি পড়তে সহজ: “ঠিক আগের operator-টিও যদি এই স্তরের তুলনা হয়”। অনুশীলন ৪-এ Python-ধাঁচের শিকল যোগ করতে চাইলে ঠিক এই জায়গাটিই বদলাতে হবে।

৬ · Expression-এর error — মেসেজ আর অবস্থান

Expression parser-এর error মাত্র কয়েক ধরনের, কিন্তু অবস্থান ঠিক রাখাই আসল কাজ। নিচের প্রতিটি সারি reference-এর সত্যিকারের আউটপুট (haat.py ast, প্রতিটি এক লাইনের ফাইল):

HaatReference বলেকোথায়, কেন
print(a +);1:10: error: expected expression)-এ: prefix টেবিলে নেই
print(* 3);1:7: error: expected expression* শুধু infix, শুরু করতে পারে না
print(f(1, ));1:12: error: expected expressionকমার পরে argument চাই
print(a b);1:9: error: expected ')' after print argumentloop b-এ থামে; print-এর ) নেই
print((a + b);1:14: error: expected ')' after print argumentভেতরের বন্ধনী print-এর ) খেয়ে নিয়েছে
print(a < b < c < d);1:13: error: comparison operators cannot be chainedপ্রথম পুনরাবৃত্তিতেই থামে
print(a == b < c == d);1:18: error: comparison operators cannot be chainedদ্বিতীয় ==-এ; মাঝের < ভেতরের ডাকে
let k = fn(x: int) -> Int { … };1:15: error: unknown type 'int' (আরও একটি)type-এর নাম বড় হাতের (decision 6)

পঞ্চম সারিটি শিক্ষণীয়। লেখক ভেতরের বন্ধনী বন্ধ করতে ভুলেছেন, কিন্তু parser-এর চোখে ভেতরের (-এর জোড়া হলো print-এর ); ভুল ধরা পড়ে এক token পরে, আর মেসেজ print-এর কথা বলে। কোনো parser মনের কথা পড়তে পারে না, সে শুধু প্রথম যেখানে আর কোনো বৈধ পথ নেই, সেটি জানায়। ভালো diagnostic দিতে কেউ কেউ দ্বিতীয় একটি নোট যোগ করে (“এখানে খোলা বন্ধনী”), যা পর্ব ৫০-এর (Parser-এর error recovery আর ভালো diagnostic message) বিষয়।

আরেকটি নিয়ম: missing ; ছাড়া প্রতিটি error অপ্রত্যাশিত token-এর জায়গায় (decision 24). তাই let total = price(2, 520 আর পরের লাইনে print(total); হলে reference বলে 2:1: error: expected ')' after arguments, পরের লাইনের শুরুতে। Missing ;-কে আলাদা করা হয় কারণ তার ক্ষেত্রে আগের লাইনের শেষটাই প্রায় সবসময় আসল জায়গা। আর একটি ফাইলে কয়েকটি ভুল থাকলে reference সবগুলো জানায়: তিন লাইনে print(1 < 2 < 3);, print(a +);, print(x == y == z); দিলে তিনটি error, 1:13, 2:10 আর 3:14, কারণ parser একটি statement-এর ভুলের পরে পরের নিরাপদ জায়গা থেকে আবার শুরু করে (panic mode, decision 25). এই পর্বের in-page parser প্রথম error-এই থামে।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় expression parsing নিয়ে এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Precedence আর associativity, একটি parser-এ কীভাবে? স্তরভাগ করা grammar (প্রতি স্তরে একটি function), অথবা binding power-এর টেবিল আর একটি loop (Pratt বা precedence climbing).
  • Unary minus কেন *-এর চেয়ে শক্ত? -a * b যেন (-a) * b হয়; Haat-এ prefix 70 > 60.
  • ডান-সংযোগী operator কীভাবে? rbp = lbp − 1 (বা rbp = lbp, loop-এর শর্ত অনুযায়ী); বাঁ-সংযোগী হলে rbp = lbp + 1.
  • Function call parser-এ কী? সবচেয়ে শক্ত postfix operator; loop-এ থাকে বলে f(1)(2) নিজে থেকেই শিকল।
  • Pratt parser-এর সময়? O(n); প্রতিটি token একবার খরচ হয়।

৭ · তিন পথ, এক গাছ — Pratt, precedence climbing আর স্তরভাগ করা grammar

Precedence প্রকাশ করার আরও দুটি পরিচিত পথ আছে। স্তরভাগ করা grammar-এ প্রতিটি precedence-স্তরের জন্য একটি নিয়ম, আর recursive descent-এ প্রতি নিয়মে একটি function; বাঁ-recursion এড়াতে { … } পুনরাবৃত্তি (তত্ত্ব গণনার তত্ত্বের পর্ব ৪২-এ, আর বাঁ-recursion কেন top-down parser-কে আটকে দেয় তা পর্ব ৩৮-এ)। Precedence climbing একটি ডাকের ভেতরে সংখ্যা তুলনা করে উঠতে থাকে; পদ্ধতিটি Martin Richards-এর BCPL compiler-এর কাজে দেখা যায়, Keith Clarke ১৯৮৬ সালের একটি প্রতিবেদনে (“The top-down parsing of expressions”) একে বর্ণনা করেন, আর “precedence climbing” নামটি সম্ভবত Theodore Norvell-এর একটি জনপ্রিয় লেখা থেকে ছড়িয়েছে। Non-associative operator সামলাতে Norvell-এর রূপে একটি উচ্চসীমা r থাকে: non-associative operator বাঁধার পরে r নেমে যায় তার স্তরের ঠিক নিচে।

Pratt (১৯৭৩) এই দুইয়ের আগের, আর তাকে precedence climbing-এর একটি সাধারণ রূপ হিসেবে দেখা যায়: prefix আর infix-এর টেবিলে যেকোনো handler বসানো যায়, শুধু binary operator নয়। এই তিনটি সত্যিই একই ভাষা আর একই গাছ দেয় কি না, যুক্তি দিয়ে দেখা যায়, আর চালিয়েও। চতুর্থ block দুটি নতুন parser বানায়, আগের Parser-এর কার্সর আর prefix ব্যবহার করে: Layered (পর্ব ৪৫-এর EBNF-এর প্রতিটি স্তরের একটি নিয়ম) আর Climbing (Norvell-ধাঁচের r-সহ)। তারপর একটি seed দেওয়া generator ৩০০০টি এলোমেলো expression বানায়, যার কিছু ইচ্ছা করে ভাঙা, আর তিনটি parser-এর ফল তুলনা করে: পুরো গাছের repr (প্রতিটি node-এর line:col-সহ), অথবা error-এর পুরো লেখা।

import random; random.seed(48)
LEVELS = [{"OR_OR"}, {"AND_AND"}, {"EQ_EQ", "BANG_EQ"}, {"LT", "LT_EQ", "GT", "GT_EQ"},
          {"PLUS", "MINUS"}, {"STAR", "SLASH", "PERCENT"}]        # one grammar rule per level
class Layered(Parser):                     # or = and {"||" and} ... eq = rel [("=="|"!=") rel] ...
    def expression(p, i=0):
        if i == len(LEVELS): return p.unary()
        left = p.expression(i + 1)
        while p.peek().kind in LEVELS[i]:
            t = p.advance(); left = Binary(INFIX[t.kind][0], left, p.expression(i + 1), t.line, t.col)
            if i in (2, 3) and p.peek().kind in LEVELS[i]: p.fail("comparison operators cannot be chained")
        return left
    def unary(p):                          # unary = ("-" | "!") unary | primary { "(" args ")" }
        if (t := p.peek()).kind in ("MINUS", "BANG"): p.advance(); return Unary(t.text, p.unary(), t.line, t.col)
        e = s = Parser.prefix(p)           # a literal, a name, ( expr ) or fn ...
        while isinstance(s, (Binary, Call)): s = s.left if isinstance(s, Binary) else s.callee
        while p.peek().kind == "LPAREN": p.advance(); e = Call(e, p.items(p.expression, "expected ')' after arguments"), s.line, s.col)
        return e
class Climbing(Layered):                   # precedence climbing (Clarke 1986; Norvell)
    def expression(p, min_prec=0):
        left, r = p.unary(), 99            # r: the highest level this call may still take
        while p.peek().kind in INFIX and INFIX[p.peek().kind][1] >= min_prec:
            t = p.advance(); op, prec, _ = INFIX[t.kind]
            if prec > r: p.fail("comparison operators cannot be chained", (t.line, t.col))
            left, r = Binary(op, left, p.expression(prec + 1), t.line, t.col), prec - (prec in NONASSOC_BP)
        return left
def gen(d):                                # random expression text; 3% lose a right operand
    if d == 0 or (k := random.random()) < 0.2: return random.choice(["a", "7", "true", '"x"', "f(a)", "fn(x: Int) { return x; }"])
    if k < 0.35: return random.choice("-!") + gen(d - 1)
    if k < 0.45: return "(" + gen(d - 1) + ")" + random.choice(["", "(1)", "(b, 2)"])
    return gen(d - 1) + f" {random.choice([v[0] for v in INFIX.values()])} " + (gen(d - 1) if random.random() > 0.03 else "")
def run(cls, src):                         # the tree (its repr shows every position) or the error
    try: p = cls(tokenize(src + ";")); e = p.expression(); p.expect("SEMI", "expected ';' after expression"); return repr(e)
    except HaatError as err: return str(err)
outs = [[run(c, s) for c in (Parser, Layered, Climbing)] for s in [gen(4) for _ in range(3000)]]
print(len(outs), "random expressions,", sum("error" not in o[0] for o in outs), "valid; all three agree on", sum(o[0] == o[1] == o[2] for o in outs))

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

3000 random expressions, 1968 valid; all three agree on 3000

৩০০০টির সবকটিতে তিনটি parser একই কথা বলে: বৈধ হলে একই গাছ, প্রতিটি node একই অবস্থানে; অবৈধ হলে একই error, একই line:col-এ। এলোমেলো ইনপুটের এক-তৃতীয়াংশের মতো অবৈধ, মূলত জোড়া তুলনা আর হারানো ডান operand থেকে, তাই error-এর পথও ভালোভাবে পরীক্ষা হয়েছে। এটিকে বলে differential testing, আর ব্যাকরণ মেনে এলোমেলো ইনপুট বানানোকে grammar-based fuzzing (পরীক্ষার কৌশলের বিস্তারিত Software Testing & QA কোর্সের পর্ব ৬০-এ)। লক্ষ করুন Climbing-এর r = prec - (prec in NONASSOC_BP): বাঁ-সংযোগী operator-এর পরে r = prec, তুলনার পরে r = prec − 1, আর পরে একই স্তরের operator এলে prec > r, তাই error.

কিন্তু “সব মিলেছে” মানে কি পরীক্ষাটি শক্ত? এটি যাচাই করার উপায় হলো ইচ্ছা করে bug বসানো (mutation), আর দেখা পরীক্ষা কতবার ধরে। ল্যাবে একই ৩০০০টি expression-এ পাঁচটি bug (সত্যিকারের run, CPython 3.14.4):

বসানো bugউদাহরণে প্রভাব৩০০০-এর কয়টিতে ধরা
Prefix-এর operand expression(0) দিয়ে-a + b → (- (+ a b))৮৮২
rbp = lbp (সব ডান-সংযোগী)10 - 4 - 3 → (- 10 (- 4 3))১১৫৯
Non-associative পাহারা নেইa < b < c গৃহীত৮৩২
Call-এর শক্তি 65 (prefix-এর নিচে)-f(x) → (call (- f) x)২৭৮
Climbing-এ সবসময় r = precতুলনা-শিকল গৃহীত৮৩২

প্রতিটি bug শত শত ইনপুটে ধরা পড়ে, তাই পরীক্ষাটি অন্ধ নয়। তবু তিনটি parser একই মানুষের লেখা, একই ভুল ধারণা তিনটিতেই থাকতে পারে। তাই ল্যাবে চূড়ান্ত তুলনা reference-এর সঙ্গে, যা আলাদাভাবে বানানো আর ৩২টি পরীক্ষায় উত্তীর্ণ (সত্যিকারের run):

~/haat/pratt $ python -B difftest.py
seed 4848: 5000 random expression statements, reference accepts 2762, identical output 5000
positions: 1099 valid expressions, every node at the same line:col in 1099
multi-line programs with Bangla comments/strings: 1000, identical 1000

৫০০০টি এলোমেলো expression statement-এ in-page parser (block ১–৩) আর reference-এর sexpr আউটপুট বা প্রথম error হুবহু এক; বৈধ ১০৯৯টিতে প্রতিটি node-এর অবস্থানও এক; আর বাংলা comment ও string-ওয়ালা ১০০০টি কয়েক লাইনের program-এও মিল। একটি সীমা স্পষ্ট বলে রাখি: in-page lexer lexical error-এ reference-এর সব মেসেজ দেয় না (যেমন অসমাপ্ত string-এ সে বলে unexpected character), আর lambda-র ভেতরে শুধু return চেনে; generator এগুলো বানায় না, তাই এই সংখ্যা শুধু expression-এর এলাকার কথা বলে।

উপপাদ্য ৪৮.৪ — তিন পথ সমতুল্য (রূপরেখা)

Haat-এর binding power-এর টেবিলে (প্রতিটি স্তরে lbpi = 10i, rbpi = 10i + 1, prefix 70, call 80) Algorithm ৪৮.১, Norvell-এর precedence climbing আর পর্ব ৪৫-এর স্তরভাগ করা EBNF একই token-সারি গ্রহণ করে আর একই গাছ দেয়।

প্রমাণের রূপরেখা. (১) Climbing আর Pratt: climbing-এর Exp(p) আর Pratt-এর expression(min_bp)-এর loop একই শর্তে (lbp ≥ সীমা) operator নেয় আর ডান পাশ একই সীমায় (lbp + 1) পড়ে; unary আর call দুটিতেই operand-এর ভেতরে থাকে। r-এর শর্ত আর last_cmp-এর শর্ত উপপাদ্য ৪৮.৩-এর ধাপ (১) অনুযায়ী একই মুহূর্তে বাজে। (২) Pratt আর স্তরভাগ grammar: স্তর i-এর নিয়ম (i = 1…6) ঠিক Pratt-এর সেই ডাকগুলোর কাজ করে, যাদের সীমা স্তর i-এর lbp থেকে স্তর i+1-এর lbp-র মধ্যে; দৈর্ঘ্যের ওপর induction-এ দেখানো যায় যে দুটি একই সময়ে একই token-এ থামে আর একই node বানায়। (৩) ফলে তিনটি একই partial function: token-সারি থেকে গাছ বা প্রথম error. ∎ ওপরের ৩০০০ আর ৫০০০ ইনপুটের পরীক্ষা এই দাবির প্রমাণ নয়, কিন্তু রূপরেখার কোনো ধাপে ফাঁক থাকলে খুব সম্ভবত তা ধরা পড়ত।

তাহলে কেন Pratt? সমান শক্তির হলেও প্রকৌশলে তিনটির স্বাদ আলাদা। স্তরভাগ grammar-এ ছয়টি স্তরের প্রতিটি সংখ্যা পড়তে ছয়টি function-ডাক লাগে, আর নতুন স্তর যোগ মানে নতুন function. Pratt-এ নতুন operator মানে টেবিলে একটি সারি (অনুশীলন ১), আর prefix-এর অদ্ভুত জিনিস (lambda, বন্ধনী, ভবিষ্যতে array literal) সরাসরি বসে। আর স্ট্যাক-ভিত্তিক shunting-yard (Dijkstra, ১৯৬১ সালের দিকে) recursion ছাড়াই একই কাজ করে, কিন্তু error message আর prefix-এর জটিল handler সেখানে বসানো তুলনায় কঠিন।

আরও গভীরে: বাস্তব compiler-এর source-এ এই loop প্রায়ই দেখা যায়, যদিও নাম আর খুঁটিনাটি version-ভেদে বদলায়। Go-র standard library-র go/parser-এ parseBinaryExpr একটি precedence সংখ্যা নিয়ে ঠিক এমন loop চালায়; Clang-এর parser-এ binary expression-এর ডান অংশ একটি operator-precedence loop-এ পড়া হয়। Pratt-এর ১৯৭৩ সালের প্রবন্ধ (“Top Down Operator Precedence”, প্রথম POPL সম্মেলন) বহু বছর তুলনামূলক অবহেলায় ছিল; ২০০৭ সালে Douglas Crockford-এর একটি প্রবন্ধ আর তাঁর JSLint, পরে Bob Nystrom-এর লেখা আর বই Crafting Interpreters একে আবার জনপ্রিয় করে। ২০১৬ সালে Andy Chu একটি লেখায় দেখান যে Pratt parsing আর precedence climbing আসলে একই algorithm-এর দুই রূপ, যা ওপরের উপপাদ্যের সঙ্গে মেলে।

৮ · AI-এর যুগে expression parser

“একটি calculator-এর parser লিখে দাও” — AI assistant-এর কাছে এটি সবচেয়ে পরিচিত অনুরোধগুলোর একটি, আর উত্তর প্রায় সবসময় সুন্দর দেখায়। কিন্তু ওপরের bug-তালিকার প্রতিটি ভুল AI-এর লেখা parser-এও দেখা যায়, কারণ ভুলগুলো ঠিক সেই জায়গায়, যেখানে ভাষাভেদে নিয়ম আলাদা। এই বিষয়ে বারবার দেখা ভুল আর ধরার উপায়:

AI-এর ভুলকীভাবে ধরবেন
Unary-কে দুর্বল রাখা: -a + b-কে -(a + b) পড়া-a + b, !a && b চালিয়ে গাছ দেখা; reference-এর haat.py ast-এর সঙ্গে মেলানো
Associativity উল্টো: 10 - 4 - 3-কে 9 দেওয়াএকই স্তরের তিনটি operator-এর শিকল; differential fuzzing
এক ভাষার নিয়ম চাপানো: Python-এর মতো a < b < c মানা, বা C-র মতো (a < b) < c পড়াSpec-এর decision 10; ঠিক সেই উদাহরণ reference-এ চালানো
Call-কে prefix-এর চেয়ে দুর্বল রাখা, বা f(1)(2) সমর্থন না করা-f(x) আর call-শিকলের পরীক্ষা
Error-এর অবস্থান ভুল: token খরচের পরে জানানোGolden file-এ line:col অক্ষরে অক্ষরে মেলানো
“এই কোড চালালে এই গাছ আসবে” বলে বানানো আউটপুটনিজে চালানো; AI-কে আউটপুট বানাতে নিষেধ করা

AI-কে পরীক্ষার প্রতিপক্ষ বানান: তাকে এমন ইনপুট খুঁজতে বলুন, যেখানে আপনার parser আর spec আলাদা কথা বলে।

আমি Haat নামের একটি শিক্ষণ-ভাষার Pratt parser লিখেছি (Python 3, শুধু standard library). Binding power: || 10/11, && 20/21, == != 30/31, < <= > >= 40/41, + - 50/51, * / % 60/61, prefix - ! 70, call f(a) postfix 80. দুই তুলনা-স্তরই non-associative: একই স্তরে দ্বিতীয় তুলনা এলে "comparison operators cannot be chained", দ্বিতীয় operator-এর জায়গায়। নিচে আমার কোড দিলাম। ১. এমন ২০টি expression দাও, যেগুলো unary, call-শিকল, বন্ধনী আর তুলনার কিনারা ছোঁয়; প্রতিটির প্রত্যাশিত S-expression বা error লেখো। ২. যেগুলো নিয়ে তুমি নিশ্চিত নও, "অনিশ্চিত" লেখো; আমি reference দিয়ে মেলাব। ৩. C, Python বা JavaScript-এর নিয়ম ধরে নেবে না; উপরের টেবিলে না থাকলে বলবে "টেবিলে নেই"। ৪. আমার কোড চালিয়ে আউটপুট বানিয়ে লিখবে না; শুধু ইনপুট আর তোমার প্রত্যাশা দেবে।

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

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

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

প্র ০১Pratt-এর ১৯৭৩ সালের পদ্ধতি এত সরল আর শক্তিশালী হলেও কয়েক দশক কেন তুলনামূলক অপরিচিত ছিল, আর পরে কেন আবার জনপ্রিয় হলো?

১৯৭০-এর দশকের compiler-জগতের কেন্দ্রে ছিল formal language-এর তত্ত্ব। Knuth-এর LR parsing (১৯৬৫), DeRemer-এর SLR আর LALR, আর Bell Labs-এর yacc একটি সুন্দর প্রতিশ্রুতি দিত: ব্যাকরণ লিখুন, যন্ত্র parser বানাবে, আর ব্যাকরণে দ্ব্যর্থতা থাকলে generator নিজেই conflict দেখাবে। এই পরিবেশে Pratt-এর প্রবন্ধ উল্টো কথা বলছিল: ব্যাকরণের বদলে প্রতিটি token-এর সঙ্গে ছোট ছোট handler আর সংখ্যা জুড়ে দিন। তত্ত্বের দিক থেকে এটি কম “ঘোষণামূলক”, আর কোনো generator-এর conflict-রিপোর্টের মতো নিরাপত্তা-জাল নেই। বইগুলো LR আর LL নিয়ে অধ্যায় লিখেছে; Pratt কয়েকটি Lisp-ঘরানার সিস্টেমে আর হাতে-লেখা parser-প্রেমীদের মধ্যে টিকে ছিল।

পরিবর্তন এসেছে দুই দিক থেকে। এক, ভাষাগুলোর expression অংশ বড় হয়েছে: JavaScript-এ prefix, postfix, ternary, arrow function, template literal; আর হাতে লেখা parser আবার মূলধারা হয়েছে (পর্ব ৪৫-এর আলোচনা)। হাতে লেখা parser-এ বিশ স্তরের precedence-এর জন্য বিশটি function লেখা ক্লান্তিকর, অথচ Pratt টেবিলে একটি সারি যোগ করেই কাজ সারে। দুই, কয়েকটি স্পষ্ট লেখা: ২০০৭ সালে Douglas Crockford-এর প্রবন্ধ (JSLint-এর ভেতরের parser নিয়ে), ২০১১ সালে Bob Nystrom-এর ব্লগ, আর পরে তাঁর বই Crafting Interpreters, যেখানে একটি ভাষার bytecode compiler Pratt দিয়েই expression পড়ে। রাস্ট-ভিত্তিক IDE-সরঞ্জামের লেখকেরাও Pratt-ধাঁচের loop নিয়ে লিখেছেন। একটি ভালো ব্যাখ্যা প্রায়ই একটি algorithm-এর ভাগ্য বদলে দেয়।

আরেকটি কারণ শিক্ষামূলক: Pratt-এর মূল প্রবন্ধের পরিভাষা (nud, led) আর লেখার ধরন প্রথমবার পড়লে দুর্বোধ্য। Haat-এর reference সেই পরিভাষা বাদ দিয়ে prefix, INFIX, lbp, rbp লেখে, আর সেটিই এখন প্রচলিত ধরন।

মূল উপলব্ধি: একটি algorithm-এর জনপ্রিয়তা শুধু তার শক্তির ওপর নয়, সে যুগের প্রকৌশলের অগ্রাধিকার আর ব্যাখ্যার মানের ওপরও নির্ভর করে। হাতে লেখা parser ফিরে আসায় Pratt-এর টেবিল-চালিত loop আবার স্বাভাবিক পছন্দ হয়েছে।

প্র ০২C, Python আর Rust তিনটি ভিন্ন উত্তর দেয় a < b < c-এর জন্য। Haat কেন Rust-এর পথ নিল, আর অন্য দুটির খরচ কী?

C-র উত্তর ব্যাকরণের দিক থেকে সবচেয়ে “সহজ”: তুলনাও আর দশটি binary operator-এর মতো বাঁ-সংযোগী, তাই (a < b) < c. সমস্যা হলো অর্থে। C17-এ a < b-এর মান int, 0 বা 1; তাই 1 < 5 < 3 হয় 1 < 3, অর্থাৎ সত্য, যদিও গণিতে মিথ্যা। প্রোগ্রামার যা লিখেছেন আর যা বোঝাতে চেয়েছেন, তার মধ্যে নিঃশব্দ ফারাক: সবচেয়ে বিপজ্জনক ধরনের bug. অনেক compiler এখানে warning দেয়, কিন্তু ভাষা অনুমতি দেয়। JavaScript-এও একই গাছ, সঙ্গে true/false থেকে সংখ্যায় স্বয়ংক্রিয় রূপান্তর।

Python উল্টো দিকে যায়: a < b < c মানে a < b and b < c, আর b একবারই হিসাব হয়। এটি গণিতের লেখার সঙ্গে মেলে, কিন্তু খরচ আছে। Parser-এর কাছে তুলনা আর সাধারণ binary operator নয়, বরং n-টি operand আর n−1টি operator-এর একটি বিশেষ node (CPython-এর ast-এ Compare). a == b < c-ও শিকল, যা অনেকের কাছে অপ্রত্যাশিত। আর b-কে একবার হিসাব করার নিয়ম মানে desugaring সরল নয়: b-এর পার্শ্বপ্রতিক্রিয়া থাকলে a < b and b < c লেখা ভুল অনুবাদ।

Rust ২০১৫-র আগে RFC 0558-এ সিদ্ধান্ত নেয়: কোনো অর্থই দেওয়া হবে না, বন্ধনী ছাড়া শিকল syntax error. এতে C-র নিঃশব্দ ভুল যায়, আর Python-এর বিশেষ node লাগে না; ভবিষ্যতে চাইলে Python-ধাঁচের অর্থ যোগ করার দরজাও খোলা থাকে, কারণ আজ কোনো বৈধ program সেই লেখা ব্যবহার করে না। Haat ঠিক এই যুক্তিতে চলে (decision 10), আর একটু বেশি কড়া: a == b != c-ও নিষেধ, কিন্তু ভিন্ন স্তর মেশানো চলে।

মূল উপলব্ধি: ভাষা নকশায় “অর্থ না দেওয়া” প্রায়ই সবচেয়ে নিরাপদ আর নমনীয় সিদ্ধান্ত। Parser-এ তার দাম মাত্র একটি variable আর একটি শর্ত।

প্র ০৩yacc বা Bison দিয়ে একটি অস্পষ্ট expression grammar লিখে %left, %right, %nonassoc ঘোষণা দিলে কী ঘটে? Pratt-এর binding power-এর সঙ্গে এর সম্পর্ক কী?

yacc-এর ঐতিহ্যে expression-এর grammar প্রায়ই ইচ্ছা করে অস্পষ্ট লেখা হয়: E → E + E ∣ E * E ∣ ( E ) ∣ num. এমন grammar-এর LALR টেবিলে shift/reduce conflict থাকে: স্তূপে E + E আর পরের token * হলে কি এখনই যোগ reduce করব, না * shift করব? Precedence ঘোষণা এই প্রশ্নের উত্তর দেয়। পরের লাইনে ঘোষিত operator বেশি শক্ত; তাই * যোগের পরের লাইনে থাকলে shift জেতে। একই operator-এ %left হলে reduce (বাঁ-সংযোগ), %right হলে shift, আর %nonassoc হলে সেই টেবিল-ঘর error হয়ে যায়: ঠিক Haat-এর তুলনার মতো।

অর্থাৎ yacc-এর ঘোষণা আর Pratt-এর সংখ্যা একই তথ্য: স্তর আর associativity. পার্থক্য কোথায় প্রয়োগ হয়। LR parser সিদ্ধান্ত নেয় স্তূপের ওপরের operator আর পরের token-এর তুলনা করে, টেবিল বানানোর সময়েই; Pratt নেয় চলার সময়, “পরের token-এর lbp কি আমার সীমার সমান বা বেশি” প্রশ্ন করে। Pratt-এর min_bp হলো স্তূপের ওপরের operator-এর rbp, অর্থাৎ recursion-এর call stack-ই LR-এর স্তূপের কাজ করছে। তাই অনেকে বলেন, Pratt parser একটি হাতে লেখা operator-precedence parser, যার স্তূপ লুকিয়ে আছে recursion-এ।

Unary minus-এ দুই জগতের মিল আরও পরিষ্কার। yacc-এ একই - token দুই অর্থে, তাই %prec UMINUS দিয়ে নিয়মটিকে আলাদা শক্তি দিতে হয়; Pratt-এ prefix টেবিল আলাদা, তাই 70 আর 50 আপনাআপনি আলাদা। LR তত্ত্ব আর generator-এর খুঁটিনাটি গণনার তত্ত্বের পর্ব ৩৯ আর পর্ব ৪০-এ আছে।

মূল উপলব্ধি: precedence আর associativity একটি ছোট টেবিল; সেই টেবিল LR-এর conflict মেটাতে, স্তরভাগ grammar লিখতে, বা Pratt-এর loop চালাতে, সব জায়গায় একই কাজ করে। পদ্ধতি বদলায়, তথ্য একই থাকে।

প্র ০৪Unary minus আর ঘাত (power) একসঙ্গে থাকলে ভাষাগুলো ভিন্ন সিদ্ধান্ত নেয়। Python-এ -2**2 কত, আর Haat-এ ঘাত যোগ করলে কোন সংখ্যা বেছে নেবেন?

Python 3.14-এ -2**2-এর মান −4: ** unary minus-এর চেয়ে শক্ত, তাই -(2**2). এটি গণিতের প্রচলিত লেখার সঙ্গে মেলে, যেখানে −x² মানে −(x²)। কিন্তু সব জায়গা এমন নয়; কিছু স্প্রেডশিট সফটওয়্যারে একই ধরনের সূত্র (=-2^2) 4 দেয় বলে পরিচিত, কারণ সেখানে negation সবচেয়ে আগে বাঁধে। একই প্রতীক, দুই ঐতিহ্য, আর ব্যবহারকারীর কাছে নিঃশব্দ ভিন্নতা। C আর Java-তে ঘাতের কোনো operator নেই, একটি function আছে, তাই প্রশ্নটিই ওঠে না: বন্ধনী লিখতে বাধ্য করাও একটি নকশা।

Pratt-এ এই সিদ্ধান্ত মাত্র দুটি সংখ্যা। Haat-এর বর্ধিত রূপে ^ যোগ করলে (অনুশীলন ১) lbp 75 নিলে, যা prefix-এর 70-এর চেয়ে বেশি, -2 ^ 2 হয় (- (^ 2 2)), Python-এর মতো। আর rbp 74 (lbp − 1) নিলে ঘাত ডান-সংযোগী: 2 ^ 3 ^ 2 = (^ 2 (^ 3 2)), যা গণিতের প্রথা। ডান operand-এ একটি minus এলেও কাজ করে: 2 ^ -1-এ ডান পাশের ডাক E(74) prefix টেবিলে - পায়, তাই (^ 2 (- 1)). এই প্রতিটি গাছ ল্যাবে extension চালিয়ে পাওয়া।

উল্টো সিদ্ধান্ত, lbp 65 (prefix-এর নিচে), দিলে -2 ^ 2 হতো (^ (- 2) 2) = 4. কোনটি “ঠিক”, তা গণিত ঠিক করে না, ঠিক করে ভাষার ব্যবহারকারী কী আশা করেন। বাজারঘরের হিসাবরক্ষক স্প্রেডশিটে অভ্যস্ত হলে এক আশা, প্রোগ্রামার হলে আরেক। নিরাপদ পথ হতে পারে Rust-এর তুলনার মতো: -a ^ b-এ বন্ধনী বাধ্যতামূলক করা।

মূল উপলব্ধি: precedence-এর সংখ্যা ভাষার নকশার সিদ্ধান্ত, parser-এর নয়। Pratt সেই সিদ্ধান্তকে একটি দৃশ্যমান টেবিলে আনে, তাই আলোচনা আর পরীক্ষা সহজ হয়।

প্র ০৫C-তে *p++ মানে *(p++), আর Haat-এ -f(x) মানে -(f(x)). Postfix কেন প্রায় সব ভাষায় prefix-এর চেয়ে শক্ত?

C17-এর ব্যাকরণে postfix-expression (array index a[i], call f(x), member s.x, p->x, আর postfix ++) unary-expression-এর ভেতরে থাকে। ফলে *p++-এ আগে p++, তারপর dereference: পুরোনো ঠিকানার মান পড়া হয়, আর p এক ঘর এগোয়। একইভাবে -s.x মানে -(s.x), আর !f(x) মানে !(f(x)). Java 21 আর JavaScript-এও member access আর call unary-র চেয়ে শক্ত। কারণটি ব্যবহারিক: postfix operator সাধারণত একটি মান “খুঁজে আনে” (কোন function-এর ফল, কোন field, কোন ঘর), আর prefix সেই আনা মানের ওপর কাজ করে। উল্টো হলে -s.x হতো “-s-এর x নামের field”, যা প্রায় কখনো অর্থপূর্ণ নয়।

Haat-এ এটি দুটি সংখ্যার সম্পর্ক: CALL_BP 80 > PREFIX_BP 70. অংশ ৭-এর পরীক্ষায় দেখা গেছে, call 65-এ নামালে ৩০০০-এর ২৭৮টি ইনপুটে গাছ বদলায়: -f(x) হয় (call (- f) x), অর্থাৎ “একটি function-এর ঋণাত্মক রূপকে ডাকা”। Haat-এর type checker তখন ভুলটি ধরত (- শুধু Int-এ, decision 11), কিন্তু মেসেজ হতো বিভ্রান্তিকর, কারণ ব্যবহারকারী যা লিখেছেন তা ঠিকই ছিল।

তবু ব্যতিক্রম আছে, আর তা আকর্ষণীয়। JavaScript-এ new একটি prefix keyword, আর new Foo().bar-এর গাছ ঠিক করতে spec-এ আলাদা নিয়ম আছে; C++-এ sizeof, cast আর template-এর কোণাগুলো parser লেখকদের পরিচিত মাথাব্যথা। Pratt-এ এসব জিনিস নিজস্ব prefix handler পায়, যে ঠিক করে তার operand কত দূর যাবে। Haat-এর lambda-ও এমন একটি handler: তার “operand” একটি পুরো block, আর শেষে সে loop-এ ফিরে একটি সাধারণ মান হয়ে যায়, যাকে সঙ্গে সঙ্গে ডাকা যায়।

মূল উপলব্ধি: “আগে মান খুঁজে আনা, তারপর তার ওপর কাজ” — postfix-কে prefix-এর চেয়ে শক্ত রাখার পেছনে এই স্বাভাবিক পড়ার ক্রম। Binding power-এর টেবিলে এটি একটি অসমতা, যার ভাঙন differential testing সহজেই ধরে।

অনুশীলন

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

  1. Parser বাড়ান (বাস্তবায়ন, Haat-এর বর্ধিত রূপ): বাজারঘরের সুদের হিসাবের জন্য ঘাতের operator ^ যোগ করুন। চাওয়া: ডান-সংযোগী (2 ^ 3 ^ 2 = 2 ^ (3 ^ 2)), গুণের চেয়ে শক্ত, আর -2 ^ 2 মানে -(2 ^ 2). (ক) lbp আর rbp কত নেবেন, কেন? (খ) অংশ ৩-এর কোডে কোথায় কী বদলাতে হবে? (গ) 2 ^ -1, a * b ^ c আর f(x) ^ 2-এর গাছ কী হবে?

    (ক) গুণের চেয়ে শক্ত হতে হলে lbp > 60; -2 ^ 2-এ minus-এর operand ডাক E(70)-কে ^ নিতে হবে, তাই lbp ≥ 70; সমান নিলে চলে, তবে স্পষ্টতার জন্য lbp = 75 আর call-এর 80-র নিচে। ডান-সংযোগের জন্য rbp = lbp − 1 = 74: তখন 2 ^ 3 ^ 2-এ ডান পাশের ডাক E(74) দ্বিতীয় ^-কে (75 ≥ 74) নিজেই নেয়।

    (খ) তিনটি জায়গা: lexer-এ নতুন token, আর টেবিলে একটি সারি। Parser-এর loop-এ কোনো বদল লাগে না:

    KIND["^"] = "CARET"                        # lexer: a new one-char token
    LEX = re.compile(LEX.pattern.replace("[-+*/%<>!=(){},;:]", "[-+*/%<>!=(){},;:^]"))
    INFIX["CARET"] = ("^", 75, 74)             # lbp 75 > PREFIX_BP 70; rbp = lbp - 1

    (গ) ল্যাবে চালানো ফল: 2 ^ 3 ^ 2 → (^ 2 (^ 3 2)); -2 ^ 2 → (- (^ 2 2)); 2 ^ -1 → (^ 2 (- 1)) (ডান পাশের ডাক prefix টেবিলে - পায়); a * b ^ c → (* a (^ b c)); f(x) ^ 2 → (^ (call f x) 2), কারণ call 80 > 75. পুরো কাজটি একটি টেবিলের সারি, আর এটিই Pratt-এর মূল সুবিধা। (এটি spec v1-এর অংশ নয়; reference এই operator জানে না।) পূর্ণ করতে হলে type নিয়ম (Int, Int → Int), ঋণাত্মক ঘাতের অর্থ আর overflow-এর wrap-ও spec-এ লিখতে হবে।

  2. ভুল খুঁজুন আর প্রমাণ করুন: একজন শিক্ষার্থী prefix handler-এ লিখলেন Unary(t.text, p.expression(0), …), অর্থাৎ সীমা 70-এর বদলে 0. (ক) -a * b, -a + b, !a && b আর -f(x)-এর গাছ কী হবে? কোনটিতে মান বদলায়? (খ) প্রমাণ করুন: সঠিক কোডে (সীমা 70) একটি Unary node-এর operand কখনো বন্ধনী ছাড়া একটি Binary node হয় না।

    (ক) ল্যাবে চালানো ফল: -a * b → (- (* a b)); -a + b → (- (+ a b)); !a && b → (! (&& a b)); -f(x) → (- (call f x)), যা ঠিকই আছে। প্রথমটিতে গাছ ভুল হলেও মান একই থাকে, কারণ ৬৪-বিট wrap-সহ −(a·b) = (−a)·b; তাই শুধু মান দেখে পরীক্ষা করলে এই bug লুকিয়ে যায়। দ্বিতীয়টিতে মান বদলায় (a = 1, b = 2: সঠিক 1, bug-এ −3), তৃতীয়টিতে যুক্তির অর্থ বদলায়। অংশ ৭-এর ৩০০০টি ইনপুটের ৮৮২টিতে এই bug ধরা পড়েছে। শিক্ষা: গাছ তুলনা করুন, শুধু মান নয়।

    (খ) প্রমাণ. (১) Unary node তৈরি হয় শুধু prefix handler-এ, আর তার operand হলো expression(70)-এর ফল। (২) expression(70)-এর loop-এ একটি binary operator বাঁধা হয় শুধু যদি তার lbp ≥ 70; কিন্তু Haat-এর সব binary operator-এর lbp ≤ 60, তাই এই loop কোনো Binary বানায় না। (৩) Loop-এর বাকি পথ শুধু call (Call node) বানায়, আর prefix অংশ বানায় একটি পাতা, একটি Unary, একটি Lambda, অথবা বন্ধনীর ভেতরের যেকোনো গাছ। (৪) তাই operand-এর মূল Binary হতে পারে শুধু বন্ধনী থেকে। ∎

  3. আউটপুট অনুমান করুন (trace): !ok == done || n % 3 - 1 > 0 && f(n)(2)-এর জন্য (ক) S-expression লিখুন; (খ) কয়টি expression(min_bp) ডাক হবে, আর কোন কোন সীমা নিয়ে; (গ) print(n < 1 >= 0);-এ reference কী বলবে, কোন column-এ; (ঘ) n < 1 == ok >= 0 কি বৈধ?

    (ক) সত্যিকারের haat.py ast: (|| (== (! ok) done) (&& (> (- (% n 3) 1) 0) (call (call f n) 2))). মূলে ||, কারণ সবচেয়ে দুর্বল (10). ! শুধু ok ধরে (30 < 70).

    (খ) instrument করা parser-এর trace অনুযায়ী মোট ১০টি ডাক: E(0) শুরুতে; E(70) !-এর operand; E(31) ==-এর ডান পাশ (done); E(11) ||-এর ডান পাশ; তার ভেতরে E(61) (3), E(51) (1), E(41) (0), E(21) (&&-এর ডান পাশ, f(n)(2)); আর দুটি argument-এর জন্য দুটি E(0). খেয়াল করুন E(11) একাই %, -, > আর && চারটি operator বাঁধে, কারণ সবার lbp ≥ 11.

    (গ) 1:13: error: comparison operators cannot be chained: < আর >= একই স্তরের (40), আর >= শুরু column 13-এ। (ঘ) হ্যাঁ: (== (< n 1) (>= ok 0)), কারণ মাঝে == ভিন্ন স্তরের। Parser গ্রহণ করে; ok একটি Bool হলে type checker ok >= 0-এ আপত্তি করবে, কারণ >= শুধু Int-এ (decision 11).

  4. একটি feature নকশা করুন: বাজারঘরের দল চায় Python-এর মতো low <= qty <= high লেখা যাক, অর্থ “qty দুই সীমার মধ্যে”। (ক) AST-এ কী রাখবেন: (&& (<= low qty) (<= qty high)), নাকি নতুন node? (খ) Pratt loop-এ কোথায় বদল? (গ) কোন পুরোনো বৈধ program-এর অর্থ বদলাবে কি? (ঘ) কোন প্রশ্নগুলো spec-এ লিখতে হবে?

    (ক) সরাসরি &&-তে ভেঙে দিলে qty দুবার হিসাব হয়। qty যদি একটি call হয়, যেমন stock(), তবে তার পার্শ্বপ্রতিক্রিয়া দুবার ঘটে (decision 12-এর বাঁ-থেকে-ডান নিয়ম থাকলেও)। নিরাপদ নকশা: নতুন node Compare(first, [(op, operand), …]), যেমন CPython-এর ast.Compare; interpreter মাঝের মান একবার হিসাব করে মনে রাখে আর প্রথম মিথ্যাতেই থামে।

    (খ) ধাপ ৫-এর পাহারার জায়গায় নতুন শাখা: last_cmp একই স্তরের হলে error না দিয়ে বর্তমান Compare-এ আরেকটি (op, operand) যোগ। ডান operand আগের মতোই expression(rbp). তবে ঠিক করতে হবে == আর < মেশানো শিকল (a < b == c) চলবে কি না; Python চালায়, কিন্তু Haat-এ আজ এটি (== (< a b) c).

    (গ) ঠিক এখানেই সাবধান: a < b == c < d আজ বৈধ আর মানে (a < b) == (c < d). দুই স্তর মিলিয়ে একটি শিকল বানালে এর অর্থ বদলে যাবে, যা পুরোনো program ভাঙে। একই স্তরের শিকলে (<= … <=) সমস্যা নেই, কারণ আজ তা সবসময় error, তাই কোনো বৈধ program সেটি ব্যবহার করে না। তাই নিরাপদ নিয়ম: শুধু স্তর ৪-এর ভেতরে শিকল।

    (ঘ) Spec-এ: কোন operator-গুলো শিকল বাঁধে; মাঝের operand একবার হিসাব হয় কি না; short-circuit কখন; type নিয়ম (প্রতিটি জোড়া Int, Int; ফল Bool); error-এর অবস্থান। আর reference README-এর decision 10 বদলাতে হবে, golden file-গুলোও।

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

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

ক্রমHaat-এর expression(min_bp) একটি পাকে যে ক্রমে কাজ করে, সেভাবে সাজান (▲▼ চেপে সরান)

  1. Prefix handler দিয়ে প্রথম গাছ (left) বানানো
  2. পরের token দেখা, খরচ না করে
  3. ( হলে call বানানো আর আবার দেখা
  4. Infix নয় বা lbp < min_bp হলে left ফেরত
  5. একই স্তরের তুলনা পরপর হলে error
  6. Operator খরচ করে ডান পাশ expression(rbp) দিয়ে পড়া

Haat-এর binding power-এ (prefix 70, call 80, * 60) -f(x) * y-এর AST কোনটি?

  • (- (* (call f x) y))
  • (* (call (- f) x) y)
  • (* (- (call f x)) y)
  • (- (call f (* x y)))

Haat reference print(a == b != c); পেলে কী বলে?

  • (!= (== a b) c), বাঁ থেকে
  • 1:14: error: comparison operators cannot be chained
  • a == b আর b != c, দুটিই সত্য হতে হবে
  • Type checker-এর error: Bool আর Int-এর তুলনা

Pratt parser-এ একটি binary operator-কে ডান-সংযোগী করতে (loop-এর শর্ত lbp >= min_bp) কী করতে হয়?

  • rbp = lbp + 1
  • lbp-কে সবার চেয়ে বড় করা
  • Operator-টিকে postfix টেবিলে রাখা
  • rbp = lbp − 1, যাতে ডান পাশের ডাক একই operator নিতে পারে

Haat-এ print((a + b); লিখলে reference কোন error দেয়?

  • 1:14: error: expected ')' after print argument
  • 1:14: error: expected ')' after expression
  • 1:12: error: expected expression
  • কোনো error নেই, a + b ছাপে

n-টি token-এর একটি expression-এ Pratt parser-এর মোট কাজ কত, আর কেন?

  • O(n²), কারণ প্রতিটি operator সব স্তর পরীক্ষা করে
  • O(n), কারণ প্রতিটি token একবারই খরচ হয়
  • সবচেয়ে খারাপ ক্ষেত্রে exponential, backtracking-এর জন্য
  • O(1), কারণ টেবিল ধ্রুবক আকারের

তিনটি expression parser (Pratt, precedence climbing, স্তরভাগ grammar) হাজার হাজার এলোমেলো ইনপুটে একই ফল দিল। এই differential test-এর সবচেয়ে বড় সীমা কোনটি?

  • ফল প্রতিবার আলাদা হয়, তাই পুনরুৎপাদন করা যায় না
  • এটি শুধু বৈধ ইনপুট পরীক্ষা করতে পারে
  • তিনটিতে একই ভুল ধারণা থাকলে অমিল দেখা যাবে না
  • এলোমেলো ইনপুট কখনো precedence-এর bug ধরতে পারে না

Haat-এ fn(x: Int) -> Int { return x; } + 1 লিখলে কী ঘটে?

  • Parser-এর error: expected expression
  • Parser-এর error: lambda-র পরে operator চলে না
  • Program চলে আর একটি নতুন function ফেরত দেয়
  • Parser গ্রহণ করে; type checker type mismatch দেয়

শব্দকোষ

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

মনে রাখুন

  1. Pratt parser = prefix টেবিল (nud) + infix/postfix টেবিল (led) + একটি loop; একই চিহ্ন (-, () অবস্থান অনুযায়ী দুই টেবিলে দুই অর্থ পায়।
  2. Haat-এর সংখ্যা: || 10, && 20, == != 30, তুলনা 40, + - 50, * / % 60, prefix 70, call 80; rbp = lbp + 1 মানে বাঁ-সংযোগ।
  3. Call একটি postfix operator; loop-এ থাকে বলে f(1)(2) নিজে থেকেই শিকল, আর call-এর অবস্থান callee-র শুরু।
  4. Non-associative তুলনা = প্রতিটি ডাকের নিজের last_cmp; error দ্বিতীয় operator-এর জায়গায়, token খরচের আগে।
  5. Pratt, precedence climbing আর স্তরভাগ grammar একই গাছ দেয়; এটি যুক্তি আর differential fuzzing দুই দিক থেকে দেখা যায়, আর পরীক্ষার শক্তি মাপতে bug বসিয়ে দেখুন।

পরের পর্বে: এই পর্বের গাছগুলো কীভাবে সাজানো থাকে: AST-এর node-এর নকশা, visitor আর pattern matching, আর ন্যূনতম বন্ধনী দিয়ে গাছকে আবার Haat-এর লেখায় ফেরানো pretty printer, round trip পরীক্ষাসহ।

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

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