Derivation Trees and Ambiguity in Grammar | व्युत्पत्ति वृक्ष और व्याकरण में अस्पष्टता

ऑटोमाटा सिद्धांत और औपचारिक भाषाओं में Derivation Tree (व्युत्पत्ति वृक्ष) और Ambiguity (अस्पष्टता) अत्यंत महत्वपूर्ण अवधारणाएँ हैं। Derivation Tree किसी grammar द्वारा उत्पन्न की गई string की संरचना को tree के रूप में प्रदर्शित करता है, जबकि Ambiguity यह बताती है कि किसी string के लिए एक से अधिक parse tree संभव हैं।

परिचय / Introduction

Grammar किसी भाषा के निर्माण के नियमों का समूह है। Derivation उस प्रक्रिया को कहते हैं जिसमें Production Rules का उपयोग करके Terminals की एक string बनाई जाती है। जब हम इस derivation को tree के रूप में प्रदर्शित करते हैं, तो हमें Derivation Tree या Parse Tree प्राप्त होता है।

1️⃣ Derivation / व्युत्पत्ति

Derivation का अर्थ है — किसी Grammar की production rules का प्रयोग करके Non-terminal symbols को step-by-step Terminals में बदलना। यह प्रक्रिया या तो Leftmost या Rightmost derivation द्वारा की जाती है।

उदाहरण:

Grammar: S → aSb | ε

String: “aabb”

S ⇒ aSb
  ⇒ aaSbb
  ⇒ aabb

Leftmost Derivation:

हर step में सबसे बाएँ Non-terminal को expand किया जाता है।

Rightmost Derivation:

हर step में सबसे दाएँ Non-terminal को expand किया जाता है।

2️⃣ Derivation Tree (Parse Tree) / व्युत्पत्ति वृक्ष

Parse Tree किसी Grammar द्वारा string उत्पन्न करने की प्रक्रिया को tree के रूप में दर्शाता है। इसमें root node Start Symbol होता है और leaves Terminals होते हैं।

उदाहरण:

Grammar: S → aSb | ε

String: aabb

        S
       / \
      a   S   b
         / \
        a   ε  b

यह tree दिखाता है कि Grammar के Production Rules का उपयोग कैसे किया गया।

3️⃣ Parse Tree के घटक / Components of a Parse Tree

• Root Node: Start Symbol
• Internal Nodes: Non-terminals
• Leaf Nodes: Terminals या ε
• Branches: Production Rules

4️⃣ Derivation Tree की विशेषताएँ / Characteristics of Parse Trees

• Parse Tree derivation को स्पष्ट रूप से दिखाता है।
• Tree traversal द्वारा string को पुनः प्राप्त किया जा सकता है।
• Ambiguity पहचानने के लिए उपयोगी होता है।

5️⃣ Ambiguity in Grammar / व्याकरण में अस्पष्टता

किसी Grammar को Ambiguous कहा जाता है यदि किसी string को एक से अधिक Parse Trees या Derivations से उत्पन्न किया जा सकता है।

औपचारिक परिभाषा:

Grammar G ambiguous है यदि कोई string w ऐसी मौजूद है कि w के लिए दो या अधिक भिन्न Parse Trees संभव हों।

उदाहरण:

Grammar:

E → E + E | E * E | id

String: id + id * id

इस string के लिए दो parse trees संभव हैं:

(1) Left Associative Parsing:

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

(2) Right Associative Parsing:

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

इस प्रकार Grammar ambiguous है क्योंकि दो अलग-अलग Parse Trees एक ही string के लिए संभव हैं।

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

• Structural Ambiguity: जब दो अलग-अलग syntax structures संभव हों।
• Lexical Ambiguity: जब किसी शब्द का एक से अधिक अर्थ हो।

7️⃣ Ambiguity हटाने की विधियाँ / Methods to Remove Ambiguity

• Operator Precedence Grammar: Grammar में Operators की precedence निर्धारित करें।
• Associativity Rules: Left या Right Associativity परिभाषित करें।
• Grammar Modification: Ambiguous rules को पुनर्लेखन (Rewrite) करें।

उदाहरण (Ambiguity Removal):

Ambiguous Grammar:

E → E + E | E * E | id

Unambiguous Grammar:

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

अब यह grammar operator precedence का पालन करती है — ‘*’ को ‘+’ से अधिक precedence दी गई है।

8️⃣ Parse Tree का उपयोग / Applications

• Compiler Design में Syntax Analysis के लिए।
• Programming Languages के Grammar Validation में।
• Natural Language Processing (NLP) में Sentence Parsing के लिए।

9️⃣ Parse Tree बनाम Derivation

विशेषता	Derivation	Parse Tree
Representation	Sequential Steps	Tree Structure
Ambiguity Detection	कठिन	आसान
Visualization	कम स्पष्ट	अधिक स्पष्ट

निष्कर्ष / Conclusion

Derivation Tree और Ambiguity दोनों Grammar की संरचना को समझने के लिए महत्वपूर्ण हैं। Parse Tree भाषा के निर्माण को दर्शाता है, जबकि Ambiguity यह बताती है कि Grammar पर्याप्त रूप से स्पष्ट नहीं है। Compiler Design में Ambiguity हटाना अनिवार्य है ताकि प्रत्येक प्रोग्राम का एक ही अर्थ (Unique Meaning) हो।