এই পর্বে যা শিখবেন
- Parser generator কী নেয় আর কী দেয়, আর কোন tool কোন parsing algorithm ও কোন grammar-শ্রেণি ব্যবহার করে
- Lark দিয়ে grammar ফাইল, transformer আর evaluator জুড়ে একটি পূর্ণ query interpreter বানানো
- Line আর column-সহ error message পড়া, আর LALR কেন কখনো error-এর আগে বাড়তি reduce করে তা বোঝা
- Conflict আর ambiguity-র সম্পর্ক প্রমাণসহ জানা, আর ANTLR 4-এর ALL(*), left recursion ও visitor নিজে চালিয়ে দেখা
- PEG-এর ordered choice, packrat-এর রৈখিক সময়ের প্রমাণ, parser combinator আর tool বাছাইয়ের নিয়ম
১ · Parser generator কী করে — grammar থেকে program
পর্ব ৩৮-এ আপনি FIRST, FOLLOW আর LL(1) টেবিল হাতে বানিয়েছেন, পর্ব ৩৯-এ LR(0) item আর shift-reduce টেবিল। একটি ছোট grammar-এ এটি অনুশীলন; কিন্তু একটি বাস্তব ভাষার grammar-এ শত শত নিয়ম, আর টেবিলে হাজার হাজার ঘর। হাতে করলে ভুল নিশ্চিত, আর grammar একটু বদলালেই সব আবার করতে হয়। তাই কাজটি দেওয়া হয় একটি program-কে: parser generator. ইতিহাসে এর আরেক নাম “compiler-compiler”, কারণ এটি compiler-এর একটি অংশ বানায়।
দর্জির দোকানের কথা ভাবুন। ওস্তাদ প্রতিটি জামা হাতে কাটেন না; তিনি একবার মাপ থেকে কাগজের প্যাটার্ন বানান, তারপর কারিগররা সেই প্যাটার্ন ধরে দিনভর কাপড় কাটেন। মাপ বদলালে শুধু নতুন প্যাটার্ন। Grammar হলো মাপ, generator হলো প্যাটার্ন বানানোর কাজ, আর বানানো parser হলো প্যাটার্ন, যা প্রতিটি input-এ বারবার খাটে। প্যাটার্ন বানাতে সময় লাগে একবারই (build time); কাপড় কাটা চলে প্রতিদিন (run time).
একটি generator সাধারণত তিনটি জিনিস নেয়: (১) token-এর নিয়ম, যা থেকে lexer হয় (পর্ব ২২); (২) একটি context-free grammar, প্রায়ই EBNF রীতিতে; (৩) প্রতিটি নিয়মের অর্থ, অর্থাৎ নিয়মটি মিললে কী করতে হবে। শেষেরটি পুরোনো tool-এ নিয়মের পাশে বসানো কোড, যার নাম semantic action; নতুন tool-এ (Lark, ANTLR) parser আগে পুরো গাছ বানায়, আর আপনি আলাদা class-এ গাছের ওপর কাজ লেখেন। ফল হলো একটি program, যা input পড়ে হয় একটি parse tree দেয়, নয়তো line আর column-সহ একটি syntax error.
Grammar ফাইল থেকে query-র উত্তর — build time আর run time
ওপরের দুই ধাপ একবার চলে; নিচের চার ধাপ প্রতিটি query-তে চলে।
তত্ত্বের ভাষায় কথাটি এমন। ধরুন 𝒞 একটি grammar-শ্রেণি, যেমন LALR(1) grammar. একটি parser generator হলো একটি algorithm, যা একটি grammar G নিয়ে দুটির একটি করে: G ∉ 𝒞 হলে একটি conflict-এর বিবরণ দেয়, আর G ∈ 𝒞 হলে একটি program PG দেয়, যেন প্রতিটি token-ধারা w-এর জন্য PG(w) একটি parse tree দেয় ঠিক তখন, যখন w ∈ L(G). অর্থাৎ PG হলো L(G)-এর একটি decider, সঙ্গে প্রমাণ হিসেবে গাছ। 𝒞 যত বড়, generator তত বেশি grammar মেনে নেয়; কিন্তু 𝒞 ছোট হলে PG সাধারণত দ্রুত, আর টেবিল বানানোর সময়েই সমস্যা ধরা পড়ে।
২ · Generator-এর পরিবার — কোন algorithm, কোন grammar
প্রতিটি generator-এর ভেতরে মডিউল ৫–৭-এর কোনো একটি algorithm. নিচের টেবিলে পরিচিত tool আর তাদের ভিত্তি; licence আর algorithm-এর দাবি প্রতিটি tool-এর নিজের নথি থেকে, আর যেগুলো এখানে চালানো হয়েছে তা চিহ্নিত।
| Tool | Algorithm | কোন grammar চলে | এখানে |
|---|---|---|---|
| yacc, Bison | LALR(1); Bison-এ GLR-ও | LALR(1), precedence ঘোষণাসহ | নাম শুধু |
| PLY, sly (Python) | LALR(1) | LALR(1) | পর্ব ৩৯ |
| Lark (Python, MIT) | LALR(1) অথবা Earley | LALR(1); Earley-তে যেকোনো CFG | চালানো |
| ANTLR 4 (BSD) | ALL(*), adaptive LL | প্রায় যেকোনো CFG, সরাসরি left recursion-সহ; indirect left recursion নয় | চালানো |
| PEG tool, CPython-এর pegen | PEG, প্রায়ই packrat | PEG (CFG নয়, আলাদা রীতি) | নিজের PEG |
| Parser combinator | সাধারণত recursive descent + backtracking | কোডে লেখা grammar | নিজের JS |
| tree-sitter | GLR-ধাঁচের LR, incremental | editor-এর জন্য, conflict ঘোষণা করে | নাম শুধু |
LR-পরিবারের tool-গুলো grammar-কে টেবিলে বদলায়, আর টেবিলের কোনো ঘরে দুটি কাজ পড়লে তা shift/reduce conflict বা reduce/reduce conflict. প্রশ্ন হলো, conflict আর ambiguity-র সম্পর্ক কী? Generator কি বলতে পারে “আপনার grammar ambiguous”? না, আর কারণটি গভীর: কোনো CFG ambiguous কি না, সেই প্রশ্ন সাধারণভাবে undecidable (পর্ব ২৭-এ উল্লেখ, প্রমাণ পর্ব ৫৪ “Post correspondence problem আর grammar-এর undecidable প্রশ্ন”-এ)। Generator তাই একটি decidable, যথেষ্ট শর্ত পরীক্ষা করে: টেবিলে conflict নেই।
যদি G-এর canonical LR(1) টেবিল বা LALR(1) টেবিলে কোনো conflict না থাকে, তাহলে G unambiguous. উল্টো দিক সত্য নয়: এমন unambiguous grammar আছে, যার কোনো k-এর জন্যই LR(k) টেবিল conflict-মুক্ত নয়।
প্রমাণের রূপরেখা:
- Conflict-মুক্ত টেবিলে প্রতিটি (state, lookahead) জোড়ায় বড়জোর একটি কাজ, তাই parser-এর প্রতিটি configuration থেকে পরের configuration অনন্য: যন্ত্রটি deterministic. — টেবিলের সংজ্ঞা
- LR parser-এর একটি গ্রহণকারী run একটি rightmost derivation-কে উল্টো দিক থেকে পড়ে: প্রতিটি reduce ঠিক একটি derivation-ধাপ। — পর্ব ৩৯-এর মূল ধারণা
- Canonical LR(1)-এর নির্মাণ নিশ্চিত করে, w-এর প্রতিটি rightmost derivation-এর জন্য parser-এর চলার একটি পথ আছে যা ঠিক সেই derivation অনুসরণ করে (প্রতিটি ধাপে handle আর এক token lookahead যে কাজ দাবি করে, সেটি টেবিলে আছে)। Knuth-এর ১৯৬৫ সালের প্রবন্ধে বা Aho–Lam–Sethi–Ullman-এর compiler বইয়ে এর পূর্ণ প্রমাণ। — নির্মাণের সঠিকতা, এখানে বাদ
- w-এর দুটি আলাদা parse tree থাকলে দুটি আলাদা rightmost derivation (পর্ব ২৬-এর সংযোগ), তাই ধাপ ৩ অনুযায়ী দুটি আলাদা run; কিন্তু ধাপ ১ অনুযায়ী run একটিই। বিরোধ, তাই G unambiguous. — পর্ব ২৬, ধাপ ১, ৩
- LALR(1) টেবিল canonical LR(1)-এর একই core-এর state জুড়ে বানানো; জোড়া দেওয়ায় শুধু lookahead-সেট বড় হয়, কোনো item হারায় না। তাই canonical টেবিলের যেকোনো conflict LALR টেবিলেও থাকে; LALR conflict-মুক্ত হলে canonical-ও conflict-মুক্ত, আর ধাপ ৪ খাটে। — LALR-এর নির্মাণ
- উল্টো দিকের পাল্টা-উদাহরণ: জোড় দৈর্ঘ্যের palindrome-এর grammar S → aSa ∣ bSb ∣ ε. এটি unambiguous (বাইরের অক্ষর থেকে ভেতরে প্রতিটি ধাপ বাধ্য)। কিন্তু এর language কোনো deterministic CFL নয় (পর্ব ৩৫), আর LR(k) grammar ঠিক DCFL-ই বর্ণনা করে (Knuth ১৯৬৫), তাই কোনো k-তে এই grammar LR(k) নয়। ∎
একটি সূক্ষ্ম কথা মনে রাখুন: নির্দিষ্ট k-এর জন্য “G কি LR(k)?” প্রশ্নটি decidable, কারণ টেবিল বানিয়ে দেখলেই হয়; কিন্তু “এমন কোনো k আছে কি যাতে G LR(k)?” প্রশ্নটি undecidable বলে পরিচিত। Generator তাই সবসময় একটি নির্দিষ্ট k (প্রায় সবসময় 1) ধরে কাজ করে। অংশ ৫-এ দেখবেন, Lark এই palindrome grammar-এর conflict কীভাবে জানায়।
৩ · Lark দিয়ে বাজারঘরের order-query interpreter
এবার পুরো একটি interpreter. বাজারঘরের admin panel-এর query ভাষা পর্ব ২২ থেকে চলছে: পর্ব ২২-এ তার token, পর্ব ২৫-এ তার grammar (Q → FIND order WHERE C, C → C OR T ∣ T, T → T AND F ∣ F, F → ( C ) ∣ amount R NUM ∣ district = STR ∣ status = STR), আর পর্ব ২৬-এ Lark দিয়ে তার গাছ। এখানে R-এ পর্ব ২২-এর ছয়টি তুলনা-চিহ্ন বসানো হলো, আর নতুন কাজ হলো গাছ থেকে উত্তর বের করা। কাজটি ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো: Python 3.12.13, Lark 1.3.1 (MIT licence; Erez Shinan-এর শুরু করা প্রকল্প)। Lark-এর উৎস-কোডে network বা usage-reporting-এর কোনো অংশ নেই, তা scratch-এ খুঁজে দেখা হয়েছে। প্রথমে grammar ফাইল:
// Bazarghar order-query language (grammar of lesson 25, six comparison signs of lesson 22)
query: "FIND" "order" "WHERE" cond
?cond: cond "OR" term -> or_
| term
?term: term "AND" fact -> and_
| fact
?fact: "(" cond ")"
| "amount" REL NUM -> amount
| "district" "=" STR -> district
| "status" "=" STR -> status
REL: ">=" | "<=" | "!=" | ">" | "<" | "="
NUM: /[0-9]+/
STR: /"[^"\n]*"/
%ignore /[ \t\r\n]+/Lark-এর রীতি পর্ব ২৬-এ দেখেছেন: ছোট হাতের নাম নিয়ম, বড় হাতের নাম terminal, উদ্ধৃতির লেখা নামহীন terminal (গাছে থাকে না)। নিয়মের আগে ? মানে এক-সন্তানের node মুছে সন্তানকে ওপরে তোলা, আর -> and_ node-এর নাম বদলানো। ফলে parse tree নিজেই প্রায় একটি AST. লক্ষ করুন, grammar-টি left-recursive (cond → cond "OR" term): LALR-এর জন্য তা কোনো সমস্যা নয়, বরং স্বাভাবিক (পর্ব ৩০-এ দেখেছেন, top-down parser-এ এটিই loop ঘটায়)। AND-এর নিয়ম OR-এর এক স্তর নিচে, তাই AND আগে বাঁধে।
অর্থের অংশটি একটি tree transformer: প্রতিটি নিয়মের নামে একটি method, যা সন্তানদের ইতিমধ্যে বদলানো মান পায় আর নিজের মান ফেরত দেয়। এখানে প্রতিটি node একটি ফাংশনে বদলায়, যা একটি অর্ডার নিয়ে True বা False দেয়। অর্ডারের টেবিল কাল্পনিক: seed 40 দিয়ে বানানো ২০০টি অর্ডার, BG-0001 থেকে BG-0200, প্রতিটিতে amount (১০০ থেকে ৫০০০ টাকা), আটটি বিভাগীয় শহরের একটি district আর চারটি status-এর একটি।
from importlib.metadata import version
import operator
from lark import Lark, Transformer
from orders import ORDERS # 200 invented orders, random.seed(40)
OPS = {">=": operator.ge, "<=": operator.le, "!=": operator.ne,
">": operator.gt, "<": operator.lt, "=": operator.eq}
class ToPredicate(Transformer): # AST node -> Python function(order) -> bool
def amount(self, kids):
rel, num = kids
op, n = OPS[str(rel)], int(num)
return lambda o: op(o["amount"], n)
def district(self, kids):
name = str(kids[0])[1:-1]
return lambda o: o["district"] == name
def status(self, kids):
name = str(kids[0])[1:-1]
return lambda o: o["status"] == name
def and_(self, kids):
a, b = kids
return lambda o: a(o) and b(o)
def or_(self, kids):
a, b = kids
return lambda o: a(o) or b(o)
def query(self, kids):
return kids[0]
parser = Lark.open("query.lark", start="query", parser="lalr")
def run(q):
pred = ToPredicate().transform(parser.parse(q))
return [o["id"] for o in ORDERS if pred(o)]
# __main__: print the tree of q1, then run(q) for four queriesসত্যিকারের run (ডেস্কটপ, Lark 1.3.1, Python 3.12.13; শেষের ছাপার লাইনগুলো বাদ দিয়ে দেখানো):
~/bazarghar-toc$ uv run python interp.py
lark 1.3.1 | orders: 200
query
and_
amount
>=
1000
district "Dhaka"
amount >= 1000 AND district = "Dhaka"
-> 25 orders: BG-0001, BG-0024, BG-0036, BG-0038 ...
status = "pending" OR amount < 200
-> 54 orders: BG-0001, BG-0002, BG-0013, BG-0017 ...
(status = "pending" OR amount < 200) AND district = "Sylhet"
-> 3 orders: BG-0033, BG-0116, BG-0147
status = "pending" OR amount < 200 AND district = "Sylhet"
-> 52 orders: BG-0001, BG-0002, BG-0013, BG-0017 ...
প্রথম query-র গাছে দুটি শর্ত একটি and_-এর নিচে। ২০০টির মধ্যে ১৫৮টি অর্ডারের amount অন্তত ১০০০, আর ৩১টি ঢাকার; দুটি একসঙ্গে ২৫টিতে। শেষ দুই query-র লেখা প্রায় এক, শুধু বন্ধনী আলাদা, অথচ উত্তর ৩ আর ৫২. বন্ধনী ছাড়া AND আগে বাঁধে: “pending, অথবা (সিলেটের ২০০ টাকার কম)”, তাই প্রায় সব pending অর্ডার আসে। এটি grammar-এর স্তর-ভাগের সরাসরি ফল (পর্ব ২৭), আর বাজারঘরের কর্মীর জন্য একটি বাস্তব বিপদ: ভুল বন্ধনীতে ভুল অর্ডারের তালিকা, কোনো error ছাড়াই।
নিচের stepper প্রথম query-টিকে পুরো পথে নিয়ে যায়। Token-এর নাম, state-এর সংখ্যা আর প্রতিটি অর্ডারের ফল একই প্রকল্পে Lark থেকে ছাপিয়ে মেলানো।
1query.lark পড়া2LALR টেবিল বানানো3lexer: token4parser: গাছ5transformer6BG-0001, BG-00027উত্তর
| কে কাজ করছে | |
| কী তৈরি হলো | |
| কখন চলে |
- Grammar পড়া। Generator EBNF-এর বিকল্পগুলো আলাদা নিয়মে খোলে: ৯টি নিয়ম (query একটি, cond দুটি, term দুটি, fact চারটি)। Terminal ১৪টি, আর একটি ফাঁকা-ঘরের নিয়ম, যা lexer বাদ দেবে।
- টেবিল বানানো। পর্ব ৩৯-এর LALR(1) নির্মাণ যন্ত্রে চলে: ২৪টি state, কোনো conflict নেই, তাই উপপাদ্য ২.১ অনুযায়ী grammar unambiguous. এই খরচ একবারই (এই কম্পিউটারে প্রায় ৯ মিলিসেকেন্ড)।
- Lexer.
FIND order WHERE amount >= 1000 AND district = "Dhaka"থেকে ১০টি token. লক্ষ করুন,>=হলো REL, কিন্তুdistrict-এর পরের=হলো EQUAL; কেন, অংশ ৪-এ। - Parser. টেবিল ধরে shift আর reduce; ? চিহ্নের কারণে cond আর term-এর এক-সন্তানের শিকল বাদ পড়ে, থাকে query-র নিচে and_, তার দুই সন্তান amount আর district.
- Transformer. নিচ থেকে ওপরে: amount হয় “o-এর amount ≥ 1000”, district হয় “o-এর district = Dhaka”, আর and_ দুটি ফাংশন জুড়ে একটি ফাংশন দেয়। Query আর লেখা নয়, এখন একটি Python ফাংশন।
- মূল্যায়ন। BG-0001-এর amount 3000, district Dhaka: দুটি শর্তই সত্য। BG-0002-এর amount 1900 হলেও district Rajshahi: and_ মিথ্যা। প্রতিটি অর্ডারে একই ফাংশন।
- উত্তর। ২০০টির মধ্যে ২৫টি অর্ডার। Grammar একবার লেখা, অথচ যেকোনো নতুন query-তে ধাপ ৩–৭ নিজে থেকে চলে; generator-এর আসল লাভ এটিই।
৪ · ভুল query আর ভালো error message
কর্মীরা ভুল query লিখবেনই। একটি ভালো parser শুধু “ভুল” বলে না; বলে কোথায় (line, column), কী পেয়েছে, আর কী আশা করেছিল। শেষ তালিকার নাম expected-token set: LR parser-এ এটি ভুল ধরার মুহূর্তের state-এর টেবিল-সারিতে যে token-এর কাজ আছে, সেগুলো। নিচের script চারটি ভাঙা query দেয়; তৃতীয়টি তিন লাইনে লেখা, শেষ বন্ধনী নেই।
from lark import UnexpectedInput, UnexpectedToken, UnexpectedEOF
from interp import run
BAD = ['FIND order WHERE amount >= AND district = "Dhaka"',
'FIND order WHERE amount >= 1000 @ 5',
'FIND order\nWHERE (amount > 500\n OR status = "paid"',
'FIND order WHERE district >= "Dhaka"']
for q in BAD:
try:
run(q)
except UnexpectedInput as e:
print(f"{type(e).__name__} at line {e.line}, column {e.column}")
if isinstance(e, (UnexpectedToken, UnexpectedEOF)):
print(" expected:", sorted(e.expected))
print(e.get_context(q).rstrip())সত্যিকারের run (একই প্রকল্প):
UnexpectedToken at line 1, column 28
expected: ['NUM']
FIND order WHERE amount >= AND district = "Dhaka"
^
UnexpectedCharacters at line 1, column 33
FIND order WHERE amount >= 1000 @ 5
^
UnexpectedToken at line 3, column 16
expected: ['OR', 'RPAR']
OR status = "paid"
^
UnexpectedToken at line 1, column 27
expected: ['EQUAL']
FIND order WHERE district >= "Dhaka"
^
প্রথমটিতে সংখ্যা নেই: col 28-এ AND পেয়ে parser বলছে শুধু NUM চলত। দ্বিতীয়টি lexer-এর ভুল (@ কোনো token-এর শুরু নয়), তাই expected-তালিকা নেই। চতুর্থটি দেখায় grammar কতটা কড়া: district-এর পরে শুধু = বৈধ। তৃতীয়টি সবচেয়ে শিক্ষণীয়, নিচের stepper-এ তার ব্যাখ্যা।
তৃতীয় query-তে input শেষ হয়েছে, তাই আসল token হলো “input শেষ” ($END); Lark এর অবস্থান হিসেবে শেষ token-এর ("paid") অবস্থান ধার করে, তাই line 3, column 16. কিন্তু expected-তালিকায় AND নেই, অথচ "paid"-এর পরে AND লেখা সম্পূর্ণ বৈধ ছিল! একই grammar-এ Earley parser (অংশ ৫) একই input-এ UnexpectedEOF দেয়, expected = AND, OR, RPAR. পার্থক্যের কারণ LALR-এর নির্মাণে: বন্ধনীর ভেতরের [term → term·AND fact] আর [cond → term·]-এর state আর বাইরের একই-core-এর state জুড়ে গেছে, ফলে [cond → term·]-এর lookahead-এ $END-ও ঢুকেছে। তাই $END দেখে parser আগে একটি বাড়তি reduce করে, তারপর ভুল ধরে এমন state-এ, যেখানে শুধু OR আর RPAR চলে। এটি LALR আর SLR-এর একটি পরিচিত বৈশিষ্ট্য: ভুল token কখনো shift হয় না, কিন্তু ভুল ধরার আগে কয়েকটি reduce হতে পারে; canonical LR(1) প্রথম সুযোগেই ধরে।
1token আর column2পাঁচটি shift3state-এর সারি4AND এলো: ভুল5caret বসানো6বন্ধনী ছাড়া শেষ7ANTLR-এর বার্তা
| stack (শেষ অংশ) | |
| পরের token | |
| expected |
- অবস্থান রাখা। Lexer প্রতিটি token-এর সঙ্গে line আর column (১ থেকে গোনা) রাখে: FIND col 1-এ,
>=col 25-এ, AND col 28-এ। Error message-এর সব তথ্য এখান থেকেই। - Shift. FIND, ORDER, WHERE, AMOUNT আর REL একে একে stack-এ; প্রতিটিতে টেবিলে একটি shift ছিল।
- সারিটি দেখা। REL-এর পরের state-এ টেবিলের সারিতে কাজ আছে শুধু NUM-এর জন্য। এই সারির token-গুলোই expected-তালিকা।
- ভুল ধরা। পরের token AND, যার জন্য সারিতে কোনো কাজ নেই। Parser থামে আর জানায়: UnexpectedToken, line 1, column 28, expected NUM.
- Caret.
get_contextলাইনটি ছাপে, তার নিচে ২৭টি ফাঁকা ঘর আর একটি ^, যা col 28-এর AND-কে দেখায়। কর্মী এক নজরে বোঝেন সংখ্যা বাদ পড়েছে। - বাড়তি reduce. তিন লাইনের query-তে $END আসে। জোড়া-দেওয়া LALR state-এ $END [cond → term·]-এর lookahead, তাই parser reduce করে, তারপর থামে ( cond-এর পরের state-এ: expected শুধু OR আর RPAR. বৈধ AND তালিকা থেকে হারাল।
- ANTLR-এর রীতি। অংশ ৬-এর ANTLR parser প্রথম query-তে লেখে “line 1:27 missing NUM at 'AND'”: column 0 থেকে গোনা, তাই 27; আর সে একটি NUM “আছে ধরে নিয়ে” বাকিটা পড়ে চলে, যাতে একবারে আরও ভুল ধরা যায়।
Contextual lexer. Stepper-এর ধাপ ৩-এ প্রশ্ন ছিল: একই = কেন কখনো REL, কখনো EQUAL? Lark-এর LALR-এ lexer নিজে থেকে contextual lexer: প্রতিটি parser-state-এ যে terminal বৈধ, শুধু সেগুলোর মধ্যে মেলায়। AMOUNT-এর পরে শুধু REL বৈধ, তাই = REL; DISTRICT-এর পরে শুধু EQUAL. একই grammar-এ lexer="basic" দিলে (পর্ব ২২-এর প্রথাগত, প্রসঙ্গ-না-জানা lexer) কী হয়, তা চালিয়ে দেখা হলো:
~/bazarghar-toc$ uv run python lexer_mode.py # parse 'FIND order WHERE amount = 5'
contextual amount
basic UnexpectedToken Unexpected token Token('EQUAL', '=') at line 1, column 25.
প্রসঙ্গ-না-জানা lexer =-কে সবসময় EQUAL বানায়, আর amount = 5 বৈধ query হয়েও ভুল বলে ধরা পড়ে। এটি পর্ব ২২-এর lexer–parser সীমানার একটি বাস্তব উদাহরণ: সীমানা পরিষ্কার না হলে grammar ঠিক থাকলেও parser ভুল ফল দেয়। সমাধান হয় contextual lexer, নয়তো grammar-এ =-কে একটিই terminal রাখা।
৫ · একই grammar, দুই algorithm — LALR বনাম Earley আর conflict
Lark-এ একটি শব্দ বদলালেই algorithm বদলায়: parser="lalr" না parser="earley". LALR(1) শুধু LALR(1) grammar মানে কিন্তু রৈখিক সময়ে চলে; Earley যেকোনো CFG মানে, ambiguous হলেও, কিন্তু সবচেয়ে খারাপ ক্ষেত্রে ঘন সময় (পর্ব ৪১-এ এর ভেতরের কাজ)। নিচের script seed 40 দিয়ে ৫০০টি এলোমেলো বৈধ query বানায় (নেস্টেড বন্ধনী, AND, OR, ছয় তুলনা-চিহ্ন), দুই parser-এ চালায়, আর গাছ মেলায়।
import time
from lark import Lark
from gen import queries # 500 random valid queries, seed 40
Q = queries(500)
toks = sum(len(q.split()) for q in Q)
print("queries:", len(Q), "| avg words:", round(toks / len(Q), 1),
"| longest:", max(len(q) for q in Q), "chars")
trees = {}
for algo in ["lalr", "earley"]:
t0 = time.perf_counter()
p = Lark.open("query.lark", start="query", parser=algo)
t1 = time.perf_counter()
trees[algo] = [p.parse(q) for q in Q]
t2 = time.perf_counter()
print(f"{algo:6} build {1000 * (t1 - t0):7.1f} ms | parse 500 {1000 * (t2 - t1):8.1f} ms")
print("identical trees:", trees["lalr"] == trees["earley"])সত্যিকারের run (ডেস্কটপ, Lark 1.3.1; তিনবার চালানো হয়েছে, এখানে প্রথমটি; বাকি দুইবারে LALR 17.8 ও 18.1 ms, Earley 248.2 ও 243.9 ms):
~/bazarghar-toc$ uv run python bench.py
queries: 500 | avg words: 11.7 | longest: 252 chars
lalr build 9.4 ms | parse 500 18.3 ms
earley build 2.0 ms | parse 500 239.6 ms
identical trees: True
৫০০টি query-র প্রতিটিতে দুই parser হুবহু একই গাছ দিয়েছে, কারণ grammar unambiguous আর দুটিই সঠিক। LALR টেবিল বানাতে বেশি সময় নেয় (৯ বনাম ২ মিলিসেকেন্ড), কিন্তু parse-এ প্রায় ১৩ গুণ দ্রুত। সময়ের অনুপাত মেশিনভেদে বদলাবে; ক্রমটি বদলায় না। বাজারঘরের মতো প্রতি সেকেন্ডে অনেক query-র সার্ভারে LALR স্বাভাবিক পছন্দ; grammar-এর খসড়া বানানোর সময় Earley সুবিধাজনক, কারণ conflict নিয়ে ভাবতে হয় না।
এবার উল্টো পরীক্ষা: grammar-এ যদি সমস্যা থাকে? পর্ব ২৭-এর ambiguous E → E+E ∣ E∗E ∣ (E) ∣ id আর অংশ ২-এর palindrome grammar LALR আর Earley দুটিতেই দেওয়া হলো। show গাছটিকে পুরো বন্ধনীসহ লেখে।
import logging
from lark import Lark, Tree, logger
from lark.exceptions import UnexpectedInput
AMBIG = r"""
e: e "+" e | e "*" e | "(" e ")" | ID
ID: "id"
"""
PAL = r"""
s: "a" s "a" | "b" s "b" |
"""
logger.setLevel(logging.DEBUG) # lark reports LALR conflicts at debug level
def show(t): # parse tree -> fully bracketed text
if not isinstance(t, Tree):
return str(t)
parts = [show(k) for k in t.children]
return "(" + "".join(parts) + ")" if len(parts) == 3 else "".join(parts)
for name, g, start, words in [("ambiguous E", AMBIG, "e", ["id+id*id", "id*id+id"]),
("palindromes", PAL, "s", ["abba"])]:
print("==", name)
p = Lark(g, start=start, parser="lalr", debug=True, keep_all_tokens=True)
for w in words:
try:
print(" lalr on", w, "->", show(p.parse(w)))
except UnexpectedInput as e:
print(" lalr on", w, "->", type(e).__name__, "at column", e.column)
q = Lark(g, start=start, parser="earley", ambiguity="explicit")
print(" earley on", words[0], "->", q.parse(words[0]).data)সত্যিকারের run (একই প্রকল্প; conflict-এর লাইনগুলো Lark-এর log, তাদের ক্রম run ভেদে বদলাতে পারে):
~/bazarghar-toc$ uv run python -u conflicts.py
== ambiguous E
Shift/Reduce conflict for terminal STAR: (resolving as shift)
* <e : e STAR e>
Shift/Reduce conflict for terminal PLUS: (resolving as shift)
* <e : e STAR e>
Shift/Reduce conflict for terminal STAR: (resolving as shift)
* <e : e PLUS e>
Shift/Reduce conflict for terminal PLUS: (resolving as shift)
* <e : e PLUS e>
lalr on id+id*id -> (id+(id*id))
lalr on id*id+id -> (id*(id+id))
earley on id+id*id -> _ambig
== palindromes
Shift/Reduce conflict for terminal B: (resolving as shift)
* <s : >
Shift/Reduce conflict for terminal A: (resolving as shift)
* <s : >
lalr on abba -> UnexpectedToken at column 4
earley on abba -> s
তিনটি শিক্ষা। প্রথম: Lark কোনো exception দেয়নি; চারটি shift/reduce conflict পেয়ে প্রতিটিতে নিজে “shift” বেছেছে, আর খবরটি শুধু debug log-এ, যা সাধারণ চালনায় চোখে পড়ে না। দ্বিতীয়: “সবসময় shift” মানে সব operator ডান দিকে জোড়া লাগে, তাই id*id+id হলো id∗(id+id), গণিতের নিয়মে ভুল; এর সঠিক সমাধান precedence ঘোষণা বা পর্ব ২৭-এর স্তর-ভাগ। Earley একই input-এ _ambig node দিয়ে স্বীকার করে যে দুটি গাছ আছে। তৃতীয়: palindrome grammar unambiguous (Earley একটি গাছই দিয়েছে), তবু LALR-এ conflict, আর “shift”-এর সমাধানে বৈধ abba-ও প্রত্যাখ্যাত: উপপাদ্য ২.১-এর উল্টো দিক মিথ্যা, তার জীবন্ত প্রমাণ।
নিয়মটি মনে রাখুন: নতুন grammar-এ LALR চালানোর সময় conflict-এর রিপোর্ট সবসময় খুলে পড়ুন (Lark-এ debug=True আর log-এর স্তর, yacc/Bison-এ সতর্কবার্তা আর -v-এর রিপোর্ট ফাইল)। “Table তৈরি হয়েছে” মানে “grammar ঠিক আছে” নয়।
৬ · ANTLR 4 — ALL(*), left recursion আর visitor
ANTLR (ANother Tool for Language Recognition) Terence Parr-এর দীর্ঘদিনের প্রকল্প; বর্তমান রূপ ANTLR 4, প্রথম প্রকাশ ২০১৩ সালের দিকে। এটি Java-তে লেখা, কিন্তু Java, Python, JavaScript, C#, Go, C++-সহ অনেক ভাষায় parser বানায়। এর ভেতরে top-down parsing, কিন্তু LL(1) নয়: ALL(*) (Adaptive LL(*); Parr, Harwell আর Fisher-এর ২০১৪ সালের OOPSLA প্রবন্ধ)। প্রতিটি সিদ্ধান্তে, অর্থাৎ কোন বিকল্প নেওয়া হবে, parser প্রয়োজনমতো যত token দরকার তত দূর সামনে দেখে; বিকল্পগুলোকে grammar-এর একটি automaton-এ একসঙ্গে চালিয়ে দেখে কোনটি টিকে থাকে, আর ফল একটি DFA-cache-এ রাখে, যাতে একই পরিস্থিতিতে পরের বার সঙ্গে সঙ্গে সিদ্ধান্ত হয়। প্রবন্ধে তত্ত্বে সবচেয়ে খারাপ সময় O(n4) বলা হয়, কিন্তু বাস্তব grammar-এ প্রায় রৈখিক আচরণের দাবি করা হয়; দুটিই প্রবন্ধের নিজের দাবি হিসেবে পড়ুন।
এখানে ANTLR সত্যিই চালানো হয়েছে। এই কম্পিউটারে Java নেই, তাই lab-এ একটি portable Eclipse Temurin 21.0.13 JRE (GPLv2 + Classpath Exception licence, শুধু চালানোর জন্য, কাজ শেষে মুছে ফেলা) আর ANTLR 4.13.2-এর jar (BSD licence) রাখা হয়; Python দিকে antlr4-python3-runtime 4.13.2 (BSD). Grammar ফাইল:
grammar Query;
query : 'FIND' 'order' 'WHERE' cond EOF ;
cond : cond 'AND' cond # And
| cond 'OR' cond # Or
| '(' cond ')' # Paren
| 'amount' op=(REL | '=') NUM # Amount
| 'district' '=' STR # District
| 'status' '=' STR # Status
;
REL : '>=' | '<=' | '!=' | '>' | '<' ;
NUM : [0-9]+ ;
STR : '"' ~["\n]* '"' ;
WS : [ \t\r\n]+ -> skip ;এখানে দুটি জিনিস লক্ষ করুন। প্রথম, cond একটি সরল, ambiguous-চেহারার নিয়ম: cond 'AND' cond. ANTLR 4 সরাসরি left recursion মেনে নেয়: নিয়মটিকে ভেতরে একটি precedence-climbing loop-এ বদলায়, যেখানে বিকল্পের ক্রমই precedence: আগে লেখা And, তাই AND বেশি শক্তভাবে বাঁধে, আর স্বাভাবিকভাবে বাঁ-associative. তবে ANTLR-এর নথি অনুযায়ী indirect left recursion (A → B…, B → A…) এখনো চলে না; সেটি পর্ব ৩০-এর পদ্ধতিতে হাতে সরাতে হয়। দ্বিতীয়, ANTLR-এর lexer প্রসঙ্গ জানে না, তাই = সবসময় একটি token; Amount-এর বিকল্পে তাই (REL | '=') লেখা হয়েছে, অংশ ৪-এর সমস্যার ANTLR-রীতির সমাধান।
ANTLR গাছের ওপর কাজের জন্য দুই কাঠামো বানায়: listener (গাছ ঘোরার সময় প্রতিটি node-এ ঢোকা ও বেরোনোর ঘটনা) আর visitor (প্রতিটি # লেবেলের জন্য একটি visit পদ্ধতি, যা মান ফেরত দেয়)। Evaluator-এর জন্য visitor স্বাভাবিক:
# generated first: java -Xmx256m -jar antlr-4.13.2-complete.jar \
# -Dlanguage=Python3 -visitor -no-listener Query.g4
class Eval(QueryVisitor): # one method per labelled alternative
def __init__(self, order): self.o = order
def visitQuery(self, ctx): return self.visit(ctx.cond())
def visitAnd(self, ctx): return self.visit(ctx.cond(0)) and self.visit(ctx.cond(1))
def visitOr(self, ctx): return self.visit(ctx.cond(0)) or self.visit(ctx.cond(1))
def visitParen(self, ctx): return self.visit(ctx.cond())
def visitAmount(self, ctx): return OPS[ctx.op.text](self.o["amount"], int(ctx.NUM().getText()))
def visitDistrict(self, ctx): return self.o["district"] == ctx.STR().getText()[1:-1]
def visitStatus(self, ctx): return self.o["status"] == ctx.STR().getText()[1:-1]
def parse(q):
p = QueryParser(CommonTokenStream(QueryLexer(InputStream(q))))
return p, p.query()
def antlr_run(q):
p, tree = parse(q)
return [o["id"] for o in ORDERS if Eval(o).visit(tree)]
print("antlr4-python3-runtime", version("antlr4-python3-runtime"))
q = 'FIND order WHERE status = "pending" OR amount < 200 AND district = "Sylhet"'
p, tree = parse(q)
print(tree.toStringTree(recog=p))
print("answers:", len(antlr_run(q)), "(lark:", len(lark_run(q)), ")")
Q = queries(500) # the same 500 random queries as bench.py
print("same answers on", sum(antlr_run(x) == lark_run(x) for x in Q), "/ 500 random queries")
print("-- syntax error:")
parse('FIND order WHERE amount >= AND district = "Dhaka"')সত্যিকারের run (ডেস্কটপ, Temurin 21.0.13 JRE-তে ANTLR 4.13.2 tool, Python 3.12.13; tool-টি কোনো লেখা ছাপেনি, শুধু QueryLexer.py, QueryParser.py, QueryVisitor.py আর কয়েকটি .interp/.tokens ফাইল বানিয়েছে; import-এর লাইন বাদ দিয়ে দেখানো):
~/bazarghar-toc$ uv run python -u antlr_run.py
antlr4-python3-runtime 4.13.2
(query FIND order WHERE (cond (cond status = "pending") OR (cond (cond amount < 200) AND (cond district = "Sylhet"))) <EOF>)
answers: 52 (lark: 52 )
same answers on 500 / 500 random queries
-- syntax error:
line 1:27 missing NUM at 'AND'
গাছে OR সবচেয়ে ওপরে, AND তার ডান সন্তানে: বিকল্পের ক্রম থেকে আসা precedence ঠিক কাজ করেছে, আর উত্তর ৫২, Lark-এর সঙ্গে এক। দুটি সম্পূর্ণ আলাদা algorithm (bottom-up LALR আর top-down ALL(*)), আলাদা grammar-রীতি, আলাদা runtime, অথচ ৫০০টি এলোমেলো query-র প্রতিটিতে একই অর্ডার-তালিকা। দুই স্বাধীন বাস্তবায়নে মেলানো, যাকে differential testing বলে, নিজের parser যাচাইয়ের সবচেয়ে কার্যকর উপায়গুলোর একটি। শেষ লাইনে ANTLR-এর error: column 0 থেকে গোনা (Lark-এর col 28-এর সমান) আর “missing NUM”, অর্থাৎ একটি token যোগ করে চলতে থাকার কৌশল।
৭ · PEG আর packrat — ordered choice-এর ফাঁদ
২০০৪ সালে Bryan Ford (POPL সম্মেলনের প্রবন্ধে) parsing expression grammar বা PEG প্রস্তাব করেন। চেহারায় EBNF-এর মতো, কিন্তু অর্থ আলাদা। CFG-এর A → α ∣ β বলে “A হতে পারে α অথবা β”; এটি একটি বর্ণনা, যন্ত্র নয়। PEG-এর A ← e1 / e2 একটি নির্দেশ: “আগে e1 চেষ্টা করুন; সফল হলে সেটিই, আর কখনো ফিরে আসবেন না; ব্যর্থ হলে একই জায়গা থেকে e2.” এটিই ordered choice. ফলে PEG কখনো ambiguous নয় (প্রতিটি input-এ বড়জোর একটি ফল), আর একটি recursive-descent parser সরাসরি তার অর্থ। Python 3.9 থেকে CPython-এর নিজের parser একটি PEG থেকে বানানো (PEP 617; Guido van Rossum, Pablo Galindo আর Lysandros Nikolaou); পুরোনো LL(1) parser 3.10-এ বাদ যায়।
রেলস্টেশনের টিকিট কাউন্টারে লাইনের নিয়ম ভাবুন: “প্রথম কাউন্টারে টিকিট পেলে সেটিই নিন, আর অন্য কাউন্টারে যাবেন না।” প্রথম কাউন্টার আপনাকে লোকাল ট্রেনের টিকিট দিল, পরে প্ল্যাটফর্মে দেখলেন আপনার দরকার ছিল আন্তঃনগরের। নিয়ম অনুযায়ী আর ফেরার উপায় নেই, যাত্রা ব্যর্থ। দ্বিতীয় কাউন্টারে ঠিক টিকিট ছিল, কিন্তু সেখানে যাওয়াই হলো না। Ordered choice ঠিক এই নিয়ম।
নিচের ব্লকে একটি ছোট PEG-interpreter: grammar একটি Python dict, আর peg ফাংশন সেটি থেকে একটি parser বানায়; একটি খুদে generator. বাজারঘরের query-র তুলনা-চিহ্ন দুই ক্রমে লেখা হয়েছে।
# A PEG as data: ("/", e1, e2, ...) ordered choice, ("seq", e1, ...) sequence,
# "NUM" one or more digits, a rule name -> its expression, any other str a literal.
def peg(G):
def m(e, s, i): # match e at position i -> new position or None
if isinstance(e, str) and e in G:
return m(G[e], s, i)
if isinstance(e, str):
i = len(s) - len(s[i:].lstrip()) # skip spaces before a token
if e == "NUM":
j = i
while j < len(s) and s[j].isdigit(): j += 1
return j if j > i else None
return i + len(e) if s.startswith(e, i) else None
if e[0] == "seq":
for x in e[1:]:
i = m(x, s, i)
if i is None: return None
return i
for x in e[1:]: # "/": the first success wins, never retried
j = m(x, s, i)
if j is not None: return j
return None
return lambda s: m("Query", s, 0) == len(s)
def query_peg(rel):
return peg({"Query": ("seq", "FIND", "order", "WHERE", "amount", "Rel", "NUM"),
"Rel": ("/",) + tuple(rel)})
short, long_ = query_peg(["=", ">", ">=", "<"]), query_peg([">=", "=", ">", "<"])
for q in ["FIND order WHERE amount = 5", "FIND order WHERE amount > 5",
"FIND order WHERE amount >= 5"]:
print(f"{q[17:]:12} short-first: {short(q)!s:5} long-first: {long_(q)}")
ab = peg({"Query": ("seq", ("/", "a", "ab"), "c")}) # L(e1/e2) vs L(e1) U L(e2)
ba = peg({"Query": ("seq", ("/", "ab", "a"), "c")})
for w in ["ac", "abc"]:
print(f'("a"/"ab") "c" on {w}: {ab(w)!s:5} ("ab"/"a") "c" on {w}: {ba(w)}')আসল আউটপুট (ব্রাউজারের Python):
amount = 5 short-first: True long-first: True
amount > 5 short-first: True long-first: True
amount >= 5 short-first: False long-first: True
("a"/"ab") "c" on ac: True ("ab"/"a") "c" on ac: True
("a"/"ab") "c" on abc: False ("ab"/"a") "c" on abc: True
ছোট চিহ্ন আগে রাখলে (">" আগে, ">=" পরে) amount >= 5 বৈধ হয়েও প্রত্যাখ্যাত; লম্বাটি আগে রাখলে সব ঠিক। নিচের দুই লাইন তত্ত্বের কথাটি সবচেয়ে ছোট উদাহরণে দেখায়: ("a"/"ab")"c" “abc” মানে না, যদিও CFG-এর (a ∪ ab)c ঠিকই মানত। সংক্ষেপে, PEG-এ e1/e2 সাধারণভাবে union নয়, আর বিকল্পের ক্রম বদলালে language বদলায়। এটি পর্ব ২২-এর maximal munch-এর উল্টো ছবি: সেখানে lexer সবসময় লম্বাটি খোঁজে, এখানে PEG প্রথমটি নেয়।
1FIND order WHERE amount2Rel: "=" চেষ্টা3Rel: ">" চেষ্টা4Rel শেষ: 255NUM at 256Query ব্যর্থ7">=" আগে রাখলে
| এখানে আছি | |
| সামনে লেখা | |
| ফল |
- Sequence. Query একটি seq: FIND, order, WHERE, amount মেলে; অবস্থান 0 থেকে 23-এ (amount-এর শেষে)।
- প্রথম বিকল্প। Rel ← "=" / ">" / ">=" / "<". ফাঁকা ঘর বাদ দিয়ে 24-এ আছে “>”; "=" মেলে না, তাই পরের বিকল্প।
- দ্বিতীয় বিকল্প। ">" মেলে। PEG-এর নিয়মে এটিই Rel-এর ফল।
- Choice বন্ধ। Rel 25 ফেরত দেয়। ">=" বিকল্পটি তালিকায় থাকলেও কখনো চেষ্টা হয়নি, হবেও না।
- NUM. 25-এ আছে “=”, অঙ্ক নয়। NUM ব্যর্থ, তাই পুরো seq ব্যর্থ।
- ফেরার পথ নেই। একটি CFG-parser বা backtracking regex এখানে Rel-এর পরের বিকল্প চেষ্টা করত। PEG-এ ব্যর্থতা ওপরে ওঠে, Rel-এর ভেতরে ফেরে না। ফল False.
- সমাধান। লম্বা চিহ্ন আগে: Rel ← ">=" / "=" / ">" / "<". এখন 24 থেকে ">=" মিলে 26, NUM ফাঁকা বাদ দিয়ে 27-এ 5 পড়ে 28-এ, যা input-এর দৈর্ঘ্য। ফল True.
Packrat. PEG-এর parser সরাসরি recursive descent with backtracking, আর backtracking-এর খরচ exponential হতে পারে: একই rule একই অবস্থানে বারবার চলে। Ford-এর আগের কাজ (২০০২) এর সমাধান দেয়: packrat parsing, অর্থাৎ প্রতিটি (rule, অবস্থান) জোড়ার ফল একটি টেবিলে রেখে দেওয়া। এটি memoization, আর DSA কোর্সের পর্ব ৫২-এর dynamic programming-এর একই ধারণা। নিচের ব্লকে একটি grammar, যার প্রথম দুই বিকল্প একই ভেতরের P পুরোটা পড়ে শুধু শেষ অক্ষরে আলাদা হয়।
# PEG: P <- "(" P ")" "x" / "(" P ")" "y" / "a"
# Both first alternatives parse the same inner P; only the last symbol differs.
def make_parser(memo):
cache, stats = {}, {"evaluations": 0}
def P(s, i): # returns the end position or None
if memo and i in cache:
return cache[i]
stats["evaluations"] += 1
res = None
for last in "xy": # ordered choice: try "x" first, then "y"
if i < len(s) and s[i] == "(":
j = P(s, i + 1)
if j is not None and s[j:j + 2] == ")" + last:
res = j + 2
break
if res is None and i < len(s) and s[i] == "a":
res = i + 1
if memo:
cache[i] = res
return res
return P, stats, cache
print(" d length plain PEG packrat memo entries")
for d in [1, 2, 4, 8, 12, 16]:
s = "(" * d + "a" + ")y" * d
row = []
for memo in (False, True):
P, stats, cache = make_parser(memo)
assert P(s, 0) == len(s) # the whole input is accepted
row.append(stats["evaluations"])
print(f"{d:2} {len(s):8} {row[0]:11} {row[1]:9} {len(cache):14}")আসল আউটপুট (ব্রাউজারের Python):
d length plain PEG packrat memo entries
1 4 3 2 2
2 7 7 3 3
4 13 31 5 5
8 25 511 9 9
12 37 8191 13 13
16 49 131071 17 17
গভীরতা d-তে সরল PEG ঠিক 2d+1 − 1 বার P হিসাব করে (d = 16-এ ১,৩১,০৭১), কারণ প্রতিটি স্তরে ভেতরের P দুবার পুরো পড়া হয়: T(d) = 1 + 2T(d − 1), T(0) = 1. Packrat-এ প্রতিটি অবস্থান একবার: d + 1. Input-এর দৈর্ঘ্য 3d + 1, তাই packrat-এর কাজ দৈর্ঘ্যের রৈখিক অনুপাতে, আর সরল PEG-এর কাজ exponential. নিচের উপপাদ্য এটি সাধারণভাবে বলে।
ধরুন একটি PEG-এ r-টি rule, প্রতিটি rule-এর expression-এর আকার বড়জোর c (ধ্রুবক), আর grammar-এ কোনো left recursion নেই (কোনো rule input না পড়েই নিজেকে আবার ডাকে না)। তাহলে দৈর্ঘ্য n-এর input-এ packrat parser বড়জোর r(n + 1)টি (rule, অবস্থান) হিসাব করে, আর মোট সময় O(r · c · n), অর্থাৎ নির্দিষ্ট grammar-এ O(n).
প্রমাণ:
- Left recursion নেই বলে প্রতিটি rule-call শেষ হয়: কোনো (rule, অবস্থান) জোড়া নিজের হিসাবের ভেতরে নিজেকে আবার ডাকে না, তাই হিসাব একটি সসীম recursion-গাছ। — শর্ত
- (rule, অবস্থান) জোড়া বড়জোর r(n + 1)টি: r-টি rule আর 0 থেকে n পর্যন্ত n + 1টি অবস্থান। — গণনা
- প্রতিটি জোড়ার প্রথম call-এর পর ফল টেবিলে থাকে; পরের প্রতিটি call O(1) সময়ে টেবিল থেকে উত্তর পায়। তাই আসল হিসাব বড়জোর r(n + 1)বার। — memoization
- একটি rule-এর expression হিসাবের সময়, ভেতরের rule-call-গুলো বাদে, তার আকারের অনুপাতে: প্রতিটি literal, sequence-এর ধাপ বা choice-এর বিকল্প একবার করে ছোঁয়া, আর প্রতিটি ছোঁয়া O(1) (literal-এর দৈর্ঘ্য grammar-এর ধ্রুবক)। তাই প্রতি হিসাবে O(c) কাজ আর বড়জোর c-টি rule-call. — expression-এর আকার
- মোট কাজ ≤ r(n + 1) · O(c) (হিসাব) + r(n + 1) · c · O(1) (টেবিল-দেখা) = O(r · c · n). ∎ — যোগ
দাম মেমরি: টেবিলে r(n + 1)টি ঘর, যা বড় ফাইলে অনেক। তাই অনেক বাস্তব PEG tool সব rule memo করে না, বেছে বেছে করে। আর left recursion: প্রথম ধাপের শর্ত না মানলে P(i) আবার P(i) ডাকে, আর parser কখনো থামে না। PEG-এ left recursion-এর জন্য পরে বিশেষ কৌশল এসেছে (Warth ও সহকর্মীদের ২০০৮ সালের প্রবন্ধ প্রায়ই উল্লেখ করা হয়), আর CPython-এর pegen এমন একটি কৌশল ব্যবহার করে; পর্ব ৩০-এর শেষে এর কথা আছে।
৮ · Parser combinator, tree-sitter আর tool বাছাই
Generator ছাড়াও parser বানানো যায়। Parser combinator-এ প্রতিটি ছোট parser একটি সাধারণ ফাংশন: (লেখা, অবস্থান) নিয়ে (মান, নতুন অবস্থান) বা ব্যর্থতা দেয়। তারপর seq, alt, many-এর মতো “combinator” ফাংশন ছোট parser জুড়ে বড় parser বানায়। Grammar তখন ভাষার নিজের কোড: আলাদা ফাইল নেই, build-এর ধাপ নেই, আর প্রতিটি নিয়মের পাশে মান হিসাবের কোড সরাসরি বসে। Haskell-এর Parsec লাইব্রেরি (২০০০-এর দশকের শুরুতে Daan Leijen-এর কাজ) এই ধারাকে জনপ্রিয় করে বলে উল্লেখ করা হয়। নিচের JavaScript ব্লকে প্রায় ২০ লাইনে বাজারঘরের পুরো query-parser আর evaluator; লক্ষ করুন, alt প্রথম সফল বিকল্প নেয়, অর্থাৎ এটি আসলে একটি PEG, আর left recursion এড়াতে C → C OR T-এর বদলে “T, তারপর (OR T)-এর শূন্য বা বেশি পুনরাবৃত্তি” লেখা হয়েছে।
// A parser is a function (s, i) => [value, nextIndex] or null.
let far = 0; // furthest position reached, for errors
const tok = re => (s, i) => {
const m = new RegExp("\\s*(" + re + ")", "y"); m.lastIndex = i;
const r = m.exec(s); if (!r) { far = Math.max(far, i); return null; }
return [r[1], m.lastIndex]; };
const seq = (...ps) => (s, i) => { const out = [];
for (const p of ps) { const r = p(s, i); if (!r) return null; out.push(r[0]); i = r[1]; }
return [out, i]; };
const alt = (...ps) => (s, i) => { for (const p of ps) { const r = p(s, i); if (r) return r; } return null; };
const many = p => (s, i) => { const out = []; let r;
while ((r = p(s, i))) { out.push(r[0]); i = r[1]; } return [out, i]; };
const map = (p, f) => (s, i) => { const r = p(s, i); return r && [f(r[0]), r[1]]; };
const lazy = f => (s, i) => f()(s, i); // allows recursion: cond inside fact
const OPS = { ">=": (a, b) => a >= b, "<=": (a, b) => a <= b, "!=": (a, b) => a != b,
">": (a, b) => a > b, "<": (a, b) => a < b, "=": (a, b) => a == b };
const str = map(tok('"[^"]*"'), t => t.slice(1, -1));
const fact = alt(map(seq(tok("\\("), lazy(() => cond), tok("\\)")), r => r[1]),
map(seq(tok("amount"), tok(">=|<=|!=|>|<|="), tok("[0-9]+")), ([, op, n]) => o => OPS[op](o.amount, +n)),
map(seq(tok("district"), tok("="), str), ([, , v]) => o => o.district === v),
map(seq(tok("status"), tok("="), str), ([, , v]) => o => o.status === v));
const chain = (p, kw, join) => map(seq(p, many(seq(tok(kw), p))),
([first, rest]) => rest.reduce((acc, [, q]) => join(acc, q), first));
const term = chain(fact, "AND", (a, b) => o => a(o) && b(o));
const cond = chain(term, "OR", (a, b) => o => a(o) || b(o));
const query = seq(tok("FIND"), tok("order"), tok("WHERE"), cond, tok("$"));
const ORDERS = [["BG-0001", 3000, "Dhaka", "pending"], ["BG-0002", 1900, "Rajshahi", "pending"],
["BG-0003", 4950, "Barishal", "delivered"], ["BG-0004", 4850, "Mymensingh", "paid"]]
.map(([id, amount, district, status]) => ({ id, amount, district, status }));
for (const q of ['FIND order WHERE amount >= 2000 AND status = "pending"',
'FIND order WHERE status = "paid" OR district = "Dhaka"',
'FIND order WHERE amount >= 2000 AND (status = "x"']) {
far = 0; const r = query(q, 0);
console.log(r ? ORDERS.filter(r[0][3]).map(o => o.id).join(" ") || "(none)"
: "syntax error near column " + (far + 1)); }আসল আউটপুট (ব্রাউজারের JavaScript; অর্ডার চারটি Lark-এর টেবিলের প্রথম চারটি):
BG-0001
BG-0001 BG-0004
syntax error near column 50
প্রথম query-তে ২০০০-এর বেশি আর pending শুধু BG-0001 (BG-0002-এর amount 1900). দ্বিতীয়টিতে paid (BG-0004) অথবা ঢাকা (BG-0001). তৃতীয়টির শেষ বন্ধনী নেই; combinator-এর কোনো টেবিল নেই, তাই কোন token আশা করা হয়েছিল তা সে জানে না। এখানে প্রচলিত কৌশল ব্যবহার করা হয়েছে: যত দূর পর্যন্ত কোনো parser পৌঁছেছিল (far), সেই অবস্থানকে ভুলের জায়গা বলা; 49 অক্ষরের query-তে column 50, ঠিক শেষের পরে। Combinator-এর দাম এটিই: লেখা সহজ, কিন্তু ভালো error message, left recursion আর গতির দায় নিজের।
tree-sitter আর incremental parsing. Code editor-এর প্রয়োজন আলাদা: প্রতিটি অক্ষর লেখার সঙ্গে সঙ্গে editor-কে রং, ভাঁজ আর কাঠামো বদলাতে হয়, আর লেখা প্রায় সবসময় অর্ধেক-ভুল অবস্থায় থাকে। Max Brunsfeld-এর tree-sitter (২০১৮ সালে GitHub-এর Atom দলে থাকার সময় প্রকাশিত) এই কাজের জন্য: grammar থেকে একটি LR-ভিত্তিক parser বানায়, যা grammar-এ ঘোষিত conflict-এর জায়গায় GLR-এর মতো একাধিক পথ চালায় (পর্ব ৪১-এ GLR), আর একটি সম্পাদনার পর পুরোনো গাছের যে অংশ বদলায়নি তা পুনর্ব্যবহার করে শুধু বদলানো জায়গা নতুন করে parse করে। ভুল থাকলেও সে গাছ দেয়, ভুলের জায়গায় একটি ERROR node রেখে। বিস্তারিত দাবিগুলো tree-sitter-এর নিজের নথিতে মিলিয়ে নিন।
| পরিস্থিতি | স্বাভাবিক পছন্দ | কেন |
|---|---|---|
| ছোট DSL, Python-এ, দ্রুত খসড়া | Lark Earley, পরে LALR | আগে conflict ছাড়া চালু, পরে গতি |
| অনেক ভাষার target, বড় grammar, tooling | ANTLR 4 | সরাসরি left recursion, visitor, ভালো error recovery |
| C/C++ প্রকল্প, পুরোনো ঐতিহ্য | Bison (LALR বা GLR) | পরীক্ষিত, precedence ঘোষণা |
| Program-এর ভেতরে ছোট format | Parser combinator | আলাদা build নেই, কোডেই grammar |
| Editor-এর রং আর কাঠামো | tree-sitter | incremental, ভুল-সহিষ্ণু |
| বড় compiler, সেরা error message | হাতে লেখা recursive descent | পূর্ণ নিয়ন্ত্রণ (ভাবনার প্রশ্ন ৩) |
আরও গভীরে: PEG-এর language-শ্রেণি CFL থেকে আলাদা: Ford ২০০৪ সালে দেখান, syntactic predicate (“সামনে এটা আছে কি না দেখা, কিন্তু না পড়া”)-সহ PEG anbncn-এর মতো non-context-free language চিনতে পারে, আর প্রতিটি PEG language রৈখিক সময়ে চেনা যায়। অন্যদিকে, প্রতিটি CFL কোনো PEG দিয়ে চেনা যায় কি না, প্রশ্নটি Ford খোলা প্রশ্ন হিসেবে রাখেন, আর সাধারণভাবে এটি এখনো অমীমাংসিত বলে উল্লেখ করা হয়। CFL-এর parsing দ্রুততম কতটা হতে পারে, তাও খোলা: Valiant-এর algorithm matrix গুণের সময়ে চলে (পর্ব ৩১), আর Lee (২০০২) দেখান, দ্রুত CFG parsing থেকে দ্রুত Boolean matrix গুণ পাওয়া যায়।
পরীক্ষা ও ইন্টারভিউতে:
- yacc/Bison কোন parsing পদ্ধতি ব্যবহার করে? — LALR(1) (Bison-এ GLR-ও বেছে নেওয়া যায়)।
- Conflict-মুক্ত LALR(1) টেবিল কী নিশ্চিত করে? — Grammar unambiguous আর parse রৈখিক সময়ে; উল্টোটি নয়।
- ANTLR 4 left recursion সামলায়? — সরাসরি left recursion হ্যাঁ (precedence-climbing-এ বদলে), indirect নয়।
- PEG-এর A ← a / ab আর CFG-এর A → a ∣ ab কি এক? — না; ordered choice-এ ab-এর বিকল্প কখনো চেষ্টা নাও হতে পারে।
- Packrat parsing-এর সময় আর মেমরি? — Left recursion ছাড়া নির্দিষ্ট grammar-এ দুটিই O(n).
৯ · AI-এর যুগে parser generator
AI assistant grammar আর parser লেখায় সত্যিই দ্রুত, আর প্রথম দুই-তিনটি উদাহরণে প্রায় সবসময় ঠিক চলে। ভুল লুকিয়ে থাকে precedence-এ, বিকল্পের ক্রমে আর tool-এর নীরব সিদ্ধান্তে। বারবার দেখা ভুলগুলো:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| AND আর OR একই স্তরে, ফলে ভুল precedence আর ভুল উত্তর | বন্ধনীসহ আর বন্ধনী ছাড়া একই query-র উত্তর তুলনা |
| LALR-এ “table তৈরি হয়েছে, তাই grammar ঠিক” | conflict-এর log খুলে পড়া; Earley-র _ambig খোঁজা |
PEG বা combinator-এ ছোট বিকল্প আগে (">" / ">=") | প্রতিটি দীর্ঘ চিহ্ন আলাদা করে পরীক্ষা |
| Recursive descent বা PEG-এ left-recursive নিয়ম, ফলে অসীম recursion | পর্ব ৩০-এর পদ্ধতিতে নিয়ম পরীক্ষা; ছোট input-এ depth-সীমা |
| ANTLR-এর indirect left recursion বা অস্তিত্বহীন option-এর দাবি | ANTLR-এর নিজের নথি আর আসল tool চালানো |
| “PEG সব CFG-এর মতোই শক্তিশালী” বা “ANTLR LL(1)”-এর মতো ভুল তত্ত্ব | Ford ২০০৪ আর Parr ও সহকর্মীদের ২০১৪ সালের প্রবন্ধ |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু grammar না চেয়ে precedence-এর যুক্তি, conflict-এর রিপোর্ট আর একটি স্বাধীন যাচাই চাওয়া, তারপর নিজে চালানো।
(নিজে যাচাই করুন: অংশ ৩-এর মতো সঠিক grammar-এ “a OR b AND c” গাছে OR ওপরে, AND তার ডান সন্তানে; Lark-এর contextual lexer-এ = প্রসঙ্গভেদে আলাদা token হতে পারে, আর lexer="basic"-এ amount = 5 ভেঙে যায়, যা অংশ ৪-এ চালিয়ে দেখা হয়েছে।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১LALR(1) কেন কয়েক দশক ধরে parser generator-এর প্রধান পদ্ধতি থাকল, অথচ canonical LR(1) বেশি শক্তিশালী?
ইতিহাসটা শুরু হয় ১৯৬৫ সালে, যখন Donald Knuth LR(k) parsing প্রকাশ করেন। তত্ত্বে এটি দারুণ ছিল: প্রতিটি deterministic CFL-এর একটি LR(1) grammar আছে, আর parse রৈখিক সময়ে। কিন্তু সেই সময়ের কম্পিউটারের মেমরিতে একটি বাস্তব ভাষার canonical LR(1) টেবিল খুব বড় হতো, কারণ একই core-এর item-সেট lookahead-ভেদে বহুবার আলাদা state হয়ে আসে। ১৯৬৯–৭১ সালের দিকে Frank DeRemer-এর কাজে SLR আর LALR আসে বলে সাধারণভাবে উল্লেখ করা হয়। LALR-এর state-সংখ্যা LR(0)-এর সমান, অথচ lookahead SLR-এর চেয়ে অনেক সূক্ষ্ম, তাই বাস্তব প্রোগ্রামিং ভাষার প্রায় সব নির্মাণ এতে ধরা পড়ে।
এরপর সিদ্ধান্তটি পাকা করে দেয় একটি tool: Bell Labs-এ Stephen Johnson-এর yacc (১৯৭০-এর দশকের মাঝামাঝি)। Unix-এর সঙ্গে yacc ছড়িয়ে পড়ে, আর C, awk-এর মতো অনেক ভাষার parser এতে লেখা হয়। yacc-এর একটি বড় ব্যবহারিক উপহার ছিল precedence ঘোষণা: %left '+'-এর মতো কয়েকটি লাইন দিয়ে ambiguous expression grammar-এর conflict মেটানো, যাতে grammar ছোট আর পড়তে সহজ থাকে। GNU-র Bison এই ঐতিহ্য চালিয়ে যায়, আর Python-এর PLY ও Lark-এর LALR মোড একই ধারার।
LALR-এর দামও আছে। জোড়া-দেওয়া state থেকে কখনো এমন reduce/reduce conflict আসে, যা canonical LR(1)-এ থাকত না; আর অংশ ৪-এ দেখেছেন, ভুল ধরার আগে বাড়তি reduce হয়ে expected-তালিকা ছোট হতে পারে। পরে IELR-এর মতো পদ্ধতি এসেছে, যা LALR-এর আকারের কাছাকাছি থেকে canonical LR(1)-এর পূর্ণ শক্তি দেয় বলে দাবি করা হয়; Bison-এ এটি বেছে নেওয়া যায়। আজকের মেমরিতে canonical LR(1)-এর আকারও সাধারণত সমস্যা নয়, তবু অভ্যাস, tool আর পরিচিতির কারণে LALR(1) এখনো সবচেয়ে প্রচলিত।
মূল উপলব্ধি: LALR(1)-এর জয় তত্ত্বের নয়, প্রকৌশলের: মেমরির সীমা, যথেষ্ট শক্তি আর yacc-এর মতো একটি সফল tool একসঙ্গে মিলেছিল। কোনো algorithm-এর প্রচলন বুঝতে তাই তার সময়ের যন্ত্র আর tool-এর ইতিহাসও দেখতে হয়।
প্র ০২Generator কেন “আপনার grammar ambiguous” বলতে পারে না, শুধু conflict দেখায়? এই দুইয়ের ফাঁক বাস্তবে কতটা বড়?
কারণটি computability-র সীমা। একটি CFG ambiguous কি না, প্রশ্নটি undecidable: এমন কোনো algorithm নেই, যা প্রতিটি CFG-এর জন্য সবসময় থেমে ঠিক উত্তর দেয়। প্রমাণ আসে Post correspondence problem থেকে একটি reduction-এ (পর্ব ৫৪), আর এর মূল ফলগুলো ১৯৬০-এর দশকের শুরুতে Cantor, Floyd, Chomsky ও Schützenberger-এর মতো গবেষকদের কাজে এসেছে বলে উল্লেখ করা হয়। তাই কোনো generator, কোনো AI বা কোনো মানুষ সাধারণ নিয়ম হিসেবে ambiguity-র সিদ্ধান্ত দিতে পারে না।
Generator তাই অন্য একটি প্রশ্নের উত্তর দেয়, যা decidable: “এই grammar কি LALR(1)?” টেবিল বানিয়ে দেখলেই উত্তর। উপপাদ্য ২.১ বলে, উত্তর হ্যাঁ হলে grammar unambiguous; কিন্তু না হলে দুই সম্ভাবনা: grammar সত্যিই ambiguous (E → E+E-এর মতো), অথবা grammar unambiguous কিন্তু LALR(1)-এর পক্ষে বেশি জটিল (palindrome-এর মতো, বা এমন grammar যার সিদ্ধান্তে দুই token সামনে দেখা লাগে)। Conflict-এর রিপোর্ট দুই ক্ষেত্রে প্রায় একই দেখায়, আর কোনটি, তা বোঝা মানুষের কাজ।
বাস্তব সমাধান কয়েক রকম। প্রথমত, conflict-এর পেছনের উদাহরণ খোঁজা: Bison-এর নতুন version-গুলো conflict-এর জন্য counterexample দেখাতে পারে বলে নথিতে আছে, আর এমন উদাহরণে দুটি গাছ পাওয়া গেলে ambiguity নিশ্চিত। দ্বিতীয়ত, ছোট দৈর্ঘ্যের সব string-এ brute force দিয়ে দুটি গাছ খোঁজা, পর্ব ২৭-এর মতো; এটি ambiguity প্রমাণ করতে পারে, অনুপস্থিতি নয়। তৃতীয়ত, Earley-র মতো parser-এ explicit ambiguity চালু করে বাস্তব input চালানো। কোনো পদ্ধতিই সম্পূর্ণ নয়, কারণ সম্পূর্ণ পদ্ধতি থাকা অসম্ভব।
মূল উপলব্ধি: Conflict-মুক্ত হওয়া ambiguity-হীনতার একটি নিরাপদ, পরীক্ষাযোগ্য প্রমাণ; conflict থাকা ambiguity-র প্রমাণ নয়। Undecidability এখানে বিমূর্ত তত্ত্ব নয়, প্রতিদিনের tool-এর আচরণের সরাসরি কারণ।
প্র ০৩GCC আর Clang-এর মতো বড় compiler কেন generator ছেড়ে হাতে লেখা recursive descent parser ব্যবহার করে?
GCC-র ইতিহাস একটি ভালো উদাহরণ। একসময় এর C আর C++ parser দুটিই Bison-এ বানানো ছিল। GCC-র mailing list-এর আলোচনা অনুযায়ী, C++ parser GCC 3.4-এ (২০০৪) হাতে লেখা recursive descent-এ বদলায়, আর C parser GCC 4.1-এ। কারণগুলো তখনকার আলোচনায় স্পষ্ট: C++-এর grammar LALR(1)-এর জন্য খুব কঠিন (Bison-এর grammar-এ বহু shift/reduce আর reduce/reduce conflict ছিল বলে উল্লেখ আছে), কারণ কিছু নির্মাণ বুঝতে অনেক দূর সামনে দেখতে হয়, আর একটি নাম type কি না তার ওপর গঠন নির্ভর করে, যা context-free নয়। নতুন parser-এর লক্ষ্য ছিল রক্ষণাবেক্ষণ সহজ করা, গতি আর ভালো error message. LLVM-এর Clang শুরু থেকেই হাতে লেখা parser নিয়ে আসে।
হাতে লেখা parser-এর সুবিধা হলো নিয়ন্ত্রণ। প্রতিটি ফাংশন grammar-এর একটি নিয়ম, কিন্তু ভেতরে প্রোগ্রামার যা খুশি করতে পারেন: symbol table দেখে সিদ্ধান্ত নেওয়া, দরকারে কয়েকটি token সামনে দেখা, আর সবচেয়ে বড় কথা, ভুলের জায়গায় মানুষের মতো বার্তা লেখা (“এখানে সম্ভবত একটি ; বাদ পড়েছে”) আর বুদ্ধিমানভাবে ভুল থেকে উঠে দাঁড়ানো। Generator-এর টেবিলে এসব বসানো কঠিন।
তবে দাম আছে। হাতে লেখা parser-এ grammar আর কোড আলাদা থাকে না, তাই grammar-এর আনুষ্ঠানিক বিবরণ আর আসল আচরণ ধীরে ধীরে আলাদা হয়ে যেতে পারে; conflict-এর কোনো স্বয়ংক্রিয় পরীক্ষা নেই, ফলে ambiguity লুকিয়ে থাকতে পারে। বড় compiler দল এই দাম দিতে পারে; বাজারঘরের মতো একটি ছোট দলের ছোট DSL-এ generator এখনো সাধারণত ভালো পছন্দ, কারণ grammar-ই সেখানে নথি আর পরীক্ষা।
মূল উপলব্ধি: Generator আর হাতে লেখা parser-এর মধ্যে বাছাই হলো স্বয়ংক্রিয় নিশ্চয়তা বনাম পূর্ণ নিয়ন্ত্রণের লেনদেন। ভাষা যত জটিল আর ব্যবহারকারী যত বেশি, error message-এর মূল্য তত বেশি, আর হাতে লেখার যুক্তি তত শক্ত।
প্র ০৪Python কেন LL(1) parser ছেড়ে PEG-এ গেল? Ordered choice-এর ঝুঁকি জেনেও এই সিদ্ধান্ত কেন যুক্তিসংগত?
CPython বহু বছর একটি নিজস্ব LL(1) parser generator (pgen) ব্যবহার করত। LL(1)-এর সীমার কারণে Python-এর grammar-এ কিছু কৃত্রিম কৌশল লাগত। PEP 617 উদাহরণ দেয়: assignment-এর বাঁ দিক আর একটি সাধারণ expression শুরুতে দেখতে একই, তাই LL(1) grammar প্রথমে দুটিকে একই নিয়মে পড়ত আর পরে আলাদা একটি ধাপে বাঁ দিক বৈধ কি না যাচাই করত। এমন জোড়াতালিতে grammar আর ভাষার আসল নিয়ম আলাদা হয়ে যাচ্ছিল, আর নতুন syntax যোগ করা কঠিন হচ্ছিল। Guido van Rossum ২০১৯ সালে PEG নিয়ে ধারাবাহিক লেখা লেখেন, আর PEP 617 অনুযায়ী Python 3.9-এ নতুন PEG parser আসে; 3.10-এ পুরোনোটি বাদ যায়।
PEG-এর সুবিধা এখানে স্পষ্ট: অসীম সামনে-দেখা (backtracking দিয়ে), left recursion-এর জন্য বিশেষ কৌশল, আর ambiguity-র প্রশ্নই নেই, কারণ ordered choice সবসময় একটি ফল দেয়। Python 3.10-এর match statement-এর মতো নতুন নির্মাণ এই parser-এ যোগ করা সহজ হয়েছে বলে উল্লেখ করা হয়, যেখানে match একটি “soft keyword”: কিছু জায়গায় keyword, অন্য জায়গায় সাধারণ নাম।
ঝুঁকিটি অংশ ৭-এর stepper-এ দেখেছেন: বিকল্পের ক্রম ভুল হলে বৈধ input নীরবে প্রত্যাখ্যাত হয়, আর কোনো tool এটিকে conflict হিসেবে জানায় না, কারণ PEG-এর দৃষ্টিতে এটি ভুল নয়, শুধু একটি ভিন্ন language. CPython দল এই ঝুঁকি সামলায় বিশাল পরীক্ষা-সংগ্রহ দিয়ে: নতুন parser-কে Python-এর নিজের standard library আর বহু জনপ্রিয় package-এর কোডে চালিয়ে পুরোনো parser-এর ফলের সঙ্গে মেলানো হয়েছিল বলে উল্লেখ পাওয়া যায়, অর্থাৎ অংশ ৬-এর differential testing. আর packrat-এর মেমরি খরচ কমাতে সব rule memo করা হয় না।
মূল উপলব্ধি: PEG তত্ত্বের কিছু নিশ্চয়তা (conflict দিয়ে সতর্কবার্তা) ছেড়ে প্রকাশের স্বাধীনতা কেনে। এই লেনদেন তখনই নিরাপদ, যখন বিশাল পরীক্ষা-সংগ্রহ হারানো নিশ্চয়তার জায়গা নেয়।
প্র ০৫Code editor-এর parser-কে কেন compiler-এর parser থেকে আলাদা হতে হয়? ভুলে-ভরা লেখার “গাছ” কি তত্ত্বে অর্থপূর্ণ?
Compiler-এর parser একটি সম্পূর্ণ ফাইল পায়, আর প্রথম গুরুতর ভুলে থামলেও চলে। Editor-এর পরিস্থিতি উল্টো। আপনি প্রতি সেকেন্ডে কয়েকটি অক্ষর লেখেন, আর প্রায় প্রতিটি মুহূর্তে ফাইলটি অসম্পূর্ণ: একটি বন্ধনী খোলা, একটি string শেষ হয়নি। তবু editor-কে রং দেখাতে হয়, ফাংশনের তালিকা দেখাতে হয়, ভাঁজ করতে হয়। তাই দুটি প্রয়োজন: গতি, অর্থাৎ প্রতিটি সম্পাদনায় পুরো ফাইল নতুন করে না পড়া; আর সহিষ্ণুতা, অর্থাৎ ভুল থাকলেও যতটা সম্ভব ভালো একটি গাছ।
Incremental parsing-এর গবেষণা পুরোনো; ১৯৯০-এর দশকে Tim Wagner আর Susan Graham-এর কাজ প্রায়ই উল্লেখ করা হয়, যা LR parsing-কে incremental করার পদ্ধতি দেয়। মূল ধারণা: একটি সম্পাদনা গাছের একটি ছোট অংশ বদলায়; বদলানো জায়গার চারপাশের node বাতিল করে, বাকি উপ-গাছগুলো পুরোনো parse থেকে “তৈরি token”-এর মতো আবার ব্যবহার করা যায়। tree-sitter এই ধারার একটি আধুনিক, ব্যাপক ব্যবহৃত রূপ, যা Neovim, Zed-এর মতো editor আর GitHub-এর code navigation-এ ব্যবহৃত হয় বলে জানা যায়।
তত্ত্বের দিক থেকে ভুলে-ভরা লেখার “গাছ” একটি সংজ্ঞার প্রশ্ন। কঠোর অর্থে w ∉ L(G) হলে w-এর কোনো parse tree নেই। Error recovery তাই আসলে একটি কাছের string খোঁজে: w-কে কয়েকটি token যোগ, বাদ বা বদলে L(G)-এর একটি w′ বানানো, আর w′-এর গাছ দেখানো। সবচেয়ে কম সম্পাদনায় এমন w′ খোঁজার সমস্যাটি ১৯৭২ সালে Aho আর Peterson-এর কাজে CFG-এর জন্য dynamic programming দিয়ে সমাধান করা হয় বলে উল্লেখ আছে, তবে ঘন সময়ে; editor তাই দ্রুত, কিন্তু অনুমান-নির্ভর কৌশল নেয়। অংশ ৬-এর ANTLR-এর “missing NUM” হলো এমন একটি সম্পাদনা: একটি token যোগ।
মূল উপলব্ধি: Editor-এর parser-এর লক্ষ্য “L(G)-এ আছে কি না” নয়, “সবচেয়ে কাছের বৈধ গঠন কী”। একই grammar, কিন্তু প্রশ্ন বদলালে algorithm-এর নকশাও বদলায়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। PEG আর packrat-এর উত্তর উপরের Python ব্লকে নিয়ম বদলে নিজেই যাচাই করতে পারেন।
-
নকশা: বাজারঘরের query ভাষায় দুটি নতুন সুবিধা আনুন: (ক) শুরুতে FIND-এর বদলে COUNT লিখলে অর্ডারের তালিকার বদলে সংখ্যা আসবে; (খ) শেষে ঐচ্ছিক
LIMIT n, যা প্রথম n-টি ফল রাখবে। অংশ ৩-এর Lark grammar-এর query-নিয়ম আর Transformer-এর query method কীভাবে বদলাবে?COUNT order WHERE district = "Dhaka"আরFIND order WHERE amount >= 1000 AND district = "Dhaka" LIMIT 3-এর উত্তর কী হবে?Grammar-এ query-নিয়ম আর একটি নতুন terminal:
query: VERB "order" "WHERE" cond ("LIMIT" NUM)? VERB: "FIND" | "COUNT"VERB নাম-দেওয়া terminal, তাই গাছে থাকে;
( … )?মানে ঐচ্ছিক, আর LIMIT থাকলে query-র তৃতীয় সন্তান NUM. Transformer-এর query method: সন্তান থেকে verb আর শর্ত-ফাংশন নিন, শর্ত মানা অর্ডারের তালিকা বানান, তিনটি সন্তান থাকলে প্রথম n-টি রাখুন, আর verb COUNT হলে তালিকার দৈর্ঘ্য ফেরত দিন। LIMIT cond-এর পরে আসে, আর cond-এর কোনো নিয়ম LIMIT দিয়ে শুরু হয় না, তাই নতুন conflict আসে না।Scratch-এ Lark 1.3.1-এ চালানো হয়েছে, debug log-এ কোনো conflict ছাড়া:
COUNT order WHERE district = "Dhaka"→ 31;… LIMIT 3→ ['BG-0001', 'BG-0024', 'BG-0036'], অংশ ৩-এর ২৫টির প্রথম তিনটি।COUNT order WHERE amount >= 1000 LIMIT 5দিয়েছে 5, অর্থাৎ এই নকশায় LIMIT আগে, COUNT পরে; চাইলে উল্টো অর্থও বেছে নিতে পারেন, কিন্তু নথিতে স্পষ্ট লিখতে হবে। -
প্রমাণের ভুল ধরুন: দাবি: “E → E+E ∣ E∗E ∣ (E) ∣ id grammar unambiguous.” যুক্তি: “Lark-এর
parser="lalr"এই grammar থেকে কোনো exception ছাড়া parser বানিয়েছে, আরid+id*id-এ একটিমাত্র গাছ দিয়েছে। উপপাদ্য ২.১ বলে LALR টেবিল থাকলে grammar unambiguous. ∎” ভুলগুলো কোথায়?- উপপাদ্যের শর্ত ভুল পড়া: উপপাদ্য ২.১-এর শর্ত “টেবিলে কোনো conflict নেই”, “টেবিল তৈরি হয়েছে” নয়। অংশ ৫-এর সত্যিকারের run-এ Lark চারটি shift/reduce conflict পেয়ে নিজে “shift” বেছে টেবিল বানিয়েছে; শর্তই পূরণ হয়নি। — hypothesis যাচাই
- একটি গাছ মানে একটি নয়: Deterministic parser সংজ্ঞা অনুযায়ী একটিই গাছ দেয়, তাই “একটি গাছ পেয়েছি” কিছু প্রমাণ করে না। Ambiguity মানে অস্তিত্ব: অন্তত একটি string-এর দুটি গাছ। — সংজ্ঞা
- পাল্টা-উদাহরণ: id+id∗id-এর দুটি leftmost derivation: E ⇒ E+E ⇒ id+E ⇒ id+E∗E ⇒ … আর E ⇒ E∗E ⇒ E+E∗E ⇒ … (পর্ব ২৭); একই run-এ Earley
ambiguity="explicit"-এ_ambigদিয়েছে। তাই grammar ambiguous, দাবিটি মিথ্যা। — পর্ব ২৭, অংশ ৫
-
আউটপুট অনুমান: অংশ ৭-এর
peg_choice.py-তে Rel-এর ক্রম[">", ">=", "="]করলেamount = 5,amount > 5আরamount >= 5-এর ফল কী? আরpackrat_count.py-তে d = 3 হলে সারিটি কী ছাপবে?PEG:
amount = 5→ True (">" আর ">=" ব্যর্থ, "=" সফল, তারপর 5).amount > 5→ True.amount >= 5→ False: ">" প্রথমে সফল, choice বন্ধ, তারপর NUM “=” পায়। Scratch-এ চালিয়ে ঠিক True, True, False এসেছে। সূত্র: কোনো বিকল্প যদি পরের কোনো বিকল্পের prefix হয়, তবে লম্বাটি আগে লিখুন।Packrat: input
(((a)y)y)y, দৈর্ঘ্য 3 · 3 + 1 = 10; সরল PEG 24 − 1 = 15 হিসাব; packrat 3 + 1 = 4; memo-তে 4টি ঘর। ছাপা হবে3 10 15 4 4. -
গণনা ও প্রমাণ: অংশ ৭-এর grammar P ← "(" P ")" "x" / "(" P ")" "y" / "a" আর input (d a (")y")d-এ সরল PEG কতবার P হিসাব করে, আর packrat কতবার? সূত্র দুটি প্রমাণ করুন, আর d = 20-এ মান বের করুন।
- ভিত্তি: d = 0-এ input “a”: P একবার হিসাব হয়, প্রথম দুই বিকল্প “(” না পেয়ে সঙ্গে সঙ্গে ব্যর্থ, তৃতীয়টি সফল। T(0) = 1. — সরাসরি
- সরল PEG-এর পুনরাবৃত্তি: d ≥ 1-এ অবস্থান i-তে “(”. প্রথম বিকল্প ভেতরের P (গভীরতা d − 1) পুরোটা পড়ে, তারপর “)x” চায় কিন্তু পায় “)y”: ব্যর্থ। দ্বিতীয় বিকল্প একই ভেতরের P আবার পুরোটা পড়ে, এবার সফল। তাই T(d) = 1 + 2T(d − 1). — ordered choice-এর আচরণ
- সমাধান: induction-এ T(d) = 2d+1 − 1: d = 0-এ 1; আর ধরে নিলে T(d − 1) = 2d − 1, তাহলে T(d) = 1 + 2(2d − 1) = 2d+1 − 1. — mathematical induction
- Packrat: দ্বিতীয় বিকল্পের ভেতরের call টেবিল থেকে উত্তর পায়, তাই প্রতিটি অবস্থান 0, 1, …, d-তে P একবার হিসাব হয় (প্রতিটি ( এর পরের অবস্থান, আর a-এর অবস্থান d): মোট d + 1. — উপপাদ্য ৭.১-এর ধাপ ৩
- d = 20: সরল PEG 221 − 1 = 2,097,151 বার, packrat 21 বার। ∎
ব্লকের আউটপুটে d = 1, 2, 4, 8, 12, 16-এ সরল PEG-এর 3, 7, 31, 511, 8191, 131071 আর packrat-এর 2, 3, 5, 9, 13, 17 সূত্রের সঙ্গে হুবহু মেলে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি parser generator দিয়ে একটি ছোট query ভাষার interpreter বানিয়ে চালানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Token আর নিয়মসহ grammar ফাইল লেখা, precedence-এর স্তর ঠিক করে
- Generator চালিয়ে lexer আর parsing টেবিল বানানো, conflict-এর রিপোর্ট পড়ে
- Query-কে lexer দিয়ে token-এর ধারায় ভাঙা
- Parser দিয়ে token-এর ধারা থেকে parse tree বানানো
- Transformer বা visitor দিয়ে গাছকে একটি শর্ত-ফাংশনে বদলানো
- প্রতিটি অর্ডারে শর্ত চালিয়ে উত্তরের তালিকা বানানো
Lark-এর parser="lalr" grammar E → E+E ∣ E∗E ∣ (E) ∣ id থেকে কোনো exception ছাড়াই parser বানাল। এর সঠিক ব্যাখ্যা কোনটি?
- Grammar unambiguous, কারণ LALR টেবিল তৈরি হয়েছে
- Lark গণিতের precedence নিজে বসিয়ে দিয়েছে
- Shift/reduce conflict ছিল, Lark নিজে “shift” বেছে মিটিয়েছে; grammar ambiguous-ই আছে
- Lark নিজে থেকে Earley parser-এ চলে গেছে
PEG-এ Rel ← ">" / ">=" আর Query ← "amount" Rel NUM (ফাঁকা ঘর বাদ) হলে input “amount >= 5”-এর কী হবে?
- গ্রহণ করবে, কারণ ">=" একটি বিকল্প
- প্রত্যাখ্যান করবে
- দুটি parse দেবে, অর্থাৎ ambiguous
- অসীম loop-এ পড়বে
নিচের কোন দাবিটি সত্য?
- কোনো grammar-এর LALR(1) টেবিল conflict-মুক্ত হলে grammar unambiguous
- প্রতিটি unambiguous grammar-এর LALR(1) টেবিল conflict-মুক্ত
- একটি ভালো generator যেকোনো CFG ambiguous কি না সবসময় বলে দিতে পারে
- Earley parser কোনো grammar মেনে নিলে সেটি unambiguous
ANTLR 4-এ cond : cond 'AND' cond | cond 'OR' cond | ID ; নিয়মটি নিয়ে কোনটি ঠিক?
- ANTLR 4 এটি মানবে না, কারণ এটি left-recursive
- AND আর OR সমান precedence পাবে
- ANTLR 4 এটি LL(1) টেবিলে বদলাবে
- এটি চলবে, আর আগে লেখা AND, OR-এর চেয়ে শক্তভাবে বাঁধবে
r-টি rule-এর একটি PEG-এ (left recursion নেই) দৈর্ঘ্য n-এর input-এ packrat parser-এর memo টেবিলে বড়জোর কতটি ঘর থাকে?
- r
- n + 1
- r(n + 1)
- 2n
একটি LALR(1) parser ভুল input-এ কী করতে পারে, যা canonical LR(1) parser করে না?
- ভুল token stack-এ shift করে ফেলতে পারে
- ভুল ধরার আগে কয়েকটি বাড়তি reduce করতে পারে
- ভুল input-কে বৈধ বলে গ্রহণ করতে পারে
- অসীম loop-এ পড়তে পারে
বাজারঘরের অর্ডার-সার্ভারে প্রতি সেকেন্ডে অনেক query, আর grammar LALR(1) (conflict নেই)। Lark-এ কোন parser বাছাই যুক্তিসংগত?
- parser="lalr", কারণ একই গাছ দেয় আর অনেক দ্রুত
- parser="earley", কারণ সব CFG মানে
- parser="earley" আর ambiguity="explicit"
- প্রতিটি query-র জন্য হাতে লেখা নতুন parser
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Parser generator grammar থেকে একবার lexer আর parser বানায় (build time), যা প্রতিটি input-এ গাছ বা line-column-সহ error দেয় (run time); অর্থ আসে semantic action, transformer বা visitor থেকে।
- Tool-এর পেছনে algorithm: yacc/Bison/PLY LALR(1), Lark LALR(1) বা Earley, ANTLR 4 ALL(*), CPython PEG. Algorithm ঠিক করে কোন grammar চলে আর কত দ্রুত।
- Conflict-মুক্ত LALR(1) ⇒ unambiguous; উল্টোটি মিথ্যা (palindrome). Ambiguity undecidable, তাই generator শুধু conflict দেখায়; আর কিছু tool conflict নীরবে “shift”-এ মেটায়।
- LALR ভুল token shift করে না, কিন্তু ভুলের আগে বাড়তি reduce করতে পারে; contextual lexer একই লেখাকে প্রসঙ্গভেদে ভিন্ন token দেয়।
- PEG-এর ordered choice union নয়: লম্বা বিকল্প আগে। Packrat memo দিয়ে left recursion-হীন PEG-কে O(n) সময়ে আনে, দাম O(r · n) মেমরি।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২২ · Lexical analysis — token, lexer আর lexer generatorফিরে দেখুনএই পর্বের query ভাষার token, PLY আর Lark-এর lexer.
- পর্ব ২৭ · Ambiguity — দ্ব্যর্থক grammar আর inherent ambiguityফিরে দেখুনPrecedence-এর স্তর, dangling else আর ambiguity-র undecidability.
- পর্ব ৩০ · Greibach normal form আর left recursion দূর করাভিত্তিTop-down parser কেন left recursion-এ আটকায়, আর তা সরানোর পদ্ধতি।
- পর্ব ৩৫ · Deterministic PDA আর deterministic CFLতত্ত্বLR(k) grammar আর DCFL-এর সম্পর্ক, palindrome কেন deterministic নয়।
- পর্ব ৩৯ · Bottom-up parsing — shift-reduce, LR(0), SLR আর LALRভিত্তিLALR টেবিল, conflict আর precedence ঘোষণা, যা generator-এর ভেতরে চলে।
- পর্ব ৪১ · সব CFG-এর parsing — Earley আর GLRপরের পর্বLark-এর Earley আর tree-sitter-এর GLR-এর ভেতরের কাজ।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৪১ Earley আর GLR.
- DSA · পর্ব ৫২ — Dynamic programming-এর ভিত্তিপাশের ট্র্যাকPackrat parsing-এর পেছনের memoization, algorithm-এর দিক থেকে।
- Software Testing · পর্ব ৬০ — Fuzz testingহাতে-কলমেএলোমেলো input দিয়ে parser পরীক্ষা, এই পর্বের differential testing-এর পরের ধাপ।