এই পর্বে যা শিখবেন
- EBNF পড়া-লেখা, আর যেকোনো EBNF grammar-কে সমতুল্য CFG-তে অনুবাদের প্রমাণ
- Operator table থেকে Pratt parser বানানো, আর তার গাছ স্তরভাগ করা grammar-এর সঙ্গে মেলানো
- Lexer আর parser-এর মধ্যে কাজ ভাগ, আর conflict-হীন grammar লেখার কৌশল
- Panic mode, error production আর expected-token set দিয়ে error recovery ও ভালো বার্তা
- Round-trip test, grammar-based fuzzing আর version বদলের সময় backward compatibility যাচাই
১ · ভালো grammar কী — শুধু “ঠিক language” যথেষ্ট নয়
মডিউল ৫ থেকে আপনি জানেন, একটি context-free grammar একটি language বর্ণনা করে। কিন্তু একই language-এর অসংখ্য grammar আছে, আর বাস্তবে তাদের মধ্যে তফাত বিশাল। পর্ব ৩৮, ৩৯ আর ৪১-এ দেখেছেন, কোনো grammar LL(1) parser-এ চলে, কোনোটি শুধু LALR-এ, কোনোটির জন্য Earley লাগে। এই পর্বের প্রশ্ন উল্টো দিক থেকে: আপনি যখন নিজে একটি ভাষা বানাচ্ছেন, যেমন বাজারঘরের admin panel-এর order-query ভাষা, তখন grammar কীভাবে লিখবেন, যাতে সেটি পড়তে সহজ, parser-এ ঝামেলাহীন, ব্যবহারকারীর কাছে ক্ষমাশীল আর ভবিষ্যতে বাড়ানো যায়?
রেলের টিকিট কাউন্টারের ফর্মের কথা ভাবুন। ফর্মটি “ঠিক তথ্য নেয়” কি না, সেটি প্রথম শর্ত মাত্র। ভালো ফর্মে ঘরগুলো এমনভাবে সাজানো যে কেউ ভুল বুঝে “যাত্রার তারিখ”-এর ঘরে জন্মতারিখ লেখেন না; ভুল হলে কাউন্টারের লোক বলেন ঠিক কোন ঘরে কী ভুল; আর পরের বছর নতুন ঘর (যেমন আসন-পছন্দ) যোগ হলে পুরোনো পূরণ করা ফর্ম বাতিল হয়ে যায় না। Grammar হলো একটি ভাষার ফর্ম; তার নকশাতেও ঠিক এই তিন গুণ লাগে।
একটি DSL (domain-specific language, নির্দিষ্ট কাজের ছোট ভাষা) বা programming language-এর grammar-এর কাছে আমরা সাতটি জিনিস চাই। প্রথম চারটি তত্ত্বের, শেষ তিনটি প্রকৌশলের:
- সঠিক language: যা লিখতে দেওয়ার কথা তা-ই গ্রহণ, বাকি সব বর্জন।
- Unambiguous: প্রতিটি string-এর ঠিক একটি parse tree (পর্ব ২৭)।
- ঠিক গাছ: সেই একমাত্র গাছটি মানুষের প্রত্যাশিত অর্থ দেয়: precedence আর associativity মানুষের অভ্যাস মেনে।
- Parser-বান্ধব: বেছে নেওয়া parsing পদ্ধতিতে (LL(1), LALR(1) বা Pratt) conflict ছাড়া চলে।
- ভালো error: ভুল input-এ অবস্থান আর প্রত্যাশিত token-সহ বার্তা, আর সম্ভব হলে একবারে একাধিক ভুল ধরা।
- যাচাইযোগ্য: grammar নিজেই test-input তৈরির ছাঁচ হিসেবে কাজে লাগে।
- বিবর্তনযোগ্য: নতুন version পুরোনো বৈধ লেখার অর্থ বদলায় না।
এই পর্বের পুরো যাত্রা একটি বাস্তব কাজ: বাজারঘরের order-query ভাষার version 2 নকশা করা। পর্ব ২৫-এর v1-এ ছিল FIND order WHERE, তারপর AND, OR আর বন্ধনী দিয়ে জোড়া তুলনা। পর্ব ৪০-এ সেই v1-কে Lark দিয়ে একটি পূর্ণ interpreter বানানো হয়েছে। এবার ব্যবসার দল তিনটি নতুন সুবিধা চেয়েছে: NOT, তালিকার সদস্যপদ (district IN ("Dhaka", "Khulna")), আর সব রকম তুলনা (!=, <=, >). ধাপে ধাপে দেখবেন, প্রতিটি সুবিধা grammar-এর কোন সিদ্ধান্ত দাবি করে, আর কোন ভুলটি কোন পরীক্ষায় ধরা পড়ে।
২ · EBNF — পুনরাবৃত্তি, ঐচ্ছিক অংশ আর CFG-এ অনুবাদ
বাস্তব ভাষার মানক দলিলে grammar প্রায় সবসময় EBNF-এ লেখা হয়, শুদ্ধ BNF-এ নয়। EBNF-এ তিনটি অতিরিক্ত গঠন: { X } মানে X শূন্য বা বেশিবার, [ X ] মানে X থাকতেও পারে না-ও পারে, আর ( X ∣ Y ) মানে বন্ধনীর ভেতরে বিকল্প। Lark আর অনেক tool একই ধারণা regex-এর চিহ্নে লেখে: X∗, X?, X+. যেমন IN-তালিকা:
BNF-এ একই জিনিস লিখতে একটি নতুন variable লাগে: list → ( STR R ), R → , STR R ∣ ε. EBNF তাই একটি সুবিধা: মানুষ “একটি বা বেশি, কমা দিয়ে আলাদা” সরাসরি পড়তে পারেন। প্রশ্ন হলো, এই সুবিধা কি language-এর শক্তি বাড়ায়? না।
প্রতিটি EBNF grammar G-এর জন্য একটি সাধারণ CFG G′ আছে যাতে L(G′) = L(G). অনুবাদটি যান্ত্রিক, আর G′-এর আকার G-এর আকারের রৈখিক গুণিতক।
প্রমাণের রূপরেখা:
- নিয়মের ডান দিকে সবচেয়ে ভেতরের একটি EBNF গঠন বাছুন, অর্থাৎ যার ভেতরে আর কোনো {·}, [·] বা (·∣·) নেই। — ভেতর থেকে বাইরে
- { X }-এর জায়গায় একটি নতুন variable R বসান আর দুটি নিয়ম যোগ করুন: R → X R ∣ ε. R থেকে ঠিক L(X)∗ আসে (অনুশীলন ২-এ এর পূর্ণ প্রমাণ)। — পুনরাবৃত্তি = recursion
- [ X ]-এর জায়গায় নতুন O, সঙ্গে O → X ∣ ε; ( X ∣ Y )-এর জায়গায় নতুন A, সঙ্গে A → X ∣ Y. — ঐচ্ছিক আর বিকল্প
- প্রতিটি প্রতিস্থাপন একটি গঠন কমায় আর language বদলায় না, কারণ নতুন variable থেকে আসা string-এর সেট ঠিক পুরোনো গঠনের সেট। তাই গঠনের সংখ্যার ওপর induction-এ সব গঠন সরে যায়। প্রতিটি গঠনে ধ্রুবক সংখ্যক নতুন নিয়ম, তাই আকার রৈখিক। ∎
অনুবাদের একটি সূক্ষ্ম দিক নকশার জন্য গুরুত্বপূর্ণ। E = T { "+" T } লেখাটি language বলে দেয়, কিন্তু associativity বলে না: T + T + T-এ কোন যোগ আগে, EBNF নীরব। R → X R অনুবাদটি গাছকে ডান দিকে ঝোঁকায়, R → R X বাঁ দিকে। বাস্তব parser এই নীরবতার সুযোগ নেয়: recursive descent parser { … }-কে একটি while-loop বানায়, আর loop-এর ভেতরে গাছ বাঁ দিকে গড়ে, তাই left recursion ছাড়াই বাম-সংযোগ পাওয়া যায় (অংশ ৩-এর দ্বিতীয় ব্লক ঠিক এটি করে)। শিক্ষা: EBNF-এ grammar লিখলে associativity আলাদা করে, কথায় বা operator table-এ, লিখে রাখতে হয়।
EBNF-এর পরিচিত ফাঁদ: { X }-এর ভেতরের X যদি নিজেই ε তৈরি করতে পারে, যেমন { [ "," ] STR }, তাহলে একই লেখা অনেকভাবে ভাগ করা যায়, অর্থাৎ ambiguity; আর কিছু সরল tool এমন loop-এ এক জায়গায় আটকে যায়। নিয়ম: পুনরাবৃত্তির ভেতরের অংশ অন্তত একটি token খরচ করবে।
৩ · Operator table আর Pratt parsing
পর্ব ২৭-এ precedence বাঁধার একটি উপায় শিখেছেন: প্রতিটি precedence-স্তরের জন্য একটি variable (E, T, F). দশটি স্তরের একটি ভাষায় এর মানে দশটি variable, আর প্রতিটি সংখ্যা পড়তে দশটি একক-সন্তানের ধাপ। Vaughan Pratt ১৯৭৩ সালের “Top Down Operator Precedence” প্রবন্ধে একটি বিকল্প দেন, যা এখন অনেক হাতে লেখা parser-এর ভিত্তি: grammar-এর স্তর বাদ দিয়ে একটি ছোট টেবিল, যেখানে প্রতিটি operator-এর দুটি সংখ্যা। একই ধারণার একটি রূপ “precedence climbing” নামে পরিচিত (Keith Clarke-এর ১৯৮৬ সালের কাজের সঙ্গে সাধারণত যুক্ত করা হয়); দুটিকে অনেকে মূলত একই algorithm মনে করেন।
প্রতিটি infix operator ⊕-এর একজোড়া স্বাভাবিক সংখ্যা (l⊕, r⊕): বাঁ আর ডান binding power. Pratt parser-এর মূল function expr(m) একটি operand পড়ে, তারপর যতক্ষণ পরের operator ⊕-এর l⊕ ≥ m, ততক্ষণ ⊕ খায় আর ডান operand হিসেবে expr(r⊕) ডাকে। পুরো input-এর জন্য expr(0).
শর্তগুলো: l⊕ < r⊕ হলে ⊕ বাম-সংযোগ, l⊕ > r⊕ হলে ডান-সংযোগ; আর বেশি precedence-এর operator-এর দুটি সংখ্যাই কম precedence-এর operator-এর দুটি সংখ্যার চেয়ে বড়।
| Operator | Precedence | Associativity | (l, r) |
|---|---|---|---|
| + − | সবচেয়ে কম | বাম | (10, 11) |
| ∗ / | মাঝারি | বাম | (20, 21) |
| ^ | সবচেয়ে বেশি | ডান | (31, 30) |
সংখ্যাগুলো কেন কাজ করে? ধরুন বাঁ দিকে একটি operand বসে আছে, আর তার দুই পাশে দুটি operator. দুই পাশের operator যেন দড়ি টানাটানি করছে: বাঁয়েরটি তার ডান binding power দিয়ে, ডানেরটি তার বাঁ binding power দিয়ে। যে বেশি জোরে টানে, operand তার সন্তান হয়। 8−4−2-এ মাঝের 4-কে বাঁয়ের − টানে 11 জোরে, ডানের − টানে 10 জোরে, তাই 4 বাঁয়ের −-এর: (8−4)−2. 2^3^2-এ মাঝের 3-কে বাঁয়ের ^ টানে 30, ডানের ^ টানে 31, তাই 3 ডানের: 2^(3^2). সমান সংখ্যা দিলে টানাটানি অমীমাংসিত থাকত, তাই একটি ১ বেশি।
1+ − : (10, 11)2∗ / : (20, 21)3^ : (31, 30)4l ≥ min → নেওয়া, ডানে min = r5l < min বা শেষ → থামা
| operand, পরের op | |
| তুলনা | |
| গাছ |
- শুরু। expr(0) প্রথম operand 2 পড়ে, পরে দেখে +. l+ = 10 ≥ 0, তাই + নেয় আর ডান operand-এর জন্য expr(11) ডাকে। গাছের এখনো ডান দিক ফাঁকা (□)।
- গুণ। expr(11) পড়ে 3, পরে ∗. l∗ = 20 ≥ 11: গুণ যোগের চেয়ে শক্ত, তাই 3 গুণের বাঁ operand হয়, যোগের নয়। ডানে expr(21).
- ঘাত। expr(21) পড়ে 4, পরে ^. 31 ≥ 21, তাই 4 ঘাতের ভিত্তি। ডানে expr(30), কারণ r^ = 30.
- ডান-সংযোগ। expr(30) পড়ে 2, পরে আবার ^. 31 ≥ 30, তাই এই দ্বিতীয় ^-ও নেওয়া হয়, ভেতরের ডাকেই। ^-এর টেবিল (31, 30) না হয়ে (30, 31) হলে 30 ≥ 31 মিথ্যা হতো, ডাকটি থামত, আর গাছ হতো (4^2)^1.
- থামা। সবচেয়ে ভেতরের expr(30) পড়ে 1, পরে input-এর শেষ ($)। শেষের কোনো binding power নেই, তাই loop থামে আর 1 ফেরত যায়।
- ফেরা। প্রতিটি ডাক তার গাছ সম্পূর্ণ করে ফেরে: 2^1 = 2, 4^2 = 16, 3∗16 = 48, 2+48 = 50. একটিই গাছ, আর সেটি গণিতের প্রচলিত অর্থ।
2+3∗4^2^1-এর গাছ আর binding power
ওপরে token-এর সারি, প্রতিটি operator-এর নিচে (l, r). নিচে Pratt parser-এর বানানো গাছ: যত শক্ত operator, তত নিচে।
নিচের ব্লকে পুরো Pratt parser, প্রায় ২০ লাইনে। trace=True দিলে প্রতিটি তুলনা ছাপে, ভেতরের ডাক ডানে সরে।
import re
# Pratt parser: operator -> (left bp, right bp). left < right: left-assoc.
BP = {"+": (10, 11), "-": (10, 11), "*": (20, 21), "/": (20, 21),
"^": (31, 30)}
OPS = {"+": int.__add__, "-": int.__sub__, "*": int.__mul__,
"/": int.__floordiv__, "^": int.__pow__}
def parse(text, trace=False):
toks = re.findall(r"\d+|[-+*/^()]", text) + ["$"]
pos = 0
def expr(min_bp, d):
nonlocal pos
t = toks[pos]; pos += 1
left = expr(0, d + 1) if t == "(" else int(t)
pos += t == "(" # skip ")"
while toks[pos] in BP:
lbp, rbp = BP[toks[pos]]
if trace:
print(f"{' ' * d}left={show(left)[0]} sees {toks[pos]}: "
f"lbp {lbp} {'>=' if lbp >= min_bp else '<'} {min_bp}")
if lbp < min_bp:
break
op = toks[pos]; pos += 1
left = (op, left, expr(rbp, d + 1))
return left
return expr(0, 0)
def show(t): # (fully bracketed text, value)
if isinstance(t, int):
return str(t), t
(a, x), (b, y) = show(t[1]), show(t[2])
return f"({a}{t[0]}{b})", OPS[t[0]](x, y)
for s in ["2+3*4^2^1", "2*3-4-1"]:
print(s, "->", *show(parse(s, trace=True)))
for s in ["8-4-2", "2^3^2", "(2+3)*4"]:
print(f"{s:8} ->", *show(parse(s)))আসল আউটপুট (ব্রাউজারের Python):
left=2 sees +: lbp 10 >= 0
left=3 sees *: lbp 20 >= 11
left=4 sees ^: lbp 31 >= 21
left=2 sees ^: lbp 31 >= 30
2+3*4^2^1 -> (2+(3*(4^(2^1)))) 50
left=2 sees *: lbp 20 >= 0
left=3 sees -: lbp 10 < 21
left=(2*3) sees -: lbp 10 >= 0
left=4 sees -: lbp 10 < 11
left=((2*3)-4) sees -: lbp 10 >= 0
2*3-4-1 -> (((2*3)-4)-1) 1
8-4-2 -> ((8-4)-2) 2
2^3^2 -> (2^(3^2)) 512
(2+3)*4 -> ((2+3)*4) 20
প্রথম চার লাইন ঠিক ওপরের stepper. দ্বিতীয় উদাহরণে “থামা” দেখুন: expr(21) 3 পড়ে − দেখে, 10 < 21, তাই থামে আর 3 ফেরত দেয়; − তখন বাইরের loop-এ (min 0) ধরা পড়ে, বাঁ operand এখন পুরো (2∗3). এভাবে প্রতিটি − বাঁয়ের সবকিছুকে নিজের বাঁ সন্তান বানায়: বাম-সংযোগ। বন্ধনী শুধু expr(0) নতুন করে ডাকে, তাই তার ভেতরে সব টেবিল আবার শূন্য থেকে শুরু। পুরো parser-এ grammar-এর কোনো স্তর নেই; precedence আর associativity সব টেবিলের ছয়টি সংখ্যায়।
কিন্তু দাবিটি কি সত্যিই ঠিক, যে এই টেবিল পর্ব ২৭-এর স্তরভাগ করা grammar-এর একই গাছ দেয়? এখানে একটি প্রমাণের রূপরেখা আর একটি গণনা-পরীক্ষা দুটিই দেখা যাক। প্রমাণের রূপরেখা: স্তরভাগ করা grammar-এর প্রতিটি স্তর Lk = “precedence ≥ k-এর operator দিয়ে জোড়া operand-এর সারি”। Pratt-এর expr(m) ঠিক সেই সারিটি পড়ে যার প্রতিটি operator-এর l ≥ m, আর থামে প্রথম দুর্বলতর operator-এ। বাম-সংযোগের জন্য r = l + 1 নিশ্চিত করে যে একই স্তরের পরের operator ভেতরের ডাকে ধরা পড়বে না, বাইরের loop-এ পড়বে; ডান-সংযোগে r = l − 1 ঠিক উল্টোটা করে। Input-এর দৈর্ঘ্যের ওপর induction-এ প্রতিটি ডাকের ফেরত গাছ grammar-এর সংশ্লিষ্ট স্তরের গাছ। নিচের ব্লক এই দাবিকে কম্পিউটারে যাচাই করে: 2 আর 3 অঙ্ক, পাঁচটি operator আর ০ থেকে ৪টি operator-এর সব expression.
from itertools import product
# Layered EBNF, one loop per { }: E = T {(+|-) T} T = P {(*|/) P} P = F [^ P]
def layered(s):
toks, pos = list(s) + ["$"], 0
def level(ops, sub): # X = sub { op sub }
nonlocal pos
left = sub()
while toks[pos] in ops:
op = toks[pos]; pos += 1
left = (op, left, sub())
return left
def P(): # right recursion
nonlocal pos
base = int(toks[pos]); pos += 1
if toks[pos] != "^":
return base
pos += 1; return ("^", base, P())
return level("+-", lambda: level("*/", P))
def differ(): # all strings, 0..4 operators
total, bad = 0, []
for k in range(5):
for nums in product("23", repeat=k + 1):
for ops in product("+-*/^", repeat=k):
s = nums[0] + "".join(o + n for o, n in zip(ops, nums[1:]))
total += 1
bad += [s] if parse(s) != layered(s) else []
return total, bad
BP["^"] = (31, 30) # the correct table
total, bad = differ()
print(f"correct table : {total} expressions, {len(bad)} trees differ")
BP["^"] = (30, 31) # mistake: ^ left-assoc
total, bad = differ()
print(f"^ as (30, 31) : {total} expressions, {len(bad)} differ, e.g. {bad[0]}")
print(" Pratt :", show(parse(bad[0]))[0], " layered:", show(layered(bad[0]))[0])আসল আউটপুট (ব্রাউজারের Python):
correct table : 22222 expressions, 0 trees differ
^ as (30, 31) : 22222 expressions, 2232 differ, e.g. 2^2^2
Pratt : ((2^2)^2) layered: (2^(2^2))
মোট expression 2 + 20 + 200 + 2000 + 20000 = 22222, আর সঠিক টেবিলে একটিরও গাছ আলাদা নয়। টেবিলে একটিমাত্র অঙ্ক উল্টে দিলে (^ = (30, 31)) ২২৩২টি expression-এ গাছ বদলে যায়, সবচেয়ে ছোট সাক্ষী 2^2^2: Pratt বলে (2^2)^2 = 16, grammar বলে 2^(2^2) = 16. মজার ব্যাপার, এই সাক্ষীতে দুটি মান কাকতালীয়ভাবে সমান, কিন্তু গাছ আলাদা; 2^3^2-এ মান 64 বনাম 512. তাই পরীক্ষা মান নয়, গাছ তুলনা করে। লক্ষ করুন, layered-এ EBNF-এর প্রতিটি { } একটি while-loop, আর [ "^" P ] একটি if, যেখানে ডান-recursion ডান-সংযোগ দেয়: অংশ ২-এর কথাটি কোডে। (এই পরীক্ষা ৪টি operator পর্যন্ত; সব দৈর্ঘ্যের জন্য নিশ্চয়তা আসে প্রমাণ থেকে।)
Pratt-এর আরও সুবিধা: prefix operator (যেমন একক −, NOT) আর postfix operator একই কাঠামোয় বসে, শুধু টেবিলে একটি করে সংখ্যা; ব্যবহারকারী নিজের operator যোগ করতে পারে এমন ভাষায় টেবিলটি চলার সময়েও বাড়ানো যায়। অসুবিধা: grammar আর কাগজে লেখা থাকে না, থাকে কোডে আর টেবিলে; তাই মানক দলিলের জন্য অনেক দল এখনো স্তরভাগ করা EBNF রাখে আর বাস্তব parser-এ Pratt চালায়, তারপর দুটিকে ওপরের মতো পরীক্ষায় মেলায়।
৪ · Lexer-parser সীমানা আর conflict এড়ানো
পর্ব ২২-এ দেখেছেন, lexer regular অংশ (নাম, সংখ্যা, উদ্ধৃতির লেখা, তুলনার চিহ্ন) সামলায়, আর parser নেস্টিং-এর অংশ। Grammar নকশায় এই সীমানা প্রথম সিদ্ধান্ত। চারটি নিয়ম কাজে আসে:
- যা regular, তা lexer-এ: সংখ্যা
[0-9]+একটি token; grammar-এ “অঙ্ক তারপর অঙ্কের সারি” নিয়ম লিখলে parser অকারণে ভারী হয়, আর ফাঁকা ঘর কোথায় বসতে পারে তা প্রতিটি নিয়মে বলতে হয়। - যা নেস্ট করে, তা parser-এ: বন্ধনী মেলানো কোনো regex পারে না (পর্ব ১৭)।
- Token-এর ধরন অর্থ দেখে নয়, আকার দেখে: “Dhaka” বৈধ জেলা কি না, সেটি lexer বা grammar-এর কাজ নয়; পরের যাচাই-ধাপের। Grammar-কে type-checker বানালে সেটি context-sensitive হওয়ার দিকে ঠেলে দেয়।
- Keyword কম রাখুন: প্রতিটি নতুন keyword একটি নাম কেড়ে নেয়। অংশ ৮-এ দেখবেন, version বদলের সময় এটিই সবচেয়ে পরিচিত ভাঙন।
এবার conflict. পর্ব ৩৯-এ দেখেছেন, LALR parser generator grammar-এর table বানাতে গিয়ে কোনো ঘরে দুটি কাজ পেলে shift/reduce conflict হয়। yacc আর Bison সতর্কবার্তা দেয়। কিন্তু সব tool সমান সোচ্চার নয়। বাজারঘরের দল v2-এর জন্য প্রথমে দুটি খসড়া লিখেছিল: খসড়া A-তে সব operator একটি স্তরে, খসড়া B-তে পর্ব ২৭-এর স্তর আছে, কিন্তু NOT-এর পরে পুরো cond. তৃতীয়টি চূড়ান্ত v2 (অংশ ৫)। তিনটিকেই lark-এর LALR দিয়ে চালানো হলো, একই query-তে। নিচের project ডেস্কটপে uv দিয়ে বানানো।
import logging
from pathlib import Path
from lark import Lark, logger
class Count(logging.Handler): # lark reports S/R conflicts
n = 0 # only as DEBUG log lines
def emit(self, r):
Count.n += "conflict" in r.getMessage()
logger.addHandler(Count()); logger.setLevel(logging.DEBUG)
TAIL = r'''
?atom: "(" cond ")" | "amount" ">" NUM -> num_cmp | "status" "=" STR -> text_cmp
NUM: /[0-9]+/
STR: /"[^"\n]*"/
%ignore " "
'''
HEAD = 'start: "FIND" "order" "WHERE" cond\n'
grammars = {
"draft A": HEAD + '?cond: cond "AND" cond -> and_ | cond "OR" cond -> or_'
' | "NOT" cond -> not_ | atom' + TAIL,
"draft B": HEAD + '?cond: cond "OR" term -> or_ | term\n'
'?term: term "AND" neg -> and_ | neg\n'
'?neg: "NOT" cond -> not_ | atom' + TAIL,
"v2": Path("query_v2.lark").read_text(),
}
q = 'FIND order WHERE NOT status = "new" OR amount > 5'
for name, g in grammars.items():
Count.n = 0
p = Lark(g, parser="lalr")
t = p.parse(q).children[0]
print(f"{name}: {Count.n} shift/reduce conflicts (silently 'shift')")
print(" root:", t.data, "| children:", [c.data for c in t.children])সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13; lark-এর নিজের DEBUG বার্তাগুলো এখানে বাদ):
~/bazarghar-toc$ uv run python draft_conflict.py
draft A: 6 shift/reduce conflicts (silently 'shift')
root: not_ | children: ['or_']
draft B: 3 shift/reduce conflicts (silently 'shift')
root: not_ | children: ['or_']
v2: 0 shift/reduce conflicts (silently 'shift')
root: or_ | children: ['not_', 'num_cmp']
পর্ব ৩৯ আর ৪০-এ দেখেছেন, lark-এর LALR shift/reduce conflict পেলে কোনো ত্রুটি দেয় না; নিজের logger-এ শুধু DEBUG স্তরে একটি লাইন লেখে (“resolving as shift”), যা ডিফল্টে চোখেই পড়ে না। খসড়া A-তে ৬টি, B-তে ৩টি conflict, আর দুটিতেই “shift” নিয়ম NOT-কে যতদূর সম্ভব ডানে প্রসারিত করেছে: NOT status = "new" OR amount > 5 পড়া হয়েছে NOT (status = "new" OR amount > 5) হিসেবে, যা SQL-অভ্যস্ত যেকোনো কর্মীর প্রত্যাশার উল্টো। চূড়ান্ত v2-এ conflict ০, আর একই query-র মূলে OR, বাঁ সন্তানে NOT: (NOT status = "new") OR amount > 5. শিক্ষা: grammar-এর conflict-সংখ্যা test-এ assert করুন, শুধু “parser তো চলছে” দেখে নিশ্চিন্ত হবেন না।
Conflict এড়ানোর নকশা-নিয়ম, পর্ব ৩৮–৩৯-এর তত্ত্ব থেকে সংক্ষেপে: (১) প্রতিটি precedence-স্তরে একটি variable, বা precedence declaration, কিন্তু দুটি মিশিয়ে নয়; (২) prefix operator (NOT)-এর operand তার নিজের স্তর বা তার নিচের স্তর, কখনো পুরো expression নয়, নইলে খসড়া B-র ভুল; (৩) একই শুরুর token দিয়ে দুটি বিকল্প শুরু হলে LL parser-এর জন্য left factoring, LR-এর জন্য সাধারণত সমস্যা নেই; (৪) “শেষ” বোঝাতে স্পষ্ট চিহ্ন (বন্ধনী, END, বা ;) dangling-else ধরনের সমস্যা গঠনগতভাবেই দূর করে।
৫ · বাজারঘর query v2 — উদাহরণ থেকে grammar
Grammar কখনো শূন্য থেকে লেখা হয় না; শুরু হয় উদাহরণ থেকে। দল প্রথমে বৈধ আর অবৈধ query-র দুটি তালিকা বানায়, প্রতিটি বৈধ query-র পাশে তার প্রত্যাশিত অর্থ বন্ধনী দিয়ে লেখা থাকে। এই তালিকা পরে test-এর ভিত্তি হয়। নিচের stepper সেই উদাহরণ থেকে চূড়ান্ত grammar পর্যন্ত যায়।
1C → C OR T ∣ T2T → T AND N ∣ N3N → NOT N ∣ A4A → ( C ) ∣ amount R NUM5A → F E STR6A → amount IN ( NUM {, NUM} )7A → F IN ( STR {, STR} )
| প্রশ্ন | |
| উত্তর |
- উদাহরণ। বৈধ: NOT district = "Dhaka" AND amount > 500 অর্থ (NOT …) AND …; district IN ("Dhaka", "Khulna"); NOT (amount IN (100, 200) OR status = "paid"). অবৈধ: খালি তালিকা IN (), শেষে কমা, অমিল বন্ধনী, উদ্ধৃতিহীন জেলা।
- Operator table. SQL-এ অভ্যস্ত কর্মীরা NOT-কে AND-এর চেয়ে শক্ত, AND-কে OR-এর চেয়ে শক্ত ধরে নেন; ভাষাটি সেই অভ্যাস মানে। OR আর AND বাম-সংযোগ (অর্থে পার্থক্য নেই, কিন্তু গাছ নির্দিষ্ট থাকা চাই)।
- স্তর। প্রতিটি precedence-এর একটি variable: C (OR), T (AND), N (NOT). মূল সিদ্ধান্ত লাইন ৩: NOT-এর পরে N, পুরো C নয়। খসড়া B-র ৩টি conflict ঠিক এখানে ছিল।
- পরমাণু। A-তে বন্ধনী, তুলনা আর IN-তালিকা। তালিকা অন্তত একটি মান নেয় ({, NUM} মানে শূন্য বা বেশিবার “কমা আর মান”)। amount-এর তালিকায় শুধু সংখ্যা, district/status-এ শুধু উদ্ধৃতির লেখা: ধরন grammar-এই বাঁধা, কারণ এটি আকারের প্রশ্ন।
- Token. F মানে district বা status, R মানে ছয়টি তুলনা, E মানে = বা !=. নতুন keyword শুধু NOT আর IN. বাকি সব (জেলার নাম বৈধ কি না) পরের যাচাই-ধাপে।
- যাচাই। Lark-এর LALR table conflict ছাড়া তৈরি হলো, আর অংশ ৭-এর fuzzer-এ v1-এর ২০০০টি query v1 আর v2 দুই parser-এ একই AST দিল। অর্থাৎ v2 পুরোনো লেখার অর্থ বদলায়নি।
Lark-এর EBNF-এ চূড়ান্ত grammar ফাইল নিচে। ? একক-সন্তানের node মুছে দেয়, -> name node-এর নাম দেয়, আর ("," NUM)* হলো EBNF-এর { "," NUM }.
// bazarghar order-query language, version 2 (query_v2.lark)
start: "FIND" "order" "WHERE" cond
?cond: cond "OR" term -> or_
| term
?term: term "AND" neg -> and_
| neg
?neg: "NOT" neg -> not_
| atom
?atom: "(" cond ")"
| "amount" REL NUM -> num_cmp
| TEXT_FIELD EQ_OP STR -> text_cmp
| "amount" "IN" "(" NUM ("," NUM)* ")" -> num_in
| TEXT_FIELD "IN" "(" STR ("," STR)* ")" -> text_in
TEXT_FIELD: "district" | "status"
REL: ">=" | "<=" | "!=" | ">" | "<" | "="
EQ_OP: "=" | "!="
NUM: /[0-9]+/
STR: /"[^"\n]*"/
%ignore /[ \t\n]+/
একটি সূক্ষ্ম বিষয় লক্ষ করুন: REL আর EQ_OP দুটি token-ই “=” আর “!=” মেলায়। সাধারণ lexer-এ এটি সমস্যা (একই lexeme, দুটি token). Lark-এর LALR ডিফল্টে একটি “contextual lexer” চালায়, যা parser-এর বর্তমান state-এ যে token বৈধ শুধু সেগুলোই চেষ্টা করে: amount-এর পরে REL, district-এর পরে EQ_OP. এটি সুবিধাজনক, কিন্তু lexer-কে parser-এর state-এর ওপর নির্ভরশীল করে, যা পর্ব ২২-এর পরিষ্কার সীমানা একটু ঝাপসা করে। বিকল্প নকশা: একটি OP token আর grammar-এ “text field-এর পরে শুধু = বা !=”। তিনটি query-তে চালানো (v2_demo.py):
~/bazarghar-toc$ uv run python v2_demo.py
lark 1.3.1 | Python 3.12.13
LALR table built: no conflicts
FIND order WHERE NOT district = "Dhaka" AND amount > 500
start
and_
not_
text_cmp
district
=
"Dhaka"
num_cmp
>
500
…
FIND order WHERE NOT (amount IN (100, 200) OR status = "paid")
start
not_
or_
num_in
100
200
text_cmp
status
=
"paid"
প্রথম query-তে মূলে and_, আর NOT শুধু district-এর তুলনাকে ঢাকে: উদাহরণ-তালিকার প্রত্যাশিত অর্থ। তৃতীয়টিতে বন্ধনী NOT-কে পুরো OR-এর ওপর বসায়।
৬ · Error recovery আর ভালো error message
বাজারঘরের admin panel-এ প্রতিদিন যত query লেখা হয়, তার একটি অংশ ভুল: কমা বাদ, উদ্ধৃতি ভুলে যাওয়া, == লেখা। Parser-এর দুটি দায়িত্ব: ভুলের জায়গা আর কী প্রত্যাশিত ছিল জানানো, আর সম্ভব হলে বাকি input পড়ে আরও ভুল খোঁজা। প্রথমটির তাত্ত্বিক ভিত্তি expected-token set: parser যে অবস্থায় থেমেছে, সেখান থেকে কোন কোন token পড়লে এগোনো যেত। LL(1)-এ সেটি parsing table-এর ওই সারির ফাঁকা নয় এমন ঘরগুলো; LR-এ বর্তমান state-এর action-ঘরগুলো। একটি গুরুত্বপূর্ণ ধর্ম: LL আর LR parser-এর “correct prefix property” আছে, অর্থাৎ input-এর যে অংশ পর্যন্ত তারা এগোয়, সেটি কোনো বৈধ string-এর prefix; তাই ভুল ধরা পড়ে প্রথম অসম্ভব token-এই, পরে নয়।
from lark.exceptions import UnexpectedToken, UnexpectedCharacters
from qlib import P2 # the LALR parser of query_v2.lark
NICE = {"NUM": "a number", "STR": 'a "quoted text"', "TEXT_FIELD": "district/status",
"REL": "a comparison", "EQ_OP": "= or !=", "LPAR": "(", "RPAR": ")",
"COMMA": ",", "AND": "AND", "OR": "OR", "NOT": "NOT", "IN": "IN",
"AMOUNT": "amount", "$END": "end of query"}
def explain(q):
try:
P2.parse(q); return "ok"
except UnexpectedToken as e:
got = "end of query" if e.token.type == "$END" else repr(str(e.token))
want = sorted(NICE.get(t, t) for t in e.expected)
col = e.column if e.token.type != "$END" else len(q) + 1
return f"col {col}: found {got}, expected one of: {', '.join(want)}"
except UnexpectedCharacters as e:
return f"col {e.column}: unexpected character {q[e.pos_in_stream]!r}"
for q in ['FIND order WHERE amount >= AND district = "Dhaka"',
'FIND order WHERE district IN ("Dhaka", )',
'FIND order WHERE (amount > 500 OR status = "new"',
'FIND order WHERE district = Dhaka',
'FIND order WHERE status == "new"']:
print(q)
print(" ->", explain(q))সত্যিকারের run (lark 1.3.1):
~/bazarghar-toc$ uv run python errors_v2.py
FIND order WHERE amount >= AND district = "Dhaka"
-> col 28: found 'AND', expected one of: a number
FIND order WHERE district IN ("Dhaka", )
-> col 40: found ')', expected one of: a "quoted text"
FIND order WHERE (amount > 500 OR status = "new"
-> col 49: found end of query, expected one of: ), OR
FIND order WHERE district = Dhaka
-> col 29: unexpected character 'D'
FIND order WHERE status == "new"
-> col 26: found '=', expected one of: a "quoted text"
প্রথম দুটি বার্তা আদর্শ: কলাম, পাওয়া token আর প্রত্যাশিত token, ব্যবহারকারীর ভাষায় (lark-এর ভেতরের নাম NUM বা RPAR নয়, NICE টেবিলে অনুবাদ করা)। তৃতীয়টিতে একটি সত্যিকারের সীমাবদ্ধতা দেখা যাচ্ছে: শেষ বন্ধনী ভুলে যাওয়া জায়গায় ) আর OR প্রত্যাশিত বলা হয়েছে, কিন্তু AND-ও সেখানে বৈধ ছিল (… status = "new" AND …)। LALR parser ভুল ধরার আগে কিছু reduce সেরে ফেলে (T থেকে C), আর তখনকার state-এ AND আর নেই। তাই LALR-এর expected-set সবসময় সম্পূর্ণ নয়; যে tool পুরো সেট চায়, সে ভুলের আগের state থেকে হিসাব করে। চতুর্থটি lexer-এর ভুল (lexical error): উদ্ধৃতিহীন Dhaka কোনো token-এ পড়ে না। পঞ্চমটি একটি পরিচিত টাইপের ভুল, যার জন্য একটি বিশেষ নিয়ম বার্তাকে আরও সাহায্যকারী করতে পারে, নিচে দেখুন।
এবার recovery: একটি ভুলে থেমে না গিয়ে আরও ভুল খোঁজা। তিনটি প্রচলিত কৌশল:
- Panic mode: ভুল পেলে input-এর token ফেলে দিতে থাকা, যতক্ষণ না একটি synchronizing token আসে (যেমন ; বা statement-এর শেষ), তারপর সেখান থেকে নতুন করে শুরু। সরল, কখনো loop-এ আটকায় না, কিন্তু মাঝের ভুলগুলো হারায়।
- Error production: পরিচিত ভুলের জন্য grammar-এ ইচ্ছা করে একটি নিয়ম রাখা, যেমন == কে = হিসেবে পড়া, কিন্তু সঙ্গে একটি সতর্কবার্তা। yacc আর Bison-এ grammar-এর বিশেষ
errortoken একই পরিবারের কৌশল। - Phrase-level মেরামত: একটি token ঢোকানো, মোছা বা বদলানো যাতে parse চালিয়ে যাওয়া যায় (যেমন “এখানে ) বসিয়ে নিলাম”)। শক্তিশালী, কিন্তু ভুল মেরামত অপ্রত্যাশিত দ্বিতীয় ভুলের বার্তা তৈরি করতে পারে।
নিচের ব্লক একটি হাতে লেখা recursive descent parser, EBNF থেকে সরাসরি (প্রতিটি { } একটি loop). একসঙ্গে ; দিয়ে আলাদা পাঁচটি query পায়, panic mode-এ ; পর্যন্ত লাফ দেয়, আর == এর জন্য একটি error production রাখে।
import re
TOK = re.compile(r'\s*("[^"]*"|\d+|==|>=|<=|!=|[(),;=<>]|\w+)')
FIELDS, OPS = ["amount", "district", "status"], ["=", "!=", ">=", "<=", ">", "<"]
def check(text):
toks, i, start = TOK.findall(text) + ["$"], 0, 0
def eat(*want): # "VAL" = any number or "text"
nonlocal i
if toks[i] not in want and not ("VAL" in want and toks[i][0] in '"0123456789'):
raise SyntaxError(f"token {i - start + 1}: found {toks[i]!r}, "
f"expected {' or '.join(want)}")
i += 1
def level(op, sub): # X = sub { op sub }
sub()
while toks[i] == op: eat(op); sub()
def N():
if toks[i] == "NOT": eat("NOT"); return N()
if toks[i] == "(": eat("("); level("OR", T); return eat(")")
eat("NOT", "(", *FIELDS)
if toks[i] == "IN":
eat("IN"); eat("("); level(",", lambda: eat("VAL")); return eat(",", ")")
if toks[i] == "==": # error production for a common slip
print(f" note, token {i - start + 1}: '==' read as '='"); toks[i] = "="
eat(*OPS); eat("VAL")
T = lambda: level("AND", N)
while toks[i] != "$": # one query per ';'
start = i
try:
eat("FIND"); eat("order"); eat("WHERE"); level("OR", T); eat(";", "AND", "OR"); print("ok")
except SyntaxError as e:
print("ERROR", e)
i = toks.index(";", i) + 1 if ";" in toks[i:] else len(toks) - 1 # panic mode
check('''FIND order WHERE amount >= 500 AND status = "new";
FIND order WHERE district IN ("Dhaka" "Khulna");
FIND order WHERE status == "paid";
FIND order WHERE NOT (amount < 100 OR) ; FIND order WHERE district != "Sylhet";''')আসল আউটপুট (ব্রাউজারের Python):
ok
ERROR token 8: found '"Khulna"', expected , or )
note, token 5: '==' read as '='
ok
ERROR token 10: found ')', expected NOT or ( or amount or district or status
ok
পাঁচটি query, একবার চালানোয় দুটি ভুল আর একটি সতর্কবার্তা। দ্বিতীয় query-তে কমা বাদ পড়েছে; বার্তাটি পুরো expected-set দেয় (“, or )”), কারণ loop-এর শেষে eat(",", ")") দুটিই তালিকায় রাখে। Panic mode বাকি token ফেলে ; পর্যন্ত যায়, তাই তৃতীয় query নতুন করে শুরু হয়। সেখানে == একটি error production-এ ধরা পড়ে: query চলে, শুধু একটি note. চতুর্থটিতে OR-এর পরে কিছু নেই; parser জানায় সেখানে NOT, ( বা একটি field আসতে পারত। লক্ষ করুন, lark-এর তৃতীয় বার্তার ঘাটতি এখানে নেই, কারণ হাতে লেখা parser কোনো reduce আগে সেরে ফেলে না; এটি হাতে লেখা parser-এর একটি পরিচিত সুবিধা।
৭ · Grammar test — round trip আর grammar-based fuzzing
অংশ ৫-এর উদাহরণ-তালিকা ভালো শুরু, কিন্তু মানুষের লেখা ২০টি উদাহরণ সব কোণ ছোঁয় না। Grammar নিজেই আরও ভালো একটি test-যন্ত্র দেয়, কারণ grammar উৎপাদক: start symbol থেকে এলোমেলো নিয়ম বেছে বেছে যত খুশি বৈধ string বানানো যায় (পর্ব ২৫-এর random derivation). এই কৌশলের নাম grammar-based (generation-based) fuzzing; সফটওয়্যার টেস্টিং কোর্সের পর্ব ৬০-এ fuzzing-এর বিস্তৃত পরিচয় আছে, এখানে শুধু grammar-এর দিকটি। এর সঙ্গে দুটি পরীক্ষা মেলে:
- Round trip: একটি এলোমেলো AST বানানো, pretty-printer দিয়ে লেখায় রূপান্তর, তারপর parse করে আবার AST. ধর্মটি: parse(print(t)) = t, প্রতিটি t-এর জন্য। এটি একসঙ্গে parser আর printer দুটিকেই পরীক্ষা করে।
- Mutation: বৈধ query-র একটি token মুছে, দ্বিগুণ করে, পাশেরটির সঙ্গে অদলবদল করে বা বদলে দিয়ে প্রায়-বৈধ input বানানো। ধর্মটি: parser হয় গ্রহণ করে, নয় একটি পরিচিত parse error দেয়; অন্য কোনো exception (crash) মানেই bug.
বাজারঘরের দল printer-এ একটি bug ইচ্ছা করে বসিয়ে fuzzer পরীক্ষা করেছে: buggy printer NOT-এর operand-এর চারপাশে কখনো বন্ধনী বসায় না। সঠিক নিয়ম: কোনো node-এর সন্তানের precedence কম হলে বন্ধনী, আর বাম-সংযোগ operator-এর ডান সন্তানের precedence সমান হলেও বন্ধনী। মূল অংশ (qlib.py থেকে):
PREC = {"or": 1, "and": 2, "not": 3, "cmp": 4, "in": 4}
def show(a, buggy=False): # AST -> query text
...
if k == "not":
need = PREC[a[1][0]] < PREC["not"] and not buggy # planted bug
return "NOT " + wrap(a[1], need)
p = PREC[k]
left = wrap(a[1], PREC[a[1][0]] < p)
right = wrap(a[2], PREC[a[2][0]] <= p) # left-assoc
return f"{left} {k.upper()} {right}"
import random, re
from collections import Counter
from lark.exceptions import UnexpectedInput
from qlib import ast, gen, query, P1 # gen: random AST shaped by the grammar
rng = random.Random(2026)
asts = [gen(rng) for _ in range(5000)]
print("generated ASTs:", len(asts), "| distinct queries:", len({query(a) for a in asts}))
# 1. round trip: AST -> text -> AST must give the same AST
for buggy in (False, True):
bad = [a for a in asts if ast(query(a, buggy)) != a]
print(f"round trip, {'buggy' if buggy else 'fixed'} printer: {len(bad)} failures")
if bad:
a = min(bad, key=lambda a: len(query(a, True)))
print(" smallest:", a)
print(" printed :", query(a, True))
print(" reparsed:", ast(query(a, True)))
# 2. mutation fuzzing: break valid queries at the token level
TOK = re.compile(r'"[^"]*"|>=|<=|!=|[(),=<>]|\w+')
POOL = ["AND", "OR", "NOT", "IN", "(", ")", ",", "=", ">", "amount", '"Dhaka"', "7"]
tally = Counter()
for a in asts[:3000]:
t = TOK.findall(query(a))
i = rng.randrange(len(t))
op = rng.choice(["delete", "duplicate", "swap", "replace"])
if op == "delete": t[i:i + 1] = []
elif op == "duplicate": t[i:i] = [t[i]]
elif op == "swap" and i + 1 < len(t): t[i], t[i + 1] = t[i + 1], t[i]
else: t[i] = rng.choice(POOL)
try:
b = ast(" ".join(t))
tally["accepted"] += 1
tally["accepted, round trip ok"] += ast(query(b)) == b
except UnexpectedInput:
tally["rejected with a parse error"] += 1
except Exception as e: # anything else = a bug
tally["CRASH " + type(e).__name__] += 1
crash = sum(v for k, v in tally.items() if k.startswith("CRASH"))
print("mutants:", dict(tally), "| crashes:", crash)
# 3. backward compatibility: every v1 query means the same in v2
v1 = [gen(rng, v1=True) for _ in range(2000)]
diff = sum(ast(query(a), P1) != ast(query(a)) for a in v1)
print("v1 queries:", len(v1), "| parsed differently by v2:", diff)সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13; পুরো run এক সেকেন্ডের মতো):
~/bazarghar-toc$ uv run python fuzz_v2.py
generated ASTs: 5000 | distinct queries: 3159
round trip, fixed printer: 0 failures
round trip, buggy printer: 658 failures
smallest: ('not', ('or', ('cmp', 'amount', '>', 1940), ('cmp', 'amount', '=', 3779)))
printed : FIND order WHERE NOT amount > 1940 OR amount = 3779
reparsed: ('or', ('not', ('cmp', 'amount', '>', 1940)), ('cmp', 'amount', '=', 3779))
mutants: {'rejected with a parse error': 2881, 'accepted': 119, 'accepted, round trip ok': 119} | crashes: 0
v1 queries: 2000 | parsed differently by v2: 0
চারটি ফল। (১) সঠিক printer-এ ৫০০০টি AST-এর একটিও round trip-এ ভাঙেনি। (২) Buggy printer ৬৫৮ বার ধরা পড়েছে, আর min দিয়ে সবচেয়ে ছোট লেখার সাক্ষী বাছায় কারণটি এক নজরে স্পষ্ট: NOT (… OR …) বন্ধনী হারিয়ে NOT … OR … হয়ে গেছে, যা v2-এ (NOT …) OR … . (৩) ৩০০০টি mutant-এর ২৮৮১টি পরিচিত parse error-এ বাতিল, ১১৯টি ঘটনাক্রমে বৈধ (যেমন একটি NOT দ্বিগুণ হলে NOT NOT … বৈধ), আর সেগুলোও round trip পেরিয়েছে; crash ০. (৪) v1-এর ২০০০টি query v2-এ হুবহু একই AST দিয়েছে। দুই parser-এর এমন তুলনাকে বলে differential testing. “distinct 3159” বলে যে ছোট AST কয়েকবার এসেছে; বড় fuzzer-এ coverage মাপতে এই সংখ্যা কাজে লাগে।
1a = gen(rng)2text = query(a)3b = ast(text)4assert a == b
| a (AST) | |
| text | |
| b (AST) |
- AST. Fuzzer একটি গাছ বানায়: NOT, যার নিচে একটি OR, যার দুই সন্তান district = "Dhaka" আর status = "new". অর্থ: ঢাকারও নয়, নতুনও নয় এমন order.
- লেখা। Buggy printer NOT-এর পরে সন্তানটি বন্ধনী ছাড়াই লেখে: NOT district = "Dhaka" OR status = "new".
- আবার পড়া। v2 grammar-এ NOT, OR-এর চেয়ে শক্ত, তাই parser পড়ে (NOT district = "Dhaka") OR status = "new". মূলে এখন OR.
- তুলনা। a আর b আলাদা গাছ। এই query চালালে ঢাকার বাইরের সব order আর সব নতুন order আসবে: সম্পূর্ণ ভিন্ন ফল। Round-trip test ঠিক এই নীরব অর্থ-বদল ধরে, যা কোনো crash দেয় না।
- কারণ। সন্তানের precedence (OR = 1) তার মাতা-node-এর (NOT = 3) চেয়ে কম হলে বন্ধনী লাগবেই; buggy printer এই শর্ত NOT-এর বেলায় বাদ দিয়েছিল।
- সংশোধন। শর্তটি ফিরিয়ে দিলে লেখা হয় NOT (district = "Dhaka" OR status = "new"), আবার পড়লে একই AST. Fuzz run-এ ঠিক printer-এ ৫০০০টির মধ্যে ০ ব্যর্থতা। এই উদাহরণ এখন একটি স্থায়ী regression test.
একই পরীক্ষা আপনার ব্রাউজারে, JavaScript-এ, একটি ছোট বুলিয়ান ভাষায় (a, b, c, NOT, AND, OR আর বন্ধনী)। Parser-টি অংশ ২-এর মতো EBNF-এর loop দিয়ে লেখা; generator-এ seed স্থির, তাই প্রতিবার একই ফল।
// Round trip AST->text->AST. C = T {OR T}, T = N {AND N}, N = NOT N | (C) | a | b | c
let seed = 7; // seeded Park-Miller
const rnd = n => (seed = (seed * 48271) % 2147483647) % n;
function gen(d) {
const k = d > 2 ? 0 : rnd(4);
if (k === 0) return "abc"[rnd(3)];
if (k === 1) return ["NOT", gen(d + 1)];
return [k === 2 ? "AND" : "OR", gen(d + 1), gen(d + 1)];
}
const PREC = { OR: 1, AND: 2, NOT: 3 }, prec = t => (typeof t === "string" ? 4 : PREC[t[0]]);
function show(t, buggy) {
if (typeof t === "string") return t;
const w = (c, need) => (need ? "(" + show(c, buggy) + ")" : show(c, buggy));
if (t[0] === "NOT") return "NOT " + w(t[1], !buggy && prec(t[1]) < 3);
const p = PREC[t[0]];
return w(t[1], prec(t[1]) < p) + " " + t[0] + " " + w(t[2], prec(t[2]) <= p);
}
function parse(s) {
const toks = s.match(/\w+|[()]/g); let i = 0;
const level = (op, sub) => { let l = sub();
while (toks[i] === op) { i++; l = [op, l, sub()]; } return l; };
const N = () => { const t = toks[i++];
if (t === "NOT") return ["NOT", N()];
if (t === "(") { const e = C(); i++; return e; } return t; };
const C = () => level("OR", () => level("AND", N)); return C();
}
const trees = Array.from({ length: 2000 }, () => gen(0));
for (const buggy of [false, true]) {
const bad = trees.filter(t => JSON.stringify(parse(show(t, buggy))) !== JSON.stringify(t));
console.log((buggy ? "buggy" : "fixed") + " printer: " + bad.length + " / 2000 fail");
const t = bad.sort((x, y) => show(x, 1).length - show(y, 1).length)[0]; if (!t) continue;
for (const [k, v] of [["AST", JSON.stringify(t)], ["printed", show(t, true)],
["reparsed", JSON.stringify(parse(show(t, true)))]])
console.log(" " + k.padEnd(8) + ": " + v);
}আসল আউটপুট (ব্রাউজারের JavaScript):
fixed printer: 0 / 2000 fail
buggy printer: 507 / 2000 fail
AST : ["NOT",["OR","b","b"]]
printed : NOT b OR b
reparsed: ["OR",["NOT","b"],"b"]
একই bug, ভিন্ন ভাষা, একই ধরনের সবচেয়ে ছোট সাক্ষী: NOT (b OR b) বন্ধনী হারিয়ে (NOT b) OR b. এখানে মজার একটি দিক: NOT (b OR b) সবসময় NOT b-এর সমান, আর (NOT b) OR b সবসময় সত্য; তাই এই দুটি লেখার মান প্রায় সব ক্ষেত্রে আলাদা। w(t[2], prec(t[2]) <= p) লাইনের <= বদলে < করে আবার চালিয়ে দেখুন: তখন a AND (b AND c) বন্ধনী হারায়, আর fixed printer-ও ব্যর্থ হবে, কারণ parser বাম-সংযোগে পড়ে (a AND b) AND c. অর্থ এক (AND associative), কিন্তু গাছ আলাদা, তাই পরীক্ষা ব্যর্থ; এটি ঠিক করা হবে কি না, সেটি একটি নকশার সিদ্ধান্ত।
৮ · Version, backward compatibility আর অবিশ্বস্ত input
একটি ভাষা একবার চালু হলে তার লেখা জমতে থাকে: বাজারঘরে সংরক্ষিত report, অন্য দলের script, documentation-এর উদাহরণ। নতুন version-এর প্রথম দায়িত্ব backward compatibility: পুরোনো প্রতিটি বৈধ লেখা নতুন version-এও বৈধ, আর একই অর্থে। Grammar-এর ভাষায় দুটি শর্ত:
G2 হলো G1-এর backward compatible সম্প্রসারণ, যদি (ক) L(G1) ⊆ L(G2), আর (খ) প্রতিটি w ∈ L(G1)-এর জন্য G1 আর G2-এর গাছ থেকে একই AST আসে।
শর্ত (ক) একটি CFG inclusion-প্রশ্ন, আর পর্ব ৩৭-এ দেখেছেন, দুটি সাধারণ CFG-এর জন্য L(G1) ⊆ L(G2) undecidable. তাই কোনো tool সাধারণভাবে এটি প্রমাণ করতে পারে না; বাস্তবে আসে দুই দিক থেকে। প্রথম, গঠন দিয়ে: v2 grammar-কে v1-এর নিয়মগুলো রেখে শুধু নতুন বিকল্প যোগ করে বানালে (ক) প্রায় স্বতঃসিদ্ধ, কারণ v1-এর প্রতিটি derivation v2-এও চলে; বাজারঘরের v2 ঠিক তাই (T → T AND F বদলে T → T AND N, আর N → A দিয়ে আগের F-এ পৌঁছানো যায়)। দ্বিতীয়, পরীক্ষা দিয়ে: অংশ ৭-এর ২০০০টি v1 query-তে AST পার্থক্য ০. শর্ত (খ) সূক্ষ্মতর: নতুন নিয়ম পুরোনো string-এর গাছ বদলে দিতে পারে, যেমন নতুন একটি operator-কে ভুল স্তরে বসালে।
Version-ভাঙনের সবচেয়ে পরিচিত উৎস নতুন keyword. ধরুন একটি ভাষায় যেকোনো নাম field হতে পারে, আর কোনো দোকান “in” নামে একটি field রেখেছে। IN keyword এলে in = 5 আর parse হবে না। বাস্তব ভাষাগুলো এ নিয়ে সতর্ক: Python 3.7-এ async আর await পূর্ণ সংরক্ষিত keyword হয়, তার আগে কয়েক version-এ এগুলো শুধু নির্দিষ্ট প্রসঙ্গে বিশেষ ছিল; আর Python 3.10-এর match একটি “soft keyword”, যা শুধু match-statement-এর জায়গায় keyword, অন্যত্র সাধারণ নাম, যাতে match নামের পুরোনো variable না ভাঙে। Soft keyword-এর দাম হলো একটি জটিলতর parser; Python 3.9-এ CPython-এর নতুন PEG-ভিত্তিক parser (PEP 617) এমন নমনীয়তার একটি কারণ হিসেবে উল্লেখিত হয়েছিল।
এবার নিরাপত্তা। Parser প্রায়ই সিস্টেমের প্রথম দরজা, আর তার input অবিশ্বস্ত: যে কেউ admin panel-এর query বাক্সে যা খুশি লিখতে পারেন। পর্ব ২১-এ ReDoS দেখেছেন, যেখানে একটি দুর্বল regex ছোট input-এ বিশাল সময় নেয়। Grammar-এ সমতুল্য বিপদ গভীর নেস্টিং। নিচের run-এ v2-এর LALR parser আর তারপর AST বানানোর tree-walk, ক্রমশ গভীর NOT NOT NOT … -এ:
~/bazarghar-toc$ uv run python deep_v2.py
100 x NOT: 431 chars, parse 0.7 ms, AST ok
1000 x NOT: 4031 chars, parse 2.8 ms, AST RecursionError
5000 x NOT: 20031 chars, parse 13.9 ms, AST RecursionError
LALR parser নিজের stack একটি সাধারণ list-এ রাখে (পর্ব ৩২-এর PDA), তাই ২০০০০ অক্ষরেও সে স্বচ্ছন্দ। কিন্তু lark-এর Transformer গাছের ওপর Python-এর recursion দিয়ে হাঁটে, আর Python-এর ডিফল্ট recursion-সীমা প্রায় ১০০০ স্তর; ফলে মাত্র ৪ KB-র একটি query প্রক্রিয়া ভেঙে দেয়। Recursive descent parser (অংশ ৬-এর ব্লক) parse-এর সময়েই একই সীমায় পৌঁছায়। প্রতিকার সহজ, কিন্তু সচেতনভাবে করতে হয়: input-এর দৈর্ঘ্যের সীমা, নেস্টিং-গভীরতার সীমা (parser-এ একটি গণক রেখে, যেমন “বন্ধনী আর NOT মিলিয়ে ৫০-এর বেশি নয়”), আর গাছের ওপর recursion-এর বদলে নিজের stack দিয়ে হাঁটা।
দ্বিতীয় বিপদ parser differential: একই input দুটি আলাদা parser দুভাবে পড়ে। যেমন একটি সিস্টেমে প্রথমে একটি নিরাপত্তা-ফিল্টার query পড়ে অনুমতি দেয়, তারপর আরেকটি parser query চালায়। দুটির grammar একটু আলাদা হলে (একটি == মানে, অন্যটি মানে না; একটি NOT-কে বেশি শক্ত ধরে, অন্যটি কম), আক্রমণকারী এমন লেখা খুঁজতে পারে যা ফিল্টারের চোখে নিরীহ কিন্তু চালকের চোখে ভিন্ন। ওয়েবে HTTP request smuggling এই শ্রেণির একটি পরিচিত উদাহরণ বলে বর্ণিত, যেখানে দুটি সার্ভার একটি request-এর সীমানা আলাদাভাবে পড়ে। প্রতিরক্ষা: একটি grammar, একটি parser, একবার parse করে তৈরি AST-ই সবাই ব্যবহার করে; আর একাধিক parser অনিবার্য হলে অংশ ৭-এর মতো differential fuzzing.
আরও গভীরে: “LangSec” (language-theoretic security) নামে একটি গবেষণা-ধারা, যা সাধারণত Len Sassaman, Meredith Patterson ও Sergey Bratus-এর ২০১০-এর দশকের শুরুর কাজের সঙ্গে যুক্ত, দাবি করে যে input-এর format-কে একটি formal language হিসেবে নির্দিষ্ট করে Chomsky hierarchy-র যত নিচে রাখা যায় ততই নিরাপদ, কারণ context-free-এর ওপরের format-এর পূর্ণ যাচাই অনেক ক্ষেত্রে undecidable হয়ে পড়ে, আর দুটি সাধারণ CFG-এর সমতাও undecidable. Grammar-based test generation-এর ইতিহাস পুরোনো: K. V. Hanford-এর ১৯৭০ সালের একটি প্রবন্ধে compiler পরীক্ষার জন্য grammar থেকে program বানানোর “syntax machine”-এর বর্ণনা আছে বলে পরিচিত, আর ২০১১ সালের Csmith প্রকল্প এলোমেলো C program দিয়ে বাস্তব compiler-এ শত শত bug খুঁজে পেয়েছিল বলে প্রকাশিত।
পরীক্ষা ও ইন্টারভিউতে:
- { X }-কে CFG-তে লিখুন। নতুন R: R → X R ∣ ε; [ X ] হলে O → X ∣ ε.
- Precedence আর associativity grammar-এ কীভাবে বাঁধবেন? দুর্বল operator ওপরের স্তরে; বাঁ-recursion বাম-সংযোগ, ডান-recursion ডান-সংযোগ; বা Pratt-এ (l, r) টেবিল।
- Pratt-এ ডান-সংযোগী ^-এর binding power? l > r, যেমন (31, 30); তাহলে 2^3^2 = 2^(3^2).
- Panic mode কী? ভুল পেলে synchronizing token (যেমন ;) পর্যন্ত token ফেলে দিয়ে আবার শুরু।
- Parser আর pretty-printer একসঙ্গে কীভাবে পরীক্ষা করবেন? Round trip: এলোমেলো AST-এ parse(print(t)) = t.
৯ · AI-এর যুগে grammar নকশা
AI assistant একটি DSL-এর grammar কয়েক সেকেন্ডে লিখে দেয়, সঙ্গে Lark বা ANTLR-এর ফাইল আর কয়েকটি উদাহরণ। সমস্যা হলো, এই পর্বের প্রতিটি ভুল সে নিয়মিত করে, আর আউটপুট দেখতে নিখুঁত। সবচেয়ে বিপজ্জনক ভুলটি অংশ ৪-এর: খসড়া B-র মতো NOT-এর পরে পুরো expression, যা lark নিঃশব্দে “shift” করে চালিয়ে দেয়। তাই AI-এর grammar-কে একজন নতুন সহকর্মীর pull request-এর মতো দেখুন: উদাহরণ, conflict-গণনা আর fuzzer না পেরোলে merge নয়।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Prefix operator-এর operand পুরো expression (NOT cond) | Conflict-সংখ্যা গুনুন (draft_conflict.py-এর মতো); NOT a OR b-এর গাছ দেখুন |
| Precedence ঠিক, associativity ভুল (^ বাম-সংযোগ) | 2^3^2 আর 8−4−2-এর গাছ; pratt_check.py-এর মতো সব ছোট expression তুলনা |
| “Lark/ANTLR চলছে, তাই grammar unambiguous” | Earley-তে ambiguity="explicit" চালিয়ে ছোট সব string-এ গাছ গুনুন (পর্ব ২৭) |
| Pretty-printer-এ বন্ধনীর নিয়ম ভুল | Round-trip fuzzer; সবচেয়ে ছোট সাক্ষী দেখুন |
| নতুন keyword যোগ করে “পুরোনো query ঠিক থাকবে” দাবি | পুরোনো সংরক্ষিত query দুই version-এ parse করে AST মেলান |
| Error message-এ ভেতরের token-নাম (RPAR, $END) | পাঁচটি সাধারণ ভুল query-তে বার্তা পড়ে দেখুন |
| Recursion-গভীরতার সীমা নেই | ১০০০ স্তরের নেস্টেড input দিয়ে চালান |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু grammar নয়, operator table, উদাহরণের প্রত্যাশিত গাছ আর একটি fuzzer চাওয়া, যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Pratt-এর ১৯৭৩ সালের ধারণা কয়েক দশক প্রায় অবহেলিত থেকে আবার জনপ্রিয় হলো কেন? Parser generator থাকতে হাতে লেখা parser কেন?
Vaughan Pratt-এর “Top Down Operator Precedence” প্রবন্ধ ১৯৭৩ সালে প্রকাশিত হয়, ঠিক সেই সময়ে যখন yacc ধারার LALR parser generator (Stephen Johnson-এর yacc, ১৯৭০-এর দশক) compiler-জগতে প্রধান হয়ে উঠছিল। Parser generator-এর প্রতিশ্রুতি ছিল আকর্ষণীয়: grammar লিখুন, tool বাকিটা করবে, আর conflict থাকলে জানাবে। সেই পরিবেশে টেবিল-চালিত হাতে লেখা একটি ছোট algorithm বড় প্রভাব ফেলেনি; পাঠ্যবইয়েও “operator precedence parsing”-এর একটি ভিন্ন, পুরোনো রূপ (Floyd-এর ১৯৬৩ সালের) বেশি জায়গা পেত।
পরের কয়েক দশকে বাস্তব compiler-গুলোর অভিজ্ঞতা কিছুটা উল্টো দিকে গেছে। GCC-র C আর C++ front end এক সময় Bison-ভিত্তিক ছিল, পরে হাতে লেখা recursive descent parser-এ সরে যায় বলে পরিচিত; Clang শুরু থেকেই হাতে লেখা। কারণগুলো এই পর্বেই দেখেছেন: হাতে লেখা parser-এ error message আর recovery সম্পূর্ণ নিয়ন্ত্রণে থাকে (অংশ ৬-এ হাতে লেখা parser-এর পূর্ণ expected-set বনাম LALR-এর অসম্পূর্ণ সেট), ভাষার context-sensitive খুঁটিনাটি (C++-এর template বা typedef-নামের সমস্যা) কোডে সামলানো সহজ, আর বাইরের tool-এর ওপর নির্ভরতা কমে। কিন্তু recursive descent-এর পুরোনো দুর্বলতা ছিল expression: দশটি precedence-স্তরের জন্য দশটি function, আর প্রতিটি সংখ্যা পড়তে দশটি ডাক।
ঠিক এই ফাঁকটি Pratt পূরণ করে। Statement আর declaration-এর জন্য সাধারণ recursive descent, আর expression-এর জন্য একটি ছোট Pratt loop: এই মিশ্র নকশা এখন হাতে লেখা parser-এর একটি প্রচলিত ছাঁচ। ২০০০-এর দশকে Douglas Crockford-এর JavaScript-এ লেখা একটি পরিচিত প্রবন্ধ আর পরে বিভিন্ন blog ও বই ধারণাটিকে নতুন প্রজন্মের কাছে জনপ্রিয় করে বলে উল্লেখ করা হয়। অংশ ৩-এর পরীক্ষা দেখিয়েছে, টেবিল-চালিত loop আর স্তরভাগ করা grammar একই গাছ দেয়; অর্থাৎ Pratt তত্ত্বে নতুন কিছু আনেনি, এনেছে প্রকৌশলের সরলতা।
মূল উপলব্ধি: Parsing পদ্ধতির জনপ্রিয়তা তত্ত্বের শক্তি দিয়ে নয়, প্রকৌশলের প্রয়োজন দিয়ে ঠিক হয়। Error message, রক্ষণাবেক্ষণ আর গতি যখন প্রধান, তখন হাতে লেখা recursive descent আর Pratt; যখন দ্রুত একটি নির্ভরযোগ্য parser দরকার আর grammar-ই মূল দলিল, তখন generator.
প্র ০২JSON কেন শেষের কমা (trailing comma) নিষেধ করে, আর JavaScript বা Python কেন অনুমতি দেয়? ছোট একটি grammar-সিদ্ধান্তের বড় প্রভাব কী?
Grammar-এর দিক থেকে পার্থক্য একটি অক্ষর: JSON-এর array মোটামুটি "[" [ value { "," value } ] "]", আর শেষের কমা অনুমোদিত হলে "[" [ value { "," value } [ "," ] ] "]". দুটিই unambiguous, দুটিই LL(1). তত্ত্বে কোনো পার্থক্য নেই, পার্থক্য পুরোটাই ব্যবহারে। JSON-এর মানক দলিল (বর্তমানে RFC 8259) শেষের কমা অনুমোদন করে না, আর JSON-এর নকশার মূল দর্শন ছিল ন্যূনতম, একটিমাত্র সঠিক লেখার রূপ, যাতে প্রতিটি ভাষার parser সহজে আর একইভাবে লেখা যায়। প্রতিটি বাড়তি স্বাধীনতা মানে আরও একটি জায়গা যেখানে দুটি parser ভিন্ন আচরণ করতে পারে, অর্থাৎ অংশ ৮-এর parser differential-এর বীজ।
অন্যদিকে programming language-এ মানুষ হাতে লেখে আর বারবার সম্পাদনা করে। শেষের কমা অনুমোদিত হলে একটি তালিকার শেষে নতুন উপাদান যোগ করতে আগের লাইন ছুঁতে হয় না, তাই version control-এর diff ছোট হয় আর merge-এর সংঘাত কমে; লাইন সরানো বা অদলবদল করাও নিরাপদ। JavaScript-এ array আর object literal-এ এটি অনেক আগে থেকে বৈধ, আর পরে function-এর argument-তালিকাতেও যোগ হয়; Python-এ list, tuple, dict আর function-ডাকে বৈধ। কিন্তু Python-এ একটি কৌতূহলজনক পরিণতি আছে: (1) একটি সংখ্যা, আর (1,) একটি tuple; শেষের কমা এখানে অর্থ বদলায়, তাই grammar-এর একটি “আরামের” নিয়ম ভাষার semantics-এ ঢুকে পড়ে।
এই কারণেই অনেক configuration format (যেমন JSON5 বা অনেক tool-এর “JSON with comments”) JSON-এর ওপর শেষের কমা আর comment যোগ করেছে: মানুষের লেখার জন্য আলাদা format, যন্ত্রে-যন্ত্রে আদান-প্রদানের জন্য কঠোর JSON. বাজারঘরের query v2-এ IN-তালিকায় শেষের কমা নিষিদ্ধ (অংশ ৬-এর দ্বিতীয় বার্তা ঠিক সেটি ধরে); query ছোট আর এক লাইনে লেখা হয়, তাই diff-এর সুবিধা এখানে নগণ্য, আর কঠোরতা ভবিষ্যতে নিয়ম শিথিল করার পথ খোলা রাখে। উল্টোটা কঠিন: একবার অনুমতি দিলে পরে নিষেধ করা মানে পুরোনো লেখা ভাঙা।
মূল উপলব্ধি: Grammar-এর ছোট সিদ্ধান্তের মূল্যায়ন তত্ত্ব দিয়ে হয় না; প্রশ্ন হলো কে লেখে, কে পড়ে, আর কত parser একই format পড়বে। আর backward compatibility অসমমিত: শিথিল করা সহজ, কঠোর করা প্রায় অসম্ভব।
প্র ০৩Round-trip আর grammar-based fuzzing হাজার হাজার input পরীক্ষা করে। তবু এটি কেন প্রমাণ নয়? আর কোন ধরনের bug এই পরীক্ষা কখনোই ধরবে না?
অংশ ৭-এর fuzzer ৫০০০টি AST পরীক্ষা করেছে; বাজারঘরের query-র সম্ভাব্য সংখ্যা অসীম। পরীক্ষা শুধু ধরা পড়া ভুল দেখায়: ৬৫৮টি ব্যর্থতা একটি নিশ্চিত সত্য, কারণ সাক্ষী হাতে আছে, কিন্তু ০টি ব্যর্থতা কিছুই প্রমাণ করে না। Edsger Dijkstra-র বহুল উদ্ধৃত কথাটি এখানে খাটে: testing bug-এর উপস্থিতি দেখাতে পারে, অনুপস্থিতি নয়। পর্ব ২৭-এ একই কথা ambiguity-র ক্ষেত্রে দেখেছেন: brute force একটি নির্দিষ্ট দৈর্ঘ্য পর্যন্ত নিশ্চয়তা দেয়, তার বাইরে প্রমাণ লাগে। অংশ ৩-এ Pratt আর স্তরভাগ grammar-এর তুলনাও তাই একটি প্রমাণের রূপরেখার সঙ্গে দেওয়া হয়েছে।
Fuzzer-এর অন্ধ জায়গা তার generator-এর আকারে। বাজারঘরের gen গভীরতা ৪-এ থামে, তালিকায় সর্বোচ্চ তিনটি মান রাখে, আর জেলার নাম চারটি নির্দিষ্ট লেখা থেকে নেয়। ফলে একটি bug যা শুধু ৫০-স্তরের নেস্টিং-এ দেখা দেয় (অংশ ৮-এর RecursionError), বা উদ্ধৃতির ভেতরে একটি বিশেষ অক্ষরে (যেমন বাংলা লেখা বা একটি উল্টো slash), এই fuzzer কখনো তৈরিই করবে না। দ্বিতীয় অন্ধ জায়গা নিজের সঙ্গে সামঞ্জস্য: round trip parse(print(t)) = t যাচাই করে যে parser আর printer একে অন্যের সঙ্গে মেলে, কিন্তু দুটিই যদি একই ভুল নিয়ম মানে (যেমন দুটিই NOT-কে OR-এর চেয়ে দুর্বল ধরে), পরীক্ষা নিঃশব্দে পাস করবে। এর জন্য লাগে একটি বাইরের সত্য: মানুষের লেখা উদাহরণ আর প্রত্যাশিত গাছ, যাকে testing-এর ভাষায় oracle বলে।
তৃতীয় সীমা mutation-এ: token-স্তরের mutation অক্ষর-স্তরের ভুল (একটি অসমাপ্ত উদ্ধৃতি, অদৃশ্য Unicode অক্ষর) তৈরি করে না। তাই বাস্তব দল কয়েক স্তরের fuzzer চালায়: grammar-ভিত্তিক (গঠনের গভীরে যেতে), byte-স্তরের coverage-guided (lexer আর অপ্রত্যাশিত অক্ষরের জন্য), আর সীমা-পরীক্ষার হাতে বানানো input (খুব লম্বা, খুব গভীর)। Generator-এর নিজস্ব পক্ষপাতও আছে: এলোমেলো নিয়ম-বাছাই ছোট গাছ বেশি বানায়; distinct-সংখ্যা (৫০০০-এ ৩১৫৯) সেই পুনরাবৃত্তিরই চিহ্ন।
মূল উপলব্ধি: Fuzzing দ্রুত, সস্তা আর ভুল খোঁজায় অসাধারণ, কিন্তু তার জগৎ generator যতদূর পৌঁছায় ততটুকু। প্রমাণ, মানুষের oracle আর ভিন্ন ধরনের fuzzer মিলেই আস্থা তৈরি হয়।
প্র ০৪Error recovery-র ইতিহাসে “বেশি চেষ্টা” কেন সবসময় ভালো ফল দেয়নি? Compiler-এর error cascade কী, আর আধুনিক tool এ নিয়ে কী করে?
Punched card আর batch processing-এর যুগে, ১৯৬০ আর ১৯৭০-এর দশকে, একটি program compile করতে কয়েক ঘণ্টা বা পুরো একদিন অপেক্ষা করতে হতো বলে প্রায়ই বর্ণনা করা হয়। তখন একটি ভুলে থেমে যাওয়া compiler ছিল ব্যয়বহুল: প্রতিটি ভুলের জন্য আলাদা একদিন। তাই compiler-নির্মাতারা আক্রমণাত্মক recovery-তে বিনিয়োগ করেছিলেন: token ঢোকানো, মোছা, বদলানো, এমনকি “সবচেয়ে কম সম্পাদনায় বৈধ program” খোঁজার algorithm (minimum-distance error correction-এর গবেষণা ওই সময়ের)। Cornell-এর PL/C compiler এমন আক্রমণাত্মক মেরামতের জন্য পরিচিত ছিল বলে উল্লেখ পাওয়া যায়।
কিন্তু মেরামতের একটি দাম আছে: ভুল মেরামত। Parser যদি একটি বাদ পড়া বন্ধনী ভুল জায়গায় বসায়, তাহলে পরের অনেক লাইন তার কাছে অর্থহীন হয়ে যায়, আর একটি আসল ভুলের পেছনে কয়েক ডজন মিথ্যা ভুলের বার্তা আসে। এর নাম error cascade. ব্যবহারকারী প্রথম বার্তা ঠিক করেন, আবার compile করেন, আর বাকি ত্রিশটি বার্তা উধাও। অভিজ্ঞ প্রোগ্রামারদের পুরোনো উপদেশ “শুধু প্রথম error পড়ুন” এই অভিজ্ঞতা থেকেই এসেছে।
আধুনিক পরিস্থিতি ভিন্ন: compile কয়েক সেকেন্ডে হয়, আর editor প্রতিটি অক্ষর টাইপ করার সঙ্গে সঙ্গে parse করে। তাই এখন লক্ষ্য দুটি: প্রথম বার্তা নির্ভুল আর সাহায্যকারী (Clang আর Rust compiler-এর বার্তা “expected ';' after expression” ধরনের নির্দিষ্টতা আর পরামর্শের জন্য প্রশংসিত), আর মিথ্যা বার্তা চাপা দেওয়া, যেমন একই জায়গায় কয়েকটি ভুল হলে শুধু একটি দেখানো, বা মেরামত-করা অংশের ভেতরের বার্তা লুকানো। Editor-এর জন্য তৈরি tree-sitter-এর মতো incremental parser আবার উল্টো চাহিদায় চলে: অসম্পূর্ণ লেখাতেও যতটা সম্ভব গাছ বানাতে হয়, কারণ ব্যবহারকারী টাইপ করছেন, ভুল করছেন না। অংশ ৬-এর panic mode সবচেয়ে রক্ষণশীল পথ: কম মেরামত, কম মিথ্যা বার্তা।
মূল উপলব্ধি: Recovery-র মান নির্ভর করে ভুল ধরার খরচ আর মিথ্যা বার্তার খরচের ভারসাম্যে, আর সেই ভারসাম্য প্রযুক্তির সঙ্গে বদলেছে। আজকের নিয়ম: প্রথম বার্তা নির্ভুল, বাকিগুলো সতর্কভাবে।
প্র ০৫বাজারঘরের query ভাষা কি আদৌ একটি নতুন DSL হওয়া উচিত ছিল? SQL-এর একটি অংশ, JSON-এর filter, বা একটি ফর্মের সঙ্গে তুলনা করলে grammar-নকশার দাম কী?
প্রতিটি নতুন ভাষা একটি দীর্ঘমেয়াদি দায়: grammar, parser, error message, documentation, editor-সহায়তা, আর এই পর্বের সব পরীক্ষা, প্রতিটি version-এ। বিকল্পগুলো ভাবা দরকার। প্রথম, একটি ফর্ম: drop-down থেকে field, operator আর মান বাছাই। এতে কোনো grammar নেই, syntax error অসম্ভব, কিন্তু নেস্টেড বন্ধনী আর NOT প্রকাশ করা কঠিন, আর অভিজ্ঞ ব্যবহারকারীর গতি কমে। দ্বিতীয়, JSON বা অনুরূপ গঠনে filter: {"and": [ {"not": …}, … ]}. এখানে grammar-এর কাজ একটি মানক parser করে দেয়, AST সরাসরি লেখা হয়, precedence-এর প্রশ্ন ওঠেই না; কিন্তু মানুষের হাতে লেখা কষ্টকর।
তৃতীয়, SQL-এর WHERE অংশ সরাসরি গ্রহণ করা। সুবিধা: কর্মীরা হয়তো আগে থেকেই জানেন, আর precedence সেই অভ্যাসেই (এই কারণেই v2 SQL-এর ক্রম নিয়েছে)। বিপদ: পূর্ণ SQL-এর grammar বিশাল, আর ব্যবহারকারীর লেখা সরাসরি database-এ পাঠালে SQL injection-এর দরজা খোলে। নিরাপদ পথ হলো SQL-এর একটি ছোট উপসেটের নিজস্ব grammar, যা AST বানায়, আর সেই AST থেকে parameter-সহ query তৈরি: অর্থাৎ শেষ পর্যন্ত একটি ছোট DSL-ই, শুধু SQL-এর চেহারায়। Martin Fowler-এর মতো লেখকেরা “internal DSL” (একটি সাধারণ programming language-এর ভেতরে API দিয়ে বানানো) আর “external DSL” (নিজস্ব grammar আর parser) আলাদা করেন; বাজারঘরের query একটি external DSL.
বাজারঘরের ক্ষেত্রে সিদ্ধান্তটি যুক্তিসংগত হতে পারে: ব্যবহারকারীরা ভেতরের কর্মী, query ছোট, প্রকাশের ক্ষমতা (নেস্টিং, NOT, তালিকা) দরকার, আর ভাষাটি এত ছোট যে পুরো grammar এক পৃষ্ঠায় ধরে, পূর্ণ fuzzing এক সেকেন্ডে চলে। কিন্তু সীমা টানতে হবে: ভাষাটি Turing-complete হওয়ার দিকে যেন না যায় (loop, ব্যবহারকারী-সংজ্ঞায়িত function). মডিউল ৯-এ দেখবেন, তখন “এই query কি শেষ হবে?” বা “দুটি query কি সমতুল্য?” প্রশ্নগুলো undecidable হয়ে যায়; এখনকার v2-এ শর্ত শুধু Boolean সূত্র, তাই প্রতিটি query একটি order-এর ওপর সসীম সময়ে শেষ হয়।
মূল উপলব্ধি: সবচেয়ে ভালো grammar কখনো কখনো কোনো grammar না থাকা। নতুন DSL তখনই, যখন প্রকাশের প্রয়োজন সত্যিকারের, ভাষা ছোট রাখা যায়, আর তার পরীক্ষা ও version-এর দায় বহনের প্রস্তুতি আছে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। pratt.py আর roundtrip.js ব্লকে নিজের উদাহরণ বসিয়ে যাচাইও করতে পারেন।
-
নকশা: বাজারঘর query v2-এ
district NOT IN ("Dhaka", "Khulna")রূপটি যোগ করতে হবে, prefix NOT রেখেই। (ক) Lark grammar-এ নতুন নিয়ম লিখুন। (খ) এটি কি prefix NOT-এর সঙ্গে conflict তৈরি করবে? কারণ বলুন। (গ) NOT district NOT IN ("Dhaka") AND status = "new"-এর গাছ কী?(ক) atom-এ একটি বিকল্প:
| TEXT_FIELD "NOT" "IN" "(" STR ("," STR)* ")" -> text_not_in.(খ) না। Prefix NOT শুধু neg-এর শুরুতে আসে, যেখানে আগে কোনো field পড়া হয়নি; নতুন NOT আসে একটি TEXT_FIELD পড়ার পরে. LALR-এর state আলাদা, তাই একই ঘরে দুটি কাজ আসে না। Scratch-এ lark 1.3.1-এ এই নিয়ম যোগ করে conflict-গণনা ০ এসেছে।
(গ) মূলে and_; বাঁ সন্তান not_, তার নিচে text_not_in (district, "Dhaka"); ডান সন্তান text_cmp (status = "new"). অর্থাৎ (NOT (district NOT IN ("Dhaka"))) AND status = "new", যা “ঢাকার নতুন order”. একই run-এ lark ঠিক এই গাছ দিয়েছে। নকশার প্রশ্ন: দ্বিগুণ নেতিবাচক পড়তে বিভ্রান্তিকর, তাই documentation-এ এর বদলে district IN ("Dhaka") লেখার পরামর্শ দেওয়া ভালো।
-
প্রমাণ: X থেকে আসা string-এর language L = L(X), যেখানে ε ∉ L. নতুন variable R-এর নিয়ম R → X R ∣ ε. প্রমাণ করুন L(R) = L∗, যেখানে L(R) = {w : R ⇒∗ w}. এই প্রমাণ উপপাদ্য ২.১-এর কোন ধাপকে সমর্থন করে?
L∗ ⊆ L(R): k-এর ওপর induction-এ দেখাই, Lk-এর প্রতিটি string R থেকে আসে।
- k = 0: L0 = {ε}, আর R ⇒ ε. — ভিত্তি
- w ∈ Lk+1 হলে w = uv, যেখানে u ∈ L আর v ∈ Lk. — Lk+1-এর সংজ্ঞা
- R ⇒ XR ⇒∗ uR (X ⇒∗ u) ⇒∗ uv (induction-এ R ⇒∗ v). — context-free: দুই অংশ স্বাধীনভাবে derive হয়
L(R) ⊆ L∗: R-এর derivation-এ R → XR নিয়ম কতবার খাটানো হয়েছে, সেই সংখ্যা m-এর ওপর induction.
- m = 0 হলে একমাত্র নিয়ম R → ε, তাই w = ε ∈ L∗. — ভিত্তি
- m ≥ 1 হলে প্রথম ধাপ R ⇒ XR, আর w = uv, যেখানে X ⇒∗ u (তাই u ∈ L) আর R ⇒∗ v-এ R → XR খাটে m − 1 বার। — গাছের মূল ভাগ
- Induction-এ v ∈ L∗, তাই uv ∈ L · L∗ ⊆ L∗. ∎
এটি উপপাদ্য ২.১-এর ধাপ ২: { X }-এর জায়গায় R বসালে language বদলায় না। শর্ত ε ∉ L প্রমাণে লাগেনি, কিন্তু অংশ ২-এর সতর্কবার্তার জন্য জরুরি: ε ∈ L হলে L(R) একই থাকে, কিন্তু একটি string-এর অসীম সংখ্যক গাছ (X থেকে ε বারবার), অর্থাৎ grammar ambiguous.
-
Output অনুমান: অংশ ৩-এর binding power টেবিল (+ − : (10, 11); ∗ / : (20, 21); ^ : (31, 30)) দিয়ে Pratt parser
parse("2^3*4-1", trace=True)চালালে কয়টি trace-লাইন ছাপবে, কোন লাইনগুলোতে “<” আসবে, আর শেষ গাছ ও মান কী?left=2 sees ^: lbp 31 >= 0 left=3 sees *: lbp 20 < 30 left=(2^3) sees *: lbp 20 >= 0 left=4 sees -: lbp 10 < 21 left=((2^3)*4) sees -: lbp 10 >= 0 2^3*4-1 -> (((2^3)*4)-1) 31পাঁচটি trace-লাইন। ^ নেওয়ার পর ডানে expr(30); সেখানে 3-এর পরে ∗ আসে, 20 < 30, তাই থামে (∗ দুর্বলতর)। ∗ বাইরের loop-এ ধরা পড়ে, বাঁ operand এখন (2^3). একইভাবে − : expr(21)-এ 4-এর পরে 10 < 21, থামা। শেষ গাছ (((2^3)∗4)−1), মান 8 × 4 − 1 = 31. Scratch-এ চালিয়ে হুবহু এই আউটপুট এসেছে।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: নতুন printer সঠিক। প্রমাণ: (১) ৫০০০টি এলোমেলো AST-এ parse(print(t)) = t সত্য পাওয়া গেছে। (২) তাই প্রতিটি AST-এ এটি সত্য। (৩) parse(print(t)) = t মানে printer প্রতিটি query-র ঠিক অর্থ লেখে। ∎” কোন ধাপগুলো ভুল, আর কেন?
ধাপ (২) ভুল: সসীম নমুনা থেকে অসীম সেটের সাধারণীকরণ। ৫০০০টি পাস করা কিছুই প্রমাণ করে না; generator যেখানে পৌঁছায় না (যেমন গভীরতা ৪-এর বেশি, অথবা উদ্ধৃতির ভেতরে বিশেষ অক্ষর), সেখানে bug থাকতে পারে। প্রমাণের জন্য AST-এর গঠনের ওপর structural induction লাগে: প্রতিটি node-এ printer যে বন্ধনী বসায়, তা দেখায় যে parser ঠিক সেই node-কেই মূল হিসেবে পড়বে।
ধাপ (৩)-ও ভুল: parse(print(t)) = t শুধু বলে printer আর parser পরস্পরের সঙ্গে সামঞ্জস্যপূর্ণ। দুটিই যদি একই ভুল নিয়ম মানে (যেমন দুটিই NOT-কে OR-এর চেয়ে দুর্বল ধরে), ধর্মটি সত্য থাকে কিন্তু অর্থ মানুষের প্রত্যাশার উল্টো। “ঠিক অর্থ” যাচাই করতে বাইরের oracle লাগে: মানুষের লেখা উদাহরণ আর প্রত্যাশিত গাছ (অংশ ৫)। ধাপ (১) তথ্য হিসেবে ঠিক, আর bug খোঁজার জন্য মূল্যবান।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি ছোট DSL-এর grammar নকশার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- বৈধ আর অবৈধ উদাহরণের তালিকা, প্রতিটির প্রত্যাশিত অর্থসহ
- Operator table: precedence আর associativity ঠিক করা
- Token আর grammar ভাগ করা: কোনটি lexer-এ, কোনটি parser-এ
- EBNF-এ স্তরভাগ করা grammar লেখা
- Parser generator-এ conflict-গণনা আর উদাহরণের গাছ মেলানো
- Round-trip, mutation আর পুরোনো version-এর সঙ্গে differential fuzzing
EBNF নিয়ম A = b { c } (b, c terminal)-এর সমতুল্য CFG কোনটি?
- A → bc
- A → bR, R → cR ∣ ε
- A → Rc, R → bR ∣ ε
- A → bR, R → cR
Pratt parser-এ ^ operator-এর binding power (l, r) = (31, 30), আর অন্য কোনো operator নেই। 2^3^2-এর গাছ আর মান কী?
- (2^3)^2 = 64
- দুটি গাছই সম্ভব, তাই মান অনির্দিষ্ট
- 2^(3^2) = 512
- Parser ত্রুটি দেয়, কারণ l ≠ r
Grammar: C → C AND C ∣ C OR C ∣ NOT C ∣ a. একটি LALR parser generator প্রতিটি shift/reduce conflict নিঃশব্দে “shift” দিয়ে মেটায়। “NOT a OR a” কীভাবে পড়া হবে?
- NOT (a OR a)
- (NOT a) OR a
- Parse ত্রুটি
- দুটি গাছই, একটি ambiguity node-এর নিচে
একটি query ভাষার parser আর pretty-printer-এর round-trip test parse(print(t)) = t কোন ধরনের bug সবচেয়ে ভালো ধরে?
- Query চালানোর সময় database ধীর হয়ে যাওয়া
- Parser আর printer দুটিই NOT-এর precedence একইভাবে ভুল ধরে
- ১০০০ স্তরের নেস্টিং-এ recursion-সীমা
- Printer প্রয়োজনীয় বন্ধনী বাদ দেয়
একটি query ভাষার v1-এ যেকোনো নাম field হতে পারে। v2-তে নতুন keyword IN যোগ হলো। কোন পরিবর্তনটি backward compatibility ভাঙে?
- নতুন operator NOT, যা আগে কোথাও বৈধ ছিল না, এমন জায়গায় যোগ করা
- IN-কে পূর্ণ সংরক্ষিত keyword করা, ফলে in নামের field আর লেখা যায় না
- ভুল query-র error message আরও বিস্তারিত করা
- IN-কে শুধু field-এর পরের অবস্থানে keyword (soft keyword) রাখা
Parser-এর panic mode error recovery-তে কী ঘটে?
- প্রথম ভুলেই parser থেমে যায় আর বাকি input পড়ে না
- Parser সবচেয়ে কম সম্পাদনায় input-কে বৈধ করে নেয়
- একটি synchronizing token পর্যন্ত token ফেলে দিয়ে আবার শুরু করে
- Grammar-এ রাখা বিশেষ নিয়ম দিয়ে == কে = হিসেবে পড়ে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- ভালো grammar = ঠিক language + একটি গাছ + প্রত্যাশিত অর্থ + conflict-হীন + ভালো error + যাচাইযোগ্য + বিবর্তনযোগ্য।
- EBNF লেখা ছোট করে, শক্তি বাড়ায় না: { X } → R → X R ∣ ε. EBNF associativity বলে না; সেটি আলাদা করে লিখতে হয়।
- Pratt: প্রতিটি operator-এর (l, r); l < r বাম-সংযোগ, l > r ডান-সংযোগ; স্তরভাগ grammar-এর একই গাছ।
- Conflict-সংখ্যা assert করুন: lark-এর LALR shift/reduce নিঃশব্দে “shift” করে, আর prefix NOT-এর operand পুরো expression হলে অর্থ বদলায়।
- Round trip, mutation আর পুরোনো version-এর সঙ্গে differential fuzzing ভুল খোঁজে; প্রমাণ আর মানুষের উদাহরণ ছাড়া নিশ্চয়তা নেই। গভীরতা আর দৈর্ঘ্যের সীমা রাখুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২৭ · Ambiguity — দ্ব্যর্থক grammar আর inherent ambiguityফিরে দেখুনPrecedence আর associativity-র স্তর, dangling else, আর ambiguity কেন undecidable.
- পর্ব ৪০ · Parser generator — Lark, ANTLR আর grammar থেকে parserআগের ধাপOrder-query v1-এর পূর্ণ Lark interpreter, যার ওপর এই পর্বের v2 দাঁড়িয়ে।
- পর্ব ২২ · Lexical analysis — token, lexer আর lexer generatorফিরে দেখুনবাজারঘরের query-র token, maximal munch আর lexer-parser সীমানার তত্ত্ব।
- পর্ব ২১ · বাস্তব regex engine — backtracking বনাম automaton আর ReDoSনিরাপত্তাঅবিশ্বস্ত input-এ regex-এর বিপদ, এই পর্বের গভীর-নেস্টিং সমস্যার আত্মীয়।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৪৩ Turing machine.
- সফটওয়্যার টেস্টিং · পর্ব ৬০ — Fuzz testingপাশের ট্র্যাকCoverage-guided fuzzing, crash খোঁজা আর fuzzing-এর পুরো কর্মপদ্ধতি।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৩ — Grammar আর formal languageপটভূমিGrammar আর BNF-এর প্রথম পরিচয়, গণিতের দিক থেকে।