Grammar ও Ambiguity — BNF, derivation, আর দ্ব্যর্থক বাক্য

Grammar — আমাদের official ToyLang expression grammar, module জুড়ে এটাই থাকবে:

# ToyLang expression grammar (precedence-correct, unambiguous)
#
# expr   → term (("+" | "-" | "||" ...) term)*      [lowest]
# term   → unary (("*" | "/" | "%") unary)*
# unary  → ("!" | "-") unary | primary              [highest prefix]
# primary → INT | STRING | TRUE | FALSE | IDENT
#          | "(" expr ")"
#
# Properties proven by this build:
#   * binds tighter than +        (1+2*3 = 1+(2*3))
#   - is left-associative         (8-3-2 = (8-3)-2)
#   parens override everything    ((1+2)*3)
#   unary minus nests             (--5 == 5)

toylang/miniparse.py — পুরো ফাইল:

"""ToyLang expression-only parser + tree printer.
Needs: toylang/lexer.py from the previous lesson.
"""
from toylang.lexer import Lexer, Tok


class ParseError(Exception):
    pass


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

    def peek(self):
        return self.toks[self.i].kind

    def eat(self, kind):
        tok = self.toks[self.i]
        if tok.kind != kind:
            raise ParseError(
                f"expected {kind.name}, got {tok.kind.name} "
                f"@{tok.line}:{tok.col}")
        self.i += 1
        return tok

    # expr → term (("+"|"-"|"||") term)*
    def expr(self):
        node = self.term()
        while self.peek() in (Tok.PLUS, Tok.MINUS, Tok.OROR):
            op = self.toks[self.i]; self.i += 1
            node = (op.value, node, self.term())
        return node

    # term → unary (("*"|"/"|"%") unary)*
    def term(self):
        node = self.unary()
        while self.peek() in (Tok.STAR, Tok.SLASH, Tok.PERCENT):
            op = self.toks[self.i]; self.i += 1
            node = (op.value, node, self.unary())
        return node

    # unary → ("!"|"-") unary | primary
    def unary(self):
        if self.peek() in (Tok.BANG, Tok.MINUS):
            op = self.eat(self.peek())
            return ("u" + op.value, self.unary())
        return self.primary()

    # primary → INT | TRUE | FALSE | IDENT | "(" expr ")"
    def primary(self):
        k = self.peek()
        if k is Tok.INT or k is Tok.IDENT or k is Tok.STRING:
            return self.eat(k).value
        if k is Tok.TRUE:
            self.eat(Tok.TRUE); return True
        if k is Tok.FALSE:
            self.eat(Tok.FALSE); return False
        if k is Tok.LPAREN:
            self.eat(Tok.LPAREN); e = self.expr()
            self.eat(Tok.RPAREN); return ("paren", e)
        raise ParseError(f"unexpected {k.name}")


# ---------- generic tree printer (the promised ~30 lines) ----------
def render(node, indent=""):
    """Nested tuples/lists -> ASCII art tree."""
    if not isinstance(node, (tuple, list)):
        return [indent + repr(node)]
    label = node[0] if isinstance(node[0], str) and len(node) >= 1 else "?"
    kids = node[1:] if isinstance(node, tuple) else node
    out = [indent + f"({label})"]
    for kid in kids:
        out += render(kid, indent + "  ")
    return out


def show(src):
    print(f"\n{src}")
    for line in render(Parser(src).expr()):
        print(line)


def _test():
    assert Parser("1+2*3").expr() == ("+", "1", ("*", "2", "3"))
    assert Parser("8-3-2").expr() == ("-", ("-", "8", "3"), "2")
    assert Parser("(1+2)*3").expr() == ("*", ("paren", ("+", "1", "2")), "3")
    assert Parser("--5").expr() == ("u-", ("u-", "5"))
    print("all grammar tests passed")


if __name__ == "__main__":
    _test()
    show("1+2*3")
    show("8-3-2")

Expected output:

$ python3 toylang/miniparse.py
all grammar tests passed

1+2*3
(+)
  '1'
  (*)
    '2'
    '3'

8-3-2
(-)
  (-)
    '8'
    '3'
  '2'

দ্বিতীয় tree-টা দেখুন — ভেতরের (-) বামে, মানে (8-3)-2: left associativity structurally proven, comment-এ claim নয়।

নিজে বাড়ান:

1. ^ power operator যোগ করুন — right-associative, unary-র চেয়ে নাকি কম tight? (-2^2 = -4 মানে ^ unary-র নিচে।)
2. Comparison layer (==,!=,<,>…) expr আর term-এর মাঝে বসান — ToyLang full grammar-এর জন্য লাগবেই।
3. show()-কে eval করার mini-evaluator লিখুন — tree walk করে value বের করুন, 8-3-2 দেয় 3 কি না verify করুন।