Syntax-directed translation और attribute evaluation
लक्ष्य और notation
Parse tree को meaning दें, grammar symbols और attributes को अलग रखें। Syntax-directed definition (SDD) productions के साथ attributes तथा semantic rules जोड़ती है। Translation scheme production की तय जगहों पर executable actions रखती है। Grammar syntax तय करती है; dependencies evaluation order तय करती हैं। Attribute तैयार होने से पहले action उसका उपयोग नहीं कर सकता।
1. Synthesized और inherited attributes
Synthesized attribute बच्चे nodes के attributes और अनुमत local जानकारी से बनता है। Inherited attribute parent और/या संबंधित siblings से मिलता है। E→E₁+T में E और E₁ अलग occurrences तथा अलग tree nodes हैं, भले grammar symbol एक हो।
Arithmetic rules लें: E→E₁+T {E.val=E₁.val+T.val}; E→T {E.val=T.val}; T→T₁F {T.val=T₁.valF.val}; T→F {T.val=F.val}; F→num {F.val=num.lexval}। सभी val synthesized हैं। Postorder में बच्चे पूरे होने के बाद parent निकाल सकते हैं। यह left-recursive grammar attribute उदाहरण और bottom-up parsing के लिए ठीक है; LL(1) grammar नहीं है।
2+34 में num leaves से 2,3,4 मिलते हैं। Multiplication subtree 34=12 देता है। Root addition 2+12=14 देता है। Right child तैयार होने से पहले addition करना dependency order तोड़ेगा। Multiplication की grouping grammar देती है, attribute rule अपने-आप precedence नहीं बनाता।
2. Dependency graph और scheduling
हर attribute occurrence के लिए एक vertex बनाएँ। x को y,z से निकालने पर y→x, z→x edges रखें। Acyclic graph का कोई भी topological order valid evaluation order है। केवल source का left-to-right क्रम पर्याप्त नहीं। किसी tree के dependency graph में directed cycle हो तो इस सीधे dependency evaluation का topological order नहीं है। General attribute grammar पर निष्कर्ष के लिए संभव trees पर भी विचार चाहिए, केवल एक diagram पर नहीं।
S-attributed definition में सिर्फ synthesized attributes होते हैं और bottom-up evaluation संभव है। A→XYZ reduction में semantic stack से X,Y,Z की values लेकर A निकालें और RHS entries को A से बदलें। ε production भी बच्चों के बिना constant synthesize कर सकती है।
3. Inherited accumulator
Grammar E→T R; R→+T R₁ | ε; T→num लें। T.val=num.lexval है। E→TR में R.inh=T.val तथा E.val=R.syn रखें। R→+TR₁ में R₁.inh=R.inh+T.val और R.syn=R₁.syn रखें। R→ε में R.syn=R.inh रखें। Right-recursive grammar में running result inherited attribute में जाता है।
2+3+4 में पहला T, 2 देता है और पहले R.inh=2। अगला T, 3 देता है, तो अगले R.inh=5। अंतिम T, 4 देता है, तो अंतिम R.inh=9। ε पर R.syn=9; यही result सभी R से लौटकर E.val=9 बनता है। Left-associative subtraction में भी यही तरीका उपयोगी है: minus rule के साथ inh−T.val करें, 2−(3−4) जैसी right association न बना दें।
L-attributed definition में RHS symbol Xᵢ का inherited attribute parent के inherited attributes तथा बाईं ओर के symbols के attributes पर निर्भर हो सकता है; अपने symbol की अनुमत dependencies भी cycle न बनाएँ। ऊपर के rules left-to-right restriction निभाते हैं: R₁.inh, R.inh और पहले आए T.val का उपयोग करता है। अभी evaluate न हुए right sibling की value माँगने वाला rule इस property से सही नहीं ठहरता।
4. Actions और postfix
Postfix translation में E→E₁+T {print('+')}, T→T₁F {print('')}, F→num {print(num.lexeme)} तथा copy productions E→T, T→F लें। Right-end actions बच्चों के बाद चलते हैं। 2+3*4 से 2 3 4 * + निकलता है। E→E₁+{print('+')}T में +, T के output से पहले छपेगा और वही postfix scheme नहीं बनेगी।
सावधानियाँ
S-attributed, L-attributed का subset है; उलटा नहीं। Synthesized का अर्थ बच्चों से पहले evaluation नहीं। Symbol-table pointer तथा numeric val अलग attributes हैं। एक attribute name को पूरे tree में एक value न मानें: हर occurrence अलग है। Tree construction, evaluation और output side effects, तीनों के ordering rules सही रखें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. केवल child vals से parent val बनाने वाले rules क्या हैं?
A. S-attributed definition B. अनिवार्य cyclic definition C. केवल inherited attributes D. अपने-आप LL(1) grammar
उत्तर: A
A: सभी synthesized हैं।
B: Child-to-parent flow में cycle जरूरी नहीं।
C: ये values ऊपर जाती हैं।
D: Attribute class से LL(1) सिद्ध नहीं।
P02. Lesson grammar में 2+3*4 का E.val क्या है?
A. 20 B. 14 C. 24 D. 9
उत्तर: B
A: 20 में addition पहले होता।
B: पहले 12, फिर 14।
C: यह operators और grouping नहीं मानता।
D: 9 में तीनों जोड़े जाते।
P03. x=f(y,z) में dependency edges क्या हैं?
A. x→y और x→z B. केवल y→z C. y→x और z→x D. कोई edge नहीं
उत्तर: C
A: Prerequisite दिशा उलटी है।
B: y से z की dependency नहीं दी।
C: जरूरी values से computed value की ओर edge है।
D: x, y,z से स्वतंत्र नहीं।
P04. 2+3+4 accumulator में अंतिम R.inh क्या है?
A. 2 B. 3 C. 5 D. 9
उत्तर: D
A: 2 शुरुआती inherited value है।
B: 3 operand है, total नहीं।
C: 5 बीच का sum है।
D: Accumulator 2,5,9 होता है।
P05. Postfix के right-end actions 2+3*4 पर क्या छापेंगे?
A. 2 3 + 4 * B. + 2 * 3 4 C. 2 3 4 * + D. 2 + 3 * 4
उत्तर: C
A: इसमें addition पहले group हुआ।
B: यह prefix क्रम है।
C: Children के बाद operator छपता है।
D: यह infix ही है।
P06. Tree attribute dependency graph में directed cycle का क्या अर्थ है?
A. कोई भी order सही B. Topological evaluation order नहीं है C. Input में lexical error जरूरी D. Left recursion हटाना हमेशा ठीक करेगा
उत्तर: B
A: Cycle prerequisite-first क्रम रोकता है।
B: Directed cycle में topological क्रम नहीं।
C: यह lexical invalidity नहीं बताता।
D: Grammar बदलने से semantic cycle अपने-आप नहीं हटती।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन