शिफ्ट-रिड्यूस पार्सर
शिफ्ट-रिड्यूस पार्सर कंप्यूटर भाषाओं और औपचारिक व्याकरण द्वारा औपचारिक रूप से परिभाषित अन्य नोटेशन के लिए कुशल, टेबल-संचालित नीचे से ऊपर का विश्लेषण विधियों का एक वर्ग है। प्रोग्रामिंग भाषाओं, एलआर पार्सर और इसकी विविधताओं को पार्स करने के लिए सबसे अधिक उपयोग की जाने वाली पार्सिंग विधियां शिफ्ट-कम करने की विधियां हैं।[1] एलआर पार्सिंग के आविष्कार से पहले उपयोग किए जाने वाले सरल पूर्ववर्ती पार्सर भी शिफ्ट-कम करने के तरीके हैं। सभी शिफ्ट-रिड्यूस पार्सर्स का बाहरी प्रभाव समान होता है, वृद्धिशील क्रम में जिसमें वे एक पार्स ट्री बनाते हैं या विशिष्ट आउटपुट क्रियाओं को कॉल करते हैं।
सिंहावलोकन
एक शिफ्ट-रिड्यूस पार्सर इनपुट टेक्स्ट को स्कैन करता है और बिना बैकअप के टेक्स्ट के ऊपर से एक फॉरवर्ड पास में पार्स करता है। पार्सर पार्स वृक्ष को क्रमिक रूप से, नीचे से ऊपर और बाएँ से दाएँ बनाता है, बिना अनुमान लगाए या पीछे हटे। इस पास के प्रत्येक बिंदु पर, पार्सर ने इनपुट टेक्स्ट के उपवृक्षों या वाक्यांशों की एक सूची जमा कर ली है जिन्हें पहले ही पार्स किया जा चुका है। वे उपवृक्ष अभी तक एक साथ नहीं जुड़े हैं क्योंकि पार्सर अभी तक सिंटैक्स पैटर्न के दाहिने छोर तक नहीं पहुंचा है जो उन्हें संयोजित करेगा।
स्ट्रिंग पर विचार करें A = B + C * 2.
उदाहरण में चरण 7 पर, केवल ए = बी + को पार्स किया गया है। पार्स वृक्ष का केवल छायांकित निचला-बाएँ कोना मौजूद है। 8 और उससे ऊपर क्रमांकित कोई भी पार्स ट्री नोड अभी तक मौजूद नहीं है। नोड 1, 2, 6, और 7 सभी आइटम 1..7 को कवर करने वाले पृथक उपवृक्षों की जड़ें हैं। नोड 1 वेरिएबल ए है, नोड 2 सीमांकक = है, नोड 6 सारांश बी है, और नोड 7 ऑपरेटर + है। इन चार रूट नोड्स को अस्थायी रूप से पार्स स्टैक में रखा जाता है। इनपुट स्ट्रीम का शेष अनपार्स्ड भाग C * 2 है।
एक शिफ्ट-रिड्यूस पार्सर शिफ्ट स्टेप्स और रिड्यूस स्टेप्स का कुछ संयोजन करके काम करता है, इसलिए इसे यह नाम दिया गया है।
- एक शिफ़्ट चरण इनपुट स्ट्रीम में एक प्रतीक द्वारा आगे बढ़ता है। वह स्थानांतरित प्रतीक एक नया एकल-नोड पार्स ट्री बन जाता है।
- रिड्यूस चरण कुछ हालिया पार्स पेड़ों पर एक पूर्ण व्याकरण नियम लागू करता है, उन्हें एक नए रूट प्रतीक के साथ एक पेड़ के रूप में जोड़ता है।
पार्सर इन चरणों के साथ तब तक जारी रहता है जब तक कि सभी इनपुट का उपभोग नहीं हो जाता और सभी पार्स पेड़ संपूर्ण कानूनी इनपुट का प्रतिनिधित्व करने वाले एक पेड़ में कम नहीं हो जाते।
वृक्ष निर्माण चरण
प्रत्येक पार्स चरण पर, संपूर्ण इनपुट टेक्स्ट को पार्स स्टैक, वर्तमान लुकहेड प्रतीक और शेष अनस्कैन किए गए टेक्स्ट में विभाजित किया जाता है। पार्सर की अगली कार्रवाई सबसे दाहिने स्टैक प्रतीक(चिह्नों) और आगे की ओर देखने वाले प्रतीक द्वारा निर्धारित की जाती है। कार्रवाई को एक तालिका से पढ़ा जाता है जिसमें स्टैक और लुकहेड प्रतीकों के सभी वाक्यात्मक रूप से मान्य संयोजन होते हैं।
| Step | Parse Stack | Look Ahead |
Unscanned | Parser Action |
|---|---|---|---|---|
| 0 | empty | id | = B + C*2 | Shift |
| 1 | id | = | B + C*2 | Shift |
| 2 | id = | id | + C*2 | Shift |
| 3 | id = id | + | C*2 | Reduce by Value ← id |
| 4 | id = Value | + | C*2 | Reduce by Products ← Value |
| 5 | id = Products | + | C*2 | Reduce by Sums ← Products |
| 6 | id = Sums | + | C*2 | Shift |
| 7 | id = Sums + | id | *2 | Shift |
| 8 | id = Sums + id | * | 2 | Reduce by Value ← id |
| 9 | id = Sums + Value | * | 2 | Reduce by Products ← Value |
| 10 | id = Sums + Products | * | 2 | Shift |
| 11 | id = Sums + Products * | int | eof | Shift |
| 12 | id = Sums + Products * int | eof | Reduce by Value ← int | |
| 13 | id = Sums + Products * Value | eof | Reduce by Products ← Products * Value | |
| 14 | id = Sums + Products | eof | Reduce by Sums ← Sums + Products | |
| 15 | id = Sums | eof | Reduce by Assign ← id = Sums | |
| 16 | Assign | eof | Done |
देखना [2] एक सरल उदाहरण के लिए.
व्याकरण
व्याकरण इनपुट भाषा के लिए पैटर्न या वाक्यविन्यास नियमों का सेट है। इसमें सभी भाषा नियमों को शामिल नहीं किया गया है, जैसे कि संख्याओं का आकार, या पूरे कार्यक्रम के संदर्भ में नामों और उनकी परिभाषाओं का लगातार उपयोग। शिफ्ट-कम पार्सर्स एक संदर्भ-मुक्त व्याकरण का उपयोग करते हैं जो केवल प्रतीकों के स्थानीय पैटर्न से संबंधित है।
मिलान करने में सक्षम जावा या सी भाषा के एक छोटे उपसमूह के रूप में व्याकरण का एक उदाहरण A = B + C*2 हो सकता है:
- असाइन करें ← आईडी = रकम
- रकम ← रकम + उत्पाद
- रकम ← उत्पाद
- उत्पाद ← उत्पाद * मूल्य
- उत्पाद ← मूल्य
- मूल्य ← int
- मूल्य ← आईडी
व्याकरण के टर्मिनल प्रतीक बहु-वर्ण प्रतीक या 'टोकन' हैं जो एक शाब्दिक विश्लेषण द्वारा इनपुट स्ट्रीम में पाए जाते हैं। यहां इनमें किसी भी पूर्णांक स्थिरांक के लिए '=' '+' '*' और int, और किसी भी पहचानकर्ता नाम के लिए id शामिल हैं। व्याकरण को इसकी परवाह नहीं है कि int मान या id वर्तनी क्या हैं, न ही यह रिक्त स्थान या पंक्ति विराम की परवाह करता है। व्याकरण इन टर्मिनल प्रतीकों का उपयोग करता है लेकिन उन्हें परिभाषित नहीं करता है। वे हमेशा पार्स पेड़ के निचले झाड़ीदार सिरे पर होते हैं।
सम्स जैसे बड़े अक्षर वाले शब्द नॉनटर्मिनल प्रतीक हैं। ये भाषा में अवधारणाओं या पैटर्न के नाम हैं। वे व्याकरण में परिभाषित हैं और इनपुट स्ट्रीम में स्वयं कभी नहीं आते हैं। वे सदैव पार्स वृक्ष के नीचे से ऊपर होते हैं। वे केवल पार्सर द्वारा कुछ व्याकरण नियम लागू करने के परिणामस्वरूप होते हैं। कुछ नॉनटर्मिनलों को दो या दो से अधिक नियमों से परिभाषित किया गया है; ये वैकल्पिक पैटर्न हैं. नियम स्वयं को वापस संदर्भित कर सकते हैं। यह व्याकरण दोहराए गए गणित ऑपरेटरों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करता है। संपूर्ण भाषाओं के व्याकरण सूचियों, कोष्ठक में रखे गए भावों और नेस्टेड कथनों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करते हैं।
किसी भी कंप्यूटर भाषा को कई अलग-अलग व्याकरणों द्वारा वर्णित किया जा सकता है। शिफ्ट-रिड्यूस पार्सर के लिए व्याकरण स्वयं अस्पष्ट व्याकरण होना चाहिए, या टाई-ब्रेकिंग प्राथमिकता नियमों द्वारा संवर्धित किया जाना चाहिए। इसका मतलब यह है कि भाषा के किसी दिए गए कानूनी उदाहरण में व्याकरण को लागू करने का केवल एक ही सही तरीका है, जिसके परिणामस्वरूप एक अद्वितीय पार्स ट्री और उस उदाहरण के लिए बदलाव/घटाने की क्रियाओं का एक अद्वितीय अनुक्रम होता है।
एक टेबल-संचालित पार्सर के पास व्याकरण के बारे में अपना सारा ज्ञान अपरिवर्तनीय डेटा में एन्कोड किया गया होता है जिसे पार्सर टेबल कहा जाता है। पार्सर का प्रोग्राम कोड एक सरल सामान्य लूप है जो कई व्याकरणों और भाषाओं पर अपरिवर्तित लागू होता है। प्राथमिकता पद्धतियों के लिए तालिकाओं को हाथ से तैयार किया जा सकता है। एलआर विधियों के लिए, जटिल तालिकाओं को जीएनयू बाइसन जैसे कुछ पार्सर जनरेटर टूल द्वारा व्याकरण से यांत्रिक रूप से प्राप्त किया जाता है।[3] पार्सर तालिकाएँ आमतौर पर व्याकरण से बहुत बड़ी होती हैं। अन्य पार्सर्स में जो टेबल-संचालित नहीं हैं, जैसे कि पुनरावर्ती वंश, प्रत्येक भाषा निर्माण को एक अलग सबरूटीन द्वारा पार्स किया जाता है, जो उस एक निर्माण के सिंटैक्स के लिए विशेष होता है।
पार्सर क्रियाएँ
शिफ्ट-रिड्यूस पार्सर कुशल है क्योंकि इसमें कोई बैकअप शामिल नहीं है। इसका कुल निष्पादन समय इनपुट की लंबाई और पूर्ण पार्स ट्री के आकार के साथ रैखिक रूप से बढ़ता है। अन्य पार्सर विधियाँ जो खराब अनुमान लगाने पर पीछे हटने में तेजी से समय ले सकती हैं।[citation needed]
अनुमान लगाने से बचने के लिए, शिफ्ट-रिड्यूस पार्सर अक्सर पहले से स्कैन किए गए प्रतीकों के साथ क्या करना है, यह तय करने से पहले अगले स्कैन किए गए प्रतीक पर आगे (बाएं से दाएं पाठ में दाईं ओर) देखता है। लेक्सिकल स्कैनर बाकी पार्सर से एक प्रतीक आगे काम करता है। प्रत्येक पार्सिंग निर्णय के लिए लुकहेड प्रतीक को 'दाहिने हाथ का संदर्भ' भी कहा जाता है। (शायद ही, दो या दो से अधिक लुकहेड प्रतीकों का उपयोग किया जा सकता है, हालांकि अधिकांश व्यावहारिक व्याकरणों को एक लुकहेड प्रतीक का उपयोग करने के लिए डिज़ाइन किया जा सकता है।)
एक शिफ्ट-रिड्यूस पार्सर तब तक इंतजार करता है जब तक कि वह संयुक्त निर्माण के लिए प्रतिबद्ध होने से पहले कुछ निर्माण के सभी हिस्सों को स्कैन और पार्स नहीं कर लेता। फिर पार्सर किसी और प्रतीक्षा के बजाय संयोजन पर तुरंत कार्य करता है। ऊपर दिए गए पार्स ट्री उदाहरण में, जैसे ही + को लुकहेड में देखा जाता है, वाक्यांश बी को मूल्य में और फिर चरण 3-6 में उत्पाद और रकम में बदल दिया जाता है, पार्स ट्री के उन हिस्सों को व्यवस्थित करने के लिए अब और इंतजार करने के बजाय। बी को कैसे संभालना है इसका निर्णय केवल उस पर आधारित होता है जो पार्सर और स्कैनर ने पहले ही देखा है, उन चीजों पर विचार किए बिना जो दाईं ओर बहुत बाद में दिखाई देती हैं।
कटौती सबसे हाल ही में पार्स की गई चीजों को पुनर्गठित करती है, यानी, लुकहेड प्रतीक के तुरंत बाईं ओर। तो पहले से ही पार्स की गई चीजों की सूची एक स्टैक (सार डेटा प्रकार) की तरह काम करती है। यह पार्स स्टैक दाईं ओर बढ़ता है। स्टैक का आधार या तल बायीं ओर है और सबसे बायीं ओर, सबसे पुराना पार्स टुकड़ा रखता है। प्रत्येक कटौती चरण केवल सबसे दाहिने, नवीनतम पार्स अंशों पर कार्य करता है। (यह संचयी पार्स स्टैक ऊपर से नीचे पार्सर्स द्वारा उपयोग किए जाने वाले पूर्वानुमानित, बाईं ओर बढ़ने वाले पार्स स्टैक से बहुत अलग है।)
जब कोई व्याकरण नियम जैसे
- उत्पाद ← उत्पाद * मूल्य
लागू किया जाता है, स्टैक टॉप पार्स ट्री रखता है ... उत्पाद * मूल्य। नियम के दाहिनी ओर के इस पाए गए उदाहरण को हैंडल कहा जाता है। कम करने का चरण हैंडल उत्पाद * मान को बायीं ओर के गैर टर्मिनल से बदल देता है, इस मामले में एक बड़ा उत्पाद। यदि पार्सर पूर्ण पार्स ट्री बनाता है, तो आंतरिक उत्पादों के लिए तीन पेड़, *, और मूल्य को बड़े उत्पादों के लिए एक नए पेड़ की जड़ से जोड़ दिया जाता है। अन्यथा, आंतरिक उत्पादों और मूल्य से सिमेंटिक्स#प्रोग्रामिंग भाषाओं का विवरण कुछ बाद के कंपाइलर पास में आउटपुट होता है, या नए उत्पाद प्रतीक में संयुक्त और सहेजा जाता है।[4] पार्सर तब तक पार्स स्टैक के शीर्ष पर कटौती लागू करता रहता है जब तक वह वहां व्याकरण नियमों के नए पूर्ण किए गए उदाहरण ढूंढता रहता है। जब कोई और नियम लागू नहीं किया जा सकता है, तो पार्सर लुकहेड प्रतीक को पार्स स्टैक पर स्थानांतरित कर देता है, एक नया लुकहेड प्रतीक स्कैन करता है, और फिर से प्रयास करता है।
शिफ्ट-रिड्यूस पार्सर्स के प्रकार
पार्सर तालिकाएँ दिखाती हैं कि शीर्षस्थ पार्स स्टैक प्रतीकों और लुकहेड प्रतीक के प्रत्येक कानूनी संयोजन के लिए आगे क्या करना है। वह अगला कार्य अद्वितीय होना चाहिए; या तो बदलाव करें, या कम करें, लेकिन दोनों नहीं। (इसका तात्पर्य स्पष्ट होने से परे, व्याकरण पर कुछ और सीमाओं से है।) विभिन्न प्रकार के शिफ्ट-रिड्यूस पार्सर्स के बीच तालिका का विवरण बहुत भिन्न होता है।
पूर्ववर्ती पार्सर्स में, शीर्ष स्टैक प्रतीकों की पूर्ववर्ती स्तर या व्याकरण की जकड़न की तुलना लुकहेड प्रतीक से करके हैंडल का दाहिना सिरा पाया जाता है। उपरोक्त उदाहरण में, int और id कथन सीमांकक की तुलना में आंतरिक व्याकरण स्तर से संबंधित हैं। इसलिए int और id दोनों को इससे अधिक प्राथमिकता वाला माना जाता है; और जब भी ; का अनुसरण किया जाए तो इसे किसी अन्य चीज़ में घटा दिया जाना चाहिए। पूर्ववर्ती पार्सर की विभिन्न किस्में हैं, जिनमें से प्रत्येक में हैंडल के बाएं छोर को ढूंढने और लागू करने के लिए सही नियम चुनने के विभिन्न तरीके हैं:
- ऑपरेटर-प्राथमिकता पार्सर, एक बहुत ही सरल संख्यात्मक विधि जो अभिव्यक्तियों के लिए काम करती है लेकिन सामान्य प्रोग्राम सिंटैक्स के लिए नहीं।
- सरल पूर्वता पार्सर, दाएं और बाएं छोर को खोजने के लिए एक बड़ी एमएक्सएन तालिका का उपयोग करता है। PL360 में प्रयुक्त.[5] सामान्य प्रोग्रामिंग भाषाओं को संभाल नहीं पाता.
- कमजोर पूर्वता पार्सर, केवल हैंडल के दाहिने सिरे को खोजने के लिए पूर्वता तालिका का उपयोग करता है। साधारण पूर्वता की तुलना में अधिक व्याकरणों को संभालता है।[6]
- विस्तारित प्राथमिकता पार्सर.
- मिश्रित रणनीति प्राथमिकता पार्सर, XPL के मूल संस्करण द्वारा उपयोग किया जाता है। त्रिगुणों को शामिल करने के लिए, किसी भी पूर्वता पहचानकर्ता में निहित युगलों का विस्तार करता है। एसएलआर से कम शक्तिशाली. आम तौर पर XPL जैसी अपेक्षाकृत छोटी भाषाओं के लिए भी बहुत बड़ी तालिकाएँ होती हैं, क्योंकि बड़ी संख्या में त्रिगुणों की आवश्यकता होती है, जिन्हें पूर्ववर्ती तरीकों द्वारा लगाई गई सीमाओं के बाहर व्याकरण को पहचानने की आवश्यकता होती है।[7]
प्राथमिकता पार्सर्स उन व्याकरणों में सीमित हैं जिन्हें वे संभाल सकते हैं। निर्णय लेते समय वे अधिकांश पार्स स्टैक को अनदेखा कर देते हैं। वे केवल सर्वोच्च प्रतीकों के नामों पर विचार करते हैं, न कि उस पूरे संदर्भ पर, जहां वे प्रतीक अब व्याकरण में कहां दिखाई दे रहे हैं। प्राथमिकता के लिए आवश्यक है कि समान दिखने वाले प्रतीक संयोजनों को पूरे व्याकरण में समान तरीकों से पार्स और उपयोग किया जाना चाहिए, हालांकि वे संयोजन संदर्भ की परवाह किए बिना होते हैं।
एलआर पार्सर शिफ्ट-रिड्यूस पार्सिंग का एक अधिक लचीला रूप है, जो कई और व्याकरणों को संभालता है।[8]
एलआर पार्सर प्रोसेसिंग
एलआर पार्सर्स एक पुशडाउन ऑटोमेटन की तरह कार्य करते हैं, जो प्रत्येक शिफ्ट या कम कार्रवाई के लिए एक राज्य संक्रमण करते हैं। ये एक स्टैक का उपयोग करते हैं जहां वर्तमान स्थिति को शिफ्ट क्रियाओं द्वारा नीचे धकेल दिया जाता है। फिर इस स्टैक को कम क्रियाओं द्वारा पॉप (अप) किया जाता है। यह तंत्र एलआर पार्सर को सभी नियतात्मक संदर्भ-मुक्त व्याकरणों को संभालने की अनुमति देता है, जो पूर्ववर्ती व्याकरणों का एक सुपरसेट है। एलआर पार्सर पूरी तरह से कैनोनिकल एलआर पार्सर द्वारा कार्यान्वित किया जाता है। एलएएलआर पार्सर|लुक-अहेड एलआर और सरल एलआर पार्सर पार्सर इसके सरलीकृत वेरिएंट को लागू करते हैं जिससे मेमोरी आवश्यकताओं में काफी कमी आई है।[9][10] हाल के शोध ने उन तरीकों की पहचान की है जिनके द्वारा कैनोनिकल एलआर पार्सर्स को नथ के टेबल-बिल्डिंग एल्गोरिदम पर नाटकीय रूप से कम टेबल आवश्यकताओं के साथ लागू किया जा सकता है।[11] चाहे एलआर, एलएएलआर या एसएलआर, मूल राज्य मशीन एक ही है; केवल तालिकाएँ भिन्न होती हैं, और ये तालिकाएँ लगभग हमेशा यंत्रवत् उत्पन्न होती हैं। इसके अतिरिक्त, इन तालिकाओं को आम तौर पर इस तरह कार्यान्वित किया जाता है कि REDUCE के परिणामस्वरूप एक बंद सबरूटीन पर कॉल आती है जो राज्य मशीन के लिए बाहरी है और जो एक कार्य करता है जो कि व्याकरण नियम के शब्दार्थ द्वारा निहित है जिसे REDUCE किया जा रहा है। इसलिए, पार्सर को एक अपरिवर्तनीय राज्य मशीन भाग और एक भिन्न शब्दार्थ भाग में विभाजित किया गया है। यह मूलभूत अंतर उच्च गुणवत्ता वाले पार्सर्स के विकास को प्रोत्साहित करता है जो असाधारण रूप से विश्वसनीय हैं।
एक विशिष्ट स्टैक स्थिति और लुकआहेड प्रतीक को देखते हुए, सटीक रूप से चार संभावित क्रियाएं हैं, त्रुटि, शिफ्ट, कम करें और रोकें (इसके बाद कॉन्फ़िगरेशन के रूप में संदर्भित)। कॉन्फ़िगरेशन में एक बिंदु की उपस्थिति, •, वर्तमान लुकहेड स्थिति का प्रतिनिधित्व करती है, जिसमें लुकहेड प्रतीक बिंदु के दाईं ओर दिखाया गया है (और जो हमेशा एक टर्मिनल प्रतीक से मेल खाता है), और वर्तमान स्टैक स्थिति बिंदु के बाईं ओर दिखाई देती है (और जो आमतौर पर एक नॉनटर्मिनल प्रतीक से मेल खाता है)।
उच्च प्रदर्शन सहित व्यावहारिक कारणों से, तालिकाओं को आम तौर पर दो-बिट प्रतीकों की कुछ बड़ी, सहायक सरणी द्वारा विस्तारित किया जाता है, जो स्पष्ट रूप से बाइट-उन्मुख मशीनों पर कुशल पहुंच के लिए चार दो-बिट प्रतीकों, एक बाइट में संपीड़ित होती है, जिसे अक्सर एन्कोड किया जाता है :
- '00'बी त्रुटि का प्रतिनिधित्व करता है
- '01'बी SHIFT को दर्शाता है
- '10'बी REDUCE को दर्शाता है
- '11'बी स्टॉप को दर्शाता है
(SHIFT का विशेष मामला बनना बंद करें)। संपूर्ण सरणी में आम तौर पर अधिकतर त्रुटि कॉन्फ़िगरेशन, SHIFT और REDUCE कॉन्फ़िगरेशन की व्याकरण-परिभाषित संख्या और एक STOP कॉन्फ़िगरेशन शामिल होता है।
प्रोग्रामिंग प्रणालियों में जो चतुर्धातुक अंक प्रणाली (आधार 4, प्रति चतुर्धातुक अंक दो बिट) में मानों के विनिर्देशन का समर्थन करते हैं, जैसे कि XPL, इन्हें इस प्रकार कोडित किया जाता है, उदाहरण के लिए:
- (2)...'0'...त्रुटि को दर्शाता है
- (2)...'1'...शिफ्ट का प्रतिनिधित्व करता है
- (2)...'2'...कम करना दर्शाता है
- (2)...'3'...स्टॉप को दर्शाता है
SHIFT और REDUCE तालिकाओं को सरणी से अलग से लागू किया जाता है। सहायक सरणी की जांच केवल वर्तमान स्थिति और लुकआहेड प्रतीक के लिए की जाती है। (सहायक) सरणी भरी हुई है, जबकि (शिफ्ट और कम) तालिकाएं वास्तव में बहुत विरल हो सकती हैं, और उन SHIFT और REDUCE तालिकाओं के इष्टतम अपघटन के माध्यम से महत्वपूर्ण दक्षताएं प्राप्त की जा सकती हैं (ERROR और STOP को तालिकाओं की आवश्यकता नहीं है)।
SHIFT-REDUCE पार्सर की मूल परिभाषा से SHIFT और REDUCE कॉन्फ़िगरेशन स्पष्ट हैं।
STOP, फिर, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करता है जहां स्टैक के शीर्ष पर स्थिति और लुकहेड टर्मिनल प्रतीक विषय व्याकरण के भीतर है, और कार्यक्रम के अंत का प्रतिनिधित्व करता है:
- '⊥' <कार्यक्रम> '•' '⊥'
वैचारिक रूप से पहुँचने के लिए अंतिम '⊥' से आगे SHIFT करना असंभव है
- '⊥' <कार्यक्रम> '⊥' '•'
त्रुटि, तब, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करती है जहां स्टैक के शीर्ष पर स्थिति, और लुकहेड टर्मिनल प्रतीक विषय व्याकरण के भीतर नहीं है। यह एक त्रुटि पुनर्प्राप्ति प्रक्रिया को लागू करने का अवसर प्रस्तुत करता है, शायद, इसके सबसे सरल रूप में, लुकहेड टर्मिनल प्रतीक को त्यागने और अगले टर्मिनल प्रतीक को पढ़ने के लिए, लेकिन स्टैक को काटने, या लुकहेड को त्यागने सहित कई अन्य प्रोग्राम किए गए कार्य संभव हैं टर्मिनल प्रतीक और स्टैक की छंटाई (और एक पैथोलॉजिकल मामले में, इसे प्राप्त करना आमतौर पर संभव है
- '⊥' <कार्यक्रम> '•' '⊥'
जहां <प्रोग्राम> में केवल एक एनओपी (कोड) होता है| शून्य कथन)।
ज्यादातर मामलों में, स्टैक को जानबूझकर प्री-लोड किया जाता है, यानी आरंभीकृत किया जाता है
- '⊥' '•' <प्रोग्राम> '⊥'
जिससे प्रारंभिक '⊥' को पहले ही पहचाना जा चुका माना जाता है। यह, तब, प्रोग्राम की शुरुआत का प्रतिनिधित्व करता है, और, इस प्रकार, एक अलग START कॉन्फ़िगरेशन होने से बचता है, जो कि वैचारिक रूप से है
- '•' '⊥' <प्रोग्राम> '⊥'
'⊥' यांत्रिक रूप से व्याकरण में जोड़ा गया एक विशेष छद्म-टर्मिनल प्रतीक है, जैसे <प्रोग्राम> यांत्रिक रूप से एक विशेष छद्म-नॉनटर्मिनल प्रतीक हैव्याकरण में जोड़ा गया (यदि प्रोग्रामर ने व्याकरण में <प्रोग्राम> को स्पष्ट रूप से शामिल नहीं किया है, तो प्रोग्रामर की ओर से <प्रोग्राम> स्वचालित रूप से व्याकरण में जोड़ा जाएगा)।
स्पष्ट रूप से, ऐसे पार्सर में सटीक रूप से एक (अंतर्निहित) START कॉन्फ़िगरेशन और एक (स्पष्ट) STOP कॉन्फ़िगरेशन होता है, लेकिन इसमें सैकड़ों SHIFT और REDUCE कॉन्फ़िगरेशन और शायद हजारों त्रुटि कॉन्फ़िगरेशन हो सकते हैं और आमतौर पर होते हैं।
संदर्भ
- ↑ Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.
- ↑ "संग्रहीत प्रति" (PDF). dragonbook.stanford.edu. Archived from the original (PDF) on 5 March 2016. Retrieved 17 January 2022.
- ↑ Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.
- ↑ Crafting a Compiler, by Fischer, Ron , and Richard , Addison Wesley 2009.
- ↑ PL360 - A Programming Language for the 360 Computers, by Niklaus Wirth, J. ACM 15:1 1968.
- ↑ The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing, by Alfred Aho and Jeffrey Ullman, Prentice Hall 1972.
- ↑ A Compiler Generator, by William M. McKeeman, J Horning, and D Wortman, Prentice Hall 1970; ISBN 978-0131550773.
- ↑ Knuth, D. E. (July 1965). "भाषाओं के बाएँ से दाएँ अनुवाद पर" (PDF). Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. Retrieved 29 May 2011.
- ↑ Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.
- ↑ Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.
- ↑ X. Chen, Measuring and extending LR(1) parsing, University of Hawaii PhD dissertation, 2009.
