সিনট্যাক্টিক পার্সিং হলো শব্দের একমাত্রিক রৈখিক অনুক্রম থেকে তার অন্তর্নিহিত ব্যাকরণিক বৃক্ষাকার কাঠামো নির্ণয়ের কম্পিউটেশনাল অ্যালগরিদম। প্রাকৃতিক ভাষার পদে পদে কাঠামোগত দ্ব্যর্থকতা (Ambiguity) থাকায় সাধারণ সার্চ অ্যালগরিদম সূচকীয় সময়ে আটকে যায়। ডায়নামিক প্রোগ্রামিং চার্ট পার্সার বহুপদী সময়ে এর নিখুঁত গাণিতিক সমাধান নিশ্চিত করে।

১. সিনট্যাক্টিক দ্ব্যর্থকতা ও কাতালান সংখ্যা

একটি বাক্যে একাধিক অনুসর্গ যুক্ত থাকলে বিভিন্ন ব্যাকরণিক ব্যাখ্যা তৈরি হয়—যেমন “টেলিস্কোপ দিয়ে লোকটিকে দেখলাম”। এখানে টেলিস্কোপ কি দেখার যন্ত্র নাকি লোকটির হাতে ছিল? একাধিক অনুসর্গ থাকলে সম্ভাব্য পার্স ট্রির সংখ্যা কাতালান সংখ্যা ((C_k sim 4^k)) অনুযায়ী সূচকীয় হারে বৃদ্ধি পায়, যা সাধারণ ব্যাকট্র্যাকিং দিয়ে সমাধান অসম্ভব করে তোলে।

২. চমস্কি নরমাল ফর্ম (CNF)

CYK অ্যালগরিদম প্রয়োগের পূর্বে ব্যাকরণকে চমস্কি নরমাল ফর্মে (CNF) রূপান্তর করতে হয়, যেখানে প্রতিটি নিয়ম কেবল দুটি নন-টার্মিনাল অথবা একটিমাত্র টার্মিনাল ধারণ করে:

[
A o B C quad ext{বা} quad A o a
]

৩. কক-ইয়ংগার-কাসামি (CYK) ডায়নামিক অ্যালগরিদম

CYK অ্যালগরিদম একটি ত্রিভুজাকার ডায়নামিক প্রোগ্রামিং টেবিল (T[i, j]) পূরণ করে এগিয়ে যায়:

  1. বেস কেস: প্রতিটি একক শব্দের জন্য ব্যাকরণিক ট্যাগ নির্ণয় ((T[i-1, i]))।
  2. রিকার্সিভ স্টেপ: ক্ষুদ্রাংশের দৈর্ঘ্য ২ থেকে শুরু করে বাক্যদৈর্ঘ্য (n) পর্যন্ত প্রতিটি বিভাজন বিন্দু (k)-এর জন্য নিয়ম পরীক্ষা:
    [
    T[i, j] = bigcup_{k} { A mid A o B C, B in T[i, k], C in T[k, j] }
    ]
  3. সমাপ্তি: শীর্ষ নোডে যদি ব্যাকরণের শুরুর প্রতীক (S) থাকে, তবে বাক্যটি ব্যাকরণগতভাবে সঠিক।

তিনটি নেস্টেড লুপ থাকার কারণে CYK অ্যালগরিদমের টাইম কমপ্লেক্সিটি নিশ্চিতভাবে কিউবিক বা ঘনকাকার: (mathcal{O}(n^3 cdot |P|))।

৪. ডিপেনডেন্সি পার্সিং ও রৈখিক সময়

আধুনিক শিল্পক্ষেত্রে বাক্যের গঠনের চেয়ে শব্দের সাথে শব্দের সরাসরি নির্ভরশীলতা (Head-Dependent Relation) নির্ণয়কারী ডিপেনডেন্সি পার্সার বেশি ব্যবহৃত হয়। ট্রানজিশন-বেসড অ্যালগরিদম (Shift, Left-Arc, Right-Arc) নিউরাল নেটওয়ার্কের সহায়তায় সম্পূর্ণ রৈখিক সময়ে ((mathcal{O}(n))) নির্ভুলভাবে ডিপেনডেন্সি গ্রাফ তৈরি করতে সক্ষম।

শাকিল মাহমুদ সজল

শাকিল মাহমুদ সজল

সফটওয়্যার প্রকৌশলী ও লেখক, ঢাকা, বাংলাদেশ। কম্পিউটার বিজ্ঞান, পদার্থবিজ্ঞান, ইতিহাস ও ভাবনার সমন্বয়ে ব্যক্তিগত নোট ও প্রবন্ধ সংকলন।