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

Bottom-up parsing — shift-reduce, LR(0), SLR আর LALR

Bottom-Up Parsing — Shift-Reduce, Handles, LR(0) Items, SLR(1), LR(1) and LALR(1) Tables, Conflicts and Precedence

Taught in Bangla, this lesson explains bottom-up parsing: shifting tokens, reducing handles and producing a rightmost derivation in reverse. It builds the LR(0) item-set automaton over viable prefixes, then SLR(1), LR(1) and LALR(1) tables. It covers shift/reduce and reduce/reduce conflicts, precedence declarations and dangling else. In-page Python (Pyodide) builds the tables, and a real PLY 3.11 run reports 9 shift/reduce conflicts on an ambiguous grammar and wrong results until precedence is declared.

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

  • Shift, reduce, handle আর viable prefix-এর সংজ্ঞা, আর কেন bottom-up parse উল্টো rightmost derivation
  • LR(0) item, closure আর goto দিয়ে item-set-এর DFA হাতে বানানো, আর এটি যে subset construction-এরই রূপ তার প্রমাণের রূপরেখা
  • SLR(1) parsing table ভরা আর stack ধরে id+id∗id-এর পুরো shift-reduce parse লেখা
  • LR(1) আর LALR(1)-এর ভাবনা, চার শ্রেণির ক্ষমতার ক্রম, আর প্রতিটি ফাঁকের যাচাই করা উদাহরণ
  • Conflict পড়া আর মেটানো: precedence, associativity, dangling else; PLY আর lark-এর আসল বার্তা বোঝা

১ · Bottom-up-এর ভাবনা — shift, reduce আর handle

পর্ব ৩৮-এ top-down parser দেখেছেন: start symbol থেকে শুরু করে, পরের token দেখে কোন নিয়ম খুলবেন তা আগেভাগে অনুমান করা। এই পর্বে উল্টো পথ। Parser আগে token পড়ে, তারপর দেখে পড়া অংশটি কোন নিয়মের ডান দিকের সঙ্গে মেলে। মিললে সেই অংশকে নিয়মের বাঁ দিকের variable দিয়ে বদলায়। এভাবে পাতা থেকে parse tree ওপরে ওঠে, যতক্ষণ না পুরো input একটি start symbol-এ গুটিয়ে যায়।

বাজারঘরের গুদামে একজন প্যাকার একটি টেবিলে বসে আছেন। কনভেয়রে একটি একটি করে জিনিস আসে। তিনি প্রতিটি জিনিস টেবিলের স্তূপের ওপরে রাখেন (shift). স্তূপের ওপরের কয়েকটি জিনিস যদি একটি প্যাকেটের তালিকার সঙ্গে হুবহু মেলে, যেমন “চাল + ডাল + তেল = বাজারের ব্যাগ”, তিনি সেগুলো তুলে একটি ব্যাগে বাঁধেন আর ব্যাগটি স্তূপে রাখেন (reduce). কঠিন প্রশ্নটি হলো সময় বেছে নেওয়া: এখনই বাঁধবেন, নাকি আরেকটি জিনিস আসার অপেক্ষা করবেন, কারণ হয়তো সেটি দিয়ে বড় একটি প্যাকেট হবে? LR parsing-এর পুরো তত্ত্ব এই একটি প্রশ্নের উত্তর।

পুরো পর্ব জুড়ে পর্ব ২৫-এর স্তরভাগ করা expression grammar ব্যবহার হবে, নিয়মগুলোর নম্বরসহ:

(1) E → E+T (2) E → T (3) T → T∗F (4) T → F (5) F → (E) (6) F → id

id+id∗id-এর জন্য shift-reduce parser যা করে, তা সংক্ষেপে: id তুলুন, F-এ গুটান, T-তে গুটান, E-তে গুটান; তারপর + আর id তুলুন, id-কে F, F-কে T-তে গুটান। এবার stack-এ E + T, আর পরের token ∗. এখানে E + T-কে E-তে গুটানো ভুল হবে, কারণ তাহলে গুণের আগে যোগ হয়ে যায়। ঠিক কাজ হলো ∗ তোলা। শেষে T ∗ F → T, তারপর E + T → E. এবার গুটানোগুলোর ক্রমটি পর্ব ২৬-এর rightmost derivation-এর সঙ্গে মেলান:

E ⇒rm E+T ⇒rm E+T∗F ⇒rm E+T∗id ⇒rm E+F∗id ⇒rm E+id∗id ⇒rm T+id∗id ⇒rm F+id∗id ⇒rm id+id∗id

ডান থেকে বাঁয়ে পড়লে প্রতিটি ধাপ ঠিক একটি reduce. Bottom-up parser একটি rightmost derivation-কে শেষ থেকে শুরুর দিকে পুনর্গঠন করে। LR নামের অর্থও এটিই: input বাঁ থেকে ডানে পড়া (Left to right), আর Rightmost derivation বানানো। এবার সংজ্ঞাগুলো নিখুঁত করা যাক। একটি CFG G = (V, Σ, R, S)-এ start symbol থেকে rightmost derivation-এ আসা প্রতিটি sentential form-কে right-sentential form বলে।

সংজ্ঞা ১.১ (handle আর viable prefix)

ধরুন S ⇒rm∗ αAw ⇒rm αβw, যেখানে A → β ∈ R আর w ∈ Σ∗ (শুধু terminal). তাহলে right-sentential form γ = αβw-এর handle হলো নিয়ম A → β আর α-এর ঠিক পরের অবস্থান। γ-এর যে prefix-গুলো αβ-এর prefix, অর্থাৎ handle-এর ডান প্রান্ত পেরোয় না, সেগুলো viable prefix.

w-এ শুধু terminal থাকার শর্তটিই মূল কথা। Rightmost derivation-এ সবসময় সবচেয়ে ডানের variable বদলায়, তাই handle-এর ডানে কখনো variable থাকে না; সবটাই এখনো-না-পড়া input. এ কারণেই parser-এর কাছে handle সবসময় stack-এর একেবারে ওপরে আসে, কখনো stack-এর ভেতরে চাপা পড়ে না। E + T ∗ id-এ handle হলো শেষের id (নিয়ম F → id), কারণ ওপরের derivation-এ E+T∗F ⇒rm E+T∗id. লক্ষ করুন, E + T নিজেও একটি নিয়মের ডান দিক, তবু এখানে handle নয়: তাকে গুটালে E ∗ id আসে, যা কোনো right-sentential form নয়।

উপপাদ্য ১.২ (shift-reduce আর rightmost derivation)

G unambiguous হলে প্রতিটি right-sentential form-এর ঠিক একটি handle আছে। যে shift-reduce parser প্রতিবার handle-ই reduce করে, সে input w ∈ L(G)-এর একমাত্র rightmost derivation উল্টো ক্রমে তৈরি করে।

প্রমাণের রূপরেখা:

  1. γ-এর দুটি আলাদা handle থাকলে S থেকে γ পর্যন্ত দুটি আলাদা rightmost derivation থাকত, শেষ ধাপে আলাদা। — handle-এর সংজ্ঞা
  2. γ থেকে w পর্যন্ত যেকোনো rightmost derivation জুড়লে w-এর দুটি আলাদা rightmost derivation, তাই দুটি parse tree. G unambiguous বলে তা অসম্ভব। — পর্ব ২৬-এর গাছ ⇔ rightmost derivation সংযোগ
  3. Parser w থেকে শুরু করে প্রতিবার একমাত্র handle গুটায়; প্রতিটি গুটানো rightmost derivation-এর একটি ধাপ উল্টো দিকে। শেষে S পেলে ধাপগুলো উল্টো ক্রমে পড়লেই derivation. ∎

উপপাদ্যটি বলে কী করতে হবে, কিন্তু কীভাবে handle চিনবেন তা বলে না। Stack-এর পুরো বিষয়বস্তু প্রতিবার নতুন করে পরীক্ষা করা ব্যয়বহুল। Donald Knuth ১৯৬৫ সালের “On the translation of languages from left to right” প্রবন্ধে এর একটি সুন্দর উত্তর দেন, যা পরের অংশের বিষয়।

২ · LR(0) item আর item-set-এর automaton

Parser যখন একটি নিয়মের মাঝপথে, তখন তার জানা দরকার নিয়মটির কতটুকু ইতিমধ্যে stack-এ এসেছে। এই তথ্য রাখার উপায় একটি LR(0) item: নিয়মের ডান দিকের কোথাও একটি বিন্দু। [E → E+·T] মানে “E আর + দেখা হয়ে গেছে, এখন একটি T আসার কথা”. [E → E+T·]-এ বিন্দু শেষে, অর্থাৎ পুরো ডান দিক stack-এ, এখন গুটানো যায়; এমন item-কে completed item বলে। প্রতিটি নিয়ম A → β থেকে |β| + 1টি item হয়।

শুরুতে grammar-এ একটি নতুন start symbol S′ আর নিয়ম S′ → S যোগ করা হয়; একে augmented grammar বলে। কারণ সহজ: [S′ → S·] দেখলে parser নিশ্চিত হয় পুরো input একটি S-এ গুটিয়েছে, আর পরের চিহ্ন end marker $ হলে গ্রহণ করে। দুটি ক্রিয়া item-set বানায়:

সংজ্ঞা ২.১ (closure আর goto)

closure(I): I-এর সব item নিন। কোনো item-এ বিন্দুর ঠিক পরে একটি variable B থাকলে, B-এর প্রতিটি নিয়মের জন্য [B → ·γ] যোগ করুন। নতুন কিছু না আসা পর্যন্ত চালিয়ে যান।

goto(I, X): I-এর যেসব item-এ বিন্দুর পরে চিহ্ন X, তাদের বিন্দু X-এর ওপারে সরান, তারপর closure নিন।

Canonical LR(0) collection: closure({[S′ → ·S]}) থেকে শুরু করে প্রতিটি নতুন set-এ প্রতিটি চিহ্নের goto নিন, যতক্ষণ নতুন set আসে।

ছোট একটি grammar দিয়ে পুরো নির্মাণটি হাতে করা যাক: (1) E → T+E, (2) E → T, (3) T → id. এটি “id + id + ⋯ + id” language তৈরি করে, যোগ ডান দিকে recursive. নিচের stepper-এ প্রতিটি ধাপে একটি closure বা goto.

এই ধাপের কাজ
ক্রিয়া
মোট state
  1. Augment. নতুন নিয়ম S′ → E যোগ হলো। প্রথম state-এর বীজ (kernel) একটিমাত্র item [S′ → ·E]: এখনো কিছু পড়া হয়নি, একটি পুরো E আসার কথা।
  2. closure(I0). বিন্দুর পরে E, তাই E-এর দুই নিয়ম [E → ·T+E] আর [E → ·T] যোগ হলো। এবার বিন্দুর পরে T, তাই [T → ·id]. id terminal, closure থামল। I0-তে ৪টি item.
  3. goto(I0, E). শুধু [S′ → ·E]-এ বিন্দুর পরে E; বিন্দু সরালে [S′ → E·]. এটিই accept-এর item, তাই I1-এ পরের চিহ্ন $ হলে গ্রহণ।
  4. goto(I0, T). দুটি item-এ বিন্দুর পরে T: সরালে [E → T·+E] আর [E → T·]. বিন্দুর পরে variable নেই, closure কিছু যোগ করে না। এটি I2.
  5. goto(I0, id). [T → ·id] থেকে [T → id·], নতুন state I3. I0-এর তিনটি চিহ্ন (E, T, id) শেষ।
  6. goto(I2, +). [E → T·+E] থেকে [E → T+·E]. বিন্দুর পরে E, তাই closure আবার E আর T-এর নিয়মগুলো আনে। এটি I4, যার ৪টি item.
  7. I4-এর তিন চিহ্ন। E-তে নতুন I5 = {[E → T+E·]}. T-তে আবার {[E → T·+E], [E → T·]}, যা হুবহু I2; নতুন state নয়, শুধু একটি তীর। id-তে I3. নতুন কিছু আসে না: ৬টি state, ৭টি তীর।
  8. দ্বন্দ্ব পরীক্ষা। I2-তে completed item [E → T·] আছে, আবার + পেলে shift-ও আছে। কোনো lookahead না দেখলে (LR(0)) এটি একটি shift/reduce conflict. FOLLOW(E) = {$}, তাই SLR নিয়মে শুধু $ এলে reduce, + এলে shift: দ্বন্দ্ব মিটে গেল।

