সরাসরি পর্বে যান
পর্ব ৩৮ · ৮৫-এর মধ্যে · মডিউল ৭

Top-down parsing — LL(1), FIRST আর FOLLOW

Top-Down Parsing — Predict and Match, Recursive Descent, Left Factoring, FIRST and FOLLOW Sets, LL(1) Tables and the Stack-Based Predictive Parser

Taught in Bangla, this lesson builds top-down parsers that predict and match along a leftmost derivation. It writes a recursive descent parser, applies left factoring, computes FIRST and FOLLOW sets, fills the LL(1) parsing table, then runs a stack-based predictive parser that is a deterministic PDA. In-page Python (Pyodide) builds the tables, a real CPython run prints a 13-entry table with zero conflicts, and a hand-written order-query parser agrees with lark 1.3.1's Earley parser on 4000 queries.

এই পর্বে যা শিখবেন

  • Top-down parsing-এর predict আর match, আর grammar থেকে সরাসরি recursive descent parser লেখা
  • Left factoring দিয়ে একই শুরুর নিয়মের সংঘাত সরানো, আর কোথায় এটি কাজ করে না
  • FIRST আর FOLLOW set-এর সংজ্ঞা আর fixpoint দিয়ে হিসাব, হাতে আর কোডে
  • LL(1) parsing table বানানো, LL(1) শর্ত, আর প্রমাণ যে LL(1) grammar unambiguous
  • Stack-সহ predictive parser চালানো, error ধরা, panic mode, আর LL(k) ও ALL(*)-এর জায়গা

১ · Top-down parsing — predict আর match

মডিউল ৫-এ আপনি grammar লিখেছেন, derivation বানিয়েছেন, আর পর্ব ৩১-এ CYK দিয়ে যেকোনো CNF grammar-এর membership প্রশ্নের উত্তর দিয়েছেন। কিন্তু CYK-এর সময় n3-এর অনুপাতে বাড়ে। একটি compiler প্রতিদিন লক্ষ লক্ষ লাইন পড়ে; সেখানে চাই এমন parser, যা input একবার বাঁ থেকে ডানে পড়ে, প্রতিটি token-এ সামান্য কাজ করে, আর কখনো পেছনে ফেরে না। এই মডিউলের বিষয় সেই বাস্তব parsing. প্রথম পদ্ধতি: ওপর থেকে নিচে।

বাজারঘরের কল সেন্টারে একজন এজেন্ট বসে আছেন। গ্রাহক কথা শুরু করলেন: “অর্ডার …”। এজেন্ট শুধু প্রথম শব্দটি শুনেই ঠিক করেন কোন ফর্ম খুলবেন: “অর্ডার” মানে নতুন অর্ডারের ফর্ম, “রিটার্ন” মানে ফেরতের ফর্ম, “অভিযোগ” মানে অভিযোগের ফর্ম। ফর্মে ঘরগুলো একটি নির্দিষ্ট ক্রমে আছে: নাম, ঠিকানা, জিনিস। এজেন্ট প্রতিটি ঘর গ্রাহকের পরের কথা দিয়ে পূরণ করেন, আর কোনো ঘর নিজেই আরেকটি ছোট ফর্ম হলে (যেমন “ঠিকানা” মানে জেলা, থানা, রাস্তা) সেটি খুলে আগে পূরণ করেন। ঝামেলা হয় দুটি ফর্ম একই শব্দ দিয়ে শুরু হলে: “অর্ডার বাতিল” আর “অর্ডার নতুন”। তখন প্রথম শব্দে সিদ্ধান্ত হয় না, পরের শব্দ শোনা পর্যন্ত অপেক্ষা করতে হয়। Top-down parser ঠিক এই এজেন্ট।

যন্ত্রের ভাষায়: parser start symbol থেকে শুরু করে, আর সবসময় সবচেয়ে বাঁয়ের variable-টি খোলে। ফলে সে input-এর একটি leftmost derivation তৈরি করে, আর parse tree তৈরি হয় root থেকে পাতার দিকে, বাঁ থেকে ডানে। প্রতিটি মুহূর্তে parser-এর কাছে থাকে “এখন পর্যন্ত মেলানো input” আর “এখনো যা বানানো বাকি”, এবং বাকি অংশটি একটি stack-এ রাখা যায়। দুটি মূল কাজ:

  • Predict: stack-এর ওপরে variable A থাকলে A-এর কোনো নিয়ম A → α বেছে নিয়ে A-কে α দিয়ে বদলানো।
  • Match: stack-এর ওপরে terminal a থাকলে input-এর পরের token-ও a কি না দেখা; হলে দুটিই সরানো, না হলে error.

পর্ব ৩৪-এ ঠিক এই দুই কাজ দিয়ে যেকোনো CFG থেকে একটি PDA বানিয়েছিলেন। সেখানে predict ছিল nondeterministic: PDA “অনুমান” করত কোন নিয়ম নেবে, আর কোনো একটি অনুমান-পথ সফল হলেই গ্রহণ। বাস্তব যন্ত্রে অনুমান মানে backtracking: একটি নিয়ম চেষ্টা, ব্যর্থ হলে ফিরে এসে পরেরটি। এতে সময় exponential হতে পারে, আর পর্ব ৩০-এ দেখেছেন, left recursion থাকলে parser কখনো থামেই না। এই পর্বের প্রশ্ন: কোন grammar-এ অনুমান লাগে না, শুধু পরের token দেখেই নিয়ম নিশ্চিতভাবে বাছা যায়?

সংজ্ঞা ১.১ (Lookahead আর end marker)

Parser input-এর যে পরের token এখনো খরচ করেনি কিন্তু সিদ্ধান্ত নিতে দেখে, তাকে বলে lookahead token. Input-এর শেষে একটি বিশেষ চিহ্ন $ বসানো হয়, যা কোনো আসল token নয়; এটি end marker. ফলে “input শেষ” অবস্থাটিও একটি lookahead, যা আলাদা করে লিখতে হয় না।

নাম “LL(1)” তিনটি কথা বলে: প্রথম L মানে input বাঁ থেকে ডানে (Left-to-right) পড়া, দ্বিতীয় L মানে leftmost derivation তৈরি করা, আর (1) মানে এক token lookahead. একটি grammar-কে LL(1) বলা হয়, যদি এই নিয়মে চলা parser প্রতিটি predict-এ ঠিক একটি সম্ভাব্য নিয়ম পায়। সংজ্ঞাটি অংশ ৫-এ table দিয়ে নিখুঁত করা হবে। যে parser backtracking ছাড়া এভাবে চলে, তাকে বলে predictive parser.

একটি ছোট উদাহরণ। Grammar S → aSb ∣ c (language {ancbn : n ≥ 0}). Input aacbb. Stack-এ S, lookahead a: S-এর দুটি নিয়মের মধ্যে শুধু aSb a দিয়ে শুরু, তাই predict S → aSb. তারপর a match. আবার S, lookahead a: আবার aSb. আবার S, এবার lookahead c: নিয়ম S → c. তারপর c, b, b match, input শেষ: গ্রহণ। প্রতিটি সিদ্ধান্ত এক token দেখেই নিশ্চিত হলো। এখন grammar-টি বদলে S → aSb ∣ ab করুন (language {anbn : n ≥ 1}). Lookahead a দেখে দুটি নিয়মই প্রার্থী; এক token যথেষ্ট নয়। একই language-এর আরেকটি grammar কিন্তু LL(1) হতে পারে, অংশ ৩ দেখাবে কীভাবে।

২ · Recursive descent — grammar থেকে সরাসরি কোড

Predictive parser লেখার সবচেয়ে সহজ উপায় recursive descent: প্রতিটি variable-এর জন্য একটি function. Function-টি lookahead দেখে নিয়ম বাছে, তারপর নিয়মের ডান দিক বাঁ থেকে ডানে চালায়: terminal হলে match, variable হলে সেই variable-এর function ডাকে। Function-গুলোর ডাকের stack-ই parser-এর stack; আলাদা stack লাগে না।

বাজারঘরের order-query ভাষা দিয়ে দেখা যাক। পর্ব ২২-এর lexer লাইনটিকে 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
R → = ∣ >= ∣ <

