शिफ्ट-रिड्यूस पार्सर: Difference between revisions

Latest revision as of 11:23, 16 August 2023

शिफ्ट-रिड्यूस पार्सर कंप्यूटर लैंग्वेज और व्याकरण द्वारा औपचारिक रूप से परिभाषित अन्य नोटेशन के लिए कुशल, टेबल-संचालित बॉटम-अप पार्सिंग विधियों का एक वर्ग है। प्रोग्रामिंग लैंग्वेज, एलआर पार्सिंग और इसकी विविधताओं को पार्स करने के लिए सबसे अधिक उपयोग की जाने वाली पार्सिंग विधियाँ शिफ्ट-कम करने की विधियाँ हैं।^[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.

[1] Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.

[2] "संग्रहीत प्रति" (PDF). dragonbook.stanford.edu. Archived from the original (PDF) on 5 March 2016. Retrieved 17 January 2022.

[3] Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.

[4] Crafting a Compiler, by Fischer, Ron , and Richard , Addison Wesley 2009.

[5] PL360 - A Programming Language for the 360 Computers, by Niklaus Wirth, J. ACM 15:1 1968.

[6] The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing, by Alfred Aho and Jeffrey Ullman, Prentice Hall 1972.

[7] A Compiler Generator, by William M. McKeeman, J Horning, and D Wortman, Prentice Hall 1970; ISBN 978-0131550773.

[8] 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.

[9] Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.

[10] Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.

[11] X. Chen, Measuring and extending LR(1) parsing, University of Hawaii PhD dissertation, 2009.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 {{Short description|Class of bottom-up parsing methods}}
-शिफ्ट-रिड्यूस पार्सर कंप्यूटर भाषाओं और [[औपचारिक व्याकरण]] द्वारा औपचारिक रूप से परिभाषित अन्य नोटेशन के लिए कुशल, टेबल-संचालित [[नीचे से ऊपर का विश्लेषण]] विधियों का एक वर्ग है। [[प्रोग्रामिंग भाषा]]ओं, [[एलआर पार्सर]] और इसकी विविधताओं को पार्स करने के लिए सबसे अधिक उपयोग की जाने वाली पार्सिंग विधियां शिफ्ट-कम करने की विधियां हैं।<ref>
+'''शिफ्ट-रिड्यूस पार्सर''' कंप्यूटर लैंग्वेज और व्याकरण द्वारा औपचारिक रूप से परिभाषित अन्य नोटेशन के लिए कुशल, टेबल-संचालित बॉटम-अप पार्सिंग विधियों का एक वर्ग है। प्रोग्रामिंग लैंग्वेज, एलआर पार्सिंग और इसकी विविधताओं को पार्स करने के लिए सबसे अधिक उपयोग की जाने वाली पार्सिंग विधियाँ शिफ्ट-कम करने की विधियाँ हैं।<ref>
-Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.</ref> एलआर पार्सिंग के आविष्कार से पहले उपयोग किए जाने वाले सरल पूर्ववर्ती पार्सर भी शिफ्ट-कम करने के तरीके हैं। सभी शिफ्ट-रिड्यूस पार्सर्स का बाहरी प्रभाव समान होता है, वृद्धिशील क्रम में जिसमें वे एक पार्स ट्री बनाते हैं या विशिष्ट आउटपुट क्रियाओं को कॉल करते हैं।
+Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.</ref> एलआर पार्सिंग के आविष्कार से पहले उपयोग किए जाने वाले पूर्ववर्ती पार्सर भी शिफ्ट-कम करने के विधियां हैं। सभी शिफ्ट-रिड्यूस पार्सर्स के समान बाहरी प्रभाव होते हैं, वृद्धिशील क्रम में जिसमें वे पार्स ट्री बनाते हैं या विशिष्ट आउटपुट क्रियाओं को कॉल करते हैं।
 == सिंहावलोकन ==
-एक शिफ्ट-रिड्यूस [[पार्सर]] इनपुट टेक्स्ट को स्कैन करता है और बिना बैकअप के टेक्स्ट के ऊपर से एक फॉरवर्ड पास में पार्स करता है। पार्सर [[पार्स वृक्ष]] को क्रमिक रूप से, नीचे से ऊपर और बाएँ से दाएँ बनाता है, बिना अनुमान लगाए या पीछे हटे। इस पास के प्रत्येक बिंदु पर, पार्सर ने इनपुट टेक्स्ट के उपवृक्षों या वाक्यांशों की एक सूची जमा कर ली है जिन्हें पहले ही पार्स किया जा चुका है। वे उपवृक्ष अभी तक एक साथ नहीं जुड़े हैं क्योंकि पार्सर अभी तक सिंटैक्स पैटर्न के दाहिने छोर तक नहीं पहुंचा है जो उन्हें संयोजित करेगा।
+शिफ्ट-रिड्यूस पार्सर इनपुट टेक्स्ट को स्कैन और पार्स करता है, बिना बैकअप के, टेक्स्ट के ऊपर से एक फॉरवर्ड पास में। पार्सर पार्स ट्री को क्रमिक रूप से, नीचे से ऊपर और बाएँ से दाएँ बनाता है, बिना अनुमान लगाए या पीछे हटे। इस पास के प्रत्येक बिंदु पर, पार्सर ने इनपुट टेक्स्ट के सबट्री या वाक्यांशों की एक सूची जमा की है जिन्हें पहले ही पार्स किया जा चुका है। वे सबट्री अभी तक एक साथ नहीं जुड़े हैं क्योंकि पार्सर अभी तक सिंटैक्स पैटर्न के दाहिने छोर तक नहीं पहुंचा है जो उन्हें संयोजित करेगा।
-[[File:Shift-Reduce_Parse_Steps_Numbered.svg|thumb|x250px|right|शिफ्ट-रिड्यूस पार्स ट्री को क्रमांकित चरणों में नीचे से ऊपर बनाया गया।]]स्ट्रिंग पर विचार करें <code>A = B + C * 2</code>.
+स्ट्रिंग पर विचार करें <code>A = B + C * 2</code>.
-उदाहरण में चरण 7 पर, केवल ए = बी + को पार्स किया गया है। पार्स वृक्ष का केवल छायांकित निचला-बाएँ कोना मौजूद है। 8 और उससे ऊपर क्रमांकित कोई भी पार्स ट्री नोड अभी तक मौजूद नहीं है। नोड 1, 2, 6, और 7 सभी आइटम 1..7 को कवर करने वाले पृथक उपवृक्षों की जड़ें हैं। नोड 1 वेरिएबल ए है, नोड 2 सीमांकक = है, नोड 6 सारांश बी है, और नोड 7 ऑपरेटर + है। इन चार रूट नोड्स को अस्थायी रूप से पार्स स्टैक में रखा जाता है। इनपुट स्ट्रीम का शेष अनपार्स्ड भाग C * 2 है।
+उदाहरण के चरण 7 में, केवल "A = B +" को पार्स किया गया है। पार्स ट्री का केवल छायांकित निचला-बाएँ कोना ही उपस्थित है। 8 और उससे अधिक संख्या वाला कोई भी पार्स ट्री नोड अभी तक उपस्थित नहीं है। नोड्स 1, 2, 6, और 7 सभी आइटम 1..7 को कवर करने वाले अलग-अलग सबट्री का रुट  हैं। नोड 1 वेरिएबल A है, नोड 2 डिलीमीटर = है, नोड 6 सारांश B है, और नोड 7 ऑपरेटर + है। ये चार रूट नोड्स अस्थायी रूप से एक पार्स स्टैक में रखे जाते हैं। इनपुट स्ट्रीम का शेष अनपार्स किया गया भाग "C * 2" है।
-एक शिफ्ट-रिड्यूस पार्सर शिफ्ट स्टेप्स और रिड्यूस स्टेप्स का कुछ संयोजन करके काम करता है, इसलिए इसे यह नाम दिया गया है।
+शिफ्ट-रिड्यूस पार्सर शिफ्ट स्टेप्स और रिड्यूस स्टेप्स का कुछ संयोजन करके काम करता है, इसलिए इसे नाम दिया गया है।
-* एक शिफ़्ट चरण इनपुट स्ट्रीम में एक प्रतीक द्वारा आगे बढ़ता है। वह स्थानांतरित प्रतीक एक नया एकल-नोड पार्स ट्री बन जाता है।
-* रिड्यूस चरण कुछ हालिया पार्स पेड़ों पर एक पूर्ण व्याकरण नियम लागू करता है, उन्हें एक नए रूट प्रतीक के साथ एक पेड़ के रूप में जोड़ता है।
-पार्सर इन चरणों के साथ तब तक जारी रहता है जब तक कि सभी इनपुट का उपभोग नहीं हो जाता और सभी पार्स पेड़ संपूर्ण कानूनी इनपुट का प्रतिनिधित्व करने वाले एक पेड़ में कम नहीं हो जाते।
-=== वृक्ष निर्माण चरण ===
+* '''शिफ़्ट''' चरण इनपुट स्ट्रीम में सिंबल (प्रतीक) द्वारा आगे बढ़ता है। वह स्थानांतरित सिंबल एक नया एकल-नोड पार्स ट्री बन जाता है।
+* '''रिड्यूस''' कदम हाल के कुछ पार्स ट्री पर एक पूर्ण व्याकरण नियम प्रयुक्त करता है, उन्हें एक नए रूट सिंबल के साथ एक ट्री के रूप में जोड़ता है। पार्सर इन चरणों के साथ तब तक जारी रहता है जब तक कि सभी इनपुट का उपभोग नहीं हो जाता है और सभी पार्स ट्री पूरे कानूनी इनपुट का प्रतिनिधित्व करने वाले एक ट्री में कम हो जाते हैं।
-प्रत्येक पार्स चरण पर, संपूर्ण इनपुट टेक्स्ट को पार्स स्टैक, वर्तमान लुकहेड प्रतीक और शेष अनस्कैन किए गए टेक्स्ट में विभाजित किया जाता है। पार्सर की अगली कार्रवाई सबसे दाहिने स्टैक प्रतीक(चिह्नों) और आगे की ओर देखने वाले प्रतीक द्वारा निर्धारित की जाती है। कार्रवाई को एक तालिका से पढ़ा जाता है जिसमें स्टैक और लुकहेड प्रतीकों के सभी वाक्यात्मक रूप से मान्य संयोजन होते हैं।
+=== ट्री निर्माण चरण ===
+प्रत्येक पार्स चरण में, संपूर्ण इनपुट टेक्स्ट को पार्स स्टैक, वर्तमान लुकहेड सिंबल और शेष अनस्कैन टेक्स्ट में विभाजित किया जाता है। पार्सर की अगली क्रिया सबसे दाएँ स्टैक सिंबल (चिह्नों) और आगे की ओर देखने वाले सिंबल द्वारा निर्धारित होती है। कार्रवाई को एक तालिका से पढ़ा जाता है जिसमें स्टैक और लुकहेड सिंबल के सभी वाक्यविन्यास रूप से मान्य संयोजन होते हैं।
 {| class="wikitable"
 |-
-! Step !! Parse Stack !! Look<br />Ahead !! Unscanned !! Parser Action
+! चरण !! पार्स स्टैक !! आगे देखें !! अनस्कैन्ड !! पार्सर एक्शन
 |-
 | 0 || ''empty'' || ''id'' || align="right" | = B + C*2 || Shift
@@ Line 58: / Line 56: @@
 | 16 || Assign || ''eof'' ||  || Done
 |}
-देखना <ref>{{cite web |url=http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/08-Bottom-Up-Parsing.pdf
+एक सरल उदाहरण के लिए देखें<ref>{{cite web |url=http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/08-Bottom-Up-Parsing.pdf
   |title=संग्रहीत प्रति|website=dragonbook.stanford.edu |access-date=17 January 2022 |archive-url=https://web.archive.org/web/20160305041504/http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/08-Bottom-Up-Parsing.pdf
-  |archive-date=5 March 2016 |url-status=dead}}</ref> एक सरल उदाहरण के लिए.
+  |archive-date=5 March 2016 |url-status=dead}}</ref>।
 == व्याकरण ==
-व्याकरण इनपुट भाषा के लिए पैटर्न या वाक्यविन्यास नियमों का सेट है। इसमें सभी भाषा नियमों को शामिल नहीं किया गया है, जैसे कि संख्याओं का आकार, या पूरे कार्यक्रम के संदर्भ में नामों और उनकी परिभाषाओं का लगातार उपयोग। शिफ्ट-कम पार्सर्स एक [[संदर्भ-मुक्त व्याकरण]] का उपयोग करते हैं जो केवल प्रतीकों के स्थानीय पैटर्न से संबंधित है।
+व्याकरण इनपुट लैंग्वेज के लिए पैटर्न या वाक्य रचना नियमों का समूह है। इसमें सभी लैंग्वेज नियम सम्मिलित नहीं हैं, जैसे संख्याओं का आकार, या पूरे कार्यक्रम के संदर्भ में नामों और उनकी परिभाषाओं का लगातार उपयोग। शिफ्ट-कम करने वाले पार्सर्स [[संदर्भ-मुक्त व्याकरण]] का उपयोग करते हैं जो केवल सिंबल के स्थानीय पैटर्न से संबंधित है।
-मिलान करने में सक्षम जावा या सी भाषा के एक छोटे उपसमूह के रूप में व्याकरण का एक उदाहरण <code>A = B + C*2</code> हो सकता है:
+जावा या C लैंग्वेज के एक छोटे उपसमुच्चय के रूप में व्याकरण का एक उदाहरण जो <code>A = B + C*2</code> से मेल खाने में सक्षम है:
-::असाइन करें ← आईडी = रकम
+:::: Assign ← ''id'' = Sums
-::रकम ← रकम + उत्पाद
+:::: Sums ← Sums + Products
-::रकम ← उत्पाद
+:::: Sums ← Products
-::उत्पाद ← उत्पाद * मूल्य
+:::: Products ← Products * Value
-::उत्पाद ← मूल्य
+:::: Products ← Value
-::मूल्य ← int
+:::: Value ← ''int''
-::मूल्य ← आईडी
+:::: Value ← ''id''
-व्याकरण के [[टर्मिनल प्रतीक]] बहु-वर्ण प्रतीक या 'टोकन' हैं जो एक [[शाब्दिक विश्लेषण]] द्वारा इनपुट स्ट्रीम में पाए जाते हैं। यहां इनमें किसी भी पूर्णांक स्थिरांक के लिए '=' '+' '*' और int, और किसी भी पहचानकर्ता नाम के लिए id शामिल हैं। व्याकरण को इसकी परवाह नहीं है कि int मान या id वर्तनी क्या हैं, न ही यह रिक्त स्थान या पंक्ति विराम की परवाह करता है। व्याकरण इन टर्मिनल प्रतीकों का उपयोग करता है लेकिन उन्हें परिभाषित नहीं करता है। वे हमेशा पार्स पेड़ के निचले झाड़ीदार सिरे पर होते हैं।
+व्याकरण के [[टर्मिनल प्रतीक|टर्मिनल सिंबल]] बहु-वर्ण सिंबल या 'टोकन' हैं जो एक लेक्सिकल स्कैनर द्वारा इनपुट स्ट्रीम में पाए जाते हैं। यहां इनमें किसी भी पूर्णांक स्थिरांक के लिए '''=''' '''+''' '''*''' और ''int'', और किसी भी पहचानकर्ता नाम के लिए id सम्मिलित हैं। व्याकरण को इसकी परवाह नहीं है कि ''int'' मान या ''id'' वर्तनी क्या हैं, न ही यह रिक्त स्थान या पंक्ति विराम की परवाह करता है। व्याकरण इन टर्मिनल सिंबल का उपयोग करता है लेकिन उन्हें परिभाषित नहीं करता है। वे हमेशा पार्स ट्री के निचले बशी सिरे पर होते हैं।
-सम्स जैसे बड़े अक्षर वाले शब्द [[नॉनटर्मिनल प्रतीक]] हैं। ये भाषा में अवधारणाओं या पैटर्न के नाम हैं। वे व्याकरण में परिभाषित हैं और इनपुट स्ट्रीम में स्वयं कभी नहीं आते हैं। वे सदैव पार्स वृक्ष के नीचे से ऊपर होते हैं। वे केवल पार्सर द्वारा कुछ व्याकरण नियम लागू करने के परिणामस्वरूप होते हैं। कुछ नॉनटर्मिनलों को दो या दो से अधिक नियमों से परिभाषित किया गया है; ये वैकल्पिक पैटर्न हैं. नियम स्वयं को वापस संदर्भित कर सकते हैं। यह व्याकरण दोहराए गए गणित ऑपरेटरों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करता है। संपूर्ण भाषाओं के व्याकरण सूचियों, कोष्ठक में रखे गए भावों और नेस्टेड कथनों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करते हैं।
+सम्स जैसे बड़े अक्षर वाले शब्द [[नॉनटर्मिनल प्रतीक|नॉनटर्मिनल सिंबल]] हैं। ये लैंग्वेज में अवधारणाओं या पैटर्न के नाम हैं। वे व्याकरण में परिभाषित हैं और इनपुट स्ट्रीम में स्वयं कभी नहीं आते हैं। वे सदैव पार्स ट्री के नीचे से ऊपर होते हैं। वे केवल पार्सर द्वारा कुछ व्याकरण नियम प्रयुक्त करने के परिणामस्वरूप होते हैं। कुछ नॉनटर्मिनलों को दो या दो से अधिक नियमों से परिभाषित किया गया है; ये वैकल्पिक पैटर्न हैं. नियम स्वयं को वापस संदर्भित कर सकते हैं। यह व्याकरण दोहराए गए गणित ऑपरेटरों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करता है। संपूर्ण लैंग्वेज के व्याकरण सूचियों, कोष्ठक में रखे गए भावों और नेस्टेड कथनों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करते हैं।
-किसी भी कंप्यूटर भाषा को कई अलग-अलग व्याकरणों द्वारा वर्णित किया जा सकता है। शिफ्ट-रिड्यूस पार्सर के लिए व्याकरण स्वयं [[अस्पष्ट व्याकरण]] होना चाहिए, या टाई-ब्रेकिंग प्राथमिकता नियमों द्वारा संवर्धित किया जाना चाहिए। इसका मतलब यह है कि भाषा के किसी दिए गए कानूनी उदाहरण में व्याकरण को लागू करने का केवल एक ही सही तरीका है, जिसके परिणामस्वरूप एक अद्वितीय पार्स ट्री और उस उदाहरण के लिए बदलाव/घटाने की क्रियाओं का एक अद्वितीय अनुक्रम होता है।
+किसी भी कंप्यूटर लैंग्वेज को कई अलग-अलग व्याकरणों द्वारा वर्णित किया जा सकता है। शिफ्ट-रिड्यूस पार्सर के लिए व्याकरण स्वयं स्पष्ट होना चाहिए, या टाई-ब्रेकिंग प्राथमिकता नियमों द्वारा संवर्धित किया जाना चाहिए। इसका मतलब यह है कि लैंग्वेज के किसी दिए गए कानूनी उदाहरण में व्याकरण को प्रयुक्त करने का केवल एक ही सही विधि है, जिसके परिणामस्वरूप एक अद्वितीय पार्स ट्री और उस उदाहरण के लिए शिफ्ट/घटाने की क्रियाओं का एक अद्वितीय अनुक्रम होता है।
-एक टेबल-संचालित पार्सर के पास व्याकरण के बारे में अपना सारा ज्ञान अपरिवर्तनीय डेटा में एन्कोड किया गया होता है जिसे पार्सर टेबल कहा जाता है। पार्सर का प्रोग्राम कोड एक सरल सामान्य लूप है जो कई व्याकरणों और भाषाओं पर अपरिवर्तित लागू होता है। प्राथमिकता पद्धतियों के लिए तालिकाओं को हाथ से तैयार किया जा सकता है। एलआर विधियों के लिए, जटिल तालिकाओं को [[जीएनयू बाइसन]] जैसे कुछ [[पार्सर जनरेटर]] टूल द्वारा व्याकरण से यांत्रिक रूप से प्राप्त किया जाता है।<ref>
+एक टेबल-संचालित पार्सर के पास व्याकरण के बारे में अपना सारा ज्ञान अपरिवर्तनीय डेटा में एन्कोड किया गया होता है जिसे पार्सर टेबल कहा जाता है। पार्सर का प्रोग्राम कोड एक सरल सामान्य लूप है जो कई व्याकरणों और लैंग्वेज पर अपरिवर्तित प्रयुक्त होता है। प्राथमिकता पद्धतियों के लिए तालिकाओं को हाथ से तैयार किया जा सकता है। एलआर विधियों के लिए, जटिल तालिकाओं को बाइसन जैसे कुछ पार्सर जनरेटर टूल द्वारा व्याकरण से यांत्रिक रूप से प्राप्त किया जाता है।<ref>
-Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.</ref> पार्सर तालिकाएँ आमतौर पर व्याकरण से बहुत बड़ी होती हैं। अन्य पार्सर्स में जो टेबल-संचालित नहीं हैं, जैसे कि [[पुनरावर्ती वंश]], प्रत्येक भाषा निर्माण को एक अलग सबरूटीन द्वारा पार्स किया जाता है, जो उस एक निर्माण के सिंटैक्स के लिए विशेष होता है।
+Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.</ref> पार्सर तालिकाएँ सामान्यतः व्याकरण से बहुत बड़ी होती हैं। अन्य पार्सर्स में जो टेबल-संचालित नहीं हैं, जैसे कि पुनरावर्ती वंश, प्रत्येक लैंग्वेज निर्माण को एक अलग सबरूटीन द्वारा पार्स किया जाता है, जो उस एक निर्माण के सिंटैक्स के लिए विशेष होता है।
-==पार्सर क्रियाएँ==
+==पार्सर एक्शन्स==
-शिफ्ट-रिड्यूस पार्सर कुशल है क्योंकि इसमें कोई बैकअप शामिल नहीं है। इसका कुल निष्पादन समय इनपुट की लंबाई और पूर्ण पार्स ट्री के आकार के साथ रैखिक रूप से बढ़ता है। अन्य पार्सर विधियाँ जो खराब अनुमान लगाने पर पीछे हटने में तेजी से समय ले सकती हैं।{{citation needed|date=July 2012}}
+शिफ्ट-रिड्यूस पार्सर कुशल है क्योंकि इसमें कोई बैकअप नहीं होता है। इसका कुल निष्पादन समय इनपुट की लंबाई और पूर्ण पार्स ट्री के आकार के साथ रैखिक रूप से बढ़ता है। अन्य पार्सर विधियाँ जो गलत अनुमान लगाने पर पीछे की ओर जाती हैं, उन्हें बहुत अधिक समय लग सकता है।
-अनुमान लगाने से बचने के लिए, शिफ्ट-रिड्यूस पार्सर अक्सर पहले से स्कैन किए गए प्रतीकों के साथ क्या करना है, यह तय करने से पहले अगले स्कैन किए गए प्रतीक पर आगे (बाएं से दाएं पाठ में दाईं ओर) देखता है। लेक्सिकल स्कैनर बाकी पार्सर से एक प्रतीक आगे काम करता है। प्रत्येक पार्सिंग निर्णय के लिए लुकहेड प्रतीक को 'दाहिने हाथ का संदर्भ' भी कहा जाता है। (शायद ही, दो या दो से अधिक लुकहेड प्रतीकों का उपयोग किया जा सकता है, हालांकि अधिकांश व्यावहारिक व्याकरणों को एक लुकहेड प्रतीक का उपयोग करने के लिए डिज़ाइन किया जा सकता है।)
+अनुमान लगाने से बचने के लिए, शिफ्ट-रिड्यूस पार्सर प्रायः पहले से स्कैन किए गए सिंबल के साथ क्या करना है, यह निर्णय लेने से पहले अगले स्कैन किए गए सिंबल पर आगे (बाएं से दाएं पाठ में दाईं ओर) देखता है। लेक्सिकल स्कैनर बाकी पार्सर से एक सिंबल आगे काम करता है। प्रत्येक विश्लेषण निर्णय के लिए लुकहेड सिंबल को 'दाहिने हाथ का संदर्भ' भी कहा जाता है। (शायद ही, दो या अधिक लुकहेड सिंबल का उपयोग किया जा सकता है, हालांकि अधिकांश व्यावहारिक व्याकरणों को एक लुकहेड सिंबल का उपयोग करने के लिए डिज़ाइन किया जा सकता है।)
-एक शिफ्ट-रिड्यूस पार्सर तब तक इंतजार करता है जब तक कि वह संयुक्त निर्माण के लिए प्रतिबद्ध होने से पहले कुछ निर्माण के सभी हिस्सों को स्कैन और पार्स नहीं कर लेता। फिर पार्सर किसी और प्रतीक्षा के बजाय संयोजन पर तुरंत कार्य करता है। ऊपर दिए गए पार्स ट्री उदाहरण में, जैसे ही + को लुकहेड में देखा जाता है, वाक्यांश बी को मूल्य में और फिर चरण 3-6 में उत्पाद और रकम में बदल दिया जाता है, पार्स ट्री के उन हिस्सों को व्यवस्थित करने के लिए अब और इंतजार करने के बजाय। बी को कैसे संभालना है इसका निर्णय केवल उस पर आधारित होता है जो पार्सर और स्कैनर ने पहले ही देखा है, उन चीजों पर विचार किए बिना जो दाईं ओर बहुत बाद में दिखाई देती हैं।
+एक शिफ्ट-रिड्यूस पार्सर तब तक प्रतीक्षा करता है जब तक कि उसने संयुक्त निर्माण के लिए प्रतिबद्ध होने से पहले कुछ निर्माण के सभी हिस्सों को स्कैन और पार्स नहीं कर लिया हो। इसके बाद पार्सर आगे इंतजार करने के बजाय तुरंत संयोजन पर कार्य करता है। ऊपर दिए गए पार्स ट्री उदाहरण में, जैसे ही + को लुकहेड में देखा जाता है, वाक्यांश बी को मूल्य में और फिर चरण 3-6 में उत्पाद और रकम में बदल दिया जाता है, पार्स ट्री के उन हिस्सों को व्यवस्थित करने के लिए अब और इंतजार करने के बजाय। बी को कैसे संभालना है, इस पर निर्णय केवल उस पर आधारित होते हैं जो पार्सर और स्कैनर ने पहले ही देखा है, उन चीजों पर विचार किए बिना जो बहुत बाद में दाईं ओर दिखाई देती हैं।
-कटौती सबसे हाल ही में पार्स की गई चीजों को पुनर्गठित करती है, यानी, लुकहेड प्रतीक के तुरंत बाईं ओर। तो पहले से ही पार्स की गई चीजों की सूची एक [[स्टैक (सार डेटा प्रकार)]] की तरह काम करती है। यह पार्स स्टैक दाईं ओर बढ़ता है। स्टैक का आधार या तल बायीं ओर है और सबसे बायीं ओर, सबसे पुराना पार्स टुकड़ा रखता है। प्रत्येक कटौती चरण केवल सबसे दाहिने, नवीनतम पार्स अंशों पर कार्य करता है। (यह संचयी पार्स स्टैक [[ऊपर से नीचे पार्सर]]्स द्वारा उपयोग किए जाने वाले पूर्वानुमानित, बाईं ओर बढ़ने वाले पार्स स्टैक से बहुत अलग है।)
+कट हाल ही में पार्स किए गए को पुनर्गठित करता है, यानी, लुकहेड सिंबल के ठीक बाईं ओर। इसलिए पहले से पार्स की गई चीज़ों की सूची एक स्टैक की तरह काम करती है। यह पार्स स्टैक दाईं ओर बढ़ता है। स्टैक का आधार या निचला भाग बायीं ओर है और सबसे बायीं ओर, सबसे पुराना पार्स टुकड़ा रखता है। प्रत्येक कमी चरण केवल सबसे दाएँ, नवीनतम पार्स अंशों पर कार्य करता है। (यह संचयी पार्स स्टैक ऊपर से नीचे पार्सर्स द्वारा उपयोग किए जाने वाले पूर्वानुमानित, बाईं ओर बढ़ने वाले पार्स स्टैक से बहुत अलग है।)
 जब कोई व्याकरण नियम जैसे
-:: उत्पाद ← उत्पाद * मूल्य
-लागू किया जाता है, स्टैक टॉप पार्स ट्री रखता है ... उत्पाद * मूल्य। नियम के दाहिनी ओर के इस पाए गए उदाहरण को हैंडल कहा जाता है। कम करने का चरण हैंडल उत्पाद * मान को बायीं ओर के गैर टर्मिनल से बदल देता है, इस मामले में एक बड़ा उत्पाद। यदि पार्सर पूर्ण पार्स ट्री बनाता है, तो आंतरिक उत्पादों के लिए तीन पेड़, *, और मूल्य को बड़े उत्पादों के लिए एक नए पेड़ की जड़ से जोड़ दिया जाता है। अन्यथा, आंतरिक उत्पादों और मूल्य से सिमेंटिक्स#प्रोग्रामिंग भाषाओं का विवरण कुछ बाद के कंपाइलर पास में आउटपुट होता है, या नए उत्पाद प्रतीक में संयुक्त और सहेजा जाता है।<ref>Crafting a Compiler, by Fischer, Ron , and Richard , Addison Wesley 2009.</ref>
+Products ← Products * Value
-पार्सर तब तक पार्स स्टैक के शीर्ष पर कटौती लागू करता रहता है जब तक वह वहां व्याकरण नियमों के नए पूर्ण किए गए उदाहरण ढूंढता रहता है। जब कोई और नियम लागू नहीं किया जा सकता है, तो पार्सर लुकहेड प्रतीक को पार्स स्टैक पर स्थानांतरित कर देता है, एक नया लुकहेड प्रतीक स्कैन करता है, और फिर से प्रयास करता है।
+प्रयुक्त किया जाता है, स्टैक शीर्ष पर पार्स ट्री "... उत्पाद * मूल्य" होता है। नियम के दायीं ओर का यह पाया गया उदाहरण हैंडल कहलाता है। कम करने का चरण बायीं ओर के गैर टर्मिनल द्वारा "उत्पाद * मूल्य" हैंडल को प्रतिस्थापित करता है, इस स्थिति में एक बड़ा उत्पाद। यदि पार्सर पूर्ण पार्स ट्री बनाता है, तो आंतरिक उत्पादों के लिए तीन ट्री, *, और मूल्य को बड़े उत्पादों के लिए एक नए ट्री की रुट द्वारा संयोजित किया जाता है। अन्यथा, आंतरिक उत्पादों और मूल्य से अर्थ संबंधी विवरण कुछ बाद के कंपाइलर पास में आउटपुट होते हैं, या नए उत्पाद सिंबल में संयुक्त और सेव किये जाते हैं।<ref>Crafting a Compiler, by Fischer, Ron , and Richard , Addison Wesley 2009.</ref>
+पार्सर तब तक पार्स स्टैक के शीर्ष पर कटौती प्रयुक्त करता रहता है जब तक वह वहां व्याकरण नियमों के नए पूर्ण किए गए उदाहरण ढूंढता रहता है। जब कोई और नियम प्रयुक्त नहीं किया जा सकता है, तो पार्सर लुकहेड सिंबल को पार्स स्टैक पर स्थानांतरित कर देता है, एक नया लुकहेड सिंबल स्कैन करता है, और फिर से प्रयास करता है।
 ==शिफ्ट-रिड्यूस पार्सर्स के प्रकार==
-पार्सर तालिकाएँ दिखाती हैं कि शीर्षस्थ पार्स स्टैक प्रतीकों और लुकहेड प्रतीक के प्रत्येक कानूनी संयोजन के लिए आगे क्या करना है। वह अगला कार्य अद्वितीय होना चाहिए; या तो बदलाव करें, या कम करें, लेकिन दोनों नहीं। (इसका तात्पर्य स्पष्ट होने से परे, व्याकरण पर कुछ और सीमाओं से है।) विभिन्न प्रकार के शिफ्ट-रिड्यूस पार्सर्स के बीच तालिका का विवरण बहुत भिन्न होता है।
+पार्सर तालिकाएँ दिखाती हैं कि शीर्षस्थ पार्स स्टैक सिंबल और लुकहेड सिंबल के प्रत्येक कानूनी संयोजन के लिए आगे क्या करना है। वह अगला कार्य अद्वितीय होना चाहिए; या तो बदलाव करें, या कम करें, लेकिन दोनों नहीं। (इसका तात्पर्य स्पष्ट होने से परे, व्याकरण पर कुछ और सीमाओं से है।) विभिन्न प्रकार के शिफ्ट-रिड्यूस पार्सर्स के बीच तालिका का विवरण बहुत भिन्न होता है।
-पूर्ववर्ती पार्सर्स में, शीर्ष स्टैक प्रतीकों की पूर्ववर्ती स्तर या व्याकरण की जकड़न की तुलना लुकहेड प्रतीक से करके हैंडल का दाहिना सिरा पाया जाता है। उपरोक्त उदाहरण में, ''int'' और ''id'' कथन सीमांकक की तुलना में आंतरिक व्याकरण स्तर से संबंधित हैं। इसलिए ''int'' और ''id'' दोनों को इससे अधिक प्राथमिकता वाला माना जाता है; और जब भी ; का अनुसरण किया जाए तो इसे किसी अन्य चीज़ में घटा दिया जाना चाहिए। पूर्ववर्ती पार्सर की विभिन्न किस्में हैं, जिनमें से प्रत्येक में हैंडल के बाएं छोर को ढूंढने और लागू करने के लिए सही नियम चुनने के विभिन्न तरीके हैं:
+पूर्ववर्ती पार्सर्स में, शीर्ष स्टैक सिंबल की पूर्ववर्ती स्तर या व्याकरण की जकड़न की तुलना लुकहेड सिंबल से करके हैंडल का दाहिना सिरा पाया जाता है। उपरोक्त उदाहरण में, ''int'' और ''id'' कथन सीमांकक की तुलना में आंतरिक व्याकरण स्तर से संबंधित हैं। इसलिए ''int'' और ''id'' दोनों को इससे अधिक प्राथमिकता वाला माना जाता है; और जब भी ; का अनुसरण किया जाए तो इसे किसी अन्य चीज़ में घटा दिया जाना चाहिए। पूर्ववर्ती पार्सर की विभिन्न किस्में हैं, जिनमें से प्रत्येक में हैंडल के बाएं छोर को ढूंढने और प्रयुक्त करने के लिए सही नियम चुनने के विभिन्न विधियां हैं:
 *[[ऑपरेटर-प्राथमिकता पार्सर]], एक बहुत ही सरल संख्यात्मक विधि जो अभिव्यक्तियों के लिए काम करती है लेकिन सामान्य प्रोग्राम सिंटैक्स के लिए नहीं।
 *सरल पूर्वता पार्सर, दाएं और बाएं छोर को खोजने के लिए एक बड़ी एमएक्सएन तालिका का उपयोग करता है। [[PL360]] में प्रयुक्त.<ref>
 PL360 - A Programming Language for the 360 Computers, by Niklaus Wirth, J. ACM 15:1 1968.
-</ref> सामान्य प्रोग्रामिंग भाषाओं को संभाल नहीं पाता.
+</ref> सामान्य प्रोग्रामिंग लैंग्वेज को संभाल नहीं पाता.
 *कमजोर पूर्वता पार्सर, केवल हैंडल के दाहिने सिरे को खोजने के लिए पूर्वता तालिका का उपयोग करता है। साधारण पूर्वता की तुलना में अधिक व्याकरणों को संभालता है।<ref>
 The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing, by Alfred Aho and Jeffrey Ullman, Prentice Hall 1972.</ref>
 *विस्तारित प्राथमिकता पार्सर.
-{{anchor|MSP}}
-*मिश्रित रणनीति प्राथमिकता पार्सर, [[XPL]] के मूल संस्करण द्वारा उपयोग किया जाता है। त्रिगुणों को शामिल करने के लिए, किसी भी पूर्वता पहचानकर्ता में निहित युगलों का विस्तार करता है। एसएलआर से कम शक्तिशाली. आम तौर पर XPL जैसी अपेक्षाकृत छोटी भाषाओं के लिए भी बहुत बड़ी तालिकाएँ होती हैं, क्योंकि बड़ी संख्या में त्रिगुणों की आवश्यकता होती है, जिन्हें पूर्ववर्ती तरीकों द्वारा लगाई गई सीमाओं के बाहर व्याकरण को पहचानने की आवश्यकता होती है।<ref>A Compiler Generator, by William M. McKeeman, J Horning, and D Wortman, Prentice Hall 1970; {{ISBN|978-0131550773}}.</ref>
+*मिश्रित रणनीति प्राथमिकता पार्सर, [[XPL]] के मूल संस्करण द्वारा उपयोग किया जाता है। त्रिगुणों को सम्मिलित करने के लिए, किसी भी पूर्वता पहचानकर्ता में निहित युगलों का विस्तार करता है। एसएलआर से कम शक्तिशाली. सामान्यतः XPL जैसी अपेक्षाकृत छोटी लैंग्वेज के लिए भी बहुत बड़ी तालिकाएँ होती हैं, क्योंकि बड़ी संख्या में त्रिगुणों की आवश्यकता होती है, जिन्हें पूर्ववर्ती विधियों द्वारा लगाई गई सीमाओं के बाहर व्याकरण को पहचानने की आवश्यकता होती है।<ref>A Compiler Generator, by William M. McKeeman, J Horning, and D Wortman, Prentice Hall 1970; {{ISBN|978-0131550773}}.</ref>
-प्राथमिकता पार्सर्स उन व्याकरणों में सीमित हैं जिन्हें वे संभाल सकते हैं। निर्णय लेते समय वे अधिकांश पार्स स्टैक को अनदेखा कर देते हैं। वे केवल सर्वोच्च प्रतीकों के नामों पर विचार करते हैं, न कि उस पूरे संदर्भ पर, जहां वे प्रतीक अब व्याकरण में कहां दिखाई दे रहे हैं। प्राथमिकता के लिए आवश्यक है कि समान दिखने वाले प्रतीक संयोजनों को पूरे व्याकरण में समान तरीकों से पार्स और उपयोग किया जाना चाहिए, हालांकि वे संयोजन संदर्भ की परवाह किए बिना होते हैं।
+प्राथमिकता पार्सर्स उन व्याकरणों में सीमित हैं जिन्हें वे संभाल सकते हैं। निर्णय लेते समय वे अधिकांश पार्स स्टैक को अनदेखा कर देते हैं। वे केवल सर्वोच्च सिंबल के नामों पर विचार करते हैं, न कि उस पूरे संदर्भ पर, जहां वे सिंबल अब व्याकरण में कहां दिखाई दे रहे हैं। प्राथमिकता के लिए आवश्यक है कि समान दिखने वाले सिंबल संयोजनों को पूरे व्याकरण में समान विधियों से पार्स और उपयोग किया जाना चाहिए, हालांकि वे संयोजन संदर्भ की परवाह किए बिना होते हैं।
 एलआर पार्सर शिफ्ट-रिड्यूस पार्सिंग का एक अधिक लचीला रूप है, जो कई और व्याकरणों को संभालता है।<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | authorlink = Donald Knuth | title = भाषाओं के बाएँ से दाएँ अनुवाद पर| doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date=July 1965 | url = http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | access-date=29 May 2011 | doi-access = free }}</ref>
 ==एलआर पार्सर प्रोसेसिंग==
