सिंटैक्स-निर्देशित अनुवाद, रनटाइम परिवेश व मध्यवर्ती कोड

पार्स वृक्ष विद्यमान हो जाने पर अग्र-भाग का शेष उससे जुड़ा हिसाब-किताब है। सिंटैक्स-निर्देशित अनुवाद व्याकरण के प्रतीकों पर गुण तथा उसके उत्पादनों पर उन्हें निकालने के नियम टाँगता है, और जो एक भेद अधिकांश प्रश्न तय करता है वह सूचना के बहाव की दिशा है। संश्लेषित गुण शीर्ष की संतानों से निकाला जाता है — व्यंजक का मान, उपवृक्ष का प्रकार — और सदा एक ही पास में नीचे-से-ऊपर मूल्यांकित हो सकता है, और LR पार्सर न्यूनन करते समय ठीक वही करता है। आरोपित गुण दूसरी दिशा में बहता है, जनक या वाम सहोदर से, और मानक उदाहरण प्रकार-घोषणा है: int a, b, c में प्रकार शीर्ष पर बैठता है और उसे प्रत्येक नाम तक नीचे धकेलना पड़ता है। यह इसलिए महत्वपूर्ण है कि एक स्वच्छ नियम है: जिस व्याकरण के सभी गुण संश्लेषित हों वह S-गुणित है और LR पार्सिंग के दौरान बिना अतिरिक्त पास मूल्यांकित हो सकता है, जबकि आरोपित गुणों को एक बाएँ-से-दाएँ बहाव में मूल्यांकनीय होने हेतु L-गुणित अनुशासन चाहिए — प्रत्येक केवल जनक तथा अपने बाईं ओर के सहोदरों पर निर्भर। तत्पश्चात् रनटाइम परिवेश उत्तर देता है कि प्रोग्राम चलते समय नाम कहाँ रहता है, और परीक्षणीय विषय-वस्तु लगभग पूर्णतः सक्रियण अभिलेखों तथा उसके विषय में है जो पुनरावर्तन को काम करने देता है: प्रत्येक कॉल को स्टैक पर अपना फ़्रेम मिलता है, अतः प्रत्येक पुनरावर्ती आह्वान के पास स्थानीय चरों की अपनी प्रतिलिपि होती है, और फ़्रेम वही है जिसमें संचित प्रतिवापसी पता व बुलाने वाले का फ़्रेम संकेतक रहते हैं। मध्यवर्ती कोड वहाँ है जहाँ अंक गणना पर लौट आते हैं। त्रि-पता कोड प्रत्येक अनुदेश को अधिकतम एक संकारक देता है, अतः व्यंजक अस्थायी चरों को निर्दिष्टीकरणों का अनुक्रम बन जाता है, और प्रश्न दो बातें पूछते हैं: उसमें कितने अनुदेश लगते हैं और उसे मूल्यांकित करने हेतु कितने रजिस्टर चाहिए — और दूसरे का उत्तर लोगों को चकित करता है, क्योंकि संतुलित व्यंजक वृक्ष को गहरे असम वृक्ष से अधिक रजिस्टर चाहिए।

संश्लेषित, आरोपित, तथा कौन-सा पार्सर सँभाल सकता है

गुणों की दोनों दिशाएँ, तथा प्रत्येक की लागत
पक्षसंश्लेषितआरोपित
किससे निकाला जाताशीर्ष की संतानेंजनक या वाम सहोदर
मूल्यांकन क्रमनीचे-से-ऊपर, एक पासऊपर-से-नीचे या बाएँ-से-दाएँ
सामान्य उदाहरणव्यंजक का मान या प्रकारप्रत्येक नाम पर धकेला घोषित प्रकार
व्याकरण वर्गS-गुणितL-गुणित, यदि प्रत्येक केवल बाईं ओर पर निर्भर हो
LR पार्सिंग के दौरान मूल्यांकनीय?हाँ — प्रत्येक न्यूनन परसामान्यतः नहीं
🎯 S-गुणित व्याकरण निःशुल्क क्यों और आरोपित नहीं
LR पार्सर किसी उत्पादन का न्यूनन तभी करता है जब उसके दक्षिण पक्ष का प्रत्येक प्रतीक पार्स हो चुका हो — जिसका अर्थ है कि जनक के बनने के ठीक क्षण प्रत्येक संतान समाप्त हो चुकी है। अतः संश्लेषित गुण वहीं, न्यूनन क्रिया में, बिना अतिरिक्त भ्रमण निकाला जा सकता है: उसे जो मान चाहिए वे पार्सर स्टैक पर बैठे हैं। आरोपित गुण को ऊपर से या बाईं ओर से सूचना चाहिए, जो न्यूनन के समय अभी विद्यमान न हो, अतः सामान्यतः उसे या वृक्ष पर पृथक् पास चाहिए या कोई प्रतिबंध। L-गुणित वही प्रतिबंध है: प्रत्येक गुण जनक तथा कठोरतः अपनी बाईं ओर के सहोदरों पर निर्भर हो सकता है, और वही क्रम बाएँ-से-दाएँ भ्रमण देता है, अतः L-गुणित व्याकरण ऊपर-से-नीचे पार्सिंग के दौरान एक बहाव में मूल्यांकित हो सकता है। व्यावहारिक पाठ यह है कि S-गुणित ⊂ L-गुणित, और कौन-सा पार्सर किसी अनुवाद-योजना का मूल्यांकन कर सकता है यह पूछता प्रश्न वस्तुतः यह पूछ रहा है कि वह इन दो वर्गों में किसमें आती है।

