Bottom-Up Evaluation of Inherited Attributes | इनहेरिटेड एट्रीब्यूट्स का बॉटम-अप मूल्यांकन - Compiler Design Notes 2025

इनहेरिटेड एट्रीब्यूट्स का बॉटम-अप मूल्यांकन (Bottom-Up Evaluation of Inherited Attributes)

Compiler Design में Inherited Attributes वे semantic गुण होते हैं जो parent या sibling nodes से प्राप्त होते हैं। जब parsing प्रक्रिया Bottom-Up (जैसे LR Parsing) द्वारा की जाती है, तो इन attributes को सही ढंग से propagate करना एक चुनौतीपूर्ण कार्य होता है। इस प्रक्रिया को ही Bottom-Up Evaluation of Inherited Attributes कहा जाता है।

---

📘 Inherited Attributes क्या हैं?

Inherited Attributes वे attributes होते हैं जो किसी node को अपने parent या sibling से मिलते हैं। इनका उपयोग context-sensitive information पास करने के लिए किया जाता है, जैसे कि:

Variable के data type या scope की जानकारी।
Operator precedence या associativity।
Parameter passing during function calls।

📗 उदाहरण:

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

यह grammar दिखाता है कि E'.inh inherited attribute है जो E (parent) से E' तक जाता है।

---

⚙️ Bottom-Up Parsing में Inherited Attributes का मूल्यांकन:

Bottom-Up Parsing (जैसे LR Parsing) में parsing stack का उपयोग करके grammar को reverse derivation order में evaluate किया जाता है। इस दौरान inherited attributes को stack के माध्यम से propagate किया जाता है।

मुख्य विचार:

🔹 Inherited attributes को stack entries में store किया जाता है।
🔹 जब reduction होती है, तो attribute computation के लिए stack से values ली जाती हैं।
🔹 Parsing actions में synthesized और inherited दोनों values को maintain किया जाता है।

---

🧩 Example: Expression Evaluation with Inherited Attributes

Grammar:

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

Input: 2 + 3 + 4

Bottom-Up Evaluation Table:

Step	Stack	Input	Action	Inherited Value	Result
1	[]	2+3+4$	Shift num	—	T.val = 2
2	[T]	+3+4$	Reduce T → num	E'.inh = T.val = 2	2
3	[E']	+3+4$	Shift +, Shift num	E'.inh = 2	3
4	[T]	+4$	Reduce E' → + T E'	E'.inh = 2 + 3	5
5	[E']	+4$	Shift +, Shift num	E'.inh = 5	4
6	[T]	$	Reduce E' → + T E'	E.val = 9	✅

Final Answer → E.val = 9 ✅

---

🧮 Evaluation Process:

हर reduction के दौरान stack entries से synthesized और inherited values निकाली जाती हैं।
Inherited values को नई states में propagate किया जाता है।
Reduction के बाद synthesized attribute को पुनः stack पर push किया जाता है।

📗 Pseudocode (LR Parser with Attributes):

while (true):
  state = top(stack)
  token = nextInput()
  action = ACTION[state, token]

  if action == shift:
    push(token)
    push(attributes[token])
  else if action == reduce by A → β:
    pop(2 * |β|)
    compute inherited and synthesized attributes
    push(A)
    push(GOTO[state, A])
  else if action == accept:
    return 'Accepted'

---

📘 Real-World Example (Type Propagation)

Grammar:

D → T L
L → L , id { id.type = L.inh } | id { id.type = L.inh }
T → int | float

Input: float a, b, c;

Result:

a → float
b → float
c → float

यहाँ type propagation inherited attributes के माध्यम से हुआ।

---

⚙️ Advantages:

✅ Context propagation in bottom-up parsing.
✅ Works seamlessly with LR parsing stack.
✅ Suitable for type and scope management.

⚠️ Limitations:

❌ Complex stack management.
❌ Difficult to visualize inheritance in bottom-up order.
❌ More parser states required.

---

🚀 आधुनिक परिप्रेक्ष्य (2025 में):

🔹 AI-assisted Parsing Systems attribute propagation को स्वचालित बनाते हैं।
🔹 LLVM & MLIR Tools में inherited evaluation का प्रयोग semantic linking में किया जाता है।
🔹 Dataflow-Based Parsers attribute values को dynamic context के साथ evaluate करते हैं।

---

📙 निष्कर्ष:

Bottom-Up Evaluation of Inherited Attributes Compiler Design का एक उन्नत विषय है, जो syntactic और semantic information के आदान-प्रदान को सक्षम बनाता है। 2025 में, AI-संचालित compilers और dynamic semantic analyzers इसी concept को वास्तविक समय (real-time) में लागू कर रहे हैं।

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...

Bottom-Up Evaluation of Inherited Attributes | इनहेरिटेड एट्रीब्यूट्स का बॉटम-अप मूल्यांकन - Compiler Design Notes 2025