কেস স্টাডি: বাস্তব রেগেক্স ইঞ্জিন ও তাদের সীমাবদ্ধতা

# অংশ A -- DFA-ভিত্তিক matcher (M2/L11-এর Kleene পাইপলাইন) -- লিনিয়ার-টাইম, ব্যাকরেফারেন্স অসম্ভব

def regex_to_nfa(node, counter):
    kind = node[0]
    if kind == 'lit':
        s0, s1 = next(counter), next(counter)
        return {s0, s1}, s0, {s1}, {(s0, node[1]): {s1}}, {}
    if kind == 'union':
        Q1, s1, F1, D1, E1 = regex_to_nfa(node[1], counter)
        Q2, s2, F2, D2, E2 = regex_to_nfa(node[2], counter)
        s0, sf = next(counter), next(counter)
        eps = {k: set(v) for k, v in E1.items()}
        for k, v in E2.items(): eps.setdefault(k, set()).update(v)
        eps.setdefault(s0, set()).update({s1, s2})
        for f in F1: eps.setdefault(f, set()).add(sf)
        for f in F2: eps.setdefault(f, set()).add(sf)
        return Q1 | Q2 | {s0, sf}, s0, {sf}, {**D1, **D2}, eps
    if kind == 'concat':
        Q1, s1, F1, D1, E1 = regex_to_nfa(node[1], counter)
        Q2, s2, F2, D2, E2 = regex_to_nfa(node[2], counter)
        eps = {k: set(v) for k, v in E1.items()}
        for k, v in E2.items(): eps.setdefault(k, set()).update(v)
        for f in F1: eps.setdefault(f, set()).add(s2)
        return Q1 | Q2, s1, F2, {**D1, **D2}, eps
    if kind == 'star':
        Q1, s1, F1, D1, E1 = regex_to_nfa(node[1], counter)
        s0, sf = next(counter), next(counter)
        eps = {k: set(v) for k, v in E1.items()}
        eps.setdefault(s0, set()).update({s1, sf})
        for f in F1: eps.setdefault(f, set()).update({s1, sf})
        return Q1 | {s0, sf}, s0, {sf}, D1, eps
    raise ValueError(node)

def eps_closure(states, eps):
    stack, result = list(states), set(states)
    while stack:
        q = stack.pop()
        for nxt in eps.get(q, ()):
            if nxt not in result:
                result.add(nxt); stack.append(nxt)
    return frozenset(result)

def subset_construction(alphabet, start, accept, D, eps):
    start_set = eps_closure({start}, eps)
    dfa_states, dfa_trans, dfa_accept = {start_set}, {}, set()
    frontier = [start_set]
    while frontier:
        S = frontier.pop()
        if S & accept: dfa_accept.add(S)
        for a in alphabet:
            nxt = set()
            for q in S: nxt |= D.get((q, a), set())
            nxt = eps_closure(nxt, eps)
            dfa_trans[(S, a)] = nxt
            if nxt not in dfa_states:
                dfa_states.add(nxt); frontier.append(nxt)
    return dfa_states, start_set, dfa_accept, dfa_trans

class DFAMatcher:
    def __init__(self, regex_ast, alphabet):
        counter = iter(range(10**6))
        Q, s0, F, D, eps = regex_to_nfa(regex_ast, counter)
        self.states, self.start, self.accept, self.trans = subset_construction(alphabet, s0, F, D, eps)
    def matches(self, s):
        steps, state = 0, self.start
        for ch in s:
            steps += 1
            state = self.trans.get((state, ch), frozenset())
        return (state in self.accept), steps

# regex (a|b)*abb -- ক্লাসিক "abb-তে শেষ হওয়া" -- একটি সত্যিকারের রেগুলার ভাষা
regex_ast = ('concat', ('star', ('union', ('lit', 'a'), ('lit', 'b'))),
             ('concat', ('lit', 'a'), ('concat', ('lit', 'b'), ('lit', 'b'))))
dfa_matcher = DFAMatcher(regex_ast, {'a', 'b'})

