BNF ও EBNF নোটেশন

১ · BNF (Backus-Naur Form) কী

BNFBackus-Naur Formকনটেক্সট-ফ্রি গ্রামারের প্রোডাকশন রুল লেখার স্ট্যান্ডার্ড, ক্লাসিক নোটেশন — <nonterminal> ::= expansion আকারে লেখা হয়। হলো L11-এ পরিচিত হওয়া গ্রামারের রুলগুলো লেখার একটি স্ট্যান্ডার্ড নোটেশন। প্রতিটি BNF রুলের আকার —

<nonterminal> ::= expansion

যেখানে ::=-এর ডানদিকের expansion হলো টার্মিনাল (আক্ষরিক সিম্বল, যেমন + বা if) ও/অথবা নন-টার্মিনাল-এর (অ্যাংগেল ব্র্যাকেটে লেখা প্লেসহোল্ডার, যেমন <expr>, যা অন্য কোনো রুলে আরও বিস্তারিতভাবে সংজ্ঞায়িত থাকে) একটি সিকোয়েন্স। যখন একই নন-টার্মিনালের একাধিক বৈধ এক্সপ্যানশন থাকে, সেগুলো | চিহ্ন দিয়ে আলাদা করে একই রুলে লেখা হয় — প্রতিটি |-এর দুই পাশ একটি করে বিকল্প (alternative)।

২ · Worked example — একটি arithmetic expression গ্রামার

নিচের গ্রামারটি একটি ক্লাসিক, স্ট্যান্ডার্ড টেক্সটবুক উদাহরণ — সাধারণ গাণিতিক এক্সপ্রেশনের সিনট্যাক্স বর্ণনা করে। এই ঠিক গ্রামারটি নোট করে রাখুন — এটি এই কোর্সের M5 (পার্সিং) মডিউলের প্রায় প্রতিটি পাঠে বারবার পুনরায় ব্যবহৃত হবে।

$$\langle expr \rangle ::= \langle expr \rangle\ {+}\ \langle term \rangle \mid \langle expr \rangle\ {-}\ \langle term \rangle \mid \langle term \rangle$$ $$\langle term \rangle ::= \langle term \rangle\ {*}\ \langle factor \rangle \mid \langle term \rangle\ {/}\ \langle factor \rangle \mid \langle factor \rangle$$ $$\langle factor \rangle ::= ({\ }\langle expr \rangle{\ }) \mid \text{number}$$

৩ · EBNF (Extended BNF) — নোটেশনাল সুবিধা, নতুন ক্ষমতা নয়

EBNFExtended BNFপ্লেইন BNF-এর উপর সুবিধাজনক শর্টহ্যান্ড যোগ করা একটি নোটেশন — কোনো নতুন এক্সপ্রেসিভ পাওয়ার যোগ করে না, শুধু পড়া/লেখা সহজ করে। সাধারণ কিছু প্যাটার্ন (ঐচ্ছিক অংশ, পুনরাবৃত্তি) প্লেইন BNF-এ বারবার একই রিকার্সিভ প্যাটার্ন লিখতে বাধ্য করে। EBNF তিনটি শর্টহ্যান্ড যোগ করে —

গুরুত্বপূর্ণ কথা — EBNF কোনো নতুন এক্সপ্রেসিভ পাওয়ার যোগ করে না। EBNF-এ লেখা যেকোনো কিছু যান্ত্রিকভাবে প্লেইন BNF-এ রূপান্তরযোগ্য। যেমন {X}-কে একটি রিকার্সিভ প্লেইন-BNF রুল দিয়ে ঠিক সমতুল্যভাবে লেখা যায় —

list ::= { item }  ⟺  list ::= item list | ε

(এখানে ε মানে খালি স্ট্রিং — "কিছুই না।") নিচের কোড সেলে এই যান্ত্রিক রূপান্তরটি আসলে বাস্তবায়ন করে দেখানো হবে।

# EBNF-এর { item } (পুনরাবৃত্তি) কে সমতুল্য প্লেইন-BNF রুলে রূপান্তর

def ebnf_repetition_to_bnf(nonterminal, item_symbol):
    """
    EBNF শর্টহ্যান্ড { item } -কে প্লেইন-BNF রুলে রূপান্তর করে।
    রুল = (lhs, [alt1, alt2, ...]) -- প্রতিটি alt একটি সিম্বলের টাপল, () মানে ε
    list ::= item list | ε
    """
    return (nonterminal, [
        (item_symbol, nonterminal),  # বিকল্প ১: item তারপর বাকি list
        ()                           # বিকল্প ২: ε -- তালিকা এখানেই শেষ
    ])

def matches_ebnf_repetition(tokens, item_symbol):
    # EBNF { item } -- সরাসরি: প্রতিটি টোকেন item-এর সাথে মেলে কিনা
    return all(tok == item_symbol for tok in tokens)

def matches_bnf_rule(tokens, item_symbol):
    # জেনারেট করা প্লেইন-BNF রুল (list ::= item list | ε) রিকার্সিভভাবে যাচাই
    if not tokens:
        return True  # বিকল্প ২: ε প্রযোজ্য
    if tokens[0] == item_symbol:
        return matches_bnf_rule(tokens[1:], item_symbol)  # বিকল্প ১
    return False

rule = ebnf_repetition_to_bnf("list", "item")

lhs, alternatives = rule
print("জেনারেট করা প্লেইন-BNF রুল:")
for i, alt in enumerate(alternatives):
    rhs = " ".join(alt) if alt else "ε"
    print(f"  {lhs} {'::=' if i == 0 else '|  '} {rhs}")

test_cases = [[], ["item"], ["item", "item"], ["item", "item", "item"], ["item", "x"]]

print("\nEBNF { item } বনাম জেনারেট করা প্লেইন-BNF রুল -- তুলনা:")
for tc in test_cases:
    ebnf_ok = matches_ebnf_repetition(tc, "item")
    bnf_ok = matches_bnf_rule(tc, "item")
    same = "একমত ✓" if ebnf_ok == bnf_ok else "MISMATCH ✗"
    print(f"  {str(tc):32s} EBNF={ebnf_ok!s:5s} BNF={bnf_ok!s:5s} {same}")