Ambiguity in Context-Free Grammar | प्रसंग-मुक्त व्याकरण में अस्पष्टता

Context-Free Grammar (CFG) औपचारिक भाषा सिद्धांत (Formal Language Theory) का एक मूलभूत भाग है। CFG भाषाओं को परिभाषित करने के लिए उपयोग की जाती है, लेकिन कभी-कभी ऐसी Grammar बनाई जाती है जो एक ही string को एक से अधिक तरीकों से generate कर सकती है। ऐसी स्थिति को Ambiguity (अस्पष्टता) कहा जाता है।

परिचय / Introduction

किसी Grammar को Ambiguous कहा जाता है यदि वह एक ही Input String के लिए एक से अधिक Parse Tree या Derivation बना सकती है। Ambiguity Compiler Design, Syntax Analysis और Parsing Algorithms के लिए गंभीर समस्या उत्पन्न करती है क्योंकि इससे Output का अर्थ बदल सकता है।

1️⃣ औपचारिक परिभाषा / Formal Definition

यदि Grammar G ऐसी है कि भाषा L(G) में कोई String ‘w’ ऐसी है जिसके लिए दो या अधिक विभिन्न Parse Trees या Derivations संभव हैं, तो Grammar G को Ambiguous कहा जाता है।

Mathematically:

∃ w ∈ L(G) such that there exist two distinct parse trees for w.

2️⃣ उदाहरण / Example

Grammar:

E → E + E | E * E | id

String: id + id * id

Derivation 1 (Leftmost):

E ⇒ E + E
  ⇒ id + E
  ⇒ id + E * E
  ⇒ id + id * id

Derivation 2 (Rightmost):

E ⇒ E * E
  ⇒ E + E * E
  ⇒ id + id * id

दो Parse Trees:

(1) Left-Associative Tree

        E
       /|\
      E + E
     id   * E
          id id

(2) Right-Associative Tree

        E
       /|\
      E * E
     E + E id
    id id

दोनों Parse Trees अलग-अलग Syntax संरचना दिखाते हैं, इसलिए Grammar Ambiguous है।

3️⃣ Ambiguity का कारण / Causes of Ambiguity

• Operator precedence का अभाव।
• Associativity नियमों का अभाव।
• Grammar के production rules का ओवरलैप।
• Improper parenthesis handling।

4️⃣ Ambiguity के प्रकार / Types of Ambiguity

• Structural Ambiguity: जब Syntax संरचना एक से अधिक तरीके से हो सकती है।
• Lexical Ambiguity: जब एक शब्द के कई अर्थ हों।
• Semantic Ambiguity: जब अर्थ में अस्पष्टता हो लेकिन संरचना सही हो।

5️⃣ Ambiguity हटाने के उपाय / Methods to Remove Ambiguity

Ambiguity को Grammar में संशोधन करके हटाया जा सकता है।

1. Operator Precedence Grammar:

Operators के precedence स्तर तय किए जाते हैं।

2. Associativity Rules:

Operator के associativity (Left/Right) को निर्धारित किया जाता है।

3. Grammar Redesign:

Grammar को स्पष्ट hierarchical संरचना में लिखा जाता है।

Example (Ambiguity-Free Grammar):

E → E + T | T
T → T * F | F
F → (E) | id

यह Grammar operator precedence को परिभाषित करती है और Ambiguity समाप्त करती है।

6️⃣ Ambiguity की पहचान / Detection of Ambiguity

Ambiguity की पहचान करने के लिए Parse Tree का निर्माण किया जाता है। यदि किसी String के लिए दो या अधिक Parse Trees संभव हों, तो Grammar ambiguous है।

7️⃣ Intrinsically Ambiguous Languages / अंतर्निहित अस्पष्ट भाषाएँ

कुछ भाषाएँ ऐसी होती हैं जिन्हें किसी भी Grammar द्वारा Unambiguous रूप में परिभाषित नहीं किया जा सकता। इन्हें Intrinsically Ambiguous Languages कहा जाता है।

Example:

L = {aⁱbʲcᵏ | i = j or j = k}

यह भाषा किसी भी Unambiguous Grammar से परिभाषित नहीं की जा सकती।

8️⃣ PDA और Ambiguity / PDA and Ambiguity

Ambiguous Grammar के लिए PDA Non-Deterministic रूप से व्यवहार करता है। DPDA केवल Unambiguous (Deterministic) CFGs को ही संभाल सकता है, जबकि NPDA Ambiguous Grammars को भी पहचान सकता है।

9️⃣ व्यावहारिक उपयोग / Practical Applications

• Compiler Design में Grammar simplification।
• Programming Language Parser Design में।
• Mathematical expression evaluation में।
• Natural Language Processing (NLP) में Disambiguation के लिए।

🔟 निष्कर्ष / Conclusion

Ambiguity Context-Free Grammars की एक महत्वपूर्ण लेकिन चुनौतीपूर्ण समस्या है। Ambiguity दूर करने से Parsing अधिक सटीक और Compiler का व्यवहार निश्चित हो जाता है। इसलिए Grammar को इस प्रकार परिभाषित किया जाना चाहिए कि वह Unambiguous हो और प्रत्येक Input String का एक ही अर्थ हो।