পার্স ট্রি ও অ্যাম্বিগুইটি (থিওরি)

# ইনহেরেন্ট অ্যাম্বিগুইটি concretely দেখানো -- একটি combined গ্রামারে দুটো ভিন্ন derivation খোঁজা
from collections import deque

class Grammar:
    def __init__(self, variables, terminals, rules, start):
        self.V = set(variables)
        self.T = set(terminals)
        self.rules = rules
        self.S = start

def derive_leftmost_all(grammar, start, target, max_steps=60, max_solutions=5):
    """L17-এর derive_leftmost-এর সম্প্রসারণ -- প্রথমটিতে না থেমে একাধিক ভিন্ন derivation খোঁজে"""
    queue = deque([((start,), [(start,)])])
    solutions = []
    while queue and len(solutions) < max_solutions:
        form, history = queue.popleft()
        if len(history) - 1 > max_steps:
            continue
        idx = next((i for i, sym in enumerate(form) if sym in grammar.V), None)
        if idx is None:
            if ''.join(form) == target:
                solutions.append(history)
            continue
        prefix = ''.join(form[:idx])
        if not target.startswith(prefix):
            continue
        var = form[idx]
        for rhs in grammar.rules.get(var, []):
            new_form = form[:idx] + rhs + form[idx + 1:]
            terms = []
            for s in new_form:
                if s in grammar.V:
                    break
                terms.append(s)
            if not target.startswith(''.join(terms)):
                continue
            if len(new_form) > len(target) + 6:
                continue
            queue.append((new_form, history + [new_form]))
    return solutions

# শাখা ১: A1 C1 -- A1 প্রোডিউস করে a^i b^i (i=j), C1 প্রোডিউস করে c^k (k স্বাধীন)
# শাখা ২: A2 B2 -- A2 প্রোডিউস করে a^i (i স্বাধীন), B2 প্রোডিউস করে b^j c^j (j=k)
V = {'S', 'S1', 'A1', 'C1', 'S2', 'A2', 'B2'}
T = {'a', 'b', 'c'}
rules = {
    'S':  [('S1',), ('S2',)],       # S -> S1 | S2  (দুই শাখার মধ্যে নন-ডিটারমিনিস্টিক বাছাই)
    'S1': [('A1', 'C1')],
    'A1': [('a', 'A1', 'b'), ()],   # A1 -> a A1 b | epsilon   (i=j নিশ্চিত করে)
    'C1': [('c', 'C1'), ()],        # C1 -> c C1 | epsilon     (k স্বাধীন)
    'S2': [('A2', 'B2')],
    'A2': [('a', 'A2'), ()],        # A2 -> a A2 | epsilon     (i স্বাধীন)
    'B2': [('b', 'B2', 'c'), ()],   # B2 -> b B2 c | epsilon   (j=k নিশ্চিত করে)
}
G = Grammar(V, T, rules, 'S')

target = "aabbcc"   # i=j=k=2 -- উভয় শর্তই সত্য
solutions = derive_leftmost_all(G, 'S', target, max_steps=40, max_solutions=5)

print(f"'{target}' -- {len(solutions)}টি ভিন্ন leftmost derivation পাওয়া গেছে\n")
for n, hist in enumerate(solutions, 1):
    print(f"--- derivation {n} ---")
    for form in hist:
        print("  ⇒", ''.join(form) if form else 'ε')
    print()

print("সিদ্ধান্ত:", "AMBIGUOUS on this string" if len(solutions) > 1 else "unambiguous on this string")