এই পর্বে যা শিখবেন
- EBNF-এর একটি নিয়ম দেখে তার recursive descent function নিজে লিখতে পারা
- Haat-এর সব statement, block,
else if,fnআর(Int, Int) -> Inttype-এর parser peek,advance,match,expectকেন আলাদা, আর কোনটি কখন- AST node-এ অবস্থান রাখা আর statement-স্তরের error message ঠিক জায়গায় দেওয়া
- নিজের parser-কে reference-এর সঙ্গে differential test আর fuzzing দিয়ে মেলানো, আর গভীর nesting-এর বিপদ
১ · Grammar থেকে function — recursive descent-এর মূল ছক
পর্ব ৪৫-এ (Compiler-এর front end) আপনি Haat-এর পুরো front end-এর মানচিত্র আর একটি ছোট সংস্করণ দেখেছেন। এবার তার মাঝের অংশটি পুরোপুরি বানাব: parser, যা token-এর সারি নিয়ে AST বানায়। এই পর্ব statement-এর দিক; expression-এর পুরো Pratt parser আসবে পর্ব ৪৮-এ, আর token কীভাবে তৈরি হয় তা পর্ব ৪৬-এ (হাতে লেখা lexer). এখানে সেই দুটির একটি সংক্ষিপ্ত রূপ সহায়ক হিসেবে ব্যবহার করব।
একটি সরকারি অফিসে ট্রেড লাইসেন্সের আবেদন যাচাইয়ের কথা ভাবুন। প্রধান কেরানি ফর্মের প্রথম ঘর দেখেই বোঝেন এটি কোন ধরনের আবেদন। তারপর “মালিকের তথ্য” অংশটি পাঠান একজন সহকারীর টেবিলে, “ঠিকানা” অংশ আরেকজনের টেবিলে। ঠিকানা-সহকারী আবার “বিভাগ, জেলা, থানা” আলাদা খাতায় মেলান। প্রত্যেকে শুধু নিজের অংশের নিয়ম জানেন, কাজ শেষ হলে ফল ফেরত দেন যিনি পাঠিয়েছিলেন তাঁর হাতে। কোনো ঘর ফাঁকা থাকলে যিনি ধরলেন তিনিই বলেন, “পৃষ্ঠা ২-এ জন্মতারিখের পরে স্বাক্ষর নেই।” Recursive descent parser ঠিক এই অফিস: প্রতিটি “টেবিল” একটি function, আর ফর্মের ভেতরে ফর্ম থাকলে function নিজেকে বা অন্যকে আবার ডাকে।
Recursive descent নামের দুটি অংশ। “Descent” মানে ওপর থেকে নিচে নামা: program থেকে statement, statement থেকে block, block থেকে আবার statement. “Recursive” মানে এই নামা function-এর recursion দিয়ে হয়: block ডাকে statement, আর statement আবার ডাকতে পারে block. Grammar-এর গঠন আর কোডের গঠন হুবহু এক, এটাই এর সবচেয়ে বড় গুণ।
তত্ত্বের দিকটি, অর্থাৎ কোন grammar-এ এভাবে backtracking ছাড়া parse করা যায় (LL(1)), FIRST আর FOLLOW set, আর top-down predictive parser, গণনার তত্ত্ব কোর্সের পর্ব ৩৮-এ প্রমাণসহ আছে; context-free grammar-এর সংজ্ঞা পর্ব ২৫-এ, আর EBNF লেখার কৌশল পর্ব ৪২-এ। এখানে আমরা সেই তত্ত্ব কাজে লাগিয়ে একটি সত্যিকারের ভাষার parser বানাব। অনুবাদের নিয়ম মাত্র কয়েকটি:
| EBNF-এ যা আছে | কোডে যা হয় | Haat-এর উদাহরণ |
|---|---|---|
Nonterminal block | একটি method, self.block() | block = "{" { stmt } "}" |
Terminal ";" | self.expect("SEMI", "…") | প্রতিটি statement-এর শেষে |
বিকল্প a ∣ b | সামনের token দেখে if | statement()-এর শাখাগুলো |
পুনরাবৃত্তি { x } | while loop | block-এর ভেতরের statement |
ঐচ্ছিক [ x ] | if self.match(…) | [ ":" type ], [ "->" type ] |
একটি সতর্কতা। stmts = stmts stmt-এর মতো left recursion সরাসরি function-এ লিখলে stmts() কোনো token না খেয়েই নিজেকে ডাকতে থাকে, আর program থামে না। তাই recursive descent-এ পুনরাবৃত্তি সবসময় { … } আর while দিয়ে লেখা হয়। এটি শুধু কৌশল নয়, অংশ ৮-এর অনুশীলন ৪-এ দেখবেন, এ থেকেই প্রমাণ হয় যে parser সবসময় থামে।
২ · Haat-এর statement grammar আর lookahead-এর সিদ্ধান্ত
পর্ব ০৩-এ (Syntax, semantics আর pragmatics) Haat-এর expression-এর একটি EBNF অংশ দেখেছিলেন। নিচে statement-এর পুরো অংশ, reference বাস্তবায়নের parser.py ঠিক যা মানে। expr এখানে একটি কালো বাক্স: পর্ব ৪৮ তার ভেতরটা খুলবে।
program = { stmt } EOF ;
stmt = letDecl | fnDecl | ifStmt | whileStmt | returnStmt
| printStmt | block | exprOrAssign ;
letDecl = ( "let" | "var" ) IDENT [ ":" type ] "=" expr ";" ;
fnDecl = "fn" IDENT fnRest ;
fnRest = "(" [ param { "," param } ] ")" [ "->" type ] block ;
param = IDENT ":" type ;
ifStmt = "if" expr block [ "else" ( ifStmt | block ) ] ;
whileStmt = "while" expr block ;
returnStmt = "return" [ expr ] ";" ;
printStmt = "print" "(" expr ")" ";" ;
block = "{" { stmt } "}" ;
exprOrAssign = expr [ "=" expr ] ";" ; (* বাঁ পাশ একটি নাম: decision 9 *)
type = "Int" | "Bool" | "Str" | "Unit"
| "(" [ type { "," type } ] ")" "->" type ;Parser প্রতিবার একটি statement শুরু করার আগে সামনের token দেখে, খায় না। একে বলে lookahead. নিচের টেবিলে দেখুন, কোন token দেখলে কোন নিয়ম বাছা হয়:
| সামনের token | নিয়ম | কত token দেখতে হয় |
|---|---|---|
LET, VAR | letDecl | ১ |
IF / WHILE / RETURN / PRINT | নিজ নিজ নিয়ম | ১ |
LBRACE | block | ১ |
FN, তারপর IDENT | fnDecl | ২ |
FN, তারপর LPAREN | exprOrAssign (নামহীন function দিয়ে শুরু) | ২ |
| বাকি সব | exprOrAssign | ১, তারপর expression শেষে = আছে কি না |
দুটি জায়গা বিশেষ। প্রথমটি fn: fn price(…) {…} একটি ঘোষণা, কিন্তু fn(x: Int) { print(x); }(5); একটি anonymous function-কে সঙ্গে সঙ্গে ডাকা, অর্থাৎ একটি expression statement. প্রথম token দুটিতেই FN, তাই reference দ্বিতীয় token-এ তাকায়: self.peek(1).kind == "IDENT". এই এক জায়গায় Haat-এর grammar LL(1) নয়, LL(2). চাইলে left factoring করে এক token-এ নামানো যেত (fn খেয়ে তারপর নাম আছে কি না দেখা), কিন্তু দুই token দেখা কোডকে বেশি পরিষ্কার রাখে।
দ্বিতীয়টি assignment. total = total + 1250; আর price(2, 520); দুটিই শুরু হয় একটি নাম দিয়ে; কোনটি কোন নিয়ম, তা জানা যায় কেবল = পর্যন্ত গেলে, আর তার আগে যেকোনো দৈর্ঘ্যের expression থাকতে পারে। কোনো নির্দিষ্ট k-টি token দেখে এটি ঠিক করা যায় না। Reference তাই “আগে বড়টি পড়ুন, পরে যাচাই করুন” কৌশল নেয়: একটি পুরো expression পড়ে, তারপর = দেখলে যাচাই করে সেটি একটি সাধারণ Var কি না। না হলে invalid assignment target (decision 9: assignment একটি statement, আর তার লক্ষ্য একটি সাধারণ নাম)। C-র ভাষায় এই লক্ষ্যকে বলে l-value.
Dangling else এখানে নেই কেন? পর্ব ২৭-এ (Control flow) dangling else দেখেছিলেন: if a if b s1 else s2-এ else কার? Haat-এ if-এর পরে সবসময় একটি { … } block লাগে, তাই একটি else কোন if-এর, তা বন্ধনীই বলে দেয়। else if লেখার সুবিধাটুকু রাখতে grammar else-এর পরে একটি ifStmt-ও মেনে নেয়, আর AST-এ সেটি বাইরের If-এর else_ ঘরে আরেকটি If হয়ে বসে।
৩ · Token-এর হাতিয়ার — peek, advance, match, expect
সব parse function কয়েকটি ছোট হাতিয়ার ভাগ করে নেয়। Reference-এর parser.py-এর শুরুতে ঠিক এগুলোই আছে, আর নিচের কোডে নাম ও আচরণ হুবহু এক:
peek(ahead): সামনের token দেখা, কিন্তু খাওয়া নয়।EOF-এর পরে আর কিছু নেই, তাই শেষের বাইরে চাইলেEOF-ই ফেরত আসে।advance(): একটি token খাওয়া।EOFকখনো খাওয়া হয় না, যাতে ভুল ইনপুটেও অবস্থান তালিকার বাইরে না যায়।match(kind): ঐচ্ছিক জিনিসের জন্য, “থাকলে খাও, না থাকলে কিছু নয়”। EBNF-এর[ … ]।expect(kind, message): বাধ্যতামূলক জিনিসের জন্য। না পেলে syntax error, আর সঙ্গে একটি নির্দিষ্ট বার্তা:expected ';' after variable declaration.
এই পাতার Python ব্লকগুলো একটি সহায়ক module, haat_front.py, import করে। এতে আছে Token, একটি সংক্ষিপ্ত tokenize (পর্ব ৪৬-এর lexer-এর জায়গায়), reference-এর একই নাম আর field-এর AST class (Let, If, FnDecl …), sexpr (reference-এর python haat.py ast যে S-expression ছাপে, হুবহু সেই লেখা), আর expression-এর জন্য ExprStandIn: reference-এর Pratt loop-এর সংক্ষিপ্ত রূপ, যা পর্ব ৪৮ ধাপে ধাপে বানাবে। Module-টি পাতাতেই রাখা আছে, খুলে পড়তে পারেন:
সহায়ক module haat_front.py দেখুন (ব্লকগুলো এটি import করে)
# haat_front.py — সহায়ক অংশ: পর্ব ৪৭-এর parser এর ওপর দাঁড়ায়।
# Reference-এর tokens.py + lexer.py (পর্ব ৪৬), ast_nodes.py + ast_print.py-র sexpr (পর্ব ৪৯)
# আর parser.py-র expression অংশ (পর্ব ৪৮)-এর সংক্ষিপ্ত রূপ; নাম আর আউটপুট reference-এর মতো।
import re
from dataclasses import dataclass, make_dataclass
@dataclass(frozen=True)
class Token:
kind: str; text: str; line: int; col: int
KW = "let var fn if else while return true false print".split()
OPS = 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()))
SPEC = (r'(?P<skip>//[^\n]*|[ \t\r\n]+)|(?P<IDENT>[A-Za-z_][A-Za-z0-9_]*)|(?P<INT>[0-9]+)'
r'|(?P<STRING>"(?:\\["\\n]|[^"\\\n])*")|(?P<op>==|!=|<=|>=|&&|\|\||->|[-+*/%<>!=(){},;:])|(?P<bad>.)')
def tokenize(src): # lexer stand-in: first lexical error stops it
toks = []
for m in re.finditer(SPEC, src):
g, t, at = m.lastgroup, m[0], m.start()
line, col = src.count("\n", 0, at) + 1, at - src.rfind("\n", 0, at)
if g == "bad":
msg = "unterminated string literal" if t == '"' else f"unexpected character '{t}'"
raise SyntaxError(f"{line}:{col}: error: {msg}")
if g == "skip": continue
kind = OPS[t] if g == "op" else t.upper() if g == "IDENT" and t in KW else g
toks.append(Token(kind, t, line, col))
return toks + [Token("EOF", "", src.count("\n") + 1, len(src) - src.rfind("\n"))]
NODES = {"Num": "value", "Str": "value", "Bool": "value", "Var": "name", "Unary": "op operand",
"Binary": "op left right", "Call": "callee args", "Param": "name type",
"Lambda": "params ret body", "Let": "name mutable type init", "Assign": "name value",
"If": "cond then else_", "While": "cond body", "Return": "value", "Print": "value",
"ExprStmt": "expr", "Block": "stmts", "FnDecl": "name params ret body"}
for _name, _fields in NODES.items(): # same class names and fields; line, col always last
globals()[_name] = make_dataclass(_name, _fields.split() + ["line", "col"])
Program = make_dataclass("Program", ["stmts"])
TypeName = make_dataclass("TypeName", ["name"], frozen=True, namespace={"__str__": lambda s: s.name})
FnType = make_dataclass("FnType", ["params", "ret"], frozen=True, namespace={
"__str__": lambda s: "(" + ", ".join(map(str, s.params)) + ") -> " + str(s.ret)})
INT, BOOL, STR, UNIT = (TypeName(n) for n in ("Int", "Bool", "Str", "Unit"))
def quote(s):
return '"' + s.replace("\\", "\\\\").replace('"', '\\"').replace("\n", "\\n") + '"'
def sexpr(n, ind=0): # same text as `python haat.py ast`
pad = "\n" + " " * (ind + 1); sub = lambda m: sexpr(m, ind + 1); e = lambda m: sexpr(m, ind)
c = type(n).__name__
if c in ("Program", "Block"): return f"({c.lower()}" + "".join(pad + sub(s) for s in n.stmts) + ")"
if c in ("Num", "Bool"): return str(n.value).lower()
if c == "Str": return quote(n.value)
if c == "Var": return n.name
if c == "Unary": return f"({n.op} {e(n.operand)})"
if c == "Binary": return f"({n.op} {e(n.left)} {e(n.right)})"
if c == "Call": return "(call " + " ".join(e(x) for x in [n.callee] + n.args) + ")"
if c in ("Lambda", "FnDecl"):
params = " ".join(f"({p.name} {p.type})" for p in n.params)
head = "(lambda" if c == "Lambda" else f"(fn {n.name}"
return f"{head} ({params}) {n.ret}{pad}{sub(n.body)})"
if c == "Let":
ann = "" if n.type is None else f" {n.type}"
return f"({'var' if n.mutable else 'let'} {n.name}{ann} {e(n.init)})"
if c == "Assign": return f"(set {n.name} {e(n.value)})"
if c == "If": return f"(if {e(n.cond)}{pad}{sub(n.then)}" + ("" if n.else_ is None else pad + sub(n.else_)) + ")"
if c == "While": return f"(while {e(n.cond)}{pad}{sub(n.body)})"
if c == "Return": return "(return)" if n.value is None else f"(return {e(n.value)})"
if c == "Print": return f"(print {e(n.value)})"
return f"(expr {e(n.expr)})"
INFIX = {"OR_OR": 10, "AND_AND": 20, "EQ_EQ": 30, "BANG_EQ": 30, "LT": 40, "LT_EQ": 40,
"GT": 40, "GT_EQ": 40, "PLUS": 50, "MINUS": 50, "STAR": 60, "SLASH": 60, "PERCENT": 60}
class ExprStandIn: # Pratt expression parser (পর্ব ৪৮ builds it step by step)
def expression(self, min_bp=0):
t = self.peek()
if t.kind not in ("INT", "STRING", "TRUE", "FALSE", "IDENT", "LPAREN", "MINUS", "BANG", "FN"):
self.fail("expected expression")
self.advance()
if t.kind == "INT": left = Num(int(t.text), t.line, t.col)
elif t.kind == "STRING":
left = Str(re.sub(r'\\(.)', lambda m: "\n" if m[1] == "n" else m[1], t.text[1:-1]), t.line, t.col)
elif t.kind in ("TRUE", "FALSE"): left = Bool(t.kind == "TRUE", t.line, t.col)
elif t.kind == "IDENT": left = Var(t.text, t.line, t.col)
elif t.kind in ("MINUS", "BANG"): left = Unary(t.text, self.expression(70), t.line, t.col)
elif t.kind == "FN": left = Lambda(*self.function_rest("expected '(' after 'fn'"), t.line, t.col)
else:
left = self.expression(); self.expect("RPAREN", "expected ')' after expression")
last_cmp = None
while True:
t = self.peek()
if t.kind == "LPAREN": # call f(a, b): postfix, binds tightest (80)
self.advance(); args = [] if self.check("RPAREN") else [self.expression()]
while self.match("COMMA"): args.append(self.expression())
self.expect("RPAREN", "expected ')' after arguments")
s = 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
bp = INFIX.get(t.kind, -1)
if bp < min_bp: return left
if bp in (30, 40) and last_cmp == bp: self.fail("comparison operators cannot be chained")
self.advance()
left = Binary(t.text, left, self.expression(bp + 1), t.line, t.col); last_cmp = bpপ্রথম ব্লক: parser-এর কাঠামো আর হাতিয়ার, সঙ্গে program-এর মূল loop. চারটি ব্লক একই namespace ভাগ করে (পরের ব্লক আগে চালালে আগেরগুলো নিজে চলে নেবে), আর প্রতিটি নতুন ব্লক class Parser(Parser) লিখে আগের class-কে বাড়ায়, তাই আগের সব method থেকে যায়। প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।
from haat_front import * # Token, tokenize, AST nodes, sexpr, ExprStandIn
class Parser(ExprStandIn): # parser.py: token helpers + the program loop
def __init__(self, tokens): self.toks, self.pos = tokens, 0
def peek(self, ahead=0): # look, do not consume
return self.toks[min(self.pos + ahead, len(self.toks) - 1)]
def check(self, kind): return self.peek().kind == kind
def advance(self): # consume one token (never past EOF)
tok = self.peek()
if tok.kind != "EOF": self.pos += 1
return tok
def match(self, kind): # consume only if it is this kind
return self.advance() if self.check(kind) else None
def expect(self, kind, message):
if self.check(kind): return self.advance()
if kind == "SEMI" and self.pos > 0: # decision 24: just after the previous token
prev = self.toks[self.pos - 1]
self.fail(message, (prev.line, prev.col + len(prev.text)))
self.fail(message)
def fail(self, message, where=None):
line, col = where or (self.peek().line, self.peek().col)
raise SyntaxError(f"{line}:{col}: error: {message}")
def parse_program(self): return Program(self.statements_until("EOF"))
def statements_until(self, end):
stmts = []
while not self.check(end) and not self.check("EOF"): stmts.append(self.statement())
return stmts
p = Parser(tokenize("var rounds = rounds + 1\nprint(rounds);"))
print(p.expect("VAR", "?"), p.expect("IDENT", "?"), p.expect("EQ", "?"), sep="\n")
print("init:", sexpr(p.expression()), " next:", p.peek())
try: p.expect("SEMI", "expected ';' after variable declaration")
except SyntaxError as err: print(err)আসল আউটপুট (ব্রাউজারের Python):
Token(kind='VAR', text='var', line=1, col=1)
Token(kind='IDENT', text='rounds', line=1, col=5)
Token(kind='EQ', text='=', line=1, col=12)
init: (+ rounds 1) next: Token(kind='PRINT', text='print', line=2, col=1)
1:24: error: expected ';' after variable declaration
তিনটি expect তিনটি token খেয়ে ফেরত দিয়েছে; প্রতিটি token-এ line আর col আছে, যা পরে AST node-এ যাবে। তারপর expression() পড়েছে rounds + 1 আর থেমেছে print-এ, কারণ print কোনো operator নয়। এবার ; চাই, কিন্তু সামনে print (2:1). Error তবু 1:24-এ: আগের token 1 শুরু column 23-এ, দৈর্ঘ্য ১, তাই ঠিক তার পরের ঘর। Reference-এর python -B haat.py ast এই দুই লাইনের ফাইলে ঠিক 1:24: error: expected ';' after variable declaration দেয়। fail একটি Python SyntaxError ছোড়ে; reference নিজের HaatError রাখে আর error-এর পরে থামে না (তার কথা অংশ ৭-এ), কিন্তু বার্তার লেখা একই।
Grammar-এ যে জিনিস ঐচ্ছিক ([ … ], বা একটি loop চলবে কি না), সেখানে match বা check: না পেলে parser অন্য পথ নেয়, কোনো error নয়। যে জিনিস বাধ্যতামূলক, সেখানে expect: না পেলে সঙ্গে সঙ্গে error, আর বার্তায় লেখা থাকে কী প্রত্যাশিত ছিল আর কিসের পরে। সিদ্ধান্তের জন্য peek আর check, খাওয়ার জন্য advance: সিদ্ধান্ত নেওয়ার আগে কখনো token খাবেন না।
৪ · Statement, block আর if/else-if
এবার মূল dispatcher, statement(). এটি অংশ ২-এর টেবিলটিই কোডে লেখা: প্রতিটি if kind == … শাখা একটি EBNF নিয়ম। ছোট নিয়মগুলো (while, return, print) এখানেই লেখা, বড়গুলো আলাদা method-এ। Reference-এ এটি parser.py-র statement, block, if_stmt আর expr_or_assign:
class Parser(Parser): # parser.py: statements, one method per rule
def statement(self): # one token of lookahead picks the rule
kind = self.peek().kind
if kind in ("LET", "VAR"): return self.let_decl()
if kind == "FN" and self.peek(1).kind == "IDENT": return self.fn_decl()
if kind == "IF": return self.if_stmt()
if kind == "WHILE":
kw = self.advance(); cond = self.expression()
return While(cond, self.block("expected '{' after while condition"), kw.line, kw.col)
if kind == "RETURN":
kw = self.advance(); value = None if self.check("SEMI") else self.expression()
self.expect("SEMI", "expected ';' after return"); return Return(value, kw.line, kw.col)
if kind == "PRINT":
kw = self.advance(); self.expect("LPAREN", "expected '(' after 'print'")
value = self.expression(); self.expect("RPAREN", "expected ')' after print argument")
self.expect("SEMI", "expected ';' after print statement"); return Print(value, kw.line, kw.col)
if kind == "LBRACE": return self.block("expected '{'")
return self.expr_or_assign()
def block(self, message):
lb = self.expect("LBRACE", message); stmts = self.statements_until("RBRACE")
self.expect("RBRACE", "expected '}' at end of block"); return Block(stmts, lb.line, lb.col)
def if_stmt(self): # else if → a nested If; else → a Block
kw = self.advance(); cond = self.expression(); then = self.block("expected '{' after if condition")
else_ = None
if self.match("ELSE"):
else_ = self.if_stmt() if self.check("IF") else self.block("expected '{' or 'if' after 'else'")
return If(cond, then, else_, kw.line, kw.col)
def expr_or_assign(self):
first = self.peek(); e = self.expression()
if self.check("EQ"): # decision 9: the target must be a plain name
if not isinstance(e, Var): self.fail("invalid assignment target")
self.advance(); value = self.expression()
self.expect("SEMI", "expected ';' after assignment"); return Assign(e.name, value, e.line, e.col)
self.expect("SEMI", "expected ';' after expression"); return ExprStmt(e, first.line, first.col)
print(sexpr(Parser(tokenize("if n > 5 { print(1); } else if n > 0 { n = n - 1; } else { f(n); }")).parse_program()))আসল আউটপুট (ব্রাউজারের Python):
(program
(if (> n 5)
(block
(print 1))
(if (> n 0)
(block
(set n (- n 1)))
(block
(expr (call f n))))))
এক লাইনে চার রকম statement: if, print, assignment (set) আর expression statement (expr). দেখুন else if কোথায় গেল: বাইরের if-এর তৃতীয় সন্তান একটি block নয়, আরেকটি (if …), যার নিজের else একটি block. f(n); শুরু হয় নাম দিয়ে, তাই গেছে expr_or_assign-এ; পুরো f(n) পড়ার পরে সামনে = নেই, তাই এটি ExprStmt. n = n - 1;-এ = আছে আর বাঁ পাশ একটি Var, তাই Assign. Reference একই লেখার জন্য হুবহু এই S-expression ছাপে। (এই ব্লকে let বা fn নেই, কারণ let_decl আর fn_decl আসবে পরের ব্লকে।)
if_stmt নিজেকে ডাকে: else-এর পরে if থাকলে আরেকটি if_stmt. তাই একটি else if শৃঙ্খল যত লম্বা, call stack তত গভীর। নিচের stepper-এ বাজারঘরের ডেলিভারি চার্জের তিন শাখার একটি if parse হওয়ার সময় stack কীভাবে বাড়ে আর কমে, দেখুন। প্রতিটি ধাপের মান পাতার parser-এ একটি tracing wrapper লাগিয়ে আসল run থেকে নেওয়া।
1if total >= 1000 { return 0; }2else if vip { return 30; }3else { return 60; }
| call stack (নিচে নতুন) | |
| পরের token | |
| AST এ পর্যন্ত |
- শুরু.
statement()সামনেIFদেখেif_stmt()ডাকে। এটিifখায়; একটিIfnode তৈরি হবে, যার অবস্থান হবে এইif-এর 1:1. - শর্ত.
expression()পড়েtotal >= 1000, আর থামে{-এ, কারণ{কোনো operator নয়। এখানে শর্তের চারপাশে বন্ধনী লাগে না, কারণ block-এর{-ই শর্তের শেষ চিহ্ন। - প্রথম block, সবচেয়ে গভীরে.
block()→statements_until("RBRACE")→statement()→RETURNশাখা →expression()পড়ে0. এই মুহূর্তে stack-এ, সবচেয়ে ওপরেরstatements_untilধরে, ৯টি ডাক। else, তারপর আবারif. Block শেষ;match("ELSE")সফল, আর সামনেIF(2:6). তাইif_stmt()নিজেকেই ডাকে। বাইরের ডাকটি এখনো শেষ হয়নি, সে অপেক্ষা করছে ভেতরেরটির ফলের জন্য।- ভেতরের
if. শর্তvip, block-এreturn 30;. সবচেয়ে গভীর অবস্থায় stack এখন আগের চেয়ে এক ঘর বেশি, কারণ মাঝে দুটিif_stmt. - শেষ
else. ভেতরেরif_stmtআবারELSEপায়, কিন্তু এবার সামনে{(3:6), তাইblock(); তার ভেতরেreturn 60;. - ফেরা. ভেতরের
Ifতৈরি হয়ে বাইরেরIf-এরelse_-এ বসে, তারপর বাইরেরটিstatement()-এ ফেরে। Reference-এরast-ও ঠিক এই আকার ছাপে (এখানে block-গুলো জায়গা বাঁচাতে এক লাইনে)। ১০০টিelse ifথাকলে stack-এ ১০০টিif_stmtজমত: অংশ ৮-এ এর দাম দেখবেন।
তিনটি ছোট নিয়মও খেয়াল করার মতো। return-এর পরে ; থাকলে value নেই (Return(None)), না থাকলে একটি expression; এখানে check("SEMI") একটি ঐচ্ছিক অংশের সিদ্ধান্ত। print একটি statement, function নয় (decision 8), তাই তার বন্ধনী grammar-এর অংশ: print 5; লিখলে expected '(' after 'print'. আর statements_until-এর loop দুটি জিনিসে থামে: চাওয়া token (RBRACE বা EOF) আর EOF. দ্বিতীয় শর্তটি না থাকলে একটি না-বন্ধ { loop-কে চিরকাল EOF-এর সামনে ঘোরাত, কারণ advance() EOF খায় না।
৫ · Declaration আর type — let, fn, parameter আর (Int, Int) -> Int
বাকি থাকল ঘোষণা: let/var, নামওয়ালা fn, আর type পড়া। দুটি নকশা-সিদ্ধান্ত এখানে কাজে লাগে। Decision 6: Int Bool Str Unit keyword নয়, সাধারণ IDENT token; type-এর জায়গায় এলে তবেই type. তাই lexer-কে type চিনতে হয় না, parse_type নামটি মিলিয়ে দেখে, আর অচেনা নাম হলে unknown type 'Money'. Decision 7: function type লেখা হয় (T1, …, Tn) -> R, () -> R-সহ; বন্ধনীর পরে -> না থাকলে সেটি type নয়। আর return type নিজেই function type হলে বাড়তি বন্ধনী লাগে না: fn adder(n: Int) -> (Int) -> Int.
নামওয়ালা function আর নামহীন function-এর বাকি অংশ একই: parameter-এর তালিকা, ঐচ্ছিক return type, তারপর body. তাই reference দুটির জন্য একটিই method রেখেছে, function_rest; fn_decl আর expression-এর ভেতরের fn(…) দুজনেই এটি ডাকে, শুধু প্রথম error message আলাদা। নিচের stepper-এ bazar.haat-এর প্রথম function-এর মাথা কীভাবে পড়া হয়, token ধরে ধরে দেখুন (অবস্থানগুলো reference-এর tokens আউটপুট থেকে):
1def fn_decl(self):2 self.advance(); name = self.advance()3 ps, ret, body = self.function_rest(…)4 return FnDecl(name.text, ps, ret, body, …)5def function_rest(self, msg):6 self.expect("LPAREN", msg)7 p = self.expect("IDENT", …)8 self.expect("COLON", …)9 ps.append(Param(p.text, self.parse_type(), …))10 if not self.match("COMMA"): break11 self.expect("RPAREN", …)12 ret = self.parse_type() if self.match("ARROW") …13 return ps, ret, self.block(…)
| call stack | |
| পরের token | |
| params | |
| ret |
- দুই token দেখে সিদ্ধান্ত.
statement()সামনেFNআর তার পরেIDENTদেখেfn_decl()ডাকে। এটিfnআরprice(2:4) খায়; নামটি রাখা হলো, কারণFnDecl-এর অবস্থান হবে নামের অবস্থান। (চাই.function_restexpect("LPAREN")দিয়ে শুরু করে। এখানে(না থাকলে বার্তা হতোexpected '(' after function name; নামহীন function হলেafter 'fn': একই method, ডাকার জায়গা অনুযায়ী আলাদা কথা।- প্রথম parameter.
qty(2:10), তারপর:, তারপরparse_type()পড়েInt(2:15) আর ফেরত দেয়TypeName("Int"). তালিকায় যোগ হলোParam("qty", Int, 2, 10). - কমা, তাই আরেকটি.
match("COMMA")সফল, loop আবার:unit(2:20),:,Int(2:26). কমার পরে আরেকটি parameter বাধ্যতামূলক, তাইfn f(a: Int,)লিখলেexpected parameter name. - কমা নেই, loop শেষ. সামনে
), তাইmatchব্যর্থ,break.expect("RPAREN")সেটি খায় (2:29). - ঐচ্ছিক return type.
match("ARROW")সফল, তাইparse_type()পড়েInt(2:34).->না থাকলে ret হতোUNIT: Haat-এ-> Unitবাদ দেওয়া যায়। - Body.
block(){(2:38) খায়, ভেতরে তিনটি statement পড়ে (let,if,return), আর}(6:1) খেয়েBlockফেরত দেয়। সামনে এখন পরের function-এরfn(7:1). - Node তৈরি.
fn_decl-এ ফিরেFnDecl("price", [qty, unit], Int, Block, 2, 4). S-expression-এর প্রথম লাইন reference-এরast-এর সঙ্গে হুবহু মেলে।
এবার তৃতীয় ব্লক: let_decl, fn_decl, function_rest আর parse_type. শেষ লাইন পুরো bazar.haat parse করে (ফাইলটি পাতায় রাখা আছে, ব্রাউজারের Python সেটি খোলে):
class Parser(Parser): # parser.py: declarations and types
def let_decl(self): # ("let" | "var") NAME [":" type] "=" expr ";"
mutable = self.advance().kind == "VAR"; kw = "var" if mutable else "let"
name = self.expect("IDENT", f"expected variable name after '{kw}'")
ann = self.parse_type() if self.match("COLON") else None
self.expect("EQ", f"expected '=' after variable name in '{kw}'"); init = self.expression()
self.expect("SEMI", "expected ';' after variable declaration")
return Let(name.text, mutable, ann, init, name.line, name.col)
def fn_decl(self): # "fn" NAME, then the shared rest
self.advance(); name = self.advance()
params, ret, body = self.function_rest("expected '(' after function name")
return FnDecl(name.text, params, ret, body, name.line, name.col)
def function_rest(self, lparen_message): # "(" params ")" ["->" type] block
self.expect("LPAREN", lparen_message); params = []
if not self.check("RPAREN"):
while True:
p = self.expect("IDENT", "expected parameter name")
self.expect("COLON", f"expected ':' and a type after parameter '{p.text}'")
params.append(Param(p.text, self.parse_type(), p.line, p.col))
if not self.match("COMMA"): break
self.expect("RPAREN", "expected ')' after parameters")
ret = self.parse_type() if self.match("ARROW") else UNIT
return params, ret, self.block("expected '{' before function body")
def parse_type(self): # Int | Bool | Str | Unit | "(" types ")" "->" type
tok = self.peek()
if tok.kind == "IDENT":
if tok.text not in ("Int", "Bool", "Str", "Unit"): self.fail(f"unknown type '{tok.text}'")
self.advance(); return TypeName(tok.text)
if not self.match("LPAREN"): self.fail("expected a type")
params = [] if self.check("RPAREN") else [self.parse_type()]
while self.match("COMMA"): params.append(self.parse_type())
self.expect("RPAREN", "expected ')' in function type"); self.expect("ARROW", "expected '->' in function type")
return FnType(tuple(params), self.parse_type())
print(sexpr(Parser(tokenize(open("bazar.haat", encoding="utf-8").read())).parse_program()))আসল আউটপুট (ব্রাউজারের Python):
(program
(fn price ((qty Int) (unit Int)) Int
(block
(let p (* qty unit))
(if (>= p 1000)
(block
(return (- p (/ p 10)))))
(return p)))
(fn delivery ((total Int)) Int
(block
(if (>= total 1000)
(block
(return 0))
(block
(return 60)))))
(let first (+ (call price 2 520) (call delivery (call price 2 520))))
(print first)
(var total 0)
(var rounds 0)
(while (< total 5000)
(block
(set total (+ total 1250))
(set rounds (+ rounds 1))))
(print total)
(print (- rounds 1)))
এটি reference-এর python -B haat.py ast examples/bazar.haat-এর আউটপুটের সঙ্গে অক্ষরে অক্ষরে এক (ল্যাবে diff চালিয়ে মেলানো)। নয়টি top-level statement: দুটি fn, একটি let, দুটি var, একটি while আর তিনটি print. (let p (* qty unit))-এ type লেখা নেই, কারণ let p = …-এ annotation নেই (Let.type = None; type পরে checker অনুমান করবে)। let p: Int = … লিখলে হতো (let p Int (* qty unit)). Comment-এর লাইনটি lexer-এই বাদ পড়েছে, parser তা দেখেইনি।
দুটি ছোট পরীক্ষা নিজে করে দেখতে পারেন। fn adder(n: Int) -> (Int) -> Int { return fn(x: Int) -> Int { return x + n; }; }-এ return type নিজেই একটি function type: parse_type ( দেখে বন্ধনীর ভেতরের type-গুলো পড়ে, তারপর -> চায়, তারপর নিজেকে আবার ডেকে শেষের Int পড়ে। ভেতরের নামহীন function আসে return-এর expression থেকে, আর expression parser সেটি পড়তে সেই একই function_rest ডাকে। Reference এই ফাইলে ছাপে (fn adder ((n Int)) (Int) -> Int, তারপর block-এর ভেতরে (return (lambda ((x Int)) Int …)). আর fn(x: Int) { print(x); }(5); একটি expression statement হয়: (expr (call (lambda ((x Int)) Unit …) 5)), যেখানে -> না থাকায় return type Unit. দুটি আউটপুটই ল্যাবে reference চালিয়ে মেলানো।
ছবি ৪৭.১ — delivery-র AST: কোন node কোন method বানাল
প্রতিটি বাক্সে node-এর নাম, তার অবস্থান (line:col, bazar.haat-এ) আর যে parse method সেটি তৈরি করে।
Int) node নয়, একটি TypeName মান, যা node-এর একটি field-এ বসে। Num-গুলো বানায় expression parser.৬ · AST node-এ অবস্থান রাখা
খেয়াল করেছেন, প্রতিটি node তৈরির সময় parser একটি (line, col) দেয়, আর reference-এর সব AST class-এ line, col শেষ দুটি field. কিন্তু কোন token-এর অবস্থান? একটি while statement-এর তো অনেক token. Reference একটি নির্দিষ্ট নিয়ম মানে (README-র “AST nodes” টেবিল):
| Node | অবস্থান | কেন এই token |
|---|---|---|
Let, Assign, FnDecl, Param | নামটি | “'x' is already declared”-এর মতো বার্তা নামের দিকেই আঙুল তোলে |
If, While, Return, Print, Lambda | keyword | statement-টি কোথায় শুরু, তা পরিষ্কার |
Block | { | scope কোথায় শুরু (পর্ব ৫১-এর symbol table এটি কাজে লাগাবে) |
ExprStmt | প্রথম token | expression-এর নিজের মূল token মাঝখানে হতে পারে |
Binary, Unary | operator | division by zero দেখায় /-এর ঘরে (decision 24) |
Call | callee-র শুরু | argument-সংখ্যার ভুল আর stack overflow callee-তে দেখানো হয় |
এই কারণে expr_or_assign expression পড়ার আগেই first = self.peek() রেখে দেয়: ExprStmt-এর অবস্থান প্রথম token, কিন্তু expression পড়ার পরে সেটি আর হাতের কাছে থাকে না। আর let_decl let-এর অবস্থান নয়, name token-এরটি নেয়। এসব খুঁটিনাটি parser-এর কাজের ফল দেখায় অনেক পরে: type checker যখন বলে 5:9: error: type mismatch: expected Int, found Bool, সেই 5:9 এসেছে এখানে, parser-এর বসানো একটি সংখ্যা থেকে। Lexer column গোনে Unicode code point ধরে (decision 1; পর্ব ২১-এ String আর Unicode), তাই বাংলা comment-ওয়ালা লাইনেও source position সঠিক।
৭ · Statement-স্তরের error message — কোথায়, কী বলে
একটি ভালো diagnostic তিনটি প্রশ্নের উত্তর দেয়: কোথায়, কী প্রত্যাশিত ছিল, আর কিসের পরে। Recursive descent-এ তৃতীয়টি প্রায় বিনা খরচে আসে, কারণ প্রতিটি expect জানে সে কোন method-এর ভেতরে: let_decl-এর ; বলে “after variable declaration”, print-এর ; বলে “after print statement”. একটি টেবিল-চালিত LR parser-এ এই প্রসঙ্গ বের করা কঠিন (তুলনা পর্ব ৪৫-এ)।
“কোথায়”-এর একটি বিশেষ নিয়ম আছে: decision 24 অনুযায়ী হারানো ; জানানো হয় আগের token-এর ঠিক পরে, gcc আর rustc-এর মতো। কেন, তা নিচের stepper-এ দেখুন:
1fn half(n: Int) -> Int {2 return n / 23}
| পরের token (peek) | |
| আগের token | |
| কাজ |
- Return শাখা. Function-এর body-র ভেতরে
statement()সামনেRETURN(2:5) দেখে সেই শাখায় যায়, আর keyword-টি খায়। - Value আছে কি না. সামনে
;নয়,n, তাইreturn-এর একটি value আছে:expression(). - Expression থামে
}-এ.n / 2পড়া হলো (Binary("/"), অবস্থান 2:14). পরের token}কোনো operator নয়, তাই expression শেষ। খেয়াল করুন, সেই}পরের লাইনে, 3:1-এ। ;নেই.expect("SEMI", "expected ';' after return"):checkব্যর্থ। সাধারণ নিয়মে error যেত সামনের token-এর ঘরে, 3:1-এ: কিন্তু পাঠক তখন একটি নিরীহ}-এর দিকে তাকিয়ে ভাববেন ভুলটা কোথায়।- আগের token-এর পরে. চাওয়া জিনিস
SEMI, তাইexpectআগের token নেয়:2, শুরু 2:16, দৈর্ঘ্য ১. ফল 2:17, ঠিক যেখানে;বসার কথা। Reference-এরastএই ফাইলে হুবহু2:17: error: expected ';' after returnদেয়।
অন্য সব syntax error জানানো হয় যে token-এ parser আটকাল, সেখানে। শেষ ব্লকটি দুই কাজ করে: প্রথমে parse method-গুলোতে একটি ছোট tracing wrapper লাগিয়ে দেখায় কোন method কাকে কোন token-এ ডাকল (অংশ ৪-এর stepper-এর মতো, এবার আপনার চোখের সামনে), তারপর দশটি ভাঙা program-এর error ছাপে:
depth = 0
def traced(f): # print every call of a parse method, indented by depth
def wrapper(self, *args):
global depth
print(" " * depth + f.__name__, "at", self.peek().text or "EOF")
depth += 1
try: return f(self, *args)
finally: depth -= 1
return wrapper
class Traced(Parser): pass
for m in ("statement", "if_stmt", "block", "expression", "let_decl", "parse_type"):
setattr(Traced, m, traced(getattr(Parser, m)))
Traced(tokenize("if a { } else if b { let n: Int = 0; }")).parse_program()
BROKEN = ["let total = 10\nprint(total);", "let p: Money = 5;", "f(x) = 3;",
"if p >= 1000 return p;", "fn half(n: Int) -> Int { return n / 2 }",
"var x 5;", "fn add(a: Int, b) -> Int { return a + b; }",
"let k: (Int, Int) = 0;", "print 5;", "while x < 3 { x = x + 1;"]
for src in BROKEN:
try: Parser(tokenize(src)).parse_program(); print("ok")
except SyntaxError as err: print(err)আসল আউটপুট (ব্রাউজারের Python):
statement at if
if_stmt at if
expression at a
block at {
if_stmt at if
expression at b
block at {
statement at let
let_decl at let
parse_type at Int
expression at 0
1:15: error: expected ';' after variable declaration
1:8: error: unknown type 'Money'
1:6: error: invalid assignment target
1:14: error: expected '{' after if condition
1:38: error: expected ';' after return
1:7: error: expected '=' after variable name in 'var'
1:17: error: expected ':' and a type after parameter 'b'
1:19: error: expected '->' in function type
1:7: error: expected '(' after 'print'
1:25: error: expected '}' at end of block
প্রথম অংশ একটি call tree: indentation মানে “ভেতরে ডাকা হয়েছে”। else if-এর if_stmt প্রথম if_stmt-এর ভেতরে, আর let n: Int = 0;-এর let_decl প্রথমে parse_type, তারপর expression ডাকে। দ্বিতীয় অংশের দশটি লাইন reference-এর python -B haat.py ast-এর দশটি আউটপুটের সঙ্গে অক্ষরে অক্ষরে মেলে (ল্যাবে প্রতিটি ফাইল আলাদা করে চালানো)। কয়েকটি দেখুন: f(x) = 3; আটকেছে 1:6-এ, =-এ, কারণ পুরো f(x) পড়ার পরেই বোঝা গেছে লক্ষ্যটি নাম নয়। let k: (Int, Int) = 0;-এ বন্ধনীর পরে -> নেই (decision 7), তাই 1:19-এ =. আর শেষটিতে } নেই, error EOF-এর ঘরে, 1:25.
একটি পার্থক্য সৎভাবে বলে রাখি। পাতার parser প্রথম error-এ থামে। Reference থামে না: error পেলে সে panic mode recovery করে, অর্থাৎ পরের ;, একটি পুরো { … } বা পরের statement-keyword পর্যন্ত token ফেলে দিয়ে আবার শুরু করে (decision 25), আর শেষে সব error অবস্থান অনুযায়ী সাজিয়ে দেখায়। তাই examples/err_syntax.haat-এ reference চারটি error দেয়, আর পাতার parser শুধু প্রথমটি, যা reference-এর প্রথম লাইনের সঙ্গে হুবহু এক। Recovery, ক্যাসকেড এড়ানো আর ভালো বার্তার নকশা পুরোটা পর্ব ৫০-এর বিষয় (Parser-এর error recovery আর ভালো diagnostic message).
৮ · Reference-এর সঙ্গে মিলিয়ে দেখা — differential test, ফাঁক আর গভীরতার সীমা
পাতার parser সঠিক, এটি কীভাবে জানলাম? কয়েকটি উদাহরণ চোখে মেলানো যথেষ্ট নয়। ল্যাবে একটি differential test চালানো হয়েছে: একই ইনপুট পাতার চারটি ব্লকের parser আর reference-এর parser.py দুটিতেই, আর আউটপুট (S-expression, বা error হলে প্রথম error-এর লেখা) তুলনা। সত্যিকারের run, Python 3.14.4:
$ python -B difftest.py
examples: 13/13 identical
random programs: 1000/1000 identical output (800 parse without error in the reference)
one-token deletions: 2403/2403 identical (2063 of them are syntax errors with the same first message)
তিনটি স্তর। (১) reference-এর examples/-এর ১৩টি ফাইল, যাদের চালানোর প্রত্যাশিত আউটপুট .out golden file-এ রাখা। (২) grammar-based fuzzing: অংশ ২-এর EBNF থেকে seed (47) দিয়ে ১,০০০টি এলোমেলো program, nested if/else if, while, fn, function type আর expression-সহ; তার ৮০০টি বৈধ, বাকি ২০০টিতে মূলত এলোমেলো শৃঙ্খলিত তুলনা (a < b < c). (৩) mutation: বৈধ program থেকে এলোমেলো একটি করে token মুছে ২,৪০৩টি ভাঙা program, যার ২,০৬৩টিতে দুই parser একই প্রথম error দিয়েছে আর বাকিগুলো মুছেও বৈধ থেকে একই গাছ দিয়েছে।
তবু সংখ্যা সব বলে না। অনুশীলন ২-এ এমন একটি বাগ দেখবেন (parameter তালিকার শেষে কমা মেনে নেওয়া), যা ১,০০০টি এলোমেলো program আর সব ৬০,৩৭৬টি এক-token-মোছা program-এর একটিতেও ধরা পড়েনি, কারণ generator কখনো শেষে কমা লেখে না আর একটি token মুছে , b: Int পুরোটা সরানো যায় না। ধরেছে একটি হাতে লেখা edge case. তাই random test-এর পাশে সবসময় সীমার উদাহরণ রাখুন: খালি তালিকা, শেষে কমা, খালি block, EOF-এ শেষ হওয়া ফাইল।
এই test-গুলো একবার লিখে ফেলে রাখার জিনিস নয়। পরের পর্বগুলোতে parser-এ বদল আসবে (পর্ব ৪৮-এ পুরো expression parser, পর্ব ৫০-এ recovery), আর প্রতিটি বদলের পরে একই script আবার চালালে বোঝা যায় পুরোনো আচরণ ভাঙেনি কি না। Golden file-এর নিয়মও সরল: প্রত্যাশিত আউটপুট একবার যত্ন করে যাচাই করে ফাইলে রাখুন, তারপর test শুধু তুলনা করে। আউটপুট ইচ্ছা করে বদলালে (যেমন একটি error message আরও পরিষ্কার করলে) golden file-ও নতুন করে লিখুন, আর সেই বদলটি নিজের চোখে পড়ে নিন।
গভীর nesting: যেখানে recursion-এর দাম দিতে হয়
Recursive descent প্রতিটি nesting স্তরে কয়েকটি function call-এর frame জমায়। ইনপুট যদি হাজারটি { দিয়ে শুরু হয়? ল্যাবে reference-কে শুধু { আর } দিয়ে বানানো ফাইল দেওয়া হয়েছে: শুরুতে n-টি {, শেষে n-টি } (Python 3.14.4, Windows; সীমাটি মেশিন আর stack-এর আকারের ওপর নির্ভর করে):
$ python -B probe.py # প্রতিটি n তিনবার, haat.py ast দিয়ে
1000 nested blocks: ['ok']
1100 nested blocks: ['ok']
1200 nested blocks: ['ok']
1300 nested blocks: ['RecursionError: Stack overflow (used 2912 kB)', 'RecursionError: Stack overflow (used 2913 kB)']
2000 nested blocks: ['RecursionError: Stack overflow (used 2912 kB)', 'RecursionError: Stack overflow (used 2913 kB)', 'RecursionError: Stack overflow (used 2914 kB)']
$ python -c "compile('x = ' + '(' * 201 + '1' + ')' * 201, 's', 'exec')"
SyntaxError: too many nested parentheses
Reference ১,২০০ স্তর পর্যন্ত চলেছে, কিন্তু ১,৩০০ স্তরে Haat-এর একটি পরিষ্কার error নয়, Python-এর একটি stack overflow traceback. শেষ দুই লাইন CPython 3.14-এর নিজের parser: সে ২০০ স্তরের পরে বন্ধনী মানে না, আর একটি বোধগম্য syntax error দেয়। এটিই nesting limit-এর উদ্দেশ্য: সাধারণ program কখনো এত গভীরে যায় না, কিন্তু একটি ভাঙা বা ইচ্ছাকৃত ইনপুট যেন compiler-কে ফেলে না দেয়। এটি Haat reference-এর একটি সীমা, বাগ বলা চলে; অনুশীলন ১-এ নিজের parser-এ সীমা যোগ করবেন।
আরও গভীরে: বাস্তবের বড় recursive descent parser-ও খাঁটি LL(1) নয়। Clang-এর C++ parser কিছু অস্পষ্ট জায়গায় “tentative parsing” করে: একটি ব্যাখ্যা ধরে এগোয়, না মিললে অবস্থান ফিরিয়ে আনে, কারণ C++-এ T(x); একটি declaration না expression, তা অনেক সময় সামনে অনেক দূর না পড়ে বলা যায় না। Python 3.9 থেকে CPython-এর parser একটি PEG grammar থেকে তৈরি (PEP 617): এটিও recursive descent, কিন্তু backtracking আর memoization (packrat) সহ, যাতে পুরোনো LL(1) parser-এ লেখা যায় না এমন নিয়মও লেখা যায়। Haat-এর সরল grammar এসব ছাড়াই চলে, আর সেটি নকশার একটি সচেতন সিদ্ধান্ত।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- একটি EBNF নিয়ম থেকে recursive descent function লিখুন। Nonterminal → function, terminal →
expect,{ }→while,[ ]→if match, বিকল্প → সামনের token দেখেif. - Left-recursive grammar-এ recursive descent কেন চলে না? Function কোনো token না খেয়েই নিজেকে ডাকে, তাই অসীম recursion; সমাধান loop বা left recursion দূর করা।
- Recursive descent আর LL(1)-এর সম্পর্ক? LL(1) grammar হলে প্রতিটি সিদ্ধান্ত একটি lookahead token-এ হয়, তাই backtracking লাগে না; হাতে লেখা parser প্রয়োজনে দুই token দেখে বা “পড়ে পরে যাচাই” করে।
- Dangling else কীভাবে এড়াবেন? বাধ্যতামূলক block (Haat, Rust, Go), বা নিয়ম “else সবচেয়ে কাছের জোড়াহীন if-এর” (C, Java).
- Syntax error-এর অবস্থান কোথায় দেবেন? সাধারণত আটকে যাওয়া token-এ; হারানো
;আগের token-এর ঠিক পরে।
৯ · AI-এর যুগে recursive descent parser
“একটি ছোট ভাষার parser লিখে দাও” AI assistant-এর খুব প্রিয় কাজ, আর প্রথম দেখায় ফলও চমৎকার লাগে। সমস্যা থাকে সীমার জায়গায়: যে ইনপুট উদাহরণে নেই। বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
তালিকার শেষে কমা মেনে নেওয়া (fn f(a: Int,)), বা খালি তালিকায় আটকে যাওয়া | হাতে লেখা edge case: (), (a: Int,), (,); reference-এর সঙ্গে তুলনা |
Loop-এ শুধু } দেখা, EOF নয়, ফলে না-বন্ধ block-এ চিরকাল ঘোরা | while x < 3 { x = x + 1;-এর মতো ফাইল; সময়সীমা দিয়ে test |
| Left-recursive নিয়ম সরাসরি function-এ লেখা, বা precedence আর associativity উল্টে ফেলা | 10 - 4 - 3-এর মতো ইনপুটে গাছ দেখা; পর্ব ৪৮-এর binding power টেবিলের সঙ্গে মেলানো |
x + 1 = 5; মেনে নেওয়া, বা else if-কে ভুল if-এর সঙ্গে জোড়া | AST/S-expression ছেপে reference-এর ast-এর সঙ্গে diff |
| Error-এর অবস্থান আন্দাজে (পরের লাইনে) বা বানানো বার্তা | Golden file-এ প্রতিটি error-এর হুবহু লেখা রাখা |
| গভীর nesting-এ crash, বা “Python-এ recursion limit নেই” জাতীয় ভুল দাবি | ১,০০০+ স্তরের তৈরি ইনপুট; সত্যিকারের run |
AI-কে কাজে লাগানোর ভালো উপায়: grammar নিজে দিন, নাম আর বার্তা নির্দিষ্ট করে দিন, আর কোডের সঙ্গে test-ও চান, যাতে নিজে চালিয়ে মেলাতে পারেন।
AI-এর লেখা parser হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Recursive descent ছয় দশকের পুরোনো কৌশল। তবু আজও কেন এত টিকে আছে, আর কোথায় এর সীমা?
ধারণাটি ১৯৬০-এর দশকের শুরু থেকে আছে: ALGOL 60-এর প্রথম দিকের compiler-গুলোতে grammar-এর নিয়ম ধরে একটির ভেতরে আরেকটি procedure ডেকে parse করার কৌশল দেখা যায় (কে প্রথম, সে নিয়ে উৎসভেদে ভিন্ন দাবি আছে)। Niklaus Wirth এটিকে জনপ্রিয় করেন: তাঁর Pascal আর পরে Oberon compiler হাতে লেখা recursive descent, আর তাঁর পাঠ্যবই “Compiler Construction” পুরো কৌশলটি একটি ছোট ভাষার ওপর শেখায়। এর পরে LR parser আর yacc-এর মতো generator জনপ্রিয় হয়, কারণ তারা বড় শ্রেণির grammar সামলায় আর grammar থেকেই parser বানায়। তবু production compiler-এর একটি বড় অংশ শেষে হাতে লেখা parser-এ ফিরেছে; সেই ইতিহাস পর্ব ৪৫-এ দেখেছেন।
টিকে থাকার কারণ এই পর্বেই দেখা গেছে। কোড grammar-এর আয়না, তাই নতুন কেউ পড়ে বুঝতে পারেন। প্রতিটি expect জানে সে কোন প্রসঙ্গে, তাই “expected ';' after return”-এর মতো নির্দিষ্ট বার্তা সহজ। দুই token দেখা, “পড়ে পরে যাচাই”, বা C-র typedef নামের মতো প্রসঙ্গ-নির্ভর সিদ্ধান্ত (lexer hack) একটি সাধারণ if দিয়েই যোগ করা যায়; generator-এ এসব প্রায়ই জটিল কৌশল চায়। আর বাড়তি কোনো tool বা build ধাপ লাগে না।
সীমাও স্পষ্ট। Left recursion সরাসরি লেখা যায় না; expression-এর precedence-স্তর গুনে গুনে function লিখলে কোড লম্বা আর ধীর হয়, তাই প্রায় সবাই expression-এ Pratt বা precedence climbing নেয় (পর্ব ৪৮)। Grammar অস্পষ্ট বা LL নয় এমন জায়গায় backtracking লাগে, যার খরচ খারাপ ক্ষেত্রে অনেক বেশি; CPython এজন্যই ৩.৯ সংস্করণে (PEP 617, ২০২০) তার পুরোনো LL(1) parser বদলে memoization-সহ একটি PEG parser নিয়েছে, যা এখনো recursive descent, কিন্তু generator থেকে তৈরি। আর recursion-এর গভীরতা stack-এর ওপর নির্ভর করে, অংশ ৮-এ যা reference-কে ১,৩০০ স্তরে ফেলে দিয়েছে।
মূল উপলব্ধি: recursive descent জিতেছে কারণ এটি মানুষের জন্য লেখা: পড়া, বদলানো আর ভালো error দেওয়া সহজ। বড় grammar-এর তাত্ত্বিক ক্ষমতা কম হলেও, ভালোভাবে নকশা করা ভাষায় সেই ক্ষমতার প্রায় দরকারই পড়ে না।
প্র ০২Haat-এর এক জায়গায় দুই token lookahead লাগে। C, C++ আর Rust-এ কোন জায়গাগুলো আরও কঠিন, আর ভাষার নকশা কীভাবে parser-কে সহজ বা কঠিন করে?
Haat-এর কঠিনতম জায়গা খুবই নিরীহ: fn-এর পরে নাম, না (. দুটি token দেখলেই উত্তর মেলে। অন্য ভাষায় অবস্থা অনেক খারাপ হতে পারে, আর প্রায় সবসময় কারণ একটি নকশা-সিদ্ধান্ত।
C: T * x; হয় T আর x-এর গুণ (একটি expression statement), নয়তো x নামের একটি pointer-এর ঘোষণা: T আগে typedef দিয়ে type হিসেবে ঘোষিত কি না তার ওপর নির্ভর করে। grammar একা এটি বলতে পারে না; parser-কে symbol table দেখতে হয়, আর lexer প্রায়ই typedef নামকে আলাদা token হিসেবে পাঠায়। এই কৌশলের নামই lexer hack. C++: সমস্যা আরও বড়। Widget w(); একটি object তৈরি নয়, w নামের একটি function-এর ঘোষণা; Scott Meyers এর নাম দিয়েছিলেন “most vexing parse”. C++-এর নিয়ম বলে, যা declaration হিসেবে পড়া যায় তা declaration, আর সেটি বুঝতে parser-কে অনেক সময় অনেক দূর পড়ে আবার ফিরতে হয়; Clang-এর tentative parsing ঠিক এই কাজ করে। C++11-এর brace initialization (Widget w{};) আংশিকভাবে এই ফাঁদ এড়ানোর পথ দেয়।
Rust: struct literal লেখা হয় Point { x: 1, y: 2 }. তাহলে if x == Point { … }-এ { কি struct literal-এর শুরু, না if-এর block? Rust নিয়ম করেছে: if আর while-এর শর্তে বন্ধনী ছাড়া struct literal চলবে না। Parser সহজ রাখতে ভাষা ব্যবহারকারীর ওপর একটি ছোট নিয়ম চাপিয়েছে। Haat এই সমস্যায় পড়েই না, কারণ তার struct literal নেই, আর শর্তের পরের { সবসময় block. কোনো বর্ধিত Haat-এ record literal যোগ করলে ঠিক এই প্রশ্ন আবার উঠবে।
মূল উপলব্ধি: parser-এর কঠিনতা ভাষার নকশা থেকে আসে। ভাষা নকশার সময় “প্রতিটি construct কি প্রথম এক-দুটি token-এ চেনা যায়?” প্রশ্নটি করলে parser সহজ হয়, error message ভালো হয়, আর মানুষও কোড পড়ে কম ভুল বোঝেন।
প্র ০৩“আগে বড়টি পড়ুন, পরে যাচাই করুন” — assignment-এর লক্ষ্য পরীক্ষার এই কৌশল অন্য ভাষাগুলো কীভাবে ব্যবহার করে?
Haat-এ x = e; আর e; একই রকম শুরু হয়, আর =-এর আগে যেকোনো দৈর্ঘ্যের expression থাকতে পারে। নির্দিষ্ট কয়েকটি token দেখে নিয়ম বাছা অসম্ভব। Reference তাই বাঁ পাশকে একটি সাধারণ expression হিসেবে পড়ে, একটি বড় ভাষা (“যেকোনো expression”) মেনে নিয়ে, তারপর = দেখলে ছোট ভাষায় নামায়: বাঁ পাশ Var না হলে invalid assignment target (decision 9). Grammar দিয়ে যা বলা কঠিন, কোডের একটি isinstance তা সহজে বলে।
অনেক বড় ভাষা একই পথে। C-তে assignment একটি expression, আর বাঁ পাশ হতে হয় একটি modifiable l-value; parser সাধারণত বাঁ পাশকে যেকোনো unary expression হিসেবে পড়ে, আর পরের ধাপের পরীক্ষা (a + b) = 5-কে আটকায়, GCC-র পরিচিত বার্তা “lvalue required as left operand of assignment”. JavaScript-এর spec এই কৌশলকে আনুষ্ঠানিক নাম দিয়েছে, “cover grammar”: (a, b) পড়ার সময় parser জানে না এটি একটি বন্ধনী-ঘেরা expression, না একটি arrow function-এর parameter তালিকা; সে একটি “ঢাকনা” নিয়মে পড়ে, আর পরে => দেখলে নতুন করে ব্যাখ্যা করে। Destructuring assignment [x, y] = [y, x]-ও এভাবে: বাঁ পাশ প্রথমে একটি array literal হিসেবে পড়া হয়।
Python-এও তাই। Python 3.8-এর walrus operator := (PEP 572) assignment-কে expression-এর ভেতরে আনল, কিন্তু তার লক্ষ্য শুধু একটি নাম; আর সাধারণ assignment-এ f() = 1 লিখলে CPython-এর parser আগে পুরোটা পড়ে, তারপর “cannot assign to function call” জানায়। Python-এর = statement আর := expression-এর এই ভাগ ঠিক Haat-এর মতো একটি সচেতন সিদ্ধান্ত: C-র বিখ্যাত বাগ if (x = 5) এভাবে grammar-এর স্তরেই বন্ধ হয়।
মূল উপলব্ধি: parser-এর কাজ grammar হুবহু অনুসরণ করা নয়, সঠিক ভাষা মেনে নেওয়া। কখনো একটি বড় ভাষা পড়ে পরে ছাঁটাই করা সবচেয়ে সরল আর সবচেয়ে ভালো error message-এর পথ, যতক্ষণ ছাঁটাইয়ের পরীক্ষাটি ঠিক জায়গায় আর ঠিক বার্তায় হয়।
প্র ০৪Haat প্রতিটি statement-এর শেষে ; চায়। JavaScript, Go আর Python অন্য পথ নিয়েছে। কোন পথের কী দাম, আর error message-এ এর প্রভাব কী?
Statement কোথায় শেষ, সেটি parser-কে জানাতে হয়। Haat, C আর Java স্পষ্ট ; চায়। সুবিধা: নিয়ম এক লাইনের, আর একটি statement কয়েক লাইনে ভাঙা যায় কোনো ঝুঁকি ছাড়া। দাম: ভুলে গেলে error, আর সেটি টের পাওয়া যায় পরের token দেখে, প্রায়ই পরের লাইনে। তাই decision 24: বার্তাটি আগের token-এর ঠিক পরে বসানো। GCC আর Clang একই কাজ করে, আর Clang প্রায়ই একটি “fix-it” পরামর্শও দেয়: ঠিক কোন ঘরে ; বসালে ঠিক হবে।
JavaScript নিয়েছে automatic semicolon insertion: কিছু জায়গায় ; না থাকলে parser নিজেই ধরে নেয়। সুবিধা স্পষ্ট, কিন্তু নিয়মগুলো সূক্ষ্ম; সবচেয়ে বিখ্যাত ফাঁদ return-এর পরে নতুন লাইনে value লেখা: parser সেখানে ; বসিয়ে দেয়, আর function undefined ফেরত দেয়। Go-র পথ আরও কঠোর আর পূর্বানুমেয়: lexer নিজেই কিছু token-এর পরে লাইন শেষ হলে একটি ; token যোগ করে (Go spec-এ লেখা নিয়ম)। ফলে Go-তে if x {-এর { পরের লাইনে নামানো যায় না, কারণ শর্তের পরে লাইন ভাঙলেই একটি ; বসে যায়: style-এর একটি তর্ক grammar-ই মিটিয়ে দিয়েছে। Python নতুন লাইনকেই statement-এর শেষ ধরে, আর indentation থেকে block বানায় (lexer INDENT/DEDENT token পাঠায়); বন্ধনীর ভেতরে লাইন ভাঙা তখন বিশেষ নিয়ম।
Error message-এর দিক থেকে প্রতিটি পথের নিজস্ব চেহারা। স্পষ্ট ;-এ বার্তা পরিষ্কার, শুধু অবস্থানটি একটু সামলাতে হয়। ASI-তে অনেক ভুল আদৌ error হয় না, ভুল আচরণ হয়, যা আরও খারাপ। Go আর Python-এ ভুল লাইন-ভাঙা একটি অদ্ভুত বার্তা দিতে পারে, কারণ lexer যে token বসিয়েছে, প্রোগ্রামার তা দেখেননি।
মূল উপলব্ধি: ছোট একটি syntax সিদ্ধান্ত parser-এর জটিলতা, error message-এর মান আর এমনকি কোডের style পর্যন্ত ঠিক করে দেয়। Haat একটি শিক্ষার ভাষা, তাই সে সবচেয়ে স্পষ্ট পথটি বেছেছে।
প্র ০৫অংশ ৮-এ reference ১,৩০০টি nested block-এ ভেঙে পড়েছে। একটি parser-এর জন্য গভীরতার সীমা কেন নিরাপত্তার প্রশ্নও, আর বাস্তব compiler এটি কীভাবে সামলায়?
Recursive descent প্রতিটি nesting স্তরে কয়েকটি function-এর frame call stack-এ রাখে। Stack-এর আকার সীমিত, তাই ইনপুট যথেষ্ট গভীর হলে parser একটি stack overflow-এ পড়ে। Python-এ সেটি একটি RecursionError; C বা C++-এ লেখা parser-এ সাধারণত পুরো প্রক্রিয়া crash করে। ল্যাবের run-এ Haat reference ১,২০০ স্তর পর্যন্ত চলেছে আর ১,৩০০-তে Python-এর traceback দিয়েছে (মাঝের ঠিক সীমাটি run-ভেদে সামান্য সরে); Haat-এর কোনো line:col: error নয়। কোনো সাধারণ বাজারঘর program এত গভীরে যাবে না, কিন্তু parser-এর ইনপুট সবসময় বিশ্বস্ত নয়।
এখানেই নিরাপত্তার প্রশ্ন। যে service ব্যবহারকারীর পাঠানো কোড, JSON, config বা query parse করে, সে একটি অতি-গভীর ইনপুট পেয়ে crash করলে সেটি একটি denial of service. Fuzzing tool-গুলো ঠিক এই ধরনের বাগ নিয়মিত খুঁজে পায়, কারণ এলোমেলো ইনপুটে বন্ধনী জমতে সময় লাগে না। তাই পরিণত parser-গুলো সীমা রাখে। CPython 3.14-এ ল্যাবের সত্যিকারের run: ২০০ স্তর পর্যন্ত বন্ধনী চলে, ২০১-এ SyntaxError: too many nested parentheses. Clang-এর ডকুমেন্টেশনে -fbracket-depth নামের একটি option আছে, যার ডিফল্ট সীমা ২৫৬ বলে লেখা; সীমা ছাড়ালে একটি পরিষ্কার error.
সমাধানের তিনটি পথ। (১) একটি গভীরতা-গণনা: প্রতিটি nested ডাকে বাড়ে, ফেরার সময় কমে, সীমা ছাড়ালে বোধগম্য error; অনুশীলন ১-এ এটিই করবেন। (২) কিছু শৃঙ্খলকে loop বানানো: else if শৃঙ্খল recursion না করে একটি loop-এ পড়া যায়, তারপর AST উল্টো দিক থেকে জোড়া লাগানো। (৩) পুরো parser-কে একটি নিজস্ব stack দিয়ে লেখা (LR parser বা Pratt-এর stack-রূপ), যেখানে গভীরতা শুধু heap-এর মাপে সীমিত। তবে AST নিজেও গভীর হবে, আর পরের প্রতিটি pass (resolver, checker, interpreter) যদি recursion-এ গাছ হাঁটে, তাদেরও একই সমস্যা; তাই সীমা front end-এই রাখা সবচেয়ে সরল।
মূল উপলব্ধি: একটি parser-এর নির্ভুলতা শুধু “সঠিক program-এ সঠিক গাছ” নয়; ভাঙা আর বিদ্বেষী ইনপুটেও সে যেন নিয়ন্ত্রিতভাবে, একটি পরিষ্কার বার্তা দিয়ে থামে।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। প্রতিটি আউটপুট Haat reference বা পাতার parser-এর সত্যিকারের run থেকে।
-
নকশা ও বাস্তবায়ন — nesting limit: পাতার
Parser-কে বাড়িয়ে একটি গভীরতার সীমা যোগ করুন: statement আর expression মিলিয়ে ১০০ স্তরের বেশি nesting হলেnesting too deep (limit 100)error, ঠিক যে token-এ সীমা ছাড়াল সেখানে। শর্ত: সাধারণ program-এর আউটপুট একটুও বদলাবে না।সবচেয়ে কম জায়গায় বদল:
statementআরexpression-কে একটি পাহারাদার method দিয়ে মোড়ানো, কারণ সব nesting এ দুটির ভেতর দিয়েই যায় (block আসে statement থেকে, বন্ধনী আর call আসে expression থেকে)।MAX_DEPTH = 100 class Guarded(Parser): depth = 0 def nested(self, method, *args): if self.depth >= MAX_DEPTH: self.fail("nesting too deep (limit 100)") self.depth += 1 try: return method(self, *args) finally: self.depth -= 1 # ফেরার পথে, error হলেও def statement(self): return self.nested(Parser.statement) def expression(self, min_bp=0): return self.nested(Parser.expression, min_bp)ল্যাবের সত্যিকারের run (n = ফাইলের শুরুতে কতটি
{, বাprint(-এর পরে কতটি():99 blocks: (program 100 blocks: (program 101 blocks: 1:101: error: nesting too deep (limit 100) 1500 blocks: 1:101: error: nesting too deep (limit 100) 98 parens: (program 99 parens: 1:106: error: nesting too deep (limit 100)১০০টি block চলে (১০০টি statement-স্তর), ১০১তম
{-এ (column 101) পরিষ্কার error, আর ১,৫০০টিতেও আর crash নেই। বন্ধনীতে সীমা একটু আগে আসে, কারণprintstatement নিজে একটি স্তর আর তার argument-এর expression আরেকটি। ১,০০০টি এলোমেলো program-এ আউটপুট আগের মতোই ছিল (১,০০০/১,০০০)।finallyজরুরি: error-এর পরে গণনা ঠিক না রাখলে reference-এর মতো recovery করা parser পরের statement-এ ভুল গভীরতা দেখত। -
ভুল খুঁজুন — শেষের কমা: একজন
function_rest-এর loop এভাবে “সরল” করলেন। পাতার সব উদাহরণ আরbazar.haatআগের মতোই চলে। ভুলটি কোথায়, কোন ইনপুটে ধরা পড়ে, আর random test কেন ধরেনি?self.expect("LPAREN", lparen_message); params = [] while not self.check("RPAREN"): p = self.expect("IDENT", "expected parameter name") self.expect("COLON", f"expected ':' and a type after parameter '{p.text}'") params.append(Param(p.text, self.parse_type(), p.line, p.col)) if not self.match("COMMA"): break self.expect("RPAREN", "expected ')' after parameters")কমা খাওয়ার পরে loop আবার শর্ত দেখে; সামনে
)থাকলে loop শেষ, অর্থাৎfn f(a: Int,) { }বৈধ হয়ে যায়। Grammar বলে"," param: কমার পরে একটি parameter বাধ্যতামূলক। Reference-এর গঠনif not check(RPAREN): while True: …ঠিক এই কারণে। সত্যিকারের run:buggy parser : (program (fn f ((a Int)) Unit (block))) reference : 1:13: error: expected parameter nameল্যাবে এই বাগওয়ালা parser-কে অংশ ৮-এর ১,০০০টি এলোমেলো program-এ চালালে ১,০০০টিতেই reference-এর সঙ্গে মিলেছে, আর বৈধ program-গুলোর প্রতিটি token একে একে মুছে বানানো ৬০,৩৭৬টি ভাঙা program-এর একটিতেও অমিল হয়নি। কারণ generator কখনো শেষে কমা লেখে না, আর একটি token মুছে
, b: Int-এর মতো পুরো parameter সরানো যায় না। শিক্ষা: fuzzing সেই ভুলই খোঁজে যা তার generator তৈরি করতে পারে; তালিকার সীমা (খালি, এক উপাদান, শেষে কমা) হাতে লিখে রাখতে হয়। -
আউটপুট বলুন: প্রতিটি ফাইলে
python haat.py astকী ছাপবে? (ক)var n: Int = 3;/while n > 0 { n = n - 1; }/print(n)(তিন লাইন, শেষে;নেই) (খ)var stock = 5;/stock + 1 = 5;(গ)let f: (Int) -> Int = fn(x: Int) -> Int { return x + 1; };/print(f(41));Reference-এর সত্যিকারের আউটপুট:
(ক) 3:9: error: expected ';' after print statement (খ) 2:11: error: invalid assignment target (গ) (program (let f (Int) -> Int (lambda ((x Int)) Int (block (return (+ x 1))))) (print (call f 41)))(ক) শেষ token
)লাইন ৩-এর column 8-এ, তাই ঠিক পরের ঘর 3:9; সামনেEOF, কিন্তু অবস্থান আগের token থেকে। (খ)stock + 1পুরো পড়া হয়, তারপর=(column 11) দেখে যাচাই: বাঁ পাশBinary,Varনয়, তাই error সেই=-এ। (গ) annotation একটি function type, তাই(let f (Int) -> Int …); ডান পাশে নামহীন function, যাfunction_restদিয়েই পড়া। এটি parse-এর পরে চালালেও (haat.py run) ঠিকঠাক চলে আর42ছাপে। -
প্রমাণ — parser সবসময় থামে, আর সময় রৈখিক: দেখান যে পাতার parser (প্রথম error-এ থামা রূপ) n-টি token-এর যেকোনো ইনপুটে থামে, আর
statement()সর্বোচ্চ n বার ডাকা হয়। ধরে নিনexpression()প্রতিবার অন্তত একটি token খায় বা error দেয় (পর্ব ৪৮-এ এটি দেখবেন)।প্রমাণের রূপরেখা:
- দাবি A:
statement()-এর প্রতিটি সফল ডাক অন্তত একটি token খায়। প্রতিটি শাখা দেখুন:LET/VAR,IF,WHILE,RETURN,PRINTআরFN+IDENTশাখা শুরুতেই keyword খায় (advance);LBRACEশাখাexpect("LBRACE")-এ{খায়; বাকি সবexpr_or_assign-এ যায়, যাexpression()ডাকে, আর অনুমান অনুযায়ী সেটি অন্তত একটি token খায় বা error দেয়। - দাবি B:
statements_until-এর loop-এর প্রতিটি পাক অন্তত একটি token এগোয়, কারণ প্রতিটি পাকে একটিstatement()ডাক (দাবি A).EOFকখনো খাওয়া হয় না, আর loopEOF-এ থামে। - গণনা: token-অবস্থান
posকখনো কমে না, আর ০ থেকে n-এর মধ্যে থাকে। প্রতিটিstatement()ডাক তাকে অন্তত ১ বাড়ায় (বা error-এ পুরো parse থেমে যায়)। তাই সব মিলিয়েstatement()-এর ডাক ≤ n, আর প্রতিটি loop সসীম বার ঘোরে। - সময়: প্রতিটি method নিজের token ছাড়া স্থির পরিমাণ কাজ করে, আর method-ডাকের মোট সংখ্যা token-সংখ্যার একটি ধ্রুবক গুণিতকের মধ্যে থাকে (প্রতিটি ডাক হয় একটি token খায়, নয়তো এমন একটি ডাকের ঠিক ভেতরে যা খায়, আর এক token-এ অল্প কয়েকটি ডাক জমে), তাই মোট সময় O(n). ∎
সত্যিকারের সংখ্যা দিয়ে মেলান:
bazar.haat-এ ১৩০টি token (EOF-সহ; reference-এরtokens-ও ১৩০ লাইন)। ল্যাবে method-ডাক গুনে:statement()১৮ বার (≤ ১৩০),expression()৩৩ বার, আর এগারোটি parse method মিলিয়ে মোট ৮২টি ডাক। প্রমাণটি left recursion কেন নিষেধ তাও দেখায়:stmts → stmts stmtসরাসরি লিখলে দাবি A ভেঙে যেত, কারণ প্রথম ডাক কিছু না খেয়েই নিজেকে ডাকত। - দাবি A:
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমHaat-এর recursive descent parser let x: Int = 5; পড়ার সময় যে কাজগুলো করে, সেগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
statement()সামনেLETদেখেlet_decl()ডাকেletখাওয়া হয়, mutable = falseexpect("IDENT")নামxখায়match("COLON")সফল,parse_type()পড়েIntexpect("EQ"), তারপরexpression()পড়ে5expect("SEMI"), তারপরLetnode তৈরি হয়
Haat-এর statement parser একটি statement-এর শুরুতে fn দেখল। fn price(qty: Int) -> Int { … } (ঘোষণা) আর fn(x: Int) { print(x); }(5); (নামহীন function ডাকা) আলাদা করতে তাকে কী দেখতে হয়?
- শুধু প্রথম token
fn - দ্বিতীয় token: নাম হলে ঘোষণা,
(হলে expression - পুরো body পড়ে শেষে
(5)আছে কি না - Symbol table-এ
priceআগে ঘোষিত কি না
Haat-এ var stock = 5; লাইনের পরের লাইনে stock + 1 = 5; লেখা হলো। Reference parser কী করে?
- এটিকে
stock = 4হিসেবে মেনে নেয় - প্রথম token
stock-এexpected statementerror দেয় - পুরো
stock + 1পড়ে, তারপর=-এর ঘরেinvalid assignment targetদেয় - Parse হয়ে যায়, পরে type checker আপত্তি করে
তিন লাইনের Haat ফাইল: fn half(n: Int) -> Int { / return n / 2 (লাইন ২, 2 আছে column 16-এ) / }. Error কোথায় জানানো হয়?
- 2:17,
2-এর ঠিক পরে - 3:1,
}-এর ঘরে - 2:5,
return-এর ঘরে - 1:4, function-এর নামে
একজন EBNF নিয়ম stmts = stmts stmt | ε সরাসরি recursive descent-এ লিখলেন: def stmts(): stmts(); stmt(). কী ঘটবে?
- Statement-গুলো উল্টো ক্রমে পড়া হবে
- শুধু প্রথম statement পড়া হবে
- সব ঠিক চলবে, কারণ ε থামার শর্ত দেয়
- কোনো token না খেয়েই নিজেকে ডাকতে থাকবে, শেষে stack overflow
Haat reference-এর AST-এ if a { … } else if b { … } else { … } কীভাবে থাকে?
- একটি
Ifnode, যারelifsতালিকায় দ্বিতীয় শর্ত - বাইরের
If-এরelse_ঘরে আরেকটিIf, যারelse_একটিBlock - বাইরের
If-এরelse_একটিBlock, যার ভেতরে একটিIfstatement - শর্ত দুটি
a || bহিসেবে একটিIf-এ
Haat-এ let p: (Int) = 5; লিখলে reference parser-এর error কোনটি?
- 1:8: unknown type '(Int)'
- কোনো error নেই,
(Int)মানেInt - 1:14: expected '->' in function type
- 1:17: expected ';' after variable declaration
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Grammar = কোডের নকশা: nonterminal → method, terminal →
expect,{ }→while,[ ]→match; left recursion নয়, loop. - সিদ্ধান্ত lookahead-এ: প্রায় সব statement প্রথম token-এ চেনা যায়;
fn-এ দুই token; assignment-এ “পড়ে পরে যাচাই” (decision 9). - Type-ও parse হয়:
Int Bool Str Unitসাধারণ নাম (decision 6);(Int, Int) -> Intবন্ধনী আর->দিয়ে (decision 7);function_restঘোষণা আর নামহীন function দুটিরই। - অবস্থান আর বার্তা: প্রতিটি node-এ নির্দিষ্ট token-এর line:col; হারানো
;আগের token-এর পরে (decision 24); বার্তায় “কী, কিসের পরে”। - যাচাই: reference-এর সঙ্গে differential test, fuzzing আর হাতে লেখা edge case মিলিয়ে; গভীর nesting-এর জন্য একটি সীমা রাখুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৮ · Pratt parsing — expression-এর precedence আর associativityপরবর্তী পর্বbinding power, prefix/infix handler আর call-শৃঙ্খল, reference-এর সঙ্গে মিলিয়ে।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্ব১৪টি মডিউলের পুরো মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ৪৫ · Compiler-এর front end — Haat ভাষার পরিচয় আর নকশাআগের ধাপspec, front end-এর মানচিত্র, হাতে লেখা parser বনাম generator.
- গণনার তত্ত্ব · পর্ব ৩৮ · Top-down parsing — LL(1), FIRST আর FOLLOWতত্ত্বকোন grammar-এ backtracking ছাড়া recursive descent চলে, প্রমাণসহ।
- Software Testing & QA · পর্ব ৬০ · Fuzz testingপাশের ট্র্যাকgrammar-based আর mutation fuzzing বিস্তারিত।
- DSA · পর্ব ০৭ · Recursionভিত্তিcall stack আর recursion-এর গভীরতা।