এই ছয়টি set আর তাদের মধ্যের তীরগুলো মিলে একটি DFA. নিচের ছবিতে পুরোটা। প্রতিটি বাক্সে একটি state-এর সব item, আর তীরের গায়ে যে চিহ্ন পড়লে (বা reduce-এর পরে যে variable পেলে) সেই state-এ যেতে হয়।

ছোট grammar-এর LR(0) automaton

Grammar: E → T+E ∣ T, T → id. নীল: সাধারণ state. সবুজ দুই-দাগ: accept-এর state. হলুদ লাল-দাগ: LR(0)-এ দ্বন্দ্বের state, যা SLR মেটায়।

LR(0) automaton of E → T+E | T, T → id I0S′ → ·EE → ·T+EE → ·TT → ·id I1 acceptS′ → E· I2 দ্বন্দ্বE → T·+EE → T· I3T → id· I4E → T+·EE → ·T+EE → ·TT → ·id I5E → T+E· শুরু ETid +T idE
ছবি ৩৯.১ — LR(0) item-set-এর DFA. শুরু থেকে কোনো পথে চলার চিহ্নগুলো, যেমন T + T, সবসময় একটি viable prefix; পথের শেষ state বলে stack-এর ওপরে handle তৈরি কি না।

এই নির্মাণ দেখে মনে হতে পারে নতুন কৌশল, কিন্তু এটি আপনার পরিচিত। পর্ব ১১-এর ε-NFA আর পর্ব ১০-এর subset construction মনে করুন। ধরুন প্রতিটি item একটি NFA state. [A → α·Xβ] থেকে X চিহ্নে [A → αX·β]-তে তীর, আর বিন্দুর পরে variable B থাকলে প্রতিটি [B → ·γ]-তে একটি ε-তীর। তাহলে closure হলো ঠিক ε-closure, আর goto হলো “চিহ্ন পড়ে সরানো, তারপর ε-closure”. Canonical collection এই item-NFA-র subset construction, শুধু পৌঁছানো যায় এমন subset নিয়ে।

উপপাদ্য ২.২ (viable prefix regular, Knuth ১৯৬৫)

যেকোনো CFG G-এর সব viable prefix-এর set একটি regular language. বিশেষ করে, শুরুর state থেকে চিহ্ন-ক্রম γ পড়ে LR(0) automaton কোনো state-এ পৌঁছায় ⇔ γ একটি viable prefix, আর সেই state-এ [A → β·α′] থাকে ⇔ কোনো rightmost derivation-এ γ-এর শেষ অংশ β, আর নিয়মটি A → βα′.

প্রমাণের রূপরেখা: item-NFA-তে [S′ → ·S] থেকে γ পড়ে [A → β·α′]-এ পৌঁছানো যায় ⇔ S′ ⇒rm∗ δAw ⇒rm δβα′w আর γ = δβ. দুই দিকই derivation-এর দৈর্ঘ্যের ওপর induction: ε-তীর মানে “একটি variable খোলা”, আর চিহ্নের তীর মানে “ডান দিকের একটি চিহ্ন পেরোনো”. NFA-টি সসীম (item-এর সংখ্যা সসীম), তাই এর language regular, আর subset construction সমান একটি DFA দেয়। পূর্ণ প্রমাণ Hopcroft–Motwani–Ullman বা Aho–Sethi–Ullman (Dragon book)-এর LR অধ্যায়ে। ∎

এটি তত্ত্বের একটি চমৎকার মুহূর্ত। Parser-এর stack সীমাহীন, তাই পুরো parser একটি PDA, কিন্তু “এখন কী করব” প্রশ্নের উত্তর দেয় একটি সসীম যন্ত্র, একটি DFA. নিচের Python ব্লক expression grammar-এর পুরো canonical collection বানায় আর প্রতিটি state-এর kernel (বীজ) item ছাপে: [S′ → ·E] আর যেসব item-এ বিন্দু শুরুতে নেই। বাকিগুলো closure থেকে আবার পাওয়া যায়।

# LR(0) items, closure, goto and the canonical collection (E/T/F grammar)
G = [("S'", ("E",)), ("E", ("E", "+", "T")), ("E", ("T",)),
     ("T", ("T", "*", "F")), ("T", ("F",)), ("F", ("(", "E", ")")), ("F", ("id",))]
NT = {A for A, _ in G}

def closure(items):                     # item = (rule number, dot position)
    items, todo = set(items), list(items)
    while todo:
        r, d = todo.pop(); rhs = G[r][1]
        if d < len(rhs) and rhs[d] in NT:   # dot before a variable B: add B -> .γ
            for j, (A, _) in enumerate(G):
                if A == rhs[d] and (j, 0) not in items:
                    items.add((j, 0)); todo.append((j, 0))
    return frozenset(items)
def goto(I, X):                         # move the dot over X, then close
    return closure({(r, d + 1) for r, d in I if d < len(G[r][1]) and G[r][1][d] == X})
def show(item):
    (A, rhs), d = G[item[0]], item[1]
    return A + " -> " + " ".join(rhs[:d] + ("·",) + rhs[d:])

states, edges = [closure({(0, 0)})], {}
for I in states:                        # the list grows while we walk it
    for X in sorted({G[r][1][d] for r, d in I if d < len(G[r][1])}):
        J = goto(I, X)
        if J not in states: states.append(J)
        edges[states.index(I), X] = states.index(J)

for i, I in enumerate(states):
    kernel = [show(it) for it in sorted(I) if it[1] > 0 or it[0] == 0]
    done = [it for it in I if it[1] == len(G[it[0]][1]) and it[0] != 0]
    shifts = [X for (s, X) in edges if s == i and X not in NT]
    flag = "   <- LR(0) conflict" if done and (shifts or len(done) > 1) else ""
    print(f"I{i}: " + " ; ".join(kernel) + flag)
print(len(states), "states,", len(edges), "goto edges")

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

I0: S' -> · E
I1: F -> ( · E )
I2: S' -> E · ; E -> E · + T
I3: T -> F ·
I4: E -> T · ; T -> T · * F   <- LR(0) conflict
I5: F -> id ·
I6: E -> E · + T ; F -> ( E · )
I7: E -> E + · T
I8: T -> T * · F
I9: F -> ( E ) ·
I10: E -> E + T · ; T -> T · * F   <- LR(0) conflict
I11: T -> T * F ·
12 states, 22 goto edges

১২টি state, ঠিক Dragon book-এর সংখ্যা; শুধু নম্বরের ক্রম আলাদা, কারণ কোডটি প্রতিটি state-এর চিহ্নগুলো ASCII ক্রমে ঘোরে। দুটি state-এ LR(0) দ্বন্দ্ব: I4-এ [E → T·] গুটাতে চায়, আবার [T → T·∗F] ∗ তুলতে চায়; I10-এ একই ঘটনা [E → E+T·]-এর সঙ্গে। lookahead ছাড়া parser জানে না id+id-এর পরে ∗ আসছে কি না। এখানে [S′ → E·] কে আমরা শুধু $ দেখে accept ধরেছি, যা প্রচলিত রীতি; তাই I2 চিহ্নিত হয়নি। (কিছু বই LR(0)-এর কঠোর সংজ্ঞায় I2-কেও দ্বন্দ্ব গোনে।) G বদলে নিজের grammar দিয়ে চালিয়ে দেখুন, যেমন S → ( S ) ∣ x.

৩ · Parsing table আর shift-reduce parse

DFA হাতে পেলে parser বানানো যান্ত্রিক। Stack-এ চিহ্নের বদলে DFA-র state রাখা হয়: প্রতিটি state নিজেই মনে রাখে নিচে কোন viable prefix আছে, তাই প্রতিবার DFA-কে শুরু থেকে চালাতে হয় না। দুটি টেবিল লাগে, একসঙ্গে যাদের নাম LR parsing table.

সংজ্ঞা ৩.১ (SLR(1) টেবিল)

ACTION[i, a], a terminal বা $: (ক) DFA-তে Ii থেকে a-তে Ij-এ তীর থাকলে “sj” (shift করে state j-তে যান)। (খ) Ii-তে completed item [A → β·] থাকলে আর A ≠ S′ হলে, প্রতিটি a ∈ FOLLOW(A)-এর জন্য “rk” (নিয়ম k = A → β দিয়ে reduce). (গ) [S′ → S·] ∈ Ii হলে ACTION[i, $] = accept. বাকি ঘর error.

GOTO[i, A], A variable: DFA-তে Ii থেকে A-তে যে state. কোনো ঘরে দুটি কাজ এলে grammar-টি SLR(1) নয়।

এখানে FOLLOW(A) মানে কোনো sentential form-এ A-এর ঠিক পরে যে terminal বসতে পারে তাদের set, আর start symbol-এর FOLLOW-এ সবসময় $. এর হিসাব (fixpoint দিয়ে) পর্ব ৩৮-এর বিষয়; এখানে শুধু ফল লাগবে। Expression grammar-এ FOLLOW(E) = {+, ), $} আর FOLLOW(T) = FOLLOW(F) = {+, ∗, ), $}. যুক্তিটি সহজ: reduce করে A বানালে A-এর পরে যে token আসবে, তা অবশ্যই FOLLOW(A)-তে থাকতে হবে; নইলে গুটানো ভুল।

Parser-এর loop খুব ছোট। Stack-এর ওপরে state s, পরের token a. ACTION[s, a] = sj হলে a খরচ করে j push করুন। rk হলে, নিয়ম k = A → β-এর জন্য |β|টি state pop করুন, তারপর নতুন ওপরের state t থেকে GOTO[t, A] push করুন। accept-এ থামুন, error-এ ভুল জানান। নিচের ব্লক আগের ব্লকের state-গুলো থেকে টেবিল বানায় আর id+id∗id parse করে (দুটি ব্লক একই namespace ভাগ করে, তাই আগে ওপরেরটি চালান)।

# SLR(1) table from the LR(0) states above, then a shift-reduce parse
FIRST = {A: set() for A in NT}; FOLLOW = {A: set() for A in NT}; FOLLOW["S'"] = {"$"}
for _ in range(len(G)):                 # simple fixpoint; this grammar has no ε-rules
    for A, rhs in G:
        FIRST[A] |= FIRST[rhs[0]] if rhs[0] in NT else {rhs[0]}
        for i, X in enumerate(rhs):
            if X in NT:
                nxt = rhs[i + 1] if i + 1 < len(rhs) else None
                FOLLOW[X] |= FOLLOW[A] if nxt is None else FIRST.get(nxt, {nxt})
ACTION, GOTO = {}, {}
for (s, X), t in edges.items():
    if X in NT: GOTO[s, X] = t
    else: ACTION[s, X] = f"s{t}"
for s, I in enumerate(states):
    for r, d in I:
        if d == len(G[r][1]):           # completed item: reduce on FOLLOW(A)
            for a in (["$"] if r == 0 else FOLLOW[G[r][0]]):
                new = "acc" if r == 0 else f"r{r}"
                if ACTION.get((s, a), new) != new: print("CONFLICT", s, a)
                ACTION[s, a] = new
print("FOLLOW:", {A: sorted(FOLLOW[A]) for A in "ETF"})

def parse(tokens):
    stack, syms, rest = [0], [], tokens + ["$"]
    while True:
        act = ACTION.get((stack[-1], rest[0]), "error")
        print(f"{' '.join(map(str, stack)):15} {' '.join(syms):10} {' '.join(rest):12} {act}")
        if act in ("acc", "error"): return act
        if act[0] == "s":
            stack.append(int(act[1:])); syms.append(rest.pop(0))
        else:
            A, rhs = G[int(act[1:])]
            del stack[-len(rhs):], syms[-len(rhs):]
            stack.append(GOTO[stack[-1], A]); syms.append(A)
parse(["id", "+", "id", "*", "id"])

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

FOLLOW: {'E': ['$', ')', '+'], 'T': ['$', ')', '*', '+'], 'F': ['$', ')', '*', '+']}
0                          id + id * id $ s5
0 5             id         + id * id $  r6
0 3             F          + id * id $  r4
0 4             T          + id * id $  r2
0 2             E          + id * id $  s7
0 2 7           E +        id * id $    s5
0 2 7 5         E + id     * id $       r6
0 2 7 3         E + F      * id $       r4
0 2 7 10        E + T      * id $       s8
0 2 7 10 8      E + T *    id $         s5
0 2 7 10 8 5    E + T * id $            r6
0 2 7 10 8 11   E + T * F  $            r3
0 2 7 10        E + T      $            r1
0 2             E          $            acc

“CONFLICT” একবারও ছাপা হয়নি: FOLLOW দিয়ে I4 আর I10-এর দ্বন্দ্ব মিটেছে, কারণ ∗ ∉ FOLLOW(E). প্রতিটি সারি একটি কাজ: বাঁয়ে state-এর stack, মাঝে সমান্তরাল চিহ্ন (শুধু পড়ার সুবিধার জন্য), তারপর বাকি input আর ACTION-এর ঘর। মোট ৫টি shift (প্রতিটি token একবার) আর ৮টি reduce (parse tree-র ভেতরের node), তারপর accept. পুরো টেবিলটি নিচে; পরের stepper এই সারিগুলো একটি একটি করে খোলে।

stateid+∗()$ETF
0s5s1243
1s5s1643
2s7acc
3r4r4r4r4
4r2s8r2r2
5r6r6r6r6
6s7s9
7s5s1103
8s5s111
9r5r5r5r5
10r1s8r1r1
11r3r3r3r3
Parser-এর অবস্থা
state stack
চিহ্ন
বাকি input
ACTION
  1. শুরু। Stack-এ শুধু state 0, পরের token id. ACTION[0, id] = s5: id তুলুন, state 5-এ যান।
  2. প্রথম reduce. State 5 = {[F → id·]}, পরের token + ∈ FOLLOW(F). ACTION[5, +] = r6: একটি state pop, ওপরে 0, GOTO[0, F] = 3.
  3. F থেকে T. ACTION[3, +] = r4 (T → F). Pop করে 0, GOTO[0, T] = 4.
  4. প্রথম আসল সিদ্ধান্ত। State 4-এ দুই item: [E → T·] আর [T → T·∗F]. পরের token +, যা FOLLOW(E)-তে, তাই r2: E → T. GOTO[0, E] = 2.
  5. যোগ চিহ্ন। ACTION[2, +] = s7. Stack-এর ওপরে এখন viable prefix E +, state 7 = {[E → E+·T], …}.
  6. দ্বিতীয় id. ACTION[7, id] = s5. পরের token ∗.
  7. আবার F → id. ACTION[5, ∗] = r6. Pop করে ওপরে 7, GOTO[7, F] = 3. লক্ষ করুন, একই নিয়ম এবার অন্য state-এর ওপরে, তাই GOTO আলাদা হতে পারত।
  8. T → F. ACTION[3, ∗] = r4, GOTO[7, T] = 10. এখন stack-এ E + T, আর পরের token ∗.
  9. Shift, reduce নয়। State 10-এ [E → E+T·] গুটাতে চাইত, কিন্তু ∗ ∉ FOLLOW(E). ACTION[10, ∗] = s8. গুণ আগে হবে, এই সিদ্ধান্তটি টেবিল থেকেই এল।
  10. তৃতীয় id. ACTION[8, id] = s5. এখন বাকি শুধু $.
  11. F → id. ACTION[5, $] = r6. ওপরে 8, GOTO[8, F] = 11.
  12. গুণ গুটানো। State 11 = {[T → T∗F·]}, ACTION[11, $] = r3. তিনটি state (10, 8, 11) pop, ওপরে 7, GOTO[7, T] = 10.
  13. যোগ গুটানো। ACTION[10, $] = r1 (E → E+T). তিনটি pop, ওপরে 0, GOTO[0, E] = 2.
  14. গ্রহণ। ACTION[2, $] = accept. ডানের বাক্সের ক্রমটি নিচ থেকে ওপরে পড়ুন: এটিই অংশ ১-এর rightmost derivation, উল্টো দিক থেকে।
উপপাদ্য ৩.২ (linear সময়)

G-তে ε-নিয়ম বা A ⇒+ A ধরনের unit-চক্র না থাকলে, SLR, LALR বা LR(1) টেবিলে conflict না থাকলে, দৈর্ঘ্য n-এর input-এ parser মোট O(n) কাজ করে: ঠিক n টি shift, আর reduce-এর সংখ্যা parse tree-র ভেতরের node-এর সংখ্যা, যা O(n).

প্রমাণের রূপরেখা: প্রতিটি shift একটি token খরচ করে, তাই shift ঠিক n টি। প্রতিটি reduce গাছের একটি ভেতরের node বানায় (উপপাদ্য ১.২)। ε-নিয়ম না থাকলে প্রতিটি ভেতরের node অন্তত একটি পাতা ঢাকে, আর unit-চক্র না থাকলে একটি node-এর ওপরে শুধু-এক-সন্তানের node-এর শিকল বড়জোর |V| লম্বা। ফলে ভেতরের node বড়জোর (|V| + 1)·(2n − 1)টি, grammar স্থির ধরলে O(n). প্রতিটি কাজ টেবিলে একবার দেখা, স্থির সময়। ∎ ওপরের run-এ ৫টি token-এ ৫টি shift আর ৮টি reduce, এই সীমার মধ্যে। পর্ব ৩১-এর CYK-এর O(n3)-এর সঙ্গে তুলনা করুন: deterministic grammar-এ নিজেকে সীমাবদ্ধ রাখার পুরস্কার এই linear সময়।

এই parser আসলে একটি deterministic PDA. Stack-এর alphabet হলো DFA-র state-গুলো, প্রতিটি কাজ একটি নির্দিষ্ট transition, আর কোনো অনুমান নেই। পর্ব ৩২-এর PDA আর পর্ব ৩৩-এর endmarker-এর আলোচনা মনে করুন: $ থাকায় parser জানে input কখন শেষ। শুধু একটি সূক্ষ্মতা: reduce-এ |β|টি চিহ্ন একসঙ্গে pop হয়, যা কয়েকটি এক-চিহ্নের ε-move দিয়ে সাজানো যায়। পর্ব ৩৪-এর CFG → PDA গঠন অনুমান করত কোন নিয়ম খুলবে; LR parser সেই অনুমানকে একটি টেবিল দিয়ে বদলেছে।

৪ · LR(1) আর LALR(1) — lookahead আরও সূক্ষ্ম করা

SLR-এর দুর্বলতা হলো FOLLOW একটি বৈশ্বিক set: “A-এর পরে কোনো না কোনো জায়গায় কী আসতে পারে”. কিন্তু একটি নির্দিষ্ট state-এ, একটি নির্দিষ্ট প্রেক্ষাপটে, তার চেয়ে কম token সম্ভব হতে পারে। Dragon book-এর একটি পরিচিত উদাহরণ (C-এর pointer assignment-এর সরল রূপ):

S → L = R ∣ R, L → ∗R ∣ id, R → L

id-এর পরে L → id গুটিয়ে যে state আসে, সেখানে দুটি item: [S → L· = R] আর [R → L·]. FOLLOW(R)-এ = আছে (কারণ S ⇒ L = R ⇒ ∗R = R), তাই SLR টেবিলের ওই ঘরে shift = আর reduce R → L দুটিই: shift/reduce conflict. অথচ এই নির্দিষ্ট state-এ, বাক্যের শুরুতে, R-এর পরে = কখনো আসতে পারে না; R থেকে শুরু হওয়া বাক্যে R-এর পরে শুধু $. Grammar-টি ambiguous নয়, শুধু SLR যথেষ্ট সূক্ষ্ম নয়।

সংজ্ঞা ৪.১ (LR(1) item, LALR(1))

একটি LR(1) item হলো [A → α·β, a], যেখানে a একটি terminal বা $: “এই নিয়ম শেষ হলে পরের token a হবে”. Closure-এর নিয়ম বদলায়: [A → α·Bβ, a] থাকলে প্রতিটি B → γ আর প্রতিটি b ∈ FIRST(βa)-এর জন্য [B → ·γ, b] যোগ করুন। Reduce শুধু [A → α·, a]-এর নিজের a-তে। এভাবে canonical LR(1) parser পাওয়া যায়।

দুটি LR(1) state-এর item থেকে lookahead বাদ দিলে যদি একই LR(0) set (core) থাকে, তাদের মিলিয়ে একটি state করা যায়, lookahead-গুলোর union নিয়ে। এভাবে বানানো parser LALR(1); এর state-সংখ্যা LR(0) collection-এর সমান।

S → L = R grammar-এ এটি কীভাবে কাজ করে, দেখা যাক। শুরুর state-এ [S′ → ·S, $] থেকে closure আনে [S → ·L = R, $] আর [S → ·R, $]; দ্বিতীয়টি থেকে [R → ·L, $], কারণ R-এর পরে কিছু নেই, তাই lookahead আগের মতোই $. প্রথমটি থেকে [L → ·∗R, =] আর [L → ·id, =], কারণ এখানে L-এর পরে =. এবার L-এর ওপর goto নিলে state-টিতে থাকে [S → L· = R, $] আর [R → L·, $]. Reduce শুধু $-এ, shift শুধু =-এ: দ্বন্দ্ব নেই। FOLLOW(R)-এর “=” এসেছিল অন্য প্রেক্ষাপট থেকে (= চিহ্নের ডান দিকের ∗R থেকে), যা এই state-এ প্রাসঙ্গিক নয়। LR(1) item প্রতিটি প্রেক্ষাপটের lookahead আলাদা করে বহন করে, আর closure-এ FIRST(βa) নেওয়ার কারণ এটাই (FIRST set-এর হিসাবও পর্ব ৩৮-এ)।

খরচের তফাতটি বাস্তব। Scratch-এ লেখা একটি স্বাধীন LR(1) builder দিয়ে গোনা হয়েছে: expression grammar-এ LR(0) state ১২টি কিন্তু canonical LR(1) state ২২টি; ওপরের S → L = R grammar-এ ১০ বনাম ১৪টি। আসল programming language-এর grammar-এ এই অনুপাত অনেক বড় হতে পারে, আর ১৯৬০-এর দশকের যন্ত্রে সেটিই ছিল সমস্যা (ভাবনার প্রশ্ন ১)। LALR(1) state-সংখ্যা ছোট রাখে, আর বেশিরভাগ বাস্তব grammar-এ LR(1)-এর মতোই কাজ করে। তবে মেলানোর একটি দাম আছে:

উপপাদ্য ৪.২ (মেলানোর ফল)

একটি grammar-এর canonical LR(1) টেবিলে কোনো conflict না থাকলে, একই core-এর state মিলিয়ে বানানো LALR(1) টেবিলে নতুন কোনো shift/reduce conflict আসে না। নতুন reduce/reduce conflict আসতে পারে।

প্রমাণ অনুশীলন ২-এ। দ্বিতীয় অংশের একটি উদাহরণ: S → aAd ∣ aBe ∣ bAe ∣ bBd, A → c, B → c. “ac”-এর পরে LR(1) state-এ [A → c·, d] আর [B → c·, e]; “bc”-এর পরে [A → c·, e] আর [B → c·, d]. দুটির core এক, {[A → c·], [B → c·]}. মেলালে দুই নিয়মেরই lookahead {d, e}: reduce/reduce conflict. মেলানোর আগে কোনো conflict ছিল না।

উপপাদ্য ৪.৩ (ক্ষমতার ক্রম)

Grammar-এর শ্রেণি হিসেবে LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1), আর প্রতিটি LR(k) grammar unambiguous. Language-এর দিক থেকে (Knuth ১৯৬৫): একটি language-এর কোনো LR(k) grammar আছে ⇔ language-টি deterministic CFL ⇔ তার একটি LR(1) grammar আছে।

অন্তর্ভুক্তিগুলো সংজ্ঞা থেকেই আসে: SLR-এর reduce-ঘর LR(0)-এর একটি উপসেট, LALR-এর lookahead (প্রমাণিত ভাবে) FOLLOW-এর উপসেট, আর LALR হলো LR(1)-এর মেলানো রূপ। “Unambiguous” অংশটি উপপাদ্য ১.২-এর উল্টো দিক: deterministic parser প্রতিটি w-এর জন্য একটিই কাজের ক্রম দেয়, তাই একটিই rightmost derivation. Language-এর অংশটির প্রমাণ এখানে বাদ (Knuth-এর মূল প্রবন্ধ, বা Hopcroft–Motwani–Ullman-এর DPDA অধ্যায়ে এর সঙ্গে সম্পর্কিত ফল); পর্ব ৩৫-এ DCFL-এর সংজ্ঞা আর DPDA দেখেছেন। একটি সরাসরি ফল: জোড় দৈর্ঘ্যের palindrome {wwR} কোনো DCFL নয়, তাই তার কোনো LR(k) grammar নেই, k যত বড়ই হোক। কঠোরতার সাক্ষী নিচের সারণিতে; প্রতিটি সারি scratch-এর independent builder আর PLY দুটি দিয়েই মিলিয়ে দেখা।

GrammarLR(0)SLR(1)LALR(1)LR(1)
S → ( S ) ∣ x✓✓✓✓
E → T+E ∣ T, T → id✗ (I2)✓✓✓
S → L = R ∣ R, L → ∗R ∣ id, R → L✗✗ (shift/reduce on =)✓✓
S → aAd ∣ aBe ∣ bAe ∣ bBd, A → c, B → c✗✗✗ (reduce/reduce)✓
E → E+E ∣ E∗E ∣ id (ambiguous)✗✗✗✗

এখানে একটি সূক্ষ্ম পার্থক্য মনে রাখুন। ✗ মানে এই grammar-টি ওই শ্রেণির নয়, language-টি নয়। প্রতিটি সারির language-ই deterministic, শেষটিরও (E → E+T ∣ T ধরনের unambiguous grammar আছে)। Parser-এর conflict প্রায় সবসময় grammar-এর লেখার ধরনের সমস্যা, language-এর সীমা নয়।

৫ · Conflict, precedence আর dangling else

পর্ব ২৭-এ দেখেছেন, E → E+E ∣ E∗E ∣ id ambiguous, আর ambiguity দূর করতে E/T/F স্তর বানাতে হয়। কিন্তু স্তর-ভাগ করা grammar লম্বা, আর দশটি precedence-স্তরের ভাষায় আরও লম্বা। yacc-এর নকশাকারীরা একটি ব্যবহারিক পথ নেন: ambiguous grammar-ই রাখুন, আর conflict-গুলো একটি ছোট নিয়মের তালিকা দিয়ে মেটান। Ambiguous grammar-এর LR(0) automaton-এ একটি state-এ থাকে [E → E+E·] আর [E → E·∗E]: stack-এ E + E, পরের token ∗. Reduce করলে (E+E)∗…, shift করলে E+(E∗…). Precedence আর associativity ঠিক এই প্রশ্নের উত্তর।

নিয়ম ৫.১ (yacc-ধাঁচের conflict মেটানো)

একটি নিয়মের precedence = তার ডান দিকের শেষ terminal-এর precedence. Shift/reduce conflict-এ নিয়মটির precedence আর পরের token-এর precedence তুলনা করুন: token-এর বেশি হলে shift; কম হলে reduce; সমান হলে left-associative-এ reduce, right-associative-এ shift, non-associative-এ error. Precedence ঘোষণা না থাকলে yacc ধরনের tool shift বেছে নেয় আর সতর্কবার্তা দেয়; reduce/reduce-এ grammar-এ আগে লেখা নিয়মটি নেয়।

Stack, পরের token আর সিদ্ধান্ত
stack
পরের token
দ্বন্দ্ব?
সিদ্ধান্ত
  1. শুরু। 2 তোলা হলো আর সঙ্গে সঙ্গে E-তে গুটানো (E2 মানে মান 2-এর একটি E). Stack-এ E আর পরের token +: ওপরে E op E নেই, কোনো দ্বন্দ্ব নেই, shift.
  2. দ্বিতীয় সংখ্যা। Stack-এ E2 +, পরের token 3: shift, আর সঙ্গে সঙ্গে E-তে গুটানো। ফলে stack হয় E2 + E3.
  3. প্রথম দ্বন্দ্ব। E + E-কে গুটানো যায়, আবার ∗ তোলাও যায়। নিয়মের শেষ terminal +, token ∗; ∗-এর স্তর উঁচু, তাই shift. গুণ যোগের ভেতরে ঢুকল।
  4. দ্বিতীয় দ্বন্দ্ব। 4 তোলার পরে stack-এ E2 + E3 ∗ E4, পরের token −. নিয়ম E∗E-এর শেষ terminal ∗, token − নিচু, তাই reduce: 3 ∗ 4 = 12.
  5. Associativity-র পালা। এবার E2 + E12 আর পরের token −. + আর − সমান স্তরের, আর দুটিই left-associative, তাই reduce: 2 + 12 = 14. এতে 8 − 2 − 3-এর মতো ক্ষেত্রেও বাঁ থেকে হিসাব হয়।
  6. শেষ গুটানো। − আর 1 তুলে stack-এ E14 − E1, পরের চিহ্ন $. Input শেষ, তাই reduce: 13.
  7. গ্রহণ। Stack-এ একটি E, মান 13 = 2 + 3 ∗ 4 − 1. এটি সাধারণ পাটিগণিতের উত্তর।
  8. Precedence ছাড়া কী হতো। সব দ্বন্দ্বে shift করলে সব operator stack-এ জমে, শেষে ডান থেকে গুটায়: 2 + (3 ∗ (4 − 1)) = 11. ভুল উত্তর, অথচ কোনো error নেই। অংশ ৬-এর PLY run ঠিক এমন ভুল দেখাবে।

নিচের JavaScript ব্লকে একই কৌশল কোডে, প্রতিটি সিদ্ধান্তের কারণসহ। এটি পূর্ণ LR টেবিল বানায় না; শুধু “stack-এর ওপরে E op E আর পরের token” দেখে নিয়ম ৫.১ খাটায়, যা ambiguous expression grammar-এর LR(0) state-এ ঠিক ঘটে।

// Shift-reduce for the ambiguous grammar E -> E+E | E-E | E*E | num,
// with every shift/reduce conflict settled by a precedence table.
const PREC = { "+": 1, "-": 1, "*": 2 };          // higher number binds tighter
const LEFT = true;                                 // all three are left-assoc
const show = (st) => st.map(x => typeof x === "number" ? "E" + x : x).join(" ");

function parse(src) {
  const rest = src.match(/\d+|[-+*]/g).concat("$"), st = [];
  console.log("input:", src);
  while (true) {
    const a = rest[0], n = st.length;
    if (n >= 3 && st[n - 2] in PREC) {             // top of stack is E op E
      const op = st[n - 2];
      let why = null;
      if (a === "$") why = "end of input";
      else if (PREC[a] < PREC[op]) why = `${a} is lower than ${op}`;
      else if (PREC[a] === PREC[op] && LEFT) why = `${a} same level, left-assoc`;
      if (why) {                                   // reduce E op E -> E
        const y = st.pop(); st.pop(); const x = st.pop();
        st.push(op === "+" ? x + y : op === "-" ? x - y : x * y);
        console.log(`  reduce E${op}E (${why})`.padEnd(42), "stack:", show(st));
        continue;
      }
      console.log(`  shift ${a} (${a} is higher than ${op})`);
    }
    if (a === "$") { console.log("  accept, value =", st[0]); return st[0]; }
    rest.shift();
    st.push(/\d/.test(a) ? Number(a) : a);         // a number is shifted and
  }                                                // reduced to E at once
}
parse("2+3*4-1");
parse("8-2-3");

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

input: 2+3*4-1
  shift * (* is higher than +)
  reduce E*E (- is lower than *)           stack: E2 + E12
  reduce E+E (- same level, left-assoc)    stack: E14
  reduce E-E (end of input)                stack: E13
  accept, value = 13
input: 8-2-3
  reduce E-E (- same level, left-assoc)    stack: E6
  reduce E-E (end of input)                stack: E3
  accept, value = 3

শুধু দ্বন্দ্বের মুহূর্তগুলো ছাপা হয়েছে; সাধারণ shift নীরব। প্রথম input-এর তিনটি সিদ্ধান্ত ঠিক stepper-এর ধাপ ৩, ৪ আর ৫. দ্বিতীয় input-এ − left-associative বলে 8 − 2 আগে গুটায়: (8 − 2) − 3 = 3. LEFT = false করে চালিয়ে দেখুন: 8 − (2 − 3) = 9, যা ঘাত (^)-এর মতো right-associative operator-এর আচরণ, বিয়োগের নয়।

এবার dangling else, পর্ব ২৭-এর grammar S → if c then S ∣ if c then S else S ∣ a. “if c then if c then a else a”-এ ভেতরের S পড়ার পরে state-এ [S → if c then S·] আর [S → if c then S·else S], পরের token else: একটি shift/reduce conflict. Reduce করলে else বাইরের if-এর; shift করলে ভেতরের, অর্থাৎ সবচেয়ে কাছের জোড়াহীন if-এর, যা প্রায় সব ভাষার নিয়ম। তাই generator-এর “দ্বন্দ্বে shift” নিয়মটি এখানে কাকতালীয়ভাবে ঠিক উত্তর দেয়। Matched/unmatched grammar দিয়ে conflict-টি পুরো সরানোও যায়, কিন্তু বাস্তবে অনেকে ছোট grammar আর একটি পরিচিত সতর্কবার্তা রাখেন।

৬ · বাস্তবে LR — PLY আর lark (সত্যিকারের run)

এবার তত্ত্বকে আসল parser generator-এর সামনে রাখা যাক। PLY (Python Lex-Yacc, BSD licence) হলো yacc-এর Python রূপ: প্রতিটি function-এর docstring-এ একটি নিয়ম, আর ডিফল্ট পদ্ধতি LALR(1); debug=True দিলে সব state আর conflict একটি parser.out ফাইলে লেখে। lark (MIT licence)-এর parser="lalr" বিকল্পও LALR(1). দুটিই বিশুদ্ধ Python, কোনো usage-reporting নেই। Scratch-এর একটি uv project-এ চালানো হয়েছে (Python 3.12.13, PLY 3.11, lark 1.3.1, uv 0.11.28); path বাদে আউটপুট হুবহু। প্রথম script-টি একই lexer-এর ওপর তিনটি grammar বানায়:

if mode == "layered":                      # E/T/F, as in section 1
    def p_e_plus(p):  "e : e PLUS t"; p[0] = p[1] + p[3]
    ...
else:                                      # the ambiguous grammar
    if mode == "precedence":
        precedence = (("left", "PLUS", "MINUS"), ("left", "TIMES"))  # low -> high
    def p_bin(p):
        """e : e PLUS e
             | e MINUS e
             | e TIMES e"""
        p[0] = {"+": p[1] + p[3], "-": p[1] - p[3], "*": p[1] * p[3]}[p[2]]
    ...
parser = yacc.yacc(debug=True, outputdir=mode, write_tables=False,
                   errorlog=yacc.PlyLogger(sys.stdout))
print("states:", len(parser.action))
for s in ["2 + 3 * 4", "2 * 3 + 4", "8 - 2 - 3"]:
    print(f"{s:10} = {parser.parse(s, lexer=lexer)}")

সত্যিকারের run:

~/bazarghar-toc$ for m in layered ambiguous precedence; do uv run python ply_expr.py $m; done
Generating LALR tables
states: 14
2 + 3 * 4  = 14
2 * 3 + 4  = 10
8 - 2 - 3  = 3
Generating LALR tables
WARNING: 9 shift/reduce conflicts
states: 12
2 + 3 * 4  = 14
2 * 3 + 4  = 14
8 - 2 - 3  = 9
Generating LALR tables
states: 12
2 + 3 * 4  = 14
2 * 3 + 4  = 10
8 - 2 - 3  = 3

Layered: কোনো conflict নেই, তিনটি উত্তরই ঠিক। ১৪টি state, অংশ ২-এর ১২টির চেয়ে বেশি, কারণ এখানে − চিহ্নের নিয়ম আছে।

Ambiguous, precedence ছাড়া: ৯টি shift/reduce conflict = তিনটি state ([E → E+E·], [E → E−E·], [E → E∗E·]) × তিনটি operator. সতর্কবার্তার পরেও PLY parser বানায়, সব দ্বন্দ্বে shift নিয়ে। ফল: 2 ∗ 3 + 4 = 2 ∗ (3 + 4) = 14 আর 8 − 2 − 3 = 8 − (2 − 3) = 9. দুটিই ভুল, অথচ program চলেছে কোনো error ছাড়া। প্রথম উত্তরটি ঠিক এসেছে শুধু কাকতালীয়ভাবে।

Precedence-সহ: conflict শূন্য, সব উত্তর ঠিক। PLY-র precedence tuple-এ ক্রম নিচু থেকে উঁচু: পরের লাইন বেশি শক্ত করে বাঁধে।

parser.out-এ conflict ঠিক কোথায়, দেখা যায়। নিচে ambiguous run-এর একটি state, আর precedence run-এ সমতুল্য state (দুই ফাইলের অংশ):

state 9                                   # ambiguous/parser.out
    (2) e -> e MINUS e .
    (1) e -> e . PLUS e
    (2) e -> e . MINUS e
    (3) e -> e . TIMES e
  ! shift/reduce conflict for PLUS resolved as shift
  ! shift/reduce conflict for MINUS resolved as shift
  ! shift/reduce conflict for TIMES resolved as shift
    $end            reduce using rule 2 (e -> e MINUS e .)
    RP              reduce using rule 2 (e -> e MINUS e .)
    PLUS            shift and go to state 4
    MINUS           shift and go to state 5
    TIMES           shift and go to state 6
...
state 8                                   # precedence/parser.out
    (1) e -> e PLUS e .
    ...
    PLUS            reduce using rule 1 (e -> e PLUS e .)
    MINUS           reduce using rule 1 (e -> e PLUS e .)
    $end            reduce using rule 1 (e -> e PLUS e .)
    RP              reduce using rule 1 (e -> e PLUS e .)
    TIMES           shift and go to state 6
  ! TIMES           [ reduce using rule 1 (e -> e PLUS e .) ]
  ! PLUS            [ shift and go to state 4 ]
  ! MINUS           [ shift and go to state 5 ]

“!” চিহ্নের সারিগুলো বাদ পড়া বিকল্প। State 9-এ (E − E·) MINUS পেলে shift, অর্থাৎ right-associative: সেই কারণেই 9. Precedence-এর state 8-এ PLUS আর MINUS পেলে reduce (left-associative), TIMES পেলে shift: ঠিক নিয়ম ৫.১. এবার একই PLY দিয়ে অংশ ৪-এর ফাঁকগুলো আর dangling else (প্রতিটি grammar আলাদা module-এ; method দিয়ে SLR বা LALR বাছা যায়, canonical LR(1) PLY-তে নেই):

~/bazarghar-toc$ uv run python run_g.py assign SLR
Generating SLR tables
WARNING: 1 shift/reduce conflict
states: 10
~/bazarghar-toc$ uv run python run_g.py assign LALR
Generating LALR tables
states: 10
id = * id                    -> ('assign', 'id', ('deref', 'id'))
* * id                       -> ('deref', ('deref', 'id'))
~/bazarghar-toc$ uv run python run_g.py lr1 LALR
Generating LALR tables
WARNING: 2 reduce/reduce conflicts
WARNING: reduce/reduce conflict in state 6 resolved using rule (x -> C)
WARNING: rejected rule (y -> C) in state 6
WARNING: Rule (y -> C) is never reduced
states: 13
a c d                        -> aAd
a c e                        -> SyntaxError: syntax error at LexToken(E,'e',1,4)
b c d                        -> SyntaxError: syntax error at LexToken(D,'d',1,4)
b c e                        -> bAe
~/bazarghar-toc$ uv run python run_g.py ite LALR
Generating LALR tables
WARNING: 1 shift/reduce conflict
states: 9
if c then if c then a else a -> if(if(a, else a))

S → L = R: SLR-এ ঠিক একটি shift/reduce conflict, আর parser.out বলে সেটি state 2-তে, যেখানে [s → l . EQ r] আর [r → l .]: অংশ ৪-এর বিশ্লেষণ হুবহু। LALR-এ conflict নেই, state একই ১০টি। (SLR run-এর parse লাইন দুটি এখানে বাদ; shift বেছে নেওয়ায় ফল একই।)

LR(1) কিন্তু LALR নয়: PLY-তে x = A, y = B. মেলানো state 6-এ reduce/reduce, আর PLY আগে লেখা নিয়ম x → C রেখে y → C ফেলে দেয়, এমনকি জানায় “never reduced”. ফল ভয়াবহ: a c e আর b c d বৈধ বাক্য, তবু syntax error. State-সংখ্যা ১৩, ঠিক LR(0) collection-এর মাপ; scratch-এর LR(1) builder এই grammar-এ ১৪টি state আর শূন্য conflict পায়।

Dangling else: একটি shift/reduce conflict, shift দিয়ে মেটানো, আর ফলাফল if(if(a, else a)): else ভেতরের if-এর সঙ্গে। এখানে ডিফল্টটিই চাওয়া উত্তর।

শেষে lark-এর LALR একই তিনটি grammar-এ। lark conflict-এর বার্তা debug স্তরের log-এ লেখে, তাই script-টি log-এর স্তর DEBUG করে আর গাছগুলো বন্ধনী আকারে ছাপে:

~/bazarghar-toc$ uv run python -u lark_lalr.py
lark 1.3.1
== layered
  id + id * id                 -> [id + [id * id]]
  id * id + id                 -> [[id * id] + id]
== ambiguous
Shift/Reduce conflict for terminal PLUS: (resolving as shift)
 * <e : e PLUS e>
Shift/Reduce conflict for terminal STAR: (resolving as shift)
 * <e : e PLUS e>
Shift/Reduce conflict for terminal PLUS: (resolving as shift)
 * <e : e STAR e>
Shift/Reduce conflict for terminal STAR: (resolving as shift)
 * <e : e STAR e>
  id + id * id                 -> [id + [id * id]]
  id * id + id                 -> [id * [id + id]]
== dangling else
Shift/Reduce conflict for terminal ELSE: (resolving as shift)
 * <e : IF C THEN e>
  if c then if c then a else a -> [if c then [if c then a else a]]

Layered grammar-এ দুটি গাছই ঠিক। Ambiguous grammar-এ lark-ও প্রতিটি দ্বন্দ্বে shift নেয়: id + id ∗ id ঠিক আসে, কিন্তু id ∗ id + id হয় id ∗ (id + id). পার্থক্য হলো, ডিফল্ট log-স্তরে এই বার্তাগুলো দেখাই যায় না; lark শুধু reduce/reduce-এ error দেয়। তাই lark-এর LALR-এ expression লিখলে precedence-এর স্তর grammar-এর ভেতরেই বানাতে হয়, অথবা Earley parser নিতে হয় (পর্ব ৪০ আর ৪১)। Dangling else-এর গাছ PLY-র মতোই।

আরও গভীরে: LALR(1)-এর lookahead মেলানো state ছাড়াই সরাসরি LR(0) automaton থেকে হিসাব করার দক্ষ পদ্ধতি DeRemer আর Pennello ১৯৮২ সালে দেন বলে পরিচিত, আর PLY-র ডকুমেন্টেশনও এই পদ্ধতির কথা বলে। LR(1)-এর ক্ষমতা আর LALR-এর আকার একসঙ্গে পেতে David Pager ১৯৭৭ সালে state শুধু তখনই মেলানোর প্রস্তাব দেন, যখন তাতে conflict আসে না; Bison-এর IELR(1) বিকল্প এই ধারার একটি আধুনিক রূপ (Denny ও Malloy, ২০১০-এর আশপাশে)। তত্ত্বের দিকে, viable prefix-এর regularity থেকে আরেকটি সুন্দর ফল আসে: LR(0) grammar আছে ঠিক সেই DCFL-গুলোর, যারা prefix-free (Hopcroft–Motwani–Ullman-এর DPDA অংশ দেখুন), আর যেকোনো LR(k) language-এর একটি LR(1) grammar আছে।

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

  • একটি ছোট grammar-এর LR(0) item-set আর SLR টেবিল বানান। Augment, closure, প্রতিটি চিহ্নে goto; তারপর shift-ঘর তীর থেকে, reduce-ঘর FOLLOW থেকে।
  • দেওয়া টেবিলে একটি string-এর shift-reduce parse লিখুন। প্রতিটি সারিতে stack, বাকি input, কাজ; reduce-এ |β|টি pop আর GOTO.
  • Handle কী? Right-sentential form-এর যে অংশ গুটালে rightmost derivation-এর আগের ধাপ আসে; সবসময় stack-এর ওপরে।
  • LALR-এ কোন conflict নতুন আসতে পারে? শুধু reduce/reduce; shift/reduce নয় (উপপাদ্য ৪.২)।
  • LL(1) বনাম LR(1), কোনটি শক্তিশালী? Grammar হিসেবে LR(1): প্রতিটি LL(1) grammar LR(1), উল্টোটা নয় (যেমন left-recursive E → E+T).