-एलआर पार्सर्स एक [[पुशडाउन ऑटोमेटन]] की तरह कार्य करते हैं, जो प्रत्येक शिफ्ट या कम कार्रवाई के लिए एक राज्य संक्रमण करते हैं। ये एक स्टैक का उपयोग करते हैं जहां वर्तमान स्थिति को शिफ्ट क्रियाओं द्वारा नीचे धकेल दिया जाता है। फिर इस स्टैक को कम क्रियाओं द्वारा पॉप (अप) किया जाता है। यह तंत्र एलआर पार्सर को सभी नियतात्मक संदर्भ-मुक्त व्याकरणों को संभालने की अनुमति देता है, जो पूर्ववर्ती व्याकरणों का एक सुपरसेट है। एलआर पार्सर पूरी तरह से [[कैनोनिकल एलआर पार्सर]] द्वारा कार्यान्वित किया जाता है। [[एलएएलआर पार्सर]]|लुक-अहेड एलआर और [[ सरल एलआर पार्सर ]] पार्सर इसके सरलीकृत वेरिएंट को लागू करते हैं जिससे मेमोरी आवश्यकताओं में काफी कमी आई है।<ref>Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.</ref><ref>Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.</ref> हाल के शोध ने उन तरीकों की पहचान की है जिनके द्वारा कैनोनिकल एलआर पार्सर्स को नथ के टेबल-बिल्डिंग एल्गोरिदम पर नाटकीय रूप से कम टेबल आवश्यकताओं के साथ लागू किया जा सकता है।<ref>X. Chen, [http://cssauh.com/xc/pub/chenx_dissertation.pdf Measuring and extending LR(1) parsing], University of Hawaii PhD dissertation, 2009.</ref>
+एलआर पार्सर्स एक [[पुशडाउन ऑटोमेटन]] की तरह कार्य करते हैं, जो प्रत्येक शिफ्ट या कम कार्रवाई के लिए एक राज्य संक्रमण करते हैं। ये एक स्टैक का उपयोग करते हैं जहां वर्तमान स्थिति को शिफ्ट क्रियाओं द्वारा नीचे धकेल दिया जाता है। फिर इस स्टैक को कम क्रियाओं द्वारा पॉप (अप) किया जाता है। यह तंत्र एलआर पार्सर को सभी नियतात्मक संदर्भ-मुक्त व्याकरणों को संभालने की अनुमति देता है, जो पूर्ववर्ती व्याकरणों का एक सुपरसेट है। एलआर पार्सर पूरी तरह से [[कैनोनिकल एलआर पार्सर]] द्वारा कार्यान्वित किया जाता है। [[एलएएलआर पार्सर]]|लुक-अहेड एलआर और [[ सरल एलआर पार्सर ]] पार्सर इसके सरलीकृत वेरिएंट को प्रयुक्त करते हैं जिससे मेमोरी आवश्यकताओं में काफी कमी आई है।<ref>Practical Translators for LR(k) Languages, by Frank DeRemer, MIT PhD dissertation 1969.</ref><ref>Simple LR(k) Grammars, by Frank DeRemer, Comm. ACM 14:7 1971.</ref> हाल के शोध ने उन विधियों की पहचान की है जिनके द्वारा कैनोनिकल एलआर पार्सर्स को नथ के टेबल-बिल्डिंग एल्गोरिदम पर नाटकीय रूप से कम टेबल आवश्यकताओं के साथ प्रयुक्त किया जा सकता है।<ref>X. Chen, [http://cssauh.com/xc/pub/chenx_dissertation.pdf Measuring and extending LR(1) parsing], University of Hawaii PhD dissertation, 2009.</ref>
-चाहे एलआर, एलएएलआर या एसएलआर, मूल राज्य मशीन एक ही है; केवल तालिकाएँ भिन्न होती हैं, और ये तालिकाएँ लगभग हमेशा यंत्रवत् उत्पन्न होती हैं। इसके अतिरिक्त, इन तालिकाओं को आम तौर पर इस तरह कार्यान्वित किया जाता है कि REDUCE के परिणामस्वरूप एक बंद सबरूटीन पर कॉल आती है जो राज्य मशीन के लिए बाहरी है और जो एक कार्य करता है जो कि व्याकरण नियम के शब्दार्थ द्वारा निहित है जिसे REDUCE किया जा रहा है। इसलिए, पार्सर को एक अपरिवर्तनीय राज्य मशीन भाग और एक भिन्न शब्दार्थ भाग में विभाजित किया गया है। यह मूलभूत अंतर उच्च गुणवत्ता वाले पार्सर्स के विकास को प्रोत्साहित करता है जो असाधारण रूप से विश्वसनीय हैं।
+चाहे एलआर, एलएएलआर या एसएलआर, मूल राज्य मशीन एक ही है; केवल तालिकाएँ भिन्न होती हैं, और ये तालिकाएँ लगभग हमेशा यंत्रवत् उत्पन्न होती हैं। इसके अतिरिक्त, इन तालिकाओं को सामान्यतः इस तरह कार्यान्वित किया जाता है कि REDUCE के परिणामस्वरूप एक बंद सबरूटीन पर कॉल आती है जो राज्य मशीन के लिए बाहरी है और जो एक कार्य करता है जो कि व्याकरण नियम के शब्दार्थ द्वारा निहित है जिसे REDUCE किया जा रहा है। इसलिए, पार्सर को एक अपरिवर्तनीय राज्य मशीन भाग और एक भिन्न शब्दार्थ भाग में विभाजित किया गया है। यह मूलभूत अंतर उच्च गुणवत्ता वाले पार्सर्स के विकास को प्रोत्साहित करता है जो असाधारण रूप से विश्वसनीय हैं।
-एक विशिष्ट स्टैक स्थिति और लुकआहेड प्रतीक को देखते हुए, सटीक रूप से चार संभावित क्रियाएं हैं, त्रुटि, शिफ्ट, कम करें और रोकें (इसके बाद कॉन्फ़िगरेशन के रूप में संदर्भित)। कॉन्फ़िगरेशन में एक बिंदु की उपस्थिति, •, वर्तमान लुकहेड स्थिति का प्रतिनिधित्व करती है, जिसमें लुकहेड प्रतीक बिंदु के दाईं ओर दिखाया गया है (और जो हमेशा एक टर्मिनल प्रतीक से मेल खाता है), और वर्तमान स्टैक स्थिति बिंदु के बाईं ओर दिखाई देती है (और जो आमतौर पर एक नॉनटर्मिनल प्रतीक से मेल खाता है)।
+एक विशिष्ट स्टैक स्थिति और लुकआहेड सिंबल को देखते हुए, सटीक रूप से चार संभावित क्रियाएं हैं, ERROR, शिफ्ट, कम करें और रोकें (इसके बाद कॉन्फ़िगरेशन के रूप में संदर्भित)। कॉन्फ़िगरेशन में एक बिंदु की उपस्थिति, •, वर्तमान लुकहेड स्थिति का प्रतिनिधित्व करती है, जिसमें लुकहेड सिंबल बिंदु के दाईं ओर दिखाया गया है (और जो हमेशा एक टर्मिनल सिंबल से मेल खाता है), और वर्तमान स्टैक स्थिति बिंदु के बाईं ओर दिखाई देती है (और जो सामान्यतः एक नॉनटर्मिनल सिंबल से मेल खाता है)।
-उच्च प्रदर्शन सहित व्यावहारिक कारणों से, तालिकाओं को आम तौर पर दो-बिट प्रतीकों की कुछ बड़ी, सहायक सरणी द्वारा विस्तारित किया जाता है, जो स्पष्ट रूप से बाइट-उन्मुख मशीनों पर कुशल पहुंच के लिए चार दो-बिट प्रतीकों, एक बाइट में संपीड़ित होती है, जिसे अक्सर एन्कोड किया जाता है :
+उच्च प्रदर्शन सहित व्यावहारिक कारणों से, तालिकाओं को सामान्यतः दो-बिट सिंबल की कुछ बड़ी, सहायक सरणी द्वारा विस्तारित किया जाता है, जो स्पष्ट रूप से बाइट-उन्मुख मशीनों पर कुशल पहुंच के लिए चार दो-बिट सिंबल, एक बाइट में संपीड़ित होती है, जिसे प्रायः एन्कोड किया जाता है :
-::'00'बी त्रुटि का प्रतिनिधित्व करता है
+::: '''00'''b represents ERROR
-::'01'बी SHIFT को दर्शाता है
+::: '''01'''b represents SHIFT
-::'10'बी REDUCE को दर्शाता है
+::: '''10'''b represents REDUCE
-::'11'बी स्टॉप को दर्शाता है
+::: '''11'''b represents STOP
-(SHIFT का विशेष मामला बनना बंद करें)। संपूर्ण सरणी में आम तौर पर अधिकतर त्रुटि कॉन्फ़िगरेशन, SHIFT और REDUCE कॉन्फ़िगरेशन की व्याकरण-परिभाषित संख्या और एक STOP कॉन्फ़िगरेशन शामिल होता है।
+::
+(SHIFT का विशेष स्थिति बनना बंद करें)। संपूर्ण सरणी में सामान्यतः अधिकतर ERROR कॉन्फ़िगरेशन, SHIFT और REDUCE कॉन्फ़िगरेशन की व्याकरण-परिभाषित संख्या और एक STOP कॉन्फ़िगरेशन सम्मिलित होता है।
 प्रोग्रामिंग प्रणालियों में जो [[चतुर्धातुक अंक प्रणाली]] (आधार 4, प्रति चतुर्धातुक अंक दो बिट) में मानों के विनिर्देशन का समर्थन करते हैं, जैसे कि XPL, इन्हें इस प्रकार कोडित किया जाता है, उदाहरण के लिए:
-:: (2)...'0'...त्रुटि को दर्शाता है
+:::: "(2)…'''0'''…" represents ERROR
-:: (2)...'1'...शिफ्ट का प्रतिनिधित्व करता है
+:::: "(2)…'''1'''…" represents SHIFT
-:: (2)...'2'...कम करना दर्शाता है
+:::: "(2)…'''2'''…" represents REDUCE
-:: (2)...'3'...स्टॉप को दर्शाता है
+:::: "(2)…'''3'''…" represents STOP
-SHIFT और REDUCE तालिकाओं को सरणी से अलग से लागू किया जाता है। सहायक सरणी की जांच केवल वर्तमान स्थिति और लुकआहेड प्रतीक के लिए की जाती है। (सहायक) सरणी भरी हुई है, जबकि (शिफ्ट और कम) तालिकाएं वास्तव में बहुत विरल हो सकती हैं, और उन SHIFT और REDUCE तालिकाओं के इष्टतम अपघटन के माध्यम से महत्वपूर्ण दक्षताएं प्राप्त की जा सकती हैं (ERROR और STOP को तालिकाओं की आवश्यकता नहीं है)।
+SHIFT और REDUCE तालिकाओं को सरणी से अलग से प्रयुक्त किया जाता है। सहायक सरणी की केवल वर्तमान स्थिति और लुकआहेड सिंबल के लिए "जांच" की जाती है। (सहायक) सरणी "पूर्ण" है, जबकि (शिफ्ट और कम) तालिकाएं वास्तव में बहुत "विरल" हो सकती हैं, और उन SHIFT और REDUCE तालिकाओं के इष्टतम "अपघटन" के माध्यम से महत्वपूर्ण दक्षताएं प्राप्त की जा सकती हैं (ERROR और STOP को तालिकाओं की आवश्यकता नहीं है) ).
 SHIFT-REDUCE पार्सर की मूल परिभाषा से SHIFT और REDUCE कॉन्फ़िगरेशन स्पष्ट हैं।
-STOP, फिर, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करता है जहां स्टैक के शीर्ष पर स्थिति और लुकहेड टर्मिनल प्रतीक विषय व्याकरण के भीतर है, और कार्यक्रम के अंत का प्रतिनिधित्व करता है:
+STOP, फिर, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करता है जहां स्टैक के शीर्ष पर स्थिति और लुकहेड टर्मिनल सिंबल विषय व्याकरण के भीतर है, और कार्यक्रम के अंत का प्रतिनिधित्व करता है:
-::'⊥' <कार्यक्रम> '•' '⊥'
+:::: '''⊥'''  <program> '''•''' '''⊥'''
 वैचारिक रूप से पहुँचने के लिए अंतिम '⊥' से आगे SHIFT करना असंभव है
-::'⊥' <कार्यक्रम> '⊥' '•'
+:::: '''⊥'''  <program> '''⊥''' '''•'''
-त्रुटि, तब, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करती है जहां स्टैक के शीर्ष पर स्थिति, और लुकहेड टर्मिनल प्रतीक विषय व्याकरण के भीतर नहीं है। यह एक त्रुटि पुनर्प्राप्ति प्रक्रिया को लागू करने का अवसर प्रस्तुत करता है, शायद, इसके सबसे सरल रूप में, लुकहेड टर्मिनल प्रतीक को त्यागने और अगले टर्मिनल प्रतीक को पढ़ने के लिए, लेकिन स्टैक को काटने, या लुकहेड को त्यागने सहित कई अन्य प्रोग्राम किए गए कार्य संभव हैं टर्मिनल प्रतीक और स्टैक की छंटाई (और एक पैथोलॉजिकल मामले में, इसे प्राप्त करना आमतौर पर संभव है
+ERROR, फिर, एक कॉन्फ़िगरेशन का प्रतिनिधित्व करती है जहां स्टैक के शीर्ष पर स्थिति और लुकहेड टर्मिनल सिंबल विषय व्याकरण के साथ नहीं है। यह ERROR पुनर्प्राप्ति प्रक्रिया को प्रयुक्त करने का अवसर प्रस्तुत करता है, संभवतः, इसके सबसे सरल रूप में, लुकहेड टर्मिनल सिंबल को त्यागने और अगले टर्मिनल सिंबल को पढ़ने के लिए, लेकिन कई अन्य प्रोग्राम किए गए कार्य संभव हैं, जिसमें स्टैक की सॉर्टिंग करना, या लुकहेड टर्मिनल सिंबल को त्यागना और स्टैक की सॉर्टिंग करना सम्मिलित है और पैथोलॉजिकल स्थिति में, सामान्यतः इसे प्राप्त करना संभव है
-::'⊥' <कार्यक्रम> '•' '⊥'
+:::::::::: '''⊥'''  <program> '''•''' '''⊥'''
-जहां <प्रोग्राम> में केवल एक एनओपी (कोड) होता है| शून्य कथन)।
+जहां <प्रोग्राम> में केवल "नल स्टेटमेंट" सम्मिलित है)।
 ज्यादातर मामलों में, स्टैक को जानबूझकर प्री-लोड किया जाता है, यानी आरंभीकृत किया जाता है
