कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) क्या है? (What is Context-Free Grammar in Compiler Design?)

कॉन्ठेक्स्ट-फ्री व्याकरण (Context-Free Grammar - CFG) कंपाइलर डिज़ाइन का एक महत्वपूर्ण भाग है, जिसका उपयोग भाषा के व्याकरणिक नियमों (Grammar Rules) को परिभाषित करने के लिए किया जाता है। यह सिंटैक्स एनालिसिस (Syntax Analysis) में मदद करता है और कंपाइलर को यह समझने में सहायता करता है कि कोई प्रोग्रामिंग भाषा का कोड वैध है या नहीं।

1. कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) की परिभाषा

CFG एक गणितीय मॉडल है, जिसे **Noam Chomsky** ने विकसित किया था। यह एक फॉर्मल व्याकरण (Formal Grammar) है, जो भाषा की संरचना को परिभाषित करने के लिए नियमों (Production Rules) का उपयोग करता है।

2. कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) के घटक (Components of CFG)

CFG चार भागों से मिलकर बना होता है:

• V (Non-Terminals): वे चिन्ह जो व्याकरण के नियमों में विस्तार कर सकते हैं।
• Σ (Terminals): वे चिन्ह जो अंतिम आउटपुट में होते हैं।
• P (Production Rules): व्याकरण के वे नियम जो एक गैर-टर्मिनल को अन्य गैर-टर्मिनल या टर्मिनल में बदलते हैं।
• S (Start Symbol): व्याकरण का प्रारंभिक प्रतीक (Starting Symbol), जिससे व्याकरण उत्पन्न होता है।

उदाहरण:

एक साधारण **CFG**:

S → aSb | ε

इस व्याकरण से उत्पन्न स्ट्रिंग्स: "", "ab", "aabb", "aaabbb", ...

3. कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) का उदाहरण

मान लीजिए, हमें निम्नलिखित भाषा को परिभाषित करना है:

L = { anbn | n ≥ 0 } → ("ab", "aabb", "aaabbb", ...)

इस भाषा के लिए **CFG** निम्नलिखित होगा:

S → aSb | ε

4. कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) के प्रकार

CFG को मुख्य रूप से दो भागों में विभाजित किया जाता है:

1. व्युत्पन्न (Derivation)

यह उस प्रक्रिया को संदर्भित करता है, जिसमें एक स्टार्ट सिंबॉल से एक स्ट्रिंग बनाई जाती है।

• लेफ्ट मोस्ट व्युत्पत्ति (Leftmost Derivation)
• राइट मोस्ट व्युत्पत्ति (Rightmost Derivation)

2. पार्स ट्री (Parse Tree)

पार्स ट्री एक ट्री संरचना है, जो यह दर्शाती है कि व्याकरण के नियमों का उपयोग करके इनपुट स्ट्रिंग कैसे उत्पन्न की जाती है।

5. पार्स ट्री का उदाहरण

यदि हमारे पास व्याकरण है:

S → aSb | ε

और इनपुट "aabb" है, तो इसका पार्स ट्री कुछ इस प्रकार होगा:

       S
      / 
     a   S
        / 
       a   S
          / 
         ε   b
      
       b

6. CFG और रेगुलर व्याकरण (CFG vs Regular Grammar)

विशेषता	कॉन्ठेक्स्ट-फ्री व्याकरण (CFG)	रेगुलर व्याकरण (Regular Grammar)
संरचना	गैर-टर्मिनल और टर्मिनल दोनों का उपयोग करता है।	केवल टर्मिनल्स और फिक्स्ड पैटर्न का उपयोग करता है।
शक्ति	रेगुलर व्याकरण की तुलना में अधिक शक्तिशाली होता है।	कम जटिल भाषा को परिभाषित करने में सक्षम होता है।
उदाहरण	पैलेन्ड्रोम, संतुलित पैरेंटेसेस	ईमेल एड्रेस, पासवर्ड पैटर्न

7. कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) का उपयोग

• प्रोग्रामिंग भाषाओं के सिंटैक्स को परिभाषित करने के लिए।
• पार्सिंग एल्गोरिदम में।
• नेचुरल लैंग्वेज प्रोसेसिंग (NLP) में।
• XML और HTML डॉक्यूमेंट्स की संरचना जांचने के लिए।

8. कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) की सीमाएँ

• यह केवल व्याकरण की संरचना की जाँच करता है, अर्थ की नहीं।
• कुछ मामलों में यह अत्यधिक जटिल हो सकता है।
• कुछ भाषाएँ रेगुलर व्याकरण द्वारा भी संभाली जा सकती हैं, जिससे CFG की आवश्यकता नहीं पड़ती।

9. निष्कर्ष (Conclusion)

कॉन्ठेक्स्ट-फ्री व्याकरण (CFG) कंपाइलर डिज़ाइन में बहुत महत्वपूर्ण भूमिका निभाता है। यह **सिंटैक्स एनालिसिस** का आधार होता है और **पार्सिंग ट्री** बनाने में मदद करता है। CFG का उपयोग प्रोग्रामिंग भाषाओं, प्राकृतिक भाषा प्रसंस्करण (NLP), और अन्य क्षेत्रों में किया जाता है।