৭ · AI-এর যুগে LR parsing

AI assistant-কে “একটি yacc grammar লিখে দাও” বললে পরিচ্ছন্ন কোড আসে, কিন্তু LR-এর সবচেয়ে বিপজ্জনক ভুলগুলো চোখে পড়ে না, কারণ parser চলে, শুধু ভুল গাছ বানায়। সবচেয়ে সাধারণ উদাহরণ precedence-এর ক্রম: yacc আর PLY-তে তালিকার পরের লাইন বেশি শক্ত করে বাঁধে, অথচ অনেক মানুষ আর AI উল্টো ধরে নেন। যাচাইয়ের উপায় সহজ: ছোট সব expression তৈরি করে parser-এর উত্তর একটি বিশ্বস্ত reference-এর সঙ্গে মেলানো, এখানে Python-এর নিজস্ব পাটিগণিত। নিচের ব্লকে তিনটি precedence টেবিল: সঠিক, একটি “AI draft” যেখানে লাইন দুটির ক্রম উল্টো, আর একটি যেখানে + আর − ভুল করে right-associative.

# Check a yacc-style precedence table against Python's own arithmetic
from itertools import product

def make_parser(precedence):            # yacc rule: later line = higher level
    level = {op: (i, assoc) for i, (assoc, *ops) in enumerate(precedence) for op in ops}
    def parse(tokens):                  # shift-reduce for E -> E op E | num
        stack, rest = [], tokens + ["$"]
        while True:
            a = rest[0]
            if len(stack) >= 3 and stack[-2] in level:      # top is E op E
                op = stack[-2]
                if a == "$" or level[a][0] < level[op][0] or (
                        level[a][0] == level[op][0] and level[op][1] == "left"):
                    y, _, x = stack.pop(), stack.pop(), stack.pop()   # reduce
                    stack.append({"+": x + y, "-": x - y, "*": x * y}[op])
                    continue
            if a == "$": return stack[0]
            stack.append(rest.pop(0))                       # shift
    return parse
def all_expressions(max_ops):
    for k in range(max_ops + 1):
        for nums in product([1, 2, 3], repeat=k + 1):
            for ops in product("+-*", repeat=k):
                yield [nums[0]] + [t for p in zip(ops, nums[1:]) for t in p]

tables = {"correct": [("left", "+", "-"), ("left", "*")],
          "AI draft": [("left", "*"), ("left", "+", "-")],
          "right -": [("right", "+", "-"), ("left", "*")]}
for name, prec in tables.items():
    parse, bad, n = make_parser(prec), [], 0
    for toks in all_expressions(3):
        n += 1
        if parse(list(toks)) != eval("".join(map(str, toks))):
            bad.append("".join(map(str, toks)))
    print(f"{name:9} wrong on {len(bad):4} of {n}; first: {bad[:3]}")

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

correct   wrong on    0 of 2460; first: []
AI draft  wrong on 1154 of 2460; first: ['1+1*2', '1-1*2', '1+1*3']
right -   wrong on  999 of 2460; first: ['1-1+1', '1-1-1', '1-1+2']

১, ২, ৩ অঙ্ক আর বড়জোর তিনটি operator-এর সব ২৪৬০টি expression পরীক্ষা হয়েছে। সঠিক টেবিল একটিতেও ভুল করেনি। উল্টো ক্রমের টেবিল প্রায় অর্ধেকে ভুল, আর প্রথম প্রতি-উদাহরণ পাঁচ অক্ষরের: 1+1∗2-কে (1+1)∗2 = 4 ধরে। Right-associative বিয়োগের প্রথম প্রতি-উদাহরণ 1−1+1 = 1 − (1 + 1). লক্ষ করুন, “2 + 3 ∗ 4”-এর মতো একটি-দুটি হাতে বাছা উদাহরণে ভুল draft-ও কখনো কখনো ঠিক উত্তর দেয় (অংশ ৬-এর PLY run-এ ঠিক এমনটি হয়েছে); সব ছোট ক্ষেত্রে পরীক্ষাই ভরসা।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
Precedence-এর ক্রম উল্টো, বা associativity ভুলওপরের মতো সব ছোট expression-এ বিশ্বস্ত হিসাবের সঙ্গে মেলান
“Conflict শুধু warning, উপেক্ষা করুন” পরামর্শparser.out বা debug log পড়ুন: কোন state, কোন token, কোন বিকল্প বাদ গেল; reduce/reduce হলে নিয়ম হারিয়ে যেতে পারে
Closure-এ কোনো নিয়ম বাদ, বা FOLLOW-এর বদলে সব token-এ reduceনিজের item-set builder (অংশ ২–৩-এর ব্লক) চালিয়ে state-সংখ্যা আর টেবিল মেলান
Handle-কে “stack-এ প্রথম যে ডান দিক মেলে” বলে ধরা (E + T ∗ id-এ E + T)গুটানোর পরের form কোনো right-sentential form কি না দেখুন; rightmost derivation লিখে মেলান
“LALR-এ shift/reduce নতুন আসে” বা “LALR আর LR(1) একই”উপপাদ্য ৪.২ আর aAd/bBd ধরনের grammar-এ PLY-র reduce/reduce বার্তা দেখুন
“প্রতিটি DCFL-এর জন্য LR(0) grammar আছে”, বা ইতিহাসের ভুল সাল ও লেখকHopcroft–Motwani–Ullman, Dragon book বা Knuth-এর ১৯৬৫ সালের প্রবন্ধে মিলিয়ে নিন

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

আমি গণনার তত্ত্ব শিখছি। Grammar: S → ( L ) | x, L → S | L , S. ১. Augmented grammar লিখে পুরো canonical LR(0) collection দাও; প্রতিটি state-এর সব item আর প্রতিটি goto তীর দেখাও। ২. কোনো state-এ LR(0) conflict আছে কি না বলো, কারণসহ। ৩. FOLLOW(S) আর FOLLOW(L) হিসাব করে SLR(1) টেবিল দাও। ৪. "(x,(x))" string-এর shift-reduce parse প্রতিটি ধাপে stack, বাকি input আর কাজসহ লেখো। ৫. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা টেবিলটি বানায় আর দৈর্ঘ্য ৭ পর্যন্ত সব string-এ grammar-এর brute-force উত্তরের সঙ্গে parser-এর উত্তর মেলায়। ৬. কোনো ঘর নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

(নিজে যাচাই করুন: lr0_items.py ব্লকে G-এর জায়গায় এই grammar বসিয়ে চালালে ৯টি state আর একটিও conflict চিহ্ন আসে না; grammar-টি LR(0). AI-এর state-সংখ্যা আলাদা হলে আগে closure পরীক্ষা করুন।)

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

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

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

প্র ০১Knuth ১৯৬৫ সালেই LR(k) parsing দিয়েছিলেন। তাহলে বাস্তবে এটি ছড়াতে কেন আরও প্রায় এক দশক লাগল?

Donald Knuth-এর ১৯৬৫ সালের প্রবন্ধ “On the translation of languages from left to right” তাত্ত্বিকভাবে প্রায় সম্পূর্ণ ছিল: LR(k) grammar-এর সংজ্ঞা, viable prefix যে একটি সসীম যন্ত্র দিয়ে চেনা যায় তার প্রমাণ, LR(k) grammar থেকে deterministic parser বানানোর পদ্ধতি, আর deterministic language-গুলোর সঙ্গে সম্পর্ক। কিন্তু সে সময়ের কম্পিউটারের memory কয়েক হাজার থেকে কয়েক লক্ষ শব্দের মাপে। একটি পূর্ণ programming language-এর canonical LR(1) টেবিলে state-এর সংখ্যা এত বড় হতো যে তা বাস্তবে অচল মনে করা হয়েছিল। এই পর্বের ছোট expression grammar-এও LR(1) state ২২টি, LR(0)-এর ১২টির প্রায় দ্বিগুণ; বড় grammar-এ অনুপাত আরও খারাপ হতে পারে।

মোড় ঘোরে Frank DeRemer-এর কাজে। তাঁর ১৯৬৯ সালের MIT PhD thesis-এ LALR ধারণা আর ১৯৭১ সালের “Simple LR(k) grammars” প্রবন্ধে SLR আসে বলে সাধারণত বলা হয়। মূল চিন্তা: LR(0) automaton রাখুন, যার আকার ছোট, আর শুধু lookahead-এর হিসাবটুকু সূক্ষ্ম করুন। ফলে LR(0)-এর মাপের টেবিলেই প্রায় সব বাস্তব grammar ধরা পড়ে। এরপর ১৯৭০-এর দশকের মাঝামাঝি Bell Labs-এ Stephen C. Johnson yacc (“Yet Another Compiler-Compiler”) বানান, যা LALR(1) টেবিল তৈরি করত আর Unix-এর সঙ্গে ছড়িয়ে পড়ে। একই সময়ে Aho আর Johnson-এর একটি জরিপ-প্রবন্ধ (১৯৭৪) LR parsing-কে বৃহত্তর প্রোগ্রামার-সমাজের কাছে বোধগম্য করে তোলে বলে পরিচিত।

অর্থাৎ বাধাটি তত্ত্বে ছিল না, ছিল প্রকৌশলে: টেবিলের আকার, তা বানানোর সময়, আর এমন একটি tool যা সাধারণ প্রোগ্রামার চালাতে পারেন। পরে টেবিল সংকোচনের কৌশল, দক্ষ LALR lookahead অ্যালগরিদম (DeRemer ও Pennello, ১৯৮২) আর Pager-এর মতো “শুধু নিরাপদ হলে মেলাও” পদ্ধতি এসে LR(1)-কেও ব্যবহারযোগ্য করে।

মূল উপলব্ধি: একটি algorithm সঠিক আর linear হলেই যথেষ্ট নয়; তার ধ্রুবক, memory আর ব্যবহারের সহজতা ঠিক করে সেটি বাস্তবে আসবে কি না। LALR জিতেছিল কারণ তা ছিল “যথেষ্ট শক্তিশালী আর যথেষ্ট ছোট”.

প্র ০২LR parser তাত্ত্বিকভাবে LL-এর চেয়ে শক্তিশালী। তবু বড় বড় compiler-এ হাতে লেখা recursive descent parser কেন এত দেখা যায়?