C আর T left-recursive, তাই আগে পর্ব ৩০-এর সূত্র A → Aα ∣ β ⇒ A → βA′, A′ → αA′ ∣ ε খাটান: C → T C′, C′ → OR T C′ ∣ ε, T → F T′, T′ → AND F T′ ∣ ε. হাতে লেখা parser-এ C′ সাধারণত একটি loop হয়ে যায়: “একটি T পড়ুন; পরের token যতক্ষণ OR, ততক্ষণ OR আর আরেকটি T পড়ুন”. Loop-এ ফল বাঁ দিক থেকে জোড়া হয়, তাই OR-এর বাঁ-associativity-ও রক্ষা পায়। F-এর চারটি নিয়ম চারটি আলাদা token দিয়ে শুরু: (, amount, district, status. তাই F-এর function একটি token দেখেই নিয়ম জানে।

এই parser কি সত্যিই grammar-এর language-টিই চেনে? একটি বাস্তব পরীক্ষা: একই grammar পর্ব ২৬-এর মতো Lark-এ (MIT licence) left-recursive রূপেই লিখে তার Earley parser চালানো, যা যেকোনো CFG নেয়, আর দুই parser-কে হাজার হাজার query দেওয়া। Query-গুলো grammar থেকে এলোমেলোভাবে তৈরি (seed 38), আর প্রতিটির একটি “নষ্ট” রূপও আছে: একটি token মুছে, ঢুকিয়ে বা দুটি token অদলবদল করে। নিচে script-এর parser অংশ; query তৈরির কোড আর Lark grammar “…” দিয়ে বাদ রাখা হয়েছে।

class RD:                                   # hand-written recursive descent
    def __init__(s, src):
        s.t = re.findall(r'>=|[()=<]|"[^"]*"|\w+|\S', src) + ["$"]; s.k = 0
    def kind(s):
        x = s.t[s.k]
        return "NUM" if x.isdigit() else "STR" if x[0] == '"' else x
    def eat(s, want):
        if s.kind() != want: raise SyntaxError(f"token {s.k+1}: expected {want}")
        s.k += 1; return s.t[s.k - 1]
    def query(s):
        s.eat("FIND"); s.eat("order"); s.eat("WHERE"); c = s.C(); s.eat("$"); return c
    def C(s):                               # C -> T { OR T }
        x = s.T()
        while s.kind() == "OR": s.k += 1; x = ("or", x, s.T())
        return x
    def T(s):                               # T -> F { AND F }
        x = s.F()
        while s.kind() == "AND": s.k += 1; x = ("and", x, s.F())
        return x
    def F(s):                               # one token decides the rule
        x = s.kind()
        if x == "(": s.k += 1; c = s.C(); s.eat(")"); return c
        if x == "amount":
            s.k += 1; r = s.kind()
            if r not in ("=", ">=", "<"): raise SyntaxError("expected relation")
            s.k += 1; return ("amount", r, s.eat("NUM"))
        if x in ("district", "status"):
            s.k += 1; s.eat("="); return (x, s.eat("STR"))
        raise SyntaxError(f"token {s.k+1}: expected ( amount district status")
# … Lark grammar (left-recursive), random query generator, mutate() …

সত্যিকারের run (ডেস্কটপ, Lark 1.3.1, Python 3.12.13):

~/bazarghar-toc$ uv run python rd_vs_lark.py
lark 1.3.1 | Python 3.12.13
4000 queries: {'both accept': 2090, 'both reject': 1910, 'same tree': 2090, 'disagree': 0}
('and', ('amount', '>=', '1000'), ('or', ('district', '"Dhaka"'), ('status', '"paid"')))

২০০০টি বৈধ query আর ২০০০টি নষ্ট রূপ। নষ্ট রূপের মধ্যে ৯০টি ঘটনাক্রমে আবার বৈধ (যেমন দুটি শর্ত অদলবদল), তাই মোট ২০৯০টি গৃহীত আর ১৯১০টি বর্জিত। দুই parser একটি query-তেও দ্বিমত করেনি, আর প্রতিটি গৃহীত query-তে AND/OR-এর গাছও হুবহু এক (same tree 2090), অর্থাৎ loop-এ লেখা parser-ও বাঁ-associativity আর “AND আগে” নিয়ম রেখেছে। শেষ লাইন একটি বন্ধনী-সহ query-র গাছ: AND-এর ডান দিকে পুরো OR. এটি প্রমাণ নয়, কিন্তু parser-এর একটি টাইপের ভুল (যেমন F-এ status ভুলে যাওয়া) প্রথম কয়েকশো query-তেই ধরা পড়ত। Lark-এর কোনো usage reporting নেই; চালানোর আগে এর documentation আর উৎস দেখে নিশ্চিত হওয়া গেছে।

লক্ষ করুন, RD-এর কোনো function কখনো পেছনে ফেরে না, কোনো token দুবার পড়ে না। ডাকের গভীরতা বন্ধনীর গভীরতার অনুপাতে, আর মোট কাজ token-সংখ্যার অনুপাতে। এই দক্ষতা এসেছে grammar-এর একটি ধর্ম থেকে: প্রতিটি সিদ্ধান্ত এক token-এ হয়। কিন্তু সব grammar এমন নয়। দুটি বাধা আছে। প্রথমটি left recursion, যা পর্ব ৩০-এ সরানো শিখেছেন। দ্বিতীয়টি একই শুরুর একাধিক নিয়ম।

৩ · একই শুরু আর left factoring

বাজারঘর ঠিক করল, query-তে একটি দামের সীমাও চলবে: amount BETWEEN 500 AND 2000. Grammar-এ নতুন নিয়ম F → amount BETWEEN NUM AND NUM. এখন F-এর দুটি নিয়ম amount দিয়ে শুরু। Lookahead amount দেখে recursive descent জানে না কোন নিয়ম নেবে; পার্থক্য আসে পরের token-এ (R না BETWEEN). সমাধান সোজা: সিদ্ধান্ত পিছিয়ে দিন। আগে সাধারণ অংশ amount পড়ুন, তারপর একটি নতুন variable সিদ্ধান্ত নিক।

গঠন ৩.১ (Left factoring)

ধরুন A-এর কয়েকটি নিয়ম একই অশূন্য অংশ α দিয়ে শুরু: A → αβ1 ∣ ⋯ ∣ αβm ∣ γ1 ∣ ⋯ ∣ γk, যেখানে m ≥ ২ আর কোনো γj α দিয়ে শুরু নয়। একটি নতুন variable A′ নিয়ে লিখুন:

A → αA′ ∣ γ1 ∣ ⋯ ∣ γk, A′ → β1 ∣ ⋯ ∣ βm

সাধারণত α নেওয়া হয় সবচেয়ে লম্বা সাধারণ শুরু (longest common prefix), আর কোনো দুই বিকল্পের সাধারণ শুরু না থাকা পর্যন্ত গঠনটি বারবার খাটানো হয়। কোনো βi ফাঁকা হতে পারে; তখন A′ → ε.

উপপাদ্য ৩.২ (Left factoring language বদলায় না)

গঠন ৩.১-এর পরের grammar G′ হলে L(G′) = L(G).

প্রমাণ:

  1. G-এর যেকোনো derivation-এ A → αβi-এর একটি ব্যবহারকে G′-এ দুই ধাপে লেখা যায়: A ⇒ αA′ ⇒ αβi. A → γj দুই grammar-এই আছে। তাই L(G) ⊆ L(G′). — নিয়ম-বদল একটি একটি করে
  2. উল্টো দিকে, A′ নতুন variable, আর এটি শুধু A → αA′-এর ডান দিকে আসে। তাই G′-এর parse tree-তে প্রতিটি A′-node একটি A → αA′ node-এর সন্তান, আর A′-এর নিচে A′ → βi. এই দুই node জুড়ে একটি A → αβi node বানালে yield বদলায় না। — A′-এর নিয়ম শুধু গঠন ৩.১-এর
  3. প্রতিবার জোড়ায় A′-node একটি কমে, তাই সসীম বার পরে গাছটি G-এর। অতএব L(G′) ⊆ L(G), আর দুই দিক মিলিয়ে সমতা। ∎ — পর্ব ২৬-এর গাছ ⇔ derivation

অংশ ১-এর S → aSb ∣ ab-এ খাটান: α = a, β1 = Sb, β2 = b. ফল S → aS′, S′ → Sb ∣ b. এবার S′-এর দুটি নিয়মের প্রথম token আলাদা? Sb শুরু হয় S দিয়ে, আর S সবসময় a দিয়ে শুরু; b শুরু হয় b দিয়ে। তাই lookahead a মানে S′ → Sb, b মানে S′ → b: LL(1). কিন্তু left factoring সবসময় সফল হয় না। নিচের stepper দুটি ঘটনা দেখায়: বাজারঘরের BETWEEN সফলভাবে, আর dangling else, যেখানে সংঘাত থেকেই যায়। Table আর “conflict”-এর সংখ্যা অংশ ৪-এর কোড দিয়ে হিসাব করা (এই অংশে শুধু ফল)।

1F → amount R NUM2F → amount BETWEEN NUM AND NUM3F → amount A,  A → R NUM ∣ BETWEEN NUM AND NUM4S → iEtS ∣ iEtSeS ∣ a,  E → b5S → iEtS S′ ∣ a,  S′ → eS ∣ ε6বাস্তব সমাধান: M[S′, e] = S′ → eS
এই ধাপের অবস্থা
সংঘাতের ঘর
সাধারণ শুরু α
table
  1. সমস্যা। বাজারঘরের order-query-র F-এ দুটি নিয়ম amount দিয়ে শুরু। পুরো grammar-এর LL(1) table-এ ২৩টি ভরা ঘর, তার একটি M[F, amount]-এ দুটি নিয়ম: এক token দেখে বাছা অসম্ভব।
  2. সাধারণ শুরু খোঁজা। দুই নিয়মের সবচেয়ে লম্বা সাধারণ শুরু α = amount. বাকি অংশ β₁ = R NUM আর β₂ = BETWEEN NUM AND NUM. পার্থক্যটি amount-এর ঠিক পরের token-এ।
  3. Factor করা। F → amount A, A → R NUM ∣ BETWEEN NUM AND NUM. A-এর দুই নিয়মের প্রথম token-এর set {=, >=, <} আর {BETWEEN}, একে অপরের থেকে আলাদা। নতুন table-এ ২৭টি ঘর, কোনো ঘরে দুটি নিয়ম নেই: grammar LL(1). BETWEEN-এর ভেতরের AND কোনো সমস্যা করে না, কারণ A সেটি নিজের নিয়মে আগেই খরচ করে।
  4. Dangling else. সংক্ষিপ্ত রূপে i = if, t = then, e = else, E → b একটি শর্ত। S → iEtS আর S → iEtSeS দুটিই i দিয়ে শুরু: M[S, i]-এ দুটি নিয়ম। Table-এ মোট ৩টি ঘর, ১টি সংঘাত।
  5. Factor করা। α = iEtS, β₁ = ε, β₂ = eS. ফল S → iEtSS′ ∣ a, S′ → eS ∣ ε. প্রথম সংঘাত গেল। কিন্তু S′ nullable, আর FOLLOW(S′) = FOLLOW(S) = {e, $}. FIRST(eS) = {e}-ও, তাই M[S′, e]-এ আবার দুটি নিয়ম।
  6. কেন থেকে যায়। এই grammar ambiguous (পর্ব ২৭): “if b then if b then a else a”-এর দুটি parse tree. অংশ ৫ প্রমাণ করবে, কোনো ambiguous grammar LL(1) হতে পারে না, তাই left factoring এখানে সাহায্য করতে পারে না। বাস্তব parser ঘরটিতে শুধু S′ → eS রাখে: else সবচেয়ে কাছের জোড়াহীন if-এর সঙ্গে যায়।

সাধারণ ভুল: “Left factoring আর left recursion দূর করলেই যেকোনো grammar LL(1) হয়ে যায়” ভাবা। দুটি রূপান্তর language রক্ষা করে, কিন্তু LL(1) হওয়ার নিশ্চয়তা দেয় না। Ambiguous grammar কখনো LL(1) নয়, আর কিছু context-free language-এর কোনো LL(1) grammar-ই নেই (অংশ ৭)। রূপান্তরের পরে সবসময় table বানিয়ে conflict গুনুন।

৪ · FIRST আর FOLLOW — কোন token কোথা থেকে আসে

“এই নিয়মটি কোন token দিয়ে শুরু হতে পারে?” প্রশ্নটি এতক্ষণ চোখে দেখে উত্তর দিয়েছেন। Variable দিয়ে শুরু নিয়মে (যেমন E → TE′) উত্তর লুকিয়ে থাকে T-এর নিয়মে, তার ভেতরে F-এর নিয়মে। আর কোনো নিয়ম ফাঁকা হতে পারলে (E′ → ε) প্রশ্ন বদলে যায়: “E′ কিছু না বানালে তার পরে কী আসতে পারে?” এই দুই প্রশ্নের নিখুঁত উত্তর দুটি set.

সংজ্ঞা ৪.১ (FIRST আর FOLLOW)

G = (V, Σ, R, S) একটি CFG, α ∈ (V ∪ Σ)∗ চিহ্নের যেকোনো ক্রম, আর A ∈ V.

FIRST(α) = { a ∈ Σ : α ⇒∗ aβ কোনো β-র জন্য } ∪ { ε, যদি α ⇒∗ ε }
FOLLOW(A) = { a ∈ Σ : S ⇒∗ βAaγ কোনো β, γ-র জন্য } ∪ { $, যদি S ⇒∗ βA }

কথায়: FIRST(α) হলো α থেকে আসা string-গুলোর প্রথম terminal-এর set, আর α ফাঁকা হতে পারলে ε-ও। FOLLOW(A) হলো কোনো sentential form-এ A-এর ঠিক পরে বসতে পারা terminal-এর set, আর A একেবারে শেষে বসতে পারলে $. FOLLOW-এ ε কখনো থাকে না; সেই ভূমিকা $-এর।

সংজ্ঞায় “⇒∗” আছে, অর্থাৎ অসীম সংখ্যক derivation; সরাসরি হিসাব করা যায় না। কিন্তু পর্ব ২৮-এর nullable set-এর মতোই এখানেও একটি fixpoint iteration কাজ করে: সব set ফাঁকা থেকে শুরু করে কয়েকটি নিয়ম বারবার খাটান, যতক্ষণ কোনো set না বাড়ে।

Algorithm ৪.২ (FIRST আর FOLLOW-এর হিসাব)

চিহ্ন-ক্রমের FIRST: terminal a-র জন্য FIRST(a) = {a}; FIRST(ε) = {ε}. α = X1X2⋯Xn হলে FIRST(X1) − {ε} নিন; X1 nullable হলে FIRST(X2) − {ε}-ও; এভাবে প্রথম non-nullable চিহ্ন পর্যন্ত। সব Xi nullable হলে ε-ও যোগ করুন।
FIRST-এর নিয়ম: প্রতিটি নিয়ম A → α-র জন্য FIRST(A) ⊇ FIRST(α).
FOLLOW-এর নিয়ম: (১) $ ∈ FOLLOW(S). (২) প্রতিটি নিয়ম A → αBβ-র জন্য FOLLOW(B) ⊇ FIRST(β) − {ε}. (৩) তার ওপর β ⇒∗ ε হলে (β = ε-সহ) FOLLOW(B) ⊇ FOLLOW(A).
কোনো set আর না বাড়া পর্যন্ত নিয়মগুলো বারবার খাটান।

কেন থামে আর কেন সঠিক (প্রমাণের রূপরেখা): প্রতিটি set সসীম set Σ ∪ {ε, $}-এর উপসেট, আর প্রতিটি রাউন্ডে কোনো set ছোট হয় না। তাই বড়জোর |V|·(|Σ| + 2) রাউন্ডে সব থামে। শুদ্ধতার দুই দিক: (ক) প্রতিটি নিয়ম সংজ্ঞা থেকে সরাসরি সত্য, তাই যা যোগ হয় তা সত্যিই set-এ আছে (রাউন্ডের ওপর induction). (খ) উল্টো দিকে, a ∈ FIRST(A) হলে A ⇒∗ aβ-এর সবচেয়ে ছোট derivation-এর দৈর্ঘ্যের ওপর induction দিয়ে দেখানো যায় যে কোনো রাউন্ডে a যোগ হবেই; FOLLOW-এর জন্য S থেকে βAaγ-এর derivation-এর ওপর একই যুক্তি। ∎ এই পর্বের হিসাবের grammar পর্ব ৩০-এর left recursion-মুক্ত expression grammar, এখানে বলা হবে ETF grammar:

E → TE′, E′ → +TE′ ∣ ε, T → FT′, T′ → ∗FT′ ∣ ε, F → (E) ∣ id

নিচের stepper রাউন্ডে রাউন্ডে set-গুলো দেখায়। প্রতিটি রাউন্ড শুধু আগের রাউন্ডের শেষের set ব্যবহার করে, তাই তথ্য কীভাবে grammar-এর ভেতর দিয়ে “চলে” তা স্পষ্ট দেখা যায়। মানগুলো একটি scratch script-এ ঠিক এভাবে রাউন্ড ধরে হিসাব করে মেলানো।

1E → T E′2E′ → + T E′ ∣ ε3T → F T′4T′ → ∗ F T′ ∣ ε5F → ( E ) ∣ id
এই ধাপের set
ধাপ
E
E′
T
T′
F
  1. FIRST, রাউন্ড ১. সব set ফাঁকা থেকে শুরু। যে নিয়ম terminal দিয়ে শুরু, সেগুলো সঙ্গে সঙ্গে কাজ করে: E′ পায় + আর (ε-নিয়ম থেকে) ε, T′ পায় ∗ আর ε, F পায় ( আর id. E আর T-এর নিয়ম variable দিয়ে শুরু, যাদের set এখনো ফাঁকা।
  2. FIRST, রাউন্ড ২. T → FT′: F nullable নয়, তাই FIRST(T) = FIRST(F) = {(, id}. E এখনো আগের রাউন্ডের ফাঁকা FIRST(T) দেখছে।
  3. FIRST, রাউন্ড ৩. E → TE′ থেকে FIRST(E) = {(, id}. রাউন্ড ৪-এ কিছু বদলায় না, তাই FIRST শেষ। E, T, F তিনটিরই FIRST এক: প্রতিটি expression শেষ পর্যন্ত একটি ( বা id দিয়ে শুরু।
  4. FOLLOW, শুরু। নিয়ম (১): E start symbol, তাই $ ∈ FOLLOW(E). বাকি সব ফাঁকা।
  5. FOLLOW, রাউন্ড ১. F → (E): E-এর পরে ), তাই FOLLOW(E) = {), $}. E → TE′: T-এর পরে E′, FIRST(E′) − {ε} = {+}; E′ nullable, তাই FOLLOW(E)-এর আগের মান {$}-ও: FOLLOW(T) = {+, $}. E′ শেষে বসে: FOLLOW(E′) ⊇ আগের FOLLOW(E) = {$}. T → FT′ থেকে F পায় ∗. T′ পায় FOLLOW(T), কিন্তু তার আগের মান ফাঁকা ছিল।
  6. FOLLOW, রাউন্ড ২. আগের রাউন্ডের তথ্য এক স্তর নিচে নামে। E′ আর T পায় ) (FOLLOW(E) থেকে)। T′ আর F পায় আগের FOLLOW(T) = {+, $}; F-এর আগের ∗ থাকে।
  7. FOLLOW, রাউন্ড ৩. এখন FOLLOW(T)-এ ) এসেছে, তাই T′ আর F-ও ) পায়। রাউন্ড ৪-এ কিছু বদলায় না। ফল: FOLLOW(E) = FOLLOW(E′) = {), $}, FOLLOW(T) = FOLLOW(T′) = {+, ), $}, FOLLOW(F) = {+, ∗, ), $}.