print("== DFA matcher: (a|b)*abb ==")
for s in ["abb", "aababb", "ab", "abbb", "bbb", ""]:
    ok, steps = dfa_matcher.matches(s)
    print(f"  {s!r:10} -> {'accept' if ok else 'reject':7} steps={steps}")

# অংশ B -- ব্যাকট্র্যাকিং matcher, group + backreference সাপোর্টসহ
def bt_match(ast, s):
    steps = [0]
    groups = {}
    def m(node, pos, cont):
        steps[0] += 1
        kind = node[0]
        if kind == 'lit':
            return cont(pos + 1) if pos < len(s) and s[pos] == node[1] else False
        if kind == 'any':
            return cont(pos + 1) if pos < len(s) else False
        if kind == 'concat':
            nodes = node[1]
            def build(i):
                return cont if i == len(nodes) else (lambda p: m(nodes[i], p, build(i + 1)))
            return build(0)(pos)
        if kind == 'star':
            inner = node[1]
            def try_repeat(p):
                def after_inner(p2):
                    # শূন্য-দৈর্ঘ্যের পুনরাবৃত্তি -- অসীম লুপ এড়াতে থামুন (বাস্তব ইঞ্জিনও এই গার্ড ব্যবহার করে)
                    return cont(p2) if p2 == p else try_repeat(p2)
                return True if m(inner, p, after_inner) else cont(p)
            return try_repeat(pos)
        if kind == 'group':
            gid, inner = node[1], node[2]
            start = pos
            def after(p):
                old = groups.get(gid)
                groups[gid] = s[start:p]
                if cont(p): return True
                groups[gid] = old if old is not None else groups.pop(gid, None)
                return False
            return m(inner, pos, after)
        if kind == 'backref':
            captured = groups.get(node[1], '')
            return cont(pos + len(captured)) if s[pos:pos + len(captured)] == captured else False
        raise ValueError(node)
    return m(ast, 0, lambda p: p == len(s)), steps[0]

# {ww} ভাষার জন্য প্যাটার্ন -- (group any*) ব্যাকরেফারেন্স \1 -- DFA প্রকাশ করতে পারে না
ww_ast = ('concat', [('group', 1, ('star', ('any',))), ('backref', 1)])

print()
print("== ব্যাকট্র্যাকিং matcher: (গ্রুপ any*)\\1  অর্থাৎ {ww} ভাষা ==")
for s in ["abab", "abcabc", "aa", "a", "", "aabb", "xyzxyz", "xyzxy"]:
    ok, steps = bt_match(ww_ast, s)
    print(f"  {s!r:10} -> {'accept' if ok else 'reject':7} steps={steps}")

# ক্যাটাস্ট্রফিক ব্যাকট্র্যাকিং -- (a*)*b প্যাটার্ন, উপরের bt_match() পুনরায় ব্যবহার করে
# ধরে নেওয়া হচ্ছে bt_match() ও AST নোড-টাইপ আগের কোড সেল থেকে ইতিমধ্যে সংজ্ঞায়িত

evil_ast = ('concat', [('star', ('group', 1, ('star', ('lit', 'a')))), ('lit', 'b')])

print("== ক্যাটাস্ট্রফিক ব্যাকট্র্যাকিং: (a*)*b ==")
print(f"{'n':>4} | ভালো ইনপুট (ম্যাচ হয়) ধাপ | খারাপ ইনপুট (ম্যাচ হয় না) ধাপ")
print("-" * 62)
for n in [5, 10, 15, 20]:
    good = "a" * n + "b"   # সাধারণ, দ্রুত ম্যাচ হয়
    evil = "a" * n + "c"   # কোনো 'b' নেই -- ইঞ্জিন প্রতিটি সম্ভাব্য a-বিভাজন চেষ্টা করে
    _, steps_good = bt_match(evil_ast, good)
    _, steps_evil = bt_match(evil_ast, evil)
    print(f"{n:>4} | {steps_good:>20} | {steps_evil:>24}")