LR পার্সিং — LR(0) ও SLR আইটেম

from collections import deque

# টয় গ্রামার (ইচ্ছাকৃতভাবে ছোট, হাতে-যাচাই করার জন্য), অগমেন্টেড স্টার্ট প্রোডাকশনসহ:
#   S' ::= S      (অগমেন্টেড স্টার্ট প্রোডাকশন)
#   S  ::= ( S )
#   S  ::= a
productions = [
    ("S'", ("S",)),
    ("S", ("(", "S", ")")),
    ("S", ("a",)),
]
nonterminals = {"S'", "S"}


def productions_of(nt):
    return [p for p in productions if p[0] == nt]


def closure(items):
    """CLOSURE(I): ডটের ঠিক পরে নন-টার্মিনাল থাকলে সেই নন-টার্মিনালের সব প্রোডাকশন
    ডট-at-start সহ যোগ করো, ফিক্সড-পয়েন্ট পর্যন্ত।"""
    items = set(items)
    changed = True
    while changed:
        changed = False
        for (lhs, rhs, dot) in list(items):
            if dot < len(rhs):
                sym = rhs[dot]
                if sym in nonterminals:
                    for (plhs, prhs) in productions_of(sym):
                        new_item = (plhs, prhs, 0)
                        if new_item not in items:
                            items.add(new_item)
                            changed = True
    return frozenset(items)


def goto(items, symbol):
    """GOTO(I, X): I-এর যেসব আইটেমে ডটের ঠিক পরে X আছে, সেগুলোতে ডট এক ঘর এগিয়ে
    নিয়ে CLOSURE নাও -- এটাই একটি নতুন স্টেট (বা বিদ্যমান কোনো স্টেট)।"""
    moved = {(lhs, rhs, dot + 1) for (lhs, rhs, dot) in items
             if dot < len(rhs) and rhs[dot] == symbol}
    return closure(moved) if moved else None


def format_item(item):
    lhs, rhs, dot = item
    parts = list(rhs)
    parts.insert(dot, ".")
    return f"{lhs} -> {' '.join(parts)}"


def all_symbols():
    syms = set()
    for (_, rhs) in productions:
        syms.update(rhs)
    return syms


def build_lr0_automaton():
    I0 = closure({("S'", ("S",), 0)})
    states = [I0]
    state_index = {I0: 0}
    transitions = {}
    queue = deque([I0])
    while queue:
        I = queue.popleft()
        i_idx = state_index[I]
        for sym in sorted(all_symbols()):
            J = goto(I, sym)
            if J is None:
                continue
            if J not in state_index:
                state_index[J] = len(states)
                states.append(J)
                queue.append(J)
            transitions[(i_idx, sym)] = state_index[J]
    return states, transitions


states, transitions = build_lr0_automaton()

print(f"মোট LR(0) স্টেট: {len(states)}\n")
for idx, I in enumerate(states):
    print(f"I{idx}:")
    for item in sorted(I, key=format_item):
        print(f"  {format_item(item)}")
    print()

print("ট্রানজিশন:")
for (i, sym), j in sorted(transitions.items()):
    print(f"  GOTO(I{i}, '{sym}') = I{j}")

# ---- হাতে-করা যাচাই ----
# I0-এ থাকা উচিত: S' -> .S, S -> .(S), S -> .a (CLOSURE প্রয়োগ করে)
expected_I0 = frozenset({
    ("S'", ("S",), 0),
    ("S", ("(", "S", ")"), 0),
    ("S", ("a",), 0),
})
assert states[0] == expected_I0
print("\nI0 = closure({S' -> .S}) হাতে-যাচাই মিলেছে: OK")

# GOTO(I0, '(') -> S -> (.S) এর CLOSURE, যেখানে আবার S->.( S ) ও S->.a যোগ হয়
expected_goto_paren = frozenset({
    ("S", ("(", "S", ")"), 1),
    ("S", ("(", "S", ")"), 0),
    ("S", ("a",), 0),
})
i1 = transitions[(0, "(")]
assert states[i1] == expected_goto_paren
print(f"GOTO(I0,'(') = I{i1} হাতে-যাচাই মিলেছে: OK")

# GOTO(I0, 'a') -> S -> a. (dot at end, reduce state)
expected_goto_a = frozenset({("S", ("a",), 1)})
i3 = transitions[(0, "a")]
assert states[i3] == expected_goto_a
print(f"GOTO(I0,'a') = I{i3} হাতে-যাচাই মিলেছে: OK")

# GOTO(I0, 'S') -> S' -> S. (accepting state)
expected_goto_S = frozenset({("S'", ("S",), 1)})
i2 = transitions[(0, "S")]
assert states[i2] == expected_goto_S
print(f"GOTO(I0,'S') = I{i2} (accepting state) হাতে-যাচাই মিলেছে: OK")

# I1 (= GOTO(I0,'(')) নিজের উপর সেল্ফ-লুপ করে '(' দিয়ে -- একই আইটেম-সেট আবার তৈরি হয়
assert transitions[(i1, "(")] == i1
print(f"GOTO(I{i1},'(') == I{i1} (সেল্ফ-লুপ, নেস্টেড বন্ধনীর জন্য) হাতে-যাচাই মিলেছে: OK")

assert len(states) == 6
print(f"\nমোট স্টেট সংখ্যা = {len(states)} -- প্রথম কয়েকটি স্টেট হাতে-করা ট্রেসের সাথে সম্পূর্ণ মিলেছে")