Parsing — recursive descent, Pratt, আর LR-এর ছায়া

toylang/parser.py — পুরো ফাইল (lexer dependency ছাড়া সম্পূর্ণ logic; lexer গত লেসনের ফাইল থেকে import):

"""ToyLang Pratt parser: token stream -> expression AST.
Needs: toylang/lexer.py (lesson 2).
"""
from toylang.lexer import Lexer, Tok

# infix operator -> (binding_power, right_assoc?)
INFIX_BP = {
    Tok.OROR:    (10, False),
    Tok.ANDAND:  (20, False),
    Tok.EQEQ:    (40, False), Tok.BANGEQ: (40, False),
    Tok.LT:      (50, False), Tok.GT: (50, False),
    Tok.LTE:     (50, False), Tok.GTE: (50, False),
    Tok.PLUS:    (60, False), Tok.MINUS: (60, False),
    Tok.STAR:    (70, False), Tok.SLASH: (70, False),
    Tok.PERCENT: (70, False),
}
PREFIX_RBP = 90          # unary - আর ! — সবার চেয়ে টাইট


class ParseError(Exception):
    def __init__(self, msg, tok):
        super().__init__(f"{msg} @{tok.line}:{tok.col}")


class Parser:
    """Pratt parser over a fixed token buffer."""

    def __init__(self, src: str):
        self.toks = Lexer(src).tokens()
        self.i = 0

    # ---- token cursor helpers -------------------------------------
    def peek(self) -> Tok:
        return self.toks[self.i].kind

    def cur(self):
        return self.toks[self.i]

    def advance(self):
        tok = self.toks[self.i]
        self.i += 1
        return tok

    def expect(self, kind: Tok):
        if self.peek() != kind:
            raise ParseError(
                f"expected {kind.name}, found "
                f"{self.cur().kind.name}", self.cur())
        return self.advance()

    # ---- the Pratt core -------------------------------------------
    def expr(self, min_bp: int = 0):
        left = self.nud()
        while True:
            k = self.peek()
            entry = INFIX_BP.get(k)
            if entry is None:
                break
            lbp, right_assoc = entry
            if lbp \<= min_bp:          # tie → বাইরেরটার, left-assoc
                break
            op = self.advance()
            rbp = lbp - 1 if right_assoc else lbp
            right = self.expr(rbp)
            left = (k.name.lower(), left, right)
        return left

    def nud(self):
        """Prefix position: literals, names, parens, unary."""
        tok = self.advance()
        k = tok.kind
        if k is Tok.INT:
            return int(tok.value)
        if k is Tok.STRING:
            return ("str", tok.value)
        if k is Tok.TRUE:
            return True
        if k is Tok.FALSE:
            return False
        if k is Tok.IDENT:
            return ("var", tok.value)
        if k is Tok.MINUS:
            return ("neg", self.expr(PREFIX_RBP))
        if k is Tok.BANG:
            return ("not", self.expr(PREFIX_RBP))
        if k is Tok.LPAREN:
            inner = self.expr(0)
            self.expect(Tok.RPAREN)
            return ("group", inner)
        raise ParseError(f"unexpected {k.name}", tok)

    def parse(self):
        tree = self.expr(0)
        if self.peek() is not Tok.EOF:
            raise ParseError("trailing input", self.cur())
        return tree


# ---------- indented AST printer -----------------------------------
def dump(node, indent=""):
    pad = indent + "| "
    if isinstance(node, tuple):
        head = node[0]
        print(f"{indent}({head}")
        for kid in node[1:]:
            dump(kid, pad)
        print(f"{indent})")
    elif isinstance(node, int) and not isinstance(node, bool):
        print(f"{indent}{node}")
    else:
        print(f"{indent}{node!r}")


def _test():
    P = Parser
    assert P("1+2*3").parse() == ("plus", 1, ("star", 2, 3))
    assert P("8-3-2").parse() == ("minus", ("minus", 8, 3), 2)
    assert P("--5").parse() == ("neg", ("neg", 5))
    assert P("!true || false").parse() == (
        "oror", ("not", True), False)
    assert P("(1+2)*3").parse() == (
        "star", ("group", ("plus", 1, 2)), 3)
    assert P("a \<= b == true").parse() == (
        "eqeq", ("lte", ("var", "a"), ("var", "b")), True)

    for bad in ["1 +", "(1+2", "*3"]:
        try:
            P(bad).parse()
            raise AssertionError(f"no error for {bad!r}")
        except ParseError:
            pass

    print("all parser tests passed")


if __name__ == "__main__":
    _test()
    dump(Parser("1 + 2 * (3 - 1) \<= 10 && ok").parse())

Expected output:

$ python3 toylang/parser.py
all parser tests passed
(andand
| (lte
| | (plus
| | | 1
| | | (star
| | | | 2
| | | | (group
| | | | | (minus
| | | | | | 3
| | | | | | 1
| | | | )
| | | )
| | )
| | 10
| )
| ('var', 'ok')
(andand

Tree পড়ুন নিচ থেকে উপরে: 3-1 সবার ভেতরে, তারপর *2, তারপর +1, তারপর \<=10, শেষে &&ok — evaluation order ঠিক এভাবেই।

নিজে বাড়ান:

1. ^ যোগ করুন INFIX_BP-তে right_assoc=True দিয়ে — test: 2^3^2 tree ডান-spine হবে।
2. Statement layer যোগ করুন: let/if/while/print/block dispatch — example section-এর ছক অনুযায়ী।
3. Panic recovery: ParseError ধরে sync-to-; করে errors list collect করুন — এক run-এ সব ভুল দেখান।