এবার একই হিসাব কোডে। নিচের ব্লকের ll1(G, S) একটি loop-এ FIRST আর FOLLOW একসঙ্গে বাড়ায় (একই fixpoint, শুধু ক্রম আলাদা, তাই শেষ ফল একই), তারপর অংশ ৫-এর নিয়মে table ভরে, আর কোনো ঘরে দ্বিতীয় নিয়ম এলে তা bad-এ রাখে। Grammar একটি dict: প্রতিটি variable-এর নিয়মগুলো tuple, আর () মানে ε. এই পর্বের তিনটি Python ব্লক একই namespace ভাগ করে (data-shared); পরের ব্লক আগে চালালে এটি নিজে থেকে আগে চলবে।

EPS = "ε"            # grammar = {variable: [right sides as tuples]}, () = ε
def first_seq(seq, FI, G):                  # FIRST of a string of symbols
    out = set()
    for X in seq:
        f = FI[X] if X in G else {X}
        out |= f - {EPS}
        if EPS not in f: return out
    return out | {EPS}                       # every symbol can vanish
def ll1(G, S):
    FI, FO = {A: set() for A in G}, {A: set() for A in G}; FO[S].add("$")
    def look(seq, A):                        # FIRST(seq), plus FOLLOW(A) if seq =>* ε
        t = first_seq(seq, FI, G)
        return (t - {EPS}) | (FO[A] if EPS in t else set())
    rules, size = [(A, r) for A in G for r in G[A]], -1
    while size != (size := sum(map(len, [*FI.values(), *FO.values()]))):
        for A, r in rules:                   # fixpoint: repeat until no set grows
            FI[A] |= first_seq(r, FI, G)
            for i, B in enumerate(r):        # FOLLOW: what can come after B
                if B in G: FO[B] |= look(r[i + 1:], A)
    M, bad = {}, []                          # table M[A, a] = right side
    for A, r in rules:
        for a in look(r, A):
            if (A, a) in M: bad.append((A, a, M[A, a], r))
            else: M[A, a] = r
    return FI, FO, M, bad
st = lambda s: "{" + ", ".join(sorted(s, key=lambda x: (x in "ε$", x))) + "}"
ETF = {"E": [("T", "E'")], "E'": [("+", "T", "E'"), ()], "T": [("F", "T'")],
       "T'": [("*", "F", "T'"), ()], "F": [("(", "E", ")"), ("id",)]}
FI, FO, M, bad = ll1(ETF, "E")
for A in ETF: print(f"{A:2}  FIRST {st(FI[A]):10} FOLLOW {st(FO[A])}")
IF = {"S": [("i", "E", "t", "S"), ("i", "E", "t", "S", "e", "S"), ("a",)], "E": [("b",)]}
LF = {"S": [("i", "E", "t", "S", "S'"), ("a",)], "S'": [("e", "S"), ()], "E": [("b",)]}
for name, G, S in (("E/T/F", ETF, "E"), ("if-else", IF, "S"), ("left-factored", LF, "S")):
    _, _, T, bad = ll1(G, S); print(f"{name}: {len(T)} entries, {len(bad)} conflict(s)")
    for A, a, r1, r2 in bad: print(f"   M[{A}, {a}] = {' '.join(r1)}  OR  {' '.join(r2) or EPS}")

আসল আউটপুট (ব্রাউজারের Python):

E   FIRST {(, id}    FOLLOW {), $}
E'  FIRST {+, ε}     FOLLOW {), $}
T   FIRST {(, id}    FOLLOW {), +, $}
T'  FIRST {*, ε}     FOLLOW {), +, $}
F   FIRST {(, id}    FOLLOW {), *, +, $}
E/T/F: 13 entries, 0 conflict(s)
if-else: 3 entries, 1 conflict(s)
   M[S, i] = i E t S  OR  i E t S e S