-::'⊥' '•' <प्रोग्राम> '⊥'
+:::: '''⊥''' '''•''' <program> '''⊥'''
-जिससे प्रारंभिक '⊥' को पहले ही पहचाना जा चुका माना जाता है। यह, तब, प्रोग्राम की शुरुआत का प्रतिनिधित्व करता है, और, इस प्रकार, एक अलग START कॉन्फ़िगरेशन होने से बचता है, जो कि वैचारिक रूप से है
+जिससे प्रारंभिक '⊥' को पहले ही पहचाना जा चुका माना जाता है। यह, तब, प्रोग्राम के आरम्भ का प्रतिनिधित्व करता है, और, इस प्रकार, एक अलग START कॉन्फ़िगरेशन होने से बचता है, जो कि वैचारिक रूप से है
-::'•' '⊥' <प्रोग्राम> '⊥'
+:::: '''•''' '''⊥''' <program> '''⊥'''
-'⊥' यांत्रिक रूप से व्याकरण में जोड़ा गया एक विशेष छद्म-टर्मिनल प्रतीक है, जैसे <प्रोग्राम> यांत्रिक रूप से एक विशेष छद्म-नॉनटर्मिनल प्रतीक हैव्याकरण में जोड़ा गया (यदि प्रोग्रामर ने व्याकरण में <प्रोग्राम> को स्पष्ट रूप से शामिल नहीं किया है, तो प्रोग्रामर की ओर से <प्रोग्राम> स्वचालित रूप से व्याकरण में जोड़ा जाएगा)।
+'⊥' यांत्रिक रूप से व्याकरण में जोड़ा गया एक विशेष छद्म-टर्मिनल सिंबल है, जैसे <प्रोग्राम> यांत्रिक रूप से एक विशेष छद्म-नॉनटर्मिनल सिंबल हैव्याकरण में जोड़ा गया (यदि प्रोग्रामर ने व्याकरण में <प्रोग्राम> को स्पष्ट रूप से सम्मिलित नहीं किया है, तो प्रोग्रामर की ओर से <प्रोग्राम> स्वचालित रूप से व्याकरण में जोड़ा जाएगा)।
-स्पष्ट रूप से, ऐसे पार्सर में सटीक रूप से एक (अंतर्निहित) START कॉन्फ़िगरेशन और एक (स्पष्ट) STOP कॉन्फ़िगरेशन होता है, लेकिन इसमें सैकड़ों SHIFT और REDUCE कॉन्फ़िगरेशन और शायद हजारों त्रुटि कॉन्फ़िगरेशन हो सकते हैं और आमतौर पर होते हैं।
+स्पष्ट रूप से, ऐसे पार्सर में सटीक रूप से एक (अंतर्निहित) START कॉन्फ़िगरेशन और एक (स्पष्ट) STOP कॉन्फ़िगरेशन होता है, लेकिन इसमें सैकड़ों SHIFT और REDUCE कॉन्फ़िगरेशन और शायद हजारों ERROR कॉन्फ़िगरेशन हो सकते हैं और सामान्यतः होते हैं।
 ==संदर्भ==
@@ Line 172: / Line 172: @@
 {{reflist}}
-{{Parsers}}
+[[Category:Collapse templates]]
-[[Category: पार्सिंग एल्गोरिदम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 26/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with broken file links]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:पार्सिंग एल्गोरिदम]]

Anonymous

Search

शिफ्ट-रिड्यूस पार्सर: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:23, 16 August 2023

Contents

सिंहावलोकन

ट्री निर्माण चरण

व्याकरण

पार्सर एक्शन्स

शिफ्ट-रिड्यूस पार्सर्स के प्रकार

एलआर पार्सर प्रोसेसिंग

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

शिफ्ट-रिड्यूस पार्सर: Difference between revisions

Latest revision as of 11:23, 16 August 2023

सिंहावलोकन

ट्री निर्माण चरण

व्याकरण

पार्सर एक्शन्स

शिफ्ट-रिड्यूस पार्सर्स के प्रकार

एलआर पार्सर प्रोसेसिंग

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories