Lexer + Pratt Parser

কেন এই প্রজেক্ট

Grammars-and-ambiguity লেসনে দেখেছি 1 + 2 * 3-এর grammar ভুল লিখলে ambiguity ঢুকে পড়ে, আর recursive-descent-এ precedence-র প্রতি স্তরে আলাদা ফাংশন লিখতে হয় (expr_add ডাকে expr_mul, expr_mul ডাকে expr_primary…)। Pratt parser সেই পুরো tower-কে একটা লুপ + একটা table-এ নামিয়ে আনে — precedence আর associativity আর control flow-এর অংশ থাকে না, হয়ে যায় ডেটা।

নতুন operator যোগ করা মানে table-এ এক লাইন। এই shift — “structure থেকে table-এ” — production parser (Rust-analyzer, Go, Monkey-style interpreters, SQL engines) কেন Pratt-ই বেছে নেয়, সেটার হাতে-কলমে উত্তর। সাথে lexer-এ position tracking: error message-এর line:col parse-এর সবচেয়ে দামি by-product।

Tokenizer — position সহ token

@dataclass
class Token:
    kind: str        # 'INT', 'IDENT', 'OP', 'LPAREN', ...
    text: str
    line: int
    col: int

def tokenize(src):
    toks, i, line, col = [], 0, 1, 1
    while i \< len(src):
        c = src[i]
        if c == '\n':
            line, col, i = line + 1, 1, i + 1
        elif c.isspace():
            col, i = col + 1, i + 1
        elif c.isdigit():
            j = i
            while j \< len(src) and src[j].isdigit(): j += 1
            toks.append(Token('INT', src[i:j], line, col))
            col += j - i; i = j
        elif c.isalpha() or c == '_':
            j = i
            while j \< len(src) and (src[j].isalnum() or src[j] == '_'): j += 1
            word = src[i:j]
            kind = 'KW' if word in KEYWORDS else 'IDENT'
            toks.append(Token(kind, word, line, col))
            col += j - i; i = j
        else:                                   # operator — longest-match
            op = next((o for o in OPERATORS if src.startswith(o, i)), None)
            if op is None:
                raise LexError(f'অচেনা অক্ষর {c!r}', line, col)
            toks.append(Token('OP', op, line, col))
            col += len(op); i += len(op)
    toks.append(Token('EOF', '', line, col))
    return toks

Longest-match (<=-কে < = ভেঙে না দেওয়া) এখানেই সিদ্ধান্ত হয় — OPERATORS list-কে length-descending সাজান। Keyword আর identifier-এর পার্থক্য lexical-analysis লেসনের keyword-table lookup।

Binding power — precedence ডেটা হিসেবে

প্রতিটা infix operator-এর বাঁ-দিকের bp আর ডান-দিকের bp আলাদা — এই জোড়াই associativity encode করে:

# operator: (left_bp, right_bp)
INFIX_BP = {
    '+':  (10, 11),   '-':  (10, 11),       # left-assoc: left \< right
    '*':  (20, 21),   '/':  (20, 21),
    '^':  (32, 31),                           # right-assoc: left \> right
    '==':  (5, 6),
}

PREFIX_BP  = {'-': 30, '!': 30}              # unary
POSTFIX_BP = {'(': 40}                        # call: f(...)

Left-assoc +-এ (10, 11): বাঁ-পাশের operand নিজের চেয়ে কম-bp প্রতিবেশী টেনে নিতে পারে না, ডান-পাশের পারে — তাই 1-2-3 পার্স হয় (1-2)-3। Right-assoc ^-এ উল্টো: 2^3^2 হয় 2^(3^2)। Grammar লিখে associativity প্রমাণ করার বদলে দুটা সংখ্যার তুলনা।

Pratt loop

def parse_expr(self, min_bp=0):
    lhs = self.parse_prefix()                 # nudge
    while True:
        tok = self.peek()
        if tok.kind == 'OP' and tok.text in INFIX_BP:
            lbp, rbp = INFIX_BP[tok.text]
            if lbp \< min_bp: break            # এই operator আমার দায়িত্ব না
            self.advance()
            rhs = self.parse_expr(rbp)        # ডান পাশ rbp দিয়ে
            lhs = BinOp(tok.text, lhs, rhs)
        else:
            break
    return lhs