left-factored: 5 entries, 1 conflict(s)
   M[S', e] = e S  OR  ε

প্রথম পাঁচ লাইন stepper-এর শেষ অবস্থার সঙ্গে হুবহু মেলে; শুধু ক্রমটি ASCII-র: ( আর ) আগে, তারপর * আর +. ETF grammar-এর table-এ ১৩টি ভরা ঘর, কোনো সংঘাত নেই, অর্থাৎ grammar-টি LL(1). Dangling-else grammar-এ left factoring-এর আগে সংঘাত M[S, i]-এ, পরে M[S′, e]-এ: stepper-এর ধাপ ৪ আর ৫. নিজের grammar পরীক্ষা করতে G বদলে দেখুন; যেমন S → aSb ∣ ab লিখলে M[S, a]-এ সংঘাত আসবে, আর অংশ ৩-এর factored রূপে আসবে না।

৫ · LL(1) parsing table আর LL(1) শর্ত

FIRST আর FOLLOW হাতে থাকলে predict-এর নিয়মটি এক লাইনে লেখা যায়। ধরুন stack-এর ওপরে A আর lookahead a. নিয়ম A → α নেওয়া অর্থবহ, যদি α থেকে a দিয়ে শুরু কিছু আসতে পারে, অথবা α পুরো ফাঁকা হয়ে গিয়ে A-এর পরের অংশ a দিয়ে শুরু হতে পারে।

সংজ্ঞা ৫.১ (LL(1) parsing table আর LL(1) grammar)

প্রতিটি নিয়ম A → α-র জন্য:

  • প্রতিটি terminal a ∈ FIRST(α)-র জন্য A → α-কে M[A, a] ঘরে বসান;
  • ε ∈ FIRST(α) হলে প্রতিটি b ∈ FOLLOW(A)-র জন্য (b = $-সহ) A → α-কে M[A, b] ঘরে বসান।

এই table-ই LL(1) parsing table; ফাঁকা ঘর মানে error. কোনো ঘরে একাধিক নিয়ম না এলে G একটি LL(1) grammar. একাধিক নিয়ম আসাকে বলে conflict.

ETF grammar-এর table নিচে। ১৩টি ভরা ঘর, প্রতিটিতে একটি নিয়ম; ফাঁকা ঘরে “—”. Lab-এ একই ll1 function CPython-এ চালিয়ে (সত্যিকারের run, Python 3.12.13, ll1_table.py) table ছাপানো হয়েছে, শেষ লাইন entries: 13 | conflicts: 0, আর প্রতিটি ঘর নিচের table-এর সঙ্গে মিলিয়ে দেখা হয়েছে।

Mid+∗()$
EE → TE′——E → TE′——
E′—E′ → +TE′——E′ → εE′ → ε
TT → FT′——T → FT′——
T′—T′ → εT′ → ∗FT′—T′ → εT′ → ε
FF → id——F → (E)——

T′-এর সারিটি ভালো করে দেখুন। ∗ দেখলে T′ → ∗FT′, কারণ আরেকটি গুণ আসছে। কিন্তু +, ) বা $ দেখলে T′ → ε: গুণের শিকল শেষ, কারণ এই তিনটিই FOLLOW(T′)-এ। আর id বা ( দেখলে ঘর ফাঁকা: “id id” বা “id (”-এর মতো input-এ একটি term-এর ঠিক পরে আরেকটি term কখনো বসে না, তাই সেখানেই error. Table থেকে সরাসরি একটি সমতুল্য শর্ত পাওয়া যায়, যা পরীক্ষায় প্রায়ই সংজ্ঞা হিসেবে চাওয়া হয়।

উপপাদ্য ৫.২ (LL(1) শর্ত)

ধরুন G-তে কোনো useless symbol নেই। G LL(1), যদি এবং কেবল যদি প্রতিটি variable A আর A-এর প্রতিটি দুটি আলাদা নিয়ম A → α ∣ β-র জন্য:

  1. FIRST(α) আর FIRST(β)-এ কোনো সাধারণ terminal নেই;
  2. α আর β-র বড়জোর একটি ε derive করতে পারে;
  3. β ⇒∗ ε হলে FIRST(α) আর FOLLOW(A)-এ কোনো সাধারণ terminal নেই, আর $ ∈ FOLLOW(A) হলে α ⇒∗ ε নয় (শর্ত ২ থেকেই আসে)।

প্রমাণ:

  1. সংজ্ঞা ৫.১ অনুযায়ী A → α বসে ঠিক look(α) = (FIRST(α) − {ε}) ∪ (ε ∈ FIRST(α) হলে FOLLOW(A)) set-এর ঘরগুলোতে। তাই A-এর ঘরে conflict ⇔ A-এর কোনো দুই নিয়মের জন্য look(α) ∩ look(β) ≠ ∅. — সংজ্ঞা ৫.১
  2. যদি কোনোটিই nullable না হয়, look(α) ∩ look(β) = FIRST(α) ∩ FIRST(β): শর্ত ১. — ধাপ ১
  3. যদি দুটিই nullable হয়, দুই look-এ FOLLOW(A) থাকে। Useless symbol নেই, তাই A কোনো sentential form-এ আসে আর তার পরে কিছু বসে বা A শেষে থাকে; ফলে FOLLOW(A) ≠ ∅, আর conflict অবশ্যম্ভাবী। তাই শর্ত ২ দরকার। — FOLLOW-এর সংজ্ঞা
  4. শুধু β nullable হলে look(β) ⊇ FOLLOW(A) আর look(α) = FIRST(α) − {ε}; তাদের ছেদ ফাঁকা হওয়াই শর্ত ৩. তিন ক্ষেত্র মিলিয়ে, conflict নেই ⇔ শর্ত ১–৩. ∎ — ধাপ ১–৩
উপপাদ্য ৫.৩ (LL(1) grammar-এর দুই ধর্ম)

যেকোনো LL(1) grammar (useless symbol ছাড়া) (ক) unambiguous, আর (খ) left-recursive নয়।

প্রমাণ (ক):

  1. ধরুন w ∈ L(G)-এর দুটি আলাদা leftmost derivation আছে। দুটি একই শুরু থেকে চলে, আর প্রথম যে ধাপে আলাদা হয়, সেখানে দুটির sentential form একই: xAγ, যেখানে x ∈ Σ∗ হলো w-এর ইতিমধ্যে তৈরি শুরু। একটি নেয় A → α, অন্যটি A → β, α ≠ β. — leftmost derivation-এর সংজ্ঞা
  2. w = xy লিখুন, আর a হোক y-এর প্রথম অক্ষর (y = ε হলে a = $). প্রথম derivation-এ αγ ⇒∗ y. হয় α থেকেই a দিয়ে শুরু কিছু আসে, তখন a ∈ FIRST(α); নয়তো α ⇒∗ ε আর a আসে γ থেকে, তখন S ⇒∗ xAγ দেখায় a ∈ FOLLOW(A). দুই ক্ষেত্রেই a ∈ look(α). — FIRST আর FOLLOW-এর সংজ্ঞা
  3. একই যুক্তিতে a ∈ look(β). তাই M[A, a]-এ দুটি নিয়ম, যা LL(1)-এর বিরোধী। অতএব দুটি leftmost derivation হতে পারে না, আর পর্ব ২৭-এর সংজ্ঞায় G unambiguous. ∎ — ধাপ ১–২

প্রমাণের রূপরেখা (খ): ধরুন A ⇒+ Aδ. A useful, তাই A থেকে কোনো terminal string আসে, অর্থাৎ এমন একটি derivation আছে যা শেষ পর্যন্ত এই চক্র ছেড়ে বেরোয়। চক্রের পথের প্রথম নিয়ম আর বেরোনোর পথের প্রথম নিয়ম কোনো এক জায়গায় একই variable-এর দুটি আলাদা নিয়ম। একটি নির্দিষ্ট terminal a দিয়ে শুরু string নিন যা চক্র একবার ঘুরে তারপর বেরিয়ে তৈরি হয়, আর আরেকটি যা সরাসরি বেরিয়ে তৈরি হয়: দুটির প্রথম token একই a, অথচ সেই জায়গায় দুই আলাদা নিয়ম নেওয়া হয়েছে, তাই একটি ঘরে conflict. পূর্ণ প্রমাণ Aho–Lam–Sethi–Ullman-এর Compilers বইয়ের top-down parsing অধ্যায়ে পাবেন। ∎

উপপাদ্যটির উল্টো সত্য নয়: unambiguous আর left recursion-মুক্ত grammar-ও LL(1) না হতে পারে, যেমন S → aSb ∣ ab (left factoring-এর আগে)। ব্যবহারিক অর্থ: grammar ambiguous হলে কোনো রূপান্তর-কৌশলেই তাকে LL(1) বানানো যাবে না যতক্ষণ ambiguity থাকে; আগে precedence-এর স্তর বসাতে হবে (পর্ব ২৭), তারপর left recursion সরাতে হবে, তারপর left factoring.

৬ · Stack-সহ predictive parser — এটি একটি PDA

Recursive descent-এ stack লুকিয়ে থাকে function-ডাকের ভেতরে। Table-চালিত parser সেটি খোলাখুলি রাখে: একটি stack, একটি input pointer, আর table M. শুরুতে stack-এ S তার নিচে $, input-এর শেষে $. তারপর এই loop:

Algorithm ৬.১ (Table-চালিত LL(1) parser)

X = stack-এর ওপরের চিহ্ন, a = lookahead.
১. X = $ আর a = $ হলে: গ্রহণ।
২. X একটি terminal আর X = a হলে: match, অর্থাৎ X pop করুন আর input এক ঘর এগোন।
৩. X একটি variable আর M[X, a] = X → Y1⋯Yk হলে: X pop করে Yk, …, Y1 push করুন (Y1 ওপরে), আর নিয়মটি output-এ লিখুন।
৪. অন্য সব ক্ষেত্রে: error.

Table-চালিত LL(1) parser-এর গঠন

id + id ∗ id পড়ার মাঝখানের একটি মুহূর্ত: প্রথম দুটি token মেলানো শেষ, stack-এর ওপরে T, lookahead id.

Table-driven LL(1) parser: input, stack, table and driver input stack id+ id∗ id$ TE′$ T → F T′ lookahead LL(1) চালক সসীম নিয়ন্ত্রণ table M M[T, id] = output: T → F T′
ছবি ৩৮.১ — চালক শুধু দুটি চিহ্ন দেখে (stack-এর ওপরে T, lookahead id), table-এর একটি ঘর পড়ে, আর T-কে F T′ দিয়ে বদলায় (F ওপরে)। Input-এ শুধু সামনে এগোনো যায়; stack-এ শুধু ওপরে push/pop. এই গঠনটিই একটি pushdown automaton.

নিচের stepper পুরো parse-টি দেখায়, কয়েকটি predict আর match একসঙ্গে জুড়ে আটটি ধাপে। শেষ লাইনে থাকে “এখন পর্যন্ত মেলানো input + stack”, যা প্রতিটি মুহূর্তে leftmost derivation-এর একটি sentential form. পরের Python ব্লক একই parse ১৭টি সারিতে ছাপে।

1E → T E′2E′ → + T E′ ∣ ε3T → F T′4T′ → ∗ F T′ ∣ ε5F → ( E ) ∣ id
এই ধাপের অবস্থা
stack (ওপর বাঁয়ে)
বাকি input
কাজ
  1. শুরু। Stack-এ E, তার নিচে $. Input-এর শেষে $ বসানো। Lookahead id.
  2. তিনটি predict. M[E, id] = E → TE′; তারপর ওপরে T, M[T, id] = T → FT′; তারপর F, M[F, id] = F → id. কোনো token খরচ হয়নি, কিন্তু stack-এর ওপরে এখন terminal id.
  3. Match id. Stack-এর id আর input-এর id মিলল, দুটিই সরল। Sentential form বদলায়নি, শুধু id-টি “মেলানো” অংশে গেল।
  4. ε আর +. ওপরে T′, lookahead +. + ∈ FOLLOW(T′), তাই M[T′, +] = T′ → ε: গুণের শিকল শেষ, T′ pop. তারপর E′ আর +: E′ → +TE′, আর + match.
  5. দ্বিতীয় id. T → FT′, F → id, match id. Form এখন id + id T′ E′.
  6. গুণ। ওপরে T′, lookahead ∗: M[T′, ∗] = T′ → ∗FT′. ∗ match. এখানে T′ ε নেয়নি, কারণ ∗ FOLLOW(T′)-এ নেই, FIRST(∗FT′)-এ আছে।
  7. তৃতীয় id. F → id আর match. Input-এ শুধু $ বাকি, stack-এ T′ E′ $.
  8. শেষ। $ ∈ FOLLOW(T′) আর FOLLOW(E′), তাই T′ → ε, E′ → ε. ওপরে $, lookahead $: গ্রহণ। মোট ১১টি predict আর ৫টি match; predict-গুলো ক্রমে পড়লে id + id ∗ id-এর leftmost derivation.

এবার কোডে। নিচের parse আগের ব্লকের ll1 দিয়ে table বানায় আর Algorithm ৬.১ চালায়, প্রতিটি পদক্ষেপে stack (ওপর বাঁয়ে), বাকি input আর কাজ ছাপে। Error হলে সে ওপরের চিহ্নের সারিতে কোন token-গুলোর ঘর ভরা আছে, তা “expected” হিসেবে বলে।

def parse(G, S, toks):                      # table-driven LL(1), explicit stack
    M = ll1(G, S)[2]
    inp, stack, k = toks + ["$"], ["$", S], 0     # top of stack = end of list
    while True:
        X, a = stack[-1], inp[k]
        print(f"{' '.join(reversed(stack)):13} {' '.join(inp[k:]):12}", end=" ")
        if X == "$" == a: print("accept"); return True
        if X not in G and X == a:               # terminal on top: match
            stack.pop(); k += 1; print("match", a)
        elif (X, a) in M:                       # variable on top: predict
            stack.pop(); stack.extend(reversed(M[X, a]))
            print(f"{X} -> {' '.join(M[X, a]) or EPS}")
        else:
            want = sorted(b for (A, b) in M if A == X) if X in G else [X]
            print(f"\nerror at token {k + 1} '{a}': expected one of {want}")
            return False
parse(ETF, "E", "id + id * id".split())
print()
parse(ETF, "E", "id + * id".split())

আসল আউটপুট (ব্রাউজারের Python):

E $           id + id * id $ E -> T E'
T E' $        id + id * id $ T -> F T'
F T' E' $     id + id * id $ F -> id
id T' E' $    id + id * id $ match id
T' E' $       + id * id $  T' -> ε
E' $          + id * id $  E' -> + T E'
+ T E' $      + id * id $  match +
T E' $        id * id $    T -> F T'
F T' E' $     id * id $    F -> id
id T' E' $    id * id $    match id
T' E' $       * id $       T' -> * F T'
* F T' E' $   * id $       match *
F T' E' $     id $         F -> id
id T' E' $    id $         match id
T' E' $       $            T' -> ε
E' $          $            E' -> ε
$             $            accept

E $           id + * id $  E -> T E'
T E' $        id + * id $  T -> F T'
F T' E' $     id + * id $  F -> id
id T' E' $    id + * id $  match id
T' E' $       + * id $     T' -> ε
E' $          + * id $     E' -> + T E'
+ T E' $      + * id $     match +
T E' $        * id $
error at token 3 '*': expected one of ['(', 'id']

প্রথম parse-এ ১৭টি সারি: ১১টি predict, ৫টি match আর শেষে accept, stepper-এর আট ধাপের সঙ্গে হুবহু মেলে। দ্বিতীয় input “id + ∗ id”-এ + মেলানোর পর ওপরে T, lookahead ∗, আর M[T, ∗] ফাঁকা। Parser ঠিক এই মুহূর্তে থামে: তৃতীয় token-এ, যেখানে ভুলটি প্রথম চোখে পড়ে, আর বলে T-এর সারিতে শুধু ( আর id-এর ঘর ভরা। এই ধর্মকে বলে valid prefix property: LL(1) parser কখনো এমন token পার হয় না, যার পরে input আর কোনোভাবে বৈধ হতে পারে না।

উপপাদ্য ৬.২ (Predictive parser-এর শুদ্ধতা আর গতি)

G একটি LL(1) grammar হলে Algorithm ৬.১ প্রতিটি input w-তে থামে, w ∈ L(G) হলে এবং কেবল তখনই গ্রহণ করে, আর গ্রহণের সময় output-এর নিয়মগুলো w-এর leftmost derivation. মোট পদক্ষেপ |w|-এর অনুপাতে (grammar স্থির ধরে)।

প্রমাণের রূপরেখা: (১) Invariant: প্রতিটি মুহূর্তে x = মেলানো input আর γ = stack ($ বাদে) হলে S ⇒lm∗ xγ. Predict একটি leftmost ধাপ যোগ করে, match শুধু চিহ্নটিকে x-এ সরায়। তাই গ্রহণ মানে S ⇒∗ w: যা গ্রহণ হয় তা language-এ আছে। (২) উল্টো দিকে, w ∈ L(G) হলে তার leftmost derivation-এর প্রতিটি ধাপের নিয়ম উপপাদ্য ৫.৩-এর ধাপ ২-এর যুক্তিতে look-set-এ lookahead ধারণ করে, আর ঘরে একটিই নিয়ম, তাই parser ঠিক সেই derivation অনুসরণ করে। (৩) থামা আর গতি: G left-recursive নয় (উপপাদ্য ৫.৩), তাই দুটি match-এর মাঝে টানা predict-এর সংখ্যা grammar-এর ওপর নির্ভরশীল একটি ধ্রুবক দিয়ে বাঁধা; match হয় ঠিক |w| বার। ∎

এখন সংযোগটি দেখুন। Algorithm ৬.১-এর যন্ত্রে আছে একটি সসীম নিয়ন্ত্রণ (table M, যা সসীম), একটি stack আর এক দিকে চলা input: হুবহু পর্ব ৩২-এর pushdown automaton. পর্ব ৩৪-এর CFG → PDA গঠনের সঙ্গে পার্থক্য একটিই: সেখানে প্রতিটি predict-এ সব নিয়ম ছিল সম্ভাব্য পথ, এখানে lookahead দেখে বড়জোর একটি। Lookahead-টি PDA-র state-এ রাখা যায় (input থেকে একটি অক্ষর পড়ে state-এ “মনে রাখা”), তাই প্রতিটি LL(1) grammar থেকে একটি deterministic PDA পাওয়া যায়, যা $-চিহ্নিত input-এর language চেনে। ফলে প্রতিটি LL(1) language একটি deterministic CFL. Deterministic PDA আর DCFL-এর পুরো তত্ত্ব পর্ব ৩৫-এ দেখেছেন; সেখানকার ফলগুলো এখানে সরাসরি খাটে।

৭ · Error ধরা, panic mode, আর LL(k) থেকে ALL(*)

বাস্তব parser-এর কাছে প্রথম error-এ থেমে যাওয়া যথেষ্ট নয়। বাজারঘরের admin panel-এ একজন কর্মী লম্বা query লিখে পাঠালে তিনি এক চালনায় যত বেশি ভুল দেখেন, তত ভালো। সবচেয়ে প্রচলিত কৌশল panic mode recovery, যা পর্ব ২২-এ lexer-এর স্তরে দেখেছেন। Parser-এর স্তরে নিয়মটি: variable A পার্স করতে গিয়ে error হলে input থেকে token ফেলতে থাকুন, যতক্ষণ না একটি synchronizing token আসে; তারপর ধরে নিন A শেষ হয়েছে আর এগিয়ে চলুন। Synchronizing set-এর স্বাভাবিক পছন্দ FOLLOW(A): এগুলোর একটি এলে A-এর পরের অংশ নির্ভরযোগ্যভাবে শুরু করা যায়।

নিচের JavaScript ব্লক অংশ ২-এর order-query parser, এবার token-এর অবস্থান-সহ error বার্তা আর F-এর স্তরে panic mode নিয়ে। FOLLOW(F) = {AND, OR, ), $}, যা অংশ ৪-এর ll1 দিয়ে পুরো order-query grammar-এ হিসাব করে মেলানো। চারটি query দেওয়া আছে; নিজের query যোগ করে দেখুন।

// Recursive descent for the Bazarghar order query, with panic-mode recovery.
function parse(src) {
  const t = src.match(/>=|[()=<]|"[^"]*"|\w+|\S/g).concat(["$"]);
  let k = 0; const errs = [];
  const kind = () => /^\d+$/.test(t[k]) ? "NUM" : t[k][0] === '"' ? "STR" : t[k];
  const eat = w => { if (kind() === w) return t[k++];
                     throw `token ${k + 1} '${t[k]}': expected ${w}`; };
  const SYNC = ["AND", "OR", ")", "$"];             // FOLLOW(F) = sync set
  function F() {
    try {
      const x = kind();
      if (x === "(") { k++; const c = C(); eat(")"); return c; }
      if (x === "amount") { k++; const r = t[k];
        if (!["=", ">=", "<"].includes(r)) eat("= >= <"); k++;
        return `(amount${r}${eat("NUM")})`; }
      if (x === "district" || x === "status") { k++; eat("="); return `(${x}=${eat("STR")})`; }
      eat("( amount district status");
    } catch (e) {                                  // panic: skip to a sync token
      errs.push(e); while (!SYNC.includes(t[k])) k++; return "ERR";
    }
  }
  function T() { let x = F(); while (kind() === "AND") { k++; x = `AND[${x} ${F()}]`; } return x; }
  function C() { let x = T(); while (kind() === "OR") { k++; x = `OR[${x} ${T()}]`; } return x; }
  try { eat("FIND"); eat("order"); eat("WHERE"); const c = C(); eat("$");
        return errs.length ? errs : c; }
  catch (e) { return errs.concat(e); }
}
for (const q of ['FIND order WHERE amount >= 1000 AND district = "Dhaka"',
                 'FIND order WHERE status = "paid" OR amount < 500 AND district = "Sylhet"',
                 'FIND order WHERE amount >> 5 AND district "Dhaka" OR status = "paid"',
                 'FIND order WHERE ( status = "paid" OR'])
{ const r = parse(q);
  console.log(Array.isArray(r) ? "errors: " + r.join(" | ") : "tree: " + r); }

আসল আউটপুট (ব্রাউজারের JavaScript):

tree: AND[(amount>=1000) (district="Dhaka")]
tree: OR[(status="paid") AND[(amount<500) (district="Sylhet")]]
errors: token 5 '>': expected = >= < | token 10 '"Dhaka"': expected =
errors: token 9 '$': expected ( amount district status | token 9 '$': expected )

দ্বিতীয় query-তে গাছটি OR[… AND[…]]: AND আগে বাঁধে, grammar-এর স্তর অনুযায়ী। তৃতীয় query-তে দুটি ভুল, আর parser এক চালনায় দুটিই ধরেছে: token 5-এ >> (lexer এটিকে দুটি > হিসেবে দেয়, আর > কোনো বৈধ তুলনা নয়), তারপর panic mode-এ AND পর্যন্ত বাদ দিয়ে আবার শুরু, আর token 10-এ = হারানো। চতুর্থ query-তে ভুল আসলে একটি (OR-এর পরে কিছু নেই), কিন্তু দুটি বার্তা এসেছে: ভেতরের F ব্যর্থ হয়ে $-এ থামে, তারপর বাইরের F-এর )-ও পায় না। একে বলে cascading error: panic mode-এর পরিচিত দুর্বলতা। ভালো compiler এমন দ্বিতীয় বার্তা চেপে রাখে, যেমন একই অবস্থানে দ্বিতীয় বার্তা না দেখানো।

LL(k): আরও token দেখা। এক token যথেষ্ট না হলে k token দেখা যায়। LL(k) grammar-এ পরের k-টি token দেখে প্রতিটি নিয়ম নিশ্চিতভাবে বাছা যায়; table-এর কলাম তখন k দৈর্ঘ্যের token-ক্রম, যার সংখ্যা |Σ|k পর্যন্ত হতে পারে। তাই বাস্তবে বড় k-এর পূর্ণ table প্রায় কেউ বানায় না। তাত্ত্বিক দিক থেকে কয়েকটি সুপরিচিত ফল (প্রমাণ এখানে বাদ, Aho ও Ullman-এর “The Theory of Parsing, Translation, and Compiling” বইয়ে পাবেন):

  • প্রতিটি k-র জন্য এমন language আছে যার LL(k+1) grammar আছে কিন্তু LL(k) grammar নেই; অর্থাৎ LL(k) language-এর শ্রেণিগুলো k বাড়ার সঙ্গে কঠোরভাবে বড় হয়। ফলটি সাধারণত Kurki-Suonio (১৯৬৯) আর Rosenkrantz ও Stearns (১৯৭০)-এর কাজের সঙ্গে যুক্ত করা হয়।
  • সব LL(k) language deterministic CFL, কিন্তু উল্টো সত্য নয়। পাঠ্যবইয়ে প্রায়ই উদাহরণ দেওয়া হয় {anbn : n ≥ 1} ∪ {ancn : n ≥ 1}: একটি DPDA a-গুলো stack-এ রেখে b বা c দেখে সহজেই চেনে, কিন্তু top-down parser-কে শুরুতেই, কোনো সসীম lookahead-এ শেষের অক্ষর না দেখে, ঠিক করতে হতো কোন শাখা নেবে।
  • প্রতিটি LL(k) grammar একটি LR(k) grammar; পরের পর্বের bottom-up পদ্ধতি তাই কঠোরভাবে বেশি grammar নেয়।

ALL(*): দরকার মতো দেখা। ANTLR parser generator-এর লেখক Terence Parr আর সহকর্মীরা ভিন্ন পথ নেন। ANTLR 3-এর LL(*) প্রতিটি সিদ্ধান্তের জন্য একটি DFA বানিয়ে প্রয়োজনমতো অনেক token দেখত। ANTLR 4 (২০১৩ সালের দিকে প্রকাশিত) ALL(*) ব্যবহার করে: সিদ্ধান্তের মুহূর্তে বিকল্পগুলো একসঙ্গে সামনে চালিয়ে দেখে কোনটি টেকে, আর ফল cache করে রাখে। Parr, Harwell আর Fisher-এর ২০১৪ সালের OOPSLA প্রবন্ধ “Adaptive LL(*) Parsing: The Power of Dynamic Analysis” এর বর্ণনা দেয়, আর সেখানে দাবি করা হয়েছে যে সবচেয়ে খারাপ ক্ষেত্রে সময় O(n4) হলেও বাস্তব grammar-এ প্রায় রৈখিক। Parser generator হাতে-কলমে আসবে পর্ব ৪০ “Parser generator — Lark, ANTLR আর grammar থেকে parser”-এ, আর পূর্ণ compiler নির্মাণ একটি ভবিষ্যৎ “Programming Languages & Compilers” কোর্সে।

“LL(k)” নামটি সাধারণত Philip Lewis আর Richard Stearns-এর ১৯৬৮ সালের syntax-directed translation-এর কাজের সঙ্গে যুক্ত, আর LL(k) grammar-এর ধর্মগুলোর বিস্তারিত বিশ্লেষণ Daniel Rosenkrantz ও Stearns-এর ১৯৭০ সালের “Properties of deterministic top-down grammars” প্রবন্ধে। Recursive descent তারও আগে থেকে হাতে লেখা compiler-এ ব্যবহৃত হতো; Niklaus Wirth-এর Pascal compiler (১৯৭০-এর দশকের শুরু) এর বিখ্যাত উদাহরণ, আর Wirth নিজের ভাষাগুলোর syntax ইচ্ছা করেই এমনভাবে নকশা করতেন যাতে এক token দেখে parse করা যায়। আজও বড় compiler-গুলোর অনেকে হাতে লেখা recursive descent ব্যবহার করে; যেমন Clang-এর C/C++ parser, আর GCC ২০০০-এর দশকের মাঝামাঝি তার yacc/Bison-ভিত্তিক C++ parser বদলে হাতে লেখা recursive descent parser নেয় বলে পরিচিত। প্রতিটি সাল উৎসভেদে সামান্য আলাদা লেখা থাকতে পারে।

আরও গভীরে: দুটি LL(k) grammar একই language দেয় কি না, এই প্রশ্ন decidable বলে Rosenkrantz ও Stearns-এর ১৯৭০ সালের কাজে দেখানো হয়েছে বলে পরিচিত; অথচ সাধারণ CFG-এর জন্য একই প্রশ্ন undecidable (পর্ব ৩৭). আরও বড় শ্রেণি deterministic PDA-র equivalence-ও decidable, যা Géraud Sénizergues ১৯৯৭ সালের দিকে প্রমাণ করেন এবং এর জন্য ২০০২ সালে Gödel Prize পান। অন্যদিকে, নির্দিষ্ট k দেওয়া থাকলে “এই grammar কি LL(k)?” decidable, কিন্তু “এই grammar কি কোনো k-র জন্য LL(k)?” প্রশ্নটি undecidable বলে পরিচিত। অর্থাৎ “আমার grammar কি LL(1)?” যন্ত্রে মুহূর্তে উত্তর পায় (table বানান), কিন্তু k খোলা রাখলে আর নয়।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • FIRST আর FOLLOW-এর সংজ্ঞা দিন; FOLLOW-এ ε থাকে কি? না; “শেষে বসতে পারে” বোঝাতে $ থাকে।
  • একটি grammar-এর LL(1) table বানান। A → α বসে FIRST(α)-র ঘরে, আর α nullable হলে FOLLOW(A)-র ঘরে; কোনো ঘরে দুটি নিয়ম মানে LL(1) নয়।
  • A → abC ∣ abD ∣ e-এ left factoring করুন। A → abA′ ∣ e, A′ → C ∣ D.
  • Ambiguous grammar কেন LL(1) হতে পারে না? দুটি leftmost derivation প্রথম যেখানে আলাদা, সেখানকার lookahead দুই নিয়মের look-set-এই পড়ে: একটি ঘরে দুটি নিয়ম।
  • Recursive descent আর table-চালিত parser-এর পার্থক্য? প্রথমটিতে stack হলো function-ডাক, দ্বিতীয়টিতে খোলাখুলি একটি stack আর table; দুটিই একই সিদ্ধান্ত নেয়।

৮ · AI-এর যুগে LL(1) parsing

“এই grammar-এর FIRST, FOLLOW আর LL(1) table দাও” বললে AI assistant সাধারণত সুন্দর সাজানো একটি table দেয়। ভুলগুলো প্রায়ই একই জায়গায়: nullable নিয়মে FOLLOW যোগ করতে ভুলে যাওয়া, start symbol-এর FOLLOW-এ $ না রাখা বা উল্টো সবার FOLLOW-এ $ বসিয়ে দেওয়া, conflict থাকা সত্ত্বেও “LL(1)” ঘোষণা করা, আর left-recursive grammar-এর জন্য সরাসরি recursive descent কোড লিখে দেওয়া। নিচের ব্লক একটি নমুনা AI-উত্তর (AI যেমন প্রায়ই দেয়) পরীক্ষা করে: grammar S → Aa ∣ b, A → a ∣ ε-এর জন্য দাবি করা set আর “এটি LL(1)” দাবি।

# An AI answer for  S -> A a | b,  A -> a | ε  claimed these sets and "LL(1)".
G = {"S": [("A", "a"), ("b",)], "A": [("a",), ()]}
claim = {"FIRST": {"S": {"a", "b"}, "A": {"a", EPS}},
         "FOLLOW": {"S": {"$"}, "A": {"$"}}}
FI, FO, M, bad = ll1(G, "S")
for A in G:
    for name, got in (("FIRST", FI[A]), ("FOLLOW", FO[A])):
        want = claim[name][A]
        print(f"{name}({A}): claimed {st(want):8} computed {st(got):8}",
              "ok" if want == got else "WRONG")
print("conflicts:", [(A, a, " ".join(r1) or EPS, " ".join(r2) or EPS) for A, a, r1, r2 in bad])
for w in ("a", "aa", "b"):                  # table keeps the first entry only
    print(f"--- {w}:"); parse(G, "S", list(w))

আসল আউটপুট (ব্রাউজারের Python):

FIRST(S): claimed {a, b}   computed {a, b}   ok
FOLLOW(S): claimed {$}      computed {$}      ok
FIRST(A): claimed {a, ε}   computed {a, ε}   ok
FOLLOW(A): claimed {$}      computed {a}      WRONG
conflicts: [('A', 'a', 'a', 'ε')]
--- a:
S $           a $          S -> A a
A a $         a $          A -> a
a a $         a $          match a
a $           $
error at token 2 '$': expected one of ['a']
--- aa:
S $           a a $        S -> A a
A a $         a a $        A -> a
a a $         a a $        match a
a $           a $          match a
$             $            accept
--- b:
S $           b $          S -> b
b $           b $          match b
$             $            accept

দাবি করা set-গুলোর তিনটি ঠিক, কিন্তু FOLLOW(A) ভুল: S → Aa নিয়মে A-এর ঠিক পরে a বসে, তাই FOLLOW(A) = {a}, $ নয়। “A শেষে আছে” ভেবে $ বসানো একটি সাধারণ ভুল। সঠিক FOLLOW দিয়ে দেখা যায় M[A, a]-এ A → a আর A → ε দুটিই আসে: grammar LL(1) নয়। Conflict-টি উপেক্ষা করে table প্রথম নিয়মটি রাখলে কী হয়, তা শেষ অংশ দেখায়: “a” language-এ আছে (S ⇒ Aa ⇒ a, A → ε নিয়ে), অথচ parser তা বর্জন করেছে। কোনো error বার্তা grammar-এর দোষ বলে না, শুধু একটি বৈধ input নীরবে ভুল উত্তর পায়। Language-টি {a, aa, b}, আর A-এর সিদ্ধান্তে দ্বিতীয় token লাগে: grammar-টি LL(2).

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Nullable নিয়মে FOLLOW যোগ না করা, বা A → αB-এর FOLLOW(A) ⊆ FOLLOW(B) নিয়ম ভুলে যাওয়াAlgorithm ৪.২-এর তিনটি FOLLOW নিয়ম প্রতিটি নিয়মের প্রতিটি variable-এ একবার করে খাটান, বা ll1-এর মতো কোড চালান
Start ছাড়া অন্য variable-এর FOLLOW-এ বিনা কারণে $, বা FOLLOW-এ ε$ আসে শুধু S থেকে বা শেষে-বসা variable-এর শিকল ধরে; FOLLOW-এ ε কখনো থাকে না
Conflict থাকা সত্ত্বেও “LL(1)” ঘোষণাপ্রতিটি ঘর গুনুন; একটি ঘরে দুটি নিয়ম থাকলেই LL(1) নয়, আর সেই ঘরের একটি ছোট input-এ parser চালিয়ে দেখুন
Left-recursive বা ambiguous grammar-এ সরাসরি recursive descent কোডপ্রথম-চিহ্নের graph-এ চক্র খুঁজুন (পর্ব ৩০); ambiguity থাকলে আগে precedence-স্তর বসান (পর্ব ২৭)
Left factoring বা left recursion সরানোর পরে language বদলে যাওয়াছোট দৈর্ঘ্য পর্যন্ত দুই grammar-এর সব string brute force-এ মেলান, বা অংশ ২-এর মতো Earley parser-এর সঙ্গে হাজার input-এ তুলনা করুন
বানানো ইতিহাস বা ভুল দাবি (“ANTLR 4 যেকোনো left recursion নেয়”)মূল প্রবন্ধ বা documentation নিজে পড়ুন; Aho–Lam–Sethi–Ullman আর tool-এর নিজের manual মিলিয়ে নিন

AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু শেষ table নয়, প্রতিটি FIRST/FOLLOW যোগের কারণ আর একটি যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্ব শিখছি। Grammar (S start symbol): S → A B c | d A → a A | ε B → b | ε ১. প্রতিটি variable-এর FIRST আর FOLLOW set বের করো। প্রতিটি উপাদান কোন নিয়ম থেকে এল, এক লাইনে কারণ লেখো। ২. LL(1) parsing table বানাও। কোনো ঘরে দুটি নিয়ম এলে স্পষ্ট করে conflict বলো। ৩. Grammar-টি LL(1) কি না বলো, আর "a b c" input-এর parse stack ধরে ধাপে ধাপে দেখাও। ৪. শুধু Python standard library দিয়ে একটি কোড দাও, যা FIRST/FOLLOW fixpoint-এ হিসাব করে, table বানায় আর conflict ছাপে। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

(নিজে যাচাই করুন: FIRST(A) = {a, ε}, FIRST(B) = {b, ε}, FIRST(S) = {a, b, c, d}; FOLLOW(S) = {$}, FOLLOW(A) = {b, c}, FOLLOW(B) = {c}. Table-এ কোনো conflict নেই, তাই grammar-টি LL(1). AI-এর উত্তর এই পর্বের ll1 ব্লকে grammar বসিয়ে মিলিয়ে নিন।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Parser generator থাকতেও Clang বা GCC-র মতো বড় compiler কেন হাতে লেখা recursive descent parser ব্যবহার করে?

Parser generator (yacc, Bison, ANTLR) grammar থেকে স্বয়ংক্রিয়ভাবে parser বানায়, আর শুদ্ধতার দিক থেকে এটি নিরাপদ: grammar-টিই documentation, আর conflict থাকলে tool জানিয়ে দেয়। তবু বাস্তবের অনেক বড় compiler হাতে লেখা recursive descent বেছে নিয়েছে। Clang শুরু থেকেই হাতে লেখা parser ব্যবহার করে, আর GCC ২০০০-এর দশকের মাঝামাঝি তার Bison-ভিত্তিক C++ parser সরিয়ে হাতে লেখা recursive descent parser আনে বলে পরিচিত। কারণগুলো তত্ত্ব আর প্রকৌশলের মিশ্রণ।

প্রথম কারণ: বাস্তব ভাষা পুরোপুরি context-free নয়। C-তে a * b; একটি গুণ, না b নামের একটি pointer-এর ঘোষণা, তা নির্ভর করে a আগে typedef হিসেবে ঘোষিত হয়েছে কি না তার ওপর। পর্ব ২২-এ এর একটি সমাধান “lexer hack” দেখেছেন। C++-এ এ ধরনের প্রশ্ন আরও জটিল, কখনো template-এর অর্থ না জেনে parse-ই করা যায় না। হাতে লেখা parser প্রতিটি সিদ্ধান্তে symbol table দেখতে পারে, প্রয়োজনে কয়েকটি token সামনে দেখে আবার ফিরে আসতে পারে; generated table-এ এই নমনীয়তা আনা কঠিন।

দ্বিতীয় কারণ: error বার্তা। অংশ ৬-এর parser বলেছে “expected one of ['(', 'id']”, যা সঠিক কিন্তু যান্ত্রিক। হাতে লেখা parser প্রতিটি function-এ জানে সে কী পার্স করছে (একটি function call, একটি for loop), তাই বলতে পারে “for-এর পরে ( দরকার” বা “এখানে সম্ভবত একটি ; বাদ পড়েছে”, আর error-এর পরে কোথা থেকে আবার শুরু করবে তাও প্রসঙ্গ বুঝে ঠিক করতে পারে। তৃতীয় কারণ: IDE আর টুলিং। আজকের editor আধা-লেখা, ভুলে ভরা code-এও autocomplete চায়, তাই parser-কে ভুলের মধ্যেও যতটা সম্ভব গাছ বানাতে হয়।

দাম হলো রক্ষণাবেক্ষণ: grammar আর কোড আলাদা হয়ে যেতে পারে, আর একটি নতুন syntax যোগ করলে কোথায় সংঘাত তৈরি হলো তা কোনো tool বলে দেয় না। এজন্যই অনেক দল হাতে লেখা parser-এর পাশে একটি formal grammar রাখে আর অংশ ২-এর মতো তুলনামূলক পরীক্ষা চালায়।

মূল উপলব্ধি: LL(1) তত্ত্ব হাতে লেখা parser-এর মেরুদণ্ড: প্রতিটি function-এ “এই token দেখলে এই শাখা” আসলে FIRST/FOLLOW-এর হিসাব। Generator আর হাতে লেখার মধ্যে বাছাই হয় ভাষার জটিলতা, error বার্তার মান আর রক্ষণাবেক্ষণের খরচ মিলিয়ে।

প্র ০২LL(1) parser এক token দেখে, LR(1) parser-ও এক token দেখে। তবু LR কেন বেশি grammar নেয়? “ক্ষমতা”-র পার্থক্যটি কোথা থেকে আসে?

পার্থক্যটি সিদ্ধান্তের সময় নিয়ে। LL parser একটি নিয়ম বাছে নিয়মের ডান দিকের কিছুই পড়ার আগে, শুধু প্রথম token দেখে। LR parser (পর্ব ৩৯) নিয়মের ডান দিকের পুরোটা পড়ে ফেলার পরে, আর তারও পরের একটি token দেখে, সিদ্ধান্ত নেয় এটি কোন নিয়মের শেষ। তাই LR-এর হাতে অনেক বেশি তথ্য থাকে। E → E + T-এর মতো left-recursive নিয়ম LR-এর জন্য কোনো সমস্যাই নয়, কারণ সে E আগে সম্পূর্ণ পড়ে, তারপর + দেখে।

একটি পরিষ্কার উদাহরণ {anbn : n ≥ 1} ∪ {ancn : n ≥ 1}. একটি deterministic PDA a-গুলো stack-এ রাখে, তারপর প্রথম b বা c দেখে ঠিক করে কী মেলাতে হবে। কিন্তু top-down parser-কে start symbol খোলার মুহূর্তেই ঠিক করতে হয় “b-শাখা না c-শাখা”, আর তখন lookahead-এ শুধু প্রথম কয়েকটি a. n যেকোনো বড় হতে পারে, তাই কোনো নির্দিষ্ট k-এর lookahead যথেষ্ট নয়। পাঠ্যবইয়ে এই language-কে প্রায়ই এমন একটি deterministic CFL-এর উদাহরণ হিসেবে দেওয়া হয়, যার কোনো LL(k) grammar নেই; সম্পূর্ণ প্রমাণে দেখাতে হয় যে কোনো grammar-ই এই সিদ্ধান্ত পিছিয়ে দিতে পারে না।

তত্ত্বে ক্রমটি এমন: LL(1) language ⊊ LL(2) language ⊊ ⋯, সব LL(k) language ⊊ deterministic CFL, আর deterministic CFL-গুলো ঠিক সেই language, যাদের LR(1) grammar আছে (Knuth-এর ১৯৬৫ সালের LR প্রবন্ধের সঙ্গে যুক্ত ফল; পর্ব ৩৫-এ দেখেছেন, পর্ব ৩৯-এ আবার আসবে)। Grammar-এর স্তরেও প্রতিটি LL(k) grammar LR(k).

তবু LL হারিয়ে যায়নি। LL parser হাতে লেখা সহজ, error-এর জায়গা বোঝা সহজ, আর parse চলাকালীন “এখন কোন নিয়মের ভেতরে আছি” সবসময় জানা থাকে, যা অর্থ-বিশ্লেষণের কোড (semantic action) বসানো সহজ করে। LR-এর ক্ষমতা বেশি, কিন্তু তার table হাতে বানানো কঠিন, তাই প্রায় সবসময় generator লাগে।

মূল উপলব্ধি: একই lookahead-এ ক্ষমতার পার্থক্য আসে সিদ্ধান্ত কত দেরিতে নেওয়া হয় তা থেকে। LL আগে বাছে আর পরে মেলায়; LR আগে পড়ে আর পরে বাছে।

প্র ০৩Dangling-else grammar-এ M[S′, e]-এর conflict-এ “শুধু S′ → eS রাখা” কি একটি কৌশল মাত্র, নাকি এতে parser সত্যিই সঠিক থাকে? ভাষা-নকশাকারীরা সমস্যাটি কীভাবে এড়ান?

Conflict-এর একটি নিয়ম বেছে নেওয়ার মানে parser-টি আর grammar-এর সব parse tree খোঁজে না, প্রতিটি input-এ একটি নির্দিষ্ট গাছ বাছে। এখানে প্রশ্ন দুটি। প্রথম: language বদলায় কি? S′ → eS রাখলে, else এলে parser সবসময় তা খেয়ে নেয়। এমন কোনো বৈধ string আছে কি, যার একমাত্র parse-এ else-কে ভেতরের if ছেড়ে দিতে হয়? না: যেকোনো if-then-if-then-else-এ else-কে ভেতরের if-এর সঙ্গে বাঁধার একটি parse সবসময় আছে, তাই language অক্ষুণ্ণ থাকে। দ্বিতীয়: কোন গাছ বাছা হলো? ঠিক সেটি, যা C, Java আর বেশিরভাগ ভাষার নিয়ম: else যায় সবচেয়ে কাছের জোড়াহীন if-এর সঙ্গে (পর্ব ২৭)।

তাহলে এটি একটি সুশৃঙ্খল কৌশল, কিন্তু grammar আর parser-এর মধ্যে একটি গোপন চুক্তি। Grammar পড়ে কেউ জানতে পারবে না কোন গাছ আসবে; সেই তথ্য আছে parser-এর conflict-নিষ্পত্তির নিয়মে। Aho, Sethi আর Ullman-এর Compilers বইসহ কয়েকটি উৎসে বলা হয়েছে যে if-else-এর এই language-এর কোনো LL(1) grammar-ই নেই; তবু conflict-নিষ্পত্তি করা LL(1) table দিয়ে একে ঠিকঠাক parse করা যায়। তাই বাস্তবে এটিই সবচেয়ে সরল পথ। পর্ব ৩৯-এ দেখবেন, LR parser-ও এখানে একটি shift/reduce conflict পায় আর “shift” বেছে একই ফল পায়।

ভাষা-নকশাকারীরা প্রায়ই সমস্যাটির মূলই সরিয়ে দেন। Wirth-এর Modula-2 আর পরে Ada-র মতো ভাষায় if-এর শেষে একটি বাধ্যতামূলক END (বা end if) চিহ্ন আছে, তাই else কার, তা লেখার গঠনেই স্পষ্ট। Python ইন্ডেন্টেশন দিয়ে একই কাজ করে: lexer প্রতিটি ব্লকের শুরু আর শেষে বিশেষ token (INDENT, DEDENT) দেয়, ফলে parser-এর কাছে প্রতিটি if-এর দেহ বন্ধনীর মতো সীমাবদ্ধ। Go আর Rust-এ if-এর দেহে কোঁকড়া বন্ধনী বাধ্যতামূলক। প্রতিটি সমাধান grammar-কে unambiguous আর সহজে parse-যোগ্য করে, আর লেখককে একটি বিখ্যাত ধরনের বাগ থেকেও বাঁচায়।

মূল উপলব্ধি: Conflict-নিষ্পত্তি গ্রহণযোগ্য, যদি নিশ্চিত হন language বদলায়নি আর বাছা গাছটি ভাষার নির্ধারিত অর্থ। তার চেয়েও ভালো সমাধান অনেক সময় ভাষার syntax নকশায়, parser-এ নয়; পর্ব ৪২-এ এই দৃষ্টিভঙ্গি বিস্তারিত আসবে।

প্র ০৪অংশ ৬-এর parser বলেছে “expected one of ['(', 'id']”. Table থেকে আসা এই বার্তা কতটা ভালো? বাজারঘরের কর্মীদের জন্য আরও ভালো error বার্তা কীভাবে বানাবেন?

Table থেকে পাওয়া “expected” set তত্ত্বের দিক থেকে নিখুঁত: এটি ঠিক সেই token-গুলো, যাদের যেকোনো একটি এই জায়গায় বসলে input আবার বৈধ হওয়ার পথে থাকত। LL(1) parser-এর valid prefix property-র কারণে এটি সবসময় প্রথম ভুল token-এই আসে, পরে নয়। এটুকুই অনেক পুরোনো tool-এর চেয়ে ভালো, যারা শুধু “syntax error” বলত।

তবে কর্মীর কাছে “expected one of ['(', 'id']” অর্থহীন। তিনটি উন্নতি সহজে করা যায়। প্রথম: token-এর নাম মানুষের ভাষায়, যেমন “একটি শর্ত (amount, district, status) বা ( দরকার”. দ্বিতীয়: অবস্থান লাইন আর কলাম দিয়ে, আর ভুল জায়গার নিচে একটি ^ চিহ্ন, যা পর্ব ২২-এর lexer আগেই জানে। তৃতীয়: সাধারণ ভুলের জন্য বিশেষ বার্তা, যেমন “AND-এর পরে শর্ত নেই” বা “বন্ধনী খোলা হয়েছিল কিন্তু বন্ধ হয়নি”; এগুলো table-এর নির্দিষ্ট ফাঁকা ঘরের সঙ্গে আলাদা বার্তা জুড়ে বানানো যায়, যাকে কখনো error entry বলা হয়।

দ্বিতীয় বিষয় হলো error-এর পরে কী করবেন। অংশ ৭-এর panic mode এক চালনায় একাধিক ভুল দেখায়, কিন্তু cascading error-ও তৈরি করে, যেমন চতুর্থ query-তে একটি ভুলে দুটি বার্তা। প্রচলিত সমাধান: একই token-এ দ্বিতীয় বার্তা চেপে রাখা, বা একটি ভুলের পর কয়েকটি token সফলভাবে না মেলা পর্যন্ত নতুন বার্তা না দেখানো। আরও উন্নত পদ্ধতি “phrase-level recovery”: একটি token ঢুকিয়ে বা মুছে দেখা কোনটিতে parse এগোয়, আর সেটিকে পরামর্শ হিসেবে দেখানো (“এখানে কি ) বাদ পড়েছে?”)।

এখানে তত্ত্বের একটি সীমাও আছে: “সবচেয়ে কম বদলে input বৈধ করা” প্রশ্নটি CFG-এর জন্য dynamic programming দিয়ে সমাধানযোগ্য (Aho ও Peterson-এর ১৯৭২ সালের least-errors parsing-এর মতো কাজ), কিন্তু তার দাম CYK-এর মতো ঘনঘাতের সময়, তাই compiler সাধারণত দ্রুত কিন্তু আনুমানিক কৌশলেই থাকে।

মূল উপলব্ধি: FIRST/FOLLOW শুধু parse করার জন্য নয়, ভুল বোঝানোর জন্যও তথ্যের উৎস। ভালো error বার্তা = সঠিক অবস্থান + মানুষের ভাষায় expected set + সাধারণ ভুলের জন্য বিশেষ বার্তা + cascading রোধ।

প্র ০৫একটি grammar LL(1) কি না, তা table বানিয়ে মুহূর্তে বলা যায়। তাহলে “এই language-এর কি কোনো LL(1) grammar আছে?” প্রশ্নটি কেন অনেক কঠিন?

প্রথম প্রশ্নটি একটি নির্দিষ্ট বস্তু নিয়ে: একটি grammar দেওয়া আছে, FIRST/FOLLOW-এর fixpoint সসীম সময়ে থামে, table-এর ঘর সসীম, তাই conflict গোনা একটি সরল algorithm. দ্বিতীয় প্রশ্নটি অসীম সংখ্যক বস্তু নিয়ে: একই language-এর অসীম সংখ্যক grammar আছে, আর প্রশ্ন হলো তাদের কোনো একটি LL(1) কি না। Left recursion সরানো আর left factoring-এর মতো রূপান্তর চেষ্টা করা যায়, কিন্তু সেগুলো ব্যর্থ হলে বলা যায় না যে অন্য কোনো চতুর grammar নেই।

এ ধরনের প্রশ্ন CFG-এর জগতে প্রায়ই undecidable হয়, আর এর পেছনে পর্ব ৫৪-এর Post correspondence problem-এর মতো হাতিয়ার কাজ করে। এমনকি grammar-স্তরেই সীমা আছে: নির্দিষ্ট k দেওয়া থাকলে “এই grammar কি LL(k)?” decidable, কিন্তু “এই grammar কি কোনো k-র জন্য LL(k)?” undecidable বলে পরিচিত। Language-স্তরের প্রশ্ন, অর্থাৎ অন্য কোনো grammar-এর অস্তিত্ব, স্বভাবতই এর চেয়ে কঠিন ধরনের; “language-টি কি regular?” প্রশ্নের মতো এরকম অনেক প্রশ্নই CFG-এর জন্য undecidable (পর্ব ৩৭), আর LL-প্রশ্নটির সঠিক অবস্থার জন্য Aho ও Ullman-এর “The Theory of Parsing, Translation, and Compiling” দেখুন। অন্যদিকে তুলনামূলক ছোট শ্রেণির কিছু প্রশ্ন যন্ত্রে উত্তর পায়, যেমন দুটি LL(k) grammar-এর equivalence.

বাস্তব প্রকৌশলে এর অর্থ: grammar-নকশাকারী একটি tool-এর conflict রিপোর্ট দেখে জানেন তাঁর grammar কোথায় সমস্যায়, কিন্তু কোনো tool বলে দিতে পারে না “চেষ্টা থামান, এই language-টিই LL নয়”. এজন্যই অভিজ্ঞ নকশাকারীরা শুরু থেকেই syntax এমনভাবে বানান যাতে প্রতিটি গঠন একটি স্বতন্ত্র keyword বা চিহ্ন দিয়ে শুরু হয়: Pascal-এর প্রতিটি statement একটি keyword (if, while, begin) দিয়ে শুরু, বা বাজারঘরের query-র প্রতিটি শর্ত একটি নিজস্ব শব্দ দিয়ে (amount, district, status). তখন LL(1) হওয়া প্রায় নিশ্চিত, আর প্রমাণ শুধু table বানানো।

একটি তুলনা: পর্ব ২০-এ দেখেছেন, দুটি DFA একই language চেনে কি না তা decidable, আর minimal DFA অনন্য। CFG-এর জগতে এমন “প্রমিত রূপ” নেই, তাই grammar-এর ধর্ম আর language-এর ধর্মের মধ্যে একটি বড় ফাঁক থাকে।

মূল উপলব্ধি: একটি নির্দিষ্ট grammar পরীক্ষা করা আর সব সম্ভাব্য grammar-এর ওপর প্রশ্ন করা আলাদা ধরনের সমস্যা; দ্বিতীয়টি প্রায়ই undecidable. তাই ভালো syntax নকশা আগে থেকেই LL-বান্ধব হয়, পরে মেরামত করে নয়।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। first_follow.py আর ll1_parse.py ব্লকে নিজের grammar বসিয়ে উত্তর যাচাই করতে পারেন।

  1. Grammar নকশা: বাজারঘরের একটি ছোট API সংখ্যার তালিকা নেয়: [ ], [ n ], [ n , n , n ] ইত্যাদি (n একটি সংখ্যার token). শেষ কমা ([ n , ]) অবৈধ। এই language-এর জন্য একটি LL(1) grammar নকশা করুন, FIRST/FOLLOW আর table দিন, আর [ n , ]-এ parser কোথায় থামবে বলুন।

    নকশা: A → [ B, B → ] ∣ n C, C → , n C ∣ ]. ভাবনা: “[”-এর পরে হয় সঙ্গে সঙ্গে “]” (ফাঁকা তালিকা), নয়তো একটি n; প্রতিটি n-এর পরে হয় “, n” আরও, নয়তো “]”. কোনো ε-নিয়ম নেই।

    FIRST/FOLLOW: FIRST(A) = {[}, FIRST(B) = {], n}, FIRST(C) = {,, ]}; তিনটির FOLLOW = {$}. Table-এ ৫টি ঘর: M[A, [] = A → [B, M[B, ]] = B → ], M[B, n] = B → nC, M[C, ,] = C → ,nC, M[C, ]] = C → ]. কোনো conflict নেই, তাই LL(1).

    [ n , ]: A → [B, match [, B → nC, match n, C → ,nC, match ,; এখন stack-এর ওপরে n, কিন্তু lookahead ]: error at token 4 ']': expected one of ['n']. Scratch-এ ll1 আর parse চালিয়ে ঠিক এই set, এই table আর এই বার্তা পাওয়া গেছে; [ ], [ n ] আর [ n , n , n ] গৃহীত।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: S → aSb ∣ ε একটি LL(1) grammar নয়। প্রমাণ: S nullable. Nullable variable-এর ε-নিয়ম table-এ FOLLOW(S)-এর সব ঘরে বসে, তাই অন্য নিয়মের সঙ্গে সংঘাত হবেই। ∎” ভুলটি কোথায়? সঠিক উত্তর কী?

    ভুল: “সংঘাত হবেই” কথাটি প্রমাণ ছাড়া ধরা হয়েছে। ε-নিয়ম FOLLOW(S)-এর ঘরে বসে ঠিকই, কিন্তু সংঘাত হয় কেবল তখন, যখন অন্য নিয়মের FIRST আর FOLLOW(S)-এর ছেদ অশূন্য (উপপাদ্য ৫.২-এর শর্ত ৩)। Nullable হওয়া নিজে কোনো দোষ নয়; ETF grammar-এর E′ আর T′ nullable, তবু grammar LL(1).

    সঠিক হিসাব: FIRST(aSb) = {a}. FOLLOW(S) = {b, $}: $ কারণ S start, b কারণ S → aSb-তে S-এর পরে b. ছেদ {a} ∩ {b, $} = ∅. Table: M[S, a] = S → aSb, M[S, b] = S → ε, M[S, $] = S → ε; কোনো ঘরে দুটি নিয়ম নেই। তাই grammar LL(1), আর দাবিটি মিথ্যা। Scratch-এ ll1 চালিয়ে এই তিনটি ঘর আর শূন্য conflict পাওয়া গেছে।

  3. Output অনুমান: ll1_parse.py ব্লকে parse(ETF, "E", ["(", "id", ")", "id"]) চালালে শেষ দুই লাইনে কী ছাপা হবে? কেন ঠিক ওই token-এ থামবে?

    উত্তর: ( id ) সম্পূর্ণ মেলার পর stack-এ T′ E′ $ আর lookahead id. শেষ দুই লাইন:

    T' E' $       id $
    error at token 4 'id': expected one of ['$', ')', '*', '+']

    কারণ: “(id)” একটি সম্পূর্ণ factor; তার পরে T′-এর জন্য বৈধ lookahead হলো ∗ (FIRST(∗FT′)) বা FOLLOW(T′) = {+, ), $}. id এগুলোর কোনোটি নয়, তাই M[T′, id] ফাঁকা। চার token-এর input-এর প্রথম তিনটি মিলেছে, error চতুর্থটিতে: valid prefix property অনুযায়ী ঠিক প্রথম অসম্ভব token-এ। Scratch-এ চালিয়ে এই আউটপুট মেলানো হয়েছে (মাঝের ১১টি সারিসহ)।

  4. হিসাব: Grammar: S → AaAb ∣ BbBa, A → ε, B → ε. FIRST আর FOLLOW বের করুন, table ভরুন, আর grammar-টি LL(1) কি না বলুন। Language-টি কী?

    FIRST: A আর B শুধু ε, তাই FIRST(A) = FIRST(B) = {ε}. FIRST(AaAb) = {a} (A ফাঁকা হয়ে a আসে), FIRST(BbBa) = {b}; তাই FIRST(S) = {a, b}.

    FOLLOW: FOLLOW(S) = {$}. AaAb-তে প্রথম A-এর পরে a, দ্বিতীয় A-এর পরে b: FOLLOW(A) = {a, b}. একইভাবে FOLLOW(B) = {a, b}.

    Table: M[S, a] = S → AaAb, M[S, b] = S → BbBa, M[A, a] = M[A, b] = A → ε, M[B, a] = M[B, b] = B → ε. মোট ৬টি ঘর, কোনোটিতে দুটি নিয়ম নেই: LL(1). Language {ab, ba}. লক্ষ করুন, A আর B দুটিরই FOLLOW-এ a আর b আছে, তবু সংঘাত নেই, কারণ প্রতিটির একটিই নিয়ম। Scratch-এ ll1 চালিয়ে ঠিক এই set আর ছয়টি ঘর পাওয়া গেছে।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি expression grammar থেকে table-চালিত LL(1) parser বানানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Precedence-এর স্তর বসিয়ে ambiguity দূর করা
  2. Left recursion দূর করা
  3. একই শুরুর নিয়মে left factoring
  4. সব variable-এর FIRST set হিসাব
  5. FIRST ব্যবহার করে FOLLOW set হিসাব
  6. Table ভরা আর কোনো ঘরে দুটি নিয়ম আছে কি না দেখা