Grammar-এর শ্রেণি হিসেবে LR(1) সত্যিই বড়: প্রতিটি LL(1) grammar LR(1), কিন্তু E → E+T-এর মতো left-recursive grammar LL(k) নয়, অথচ LR(0)/SLR-এ স্বচ্ছন্দে চলে। Bottom-up parser নিয়ম বাছাইয়ের সিদ্ধান্ত পুরো ডান দিক দেখার পরে নেয়, আর top-down parser নেয় শুরুতেই; এই দেরিটাই LR-এর শক্তি। তবু বাস্তবের অনেক compiler-এর নির্মাতারা recursive descent বেছে নিয়েছেন। একটি পরিচিত উদাহরণ GCC: এর C++ parser ২০০০-এর দশকের শুরুতে (GCC 3.4) আর C parser কয়েক বছর পরে (GCC 4.1) yacc/Bison-ভিত্তিক থেকে হাতে লেখা recursive descent-এ বদলায় বলে জানা যায়।

কারণগুলো প্রকৌশলের। প্রথমত, ভুলের বার্তা: হাতে লেখা parser প্রতিটি জায়গায় জানে সে কী খুঁজছিল (“এখানে ; প্রত্যাশিত ছিল”), আর প্রসঙ্গ বুঝে বার্তা দিতে পারে। LR parser-এর error হয় একটি সংখ্যাযুক্ত state-এ, যার অর্থ মানুষের ভাষায় আনা কঠিন। দ্বিতীয়ত, বাস্তব ভাষা প্রায়ই সম্পূর্ণ context-free নয়: C-তে “T * x;” একটি গুণ নাকি pointer ঘোষণা, তা নির্ভর করে T একটি type-এর নাম কি না, যা আগের ঘোষণা থেকে জানা যায় (পর্ব ২২-এর lexer hack). C++-এ এই সমস্যা আরও জটিল। হাতে লেখা parser-এ এমন তথ্য সহজে ব্যবহার করা যায়। তৃতীয়ত, debugging আর রক্ষণাবেক্ষণ: সাধারণ function-এর কোড যেকোনো প্রোগ্রামার পড়তে পারেন, টেবিল পারেন না।

অন্যদিকে LR-ভিত্তিক generator এখনো বহুল ব্যবহৃত: PostgreSQL-এর SQL parser Bison দিয়ে বানানো বলে জানা, আর অনেক DSL বা কনফিগারেশন ভাষায় generator সময় বাঁচায়। আর generator একটি বড় সুবিধা দেয় যা হাতের কোড দেয় না: grammar ambiguous হলে বা সিদ্ধান্ত অস্পষ্ট হলে conflict-এর বার্তা দিয়ে আগেভাগে সতর্ক করে।

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

প্র ০৩Generator যখন conflict “shift দিয়ে মেটায়”, তখন সেটি কি নিরাপদ? কখন সতর্কবার্তা মেনে নেওয়া যায় আর কখন নয়?

“দ্বন্দ্বে shift” নিয়মের পেছনে একটি ভালো কারণ আছে। Shift মানে সিদ্ধান্ত পিছিয়ে দেওয়া, আরও input দেখার সুযোগ রাখা; আর সবচেয়ে পরিচিত conflict, dangling else, ঠিক shift-এই সেই উত্তর দেয় যা প্রায় সব ভাষা চায়। তাই yacc-এর প্রথম দিন থেকেই এই ডিফল্ট। কিন্তু অংশ ৬-এর run দেখিয়েছে এর বিপদ: precedence ছাড়া ambiguous expression grammar-এ PLY “৯টি conflict” বলে, তারপর একটি parser বানায় যা 2 ∗ 3 + 4-কে 14 আর 8 − 2 − 3-কে 9 বলে। Program চলে, crash করে না, শুধু চুপচাপ ভুল হিসাব করে। lark-এর LALR ডিফল্ট log-স্তরে বার্তাটিও দেখায় না।

Reduce/reduce আরও বিপজ্জনক। aAd/bBd grammar-এ PLY একটি নিয়ম পুরোপুরি ফেলে দেয়, আর বৈধ বাক্য “a c e” syntax error পায়। এখানে কোনো ডিফল্ট “ঠিক” হতে পারে না, কারণ দুটি নিয়মই দরকারি; grammar নতুন করে লিখতে হয়।

পেশাদার রীতি তাই: প্রতিটি conflict বুঝে নিন। Bison-এ %expect n ঘোষণা আছে বলে জানা, যা বলে “আমি ঠিক nটি shift/reduce conflict আশা করি”; সংখ্যা বদলালে build ব্যর্থ হয়। এতে dangling else-এর একটি জানা conflict রাখা যায়, কিন্তু grammar বদলে নতুন কোনো conflict ঢুকলে সঙ্গে সঙ্গে ধরা পড়ে। Expression-এর জন্য precedence declaration, আর বাকি সব conflict grammar নতুন করে লিখে দূর করা ভালো। আর অংশ ৭-এর মতো স্বয়ংক্রিয় পরীক্ষা: একটি reference-এর সঙ্গে হাজার হাজার ছোট input মেলানো।

বাজারঘরের দিক থেকে ভাবুন: order-query-তে “amount > 500 OR district = Dhaka AND status = paid” কে কীভাবে গোছানো হবে, তা ভুল হলে ভুল গ্রাহকের কাছে ছাড়ের বার্তা যাবে, কোনো error ছাড়াই।

মূল উপলব্ধি: Conflict-এর বার্তা grammar-এর সম্ভাব্য দ্ব্যর্থতার প্রমাণপত্র। ডিফল্ট সমাধান মেনে নেওয়া যায় শুধু তখন, যখন আপনি জানেন কোন গাছ বাদ গেল আর কেন সেটি বাদ যাওয়াই ঠিক।

প্র ০৪LR parser একটি PDA, কিন্তু তার সিদ্ধান্ত নেয় একটি DFA. এই “stack-এর ভেতরে finite automaton” ছবিটি গণনার তত্ত্বে আর কোথায় কাজে লাগে?

উপপাদ্য ২.২-এর গুরুত্ব হলো: stack-এর বিষয়বস্তু সীমাহীন হলেও, “এখন কী করব” প্রশ্নের উত্তর নির্ভর করে stack-এর একটি regular ধর্মের ওপর। LR parser এটি কাজে লাগায় প্রতিটি stack-ঘরে DFA-র state রেখে, যাতে ওপরের ঘরটিই পুরো stack-এর সারাংশ হয়। Knuth-এর প্রবন্ধের এই পর্যবেক্ষণ পরে PDA-তত্ত্বে একটি সাধারণ ফল হিসেবে দেখা দেয়: যেকোনো PDA-র নাগালের মধ্যে থাকা stack-বিষয়বস্তুর set একটি regular language. Büchi ১৯৬৪ সালের কাছাকাছি সময়ে এই ধরনের ফল দেন বলে উল্লেখ পাওয়া যায়।

এই ফলের একটি বড় বাস্তব প্রয়োগ আছে software verification-এ। একটি recursive program-এর call stack সীমাহীন হতে পারে, তাই তাকে একটি pushdown system হিসেবে মডেল করা হয়। “কোনো অবস্থায় কি একটি বিপজ্জনক function ডাকা সম্ভব?” প্রশ্নের উত্তর দিতে নাগালের stack-এর set হিসাব করা হয়, আর regular হওয়ায় তা একটি finite automaton দিয়ে প্রকাশ করা যায়। ১৯৯০-এর দশকের শেষে Bouajjani, Esparza, Maler প্রমুখের কাজে এই “pushdown model checking” কৌশল গড়ে ওঠে বলে পরিচিত, আর পর্ব ৭৭-এর model checking-এর সঙ্গে এর যোগ আছে।

Parsing-এর ভেতরেও ছবিটি ফিরে আসে। Error recovery-তে parser জানতে চায় “এই stack থেকে কোন token গ্রহণযোগ্য”, যা ওপরের state থেকেই পড়া যায়; তাই LR parser “expected one of …” বার্তা দিতে পারে। GLR parser (পর্ব ৪১) একাধিক stack একসঙ্গে রাখে, আর DFA-র state থাকায় একই state-এর stack-শাখাগুলো মেলানো যায়, যা তার দক্ষতার ভিত্তি।

মূল উপলব্ধি: সীমাহীন স্মৃতির যন্ত্রেরও অনেক প্রশ্নের উত্তর সসীম যন্ত্রে ধরা যায়। Regular language শুধু শুরুর অধ্যায় নয়; বড় যন্ত্রের ভেতরে লুকানো কাঠামো বোঝার হাতিয়ারও।

প্র ০৫LR parser ভুল পেলে কী করে? একটি ভুলেই থেমে না গিয়ে আরও ভুল খুঁজে পেতে কোন কৌশল আছে?

LR parser-এর একটি মূল্যবান ধর্ম হলো valid prefix property: যে মুহূর্তে পড়া অংশ আর কোনো বৈধ string-এর prefix নয়, ঠিক সেই token-এ ACTION টেবিলের ঘর error. Canonical LR(1) parser এই প্রথম অসম্ভব token-এ কোনো shift না করেই থামে। SLR আর LALR-এর ক্ষেত্রে একটি ছোট সূক্ষ্মতা আছে: বাড়তি lookahead-এর কারণে তারা ভুল token-এর আগে কয়েকটি অপ্রয়োজনীয় reduce করতে পারে, তবে ভুল token-টি কখনো shift করে না। তাই ভুলের অবস্থান নির্ভুল থাকে।

একটি ভুলে থামা compiler-এর জন্য যথেষ্ট নয়; প্রোগ্রামার একবারে সব ভুল দেখতে চান। yacc এর জন্য একটি বিশেষ token error দেয়। Grammar লেখক লেখেন, যেমন stmt → error ; অর্থাৎ “একটি statement-এর ভেতরে ভুল হলে ; পর্যন্ত বাদ দিয়ে আবার শুরু করো”. ভুল পেলে parser stack থেকে state pop করতে থাকে, যতক্ষণ না এমন state পায় যেখানে error token shift করা যায়, তারপর input থেকে token ফেলে দেয় যতক্ষণ না একটি গ্রহণযোগ্য token আসে। এটি পর্ব ৩৮-এর panic mode-এর LR রূপ। PLY-তেও একই error token আর p_error function আছে।

আরও পরিশীলিত কৌশলও আছে। Burke ও Fisher ১৯৮০-এর দশকে এমন পদ্ধতি দেন বলে পরিচিত, যা ভুলের আশপাশে ছোট সংশোধন (একটি token যোগ, মোছা বা বদল) চেষ্টা করে দেখে কোনটি সবচেয়ে বেশি দূর পর্যন্ত parse চালাতে দেয়। আধুনিক Bison-এ LAC (lookahead correction) নামের একটি বিকল্প আছে বলে জানা, যা LALR-এর অপ্রয়োজনীয় reduce-এর কারণে “expected” তালিকা ভুল হওয়ার সমস্যা কমায়। Menhir (OCaml-এর একটি LR(1) generator) প্রতিটি error state-এর জন্য হাতে লেখা বার্তা যোগ করার ব্যবস্থা রাখে।

