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

সব CFG-এর parsing — Earley আর GLR

Parsing Every Context-Free Grammar — Earley's Algorithm (Predict, Scan, Complete), Correctness and Cost, ε-Rules, Shared Packed Parse Forests and GLR with a Graph-Structured Stack

Taught in Bangla, this lesson covers general parsers that accept any context-free grammar. It builds Earley's algorithm from items, chart sets and the predict, scan and complete steps, proves correctness and O(n³) worst-case cost, fixes the ε-rule trap with the Aycock–Horspool idea, and stores exponentially many parse trees in a shared packed parse forest. It explains GLR with a graph-structured stack, with in-page Python (Pyodide) and a real lark run storing over 10⁴⁵ trees.

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

  • Earley item আর chart-এর সংজ্ঞা, আর predict, scan, complete দিয়ে হাতে chart ভরা
  • Left-recursive আর ambiguous grammar-এ Earley কেন আটকায় না, আর এর সঠিকতার প্রমাণ
  • O(n3), O(n2) আর linear সীমার কারণ, আর ε-নিয়মের ফাঁদ ও তার সমাধান
  • Chart থেকে parse tree গোনা, আর shared packed parse forest কেন polynomial থাকে
  • GLR-এর graph-structured stack, আর কখন CYK, Earley, GLR, LL বা LR বেছে নেবেন

১ · কেন সব CFG-এর জন্য একটি parser দরকার

আগের তিন পর্বে আপনি দেখেছেন, বাস্তবের বেশিরভাগ parser একটি চুক্তির ওপর দাঁড়িয়ে। পর্ব ৩৮-এর LL(1) parser চায় grammar-এ left recursion না থাকুক আর প্রতিটি বিকল্প একটি token দেখেই আলাদা করা যাক। পর্ব ৩৯-এর LR parser চায় টেবিলে কোনো shift/reduce conflict না থাকুক। চুক্তি মানলে পুরস্কার বড়: linear সময়, পরিষ্কার ভুলের বার্তা, আর grammar যে unambiguous, তার একটি নিশ্চয়তা। কিন্তু চুক্তি না মানলে parser generator শুধু conflict-এর তালিকা দেয়, parser দেয় না।

কিছু ক্ষেত্রে চুক্তি মানা কঠিন বা অসম্ভব। মানুষের ভাষা নিজেই ambiguous: “বড় বাজারের দোকান” মানে বড় একটি বাজারের দোকান, নাকি বাজারের বড় দোকান? দুটি অর্থই বৈধ, আর parser-কে দুটিই দেখাতে হয়। আবার, নতুন একটি ছোট ভাষা (DSL) নকশার শুরুতে grammar বারবার বদলায়; প্রতিবার conflict মেটাতে গেলে নকশার কাজ থেমে যায়। বাজারঘরের কর্মীদের জন্য একটি খোলামেলা খোঁজের ঘর ধরুন, যেখানে কেউ লিখলেন amount > 500 AND district = "Dhaka" OR status = "new". বন্ধনী ছাড়া এর দুটি অর্থ সম্ভব, আর prototype পর্যায়ে আমরা চাই parser দুটি অর্থই বের করুক, তারপর আমরা ঠিক করব কোনটি রাখব।

কমলাপুর স্টেশনের টিকিট কাউন্টারে একজন কর্মী ভাবুন, যাঁর কাছে একসঙ্গে অনেক যাত্রী আসছেন। LL বা LR parser সেই কর্মী, যিনি প্রথম শব্দ শুনেই ঠিক করেন যাত্রী কোন লাইনের ট্রেনে যাবেন; ভুল আন্দাজের সুযোগ নেই, তাই কাউন্টারের নিয়ম আগে থেকে এমনভাবে সাজানো যে আন্দাজই লাগে না। Earley parser সেই কর্মী, যিনি একটি খাতায় প্রতিটি যাত্রীর সব সম্ভাব্য গন্তব্য লিখে রাখেন, আর প্রতিটি নতুন তথ্য শুনে খাতা থেকে অসম্ভবগুলো বাদ দেন, সম্ভবগুলো এগিয়ে নেন। খাতাটি বড় হয়, কিন্তু কখনো অসীম হয় না, কারণ একই কথা দুবার লেখা হয় না।

এমন একটি সাধারণ algorithm আপনি আগেই দেখেছেন: পর্ব ৩১-এর CYK algorithm, যা যেকোনো CFG-এর membership problem O(n3) সময়ে মেটায়। কিন্তু CYK-এর দুটি অসুবিধা। এক, grammar-কে আগে Chomsky normal form-এ নিতে হয়, ফলে parse tree মূল grammar-এর নয়। দুই, CYK সবসময় পুরো টেবিল ভরে, grammar সহজ হলেও; পর্ব ৩১-এর সত্যিকারের run-এ ৪০১ token-এর একটি সহজ expression-এ CYK নিয়েছিল ১৪০০ ms-এর বেশি, যেখানে lark-এর Earley ২৩ ms. এই পর্বের দুই algorithm, Earley আর GLR, মূল grammar-এর ওপরেই চলে, আর grammar যত “সহজ”, তত দ্রুত।

২ · Earley-র ভাবনা — item, chart আর তিন ক্রিয়া

Jay Earley ১৯৬৮ সালে Carnegie Mellon-এ তাঁর PhD thesis-এ আর ১৯৭০ সালে Communications of the ACM-এ “An efficient context-free parsing algorithm” প্রবন্ধে এই algorithm দেন। ভাবনাটি পর্ব ৩৯-এর LR item-এর খুব কাছের: একটি নিয়মের ডান দিকে একটি বিন্দু, যা বলে কতটুকু দেখা হয়েছে। Earley তার সঙ্গে একটি সংখ্যা জোড়েন: নিয়মটি input-এর কোন অবস্থান থেকে শুরু হয়েছিল।

সংজ্ঞা ২.১ (Earley item আর chart)

CFG G = (V, Σ, R, S)-এর সঙ্গে একটি নতুন start S′ আর নিয়ম S′ → S যোগ করুন। Input w = w1w2⋯wn. অক্ষরগুলোর মাঝের সীমানাগুলোকে 0, 1, …, n নাম দিন; সীমানা j থেকে k-এর টুকরো হলো wj+1⋯wk.

একটি Earley item হলো [A → α·β, j], যেখানে A → αβ ∈ R আর j একটি সীমানা (origin). Chart হলো n + 1টি set S0, S1, …, Sn; item [A → α·β, j] ∈ Sk-এর অর্থ: A-র এই নিয়মটি সীমানা j-তে শুরু হয়েছে, আর α ইতিমধ্যে টুকরো wj+1⋯wk তৈরি করেছে।

যেমন, [E → E + ·E, 0] ∈ S2 মানে: অবস্থান ০ থেকে শুরু করে “E +” অংশটি প্রথম দুটি token পড়ে ফেলেছে, আর এখন একটি E আসার অপেক্ষা। Chart শুরু হয় S0 = {[S′ → ·S, 0]} দিয়ে। তারপর k = 0, 1, …, n ক্রমে প্রতিটি set-এ, নতুন কিছু না আসা পর্যন্ত, প্রতিটি item-এ তিনটি নিয়মের যেটি খাটে সেটি চালানো হয়:

Earley-র তিন ক্রিয়া
  1. Predict (অনুমান): [A → α·Bβ, j] ∈ Sk আর B একটি variable হলে, প্রতিটি নিয়ম B → γ-র জন্য [B → ·γ, k] যোগ করুন Sk-এ। অর্থ: “এখান থেকে একটি B শুরু হতে পারে।”
  2. Scan (পড়া): [A → α·aβ, j] ∈ Sk আর a = wk+1 হলে [A → αa·β, j] যোগ করুন Sk+1-এ। অর্থ: “প্রত্যাশিত token সত্যিই এসেছে।”
  3. Complete (সম্পূর্ণ): [B → γ·, i] ∈ Sk হলে, Si-এর প্রতিটি [A → α·Bβ, j]-এর জন্য [A → αB·β, j] যোগ করুন Sk-এ। অর্থ: “i থেকে k পর্যন্ত একটি B পাওয়া গেছে, তাই যারা সীমানা i-তে B-র অপেক্ষায় ছিল, তারা এক ধাপ এগোয়।”

কোনো item একটি set-এ একবারের বেশি যোগ হয় না। গ্রহণের শর্ত: [S′ → S·, 0] ∈ Sn.

এই পর্বের প্রথম grammar ইচ্ছা করে কঠিন: E → E + E ∣ id. এটি ambiguous (id+id+id-এর দুটি গাছ) আর left-recursive (E-র নিয়ম E দিয়েই শুরু), অর্থাৎ পর্ব ৩৮ আর ৩৯-এর দুই parser-ই এটি সরাসরি নিতে পারে না। নিচের stepper “id+id”-এর পুরো chart ধাপে ধাপে ভরে। Item-গুলো জায়গা বাঁচাতে ফাঁকা ছাড়া লেখা: [E→E+·E,0] মানে [E → E + ·E, 0].

Grammar: S′ → E, E → E+E ∣ id
এখন যে set
ক্রিয়া
নতুন item
  1. শুরু। S0-এ শুধু [S′ → ·E, 0]: অবস্থান ০ থেকে পুরো input একটি E হওয়ার অপেক্ষা। এখনো কোনো token পড়া হয়নি।
  2. Predict. বিন্দুর পরে variable E, তাই E-র দুই নিয়মের item যোগ: [E → ·E+E, 0] আর [E → ·id, 0]. প্রথমটির বিন্দুর পরেও E, তাই আবার predict চেষ্টা হয়, কিন্তু দুটি item আগেই আছে; কিছু যোগ হয় না। S0 বন্ধ, ৩টি item.
  3. Scan id. প্রথম token id. S0-এর যে item-এর বিন্দুর পরে id, শুধু [E → ·id, 0], বিন্দু পেরিয়ে S1-এ যায়: [E → id·, 0].
  4. Complete. [E → id·, 0] সম্পূর্ণ: ০ থেকে ১ পর্যন্ত একটি E. S0-এ যারা E-র অপেক্ষায় ছিল, তারা এগোয়: [S′ → E·, 0] আর [E → E·+E, 0]. প্রথমটি বলে “শুধু id” input হলে গৃহীত হতো।
  5. Scan +, তারপর predict. দ্বিতীয় token +. শুধু [E → E·+E, 0] এটি চায়, তাই S2-এ [E → E+·E, 0]. বিন্দুর পরে E, তাই origin 2 নিয়ে আবার E-র দুই নিয়ম predict হয়।
  6. Scan id, complete. তৃতীয় token id: S3-এ [E → id·, 2]. এটি সম্পূর্ণ, origin 2, তাই S2-এর E-অপেক্ষারত দুটি item এগোয়: [E → E+E·, 0] আর [E → E·+E, 2].
  7. Complete-এর শিকল। নতুন [E → E+E·, 0] নিজেও সম্পূর্ণ, origin 0, তাই এবার S0-এর E-অপেক্ষারত item এগোয়: [S′ → E·, 0] আর [E → E·+E, 0]. [S′ → E·, 0] ∈ S3, তাই “id+id” গৃহীত। মোট ১৪টি item.