Grammar S → aSb ∣ ε (S start symbol)-এ FOLLOW(S) কী?

  • {$}
  • {b, $}
  • {a, b, $}
  • {b, ε}

LL(1) parsing table-এ নিয়ম A → α কোন ঘরগুলোতে বসে?

  • শুধু FOLLOW(A)-এর প্রতিটি terminal-এর ঘরে
  • FIRST(A)-এর প্রতিটি terminal-এর ঘরে
  • FIRST(α)-এর প্রতিটি terminal-এর ঘরে, আর α ⇒∗ ε হলে FOLLOW(A)-এর প্রতিটি চিহ্নের ঘরেও
  • শুধু α-র প্রথম চিহ্নটি terminal হলে, সেই terminal-এর ঘরে

A → abC ∣ abD ∣ e-এ (A, C, D variable; a, b, e terminal) left factoring-এর সঠিক ফল কোনটি?

  • A → abA′ ∣ e, A′ → C ∣ D
  • A → aA′ ∣ e, A′ → bC ∣ bD
  • A → abA′, A′ → C ∣ D ∣ e
  • A → eA′, A′ → abC ∣ abD ∣ ε

ETF grammar (E → TE′, E′ → +TE′ ∣ ε, T → FT′, T′ → ∗FT′ ∣ ε, F → (E) ∣ id)-এর table-চালিত parser-এ stack-এর ওপরে T′ আর lookahead +. Parser কী করবে?

  • Error দেবে, কারণ T′ আর + মেলে না
  • T′ → ∗FT′ নিয়ে ∗ push করবে
  • E′ → +TE′ নেবে
  • T′ → ε নিয়ে T′ pop করবে