মূল উপলব্ধি: LR parser ভুল খুব নির্ভুলভাবে ধরে, কিন্তু ভালোভাবে ব্যাখ্যা আর সামলানো আলাদা প্রকৌশল। পর্ব ৪২-এ grammar নকশার সঙ্গে error recovery-র কৌশল আবার আসবে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। lr0_items.py আর slr_parse.py ব্লকে G বদলে উত্তর যাচাই করতে পারেন।

  1. নির্মাণ: Grammar S → ( S ) ∣ x. (ক) Augment করে canonical LR(0) collection বানান। (খ) Grammar-টি কি LR(0)? (গ) SLR টেবিল ভরে “((x))”-এর shift-reduce parse লিখুন।

    State-গুলো (নিয়ম ১: S → (S), ২: S → x): I0 = {[S′ → ·S], [S → ·(S)], [S → ·x]}; I1 = goto(I0, ( ) = {[S → (·S)], [S → ·(S)], [S → ·x]}; I2 = goto(I0, S) = {[S′ → S·]}; I3 = goto(I0, x) = {[S → x·]}; I4 = goto(I1, S) = {[S → (S·)]}; I5 = goto(I4, ) ) = {[S → (S)·]}. এছাড়া goto(I1, ( ) = I1 আর goto(I1, x) = I3. মোট ৬টি state, ৭টি তীর।

    LR(0)? হ্যাঁ। প্রতিটি completed item (I2, I3, I5-এ) নিজের state-এ একা; কোনো state-এ shift আর reduce একসঙ্গে নেই।

    Parse: FOLLOW(S) = {), $}. ধাপগুলো: [0] s1 → [0 1] s1 → [0 1 1] s3 → [0 1 1 3] দেখে ) : r2 (S → x), GOTO[1, S] = 4 → [0 1 1 4] s5 → [0 1 1 4 5] দেখে ) : r1, তিনটি pop, GOTO[1, S] = 4 → [0 1 4] s5 → [0 1 4 5] দেখে $ : r1, GOTO[0, S] = 2 → [0 2] accept. ৫টি shift, ৩টি reduce. Scratch-এ slr_parse.py-র কোড এই grammar-এ চালিয়ে হুবহু এই ক্রম এসেছে; “(x”-এ state 4-এ $ পেয়ে error.

  2. প্রমাণ: উপপাদ্য ৪.২-এর প্রথম অংশ প্রমাণ করুন: canonical LR(1) টেবিলে conflict না থাকলে, একই core-এর state মিলিয়ে বানানো LALR(1) টেবিলে কোনো shift/reduce conflict থাকতে পারে না।
    1. ধরুন মেলানো state J-তে token a-তে shift/reduce conflict: কোনো item [A → α·, a] (reduce on a) আর কোনো item [B → β·aγ, b] (shift on a). — conflict-এর সংজ্ঞা
    2. J কয়েকটি LR(1) state-এর union, যাদের সবার core এক, C. Reduce item-টি এদের একটি, ধরুন K1-এ এসেছে, তাই [A → α·, a] ∈ K1. — মেলানোর সংজ্ঞা: lookahead-এর union
    3. Shift item-এর core [B → β·aγ] ∈ C, আর K1-এর core-ও C, তাই K1-এ কোনো lookahead c-সহ [B → β·aγ, c] আছে। Shift-এর সিদ্ধান্ত lookahead-এর ওপর নির্ভর করে না, শুধু বিন্দুর পরের a-র ওপর। — একই core
    4. তাহলে K1 নিজেই a-তে shift আর reduce দুটিই চায়: canonical LR(1) টেবিলে conflict, যা অনুমানের বিরোধী। ∎

    কেন reduce/reduce পারে: ধাপ ৩-এর যুক্তি reduce-এর জন্য খাটে না, কারণ reduce-এর সিদ্ধান্ত lookahead-এর ওপরই নির্ভর করে। দুই state-এ [A → c·, d], [B → c·, e] আর [A → c·, e], [B → c·, d] আলাদাভাবে নিরাপদ, কিন্তু union-এ দুই নিয়মই {d, e}-তে reduce চায় (অংশ ৪ আর PLY run).

  3. Output অনুমান: অংশ ৩-এর SLR টেবিল (expression grammar) দিয়ে “( id ) ∗ id” parse করা হলো। (ক) মোট কয়টি shift আর কয়টি reduce হবে? (খ) ) পড়ার ঠিক আগে, অর্থাৎ ACTION[·, )] দেখার মুহূর্তগুলোতে stack-এ কী কী থাকবে? (গ) শেষ reduce কোনটি?

    (ক) Token ৫টি, তাই ৫টি shift. Reduce = parse tree-র ভেতরের node: F → id, T → F, E → T, F → (E), T → F, F → id, T → T∗F, E → T, মোট ৮টি।

    (খ) ( আর id shift-এর পরে, ) পরের token থাকা অবস্থায় stack ধাপে ধাপে: 0 1 5 (r6) → 0 1 3 (r4) → 0 1 4 (r2: ) ∈ FOLLOW(E)) → 0 1 6, যেখানে ACTION[6, )] = s9. অর্থাৎ ভেতরের id পুরো E পর্যন্ত গুটিয়ে তারপর ) তোলা হয়।

    (গ) শেষ reduce r2 (E → T), stack 0 4 থেকে 0 2, তারপর accept. Scratch-এ slr_parse.py-র শেষ লাইন বদলে parse(["(", "id", ")", "*", "id"]) চালিয়ে ঠিক এই ১৪টি সারি এসেছে।

  4. নকশা: বাজারঘরের হিসাবের ছোট ভাষায় + − ∗ / আর ঘাত ^ আছে। ^ right-associative আর সবচেয়ে উঁচু, ∗ / তার নিচে, + − সবচেয়ে নিচে, সবাই বাকি left-associative. ambiguous grammar E → E op E ∣ num-এর জন্য PLY-র precedence tuple লিখুন, আর 2^3^2, 2∗3^2, 8/2/2 আর 10−4−3∗2-এর মান বলুন।

    Tuple (নিচু থেকে উঁচু): (("left", "PLUS", "MINUS"), ("left", "TIMES", "DIV"), ("right", "POW")).

    মান: 2^3^2 = 2^(3^2) = 512 (right: stack-এ E^E, পরের ^-এ সমান স্তর, right-associative তাই shift). 2∗3^2 = 2∗9 = 18 (^ উঁচু, shift). 8/2/2 = (8/2)/2 = 2 (left: reduce). 10−4−3∗2 = (10−4) − 6 = 0. সত্যিকারের run-এ (PLY 3.11, এই tuple, পূর্ণসংখ্যার ভাগ) ঠিক 512, 18, 2 আর 0 এসেছে, কোনো conflict ছাড়া, ১৩টি state.

    সাধারণ ভুল: ("right", "POW")-কে প্রথম লাইনে লেখা। তখন ^ সবচেয়ে নিচু হয়ে যায়, আর 2∗3^2 = (2∗3)^2 = 36. ঘাতকে left রাখলে 2^3^2 = 64.

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

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

ক্রমএকটি CFG থেকে SLR(1) parser বানিয়ে input parse করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. নতুন start symbol S′ আর নিয়ম S′ → S যোগ করে grammar augment করা
  2. closure({[S′ → ·S]}) থেকে শুরু করে goto দিয়ে সব LR(0) item-set বানানো
  3. প্রতিটি variable-এর FOLLOW set হিসাব করা
  4. Terminal-এর তীর থেকে shift-ঘর আর variable-এর তীর থেকে GOTO-ঘর ভরা
  5. Completed item-এর জন্য FOLLOW-এর token-এ reduce আর $-এ accept বসিয়ে conflict পরীক্ষা করা
  6. State-এর stack নিয়ে টেবিল দেখে shift-reduce parse চালানো

Grammar E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id-এর SLR parser একটি state-এ আছে, যার item [E → T·] আর [T → T·∗F]. পরের token + হলে parser কী করবে?

  • ∗ আসার অপেক্ষায় shift করবে
  • E → T দিয়ে reduce করবে
  • Conflict-এর কারণে থেমে যাবে
  • Error জানাবে

Grammar E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id. Right-sentential form “E + T ∗ id”-এর handle কোনটি?

  • E + T (নিয়ম E → E+T)
  • T ∗ id
  • T (নিয়ম E → T)
  • শেষের id (নিয়ম F → id)

Grammar-এর শ্রেণি হিসেবে কোন ক্রমটি সঠিক (⊊ মানে কঠোর অংশ)?

  • LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1)
  • LR(0) ⊊ SLR(1) ⊊ LR(1) ⊊ LALR(1)
  • LR(0) ⊊ LALR(1) ⊊ SLR(1) ⊊ LR(1)
  • চারটি শ্রেণিই সমান, শুধু টেবিলের আকার আলাদা

একটি grammar-এর canonical LR(1) টেবিলে কোনো conflict নেই। একই core-এর state মিলিয়ে LALR(1) টেবিল বানানো হলো। নতুন কোন ধরনের conflict দেখা দিতে পারে?

  • শুধু shift/reduce
  • Shift/reduce আর reduce/reduce দুটিই
  • শুধু reduce/reduce
  • কোনোটিই নয়, LALR আর LR(1) সবসময় সমান

yacc-ধাঁচের একটি generator-এ + আর ∗ দুটিই left-associative, আর ∗-এর precedence বেশি। ambiguous grammar E → E+E ∣ E∗E ∣ id-এর parser-এর stack-এ E + E, পরের token ∗. কী ঘটবে?

  • E + E গুটিয়ে E বানাবে, কারণ + left-associative
  • ∗ shift করবে, কারণ ∗-এর precedence নিয়মের শেষ terminal +-এর চেয়ে বেশি
  • Syntax error দেবে
  • দুটি পথই চালিয়ে দুটি গাছ দেবে

LR(k) grammar আর deterministic CFL (DCFL) নিয়ে কোন কথাটি সঠিক?

  • একটি language-এর কোনো LR(k) grammar আছে ঠিক তখন, যখন সেটি DCFL; তাই {wwR}-এর কোনো LR(k) grammar নেই
  • যথেষ্ট বড় k নিলে প্রতিটি CFL-এর LR(k) grammar পাওয়া যায়
  • LR(k) grammar ambiguous হতে পারে, যদি k বড় হয়
  • LR(2) language-শ্রেণি LR(1) language-শ্রেণির চেয়ে কঠোরভাবে বড়

শব্দকোষ

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

মনে রাখুন

  1. Bottom-up parser shift আর reduce দিয়ে একটি rightmost derivation উল্টো ক্রমে বানায়; প্রতিবার গুটায় handle, যা সবসময় stack-এর ওপরে।
  2. LR(0) item [A → α·β], closure আর goto দিয়ে বানানো item-set-এর DFA ঠিক viable prefix চেনে; এটি item-NFA-র subset construction.
  3. SLR(1): shift তীর থেকে, reduce FOLLOW থেকে, accept [S′ → S·]-এ $. Parse-এ reduce মানে |β|টি pop আর GOTO.
  4. LR(1) item-এ নিজস্ব lookahead; LALR(1) একই core মেলায়, যাতে নতুন reduce/reduce আসতে পারে কিন্তু shift/reduce নয়। LR(0) ⊊ SLR ⊊ LALR ⊊ LR(1); LR(k) language = DCFL.
  5. Ambiguous grammar-এর conflict precedence আর associativity মেটায়; ঘোষণা না থাকলে generator shift নেয়, যা dangling else-এ ঠিক, কিন্তু expression-এ চুপচাপ ভুল হিসাব দিতে পারে।

পরের পর্বে: Parser generator-এর পুরো জগৎ: Lark-এর EBNF grammar, Earley আর LALR, transformer দিয়ে AST, ANTLR আর PEG, আর বাজারঘরের order-query ভাষার একটি সম্পূর্ণ parser ও evaluator.

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

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