LALR পার্সিং ও পার্সার জেনারেটর

# LR0, SLR, LALR, LR1 তুলনামূলক তথ্য
comparison = {
    "lr0":  {"relative_table_size": "সবচেয়ে ছোট", "relative_power": "সবচেয়ে কম", "hand_constructible": "ছোট গ্রামারে সম্ভব (L25)"},
    "slr":  {"relative_table_size": "ছোট",          "relative_power": "মাঝারি",     "hand_constructible": "ছোট গ্রামারে সম্ভব"},
    "lalr": {"relative_table_size": "ছোট (SLR-এর কাছাকাছি)", "relative_power": "উচ্চ", "hand_constructible": "বাস্তবে প্রায় সবসময় মেশিন-জেনারেটেড"},
    "lr1":  {"relative_table_size": "সবচেয়ে বড়",   "relative_power": "সর্বোচ্চ",  "hand_constructible": "বাস্তবে প্রায় কখনো হাতে নয়"},
}
print("অ্যালগরিদম তুলনা:")
for name, info in comparison.items():
    print(f"  {name:5s} -> {info}")
print()

from collections import deque

END = "$"

# L25-এর সেই একই টয় গ্রামার -- এই লেসনের লক্ষ্য: L25-এ হাতে-যাচাই করা স্টেটগুলো
# এখন সম্পূর্ণ স্বয়ংক্রিয়ভাবে একটি পূর্ণাঙ্গ ACTION/GOTO টেবিলে রূপান্তর করা।
productions = [
    ("S'", ("S",)),
    ("S", ("(", "S", ")")),
    ("S", ("a",)),
]
nonterminals = {"S'", "S"}
terminals = {"(", ")", "a"}
start_symbol = "S'"


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


def closure(items):
    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(items, symbol):
    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 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_items(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


def compute_follow():
    """এই ছোট গ্রামারের জন্য FOLLOW সেট (L23-এর অ্যালগরিদমের একই কাঠামো)।"""
    follow = {nt: set() for nt in nonterminals}
    follow[start_symbol].add(END)
    changed = True
    while changed:
        changed = False
        for (lhs, rhs) in productions:
            for i, sym in enumerate(rhs):
                if sym not in nonterminals:
                    continue
                rest = rhs[i + 1:]
                if rest:
                    first_rest = {rest[0]}  # এই গ্রামারে rest[0] সবসময় টার্মিনাল
                    before = len(follow[sym])
                    follow[sym].update(first_rest)
                    if len(follow[sym]) != before:
                        changed = True
                else:
                    before = len(follow[sym])
                    follow[sym].update(follow[lhs])
                    if len(follow[sym]) != before:
                        changed = True
    return follow


def generate_parse_table(states, transitions):
    """স্বয়ংক্রিয় "পার্সার জেনারেটর": GOTO থেকে shift/goto, complete আইটেম + FOLLOW
    থেকে reduce/accept -- কোনো স্টেট লেখক নিজে হাতে লেখেননি।"""
    follow = compute_follow()
    action = {}
    goto_tbl = {}
    conflicts = []

    for (i, sym), j in transitions.items():
        if sym in terminals:
            key = (i, sym)
            entry = ("shift", j)
            if key in action and action[key] != entry:
                conflicts.append((key, action[key], entry))
            action[key] = entry
        else:
            goto_tbl[(i, sym)] = j

    for idx, I in enumerate(states):
        for (lhs, rhs, dot) in I:
            if dot == len(rhs):
                if lhs == start_symbol:
                    key = (idx, END)
                    entry = ("accept",)
                else:
                    for t in follow[lhs]:
                        key = (idx, t)
                        entry = ("reduce", lhs, rhs)
                        if key in action and action[key] != entry:
                            conflicts.append((key, action[key], entry))
                        action[key] = entry
                    continue
                if key in action and action[key] != entry:
                    conflicts.append((key, action[key], entry))
                action[key] = entry
    return action, goto_tbl, conflicts


states, transitions = build_lr0_automaton()
action, goto_tbl, conflicts = generate_parse_table(states, transitions)

print(f"স্বয়ংক্রিয়ভাবে জেনারেট করা স্টেট সংখ্যা: {len(states)}")
print(f"ACTION টেবিল এন্ট্রি: {len(action)}, GOTO টেবিল এন্ট্রি: {len(goto_tbl)}")
print(f"কনফ্লিক্ট: {len(conflicts)}\n")

for (i, t), entry in sorted(action.items(), key=lambda kv: (kv[0][0], str(kv[0][1]))):
    print(f"  ACTION[I{i}, '{t}'] = {entry}")
for (i, nt), j in sorted(goto_tbl.items()):
    print(f"  GOTO[I{i}, '{nt}'] = I{j}")

assert len(conflicts) == 0
assert len(states) == 6, "L25-এ হাতে-যাচাই করা ৬টি স্টেটের সাথে মিলতে হবে"
print(f"\nস্বয়ংক্রিয়ভাবে তৈরি {len(states)}টি স্টেট L25-এর হাতে-যাচাই করা স্টেট সংখ্যার সাথে মিলেছে -- OK")


def run_lr_driver(tokens):
    """জেনারেট করা টেবিল আসলেই সঠিকভাবে পার্স করে কি না তা যাচাই করার জন্য একটি
    real LR ড্রাইভার -- স্টেট গঠন মেলা যথেষ্ট নয়, এটি সত্যিই একটি ভাষা চিনতে পারা উচিত।"""
    stack = [0]
    pos = 0
    toks = tokens + [END]
    for _ in range(100):
        state = stack[-1]
        lookahead = toks[pos]
        entry = action.get((state, lookahead))
        if entry is None:
            return False
        if entry[0] == "shift":
            stack.append(lookahead)
            stack.append(entry[1])
            pos += 1
        elif entry[0] == "reduce":
            _, lhs, rhs = entry
            for _ in range(2 * len(rhs)):
                stack.pop()
            top_state = stack[-1]
            stack.append(lhs)
            stack.append(goto_tbl[(top_state, lhs)])
        elif entry[0] == "accept":
            return True
    raise RuntimeError("পার্সার থামছে না")


checks = [
    (["(", "a", ")"], True),
    (["a"], True),
    (["(", "a"], False),   # বন্ধনী বন্ধ হয়নি
    (["(", ")"], False),   # ভেতরে 'a' নেই
]
print()
for toks, expected in checks:
    got = run_lr_driver(toks)
    status = "OK" if got == expected else "FAIL"
    print(f"  parse({toks!r}) = {got}  (expected {expected})  [{status}]")
    assert got == expected

print("\nজেনারেট করা টেবিল সত্যিই সঠিকভাবে পার্স করে -- ALL OK")