Useless symbol ছাড়া একটি context-free grammar সম্পর্কে কোন কথাটি সবসময় সত্য?

  • Unambiguous আর left recursion-মুক্ত হলেই grammar LL(1)
  • LL(1) grammar হলে সেটি unambiguous
  • Left factoring করলে যেকোনো grammar LL(1) হয়
  • কোনো nullable variable থাকলে grammar LL(1) হতে পারে না

Grammar S → Aa ∣ b, A → a ∣ ε-এর LL(1) table-এ কোন ঘরে conflict হয়?

  • M[S, a]
  • M[A, $]
  • M[A, a]
  • M[A, b]

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Top-down parser leftmost derivation বানায়: ওপরে variable থাকলে predict, terminal থাকলে match. LL(1) মানে এক token দেখেই প্রতিটি predict নিশ্চিত।
  2. দুই বাধা: left recursion (A → βA′, A′ → αA′ ∣ ε) আর একই শুরু (left factoring: A → αA′, A′ → β1 ∣ β2). দুটিই language রাখে, কিন্তু LL(1) হওয়ার নিশ্চয়তা দেয় না।
  3. FIRST(α) = α থেকে আসা প্রথম terminal (+ ε যদি α ⇒∗ ε); FOLLOW(A) = A-এর পরে বসতে পারা terminal (+ $). দুটিই fixpoint-এ হিসাব হয়।
  4. A → α বসে FIRST(α)-এর ঘরে, আর α nullable হলে FOLLOW(A)-এর ঘরে। কোনো ঘরে দুটি নিয়ম না থাকলে LL(1); LL(1) grammar কখনো ambiguous বা left-recursive নয়।
  5. Table-চালিত parser একটি deterministic PDA: |w|-এর অনুপাতে সময়, প্রথম অসম্ভব token-এ error, আর panic mode-এ FOLLOW-কে synchronizing set ধরে এগোনো।

পরের পর্বে: Bottom-up parsing: shift আর reduce, handle, LR(0) item আর item set-এর DFA, SLR আর LALR table, আর shift/reduce বা reduce/reduce conflict কোথা থেকে আসে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান