LL(1) পার্সিং — FIRST ও FOLLOW সেট

# গ্রামার (L22-এর left-recursion-eliminated রূপ):
# E  ::= T E'
# E' ::= + T E' | - T E' | ε
# T  ::= F T'
# T' ::= * F T' | / F T' | ε
# F  ::= ( E ) | number

EPSILON = "ε"
END = "$"

grammar = {
    "E":  [("T", "E'")],
    "E'": [("+", "T", "E'"), ("-", "T", "E'"), (EPSILON,)],
    "T":  [("F", "T'")],
    "T'": [("*", "F", "T'"), ("/", "F", "T'"), (EPSILON,)],
    "F":  [("(", "E", ")"), ("number",)],
}
nonterminals = set(grammar.keys())
start_symbol = "E"


def compute_first(grammar):
    """প্রকৃত ফিক্সড-পয়েন্ট অ্যালগরিদম -- কোনো ফলাফল হার্ডকোড করা নেই।"""
    first = {nt: set() for nt in grammar}
    changed = True
    while changed:
        changed = False
        for nt, productions in grammar.items():
            for prod in productions:
                if prod == (EPSILON,):
                    if EPSILON not in first[nt]:
                        first[nt].add(EPSILON)
                        changed = True
                    continue
                all_derive_epsilon = True
                for sym in prod:
                    if sym not in nonterminals:
                        if sym not in first[nt]:
                            first[nt].add(sym)
                            changed = True
                        all_derive_epsilon = False
                        break
                    before = len(first[nt])
                    first[nt].update(first[sym] - {EPSILON})
                    if len(first[nt]) != before:
                        changed = True
                    if EPSILON not in first[sym]:
                        all_derive_epsilon = False
                        break
                if all_derive_epsilon:
                    if EPSILON not in first[nt]:
                        first[nt].add(EPSILON)
                        changed = True
    return first


def first_of_sequence(seq, first):
    result = set()
    all_epsilon = True
    for sym in seq:
        if sym not in nonterminals:
            result.add(sym)
            all_epsilon = False
            break
        result.update(first[sym] - {EPSILON})
        if EPSILON not in first[sym]:
            all_epsilon = False
            break
    if all_epsilon:
        result.add(EPSILON)
    return result


def compute_follow(grammar, first, start_symbol):
    follow = {nt: set() for nt in grammar}
    follow[start_symbol].add(END)
    changed = True
    while changed:
        changed = False
        for nt, productions in grammar.items():
            for prod in productions:
                if prod == (EPSILON,):
                    continue
                for i, sym in enumerate(prod):
                    if sym not in nonterminals:
                        continue
                    rest = prod[i+1:]
                    if rest:
                        first_rest = first_of_sequence(rest, first)
                        before = len(follow[sym])
                        follow[sym].update(first_rest - {EPSILON})
                        if EPSILON in first_rest:
                            follow[sym].update(follow[nt])
                        if len(follow[sym]) != before:
                            changed = True
                    else:
                        before = len(follow[sym])
                        follow[sym].update(follow[nt])
                        if len(follow[sym]) != before:
                            changed = True
    return follow


first_sets = compute_first(grammar)
follow_sets = compute_follow(grammar, first_sets, start_symbol)

print("FIRST সেট:")
for nt in ["E", "E'", "T", "T'", "F"]:
    print(f"  FIRST({nt}) = {sorted(first_sets[nt])}")

print("\nFOLLOW সেট:")
for nt in ["E", "E'", "T", "T'", "F"]:
    print(f"  FOLLOW({nt}) = {sorted(follow_sets[nt])}")

# হাতে-যাচাই: FIRST(F) = {'(', 'number'} -- কারণ <factor>-এর দুটি বিকল্পই এই দুটি দিয়ে শুরু
assert first_sets["F"] == {"(", "number"}
# হাতে-যাচাই: FOLLOW(F) -- F-এর পরে T' আসে, যা * বা / দিয়ে শুরু হতে পারে অথবা ε (তখন FOLLOW(T) বসে)
assert follow_sets["F"] == {"*", "/", "+", "-", END, ")"}
print("\nহাতে-করা যাচাই (FIRST(F), FOLLOW(F)) মিলেছে -- PASSED")

# LL(1) টেবিল তৈরি
table = {}
conflicts = []
for nt, productions in grammar.items():
    for prod in productions:
        first_alpha = {EPSILON} if prod == (EPSILON,) else first_of_sequence(prod, first_sets)
        for t in first_alpha - {EPSILON}:
            key = (nt, t)
            if key in table and table[key] != prod:
                conflicts.append(key)
            table[key] = prod
        if EPSILON in first_alpha:
            for t in follow_sets[nt]:
                key = (nt, t)
                if key in table and table[key] != prod:
                    conflicts.append(key)
                table[key] = prod

print(f"\nLL(1) টেবিলে মোট এন্ট্রি: {len(table)}")
print(f"কনফ্লিক্ট পাওয়া গেছে: {len(conflicts)}")
assert len(conflicts) == 0
print("গ্রামারটি নিশ্চিতভাবে LL(1) -- কোনো টেবিল সেলে একাধিক নিয়ম নেই")