লেক্সিক্যাল স্পেসিফিকেশনের জন্য রেগুলার এক্সপ্রেশন

# regex AST নোড: ('char', c) | ('concat', r1, r2) | ('union', r1, r2) | ('star', r)
# পাইথনের re মডিউল ব্যবহার করা হয়নি -- একদম হাতে-লেখা রিকার্সিভ ম্যাচার

def match_positions(node, s, start):
    """node প্যাটার্নটি s-এর start পজিশন থেকে যত পজিশন পর্যন্ত পৌঁছাতে পারে তার সেট।"""
    kind = node[0]
    if kind == 'char':
        c = node[1]
        if start < len(s) and s[start] == c:
            return {start + 1}
        return set()
    if kind == 'concat':
        left, right = node[1], node[2]
        result = set()
        for p in match_positions(left, s, start):
            result |= match_positions(right, s, p)
        return result
    if kind == 'union':
        left, right = node[1], node[2]
        return match_positions(left, s, start) | match_positions(right, s, start)
    if kind == 'star':
        inner = node[1]
        reachable = {start}
        frontier = {start}
        while frontier:
            new_positions = set()
            for p in frontier:
                for q in match_positions(inner, s, p):
                    if q not in reachable:
                        new_positions.add(q)
            frontier = new_positions
            reachable |= new_positions
        return reachable
    raise ValueError(f"অজানা নোড: {kind}")

def matches(node, s):
    return len(s) in match_positions(node, s, 0)

def union_of_chars(chars):
    node = ('char', chars[0])
    for c in chars[1:]:
        node = ('union', node, ('char', c))
    return node

letters = "abcdefghijklmnopqrstuvwxyz"
digits = "0123456789"
LETTER = union_of_chars(letters)
DIGIT = union_of_chars(digits)

# IDENTIFIER = letter (letter|digit)*
IDENTIFIER = ('concat', LETTER, ('star', ('union', LETTER, DIGIT)))
# NUMBER = digit digit*  (অর্থাৎ digit+)
NUMBER = ('concat', DIGIT, ('star', DIGIT))

print("IDENTIFIER প্যাটার্ন পরীক্ষা:")
for s in ["x", "x1", "total", "a1b2c3", "1x", "", "1"]:
    print(f"  matches(IDENTIFIER, {s!r}) = {matches(IDENTIFIER, s)}")

print("\nNUMBER প্যাটার্ন পরীক্ষা:")
for s in ["42", "0", "007", "", "4x", "x4"]:
    print(f"  matches(NUMBER, {s!r}) = {matches(NUMBER, s)}")