হাতের হিসাব যন্ত্রে মিলিয়ে নিন। নিচের ব্লকে Earley recognizer প্রায় ২০ লাইনের। প্রতিটি set একটি dict, যা item-এর সঙ্গে লিখে রাখে কোন ক্রিয়ায় সেটি এল; Python-এর dict যোগ করার ক্রম মনে রাখে, তাই ছাপার ক্রমই প্রক্রিয়ার ক্রম। মূল কৌশল while i < len(S[k]): set-টি পড়তে পড়তেই বড় হয়, আর loop নতুন item-গুলোও ধরে।

# Earley recognizer that prints every chart set S0..Sn
G = {"E": [("E", "+", "E"), ("id",)]}       # ambiguous AND left-recursive

def show(item):
    A, rhs, d, j = item
    return f"[{A} → {' '.join(rhs[:d] + ('·',) + rhs[d:])}, {j}]"

def earley(G, start, w):
    n = len(w)
    S = [{} for _ in range(n + 1)]          # S[k]: item -> how it was added
    def add(k, item, how):
        if item not in S[k]: S[k][item] = how   # dict keeps insertion order
    add(0, ("S'", (start,), 0, 0), "start")
    for k in range(n + 1):
        i = 0
        while i < len(S[k]):                # S[k] grows while we read it
            A, rhs, d, j = list(S[k])[i]; i += 1
            if d < len(rhs) and rhs[d] in G:                # PREDICT
                for r in G[rhs[d]]: add(k, (rhs[d], r, 0, k), "predict")
            elif d < len(rhs):                              # SCAN
                if k < n and w[k] == rhs[d]:
                    add(k + 1, (A, rhs, d + 1, j), "scan")
            else:                                           # COMPLETE
                for B, r2, d2, j2 in list(S[j]):
                    if d2 < len(r2) and r2[d2] == A:
                        add(k, (B, r2, d2 + 1, j2), "complete")
        print(f"S{k}" + (f"  (after reading '{w[k-1]}')" if k else ""))
        for item, how in S[k].items():
            print(f"   {how:9}{show(item)}")
    return ("S'", (start,), 1, 0) in S[n]

w = ["id", "+", "id"]
print("accepted:", earley(G, "E", w))

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