सक्रियण अभिलेख, तथा पुनरावर्तन को क्या काम करने देता है

प्रत्येक कॉल एक सक्रियण अभिलेख — फ़्रेम — पुश करता है जिसमें प्राचल, स्थानीय चर, संचित प्रतिवापसी पता तथा बुलाने वाले के फ़्रेम की कड़ी होती है। पुनरावर्तन के पीछे सम्पूर्ण तंत्र वही है: पुनरावर्ती कॉल को नया फ़्रेम मिलता है, अतः उसके स्थानीय चर नए व बुलाने वाले से स्वतंत्र होते हैं, और प्रतिवापसी फ़्रेम पॉप करके बुलाने वाले का दृश्य पुनःस्थापित करती है। स्थैतिक आवंटन यह नहीं कर सकता, क्योंकि प्रति चर एक नियत स्थान प्रत्येक आह्वान द्वारा साझा होता, और इसीलिए स्टैक अनुशासन से रहित भाषाएँ पुनरावर्तन का समर्थन नहीं कर सकतीं।

⚠️ स्थैतिक व गतिक विस्तार केवल तब भिन्न हैं जब नाम स्थानीय न हो
स्थैतिक (शाब्दिक) विस्तार में मुक्त नाम प्रोग्राम के परिवेष्टक पाठ से बाहर की ओर देखकर सुलझता है, अतः उत्तर संकलन-काल पर नियत होता है और स्रोत से पढ़ा जा सकता है। गतिक विस्तार में वह कॉल स्टैक नीचे उस निकटतम फ़्रेम तक देखकर सुलझता है जो उसे परिभाषित करता है, अतः उत्तर इस पर निर्भर है कि किसने किसे बुलाया और उसी फलन के दो निष्पादनों के बीच भिन्न हो सकता है। लगभग प्रत्येक वास्तविक भाषा स्थैतिक विस्तार वाली है। परीक्षणीय रूप सदा वही है: कोई छोटा प्रोग्राम जहाँ फलन ऐसे नाम को संदर्भित करे जिसे वह घोषित नहीं करता, दो भिन्न स्थानों से बुलाया गया — और दोनों अनुशासन भिन्न उत्तर ठीक इसलिए देते हैं कि एक प्रोग्राम पढ़ता है और दूसरा स्टैक। यदि नाम स्थानीय है, तो दोनों सहमत हैं, अतः पहली जाँच योग्य बात यह है कि नाम वस्तुतः मुक्त है या नहीं।

त्रि-पता कोड, गिना गया

a = bc + bc − d, सामान्य उप-व्यंजक हटाने से पूर्व व पश्चात्
भोलाCSE के पश्चात्
t1 = b * ct1 = b * c
t2 = b * ct2 = t1 + t1
t3 = t1 + t2t3 = t2 - d
t4 = t3 - da = t3
a = t4—
5 अनुदेश4 अनुदेश
🧠 संतुलित व्यंजक वृक्ष को असम वृक्ष से **अधिक** रजिस्टर चाहिए
यही प्रति-अंतर्ज्ञानी परिणाम है, और वह सीधे सेठी–उलमैन अंकन से आता है: पत्ती को 1 रजिस्टर चाहिए, और जिस शीर्ष के दो उपवृक्षों को a व b रजिस्टर चाहिए उसे max(a, b) चाहिए यदि a ≠ b, तथा a + 1 यदि वे बराबर हों। अतः (a+b)*(c+d) — दो उपवृक्ष प्रत्येक को 2 चाहिए — को 3 रजिस्टर चाहिए, क्योंकि बायाँ पक्ष रजिस्टर में मूल्यांकित करने के पश्चात् आपको उसे धारण करना होगा जब तक दायाँ पक्ष मूल्यांकित हो, जिसे स्वयं दो चाहिए। परंतु वाम-गहन श्रृंखला ((a+b)+c)+d को केवल 2 चाहिए, क्योंकि प्रत्येक चरण पर एक प्रचालक पत्ती है और दूसरे रजिस्टर में लादकर तुरंत खपाया जा सकता है, अतः कुछ संचित नहीं होता। दोनों आँकड़े निकाले गए। शिक्षा यह है कि रजिस्टर-दबाव इससे चालित है कि कितने आंशिक परिणाम एक साथ धारण करने पड़ते हैं, जो वृक्ष के आकार के बजाय उसकी आकृति का गुण है — और इसीलिए संकलक जान-बूझकर व्यंजक का पुनःसाहचर्य कर सकता है।

