Syntax Directed Definitions (SDD) and Construction of Syntax Trees | सिंटैक्स निर्देशित परिभाषाएँ और सिंटैक्स वृक्ष निर्माण - Compiler Design Notes 2025

सिंटैक्स निर्देशित परिभाषाएँ (Syntax Directed Definitions) और सिंटैक्स वृक्ष निर्माण (Construction of Syntax Trees)

Compiler Design में Syntax Directed Definitions (SDD) एक ऐसा ढांचा है जो व्याकरण (Grammar) को अर्थ (Semantics) से जोड़ता है। यह Compiler को Syntax Tree (या Parse Tree) बनाने, expressions evaluate करने, और intermediate code generate करने में मदद करता है।

📘 Syntax Directed Definitions (SDD) क्या है?

Syntax Directed Definition एक ऐसी formal method है जिसमें grammar के साथ semantic rules जोड़े जाते हैं। प्रत्येक grammar rule के साथ attributes और actions associate किए जाते हैं जो program के अर्थ को परिभाषित करते हैं।

उदाहरण:

E → E1 + T      { E.val = E1.val + T.val }
E → T           { E.val = T.val }
T → T1 * F      { T.val = T1.val * F.val }
T → F           { T.val = F.val }
F → (E)         { F.val = E.val }
F → num         { F.val = num.lexval }

यह SDD grammar Arithmetic Expression का मूल्य निकाल सकता है जैसे (3 + 4) * 5।

---

⚙️ SDD के घटक:

🔹 Attributes: Grammar symbols के साथ जुड़े मान या गुण।
🔹 Semantic Rules: वे नियम जो attributes को calculate करते हैं।

📗 Attributes के प्रकार:

1️⃣ Synthesized Attributes: Child nodes से parent nodes तक जानकारी ले जाते हैं।
2️⃣ Inherited Attributes: Parent या sibling nodes से child nodes तक जानकारी ले जाते हैं।

उदाहरण:

S → A B
A → a
B → b

यदि B को A की value चाहिए, तो वह Inherited Attribute कहलाएगा।

---

🧩 Syntax Directed Translation (SDT):

जब SDD में semantic rules के साथ-साथ actions भी जोड़े जाते हैं, तो इसे Syntax Directed Translation (SDT) कहा जाता है। इन actions को grammar rules में curly braces { } के भीतर लिखा जाता है।

उदाहरण:

E → E1 + T  { print('+') }
E → T
T → T1 * F  { print('*') }
T → F
F → (E)
F → id      { print(id.name) }

यह postfix expression (Reverse Polish Notation) generate करता है।

---

🧮 S-Attributed Definition (Synthesized Attributes Only):

यदि grammar में केवल synthesized attributes उपयोग किए जाते हैं, तो उसे S-Attributed Definition कहा जाता है।

उदाहरण:

E → E1 + T  { E.val = E1.val + T.val }
E → T       { E.val = T.val }
T → num     { T.val = num.lexval }

यह syntax tree को bottom-up तरीके से evaluate करता है।

---

📘 L-Attributed Definition:

यदि grammar में synthesized और कुछ inherited attributes दोनों का प्रयोग हो, तो उसे L-Attributed Definition कहा जाता है।

उदाहरण:

E → T E'
E' → + T { E'.inh = E.inh + T.val } E'
E' → ε   { E.val = E'.inh }

यह top-down evaluation के लिए उपयुक्त होता है।

---

🧩 Syntax Tree (सिंटैक्स वृक्ष):

Syntax Tree एक simplified Parse Tree होता है जो केवल आवश्यक operators और operands को दिखाता है। यह compiler के Intermediate Representation के रूप में कार्य करता है।

📘 उदाहरण:

Expression: (3 + 4) * 5

Parse Tree:

        E
       /|\
      E + T
     /   /|\
    T   F * F
   |   |   |
   F   id  id

Syntax Tree:

📗 Syntax Tree Construction Algorithm:

हर grammar rule के लिए एक function बनाएं।
Operators के लिए internal nodes बनाएं।
Operands (identifiers, numbers) के लिए leaves बनाएं।
Recursive connections बनाएं।

⚙️ Example Code (Syntax Tree Node Creation):

struct Node {
  char op;
  struct Node *left, *right;
};

Node* makeNode(char op, Node* left, Node* right) {
  Node* node = (Node*)malloc(sizeof(Node));
  node->op = op;
  node->left = left;
  node->right = right;
  return node;
}

---

🧠 Evaluation Using Syntax Trees:

Syntax Tree का उपयोग expression evaluation और intermediate code generation में किया जाता है।

Example:

Infix: (3 + 4) * 5
Postfix: 3 4 + 5 *

---

🚀 आधुनिक उपयोग (2025 में):

🔹 AI-assisted Tree Builders – Syntax tree generation with semantic tagging।
🔹 Visualization Tools – Tree diagrams using compiler IDEs।
🔹 Machine Learning Parsers – Syntax + meaning extraction combined।

---

📙 निष्कर्ष:

Syntax Directed Definitions Compiler Design की रीढ़ हैं। ये Grammar और Semantics के बीच पुल का काम करती हैं। Syntax Tree Intermediate Code Generation का पहला चरण है और आधुनिक Compiler Tools में इसकी भूमिका और भी मजबूत होती जा रही है।

Symbolic Debugging of Optimized Code | ऑप्टिमाइज़्ड कोड का प्रतीकात्मक डीबगिंग

ऑप्टिमाइज़्ड कोड का प्रतीकात्मक डीबगिंग (Symbo...

Data Flow Analysis of Structured Flow Graph | स्ट्रक्चर्ड फ्लो ग्राफ का डेटा फ्लो विश्लेषण

स्ट्रक्चर्ड फ्लो ग्राफ का डेटा फ्लो विश्ले�...

Code Improving Transformations in Compiler Design | कोड सुधार परिवर्तन की उन्नत तकनीकें

कोड सुधार परिवर्तन की उन्नत तकनीकें (Code Improving Tran...

Introduction to Global Data Flow Analysis | ग्लोबल डेटा फ्लो एनालिसिस का परिचय

ग्लोबल डेटा फ्लो एनालिसिस का परिचय (Introduction to Global...

Loop Optimization | लूप ऑप्टिमाइज़ेशन

लूप ऑप्टिमाइज़ेशन (Loop Optimization in Compiler Design) Loop Optimiza...

Syntax Directed Definitions (SDD) and Construction of Syntax Trees | सिंटैक्स निर्देशित परिभाषाएँ और सिंटैक्स वृक्ष निर्माण - Compiler Design Notes 2025