কনটেক্সট-ফ্রি গ্রামার ও ডেরিভেশন

<expr>
  ⇒ <expr> + <term>              (expr ::= expr + term)
  ⇒ <term> + <term>              (expr ::= term)
  ⇒ <factor> + <term>            (term ::= factor)
  ⇒ 2 + <term>                    (factor ::= number [= 2])
  ⇒ 2 + <term> * <factor>        (term ::= term * factor)
  ⇒ 2 + <factor> * <factor>      (term ::= factor)
  ⇒ 2 + 3 * <factor>              (factor ::= number [= 3])
  ⇒ 2 + 3 * 4                      (factor ::= number [= 4])

# একটি real leftmost-derivation-search -- L12-এর গ্রামার দিয়ে
# টার্গেট টোকেন লিস্ট থেকে একটি বৈধ leftmost derivation খুঁজে বের করে

grammar = {
    '<expr>':   [('<expr>', '+', '<term>'), ('<expr>', '-', '<term>'), ('<term>',)],
    '<term>':   [('<term>', '*', '<factor>'), ('<term>', '/', '<factor>'), ('<factor>',)],
    '<factor>': [('(', '<expr>', ')'), ('number',)],
}
NONTERMINALS = set(grammar.keys())

def symbol_matches(symbol, token):
    # 'number' একটি টার্মিনাল "ক্যাটেগরি" -- যেকোনো ডিজিট-টোকেনের সাথে মেলে
    if symbol == 'number':
        return token.isdigit()
    return symbol == token

def terminals_match(seq, target_slice):
    if len(seq) != len(target_slice):
        return False
    return all(symbol_matches(s, t) for s, t in zip(seq, target_slice))

def leftmost_derive(grammar, start, target, max_calls=5000):
    """
    সবচেয়ে বামের নন-টার্মিনাল বারবার এক্সপ্যান্ড করে একটি ডেরিভেশন খোঁজে (backtracking সহ)।
    প্রতিটি সেন্টেনশিয়াল ফর্মের length target-এর length ছাড়িয়ে গেলে prune করে দেয় --
    যেহেতু এই গ্রামারে কোনো ε-প্রোডাকশন নেই, একটি ফর্মের length কখনো কমতে পারে না।
    """
    calls = [0]

    def search(form, steps):
        calls[0] += 1
        if calls[0] > max_calls or len(form) > len(target):
            return None
        idx = next((i for i, s in enumerate(form) if s in NONTERMINALS), None)
        if idx is None:
            return steps if terminals_match(form, target) else None
        if not terminals_match(form[:idx], target[:idx]):
            return None  # ইতিমধ্যে ফাইনালাইজড prefix টার্গেটের সাথে মেলে না -- ডেড ব্রাঞ্চ
        nt = form[idx]
        for alt in grammar[nt]:
            new_form = form[:idx] + list(alt) + form[idx + 1:]
            rule = f"{nt} ::= {' '.join(alt) if alt else 'ε'}"
            result = search(new_form, steps + [(rule, list(new_form))])
            if result is not None:
                return result
        return None

    return search([start], [])

target = ['2', '+', '3']
derivation = leftmost_derive(grammar, '<expr>', target)

if derivation is None:
    print("কোনো derivation পাওয়া যায়নি।")
else:
    print(f"টার্গেট: {target}  →  leftmost derivation পাওয়া গেছে ({len(derivation)} ধাপ):\n")
    form = ['<expr>']
    print(f"  {' '.join(form)}")
    for rule, new_form in derivation:
        print(f"    ⇒ {' '.join(new_form):25s} [{rule}]")
    print(f"\nচূড়ান্ত ফর্ম টার্গেট টোকেনের সাথে মিলছে: {terminals_match(derivation[-1][1], target)}")