def parse_prefix(self):
    tok = self.next()
    if tok.kind == 'INT':
        return IntLit(int(tok.text))
    if tok.kind == 'IDENT':
        return Ident(tok.text)
    if tok.kind == 'LPAREN':
        e = self.parse_expr(0)
        self.expect('RPAREN')                  # না পেলে line:col সহ error
        return e
    if tok.kind == 'OP' and tok.text in PREFIX_BP:
        operand = self.parse_expr(PREFIX_BP[tok.text])
        return Unary(tok.text, operand)
    raise ParseError(f'অপ্রত্যাশিত token {tok.text!r}', tok.line, tok.col)

Postfix/call একটা ছোট সংযোজন — loop-এর ভেতরে (-এর bp-ও চেক করে call node বানান: fib(n-1)+fib(n-2)-এ fib-এর পরেই (...) খেয়ে Call(fib, args) হবে, comma-separated argument list সহ।

Checkpoint: -2^2 কী হবে? Prefix --এর bp 30, ^-এর left bp 32 — unary শুধু 2 টেনে নেবে, ফলে (-2)^2 নয়, -(2^2)। Mathematical convention এটাই; আপনার table ইচ্ছাকৃতভাবে এই সিদ্ধান্ত নিয়েছে — grammar version-এ এই এক লাইনের জন্য production একটা স্তর বাড়ত।

AST + pretty-printer

@dataclass
class BinOp: op: str; lhs: object; rhs: object
@dataclass
class Unary: op: str; operand: object
@dataclass
class IntLit: value: int
@dataclass
class Ident: name: str
@dataclass
class Call: fn: object; args: list

Printer-এ paren তখনই যখন child-এর bp parent-এর চাহিদার চেয়ে কম — ফলে minimum-parentheses output:

input : 1 + 2 * 3 ^ 2
print : 1 + 2 * 3 ^ 2          # কোনো বাড়তি paren নেই
input : (1 + 2) * 3
print : (1 + 2) * 3            # দরকারি paren টিকে আছে

Error cases — সৎ message

দুটো classic ধরুন:

source: 1 + * 2
error [line 1, col 5]: অপ্রত্যাশিত token '*'

source: (1 + 2
error [line 1, col 8]: '(' বন্ধ হয়নি — ')' চাই, পেল EOF

expect() helper যে token চেয়েছিল আর কী পেল — দুটোই ছাপে। Col সংখ্যা সঠিক কি না নিজে যাচাই করুন — tokenizer-এ col update ভুল হলে সব error message-এর বিশ্বাসযোগ্যতা যায়।

Round-trip টেস্ট

Parser testing-এর সবচেয়ে শক্তিশালী property: print(parse(p)) re-parse করলে হুবহু একই AST আসা উচিত —

def test_roundtrip(src):
    ast1 = parse(src)
    printed = pprint(ast1)
    ast2 = parse(printed)
    assert ast1 == ast2, f'{src!r} → {printed!r} ভিন্ন AST!'

Case list: 1+2*3, (1+2)*3, 2^3^2, -2^2, !(a==b), f(x, g(y), 1+z), a-b-c, a-(b-c)। শেষ দুটো associativity- specific — round-trip এগুলো ধরে ফেলে।

Checkpoint: উপরের ৮টা case-এ round-trip green — তখন parser precedence আর associativity দুটোই ঠিক ধরেছে।

নিজেকে চ্যালেঞ্জ করুন

1. Assignment (x = expr) — lowest bp, right-assoc, আর statement/expression সীমানা
2. Conditional ? : — ternary-র ভেতরে আলাদা parsing rule
3. Index postfix a[i] — call-এর সাথে same bp, different led
4. Lexer mode — string literal escape আর number separator (1_000_000)
5. Recovery — error-এর পরে panic-mode sync (; পর্যন্ত skip) করে এক রানে একাধিক error ছাপা

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Position-carrying tokens	Bytecode VM প্রজেক্টে runtime error-এর source map
Binding-power table	Operator-overloading ভাষা design, query parser
Nudge/led separation	Extensible syntax — macro system-এর ভিত্তি
Round-trip testing	Formatter (prettier-style), refactor tooling