S0
   start    [S' → · E, 0]
   predict  [E → · E + E, 0]
   predict  [E → · id, 0]
S1  (after reading 'id')
   scan     [E → id ·, 0]
   complete [S' → E ·, 0]
   complete [E → E · + E, 0]
S2  (after reading '+')
   scan     [E → E + · E, 0]
   predict  [E → · E + E, 2]
   predict  [E → · id, 2]
S3  (after reading 'id')
   scan     [E → id ·, 2]
   complete [E → E + E ·, 0]
   complete [E → E · + E, 2]
   complete [S' → E ·, 0]
   complete [E → E · + E, 0]
accepted: True

ছাপা chart stepper-এর সঙ্গে item ধরে মেলে, ক্রমসহ। কোডে item একটি tuple (A, rhs, d, j): d হলো বিন্দুর অবস্থান, j origin. তিনটি শাখা ঠিক তিন ক্রিয়া: বিন্দুর পরে variable থাকলে predict, terminal থাকলে scan, কিছু না থাকলে complete. লক্ষ করুন, scan শুধু S[k+1]-এ লেখে, আর complete শুধু পুরোনো set S[j] পড়ে; তাই set-গুলো বাঁ থেকে ডানে একবারেই চূড়ান্ত হয়। w বদলে ["id", "+"] দিন: S2 খালি থাকবে না, কিন্তু [S′ → E·, 0] থাকবে না, তাই উত্তর False. আর ["+", "id"] দিলে S1-ই খালি: প্রথম token-এই ভুল ধরা পড়ে।

শেষ পর্যবেক্ষণটির একটি নাম আছে। Earley parser একটি valid prefix property মানে (grammar-এ useless symbol না থাকলে): কোনো set Sk খালি হলে w1⋯wk কোনো বৈধ string-এর prefix নয়, আর যতক্ষণ set খালি নয়, ততক্ষণ পড়া অংশটি কোনো বৈধ string-এর শুরু। তাই ভুলের বার্তা ঠিক প্রথম ভুল token-কে দেখাতে পারে, পর্ব ২৬-এ যেমন বলা হয়েছিল। CYK-এর এমন কিছু নেই; সে পুরো string হাতে না পেলে কিছু বলে না।

৩ · Left recursion আর ambiguity — Earley কেন আটকায় না

পর্ব ৩০-এ দেখেছেন, E → E + T-এর মতো নিয়মে একটি সরল recursive descent parser কোনো token না পড়েই নিজেকে বারবার ডাকে। কারণ function E()-র প্রথম কাজ আবার E() ডাকা, আর দ্বিতীয় ডাকটি প্রথমটির থেকে কোনোভাবে আলাদা নয়: একই function, input-এর একই অবস্থান। Earley-র predict-ও একই কাজ করে, “E থেকে E শুরু হতে পারে”, কিন্তু তার একটি স্মৃতি আছে। নিচের stepper দুটি parser পাশাপাশি চালায়, input-এর অবস্থান ০-তে।

Grammar E → E+E ∣ id, অবস্থান ০, কোনো token পড়া হয়নি
Earley-র S0
Recursive descent
পড়া token
  1. দুজনেই শুরু করে। Earley S0-এ [S′ → ·E, 0] রাখে। Recursive descent E() ডাকে, input-এর অবস্থান ০।
  2. প্রথম predict, প্রথম ডাক। Earley E-র দুই নিয়মের item যোগ করে, origin 0. Recursive descent প্রথম বিকল্প E + E চেষ্টা করে, যার প্রথম চিহ্ন E, তাই আবার E() ডাকে; অবস্থান এখনো ০।
  3. পার্থক্যের মুহূর্ত। Earley এবার [E → ·E+E, 0] প্রক্রিয়া করে: বিন্দুর পরে E, তাই E-র নিয়মগুলো origin 0 নিয়ে predict করতে চায়। কিন্তু [E → ·E+E, 0] আর [E → ·id, 0] আগেই S0-এ আছে, তাই কিছুই যোগ হয় না। Recursive descent-এর কাছে এই তথ্য নেই; সে তৃতীয়বার E() ডাকে।
  4. Earley থামে, অন্যজন চলতেই থাকে। [E → ·id, 0]-এর বিন্দুর পরে terminal, তাই এটি scan-এর অপেক্ষায়। S0-এ প্রক্রিয়া করার মতো আর কিছু নেই: ৩টি item, set বন্ধ। Recursive descent-এর call stack ৪, ৫, ৬ স্তরে গভীর হয়, একটিও token না পড়ে।
  5. ফল। Earley পরের token পড়তে S1-এ যায়। Recursive descent শেষে stack-এর সীমায় ধাক্কা খায়: Python-এ RecursionError, অন্য ভাষায় stack overflow.
  6. কেন এমন হয়। একটি item মানে (নিয়ম, বিন্দুর অবস্থান, origin); Sk-এ origin 0 থেকে k, তাই আলাদা item বড়জোর (বিন্দুসহ নিয়মের সংখ্যা) × (k + 1)টি। এখানে E-র বিন্দু-শুরুর item বড়জোর 2 × 1টি। “আগে আছে কি?” পরীক্ষাটিই সেই স্মৃতি, যা recursive descent-এর নেই।

Ambiguity-ও Earley-কে আটকায় না, একই কারণে। “id+id+id”-এর দুটি গাছ আছে: (id+id)+id আর id+(id+id). Chart-এ এই দুটি পথ এক জায়গায় এসে মেলে: [E → E+E·, 0] item-টি S5-এ দুটি আলাদা উপায়ে তৈরি হয়, কিন্তু set-এ একবারই ঢোকে। Recognizer-এর কাছে এটি একটি তথ্য, “০ থেকে ৫ পর্যন্ত একটি E আছে”; কতভাবে আছে, সেটি অংশ ৬-এর parse forest-এর কাজ। ঠিক এই একীকরণের কারণেই exponential সংখ্যক গাছ থাকলেও chart polynomial আকারের থাকে।

সাধারণ ভুল: “Earley top-down, তাই left recursion-এ আটকাবে।” Earley-র predict top-down, কিন্তু parser একটি গাছ ধরে নিচে নামে না; সব সম্ভাবনা একটি set-এ জমা রাখে, আর একই সম্ভাবনা দুবার রাখে না। উল্টো দিকে, right recursion (E → id + E) Earley-তে কোনো ভুল ঘটায় না, কিন্তু মূল algorithm-এ item-এর সংখ্যা n2-এর মাপে বাড়াতে পারে; Joop Leo ১৯৯১ সালে এর একটি সমাধান দেন বলে পরিচিত, আর lark-এর Earley-র source code-এ এই “Leo” পরিবর্তনের অংশ দেখা যায়।

৪ · সঠিকতা আর খরচ — প্রমাণ

Chart ঠিক কী ধরে রাখে, তার একটি সুনির্দিষ্ট বিবরণ আছে। এটিই Earley-র মূল উপপাদ্য, আর এর দুই দিক মিলে বলে chart ঠিক “যা হওয়া সম্ভব” তা-ই রাখে, কম বা বেশি নয়।

উপপাদ্য ৪.১ (Earley chart-এর অর্থ)

G-তে কোনো ε-নিয়ম নেই ধরুন (ε-এর কথা অংশ ৫-এ)। প্রতিটি 0 ≤ j ≤ k ≤ n আর প্রতিটি নিয়ম A → αβ-র জন্য, [A → α·β, j] ∈ Sk হবে ঠিক তখন, যখন দুটি শর্তই সত্য:

(ক) α ⇒∗ wj+1⋯wk, (খ) কোনো γ-র জন্য S′ ⇒∗ w1⋯wj A γ.

বিশেষ ক্ষেত্র: [S′ → S·, 0] ∈ Sn ⇔ S ⇒∗ w ⇔ w ∈ L(G).

শর্ত (ক) বলে “বিন্দুর বাঁ দিকের অংশ সত্যিই এই টুকরো তৈরি করে”, আর শর্ত (খ) বলে “A-কে ঠিক সীমানা j-তে শুরু করা অর্থবহ”, অর্থাৎ শুরু থেকে j পর্যন্ত পড়া অংশের পরে একটি A আসতে পারে। (খ)-ই predict-এর ছাঁকনি: CYK প্রতিটি টুকরোর জন্য সব variable পরীক্ষা করে, Earley শুধু সেগুলো, যা বাঁ দিকের প্রসঙ্গে সম্ভব।

প্রমাণ, (⇒) দিক (item যোগ হওয়ার ক্রমের ওপর induction: প্রতিটি নতুন item-এর জন্য দেখাব, আগের item-গুলো শর্ত মানলে নতুনটিও মানে):

  1. শুরু: [S′ → ·S, 0] ∈ S0. α = ε, তাই (ক) ε ⇒∗ ε; আর (খ) S′ ⇒∗ S′, j = 0. — সংজ্ঞা
  2. Predict: [A → α·Bβ, j] ∈ Sk থেকে [B → ·γ, k]. নতুন item-এর α ফাঁকা, তাই (ক) তুচ্ছ। (খ): পুরোনো item-এর (খ) আর (ক) মিলিয়ে S′ ⇒∗ w1⋯wjAδ ⇒ w1⋯wjαBβδ ⇒∗ w1⋯wkBβδ. — IH + নিয়ম A → αBβ
  3. Scan: [A → α·aβ, j] ∈ Sk, a = wk+1 থেকে [A → αa·β, j] ∈ Sk+1. (ক): α ⇒∗ wj+1⋯wk, তাই αa ⇒∗ wj+1⋯wk+1. (খ) বদলায় না, কারণ A আর j একই। — IH
  4. Complete: [B → γ·, i] ∈ Sk আর [A → α·Bβ, j] ∈ Si থেকে [A → αB·β, j] ∈ Sk. IH-এ α ⇒∗ wj+1⋯wi আর γ ⇒∗ wi+1⋯wk, তাই αB ⇒ αγ ⇒∗ wj+1⋯wk. (খ) পুরোনো item থেকেই আসে। — IH + নিয়ম B → γ
  5. উপসংহার: algorithm শুধু এই চার উপায়ে item যোগ করে, তাই chart-এর প্রতিটি item দুই শর্ত মানে। বিশেষ করে [S′ → S·, 0] ∈ Sn হলে S ⇒∗ w. ∎

প্রমাণের রূপরেখা, (⇐) দিক: ধরুন (ক) আর (খ) সত্য। (খ)-এর derivation আর (ক)-এর derivation মিলিয়ে একটি parse tree পাওয়া যায়, যেখানে A-র node-টি সীমানা j-তে শুরু। Induction চলে একটি জোড়ের ওপর: প্রথমে k (সেট-এর নম্বর), তারপর একই k-এর ভেতরে (খ)-এর derivation-এর দৈর্ঘ্য আর α-র derivation-এর আকার। α = ε হলে item-টি predict থেকে আসে (A-র মা-node-এর item, যা আগেই আছে বলে induction বলে); α-র শেষ চিহ্ন terminal হলে scan থেকে; variable হলে complete থেকে, যেখানে সেই variable-এর ছোট গাছের item আগে তৈরি। প্রতিটি ক্ষেত্রে দরকারি পুরোনো item chart-এ থাকে, আর algorithm প্রতিটি set-এ নতুন কিছু না আসা পর্যন্ত চলে বলে নতুনটিও যোগ হয়। পূর্ণ প্রমাণ Aho ও Ullman-এর The Theory of Parsing, Translation, and Compiling (খণ্ড ১, ১৯৭২) আর Grune ও Jacobs-এর Parsing Techniques বইয়ে পাবেন। ∎

উপপাদ্য ৪.২ (Earley-র খরচ)

Grammar স্থির ধরুন, আর |D| = বিন্দুসহ নিয়মের সংখ্যা। তাহলে:

  1. Sk-এ বড়জোর |D| · (k + 1)টি item, তাই পুরো chart-এ O(n2)টি item, আর জায়গা O(n2).
  2. সবচেয়ে খারাপ সময় O(n3), যেকোনো CFG-এ।
  3. Unambiguous grammar-এ সময় O(n2).
  4. অনেক LR(k) grammar-এ সময় O(n) (Earley ১৯৭০-এর বিশ্লেষণ); Leo-র ১৯৯১ সালের পরিবর্তনে সব LR(k) grammar-এ linear বলে পরিচিত।

প্রমাণের রূপরেখা: (১) একটি item মানে একটি বিন্দুসহ নিয়ম (|D|টি বিকল্প) আর একটি origin (k + 1টি বিকল্প)। (২) Predict আর scan প্রতিটি item-এ স্থির কাজ। Complete-এ [B → γ·, i] ∈ Sk-এর জন্য Si-এর সব item দেখতে হয়, যা O(n). প্রতিটি set-এ O(n)টি item, প্রতিটিতে O(n) কাজ: set প্রতি O(n2), n + 1টি set-এ O(n3). (৩) Unambiguous grammar-এ complete-এর প্রতিটি সফল যোগ একটি আলাদা “গাছের টুকরো”-র সঙ্গে মেলে, তাই একটি item একই set-এ বড়জোর একবার “তৈরি” হয়, দুবার চেষ্টা হয় না; set প্রতি O(n) কাজ, মোট O(n2). এই যুক্তির সূক্ষ্ম অংশটি Earley-র মূল প্রবন্ধে আছে; এখানে বাদ রাখা হলো। (৪) বেশিরভাগ LR grammar-এ প্রতিটি set-এ item-এর সংখ্যা একটি ধ্রুবকে সীমিত থাকে, তবে right recursion-এ সাধারণত নয়; Leo সেই ব্যতিক্রমটি সামলান। ∎

CYK-এর সঙ্গে তুলনাটি এখন স্পষ্ট। CYK-এর ঘর T[i, l] আর Earley-র “origin j, set k” দুটিই input-এর একটি টুকরো; দুটিই dynamic programming. পার্থক্য দিকের: CYK নিচ থেকে ওপরে সব টুকরো সব variable-এ পরীক্ষা করে, তাই সবসময় Θ(n3); Earley বাঁ থেকে ডানে চলে আর (খ)-এর ছাঁকনিতে অসম্ভব টুকরো বাদ দেয়, তাই সহজ grammar-এ কম কাজ করে। আর CYK-এর CNF লাগে, Earley-র লাগে না।

৫ · ε-নিয়মের ফাঁদ আর Aycock–Horspool-এর সমাধান

উপপাদ্য ৪.১-এ ε-নিয়ম বাদ রাখা হয়েছিল কারণ আছে। ε-production A → ε থাকলে [A → ·, k] item একই set Sk-এ শুরু আর শেষ হয়, origin k. Complete তখন Sk-এরই A-অপেক্ষারত item এগিয়ে দেয়। কিন্তু Sk তো তখনো বাড়ছে! যে item [A → ·] সম্পূর্ণ হওয়ার পরে Sk-এ এসে A-র অপেক্ষা শুরু করে, সে আর এগোয় না, কারণ [A → ·, k] আবার যোগ হয় না (আগেই আছে), তাই আবার complete-ও হয় না।

উদাহরণ: S → A B, A → ε, B → A x. এখানে L(G) = {x}. প্রক্রিয়ার ক্রম দেখুন: [S → ·AB, 0] থেকে predict-এ [A → ·, 0]; এটি সম্পূর্ণ, তাই [S → A·B, 0]; তারপর predict-এ [B → ·Ax, 0]; এখন এর জন্য A predict হয়, কিন্তু [A → ·, 0] আগেই আছে, যোগ হয় না, complete-ও আর ঘটে না। ফলে [B → A·x, 0] কখনো তৈরি হয় না, আর “x” প্রত্যাখ্যাত হয়, যদিও এটি language-এর একমাত্র string.

John Aycock আর R. Nigel Horspool তাঁদের ২০০২ সালের প্রবন্ধ “Practical Earley Parsing”-এ (The Computer Journal) একটি ছোট পরিবর্তন প্রস্তাব করেন বলে পরিচিত: আগে থেকে nullable symbol-গুলো হিসাব করুন (পর্ব ২৮-এর fixpoint), আর predict-এর সময় বিন্দুর পরের variable B nullable হলে বিন্দুটি B-র পরেও এক ঘর সরিয়ে item যোগ করুন। নিচের ব্লক দুটি রূপ পাশাপাশি চালায়।

# ε-rules: the classic Earley bug and the Aycock–Horspool fix
G = {"S": [("A", "B")], "A": [()], "B": [("A", "x")]}   # L(G) = {x}
NULLABLE = {"A"}                               # computed by hand (পর্ব ২৮)

def show(it):
    A, rhs, d, j = it
    return f"[{A} → {' '.join(rhs[:d] + ('·',) + rhs[d:])}, {j}]"

def earley(w, fix):
    n = len(w); S = [[] for _ in range(n + 1)]
    def add(k, it):
        if it not in S[k]: S[k].append(it)
    add(0, ("S'", ("S",), 0, 0))
    for k in range(n + 1):
        for A, rhs, d, j in S[k]:              # list grows while we loop
            if d < len(rhs) and rhs[d] in G:              # PREDICT
                for r in G[rhs[d]]: add(k, (rhs[d], r, 0, k))
                if fix and rhs[d] in NULLABLE:            # Aycock–Horspool
                    add(k, (A, rhs, d + 1, j))
            elif d < len(rhs):                            # SCAN
                if k < n and w[k] == rhs[d]: add(k + 1, (A, rhs, d + 1, j))
            else:                                         # COMPLETE
                for B, r2, d2, j2 in S[j]:
                    if d2 < len(r2) and r2[d2] == A:
                        add(k, (B, r2, d2 + 1, j2))
    return S, ("S'", ("S",), 1, 0) in S[n]

for fix in (False, True):
    S, ok = earley(["x"], fix)
    print("with fix" if fix else "naive", "-> accepts 'x':", ok)
    for it in S[0]: print("   ", show(it))

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

naive -> accepts 'x': False
    [S' → · S, 0]
    [S → · A B, 0]
    [A → ·, 0]
    [S → A · B, 0]
    [B → · A x, 0]
with fix -> accepts 'x': True
    [S' → · S, 0]
    [S → · A B, 0]
    [A → ·, 0]
    [S → A · B, 0]
    [B → · A x, 0]
    [B → A · x, 0]

সরল রূপের S0-এ পাঁচটি item, আর ঠিক যেটি দরকার, [B → A·x, 0], নেই; তাই x scan করার মতো কোনো item নেই, উত্তর False. সংশোধিত রূপে [B → ·Ax, 0] প্রক্রিয়ার সময় A nullable বলে বিন্দু সরানো item সরাসরি যোগ হয়, আর x scan হয়ে গ্রহণ। লক্ষ করুন, ভুলটি নির্ভর করে item প্রক্রিয়ার ক্রমের ওপর: S → A A x-এর মতো grammar-এ এই কোডের সরল রূপ কাকতালীয়ভাবে ঠিক উত্তর দেয়, কারণ complete চলার সময় নতুন item একই list-এ যোগ হয়ে loop-এ ধরা পড়ে। তাই এমন ভুল কয়েকটি উদাহরণে চোখে পড়ে না; ছোট grammar-এ সব string-এ brute-force যাচাই লাগে।

সংশোধনটি ঠিক কেন? A nullable মানে A ⇒∗ ε, তাই “সীমানা k-তে A শুরু আর সীমানা k-তেই শেষ” সবসময় সম্ভব; বিন্দু সরানো item উপপাদ্য ৪.১-এর দুই শর্তই মানে। আর ε-এর বাইরে কিছু যোগ হয় না, তাই ভুল item-ও আসে না। বাস্তবের library-গুলো এই সমস্যা নানাভাবে সামলায়: lark-এর Earley-র source-এ “held completions” নামে Elizabeth Scott-এর একটি প্রবন্ধের পদ্ধতির উল্লেখ আছে, যা একই উদ্দেশ্যে সম্পূর্ণ ε-item মনে রাখে। অংশ ৮-এর সত্যিকারের run-এ lark এই grammar-এ “x” ঠিকঠাক গ্রহণ করে।

৬ · Chart থেকে parse forest — exponential গাছ, polynomial forest

Recognizer শুধু হ্যাঁ বা না বলে। Parser-কে গাছ দিতে হয়, আর ambiguous grammar-এ গাছ অনেক। পর্ব ২৭-এ দেখেছেন, E → E+E ∣ E∗E ∣ id-এ k-টি operator-এর expression-এর গাছের সংখ্যা Catalan number Ck = C(2k, k)/(k + 1), যা মোটামুটি 4k হারে বাড়ে। সব গাছ আলাদা করে লিখলে জায়গা exponential. সমাধান হলো গাছগুলোর অভিন্ন অংশ একবারই রাখা। (Catalan সংখ্যার গণিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫০-এ।)

সংজ্ঞা ৬.১ (Shared packed parse forest, SPPF)

একটি directed acyclic graph, যার symbol node (X, i, k) মানে “চিহ্ন X থেকে wi+1⋯wk”, আর প্রতিটি symbol node-এর নিচে এক বা একাধিক packed node, প্রতিটি X-এর একটি আলাদা ভাঙন (কোন নিয়ম, কোথায় ভাগ)। একটি symbol node-এর নিচে দুটি packed node থাকা মানেই ওই জায়গায় ambiguity. প্রতিটি গাছ পাওয়া যায় প্রতিটি symbol node-এ একটি packed node বেছে নিয়ে।

id + id ∗ id-এর shared packed parse forest

নীল আয়তক্ষেত্র: symbol node “E i–k”, মানে সীমানা i থেকে k পর্যন্ত একটি E. হলুদ বৃত্ত: packed node, একটি আলাদা ভাঙন। শুধু যেখানে বিকল্প আছে, সেখানে packed node আঁকা; operator-এর পাতা বাদ।

Shared packed parse forest of id + id * id E 0–5 E 0–3 E 2–5 E 0–1 E 2–3 E 4–5 ক খ id+id∗id
ছবি ৪১.১ — দুটি গাছ, একটি forest. ক (নীল): (id+id)∗id, অর্থাৎ E 0–3 আর E 4–5. খ (কমলা): id+(id∗id), অর্থাৎ E 0–1 আর E 2–5. মোট symbol node ৬টি; দুটি গাছ আলাদা করে আঁকলে E-node লাগত ১০টি। মাঝের E 2–3 দুটি বড় node ভাগাভাগি করে।

Chart থেকেই এই forest পড়া যায়। Sk-এ প্রতিটি সম্পূর্ণ item [A → γ·, i] একটি symbol node (A, i, k)-এর একটি নিয়ম; সেই নিয়মের ডান দিককে টুকরো wi+1⋯wk-এ কতভাবে ভাগ করা যায়, তা ছোট টুকরোর সম্পূর্ণ item দেখে বের হয়। গাছ গোনার জন্য এটুকুই যথেষ্ট, পর্ব ৩১-এর CYK-গোনার মতো একই “যোগ আর গুণ” কৌশলে। নিচের ব্লক chart বানায়, তারপর শুধু সম্পূর্ণ item ব্যবহার করে গাছ গোনে।

# Count parse trees using only the COMPLETED items of the Earley chart
from functools import lru_cache
G = {"E": [("E", "+", "E"), ("E", "*", "E"), ("id",)]}
def chart(w):
    n = len(w); S = [[] for _ in range(n + 1)]
    def add(k, it):
        if it not in S[k]: S[k].append(it)
    add(0, ("S'", ("E",), 0, 0))
    for k in range(n + 1):
        for A, rhs, d, j in S[k]:           # list grows while we loop
            if d < len(rhs) and rhs[d] in G:
                for r in G[rhs[d]]: add(k, (rhs[d], r, 0, k))
            elif d < len(rhs):
                if k < n and w[k] == rhs[d]: add(k + 1, (A, rhs, d + 1, j))
            else:
                for B, r2, d2, j2 in S[j]:
                    if d2 < len(r2) and r2[d2] == A: add(k, (B, r2, d2 + 1, j2))
    return S
def count_trees(w):
    S = chart(w)
    done = {(A, rhs, j, k) for k in range(len(w) + 1)
            for A, rhs, d, j in S[k] if d == len(rhs)}   # A -> rhs over j..k
    @lru_cache(None)
    def N(A, i, k):                          # trees with root A over w[i:k]
        return sum(ways(r, i, k) for B, r, j, kk in done if (B, j, kk) == (A, i, k))
    @lru_cache(None)
    def ways(rhs, i, k):                     # no ε-rules: each symbol takes ≥ 1
        if not rhs: return 1 if i == k else 0
        X, rest = rhs[0], rhs[1:]
        if X not in G: return ways(rest, i + 1, k) if i < k and w[i] == X else 0
        return sum(N(X, i, m) * ways(rest, m, k) for m in range(i + 1, k - len(rest) + 1))
    return N("E", 0, len(w)), sum(map(len, S))
for ops in range(1, 8):
    w = ("id " + " ".join(["+ id", "* id"][i % 2] for i in range(ops))).split()
    print(f"{ops} operators, n={len(w):2}: " + "trees=%4d  chart items=%4d" % count_trees(tuple(w)))

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

1 operators, n= 3: trees=   1  chart items=  19
2 operators, n= 5: trees=   2  chart items=  35
3 operators, n= 7: trees=   5  chart items=  56
4 operators, n= 9: trees=  14  chart items=  82
5 operators, n=11: trees=  42  chart items= 113
6 operators, n=13: trees= 132  chart items= 149
7 operators, n=15: trees= 429  chart items= 190

গাছের সংখ্যা ১, ২, ৫, ১৪, ৪২, ১৩২, ৪২৯: ঠিক Catalan ধারা, পর্ব ২৭-এর brute-force গোনার সঙ্গে মেলে। অথচ chart-এর item মাত্র ১৯ থেকে ১৯০: প্রতিবার operator একটি বাড়লে গাছ প্রায় তিনগুণ (শেষে প্রায় চারগুণ), কিন্তু item বাড়ছে প্রতিবার আগের চেয়ে কিছুটা বেশি করে, n2-এর মাপে। N(A, i, k) হলো forest-এর symbol node (A, i, k)-এর গাছ-সংখ্যা, আর done-এর প্রতিটি সদস্য একটি নিয়ম-ভিত্তিক packed বিকল্প। প্রতিটি (চিহ্ন, শুরু, শেষ) একবারই হিসাব হয় (lru_cache), তাই গোনা নিজেও polynomial, যদিও উত্তরটি exponential বড়।

এখানে একটি সূক্ষ্মতা আছে। E → E + E + E-এর মতো লম্বা ডান দিক থাকলে একটি packed node-এর অনেক সন্তান, আর সব ভাগের জায়গা আলাদা রাখলে forest-এর আকার np+1 পর্যন্ত যেতে পারে, যেখানে p দীর্ঘতম ডান দিকের দৈর্ঘ্য। বাস্তবের SPPF তাই লম্বা নিয়মকে দুই-দুই করে ভাঙা “intermediate node” রাখে (CNF-এর binary ভাবনার মতো), যাতে আকার O(n3)-এ থাকে। lark-এর forest-এ এই intermediate node-এর ধারণা আছে বলে source code-এ দেখা যায়।

৭ · GLR — LR parser যখন ভাগ হয়ে যায়

Earley-র ভাবনা “সব সম্ভাবনা একটি set-এ”. একই লক্ষ্যে আরেকটি পথ আছে, যা পর্ব ৩৯-এর LR parser থেকে শুরু করে। LR টেবিলের কোনো ঘরে conflict থাকলে (shift নাকি reduce, বা কোন নিয়মে reduce), সাধারণ LR parser থেমে যায় বা একটি বেছে নেয়। Generalized LR (GLR) parser দুটিই নেয়: stack-টি ভাগ হয়ে যায়, আর প্রতিটি কপি নিজের পথে চলে। কোনো কপি পরে ব্যর্থ হলে সেটি মুছে যায়; একাধিক কপি শেষ পর্যন্ত সফল হলে সেটিই ambiguity.

প্রতিবার পুরো stack কপি করলে খরচ exponential হতো। মূল কৌশলটি তাই graph-structured stack (GSS): কপিগুলোর অভিন্ন নিচের অংশ একবারই রাখা হয়, আর ওপরের ভিন্ন অংশ শাখা হয়ে ছড়ায়; দুটি কপি একই state-এ একই অবস্থানে পৌঁছালে আবার মিলে যায়। পর্ব ৩২-এর nondeterminism-এর কথা মনে করুন: একটি nondeterministic PDA-র সব পথ একসঙ্গে চালানোর বাস্তব রূপ এটিই। নিচের stepper ধারণাগত; LR automaton-এর state নম্বর বাদ দিয়ে শুধু stack-এর চিহ্ন দেখানো হয়েছে, ⊥ মানে stack-এর তলা।

Grammar: E → E+E ∣ E∗E ∣ id
পড়া হয়েছে
পরের token
ঘটনা
  1. সাধারণ LR-এর মতো শুরু। id shift, তারপর E → id দিয়ে reduce. Stack: ⊥ E. এখনো কোনো দ্বিধা নেই, তাই GLR ঠিক একটি সাধারণ LR parser.
  2. আরও দুটি token. + আর id shift, E → id reduce. Stack: ⊥ E + E. পরের token ∗.
  3. Conflict, তাই ভাগ। টেবিলে দুটি কাজ: E → E+E দিয়ে reduce (তাহলে + আগে হয়), অথবা ∗ shift (তাহলে ∗ আগে হয়)। GLR দুটিই করে। শাখা ক: reduce করে ⊥ E, তারপর ∗ shift. শাখা খ: সরাসরি ∗ shift. নিচের “⊥ E” দুই শাখা ভাগাভাগি করে; কপি হয়নি।
  4. একটি token, দুই শাখা। শেষ id একবারই পড়া হয়, আর দুই শাখার ওপরেই shift হয়, তারপর E → id. GSS-এ দুটি আলাদা মাথা। Input একবারই বাঁ থেকে ডানে পড়া হচ্ছে, Earley-র মতো।
  5. শেষে reduce. শাখা ক: E → E∗E, ফলে ⊥ E, যার অর্থ (id+id)∗id. শাখা খ: প্রথমে E → E∗E, ফলে ⊥ E + E, তারপর E → E+E, ফলে ⊥ E, যার অর্থ id+(id∗id).
  6. মিলন। দুই শাখা এখন একই state-এ, একই E দিয়ে, একই টুকরো 0–5 ঢেকে। GSS তাদের একটি মাথায় মেলায়, আর forest-এর symbol node E 0–5-এর নিচে দুটি packed node যোগ হয়, ছবি ৪১.১-এর ক আর খ। Parser গ্রহণ করে, একটি forest-সহ।

GLR-এর ইতিহাস দুই ধাপে বলা হয়। Bernard Lang ১৯৭৪ সালে nondeterministic parser-কে দক্ষভাবে চালানোর একটি সাধারণ কৌশল দেন, যা পরে GLR-এর তাত্ত্বিক ভিত্তি হিসেবে স্বীকৃত হয়। Masaru Tomita ১৯৮৫ সালের একটি সম্মেলন-প্রবন্ধে আর ১৯৮৬ সালের বই Efficient Parsing for Natural Language-এ মানুষের ভাষার parsing-এর জন্য graph-structured stack আর shared packed forest-এর ব্যবহারিক রূপ জনপ্রিয় করেন। Tomita-র মূল algorithm ε-নিয়মের কিছু grammar-এ ভুল করত বলে পরে দেখা যায়; Elizabeth Scott আর Adrian Johnstone-এর RNGLR (২০০৬ সালের প্রবন্ধ) সেটি সংশোধন করে বলে পরিচিত। আর মূল GLR-এর সবচেয়ে খারাপ সময় দীর্ঘতম নিয়মের দৈর্ঘ্যের ওপর নির্ভর করে, কিছু পরের রূপ O(n3)-এ নামায়।

GLR-এর বড় সুবিধা: grammar প্রায় LR হলে, অর্থাৎ conflict কম আর বিরল জায়গায়, parser প্রায় সবসময় একটিমাত্র stack নিয়ে চলে আর LR-এর গতি পায়; শাখা হয় শুধু দ্বিধার জায়গায়। Bison-এ %glr-parser ঘোষণা দিলে একই grammar ফাইল থেকে GLR parser তৈরি হয়, যা C++-এর মতো parse করা কঠিন ভাষার কিছু টুলে ব্যবহারের কথা জানা যায়। Earley আর GLR তাই একে অপরের প্রতিদ্বন্দ্বী নয়, একই সমস্যার দুই দিক থেকে উত্তর: একটি top-down predict থেকে, অন্যটি bottom-up LR টেবিল থেকে।

৮ · বাস্তবে Earley — lark, CYK আর বড় input (সত্যিকারের run)

এবার তত্ত্বের দাবিগুলো একটি সত্যিকারের library-তে পরীক্ষা। lark (Python parser library, MIT licence; পর্ব ২৬, ২৭ আর ৩১-এ ব্যবহৃত) তিন ধরনের Earley ফল দিতে পারে: ambiguity="resolve" (একটি গাছ বেছে দেয়), "explicit" (বিকল্পগুলো _ambig node-এ) আর "forest" (সরাসরি SPPF-এর root). lark-এর কোডে কোনো network বা usage-reporting অংশ নেই, তা scratch-এ খুঁজে দেখা হয়েছে। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টি চারটি কাজ করে: (১) k = 1 থেকে 6 operator-এ lark-এর explicit গাছ গুনে পর্ব ৩১-এর ধাঁচের CYK-গোনা আর Catalan সংখ্যার সঙ্গে মেলায়; (২) বড় হতে থাকা input-এ নিজের Earley-র item-সংখ্যা, lark-এর SPPF-এর আকার আর parse-এর সময় মাপে, ambiguous আর স্তরভাগ করা (layered) দুই grammar-এ; (৩) ৩০০০টি random token-ক্রমে তিনটি recognizer মেলায়; (৪) অংশ ৫-এর ε-grammar lark-এ চালায়। মূল অংশ:

LARK_AMB = 'e: e "+" e | e "*" e | "id"\n%ignore " "'
LARK_LAY = 'e: e "+" t | t\nt: t "*" f | f\nf: "id" | "(" e ")"\n%ignore " "'
amb   = Lark(LARK_AMB, start="e", parser="earley")
lay   = Lark(LARK_LAY, start="e", parser="earley")
amb_x = Lark(LARK_AMB, start="e", parser="earley", ambiguity="explicit")
amb_f = Lark(LARK_AMB, start="e", parser="earley", ambiguity="forest")
...
for k in (5, 10, 20, 40, 80):                   # n = 2k + 1 tokens
    w = ["id"] + sum([[("+", "*")[i % 2], "id"] for i in range(k)], [])
    _, ia = earley_items(AMB, "E", w); _, il = earley_items(LAY, "E", w)
    sy, pk = forest_size(amb_f.parse(" ".join(w)))   # symbol + packed nodes
    ta = min(timed(amb, " ".join(w)) for _ in range(3))
...

সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13, uv 0.11.28; random seed স্থির):

~/bazarghar-toc$ uv run python earley_lark.py
lark 1.3.1 | Python 3.12.13

== explicit ambiguity: trees for id op id op ... (k operators)
k=1  lark trees=   1  CYK count=   1  Catalan=   1
k=2  lark trees=   2  CYK count=   2  Catalan=   2
k=3  lark trees=   5  CYK count=   5  Catalan=   5
k=4  lark trees=  14  CYK count=  14  Catalan=  14
k=5  lark trees=  42  CYK count=  42  Catalan=  42
k=6  lark trees= 132  CYK count= 132  Catalan= 132

== growing input: chart items (own Earley), SPPF size, lark time
  n  items(amb) items(lay)  sppf sym+packed   trees(amb)   t_amb ms  t_lay ms
 11        113         64     51+71                42        1.1       0.5
 21        343        113    176+341         1.68e+04        3.8       0.9
 41       1178        213    651+1981        6.56e+09       19.8       1.6
 81       4348        413   2501+13161       2.62e+21      125.6       3.3
161      16688        813   9801+95121       1.14e+45      972.0       6.6

== membership: own Earley vs CYK vs lark Earley on random token strings
strings: 3000  accepted: 179  all three agree: 3000/3000

== epsilon rules: s -> a b, a -> (empty), b -> a 'x'
Tree(Token('RULE', 's'), [Tree(Token('RULE', 'a'), []), Tree(Token('RULE', 'b'), [Tree(Token('RULE', 'a'), [])])])

গাছ গোনা: তিনটি স্বাধীন হিসাব, lark-এর _ambig গাছ, CNF-এর ওপর CYK-গোনা আর Catalan সূত্র, ছয়টি ক্ষেত্রেই এক। n = 11-এ আমাদের নিজের Earley-র ১১৩টি item ওপরের earley_count.py-র “5 operators” লাইনের সঙ্গেও মেলে।

Chart আর forest: n প্রায় দ্বিগুণ হলে ambiguous grammar-এ item প্রায় ৩ থেকে ৩.৮ গুণ, অর্থাৎ n2-এর দিকে (22 = 4); layered grammar-এ ঠিক দ্বিগুণের কাছাকাছি (৬৪, ১১৩, ২১৩, ৪১৩, ৮১৩), অর্থাৎ linear. SPPF-এর packed node প্রতি দ্বিগুণে ৪.৮ থেকে ৭.২ গুণ বাড়ছে, n3-এর দিকে। অথচ শেষ সারিতে গাছ প্রায় 1.14 × 1045টি, আর পুরো forest-এ node এক লাখ পাঁচ হাজারের মতো (৯৮০১ + ৯৫১২১)।

সময়: ambiguous grammar-এ প্রতি দ্বিগুণে সময় ৩.৫, ৫.২, ৬.৩ আর ৭.৭ গুণ, বড় n-এ ৮-এর দিকে: O(n3)-এর চিহ্ন। Layered (unambiguous, LR) grammar-এ প্রায় দ্বিগুণ, অর্থাৎ linear; উপপাদ্য ৪.২-এর (৪) নম্বর দাবির সঙ্গে মেলে। ১৬১ token-এ দুই grammar-এর সময়ের পার্থক্য প্রায় ১৫০ গুণ, যদিও দুটি একই language-এর (বন্ধনী ছাড়া) একই string. সংখ্যাগুলো যন্ত্রভেদে বদলাবে; অনুপাতগুলোই আসল তথ্য।

মিল আর ε: ৩০০০টি random string-এ (গৃহীত ১৭৯টি) নিজের Earley, CNF-এর CYK আর lark একটিতেও অমিল করেনি। শেষ লাইনে lark অংশ ৫-এর grammar-এ “x” গ্রহণ করে গাছ দিয়েছে: s-এর নিচে ফাঁকা a, আর b-এর নিচে আবার ফাঁকা a.

এই run থেকে একটি ব্যবহারিক শিক্ষা: সাধারণ parser হাতে থাকলেও grammar-এর নকশা গুরুত্বপূর্ণ। একই ভাষা দুটি grammar-এ লেখা যায়, আর ambiguous রূপটি শুধু ধীরই নয়, তার ফলও একটি forest, যা থেকে একটি অর্থ বেছে নিতে আলাদা নিয়ম লাগে। পর্ব ৪২-এ এই নকশার কৌশলগুলো আসবে। নিচের সারণি সিদ্ধান্ত নিতে সাহায্য করবে।

পদ্ধতিকোন grammarসময়কখন বেছে নেবেন
LL(1), LR(1)/LALRবিশেষ শ্রেণি, conflict নেইO(n)programming language-এর compiler, স্থির DSL
CYKCNFসবসময় Θ(n3)তত্ত্ব, শিক্ষা, probabilistic grammar
Earleyযেকোনো CFG, মূল রূপেO(n3); unambiguous-এ O(n2); অনেক LR-এ O(n)grammar-এর prototype, ambiguous DSL, ভাষাতত্ত্ব
GLRযেকোনো CFG (LR টেবিল থেকে)প্রায়-LR grammar-এ প্রায় linear; খারাপ ক্ষেত্রে polynomialকিছু conflict-সহ বড় grammar, যেমন C++-ধাঁচের ভাষা

আরও গভীরে: সাধারণ CFG parsing n3-এর চেয়ে দ্রুত হতে পারে কি না, তা খোলা প্রশ্ন: Valiant ১৯৭৫ সালে matrix গুণের মাধ্যমে nω দেখান, আর Lee ২০০২ সালে দেখান দ্রুত parsing থেকে দ্রুত Boolean matrix গুণ আসে (পর্ব ৩১)। আরেকটি সীমা: একটি grammar ambiguous কি না, তা সাধারণভাবে undecidable (পর্ব ৫৪), তাই Earley বা GLR একটি নির্দিষ্ট input-এ ambiguity দেখাতে পারে, কিন্তু grammar-টি সব input-এ unambiguous, তা প্রমাণ করতে পারে না। ভাষাতত্ত্বে Earley-র ধারণা probabilistic grammar আর “mildly context-sensitive” formalism-এর parser পর্যন্ত বিস্তৃত হয়েছে।

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

  • একটি ছোট grammar আর ৩–৪ token-এর input দিয়ে Earley chart ভরুন। অংশ ২-এর stepper-এর পদ্ধতি; প্রতিটি item-এর পাশে predict, scan বা complete লিখুন।
  • Earley item [A → α·β, j] ∈ Sk-এর অর্থ কী? α টুকরো wj+1⋯wk তৈরি করে, আর সীমানা j-তে A শুরু হওয়া সম্ভব।
  • Earley-র time complexity? সবচেয়ে খারাপ O(n3), unambiguous-এ O(n2), অনেক LR grammar-এ O(n).
  • Left recursion-এ Earley কেন loop করে না? একই item একটি set-এ একবারই যোগ হয়, আর item-এর সংখ্যা সসীম।
  • GLR কী করে conflict-এ? Stack ভাগ করে সব পথ চালায়; graph-structured stack ভাগাভাগি রাখে, আর ambiguity একটি shared packed forest-এ আসে।

৯ · AI-এর যুগে Earley আর GLR

“Earley parser-এর Python কোড দাও” বললে AI assistant কয়েক সেকেন্ডে ঝকঝকে কোড দেয়, আর সাধারণ উদাহরণে তা ঠিকই চলে। সমস্যা লুকিয়ে থাকে কোণের ক্ষেত্রে: ε-নিয়ম, item-এর ক্রম, complete-এর সময় কোন set পড়া হচ্ছে। অংশ ৫-এ দেখেছেন, ε-ভুলটি একটি grammar-এ ধরা পড়ে, আরেকটিতে পড়ে না। তাই AI-এর লেখা parser-কে বিশ্বাস করার একমাত্র নিরাপদ পথ: একটি সরল brute-force reference (grammar থেকে দৈর্ঘ্য n পর্যন্ত সব string তৈরি করা) আর সেই দৈর্ঘ্যের সব string-এ মিলিয়ে দেখা, ε-নিয়মসহ কয়েকটি grammar-এ।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
ε-নিয়মে item হারানো (অংশ ৫-এর ফাঁদ), বা খালি string ε-এর ক্ষেত্র ভুলে যাওয়াS → A B, A → ε, B → A x-এর মতো grammar-এ চালান; nullable variable-সহ grammar-এ brute force-এর সঙ্গে সব ছোট string মেলান
Item-এ origin না রাখা, বা complete-এ ভুল set (Sk-এর বদলে Si-এর উল্টো) পড়াid+id-এর chart হাতে ভরে কোডের ছাপার সঙ্গে item ধরে মেলান
“Earley সবসময় O(n2)” বা “GLR সবসময় linear” জাতীয় দাবিAmbiguous grammar-এ n দ্বিগুণ করে সময় মাপুন; অনুপাত ৮-এর দিকে গেলে ঘন
“Parser ambiguity দেখায়নি, তাই grammar unambiguous” সিদ্ধান্তAmbiguity সাধারণভাবে undecidable; শুধু বলা যায়, পরীক্ষিত input-গুলোয় একটি গাছ
সব গাছ list-এ তৈরি করা, ফলে বড় input-এ memory শেষগাছের সংখ্যা আগে গুনুন (Catalan বৃদ্ধি); forest রেখে প্রয়োজনমতো একটি গাছ বের করুন
বানানো ইতিহাস (ভুল সাল, ভুল লেখক) বা অস্তিত্বহীন প্রবন্ধEarley ১৯৭০, Tomita ১৯৮৫–৮৬, Aycock–Horspool ২০০২-এর মূল শিরোনাম খুঁজুন; Grune–Jacobs-এর বইয়ে মিলিয়ে নিন

AI-কে ভালোভাবে কাজে লাগানোর উপায়: chart-এর সঙ্গে প্রতিটি item-এর উৎস আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্ব শিখছি। Grammar: S → S S | a. Input: aaa. ১. এই input-এর পুরো Earley chart (S0 থেকে S3) দাও। প্রতিটি item [A → α·β, j] আকারে লেখো, আর পাশে লেখো সেটি predict, scan নাকি complete থেকে এসেছে। ২. কোনো item একই set-এ একাধিক উপায়ে তৈরি হলে চিহ্নিত করো, আর বলো এর সঙ্গে ambiguity-র সম্পর্ক কী। ৩. এই input-এর parse tree কয়টি, chart থেকে কীভাবে গুনলে, দেখাও। ৪. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা grammar থেকে দৈর্ঘ্য ৬ পর্যন্ত সব string brute force-এ তৈরি করে আর তোমার Earley কোডের সঙ্গে সব string-এ মেলায়; একটি ε-নিয়মসহ grammar-এও পরীক্ষা চালাও। ৫. কোনো ধাপ নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

(নিজে যাচাই করুন: সঠিক chart-এ S0 থেকে S3-এ item যথাক্রমে ৩, ৫, ৭ আর ৯টি, মোট ২৪টি। S3-এ [S → S S·, 0] দুটি উপায়ে আসে, a∣aa আর aa∣a ভাগে; গাছ ২টি। ওপরের earley_chart.py-তে grammar আর input বদলে মিলিয়ে নিন; অনুশীলন ১-এ পুরো chart আছে।)

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

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

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

প্র ০১Earley-র algorithm ১৯৭০ সালেই ছিল, তবু কয়েক দশক ধরে compiler-এর জগৎ LALR আর LL-এ থাকল কেন? আর এখন lark-এর মতো library-তে Earley আবার জনপ্রিয় কেন?

১৯৭০-এর দশকের কম্পিউটারের memory কয়েকশো কিলোবাইটের মাপে, আর একটি compiler-কে হাজার হাজার লাইনের program দ্রুত পড়তে হতো। Earley-র chart প্রতিটি token-এর জন্য একটি set রাখে, আর প্রতিটি set-এ অনেক item; LALR parser রাখে শুধু একটি stack আর একটি স্থির টেবিল। Stephen Johnson-এর yacc (১৯৭০-এর দশকের মাঝামাঝি, Bell Labs) LALR(1) টেবিল তৈরি করত, আর Unix-এর সঙ্গে ছড়িয়ে পড়ে; ফলে একটি প্রজন্ম “grammar লিখুন, conflict মেটান, linear parser পান” রীতিতে অভ্যস্ত হয়। এর একটি বাড়তি লাভও ছিল: conflict-এর বার্তা grammar নকশাকারীকে সতর্ক করত যে ভাষাটি হয়তো ambiguous, আর programming language-এ ambiguity সাধারণত অবাঞ্ছিত।

Earley নিজেও তাঁর প্রবন্ধে দেখিয়েছিলেন, অনেক বাস্তব grammar-এ তাঁর algorithm linear সময়ে চলে; সমস্যা ছিল ধ্রুবক অংশে, অর্থাৎ প্রতিটি token-এ কত কাজ। তার ওপর ε-নিয়মের সূক্ষ্মতা আর parse tree বের করার জটিলতা বাস্তব প্রয়োগকে কঠিন করত।

চার দশক পরে পরিস্থিতি বদলেছে। যন্ত্র কয়েক হাজার গুণ দ্রুত, memory প্রচুর, আর বেশিরভাগ DSL বা config ভাষার input ছোট। Aycock–Horspool-এর ২০০২ সালের প্রবন্ধ ε-সমস্যার পরিষ্কার সমাধান দেয়, Elizabeth Scott-এর কাজ chart থেকে SPPF বানানোর নির্ভরযোগ্য পদ্ধতি দেয়, আর Joop Leo-র পরিবর্তন right recursion-এ গতি আনে। Jeffrey Kegler-এর Marpa-র মতো parser এসব মিলিয়ে ব্যবহারিক Earley-র পক্ষে জোরালো যুক্তি দেয় বলে পরিচিত। lark এর একটি Python রূপ, আর একই grammar থেকে LALR-ও বানাতে পারে। এখনকার রীতি তাই প্রায়ই দুই ধাপের: নকশার সময় Earley দিয়ে স্বাধীনভাবে grammar লেখা, আর grammar স্থির হলে, দরকার হলে, LALR-এ যাওয়া।

মূল উপলব্ধি: একটি algorithm-এর জনপ্রিয়তা শুধু তার O(·) সীমা নয়, যুগের যন্ত্র, input-এর আকার আর ব্যবহারকারীর কাজের ধরনের ওপরও নির্ভর করে। যে খরচ ১৯৭৫ সালে অসহ্য ছিল, আজ তা প্রায়ই চোখেই পড়ে না।

প্র ০২GLR মূলত মানুষের ভাষার জন্য জনপ্রিয় হয়েছিল। মানুষের ভাষার ambiguity কেমন, আর একটি parser কেন সব অর্থ রাখতে চায়, একটি বেছে না নিয়ে?

মানুষের ভাষার ambiguity প্রায় সব স্তরে। ইংরেজির পরিচিত উদাহরণ “I saw the man with the telescope”: telescope কি দেখার যন্ত্র, নাকি লোকটির হাতে? বাংলাতেও একই অবস্থা: “বড় বাজারের দোকান” বা “পুরোনো বইয়ের তাক”-এ বিশেষণটি কোন শব্দের সঙ্গে যায়, তা grammar বলে না, প্রসঙ্গ বলে। একটি বাক্যে কয়েকটি এমন জায়গা থাকলে সম্ভাব্য অর্থের সংখ্যা গুণ হয়ে বাড়ে, Catalan সংখ্যার মতো, কারণ প্রতিটি সংযুক্তি একটি “বন্ধনী কোথায় বসবে” প্রশ্ন।

১৯৮০-এর দশকে Carnegie Mellon-এ machine translation-এর গবেষণায় Masaru Tomita এই সমস্যার মুখোমুখি হন বলে বর্ণনা পাওয়া যায়। Syntax-এর স্তরে একটি অর্থ বেছে নিলে পরে অর্থের স্তরে দেখা যেতে পারে সেটি ভুল ছিল, তখন পেছনে ফিরে আবার parse করতে হয়। তার চেয়ে ভালো, সব অর্থ একটি সংক্ষিপ্ত forest-এ রেখে পরের ধাপকে বেছে নিতে দেওয়া: অর্থ, অভিধান বা পরিসংখ্যান দেখে। GLR-এর graph-structured stack আর shared packed forest ঠিক এই কাজটি polynomial জায়গায় করে।

পরিসংখ্যানের যুগে ধারণাটি আরও শক্ত হয়। Probabilistic CFG-তে প্রতিটি নিয়মের একটি সম্ভাবনা থাকে, আর forest-এর প্রতিটি packed node-এ গুণ-যোগ করে সবচেয়ে সম্ভাব্য গাছ বের করা যায়, ঠিক পর্ব ৩১-এর গাছ-গোনার কৌশলে, যোগের বদলে সর্বোচ্চ নিয়ে। আজকের বড় language model অনেক কাজে স্পষ্ট parse tree ছাড়াই চলে, তবু “সব অর্থ রেখে পরে বাছাই” ভাবনাটি speech recognition-এর lattice থেকে compiler-এর overload resolution পর্যন্ত নানা জায়গায় দেখা যায়।

মূল উপলব্ধি: যখন সঠিক সিদ্ধান্তের তথ্য পরে আসে, তখন আগেভাগে একটি পথ বেছে নেওয়ার চেয়ে সব পথ সংক্ষিপ্তভাবে ধরে রাখা ভালো। Forest সেই “সিদ্ধান্ত পিছিয়ে দেওয়া”-র গাণিতিক রূপ।

প্র ০৩সত্যিকারের run-এ ১৬১ token-এ প্রায় ১০৪৫টি parse tree, অথচ forest-এ এক লাখের কিছু বেশি node. এটি কীভাবে সম্ভব, আর এর ব্যবহারিক মানে কী?

মূল কথা হলো গাছের সংখ্যা আর গাছের উপাদানের সংখ্যা আলাদা জিনিস। n দৈর্ঘ্যের input-এ একটি টুকরো (i, k) মাত্র n(n + 1)/2টি, আর grammar স্থির হলে চিহ্নও সসীম। তাই “চিহ্ন X থেকে টুকরো (i, k)” আকারের আলাদা প্রশ্ন বড়জোর |V| · n2-এর মাপে। একটি গাছ মানে এই প্রশ্নগুলোর প্রতিটির জন্য একটি উত্তর (একটি ভাঙন) বেছে নেওয়া; আর পছন্দগুলো স্বাধীনভাবে মেশানো যায় বলে গাছের সংখ্যা পছন্দের গুণফল, যা exponential. Forest পছন্দগুলো রাখে, পছন্দের সব সমন্বয় নয়।

ছোট একটি তুলনা: একটি বাজারঘরের অর্ডারে তিন ধরনের চাল, চার ধরনের ডাল আর পাঁচ ধরনের তেল থেকে বাছার সুযোগ থাকলে সম্ভাব্য ঝুড়ি ৬০টি, কিন্তু তালিকায় লিখতে হয় মাত্র ১২টি পণ্য। Forest সেই তালিকা, গাছ সেই ঝুড়ি। Run-এর সংখ্যা এটি দেখায়: symbol node ৯৮০১টি, যা n2-এর মাপে, আর packed node ৯৫,১২১টি, যা ভাগের জায়গার কারণে n3-এর মাপে।

ব্যবহারিক মানে তিনটি। প্রথম, ambiguous grammar-এ “সব গাছ দাও” কখনো চাওয়া উচিত নয়; lark-এর explicit রূপও বড় input-এ বিশাল হতে পারে, কারণ সেটি গাছ-আকারে বিকল্প খুলে লেখে। দ্বিতীয়, forest-এর ওপর সরাসরি কাজ করা যায়: গাছ গোনা, সবচেয়ে সম্ভাব্য গাছ খোঁজা, বা অগ্রাধিকারের নিয়মে (যেমন “∗ আগে”) প্রতিটি packed জায়গায় একটি বিকল্প রাখা, সব polynomial সময়ে। তৃতীয়, forest-এর আকারও নির্ভর করে grammar-এর আকারের ওপর; লম্বা নিয়মে intermediate node ছাড়া আকার আরও বাড়ে।

মূল উপলব্ধি: Exponential সংখ্যক বস্তু polynomial আকারে লেখা যায় যখন তারা স্বাধীন ছোট পছন্দের সমন্বয়; dynamic programming আর shared forest একই ভাবনার দুই রূপ।

প্র ০৪Earley বা GLR যেকোনো CFG parse করতে পারলে, programming language-এর নকশাকারীরা এখনো LL বা LR-উপযোগী grammar নিয়ে মাথা ঘামান কেন?

প্রথম কারণ নিশ্চয়তা। একটি LR(1) টেবিল conflict ছাড়া তৈরি হলে grammar-টি unambiguous, এটি একটি প্রমাণিত সত্য। Programming language-এ প্রতিটি program-এর ঠিক একটি অর্থ থাকা দরকার; একই কোড দুই compiler-এ দুইভাবে বোঝা গেলে ভয়ংকর ভুল হয়। Earley বা GLR কোনো input-এ ambiguity পেলে জানায়, কিন্তু grammar-টি সব input-এ unambiguous কি না, তা সাধারণভাবে কেউ বলতে পারে না, কারণ CFG-এর ambiguity undecidable (পর্ব ৫৪)। LR-এর conflict-পরীক্ষা তাই একটি রক্ষণশীল কিন্তু নিশ্চিত ছাঁকনি: কিছু unambiguous grammar-ও বাদ পড়ে, তবে যা পার হয়, তা নিশ্চিত।

দ্বিতীয় কারণ গতি আর পূর্বানুমেয়তা। Compiler বা editor লাখ লাইনের কোড পড়ে; linear সময়ের নিশ্চয়তা আর একটিমাত্র stack-এর ছোট memory বাস্তবে গুরুত্বপূর্ণ। সত্যিকারের run-এ দেখেছেন, একই language-এর ambiguous grammar-এ ১৬১ token-এ সময় প্রায় ১৫০ গুণ।

তৃতীয় কারণ ভুলের বার্তা। LL বা LR parser জানে ঠিক কোন token প্রত্যাশিত ছিল, তাই “এখানে ; প্রত্যাশিত” ধরনের বার্তা সহজ। Earley-রও valid prefix property আছে, তবে প্রত্যাশিত token-এর set বড় আর কম কেন্দ্রীভূত হতে পারে।

তবু বাস্তবে মিশ্র ছবি দেখা যায়। C++-এর মতো কিছু ভাষার grammar স্বভাবতই LR নয়, আর কিছু টুল GLR ব্যবহার করে বলে জানা যায়; Bison-এর %glr-parser এই কারণেই আছে। অনেক production compiler আবার হাতে লেখা recursive descent ব্যবহার করে, ভালো বার্তা আর নমনীয়তার জন্য। আর DSL-এর prototype পর্যায়ে Earley দিয়ে শুরু করে পরে LALR-এ যাওয়া একটি পরিচিত রীতি, যা পর্ব ৪০ আর ৪২-এর বিষয়।

মূল উপলব্ধি: সাধারণ parser ক্ষমতা দেয়, সীমিত parser নিশ্চয়তা দেয়। ভাষার নকশায় “সব grammar parse করা যায়” যথেষ্ট নয়; “প্রতিটি program-এর অর্থ এক” প্রমাণ করা আরও জরুরি।

প্র ০৫Earley chart আর পর্ব ৩২–৩৪-এর pushdown automaton-এর মধ্যে সম্পর্ক কী? Earley কি আসলে একটি nondeterministic PDA-র দক্ষ simulation?

পর্ব ৩৪-এ দেখেছেন, প্রতিটি CFG থেকে একটি PDA বানানো যায়, যা stack-এ sentential form-এর বাকি অংশ রেখে, একটি variable পেলে তার যেকোনো নিয়ম nondeterministically বেছে নিয়ে, আর terminal পেলে input-এর সঙ্গে মিলিয়ে চলে। এই PDA-টি আসলে একটি top-down parser, শুধু সে “আন্দাজ” করে। সমস্যা হলো, সব আন্দাজ আলাদা করে চালালে পথ exponential সংখ্যক, আর left recursion-এ stack অসীম উঁচু হতে পারে, ঠিক recursive descent-এর মতো।

Earley এই সব পথ একসঙ্গে চালায়, কিন্তু stack পুরোটা রাখে না। একটি item [A → α·β, j] হলো stack-এর একটি “ফ্রেম”-এর বর্ণনা: A-র নিয়ম চলছে, এতদূর এসেছে, আর সীমানা j-তে শুরু হয়েছিল। Origin j হলো সেই ফ্রেমের নিচের ফ্রেমগুলোর একটি সূচক: complete ধাপ Sj-তে গিয়ে খুঁজে নেয় কারা A-র অপেক্ষায় ছিল, অর্থাৎ stack-এর নিচের অংশ “ফিরিয়ে আনে”. এই অর্থে Earley chart একটি সংক্ষিপ্ত, ভাগ করা stack, ঠিক যেমন GLR-এর graph-structured stack একটি LR-PDA-র সব stack একসঙ্গে রাখে।

একই ভাবনার একটি সাধারণ তাত্ত্বিক রূপও আছে। Lang-এর ১৯৭৪ সালের কাজ দেখায়, একটি nondeterministic PDA-র চলাকে সীমিত আকারের তথ্যে (দুটি অবস্থান আর stack-এর ওপরের অংশ) ভেঙে dynamic programming দিয়ে polynomial সময়ে simulate করা যায়, আর এর থেকে Earley-ধাঁচ আর GLR-ধাঁচ দুটি parser-ই পাওয়া যায় বলে বর্ণনা করা হয়। এটি “PDA-র acceptance polynomial সময়ে decidable” দাবির একটি সরাসরি algorithm, CYK ছাড়াই।

মূল উপলব্ধি: Nondeterminism মানেই exponential খরচ নয়। যখন আলাদা পথগুলোর অবস্থা অল্প কিছু সংখ্যায় (অবস্থান, নিয়ম, বিন্দু) লেখা যায়, তখন পথগুলো মিলিয়ে polynomial সময়ে সব পথ একসঙ্গে চালানো যায়; Earley, GLR আর CYK এরই তিন রূপ।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। earley_chart.py আর earley_count.py ব্লকে grammar বা input বদলে উত্তর যাচাই করতে পারেন।

  1. Chart ভরা (trace): Grammar S → S S ∣ a (ambiguous আর left-recursive). Input “aaa”-এর জন্য S0 থেকে S3 পর্যন্ত Earley chart ভরুন, প্রতিটি item-এর উৎস লিখুন। কোন item একই set-এ দুই উপায়ে তৈরি হয়, আর parse tree কয়টি?

    S0: [S′ → ·S, 0] (শুরু), [S → ·SS, 0], [S → ·a, 0] (predict).

    S1: [S → a·, 0] (scan); [S′ → S·, 0], [S → S·S, 0] (complete); [S → ·SS, 1], [S → ·a, 1] (predict). মোট ৫টি।

    S2: [S → a·, 1] (scan); complete থেকে [S → SS·, 0], [S → S·S, 1]; তারপর [S → SS·, 0] সম্পূর্ণ বলে [S′ → S·, 0], [S → S·S, 0]; predict থেকে [S → ·SS, 2], [S → ·a, 2]. মোট ৭টি।

    S3: [S → a·, 2] (scan); complete থেকে [S → SS·, 1], [S → SS·, 0], [S → S·S, 2]; তারপর [S → SS·, 1]-এর complete-এ [S → S·S, 1] আর আবার [S → SS·, 0]-এর চেষ্টা, যা আগেই আছে; [S → SS·, 0]-এর complete-এ [S′ → S·, 0], [S → S·S, 0]; predict থেকে [S → ·SS, 3], [S → ·a, 3]. মোট ৯টি।

    [S → SS·, 0] ∈ S3 দুটি উপায়ে তৈরি হয়: প্রথম S “a” আর দ্বিতীয় S “aa” (a∣aa), অথবা প্রথম S “aa” আর দ্বিতীয় “a” (aa∣a). তাই গাছ ২টি: S(a, S(a, a)) আর S(S(a, a), a). মোট item ২৪টি; এটি scratch-এ earley_chart.py-র কোডে grammar আর input বদলে চালিয়ে মেলানো হয়েছে।

  2. প্রমাণে ভুল খুঁজুন: একজন লিখলেন, “Sk-এ বড়জোর |D|(k + 1)টি item, তাই chart-এ O(n2)টি item. প্রতিটি item-এ একটি ক্রিয়া চলে, তাই Earley-র সময় সবসময় O(n2).” প্রথম বাক্যটি প্রমাণ করুন, আর দ্বিতীয় বাক্যের ভুল দেখান।
    1. Sk-এর প্রতিটি item [A → α·β, j] একটি (বিন্দুসহ নিয়ম, origin) জোড়া। — সংজ্ঞা
    2. বিন্দুসহ নিয়ম |D|টি, আর origin j-এর মান 0 ≤ j ≤ k, অর্থাৎ k + 1টি। — উপপাদ্য ৪.১-এ j ≤ k
    3. একটি set-এ একই item দুবার থাকে না, তাই |Sk| ≤ |D|(k + 1). সব set মিলিয়ে ∑k=0n |D|(k + 1) = |D|(n + 1)(n + 2)/2 = O(n2). ∎ — যোগফল

    ভুল: “প্রতিটি item-এ স্থির কাজ” মিথ্যা। Complete-এ [B → γ·, i] ∈ Sk-এর জন্য Si-এর সব item দেখতে হয়, যা O(n). তাই একটি set-এ O(n)টি item × O(n) কাজ, আর মোট O(n3). সত্যিকারের run-এ ambiguous grammar-এ item n2-এর মাপে বাড়লেও সময় প্রতি দ্বিগুণে প্রায় ৮ গুণের দিকে গিয়েছে। তবে unambiguous grammar-এ বাক্যটির উপসংহার সত্য, অন্য যুক্তিতে (উপপাদ্য ৪.২-এর ৩)।

  3. Grammar নকশা: বাজারঘরের খোঁজের ঘরের জন্য প্রথম খসড়া grammar: C → C OR C ∣ C AND C ∣ p ∣ q ∣ r ∣ s (p, q, r, s চারটি শর্ত, যেমন amount > 500). (ক) “p OR q AND r OR s”-এর কয়টি parse tree? (খ) একটি unambiguous grammar নকশা করুন, যেখানে AND, OR-এর চেয়ে আগে হয় আর দুটিই বাঁ দিক থেকে জোড়ে। (গ) নতুন grammar-এ একই input-এর কয়টি গাছ?

    (ক) তিনটি operator, আর খসড়া grammar operator-এর ধরন আলাদা করে না, তাই গাছ C3 = 5টি: যেকোনো একটি operator সবার শেষে, তার দুই পাশে বাকিদের সব বিন্যাস।

    (খ) পর্ব ২৭-এর স্তরভাগ: C → C OR T ∣ T, T → T AND F ∣ F, F → p ∣ q ∣ r ∣ s ∣ ( C ). নিচের স্তর (AND) আগে জোড়ে, আর বাঁ-recursive নিয়ম বাঁ দিক থেকে জোড়া নিশ্চিত করে। Earley left recursion-এ আটকায় না, তাই এই grammar সরাসরি lark-এ চলে।

    (গ) গাছ ১টি: (p OR (q AND r)) OR s. Scratch-এ earley_count.py-র গোনার কোডে দুটি grammar বসিয়ে ঠিক 5 আর 1 এসেছে।

  4. Output অনুমান: earley_count.py ব্লকের শেষ loop range(1, 8) বদলে range(1, 9) করা হলো। নতুন শেষ লাইনে trees-এর মান কত হবে? আর earley_epsilon.py-তে input ["x"]-এর বদলে খালি list [] দিলে দুই রূপের উত্তর কী?

    নতুন লাইন “8 operators, n=17”, আর trees = C8 = C(16, 8)/9 = 12870/9 = 1430. Chart items 236 (scratch-এ চালিয়ে মেলানো); আগের লাইনের ১৯০ থেকে মাত্র ৪৬ বেশি, অথচ গাছ ৪২৯ থেকে ১৪৩০।

    খালি input-এ দুই রূপই False দেবে, আর এটিই সঠিক, কারণ L(G) = {x}, ε নয়। সংশোধিত রূপে [B → A·x, 0] আসে, কিন্তু x পড়ার মতো token নেই, তাই [S′ → S·, 0] তৈরি হয় না। শিক্ষা: ε-সংশোধন নতুন string গ্রহণ করায় না, শুধু হারানো item ফিরিয়ে আনে।

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

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

ক্রমএকটি CFG আর input w = w1⋯wn-এ Earley parser-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. নতুন start S′ → S যোগ করে S0-এ [S′ → ·S, 0] রাখা
  2. S0-এ predict আর complete চালানো, যতক্ষণ নতুন item আসে
  3. w1 পড়ে scan করে S1-এর প্রথম item বানানো
  4. প্রতিটি পরের set-এ একই কাজ, শেষ token পর্যন্ত
  5. Sn-এ [S′ → S·, 0] আছে কি না দেখে গ্রহণ বা প্রত্যাখ্যান
  6. গৃহীত হলে সম্পূর্ণ item থেকে parse forest বা একটি গাছ পড়া

Grammar E → E + E ∣ id, input “id + id”. Earley item [E → E + ·E, 0] ∈ S2-এর অর্থ কী?

  • পুরো input একটি E হিসেবে গৃহীত হয়েছে
  • সীমানা ০ থেকে শুরু হওয়া E + E-র “E +” অংশ প্রথম দুটি token পড়েছে, এখন একটি E প্রত্যাশিত
  • E-র নিয়মটি সীমানা ২-তে শুরু হয়েছে
  • Input-এ দ্বিতীয় token-এ ভুল আছে

দৈর্ঘ্য n-এর input-এ, একটি স্থির grammar নিয়ে, Earley algorithm-এর সময় সম্পর্কে কোন কথাটি সঠিক?

  • সব grammar-এ O(n2), কারণ chart-এ O(n2)টি item
  • সব grammar-এ সবসময় Θ(n3), CYK-এর মতো
  • সবচেয়ে খারাপ O(n3), unambiguous grammar-এ O(n2), অনেক LR grammar-এ O(n)
  • Ambiguous grammar-এ exponential, কারণ গাছ exponential সংখ্যক

Grammar E → E + E ∣ id-এ Earley parser S0-এ অসীম loop-এ পড়ে না কেন, যদিও নিয়মটি left-recursive?

  • একই item একটি set-এ একবারই যোগ হয়, আর সম্ভাব্য item-এর সংখ্যা সসীম
  • Earley আগে স্বয়ংক্রিয়ভাবে left recursion দূর করে
  • Predict প্রতিবার একটি token পড়ে, তাই input শেষ হলে থামে
  • একটি নির্দিষ্ট গভীরতার পর recursion কেটে দেওয়া হয়

Grammar E → E + E ∣ E ∗ E ∣ id-এ “id + id ∗ id + id ∗ id” (চারটি operator)-এর parse tree কয়টি?

  • ২টি
  • ৫টি
  • ২৪টি
  • ১৪টি

একটি GLR parser LR টেবিলের একটি ঘরে shift/reduce conflict পেলে কী করে?

  • সবসময় shift বেছে নেয়, dangling else-এর মতো
  • Stack ভাগ করে দুটি কাজই চালায়, আর অভিন্ন অংশ graph-structured stack-এ ভাগাভাগি করে
  • পুরো stack-এর একটি সম্পূর্ণ কপি বানিয়ে দুটি আলাদা parser চালায়
  • ভুলের বার্তা দিয়ে থেমে যায়

Grammar S → A B, A → ε, B → A x (L = {x})। ε-এর বিশেষ ব্যবস্থা ছাড়া একটি সরল Earley parser “x”-এ ভুল করে। Aycock–Horspool-এর সংশোধনটি কোনটি?

  • Parse করার আগে সব ε-নিয়ম মুছে ফেলা
  • প্রতিটি set শেষে আবার শুরু থেকে সব item প্রক্রিয়া করা
  • Predict-এর সময় বিন্দুর পরের variable nullable হলে বিন্দু সেটি পেরিয়ে আরেকটি item যোগ করা
  • [A → ·, k] ধরনের item কখনো set-এ না রাখা

শব্দকোষ

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

মনে রাখুন

  1. Earley item [A → α·β, j] ∈ Sk: α টুকরো wj+1⋯wk তৈরি করে, আর সীমানা j-তে A শুরু হওয়া সম্ভব। গ্রহণ ⇔ [S′ → S·, 0] ∈ Sn.
  2. তিন ক্রিয়া: predict (variable-এর নিয়ম যোগ), scan (token মেলানো), complete (সম্পূর্ণ variable দিয়ে অপেক্ষারতদের এগোনো); একই item একবারই, তাই left recursion আর ambiguity-তে loop নেই।
  3. খরচ: item O(n2), সময় O(n3); unambiguous-এ O(n2), অনেক LR grammar-এ O(n). ε-নিয়মে nullable variable-এর জন্য predict-এ বিন্দু সরানো (Aycock–Horspool).
  4. গাছ exponential (Catalan), কিন্তু shared packed parse forest polynomial: symbol node (X, i, k) আর তার নিচে বিকল্প ভাঙনের packed node.
  5. GLR: LR টেবিলে conflict-এ stack ভাগ, graph-structured stack-এ ভাগাভাগি আর মিলন; প্রায়-LR grammar-এ প্রায় linear. সাধারণ parser ক্ষমতা দেয়, LL/LR নিশ্চয়তা দেয়।

পরের পর্বে: পর্ব ৪২-এ ভালো grammar নকশা: EBNF, precedence climbing আর Pratt parsing, ambiguity আর conflict এড়ানো, ভুলের বার্তা আর error recovery, আর বাজারঘরের order-query ভাষার দ্বিতীয় সংস্করণ নকশা।

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

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