शिफ्ट-रिड्यूस पार्सर
शिफ्ट-रिड्यूस पार्सर कंप्यूटर लैंग्वेज और व्याकरण द्वारा औपचारिक रूप से परिभाषित अन्य नोटेशन के लिए कुशल, टेबल-संचालित बॉटम-अप पार्सिंग विधियों का एक वर्ग है। प्रोग्रामिंग लैंग्वेज, एलआर पार्सिंग और इसकी विविधताओं को पार्स करने के लिए सबसे अधिक उपयोग की जाने वाली पार्सिंग विधियाँ शिफ्ट-कम करने की विधियाँ हैं।[1] एलआर पार्सिंग के आविष्कार से पहले उपयोग किए जाने वाले पूर्ववर्ती पार्सर भी शिफ्ट-कम करने के विधियां हैं। सभी शिफ्ट-रिड्यूस पार्सर्स के समान बाहरी प्रभाव होते हैं, वृद्धिशील क्रम में जिसमें वे पार्स ट्री बनाते हैं या विशिष्ट आउटपुट क्रियाओं को कॉल करते हैं।
सिंहावलोकन
शिफ्ट-रिड्यूस पार्सर इनपुट टेक्स्ट को स्कैन और पार्स करता है, बिना बैकअप के, टेक्स्ट के ऊपर से एक फॉरवर्ड पास में। पार्सर पार्स ट्री को क्रमिक रूप से, नीचे से ऊपर और बाएँ से दाएँ बनाता है, बिना अनुमान लगाए या पीछे हटे। इस पास के प्रत्येक बिंदु पर, पार्सर ने इनपुट टेक्स्ट के सबट्री या वाक्यांशों की एक सूची जमा की है जिन्हें पहले ही पार्स किया जा चुका है। वे सबट्री अभी तक एक साथ नहीं जुड़े हैं क्योंकि पार्सर अभी तक सिंटैक्स पैटर्न के दाहिने छोर तक नहीं पहुंचा है जो उन्हें संयोजित करेगा।
स्ट्रिंग पर विचार करें A = B + C * 2.
उदाहरण के चरण 7 में, केवल "A = B +" को पार्स किया गया है। पार्स ट्री का केवल छायांकित निचला-बाएँ कोना ही उपस्थित है। 8 और उससे अधिक संख्या वाला कोई भी पार्स ट्री नोड अभी तक उपस्थित नहीं है। नोड्स 1, 2, 6, और 7 सभी आइटम 1..7 को कवर करने वाले अलग-अलग सबट्री का रुट हैं। नोड 1 वेरिएबल A है, नोड 2 डिलीमीटर = है, नोड 6 सारांश B है, और नोड 7 ऑपरेटर + है। ये चार रूट नोड्स अस्थायी रूप से एक पार्स स्टैक में रखे जाते हैं। इनपुट स्ट्रीम का शेष अनपार्स किया गया भाग "C * 2" है।
शिफ्ट-रिड्यूस पार्सर शिफ्ट स्टेप्स और रिड्यूस स्टेप्स का कुछ संयोजन करके काम करता है, इसलिए इसे नाम दिया गया है।
- शिफ़्ट चरण इनपुट स्ट्रीम में सिंबल (प्रतीक) द्वारा आगे बढ़ता है। वह स्थानांतरित सिंबल एक नया एकल-नोड पार्स ट्री बन जाता है।
- रिड्यूस कदम हाल के कुछ पार्स ट्री पर एक पूर्ण व्याकरण नियम प्रयुक्त करता है, उन्हें एक नए रूट सिंबल के साथ एक ट्री के रूप में जोड़ता है। पार्सर इन चरणों के साथ तब तक जारी रहता है जब तक कि सभी इनपुट का उपभोग नहीं हो जाता है और सभी पार्स ट्री पूरे कानूनी इनपुट का प्रतिनिधित्व करने वाले एक ट्री में कम हो जाते हैं।
ट्री निर्माण चरण
प्रत्येक पार्स चरण में, संपूर्ण इनपुट टेक्स्ट को पार्स स्टैक, वर्तमान लुकहेड सिंबल और शेष अनस्कैन टेक्स्ट में विभाजित किया जाता है। पार्सर की अगली क्रिया सबसे दाएँ स्टैक सिंबल (चिह्नों) और आगे की ओर देखने वाले सिंबल द्वारा निर्धारित होती है। कार्रवाई को एक तालिका से पढ़ा जाता है जिसमें स्टैक और लुकहेड सिंबल के सभी वाक्यविन्यास रूप से मान्य संयोजन होते हैं।
| चरण | पार्स स्टैक | आगे देखें | अनस्कैन्ड | पार्सर एक्शन |
|---|---|---|---|---|
| 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]।
व्याकरण
व्याकरण इनपुट लैंग्वेज के लिए पैटर्न या वाक्य रचना नियमों का समूह है। इसमें सभी लैंग्वेज नियम सम्मिलित नहीं हैं, जैसे संख्याओं का आकार, या पूरे कार्यक्रम के संदर्भ में नामों और उनकी परिभाषाओं का लगातार उपयोग। शिफ्ट-कम करने वाले पार्सर्स संदर्भ-मुक्त व्याकरण का उपयोग करते हैं जो केवल सिंबल के स्थानीय पैटर्न से संबंधित है।
जावा या C लैंग्वेज के एक छोटे उपसमुच्चय के रूप में व्याकरण का एक उदाहरण जो A = B + C*2 से मेल खाने में सक्षम है:
- Assign ← id = Sums
- Sums ← Sums + Products
- Sums ← Products
- Products ← Products * Value
- Products ← Value
- Value ← int
- Value ← id
व्याकरण के टर्मिनल सिंबल बहु-वर्ण सिंबल या 'टोकन' हैं जो एक लेक्सिकल स्कैनर द्वारा इनपुट स्ट्रीम में पाए जाते हैं। यहां इनमें किसी भी पूर्णांक स्थिरांक के लिए = + * और int, और किसी भी पहचानकर्ता नाम के लिए id सम्मिलित हैं। व्याकरण को इसकी परवाह नहीं है कि int मान या id वर्तनी क्या हैं, न ही यह रिक्त स्थान या पंक्ति विराम की परवाह करता है। व्याकरण इन टर्मिनल सिंबल का उपयोग करता है लेकिन उन्हें परिभाषित नहीं करता है। वे हमेशा पार्स ट्री के निचले बशी सिरे पर होते हैं।
सम्स जैसे बड़े अक्षर वाले शब्द नॉनटर्मिनल सिंबल हैं। ये लैंग्वेज में अवधारणाओं या पैटर्न के नाम हैं। वे व्याकरण में परिभाषित हैं और इनपुट स्ट्रीम में स्वयं कभी नहीं आते हैं। वे सदैव पार्स ट्री के नीचे से ऊपर होते हैं। वे केवल पार्सर द्वारा कुछ व्याकरण नियम प्रयुक्त करने के परिणामस्वरूप होते हैं। कुछ नॉनटर्मिनलों को दो या दो से अधिक नियमों से परिभाषित किया गया है; ये वैकल्पिक पैटर्न हैं. नियम स्वयं को वापस संदर्भित कर सकते हैं। यह व्याकरण दोहराए गए गणित ऑपरेटरों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करता है। संपूर्ण लैंग्वेज के व्याकरण सूचियों, कोष्ठक में रखे गए भावों और नेस्टेड कथनों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करते हैं।
किसी भी कंप्यूटर लैंग्वेज को कई अलग-अलग व्याकरणों द्वारा वर्णित किया जा सकता है। शिफ्ट-रिड्यूस पार्सर के लिए व्याकरण स्वयं स्पष्ट होना चाहिए, या टाई-ब्रेकिंग प्राथमिकता नियमों द्वारा संवर्धित किया जाना चाहिए। इसका मतलब यह है कि लैंग्वेज के किसी दिए गए कानूनी उदाहरण में व्याकरण को प्रयुक्त करने का केवल एक ही सही विधि है, जिसके परिणामस्वरूप एक अद्वितीय पार्स ट्री और उस उदाहरण के लिए शिफ्ट/घटाने की क्रियाओं का एक अद्वितीय अनुक्रम होता है।
एक टेबल-संचालित पार्सर के पास व्याकरण के बारे में अपना सारा ज्ञान अपरिवर्तनीय डेटा में एन्कोड किया गया होता है जिसे पार्सर टेबल कहा जाता है। पार्सर का प्रोग्राम कोड एक सरल सामान्य लूप है जो कई व्याकरणों और लैंग्वेज पर अपरिवर्तित प्रयुक्त होता है। प्राथमिकता पद्धतियों के लिए तालिकाओं को हाथ से तैयार किया जा सकता है। एलआर विधियों के लिए, जटिल तालिकाओं को बाइसन जैसे कुछ पार्सर जनरेटर टूल द्वारा व्याकरण से यांत्रिक रूप से प्राप्त किया जाता है।[3] पार्सर तालिकाएँ सामान्यतः व्याकरण से बहुत बड़ी होती हैं। अन्य पार्सर्स में जो टेबल-संचालित नहीं हैं, जैसे कि पुनरावर्ती वंश, प्रत्येक लैंग्वेज निर्माण को एक अलग सबरूटीन द्वारा पार्स किया जाता है, जो उस एक निर्माण के सिंटैक्स के लिए विशेष होता है।
पार्सर एक्शन्स
शिफ्ट-रिड्यूस पार्सर कुशल है क्योंकि इसमें कोई बैकअप नहीं होता है। इसका कुल निष्पादन समय इनपुट की लंबाई और पूर्ण पार्स ट्री के आकार के साथ रैखिक रूप से बढ़ता है। अन्य पार्सर विधियाँ जो गलत अनुमान लगाने पर पीछे की ओर जाती हैं, उन्हें बहुत अधिक समय लग सकता है।
अनुमान लगाने से बचने के लिए, शिफ्ट-रिड्यूस पार्सर प्रायः पहले से स्कैन किए गए सिंबल के साथ क्या करना है, यह निर्णय लेने से पहले अगले स्कैन किए गए सिंबल पर आगे (बाएं से दाएं पाठ में दाईं ओर) देखता है। लेक्सिकल स्कैनर बाकी पार्सर से एक सिंबल आगे काम करता है। प्रत्येक विश्लेषण निर्णय के लिए लुकहेड सिंबल को 'दाहिने हाथ का संदर्भ' भी कहा जाता है। (शायद ही, दो या अधिक लुकहेड सिंबल का उपयोग किया जा सकता है, हालांकि अधिकांश व्यावहारिक व्याकरणों को एक लुकहेड सिंबल का उपयोग करने के लिए डिज़ाइन किया जा सकता है।)
एक शिफ्ट-रिड्यूस पार्सर तब तक प्रतीक्षा करता है जब तक कि उसने संयुक्त निर्माण के लिए प्रतिबद्ध होने से पहले कुछ निर्माण के सभी हिस्सों को स्कैन और पार्स नहीं कर लिया हो। इसके बाद पार्सर आगे इंतजार करने के बजाय तुरंत संयोजन पर कार्य करता है। ऊपर दिए गए पार्स ट्री उदाहरण में, जैसे ही + को लुकहेड में देखा जाता है, वाक्यांश बी को मूल्य में और फिर चरण 3-6 में उत्पाद और रकम में बदल दिया जाता है, पार्स ट्री के उन हिस्सों को व्यवस्थित करने के लिए अब और इंतजार करने के बजाय। बी को कैसे संभालना है, इस पर निर्णय केवल उस पर आधारित होते हैं जो पार्सर और स्कैनर ने पहले ही देखा है, उन चीजों पर विचार किए बिना जो बहुत बाद में दाईं ओर दिखाई देती हैं।
कट हाल ही में पार्स किए गए को पुनर्गठित करता है, यानी, लुकहेड सिंबल के ठीक बाईं ओर। इसलिए पहले से पार्स की गई चीज़ों की सूची एक स्टैक की तरह काम करती है। यह पार्स स्टैक दाईं ओर बढ़ता है। स्टैक का आधार या निचला भाग बायीं ओर है और सबसे बायीं ओर, सबसे पुराना पार्स टुकड़ा रखता है। प्रत्येक कमी चरण केवल सबसे दाएँ, नवीनतम पार्स अंशों पर कार्य करता है। (यह संचयी पार्स स्टैक ऊपर से नीचे पार्सर्स द्वारा उपयोग किए जाने वाले पूर्वानुमानित, बाईं ओर बढ़ने वाले पार्स स्टैक से बहुत अलग है।)
जब कोई व्याकरण नियम जैसे
Products ← Products * Value
प्रयुक्त किया जाता है, स्टैक शीर्ष पर पार्स ट्री "... उत्पाद * मूल्य" होता है। नियम के दायीं ओर का यह पाया गया उदाहरण हैंडल कहलाता है। कम करने का चरण बायीं ओर के गैर टर्मिनल द्वारा "उत्पाद * मूल्य" हैंडल को प्रतिस्थापित करता है, इस स्थिति में एक बड़ा उत्पाद। यदि पार्सर पूर्ण पार्स ट्री बनाता है, तो आंतरिक उत्पादों के लिए तीन ट्री, *, और मूल्य को बड़े उत्पादों के लिए एक नए ट्री की रुट द्वारा संयोजित किया जाता है। अन्यथा, आंतरिक उत्पादों और मूल्य से अर्थ संबंधी विवरण कुछ बाद के कंपाइलर पास में आउटपुट होते हैं, या नए उत्पाद सिंबल में संयुक्त और सेव किये जाते हैं।[4]
पार्सर तब तक पार्स स्टैक के शीर्ष पर कटौती प्रयुक्त करता रहता है जब तक वह वहां व्याकरण नियमों के नए पूर्ण किए गए उदाहरण ढूंढता रहता है। जब कोई और नियम प्रयुक्त नहीं किया जा सकता है, तो पार्सर लुकहेड सिंबल को पार्स स्टैक पर स्थानांतरित कर देता है, एक नया लुकहेड सिंबल स्कैन करता है, और फिर से प्रयास करता है।
शिफ्ट-रिड्यूस पार्सर्स के प्रकार
पार्सर तालिकाएँ दिखाती हैं कि शीर्षस्थ पार्स स्टैक सिंबल और लुकहेड सिंबल के प्रत्येक कानूनी संयोजन के लिए आगे क्या करना है। वह अगला कार्य अद्वितीय होना चाहिए; या तो बदलाव करें, या कम करें, लेकिन दोनों नहीं। (इसका तात्पर्य स्पष्ट होने से परे, व्याकरण पर कुछ और सीमाओं से है।) विभिन्न प्रकार के शिफ्ट-रिड्यूस पार्सर्स के बीच तालिका का विवरण बहुत भिन्न होता है।
पूर्ववर्ती पार्सर्स में, शीर्ष स्टैक सिंबल की पूर्ववर्ती स्तर या व्याकरण की जकड़न की तुलना लुकहेड सिंबल से करके हैंडल का दाहिना सिरा पाया जाता है। उपरोक्त उदाहरण में, int और id कथन सीमांकक की तुलना में आंतरिक व्याकरण स्तर से संबंधित हैं। इसलिए int और id दोनों को इससे अधिक प्राथमिकता वाला माना जाता है; और जब भी ; का अनुसरण किया जाए तो इसे किसी अन्य चीज़ में घटा दिया जाना चाहिए। पूर्ववर्ती पार्सर की विभिन्न किस्में हैं, जिनमें से प्रत्येक में हैंडल के बाएं छोर को ढूंढने और प्रयुक्त करने के लिए सही नियम चुनने के विभिन्न विधियां हैं:
- ऑपरेटर-प्राथमिकता पार्सर, एक बहुत ही सरल संख्यात्मक विधि जो अभिव्यक्तियों के लिए काम करती है लेकिन सामान्य प्रोग्राम सिंटैक्स के लिए नहीं।
- सरल पूर्वता पार्सर, दाएं और बाएं छोर को खोजने के लिए एक बड़ी एमएक्सएन तालिका का उपयोग करता है। PL360 में प्रयुक्त.[5] सामान्य प्रोग्रामिंग लैंग्वेज को संभाल नहीं पाता.
- कमजोर पूर्वता पार्सर, केवल हैंडल के दाहिने सिरे को खोजने के लिए पूर्वता तालिका का उपयोग करता है। साधारण पूर्वता की तुलना में अधिक व्याकरणों को संभालता है।[6]
- विस्तारित प्राथमिकता पार्सर.
- मिश्रित रणनीति प्राथमिकता पार्सर, XPL के मूल संस्करण द्वारा उपयोग किया जाता है। त्रिगुणों को सम्मिलित करने के लिए, किसी भी पूर्वता पहचानकर्ता में निहित युगलों का विस्तार करता है। एसएलआर से कम शक्तिशाली. सामान्यतः XPL जैसी अपेक्षाकृत छोटी लैंग्वेज के लिए भी बहुत बड़ी तालिकाएँ होती हैं, क्योंकि बड़ी संख्या में त्रिगुणों की आवश्यकता होती है, जिन्हें पूर्ववर्ती विधियों द्वारा लगाई गई सीमाओं के बाहर व्याकरण को पहचानने की आवश्यकता होती है।[7]
प्राथमिकता पार्सर्स उन व्याकरणों में सीमित हैं जिन्हें वे संभाल सकते हैं। निर्णय लेते समय वे अधिकांश पार्स स्टैक को अनदेखा कर देते हैं। वे केवल सर्वोच्च सिंबल के नामों पर विचार करते हैं, न कि उस पूरे संदर्भ पर, जहां वे सिंबल अब व्याकरण में कहां दिखाई दे रहे हैं। प्राथमिकता के लिए आवश्यक है कि समान दिखने वाले सिंबल संयोजनों को पूरे व्याकरण में समान विधियों से पार्स और उपयोग किया जाना चाहिए, हालांकि वे संयोजन संदर्भ की परवाह किए बिना होते हैं।
एलआर पार्सर शिफ्ट-रिड्यूस पार्सिंग का एक अधिक लचीला रूप है, जो कई और व्याकरणों को संभालता है।[8]
एलआर पार्सर प्रोसेसिंग
एलआर पार्सर्स एक पुशडाउन ऑटोमेटन की तरह कार्य करते हैं, जो प्रत्येक शिफ्ट या कम कार्रवाई के लिए एक राज्य संक्रमण करते हैं। ये एक स्टैक का उपयोग करते हैं जहां वर्तमान स्थिति को शिफ्ट क्रियाओं द्वारा नीचे धकेल दिया जाता है। फिर इस स्टैक को कम क्रियाओं द्वारा पॉप (अप) किया जाता है। यह तंत्र एलआर पार्सर को सभी नियतात्मक संदर्भ-मुक्त व्याकरणों को संभालने की अनुमति देता है, जो पूर्ववर्ती व्याकरणों का एक सुपरसेट है। एलआर पार्सर पूरी तरह से कैनोनिकल एलआर पार्सर द्वारा कार्यान्वित किया जाता है। एलएएलआर पार्सर|लुक-अहेड एलआर और सरल एलआर पार्सर पार्सर इसके सरलीकृत वेरिएंट को प्रयुक्त करते हैं जिससे मेमोरी आवश्यकताओं में काफी कमी आई है।[9][10] हाल के शोध ने उन विधियों की पहचान की है जिनके द्वारा कैनोनिकल एलआर पार्सर्स को नथ के टेबल-बिल्डिंग एल्गोरिदम पर नाटकीय रूप से कम टेबल आवश्यकताओं के साथ प्रयुक्त किया जा सकता है।[11] चाहे एलआर, एलएएलआर या एसएलआर, मूल राज्य मशीन एक ही है; केवल तालिकाएँ भिन्न होती हैं, और ये तालिकाएँ लगभग हमेशा यंत्रवत् उत्पन्न होती हैं। इसके अतिरिक्त, इन तालिकाओं को सामान्यतः इस तरह कार्यान्वित किया जाता है कि REDUCE के परिणामस्वरूप एक बंद सबरूटीन पर कॉल आती है जो राज्य मशीन के लिए बाहरी है और जो एक कार्य करता है जो कि व्याकरण नियम के शब्दार्थ द्वारा निहित है जिसे REDUCE किया जा रहा है। इसलिए, पार्सर को एक अपरिवर्तनीय राज्य मशीन भाग और एक भिन्न शब्दार्थ भाग में विभाजित किया गया है। यह मूलभूत अंतर उच्च गुणवत्ता वाले पार्सर्स के विकास को प्रोत्साहित करता है जो असाधारण रूप से विश्वसनीय हैं।
एक विशिष्ट स्टैक स्थिति और लुकआहेड सिंबल को देखते हुए, सटीक रूप से चार संभावित क्रियाएं हैं, ERROR, शिफ्ट, कम करें और रोकें (इसके बाद कॉन्फ़िगरेशन के रूप में संदर्भित)। कॉन्फ़िगरेशन में एक बिंदु की उपस्थिति, •, वर्तमान लुकहेड स्थिति का प्रतिनिधित्व करती है, जिसमें लुकहेड सिंबल बिंदु के दाईं ओर दिखाया गया है (और जो हमेशा एक टर्मिनल सिंबल से मेल खाता है), और वर्तमान स्टैक स्थिति बिंदु के बाईं ओर दिखाई देती है (और जो सामान्यतः एक नॉनटर्मिनल सिंबल से मेल खाता है)।
उच्च प्रदर्शन सहित व्यावहारिक कारणों से, तालिकाओं को सामान्यतः दो-बिट सिंबल की कुछ बड़ी, सहायक सरणी द्वारा विस्तारित किया जाता है, जो स्पष्ट रूप से बाइट-उन्मुख मशीनों पर कुशल पहुंच के लिए चार दो-बिट सिंबल, एक बाइट में संपीड़ित होती है, जिसे प्रायः एन्कोड किया जाता है :
- 00b represents ERROR
- 01b represents SHIFT
- 10b represents REDUCE
- 11b represents STOP
(SHIFT का विशेष स्थिति बनना बंद करें)। संपूर्ण सरणी में सामान्यतः अधिकतर ERROR कॉन्फ़िगरेशन, SHIFT और REDUCE कॉन्फ़िगरेशन की व्याकरण-परिभाषित संख्या और एक STOP कॉन्फ़िगरेशन सम्मिलित होता है।
प्रोग्रामिंग प्रणालियों में जो चतुर्धातुक अंक प्रणाली (आधार 4, प्रति चतुर्धातुक अंक दो बिट) में मानों के विनिर्देशन का समर्थन करते हैं, जैसे कि XPL, इन्हें इस प्रकार कोडित किया जाता है, उदाहरण के लिए:
- "(2)…0…" represents ERROR
- "(2)…1…" represents SHIFT
- "(2)…2…" represents REDUCE
- "(2)…3…" represents STOP
SHIFT और REDUCE तालिकाओं को सरणी से अलग से प्रयुक्त किया जाता है। सहायक सरणी की केवल वर्तमान स्थिति और लुकआहेड सिंबल के लिए "जांच" की जाती है। (सहायक) सरणी "पूर्ण" है, जबकि (शिफ्ट और कम) तालिकाएं वास्तव में बहुत "विरल" हो सकती हैं, और उन SHIFT और REDUCE तालिकाओं के इष्टतम "अपघटन" के माध्यम से महत्वपूर्ण दक्षताएं प्राप्त की जा सकती हैं (ERROR और STOP को तालिकाओं की आवश्यकता नहीं है) ).
SHIFT-REDUCE पार्सर की मूल परिभाषा से SHIFT और REDUCE कॉन्फ़िगरेशन स्पष्ट हैं।
STOP, फिर, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करता है जहां स्टैक के शीर्ष पर स्थिति और लुकहेड टर्मिनल सिंबल विषय व्याकरण के भीतर है, और कार्यक्रम के अंत का प्रतिनिधित्व करता है:
- ⊥ <program> • ⊥
वैचारिक रूप से पहुँचने के लिए अंतिम '⊥' से आगे SHIFT करना असंभव है
- ⊥ <program> ⊥ •
ERROR, फिर, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करती है जहां स्टैक के शीर्ष पर स्थिति और लुकहेड टर्मिनल सिंबल विषय व्याकरण के साथ नहीं है। यह ERROR पुनर्प्राप्ति प्रक्रिया को प्रयुक्त करने का अवसर प्रस्तुत करता है, संभवतः, इसके सबसे सरल रूप में, लुकहेड टर्मिनल सिंबल को त्यागने और अगले टर्मिनल सिंबल को पढ़ने के लिए, लेकिन कई अन्य प्रोग्राम किए गए कार्य संभव हैं, जिसमें स्टैक की सॉर्टिंग करना, या लुकहेड टर्मिनल सिंबल को त्यागना और स्टैक की सॉर्टिंग करना सम्मिलित है और पैथोलॉजिकल स्थिति में, सामान्यतः इसे प्राप्त करना संभव है
- ⊥ <program> • ⊥
जहां <प्रोग्राम> में केवल "नल स्टेटमेंट" सम्मिलित है)।
ज्यादातर मामलों में, स्टैक को जानबूझकर प्री-लोड किया जाता है, यानी आरंभीकृत किया जाता है
- ⊥ • <program> ⊥
जिससे प्रारंभिक '⊥' को पहले ही पहचाना जा चुका माना जाता है। यह, तब, प्रोग्राम के आरम्भ का प्रतिनिधित्व करता है, और, इस प्रकार, एक अलग START कॉन्फ़िगरेशन होने से बचता है, जो कि वैचारिक रूप से है
- • ⊥ <program> ⊥
'⊥' यांत्रिक रूप से व्याकरण में जोड़ा गया एक विशेष छद्म-टर्मिनल सिंबल है, जैसे <प्रोग्राम> यांत्रिक रूप से एक विशेष छद्म-नॉनटर्मिनल सिंबल हैव्याकरण में जोड़ा गया (यदि प्रोग्रामर ने व्याकरण में <प्रोग्राम> को स्पष्ट रूप से सम्मिलित नहीं किया है, तो प्रोग्रामर की ओर से <प्रोग्राम> स्वचालित रूप से व्याकरण में जोड़ा जाएगा)।
स्पष्ट रूप से, ऐसे पार्सर में सटीक रूप से एक (अंतर्निहित) START कॉन्फ़िगरेशन और एक (स्पष्ट) STOP कॉन्फ़िगरेशन होता है, लेकिन इसमें सैकड़ों SHIFT और REDUCE कॉन्फ़िगरेशन और शायद हजारों ERROR कॉन्फ़िगरेशन हो सकते हैं और सामान्यतः होते हैं।
संदर्भ
- ↑ 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.