मुख्य बिंदु

  • संश्लेषित गुण संतानों से आता है और प्रत्येक LR न्यूनन पर मूल्यांकित हो सकता है, बिना अतिरिक्त पास।
  • आरोपित गुण जनक या वाम सहोदर से आता है — घोषित-प्रकार-प्रत्येक-नाम-पर वाली स्थिति।
  • S-गुणित ⊂ L-गुणित; L-गुणित एक बाएँ-से-दाएँ बहाव में मूल्यांकनीय है।
  • प्रत्येक कॉल को अपना सक्रियण अभिलेख मिलता है, और पुनरावर्तन के पीछे सम्पूर्ण तंत्र वही है।
  • स्थैतिक विस्तार मुक्त नाम को परिवेष्टक पाठ से सुलझाता है; गतिक विस्तार कॉल स्टैक से।
  • त्रि-पता कोड प्रत्येक अनुदेश को अधिकतम एक संकारक देता है, अतः व्यंजक अस्थायी चरों का अनुक्रम बन जाता है।
  • a = bc + bc − d भोले रूप में 5 अनुदेश लेता है और सामान्य उप-व्यंजक हटाने पर 4।
  • सेठी–उलमैन: (a+b)*(c+d) को 3 रजिस्टर चाहिए जबकि ((a+b)+c)+d को 2 — आकृति, आकार नहीं।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. सामान्य उप-व्यंजक हटाने के पश्चात् a = bc + bc − d हेतु कितने त्रि-पता अनुदेश आवश्यक हैं?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 4

    t1 = b * c, t2 = t1 + t1, t3 = t2 - d, a = t3 — चार। भोला अनुवाद पाँच लेता है, क्योंकि वह b * c को दो बार पृथक् अस्थायी चरों में निकालता है। बचत ठीक एक अनुदेश की है, और यह देखना महत्वपूर्ण है कि वह कहाँ से आती है: CSE योग या घटाव नहीं हटाता, केवल उस प्रचालक की पुनर्गणना जो पहले से उपलब्ध था। 5 उत्तर देने का अर्थ है कि उन्मूलन लागू नहीं हुआ; 3 उत्तर देने का अर्थ प्रायः यह है कि a में अंतिम प्रतिलिपि छोड़ दी गई, जो त्रि-पता कोड को चाहिए ही, बशर्ते अंतिम संक्रिया सीधे a को लक्ष्य न कर सके।

  2. स्मृति में स्पिल किए बिना (a+b)*(c+d) मूल्यांकित करने हेतु न्यूनतम कितने रजिस्टर आवश्यक हैं?

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 3

    तीन। सेठी–उलमैन नियम से पत्ती की लागत 1 है और जिस शीर्ष के उपवृक्षों की लागत a व b है उसकी लागत भिन्न होने पर max(a, b) तथा बराबर होने पर a + 1 है। यहाँ दोनों उपवृक्षों की लागत 2 है और वे बराबर हैं, अतः उत्तर 3 है: a+b को एक रजिस्टर में मूल्यांकित करें, उसे धारण करें, और दाएँ उपवृक्ष को अपने दो और चाहिए। शिक्षाप्रद तुलना वाम-गहन श्रृंखला ((a+b)+c)+d है, जिसे केवल 2 चाहिए — प्रत्येक चरण पर एक प्रचालक पत्ती है, लादा व तुरंत खपाया गया, अतः कुछ संचित नहीं होता। अतः संतुलित वृक्ष उसी आकार के असम वृक्ष से अधिक रजिस्टर लेता है, जो अधिकांश लोगों की अपेक्षा के विपरीत है और इसीलिए रजिस्टर-दबाव वृक्ष की आकृति का गुण है।

  3. केवल किसी शीर्ष की संतानों के गुणों से निकाला गया गुण है:

    1. आरोपित, और उसे ऊपर-से-नीचे पास चाहिए
    2. संश्लेषित, और LR पार्सिंग के दौरान मूल्यांकनीय
    3. संश्लेषित, पर उसे पृथक् पास चाहिए
    4. आरोपित, और LR पार्सिंग के दौरान मूल्यांकनीय
    उत्तर देखें

    उत्तर: B — संश्लेषित, और LR पार्सिंग के दौरान मूल्यांकनीय

    संश्लेषित, और LR पार्सिंग के दौरान मूल्यांकनीय। LR पार्सर किसी उत्पादन का न्यूनन तभी करता है जब उसके दक्षिण पक्ष का प्रत्येक प्रतीक पूर्ण हो, अतः जनक शीर्ष के बनने के क्षण उसकी सभी संतानें समाप्त हो चुकी हैं और उनके गुण-मान स्टैक पर हैं — गणना न्यूनन क्रिया में होती है, बिना अतिरिक्त भ्रमण (जो विकल्प C को बाहर करता है)। विकल्प D उलटा है: आरोपित गुणों को जनक से या बाईं ओर से सूचना चाहिए, जो न्यूनन के समय अभी विद्यमान न हो। केवल संश्लेषित गुणों वाला व्याकरण S-गुणित कहलाता है, और S-गुणित होना नीचे-से-ऊपर पार्सिंग के दौरान एक-पास मूल्यांकन की ठीक वही शर्त है।

  4. पुनरावर्तन हेतु सक्रियण अभिलेखों का आवंटन आवश्यक है:

    1. स्थैतिक रूप से, प्रति फलन एक
    2. स्टैक पर, प्रति कॉल एक
    3. हीप पर, प्रति प्रोग्राम एक
    4. केवल रजिस्टरों में
    उत्तर देखें

    उत्तर: B — स्टैक पर, प्रति कॉल एक

    स्टैक पर, प्रति कॉल एक। पुनरावर्ती फलन एक साथ कई बार सक्रिय होता है, और प्रत्येक सक्रियण को अपने प्राचल व स्थानीय चर चाहिए — अतः संचयन प्रति कॉल होना चाहिए, प्रति फलन नहीं। स्थैतिक आवंटन प्रति चर एक नियत स्थान देता है, प्रत्येक आह्वान द्वारा साझा, अतः भीतरी कॉल बाहरी कॉल के स्थानीय चर अधिलिखित कर देती: ठीक इसीलिए शुद्ध स्थैतिक आवंटन वाली भाषाएँ पुनरावर्तन का समर्थन नहीं कर सकतीं, और इस प्रश्न के पीछे ऐतिहासिक बिंदु वही है। फ़्रेम संचित प्रतिवापसी पता तथा बुलाने वाले के फ़्रेम की कड़ी भी वहन करता है, और वही प्रतिवापसी को बुलाने वाले का दृश्य ठीक-ठीक पुनःस्थापित करने देता है।

  5. कोई फलन ऐसे चर को संदर्भित करता है जिसे वह घोषित नहीं करता। स्थैतिक व गतिक विस्तार वही उत्तर देते हैं जब:

    1. प्रोग्राम में कोई पुनरावर्तन न हो
    2. परिवेष्टक परिभाषा तथा उसे परिभाषित करता निकटतम बुलाने वाला वही हों
    3. प्रोग्राम संकलित हो, व्याख्यायित नहीं
    4. कभी नहीं
    उत्तर देखें

    उत्तर: B — परिवेष्टक परिभाषा तथा उसे परिभाषित करता निकटतम बुलाने वाला वही हों

    स्थैतिक विस्तार परिवेष्टक पाठ से बाहर की ओर देखता है; गतिक विस्तार नाम को परिभाषित करते निकटतम फ़्रेम हेतु कॉल स्टैक नीचे देखता है। जब वे दोनों संयोगवश वही घोषणा पहचानें, तो अनुशासन सहमत होते हैं — और इसीलिए अंतर केवल उस प्रोग्राम में दिखता है जो जान-बूझकर ऐसे बनाया गया हो कि बुलाने वाला परिवेष्टक विस्तार न हो। विकल्प D गलत है और देखते ही अस्वीकार करने योग्य: तुरंत परिवेष्टक फलन में घोषित उस नाम हेतु जो बुलाने वाला भी हो, दोनों तुच्छ रूप से मिलते हैं। विकल्प C सुलझाव-नियम को कार्यान्वयन रणनीति से भ्रमित करता है; स्थैतिक विस्तार भाषा का गुण है और संकलक हो या न हो, टिकता है।

  6. L-गुणित परिभाषाओं के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक सही हो सकते हैं।)

    1. प्रत्येक S-गुणित परिभाषा L-गुणित है
    2. वे एक ही बाएँ-से-दाएँ भ्रमण में मूल्यांकित हो सकती हैं
    3. आरोपित गुण अपनी दाईं ओर के सहोदर पर निर्भर हो सकता है
    4. वे ऊपर-से-नीचे पार्सिंग के लिए उपयुक्त हैं
    उत्तर देखें

    उत्तर: A — प्रत्येक S-गुणित परिभाषा L-गुणित है; B — वे एक ही बाएँ-से-दाएँ भ्रमण में मूल्यांकित हो सकती हैं; D — वे ऊपर-से-नीचे पार्सिंग के लिए उपयुक्त हैं

    A, B व D। S-गुणित का अर्थ है प्रत्येक गुण संश्लेषित है, जो L-गुणित शर्त को रिक्त रूप से संतुष्ट करता है — अतः A में अंतर्वेशन, और इसीलिए S-गुणित ⊂ L-गुणित। परिभाषक प्रतिबंध यह है कि प्रत्येक आरोपित गुण केवल जनक तथा कठोरतः अपनी बाईं ओर के सहोदरों पर निर्भर हो, और वही क्रम एक बाएँ-से-दाएँ बहाव उपलब्ध कराता है (B) तथा ठीक वही पूर्वानुमानी ऊपर-से-नीचे पार्सर अवतरण करते समय उत्पन्न करता है (D)। C असत्य है और स्वयं वही प्रतिबंध है: दाएँ सहोदर पर निर्भरता एक बाएँ-से-दाएँ पास में संतुष्ट नहीं हो सकती, क्योंकि उस सहोदर तक अभी पहुँचा ही नहीं गया — उसकी अनुमति देना ही दूसरा भ्रमण बाध्य करता।

  7. int a, b, c; में a, b व c में प्रत्येक तक पहुँचता घोषित प्रकार किसका उदाहरण है:

    1. संश्लेषित गुण
    2. आरोपित गुण
    3. टर्मिनल गुण
    4. शब्दार्थ त्रुटि
    उत्तर देखें

    उत्तर: B — आरोपित गुण

    आरोपित। प्रकार int घोषणा के शीर्ष के निकट पहचाना जाता है और उसे सूची के प्रत्येक नाम तक नीचे सौंपना पड़ता है — सूचना जनक से, या वाम सहोदर से बहती है, संतानों से ऊपर नहीं। वही आरोपित गुण की परिभाषा है, और वह पाठ्यपुस्तकीय उदाहरण ठीक इसलिए है कि संश्लेषित गुण यह नहीं कर सकता: नामों के पास अपने उपवृक्षों से प्रकार निकालने का कोई मार्ग नहीं। यही कारण भी है कि घोषणा-व्याकरण L-गुणित परिभाषाओं की मानक प्रेरणा हैं — प्रकार प्रत्येक नाम तक उसकी बाईं ओर से पहुँचता है, अतः एक बाएँ-से-दाएँ बहाव पर्याप्त है।

  8. त्रि-पता अनुदेश में अधिकतम होता है:

    1. तीन संकारक
    2. एक संकारक
    3. तीन अस्थायी चर
    4. दो अनुदेश
    उत्तर देखें

    उत्तर: B — एक संकारक

    एक संकारक। नाम पतों की गणना करता है — प्रायः एक गंतव्य व दो प्रचालक, अतः "त्रि-पता" — संकारकों की नहीं, और एक-संकारक प्रतिबंध ही उस रूप को उपयोगी बनाता है: प्रत्येक अनुदेश एक मशीन संक्रिया पर निकटता से मानचित्रित होता है, और किसी भी गहराई का व्यंजक वृक्ष अस्थायी चरों को निर्दिष्टीकरणों का सपाट अनुक्रम बन जाता है। विकल्प A नाम का स्वाभाविक भ्रम-पाठ है और जान-बूझकर सुधारने योग्य। वही सपाटपन है जिस पर अगले अध्याय के अनुकूलन काम करते हैं: रैखिक अनुक्रम ही आपको यह पूछने देता है कि कौन-से मान उपलब्ध हैं, कौन जीवित हैं, और कौन-सी गणनाएँ दोहराई जाती हैं।