প্রসঙ্গমুক্ত ব্যাকরণ

ভাষাবিজ্ঞান এবং কম্পিউটার বিজ্ঞানে প্রসঙ্গমুক্ত ব্যাকরণ (ইংরেজি: Context-free grammar বা সংক্ষেপে CFG) হচ্ছে একটি বিধিগত ব্যাকরণ (formal grammar) যেখানে প্রতিটি উৎপাদনী সূত্র (production rule) নিম্নোক্ত রূপের হয়-

V → w

যেখানে V একটি অসমাপ্তিজ্ঞাপক প্রতীক (nonterminal symbol) এবং w হচ্ছে সমাপ্তিজ্ঞাপক (terminal symbol) ও/অথবা অসমাপ্তিজ্ঞাপক প্রতীক দিয়ে গঠিত একটি স্ট্রিং। "প্রসঙ্গমুক্ত" (context-free) পরিভাষাটি দিয়ে বোঝানো হচ্ছে যে অসমাপ্তিজ্ঞাপক V-কে সর্বদাই w দিয়ে প্রতিস্থাপিত করা যাবে, সেটি যে প্রসঙ্গেই ঘটুক না কেন। একটি বিধিগত ভাষা (formal language) যদি কোন প্রসঙ্গমুক্ত ব্যাকরণ থেকে উৎপাদন বা সৃষ্টি (generate) করা হয়, তবে তাকে প্রসঙ্গমুক্ত ভাষা (context-free language) বলা হয়।

প্রসঙ্গমুক্ত ব্যাকরণ একটি শক্তিশালী ধারণা এবং এর সাহায্যে বেশির ভাগ প্রোগ্রামিং ভাষার সিনট্যাক্স বর্ণনা করা যায় এবং তা-ই বাস্তবে ঘটেছে। কিন্তু প্রসঙ্গমুক্ত ব্যাকরণগুলি সরলও বটে; এগুলির সাহায্যে দক্ষ পার্সিং অ্যালগোরিদম নির্মাণ করা সম্ভব, যেগুলি কোন প্রদত্ত স্ট্রিং কীভাবে ব্যাকরণটি থেকে সৃষ্টি হতে পারে, তা নির্ণয়ে সক্ষম। আর্লি পার্সার (Earley parser) এই ধরনের অ্যালগোরিদমের একটি উদাহরণ। এলআর পার্সার (LR parser) এবং এলএল পার্সারগুলি (LL parser) প্রসঙ্গমুক্ত ব্যাকরণসমূহের একটি সীমিত উপসেটের ওপর কাজ করে।

প্রসঙ্গমুক্ত ব্যাকরণ প্রকাশ করার জন্য সবচেয়ে প্রচলিত লিখন পদ্ধতি (notation) হচ্ছে বিএনএফ (BNF) বা বাকাস-নাউর রূপ।

বিধিগত ভাষামাত্রেই প্রসঙ্গমুক্ত নয়। এরকম একটি ভাষা হল $\{a^{n}b^{n}c^{n}:n\geq 0\}$, যা এমন কতগুলি স্ট্রিং-এর সেট, যার প্রতিটি স্ট্রিং কিছু সংখ্যক a দিয়ে শুরু হয়, এবং একে অনুসরণ করে সমসংখ্যক b এবং c।

বিধিগত সংজ্ঞা

অন্য যেকোন বিধিগত ব্যাকরণের (formal grammar) মতই কোন প্রসঙ্গমুক্ত ব্যাকরণ G-কে একটি ৪-টুপল আকারে প্রকাশ করা যায়:

$G=(V_{t},V_{n},P,S)$ যেখানে

• $V_{t}$ সমাপ্তিজ্ঞাপক প্রতীকের সসীম সেট
• $V_{n}$ অ-সমাপ্তিজ্ঞাপক প্রতীকের সসীম সেট
• $P$ উৎপাদন নিয়মসমূহের একটি সসীম সেট
• $S$ হচ্ছে $V_{n}$ একটি উপাদান, একটি বিশেষভাবে চিহ্নিত আরম্ভসূচক অ-সমাপ্তিজ্ঞাপক প্রতীক (starting non-terminal)
• $P$-এর উপাদানগুলি নিচের রূপবিশিষ্ট

$V_{n}\longrightarrow (V_{t}\cup V_{n})^{*}$

কোন ভাষা L-কে একটি প্রসঙ্গমুক্ত ভাষা (Context-Free-Language বা CFL) বলা হয় যদি এর ব্যাকরণটি প্রসঙ্গমুক্ত হয়। আরও সঠিকভাবে, L এমন একটি ভাষা যার শব্দ, বাক্য এবং পদগুচ্ছগুলি একটি প্রসঙ্গমুক্ত ব্যাকরণের প্রতীক ও শব্দ দিয়ে গঠিত। L-কে তাই সাধারণত L=L(G) আকারে প্রকাশ করা হয়।

নিচে কিছু প্রসঙ্গমুক্ত ব্যাকরণের উদাহরণ দেয়া হল:

উদাহরণসমূহ

উদাহরণ ১

নিচে একটি সরল প্রসঙ্গমুক্ত ব্যাকরণ দেয়া হল:

S → aSb | ε

যেখানে | দিয়ে একই অসমাপ্তিজ্ঞাপক প্রতীকের জন্য একাধিক অপশনগুলিকে পৃথক করে দেখানো হয়েছে এবং ε দিয়ে খালি স্ট্রিং বোঝানো হয়েছে। এই ব্যাকরণটি নিচের ভাষাটিকে সৃষ্টি করে: $\{a^{n}b^{n}:n\geq 0\}$ যা একটি নিয়মিত ভাষা নয়।

উদাহরণ ২

নিচের প্রসঙ্গমুক্ত ব্যাকরণটি x, y এবং z নামক তিনটি চলকের জন্য সিনট্যাক্সগতভাবে সঠিক ইনফিক্স বীজগাণীতিক এক্সপ্রেশন সৃষ্টি করতে পারে:

S → x | y | z | S + S | S - S | S * S | S/S | (S)

উদাহরণস্বরূপ এই ব্যাকরণটি "( x + y ) * x - z * y / ( x + x )" স্ট্রিংটি সৃষ্টি করতে পারে।

এই ব্যাকরণটি দ্ব্যর্থবোধক, অর্থাৎ এতে একই স্ট্রিং-কে একাধিক পার্স-বৃক্ষের সাহায্যে সৃষ্টি করা সম্ভব।

উদাহরণ ৩

{a,b} সেটটির উপর ভিত্তি করে গঠিত সমস্ত স্ট্রিং, যেগুলির প্রতিটিতে a-এর সংখ্যা b-এর সংখ্যার সমান নয়, যে ভাষা গঠন করে, সেই ভাষাটিকে নিচের প্রসঙ্গমুক্ত ব্যাকরণ দিয়ে নির্দেশ করা যায়

S → U | V

U → TaU | TaT

V → TbV | TbT

T → aTbT | bTaT | ε

এখানে T এরকম সমস্ত স্ট্রিং সৃষ্টি করে যেগুলিতে a ও b-এর সংখ্যা সমান। U এরকম সমস্ত স্ট্রিং সৃষ্টি করে যেগুলিতে a-এর সংখ্যা b-এর চেয়ে বেশি এবং V এমন সমস্ত স্ট্রিং সৃষ্টি করে যেগুলিতে a-এর সংখ্যা b-এর সংখ্যার চেয়ে কম।

উদাহরণ ৪

প্রসঙ্গমুক্ত ভাষার আরেকটি উদাহরণ হল $\{b^{n}a^{m}b^{2n}:n\geq 0,m\geq 0\}$। এটি একটি নিয়মিত ভাষা নয়, কিন্তু এটি প্রসঙ্গমুক্ত এবং নিচের প্রসঙ্গমুক্ত ব্যাকরণটি দিয়ে সৃষ্টি করা সম্ভব:

S → bSbb | A

A → aA | ε

অন্যান্য উদাহরণ

প্রসঙ্গমুক্ত ব্যাকরণ কেবল গাণিতিক বিধিগত ভাষাসমূহের মধ্যেই সীমাবদ্ধ নয়। ভেনপা নামের এক শ্রেণীর তামিল কবিতা প্রসঙ্গমুক্ত ব্যাকরণ-নিয়ন্ত্রিত বলে ধারণা করা হয়।

তথ্যসূত্র

• Michael Sipser (১৯৯৭)। Introduction to the Theory of Computation। PWS Publishing। আইএসবিএন ০-৫৩৪-৯৪৭২৮-X।  Section 2.1: Context-Free Grammars, pp. 91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp. 156–159. Section 5.1.1: Reductions via computation histories: pp. 176–183.