एलआर पार्सर: Difference between revisions

Revision as of 14:07, 4 August 2023

कंप्यूटर साइंस में, एलआर पार्सर प्रकार का नीचे से ऊपर का विश्लेषण|बॉटम-अप पार्सर है जो रैखिक समय में नियतात्मक संदर्भ-मुक्त लैंग्वेज का विश्लेषण करता है।^[1] एलआर पार्सर के अनेक प्रकार हैं: एसएलआर पार्सर, एलएएलआर पार्सर, कैनोनिकल एलआर पार्सर|कैनोनिकल एलआर(1) पार्सर, कैनोनिकल एलआर पार्सर|मिनिमल एलआर(1) पार्सर, और सामान्यीकृत एलआर पार्सर। एलआर पार्सर्स को पार्सर जनरेटर द्वारा पार्स की जाने वाली लैंग्वेज के सिन्टैक्स को परिभाषित करने वाले फॉर्मल व्याकरण से उत्पन्न किया जा सकता है। इनका व्यापक रूप से कंप्यूटर लैंग्वेजओं के प्रसंस्करण के लिए उपयोग किया जाता है।

एक एलआर पार्सर (बाएं से दाएं, विपरीत दिशा में अधिक दाहिनी व्युत्पत्ति) बिना बैकअप के बाएं से दाएं इनपुट टेक्स्ट को रीड करता है (यह अधिकांश पार्सर्स के लिए सत्य है), और रिवर्स में अधिक दाईं ओर व्युत्पत्ति उत्पन्न करता है: यह बॉटम-अप पार्सिंग|बॉटम-अप पार्स करता है - न कि ऊपर से नीचे विश्लेषण |टॉप-डाउन एलएल पार्स या एड-हॉक पार्स। एलआर नाम के पश्चात प्रायः संख्यात्मक क्वालीफायर आता है, जैसे एलआर(1) या कभी-कभी एलआर(के)। बैक ट्रैकिंग या अनुमान लगाने से बचने के लिए, एलआर पार्सर को पूर्व के सिम्बल को पार्स करने का निर्णय लेने से पहले k पार्सिंग#लुकहेड इनपुट सिम्बल (फॉर्मल) पर आगे देखने की अनुमति है। सामान्यतः k 1 होता है और इसका उल्लेख नहीं किया जाता है। एलआर नाम के पहले प्रायः अन्य क्वालीफायर आते हैं, जैसे एसएलआर और एलएएलआर में। व्याकरण के लिए LR(k) संकेतन का सुझाव नुथ द्वारा दिया गया था, जिसका अर्थ है k के साथ बाएँ से दाएँ अनुवाद किया जा सकता है।^[1]

एलआर पार्सर नियतात्मक हैं; वे रैखिक समय में बिना किसी अनुमान या पीछे हटने के ही सही पार्स तैयार करते हैं। यह कंप्यूटर लैंग्वेज के लिए आदर्श है, किन्तु एलआर पार्सर मानव लैंग्वेज के लिए उपयुक्त नहीं हैं, जिन्हें अधिक लचीले किन्तु अनिवार्य रूप से धीमे विधियों की आवश्यकता होती है। कुछ विधियाँ जो इच्छानुसार से संदर्भ-मुक्त लैंग्वेज को पार्स कर सकती हैं (उदाहरण के लिए, CYK एल्गोरिथ्म | कॉके-यंगर-कासामी, अर्ली पार्सर, जीएलआर पार्सर) में O( का प्रदर्शन सबसे खराब है)n³) समय. अन्य विधियां जो गलत अनुमान लगाने पर पीछे हटती हैं या कई विश्लेषण देती हैं, उनमें सामान्य अधिक समय लग सकता है।^[2]

एल, आर, और के के उपरोक्त गुण वास्तव में सभी शिफ्ट-कम पार्सर द्वारा साझा किए जाते हैं, जिनमें सरल प्राथमिकता वाले पार्सर्स भी सम्मिलित हैं। किन्तु परंपरा के अनुसार, एलआर नाम डोनाल्ड नुथ द्वारा आविष्कार किए गए पार्सिंग के रूप को दर्शाता है, और पूर्व के, कम शक्तिशाली पूर्ववर्ती विधि (उदाहरण के लिए ऑपरेटर-प्राथमिकता पार्सर) को बाहर करता है।^[1] एलआर पार्सर पूर्ववर्ती पार्सर या टॉप-डाउन एलएल पार्सिंग की तुलना में लैंग्वेज और व्याकरणों की उच्च श्रृंखला को संभाल सकते हैं।^[3] ऐसा इसलिए है क्योंकि एलआर पार्सर तब तक वेट करता है जब तक कि उसने जो पाया है उसे पूर्ण करने से प्रथम कुछ व्याकरण पैटर्न का पूर्ण उदाहरण नहीं दर्शाया है। और एलएल पार्सर को यह तय करना होगा या अनुमान लगाना होगा कि वह क्या दर्शा रहा है, जबकि उसने केवल उस पैटर्न का अधिक बायां इनपुट सिम्बल दर्शाया गया है।

अवलोकन

उदाहरण के लिए बॉटम-अप पार्स ट्री A*2 + 1

File:Shift-Reduce Parse Steps for A*2+1.svg

बॉटम-अप पार्स ट्री क्रमांकित चरणों में निर्मित

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

उदाहरण पार्स में चरण 6 पर, केवल A*2 को अपूर्ण रूप से पार्स किया गया है। पार्स ट्री का केवल छायांकित निचला-बाएँ कोना उपस्तिथ है। अतः 7 और उससे ऊपर क्रमांकित कोई भी पार्स ट्री नोड अभी तक उपस्तिथ नहीं है। नोड्स 3, 4, और 6 क्रमशः वेरिएबल ए, ऑपरेटर * और नंबर 2 के लिए भिन्न-भिन्न सबट्री की रूट हैं। इन तीन रूट नोड्स को अस्थायी रूप से पार्स स्टैक में रखा जाता है। और इनपुट स्ट्रीम का शेष अनपार्स्ड भाग + 1 है।

कार्यों को परिवर्तन और कम करें

अन्य शिफ्ट-रिड्यूस पार्सर्स की तरह, एलआर पार्सर शिफ्ट स्टेप्स और रिड्यूस स्टेप्स का कुछ संयोजन करके कार्य करता है।

एक शिफ़्ट चरण इनपुट स्ट्रीम में सिम्बल द्वारा आगे बढ़ता है। वह स्थानांतरित सिम्बल नया एकल-नोड पार्स ट्री बन जाता है।
रिड्यूस चरण कुछ वर्तमान पार्स ट्री पर पूर्ण व्याकरण नियम प्रयुक्त करता है, उन्हें नए रूट सिम्बल के साथ ट्री के रूप में जोड़ता है।

यदि इनपुट में कोई सिन्टैक्स त्रुटियां नहीं हैं, तो पार्सर इन चरणों के साथ तब तक प्रवाहित रहता है जब तक कि सभी इनपुट का उपभोग नहीं हो जाता है और सभी पार्स ट्री पूर्ण नियम इनपुट का प्रतिनिधित्व करने वाले ट्री में कम नहीं हो जाते हैं।

एलआर पार्सर अन्य शिफ्ट-रिड्यूस पार्सर्स से भिन्न होते हैं कि वे कैसे तय करते हैं कि कब कम करना है, और समान अंत वाले नियमों के मध्य कैसे चयन करना है। किन्तु अंतिम निर्णय और परिवर्तन या कमी के पदों का क्रम समान है।

इस प्रकार से एलआर पार्सर की अधिकांश दक्षता नियतिवादी होने से है। अनुमान लगाने से बचने के लिए, एलआर पार्सर प्रायः पूर्व के स्कैन किए गए सिम्बल के साथ क्या करना है, यह तय करने से पूर्व, अगले स्कैन किए गए सिम्बल पर आगे (दाईं ओर) देखता है। लेक्सिकल स्कैनर पार्सर के आगे या अधिक सिम्बल पर कार्य करता है। और पार्सिंग निर्णय के लिए लुकहेड प्रतीक 'दाहिने हाथ का संदर्भ' हैं।^[4]

बॉटम-अप पार्स स्टैक

File:Bottom-Up Parser.svg

चरण 6 पर बॉटम-अप पार्सर

अन्य शिफ्ट-रिड्यूस पार्सर्स की तरह, एलआर पार्सर तब तक प्रतीक्षा करता है जब तक कि वह संयुक्त निर्माण के लिए प्रतिबद्ध होने से पूर्व कुछ निर्माण के सभी भागो को स्कैन और पार्स नहीं करता है। फिर पार्सर किसी और प्रतीक्षा के अतिरिक्त संयोजन पर शीघ्र कार्य करता है। और पार्स ट्री उदाहरण में, जैसे ही लुकआहेड * दिखाई देता है, चरण 1-3 में वाक्यांश ए वैल्यू में और फिर उत्पादों में कम हो जाता है, अतः पार्स ट्री के उन भागो को व्यवस्थित करने के लिए पश्चात में प्रतीक्षा करने के अतिरिक्त कार्य करता है। चूंकि ए को कैसे संभालना है इसका निर्णय केवल उस पर आधारित है जो पार्सर और स्कैनर ने पहले ही देखा है, उन वस्तु पर विचार किए बिना जो दाईं ओर में पुनः दिखाई देती हैं।

इस प्रकार से कटौती सामान्य वर्तमान  में पार्स की गई वस्तु  को पुनर्गठित करती है, लुकहेड सिम्बल  के शीघ्र  बाईं ओर है । तब  पुनः से ही पार्स की गई वस्तु की सूची स्टैक (सार डेटा प्रकार) की तरह कार्य  करती है। यह पार्स स्टैक दाईं ओर बढ़ता है। और स्टैक का आधार या सतह  बायीं ओर है और सामान्य से  बायीं ओर, अधिक ओल्ड  पार्स टुकड़ा रखता है। प्रत्येक कटौती चरण केवल सामान्य दाहिने, नवीनतम पार्स अंशों पर कार्य करता है। (यह संचयी पार्स स्टैक ऊपर से नीचे पार्सर द्वारा उपयोग किए जाने वाले पूर्वानुमानित, बाईं ओर बढ़ने वाले पार्स स्टैक से अधिक अलग है।)

उदाहरण के लिए नीचे से ऊपर पार्स चरण ए*2 + 1

Step	Parse Stack	Unparsed	Shift/Reduce
0	empty	A*2 + 1	shift
1	id	*2 + 1	Value → id
2	Value	*2 + 1	Products → Value
3	Products	*2 + 1	shift
4	Products *	2 + 1	shift
5	Products * int	+ 1	Value → int
6	Products * Value	+ 1	Products → Products * Value
7	Products	+ 1	Sums → Products
8	Sums	+ 1	shift
9	Sums +	1	shift
10	Sums + int	eof	Value → int
11	Sums + Value	eof	Products → Value
12	Sums + Products	eof	Sums → Sums + Products
13	Sums	eof	done

चरण 6 अनेक भागों के साथ व्याकरण नियम प्रयुक्त करता है:

उत्पाद → उत्पाद * मूल्य

यह पार्स किए गए सिटैक्स को रखने वाले स्टैक टॉप से मेल खाता है ... उत्पाद * मान। कम करने का चरण नियम के दाईं ओर के इस उदाहरण को प्रतिस्थापित करता है, उत्पाद * मान को नियम के बाईं ओर के सिम्बल से, यहां उच्च उत्पाद है। यदि पार्सर पूर्ण पार्स ट्री बनाता है, तो आंतरिक उत्पादों के लिए तीन ट्री, *, और मान को उत्पादों के लिए नवीन ट्री की रूट से जोड़ दिया जाता है। अन्यथा, आंतरिक उत्पादों और मान से सिमेंटिक्स#प्रोग्रामिंग लैंग्वेज का विवरण के पश्चात कंपाइलर पास में आउटपुट होता है, या नए उत्पाद सिम्बल में संयुक्त और सहेजा जाता है।^[5]

एलआर पार्स चरण उदाहरण के लिए ए*2 + 1

एलआर पार्सर्स में, परिवर्तन और कटौती के निर्णय संभावित रूप से पूर्व से पार्स किए गए सभी वस्तु के पूर्ण स्टैक पर आधारित होते हैं, न कि केवल एक, अधिक ऊपरी स्टैक सिम्बल पर है। यदि अस्पष्ट विधि से किया जाता है, तो इससे अधिक धीमे पार्सर हो सकते हैं जो लंबे इनपुट के लिए धीमे और धीमे होते जाते हैं। एलआर पार्सर सभी प्रासंगिक बाएं संदर्भ जानकारी को एलआर (0) पार्सर स्थिति नामक एकल संख्या में सारांशित करके निरंतर गति से करते हैं। प्रत्येक व्याकरण और एलआर विश्लेषण पद्धति के लिए, ऐसी अवस्थाओं की निश्चित (सीमित) संख्या होती है। पूर्व से ही पार्स किए गए सिम्बल को रखने के अतिरिक्त, पार्स स्टैक उन बिंदुओं तक पहुंची राज्य संख्याओं को भी याद रखता है।

इस प्रकार से प्रत्येक पार्स चरण में, संपूर्ण इनपुट टेक्स्ट को पूर्व से पार्स किए गए सिन्टैक्स के रूप में, वर्तमान लुक-फ़ॉरवर्ड सिम्बल और शेष अनस्कैन किए गए है, टेक्स्ट में विभाजित किया गया है। पार्सर की अगली नियम उसके वर्तमान LR(0) द्वारा निर्धारित होती है state number (स्टैक पर सबसे दाहिनी ओर) और आगे की ओर देखने का सिम्बल है। नीचे दिए गए चरणों में, सभी ब्लैक विवरण अन्य नॉन-एलआर शिफ्ट-रिड्यूस पार्सर्स के समान ही हैं। और एलआर पार्सर स्टैक बैंगनी रंग में स्थिति की जानकारी जोड़ते हैं, स्टैक पर उनके बाईं ओर ब्लैक सिन्टैक्स का सारांश देते हैं और आगे क्या सिंटैक्स संभावनाओं की उम्मीद करते हैं। एलआर पार्सर के उपयोगकर्ता सामान्यतः अवस्था की जानकारी को अनदेखा कर सकते हैं। इन स्थितियों को पश्चात के अनुभाग में दर्शाया गया है।

Step	Parse Stack _state [Symbol_state]*	Look Ahead	Unscanned	Parser Action	Grammar Rule	Next State
0	₀	id	*2 + 1	shift		9
1	₀ id₉	*	2 + 1	reduce	Value → id	7
2	₀ Value₇	*	2 + 1	reduce	Products → Value	4
3	₀ Products₄	*	2 + 1	shift		5
4	₀ Products₄ *₅	int	+ 1	shift		8
5	₀ Products₄ ₅ int*₈	+	1	reduce	Value → int	6
6	₀ Products₄ *₅ Value₆	+	1	reduce	Products → Products * Value	4
7	₀ Products₄	+	1	reduce	Sums → Products	1
8	₀ Sums₁	+	1	shift		2
9	₀ Sums₁ +₂	int	eof	shift		8
10	₀ Sums₁ +₂ int₈	eof		reduce	Value → int	7
11	₀ Sums₁ +₂ Value₇	eof		reduce	Products → Value	3
12	₀ Sums₁ +₂ Products₃	eof		reduce	Sums → Sums + Products	1
13	₀ Sums₁	eof		done

प्रारंभिक चरण 0 पर, इनपुट स्ट्रीम A*2 + 1 में विभाजित है

पार्स स्टैक पर रिक्त अनुभाग,
आगे की ओर देखें टेक्स्ट ए को आईडी सिम्बल के रूप में स्कैन किया गया है,
शेष बिना स्कैन किया हुआ पाठ *2 + 1।

पार्स स्टैक केवल प्रारंभिक स्थिति 0 को पकड़कर प्रारंभ होता है। जब स्थिति 0 लुकहेड आईडी देखती है, तो वह उस आईडी को स्टैक पर स्थानांतरित करती है, और अगले इनपुट सिंटैक्स '*' को स्कैन करती है, और स्थिति 9 पर आगे बढ़ती है।

चरण 4 पर, कुल इनपुट स्ट्रीम A*2 + 1 को वर्तमान में विभाजित किया गया है

पार्स किया गया अनुभाग ए * 2 स्टैक्ड सिंटैक्स के साथ उत्पाद और *,
लुकअहेड टेक्स्ट 2 को int सिम्बल के रूप में स्कैन किया गया, और
शेष बिना स्कैन किया हुआ पाठ + 1।

स्टैक्ड सिंटैक्स के अनुरूप स्थितियाँ 0, 4, और 5 हैं। स्टैक पर वर्तमान, सबसे दाहिनी स्थिति स्थिति 5 है। जब स्थिति 5 लुकहेड int को देखती है, तो वह उस int को अपने स्वयं के सिंटैक्स के रूप में स्टैक पर स्थानांतरित करना जानती है, और अगले इनपुट सिम्बल + को स्कैन करती है, और स्थिति 8 पर आगे बढ़ती है।

चरण 12 पर, सभी इनपुट स्ट्रीम का उपभोग हो चुका है किन्तु केवल आंशिक रूप से व्यवस्थित किया गया है। वर्तमान स्थिति 3 है। जब स्थिति 3 ईओफ़ का पूर्वाभास देखती है, तो वह पूर्ण व्याकरण नियम को प्रयुक्त करती है

सम्स→ सम्स+ उत्पाद

सम्स, '+' और प्रोडक्ट्स के लिए स्टैक के सबसे दाहिने तीन वाक्यांशों को वस्तु में जोड़कर प्रयुक्त करती है। यदि अवस्था 3 को स्वयं नहीं पता कि अगली अवस्था क्या होना चाहिए। इसे कम किए जा रहे वाक्यांश के ठीक बाईं ओर स्थिति 0 पर वापस जाकर पाया जाता है। जब अवस्था 0 सम्स के इस नए पूर्ण उदाहरण को देखता है, तो यह राज्य 1 (फिर से) की ओर बढ़ता है। पुराने अवस्था के इस परामर्श के कारण ही उन्हें केवल वर्तमान स्थिति को ध्यान में रखने के अतिरिक्त, स्टैक पर रखा जाता है।

उदाहरण के लिए व्याकरण ए*2 + 1

एलआर पार्सर व्याकरण से निर्मित होते हैं जो औपचारिक रूप से इनपुट लैंग्वेज के वाक्यविन्यास को पैटर्न के सेट के रूप में परिभाषित करता है। व्याकरण सभी लैंग्वेज नियमों को सम्मिलित नहीं करता है, जैसे संख्याओं का आकार, या पूरे कार्यक्रम के संदर्भ में नामों और उनकी परिभाषाओं का निरंतर उपयोग किया जाता है। एलआर पार्सर्स संदर्भ-मुक्त व्याकरण का उपयोग करते हैं जो केवल सिम्बल के स्थानीय पैटर्न से संबंधित है।

यहां प्रयुक्त उदाहरण व्याकरण जावा या सी लैंग्वेज का छोटा सबसेट है:

r0: लक्ष्य → योग

r1: सम्स → सम्स + उत्पाद

r2: सम्स → उत्पाद

r3: उत्पाद → उत्पाद * मान

r4: उत्पाद → मान

r5: मान → पूर्णांक

r6: मान → आईडी

व्याकरण के टर्मिनल सिम्बल बहु-वर्ण सिम्बल या 'टोकन' हैं जो शाब्दिक विश्लेषण द्वारा इनपुट स्ट्रीम में पाए जाते हैं। यहां इनमें किसी भी पूर्णांक स्थिरांक के लिए '+' '*' और int, और किसी भी पहचानकर्ता नाम के लिए id, और इनपुट फ़ाइल के अंत के लिए eof सम्मिलित हैं। व्याकरण को इसकी नेतृत्व नहीं है कि int मान या id वर्तनी क्या हैं, न ही यह रिक्त स्थान या पंक्ति विराम की नेतृत्व करता है। व्याकरण इन टर्मिनल सिम्बल का उपयोग करता है किन्तु उन्हें परिभाषित नहीं करता है। वे सदैव पार्स ट्री के लीव्स के नोड (निचले बुशय हेड पर) होते हैं।

सम्स जैसे उच्च अक्षर वाले शब्द नॉनटर्मिनल सिम्बल हैं। ये लैंग्वेज में अवधारणाओं या पैटर्न के नाम हैं। वे व्याकरण में परिभाषित हैं और इनपुट स्ट्रीम में स्वयं कभी नहीं आते हैं। वे प्रायः पार्स ट्री के आंतरिक नोड्स (नीचे से ऊपर) होते हैं। वे केवल पार्सर द्वारा कुछ व्याकरण नियम प्रयुक्त करने के परिणामस्वरूप होते हैं। कुछ नॉनटर्मिनलों को दो या दो से अधिक नियमों से परिभाषित किया गया है; ये वैकल्पिक पैटर्न हैं. नियम स्वयं को वापस संदर्भित कर सकते हैं, जिन्हें पुनरावर्ती कहा जाता है। यह व्याकरण दोहराए गए गणित ऑपरेटरों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करता है। संपूर्ण लैंग्वेज के व्याकरण सूचियों, कोष्ठकबद्ध अभिव्यक्तियों और नेस्टेड कथनों को संभालने के लिए पुनरावर्ती नियमों का उपयोग करते हैं।

किसी भी कंप्यूटर लैंग्वेज को अनेक अलग-अलग व्याकरणों द्वारा वर्णित किया जा सकता है। LR(1) पार्सर अनेक सामान्य व्याकरणों को नहीं किन्तु सभी को संभाल सकता है। सामान्यतः व्याकरण को मैन्युअल रूप से संशोधित करना संभव है जिससे यह एलआर (1) पार्सिंग और जेनरेटर टूल की सीमाओं में फिट हो सकते है।

अतः एलआर पार्सर के लिए व्याकरण स्वयं अस्पष्ट व्याकरण होना चाहिए, या टाई-ब्रेकिंग प्राथमिकता नियमों द्वारा संवर्धित किया जाना चाहिए। इसका अर्थ यह है कि लैंग्वेज के किसी दिए गए नियम उदाहरण में व्याकरण को प्रयुक्त करने का केवल ही सही विधि है, जिसके परिणामस्वरूप केवल अर्थ के साथ अद्वितीय पार्स ट्री होता है, और उस उदाहरण के लिए क्रियाओं को परिवर्तन/घटाने का अद्वितीय अनुक्रम होता है। एलआर पार्सिंग अस्पष्ट व्याकरण वाली मानव लैंग्वेज के लिए उपयोगी तकनीक नहीं है जो शब्दों के परस्पर क्रिया पर निर्भर करती है। मानव लैंग्वेज को सामान्यीकृत एलआर पार्सर, अर्ली पार्सर, या CYK एल्गोरिथ्म जैसे पार्सर्स द्वारा उत्तम रूप से नियंत्रित किया जाता है जो ही पास में सभी संभावित पार्स ट्री की साथ गणना कर सकते हैं।

उदाहरण व्याकरण के लिए पार्स टेबल

अधिकांश एलआर पार्सर टेबल चालित होते हैं। पार्सर का प्रोग्राम कोड सरल सामान्य लूप है जो सभी व्याकरणों और लैंग्वेज के लिए समान है। व्याकरण का ज्ञान और इसके वाक्य-विन्यास निहितार्थों को अपरिवर्तनीय डेटा टेबल में कोडित किया जाता है जिन्हें पार्स टेबल (या पार्सिंग टेबल) कहा जाता है। टेबल में प्रविष्टियाँ दर्शाती हैं कि पार्सर स्थिति और लुकहेड सिम्बल के प्रत्येक नियम संयोजन के लिए परिवर्तन करना है या कम करना है (और किस व्याकरण नियम के अनुसार)। पार्स टेबल यह भी दर्शाती हैं कि केवल वर्तमान स्थिति और अगले सिम्बल को देखते हुए, अगली स्थिति की गणना कैसे करते है।

पार्स टेबल व्याकरण से अधिक उच्च होती हैं। उच्च व्याकरणों के लिए एलआर टेबल की हाथ से स्पष्ट गणना करना कठिन है। इसलिए वे जीएनयू बाइसन जैसे कुछ पार्सर जेनरेटर टूल द्वारा व्याकरण से यांत्रिक रूप से प्राप्त किए जाते हैं।^[6]

स्थिति और पार्सिंग टेबल कैसे उत्पन्न होती है, इसके आधार पर, परिणामी पार्सर को या तो साधारण एलआर पार्सर|एसएलआर (सरल एलआर) पार्सर, एलएएलआर पार्सर|एलएएलआर (लुक-फॉरवर्ड एलआर) पार्सर, या कैनोनिकल एलआर पार्सर कहा जाता है। एलएएलआर पार्सर एसएलआर पार्सर की तुलना में अधिक व्याकरण संभालते हैं। कैनोनिकल एलआर पार्सर और भी अधिक व्याकरणों को संभालते हैं, किन्तु अनेक अधिक राज्यों और अधिक उच्च टेबल का उपयोग करते हैं। उदाहरण व्याकरण एसएलआर है.

एलआर पार्स टेबल द्वि-आयामी हैं। प्रत्येक वर्तमान LR(0) पार्सर स्थिति की अपनी पंक्ति होती है। प्रत्येक संभावित अगले सिम्बल का अपना कॉलम होता है। वैध इनपुट स्ट्रीम के लिए राज्य और अगले सिम्बल के कुछ संयोजन संभव नहीं हैं। ये रिक्त सेल सिंटैक्स त्रुटि संदेशों को ट्रिगर करती हैं।

टेबल के बाएँ आधे भाग में लुकअहेड टर्मिनल सिम्बल के लिए कॉलम हैं। ये सेल निर्धारित करती हैं कि अगली पार्सर क्रिया शिफ्ट है (अवस्था एन के लिए), या कम करें (व्याकरण नियम आर द्वारा)।_n).

टेबल के गोटो दाहिने आधे भाग में नॉनटर्मिनल सिम्बल के लिए कॉलम हैं। ये सेल दिखाते हैं कि किस स्थिति में आगे बढ़ना है, कुछ कमी के पश्चात लेफ्ट हैंड साइड ने उस सिम्बल का अपेक्षित नया उदाहरण बनाया है। यह शिफ्ट नियम की तरह है किन्तु गैर-टर्मिनलों के लिए; लुकअहेड टर्मिनल सिम्बल अपरिवर्तित है।

टेबल कॉलम वर्तमान नियम प्रत्येक अवस्था के लिए अर्थ और वाक्यविन्यास संभावनाओं का दस्तावेजीकरण करता है, जैसा कि पार्सर जनरेटर द्वारा तैयार किया गया है। यह पार्सिंग के समय उपयोग की जाने वाली वास्तविक टेबल में सम्मिलित नहीं है। <बड़ा>•</बड़ा>(गुलाबी बिंदु) मार्कर दिखाता है कि पार्सर अब कहां है, कुछ आंशिक रूप से मान्यता प्राप्त व्याकरण नियमों के अन्दर । <बड़े> के बायीं ओर की वस्तु•विश्लेषण कर लिया गया है, और दाईं ओर की वस्तु शीघ्र ही अपेक्षित हैं। अवस्था में ऐसे कई उपस्तिथ नियम हैं यदि पार्सर ने अभी तक संभावनाओं को नियम तक सीमित नहीं किया है।

Curr		Lookahead					LHS Goto
State	Current Rules	int	id	*	+	eof	Sums	Products	Value
0	Goal → • Sums eof	8	9				1	4	7
1	Goal → Sums • eof Sums → Sums • + Products				2	done
2	Sums → Sums + • Products	8	9					3	7
3	Sums → Sums + Products • Products → Products • * Value			5	r1	r1
4	Sums → Products • Products → Products • * Value			5	r2	r2
5	Products → Products * • Value	8	9						6
6	Products → Products * Value •			r3	r3	r3
7	Products → Value •			r4	r4	r4
8	Value → int •			r5	r5	r5
9	Value → id •			r6	r6	r6

उपरोक्त स्थिति 2 में, पार्सर ने अभी-अभी व्याकरण नियम का + पाया और स्थानांतरित किया है

r1: सम्स → सम्स+ <बड़ा>•</बड़े>उत्पाद

अगला अपेक्षित वाक्यांश उत्पाद है। उत्पाद टर्मिनल सिम्बल int या id से प्रारंभ होते हैं। यदि लुकआहेड इनमें से कोई है, तो पार्सर उन्हें स्थानांतरित कर देता है और क्रमशः 8 या 9 स्थिति में ले जाता है। जब कोई उत्पाद मिल जाता है, तो पार्सर सारांश की पूर्ण सूची जमा करने और नियम r0 का अंत खोजने के लिए अवस्था 3 पर आगे बढ़ता है। उत्पाद नॉनटर्मिनल वैल्यू से भी प्रारंभ हो सकता है। किसी अन्य लुकअहेड या नॉनटर्मिनल के लिए, पार्सर सिंटैक्स त्रुटि की घोषणा करता है।

राज्य 3 में, पार्सर को अभी उत्पाद वाक्यांश मिला है, जो दो संभावित व्याकरण नियमों से हो सकता है:

r1: सम्स → सम्स + उत्पाद <बड़ा>•</बड़ा>

r3: उत्पाद → उत्पाद <बड़ा>•</बड़ा> *मूल्य

आर1 और आर3 के मध्य चयन का निर्णय केवल पूर्व वाक्यांशों को पीछे मुड़कर देखने से नहीं किया जा सकता है। क्या करना है यह बताने के लिए पार्सर को लुकअहेड सिम्बल की जांच करनी होती है। यदि लुकहेड * है, तो यह नियम 3 में है, इसलिए पार्सर * में स्थानांतरित हो जाता है और स्थिति 5 पर आगे बढ़ता है। यदि लुकहेड ईओएफ है, तो यह नियम 1 और नियम 0 के अंत में है, इसलिए पार्सर कर दिया है।

उपरोक्त स्थिति 9 में, सभी गैर-रिक्त, गैर-त्रुटि सेल समान कमी r6 के लिए हैं। कुछ पार्सर इन साधारण स्तिथितो में लुकहेड सिम्बल की जाँच न करके समय और टेबल स्थान बचाते हैं। सिंटैक्स एरर का पता कुछ सीमा के पश्चात लगाया जाता है, कुछ हानिरहित कटौती के पश्चात , किन्तु फिर भी अगली शिफ्ट नियम या पार्सर निर्णय से पहले।

भिन्न-भिन्न टेबल सेल में एकाधिक, वैकल्पिक क्रियाएं नहीं होनी चाहिए, अन्यथा पार्सर अनुमान और बैकट्रैकिंग के साथ गैर-निर्धारक होता है। यदि व्याकरण एलआर (1) नहीं है, तो कुछ सेल में संभावित शिफ्ट कार्रवाई और कार्रवाई को कम करने, या एकाधिक व्याकरण नियमों के मध्य संघर्ष को कम/कम करने की क्षमता होगी। एलआर (के) पार्सर्स पहले से परे अतिरिक्त लुकहेड सिम्बल की जांच करके इन संघर्षों (जहां संभव हो) को हल करते हैं।

एलआर पार्सर लूप

एलआर पार्सर लगभग रिक्त पार्स स्टैक के साथ प्रारंभ होता है जिसमें सिर्फ प्रारंभिक स्थिति 0 होती है, और लुकहेड में इनपुट स्ट्रीम का प्रथम स्कैन किया गया सिम्बल होता है। पार्सर तब तक निम्न लूप चरण को दोहराता है जब तक कि यह पूरा न हो जाए, या सिंटैक्स त्रुटि पर अटक न जाए:

पार्स स्टैक पर सबसे ऊपरी स्थिति कुछ स्थिति s है, और वर्तमान लुकहेड कुछ टर्मिनल सिम्बल t है। लुकहेड एक्शन टेबल की पंक्ति एस और कॉलम टी से अगली पार्सर कार्रवाई देखें। वह क्रिया या तो शिफ्ट, रिड्यूस, पूर्ण या त्रुटि है:

शिफ्ट एन:

मिलान किए गए टर्मिनल टी को पार्स स्टैक पर शिफ्ट करें और अगले इनपुट सिंबल को लुकहेड बफर में स्कैन करें।

अगली स्थिति n को नई वर्तमान स्थिति के रूप में पार्स स्टैक पर पुश करें।

आर कम करें_m: व्याकरण नियम प्रयुक्त करें आर_m: एलएचएस → एस₁ S₂ ... एस_L

पार्स स्टैक से मिलान किए गए सबसे ऊपरी एल सिम्बल (और ट्रीों और संबंधित राज्य संख्याओं को पार्स करें) को हटा दें।

यह पूर्व स्थिति p को उजागर करता है जो Lhs सिम्बल के उदाहरण की अपेक्षा कर रहा था।

एल पार्स ट्री को नए मूल सिम्बल एलएचएस के साथ पार्स ट्री के रूप में जोड़ें।

एलएचएस गोटो टेबल की पंक्ति पी और कॉलम एलएचएस से अगली स्थिति एन देखें।

पार्स स्टैक पर Lhs के लिए सिम्बल और ट्री को पुश करें।

अगली स्थिति n को नई वर्तमान स्थिति के रूप में पार्स स्टैक पर पुश करें।

लुकहेड और इनपुट स्ट्रीम अपरिवर्तित रहते हैं।

हो गया: लुकहेड टी ईओफ़ मार्कर है। पार्सिंग का अंत. यदि राज्य स्टैक में केवल प्रारंभ स्थिति रिपोर्ट सफलता है। अन्यथा, सिंटैक्स त्रुटि की रिपोर्ट करें.
त्रुटि: सिंटैक्स त्रुटि की रिपोर्ट करें। पार्सर समाप्त हो जाता है, या कुछ पुनर्प्राप्ति का प्रयास करता है।

एलआर पार्सर स्टैक आमतौर पर केवल एलआर (0) ऑटोमेटन राज्यों को संग्रहीत करता है, क्योंकि व्याकरण प्रतीकों को उनसे प्राप्त किया जा सकता है (ऑटोमेटन में, कुछ राज्य में सभी इनपुट संक्रमणों को ही प्रतीक के साथ चिह्नित किया जाता है, जो इस राज्य से जुड़ा प्रतीक है)। इसके अलावा, इन प्रतीकों की लगभग कभी भी आवश्यकता नहीं होती है क्योंकि पार्सिंग निर्णय लेते समय राज्य ही मायने रखता है।^[7]

एलआर जनरेटर विश्लेषण

लेख का यह भाग एलआर पार्सर जेनरेटर के अधिकांश उपयोगकर्ताओं द्वारा छोड़ा जा सकता है।

एलआर राज्य

उदाहरण पार्स तालिका में राज्य 2 आंशिक रूप से पार्स किए गए नियम के लिए है

r1: रकम → रकम + <बड़ा>•</बड़े>उत्पाद

इससे पता चलता है कि पार्सर यहां तक कैसे पहुंचा, फिर सम्स को देखकर + बड़े सम्स की तलाश करते हुए। <बड़ा>•</बड़ा>मार्कर नियम की शुरुआत से आगे बढ़ गया है। यह यह भी दर्शाता है कि कैसे पार्सर अंततः पूर्ण उत्पाद ढूंढकर नियम को पूरा करने की उम्मीद करता है। किन्तु उस उत्पाद के सभी हिस्सों को कैसे पार्स किया जाए, इस पर अधिक विवरण की आवश्यकता है।

किसी राज्य के लिए आंशिक रूप से पार्स किए गए नियमों को उसके मूल LR(0) आइटम कहा जाता है। पार्सर जनरेटर अपेक्षित उत्पादों के निर्माण में सभी संभावित अगले चरणों के लिए अतिरिक्त नियम या आइटम जोड़ता है:

r3: उत्पाद → <बड़ा>•उत्पाद * मूल्य

r4: उत्पाद → <बड़ा>•</बड़ा>मूल्य

r5: मान → <बड़ा>•इंट

r6: मान → <बड़ा>•</बड़ा>आईडी

<बड़ा>•</बड़ा>मार्कर इनमें से प्रत्येक जोड़े गए नियम की प्रारंभ में है; पार्सर ने अभी तक उनमें से किसी भी भाग की पुष्टि और विश्लेषण नहीं किया है। इन अतिरिक्त वस्तुओं को मुख्य वस्तुओं का समापन कहा जाता है। <बड़े> के शीघ्र बाद प्रत्येक नॉनटर्मिनल प्रतीक के लिए•, जनरेटर उस प्रतीक को परिभाषित करने वाले नियम जोड़ता है। यह और अधिक <बड़ा> जोड़ता है•</बड़े>मार्कर, और संभवतः विभिन्न अनुयायी प्रतीक। यह बंद करने की प्रक्रिया तब तक जारी रहती है जब तक कि सभी अनुयायी प्रतीकों का विस्तार नहीं हो जाता। राज्य 2 के लिए अनुयायी नॉनटर्मिनल्स उत्पादों से शुरू होते हैं। फिर बंद करके मूल्य जोड़ा जाता है। अनुयायी टर्मिनल int और id हैं।

कर्नेल और क्लोजर आइटम साथ वर्तमान स्थिति से भविष्य की स्थिति और पूर्ण वाक्यांशों तक आगे बढ़ने के सभी संभावित कानूनी विधि दिखाते हैं। यदि कोई अनुयायी प्रतीक केवल आइटम में दिखाई देता है, तो यह अगले राज्य की ओर ले जाता है जिसमें के साथ केवल मुख्य आइटम होता है•</बड़ा>मार्कर उन्नत। तो यह कोर के साथ अगले राज्य 8 की ओर ले जाता है

r5: मान → <बड़े> में•</बड़ा>

यदि एक ही अनुयायी प्रतीक कई वस्तुओं में दिखाई देता है, तो पार्सर अभी तक यह नहीं बता सकता है कि कौन सा नियम यहां लागू होता है। तो वह प्रतीक एक अगली स्थिति की ओर ले जाता है जो सभी शेष संभावनाओं को दिखाता है, फिर से <बड़े> के साथ•</बड़ा>मार्कर उन्नत। उत्पाद r1 और r3 दोनों में दिखाई देते हैं। तो उत्पाद कोर के साथ अगले राज्य 3 की ओर ले जाता है

r1: रकम → रकम + उत्पाद <बड़ा>•</बड़ा>

r3: उत्पाद → उत्पाद <बड़ा>•</बड़ा> *मूल्य

शब्दों में, इसका मतलब है कि यदि पार्सर ने एक ही उत्पाद देखा है, तो यह किया जा सकता है, या इसमें अभी भी एक साथ गुणा करने के लिए और भी चीजें हो सकती हैं। सभी मुख्य वस्तुओं में से पहले एक ही प्रतीक होता है•</बड़ा>मार्कर; इस अवस्था में सभी परिवर्तन हमेशा एक ही प्रतीक के साथ होते हैं।कुछ परिवर्तन कोर और राज्यों में होंगे जिनकी गणना पहले ही की जा चुकी है। अन्य परिवर्तन नए राज्यों की ओर ले जाते हैं। जनरेटर व्याकरण के लक्ष्य नियम से शुरू होता है। वहां से यह तब तक ज्ञात अवस्थाओं और संक्रमणों की खोज करता रहता है जब तक कि सभी आवश्यक अवस्थाएं नहीं मिल जातीं।

इन राज्यों को LR(0) राज्य कहा जाता है क्योंकि वे k=0 के लुकहेड का उपयोग करते हैं, यानी कोई लुकहेड नहीं। इनपुट प्रतीकों की एकमात्र जांच तब होती है जब प्रतीक को स्थानांतरित किया जाता है। कटौती के लिए लुकहेड्स की जांच पार्स तालिका द्वारा अलग से की जाती है, न कि गणना किए गए राज्यों द्वारा।

परिमित अवस्था मशीन

पार्स तालिका सभी संभावित LR(0) स्थितियों और उनके बदलावों का वर्णन करती है। वे एक परिमित राज्य ऑटोमेटन (एफएसएम) बनाते हैं। एफएसएम स्टैक का उपयोग किए बिना, सरल अननेस्टेड भाषाओं को पार्स करने के लिए एक सरल इंजन है। इस एलआर एप्लिकेशन में, एफएसएम की संशोधित इनपुट भाषा में टर्मिनल और नॉनटर्मिनल दोनों प्रतीक हैं, और पूर्ण एलआर पार्स के किसी भी आंशिक रूप से पार्स किए गए स्टैक स्नैपशॉट को कवर करता है।

पार्स चरण उदाहरण के चरण 5 को याद करें:

Step	Parse Stack _state Symbol _state ...	Look Ahead	Unscanned
5	₀ Products₄ ₅ int*₈	+	1

पार्स स्टैक राज्य संक्रमणों की एक श्रृंखला दिखाता है, प्रारंभिक स्थिति 0 से, स्थिति 4 तक और फिर 5 और वर्तमान स्थिति 8 तक। पार्स स्टैक पर प्रतीक उन संक्रमणों के लिए शिफ्ट या गोटो प्रतीक हैं। इसे देखने का दूसरा तरीका यह है कि परिमित राज्य मशीन स्ट्रीम प्रोडक्ट्स * int + 1 को स्कैन कर सकती है (किसी अन्य स्टैक का उपयोग किए बिना) और सबसे बाएं पूर्ण वाक्यांश को ढूंढ सकती है जिसे अगले कम किया जाना चाहिए। और वास्तव में यही इसका काम है!

एक मात्र एफएसएम ऐसा कैसे कर सकता है जब मूल अनपार्स्ड भाषा में नेस्टिंग और रिकर्सन है और निश्चित रूप से स्टैक के साथ एक विश्लेषक की आवश्यकता है? चाल यह है कि स्टैक शीर्ष के बाईं ओर की हर चीज़ पहले ही पूरी तरह से कम हो चुकी है। यह उन वाक्यांशों से सभी लूप और नेस्टिंग को समाप्त कर देता है। एफएसएम वाक्यांशों की सभी पुरानी शुरुआतों को अनदेखा कर सकता है, और केवल उन नवीनतम वाक्यांशों को ट्रैक कर सकता है जो आगे पूरे हो सकते हैं। एलआर सिद्धांत में इसके लिए अस्पष्ट नाम व्यवहार्य उपसर्ग है।

लुकहेड सेट

स्थितियाँ और परिवर्तन पार्स तालिका की शिफ्ट क्रियाओं और गोटो क्रियाओं के लिए सभी आवश्यक जानकारी देते हैं। जनरेटर को प्रत्येक कम कार्रवाई के लिए अपेक्षित लुकहेड सेट की गणना करने की भी आवश्यकता है।

एसएलआर पार्सर्स में, ये लुकहेड सेट अलग-अलग राज्यों और बदलावों पर विचार किए बिना सीधे व्याकरण से निर्धारित होते हैं। प्रत्येक नॉनटर्मिनल एस के लिए, एसएलआर जनरेटर सभी टर्मिनल प्रतीकों के सेट फॉलो (एस) पर काम करता है, जो तुरंत एस की कुछ घटनाओं का पालन कर सकता है। पार्स तालिका में, एस में प्रत्येक कमी फॉलो (एस) को अपने एलआर (1) के रूप में उपयोग करती है। ) लुकअहेड सेट। ऐसे फॉलो सेट का उपयोग जेनरेटर द्वारा एलएल टॉप-डाउन पार्सर्स के लिए भी किया जाता है। एक व्याकरण जिसमें फॉलो सेट का उपयोग करते समय कोई बदलाव/घटाव या विरोध कम/कम नहीं होता है, उसे एसएलआर व्याकरण कहा जाता है।

एलएएलआर पार्सर्स में एसएलआर पार्सर्स के समान ही स्थिति होती है, किन्तु प्रत्येक व्यक्तिगत स्थिति के लिए न्यूनतम आवश्यक कमी की संभावनाओं को पूरा करने के लिए अधिक जटिल, अधिक सटीक तरीके का उपयोग किया जाता है। व्याकरण के विवरण के आधार पर, यह एसएलआर पार्सर जनरेटर द्वारा गणना किए गए फॉलो सेट के समान हो सकता है, या यह एसएलआर लुकहेड्स का सबसेट बन सकता है। कुछ व्याकरण एलएएलआर पार्सर जनरेटर के लिए ठीक हैं किन्तु एसएलआर पार्सर जनरेटर के लिए नहीं। ऐसा तब होता है जब व्याकरण में फॉलो सेट का उपयोग करके विरोधाभासों को गलत बदलाव / कम या कम किया जाता है, किन्तु एलएएलआर जनरेटर द्वारा गणना किए गए सटीक सेटों का उपयोग करते समय कोई टकराव नहीं होता है। व्याकरण को तब LALR(1) कहा जाता है, किन्तु SLR नहीं।

एक एसएलआर या एलएएलआर पार्सर डुप्लिकेट स्थिति होने से बचाता है। किन्तु यह न्यूनतमकरण आवश्यक नहीं है, और कभी-कभी अनावश्यक पूर्वव्यापी टकराव पैदा कर सकता है। कैनोनिकल एलआर पार्सर्स नॉनटर्मिनल के उपयोग के बाएँ और दाएँ संदर्भ को बेहतर ढंग से याद रखने के लिए डुप्लिकेट (या स्प्लिट) स्थितियों का उपयोग करते हैं। व्याकरण में प्रतीक एस की प्रत्येक घटना को अपने स्वयं के लुकहेड सेट के साथ स्वतंत्र रूप से व्यवहार किया जा सकता है, ताकि कम करने वाले संघर्षों को हल करने में मदद मिल सके। यह कुछ और व्याकरणों को संभालता है। दुर्भाग्य से, यदि व्याकरण के सभी भागों के लिए ऐसा किया जाए तो यह पार्स तालिकाओं के आकार को बहुत बढ़ा देता है। कुछ गैर-टर्मिनलों की दो या अधिक नामित प्रतियां बनाकर, राज्यों का यह विभाजन किसी भी एसएलआर या एलएएलआर पार्सर के साथ मैन्युअल रूप से और चुनिंदा रूप से किया जा सकता है। एक व्याकरण जो एक कैनोनिकल एलआर जनरेटर के लिए संघर्ष-मुक्त है, किन्तु एलएएलआर जनरेटर में विरोधाभास है, उसे एलआर (1) कहा जाता है, किन्तु एलएएलआर (1) नहीं, और एसएलआर नहीं।

एसएलआर, एलएएलआर, और कैनोनिकल एलआर पार्सर बिल्कुल समान बदलाव करते हैं और इनपुट स्ट्रीम सही भाषा होने पर निर्णय कम करते हैं। जब इनपुट में सिंटैक्स त्रुटि होती है, तो एलएएलआर पार्सर कैनोनिकल एलआर पार्सर की तुलना में त्रुटि का पता लगाने से पहले कुछ अतिरिक्त (हानिरहित) कटौती कर सकता है। और एसएलआर पार्सर और भी अधिक कर सकता है। ऐसा इसलिए होता है क्योंकि एसएलआर और एलएएलआर पार्सर उस विशेष स्थिति के लिए वास्तविक, न्यूनतम लुकहेड प्रतीकों के लिए एक उदार सुपरसेट सन्निकटन का उपयोग कर रहे हैं।

सिंटेक्स त्रुटि पुनर्प्राप्ति

एलआर पार्सर किसी प्रोग्राम में पहली सिंटैक्स त्रुटि के लिए कुछ हद तक उपयोगी त्रुटि संदेश उत्पन्न कर सकते हैं, बस उन सभी टर्मिनल प्रतीकों की गणना करके जो अप्रत्याशित खराब लुकहेड प्रतीक के बजाय आगे दिखाई दे सकते थे। किन्तु इससे पार्सर को आगे, स्वतंत्र त्रुटियों को देखने के लिए इनपुट प्रोग्राम के शेष भाग को पार्स करने में मदद नहीं मिलती है। यदि पार्सर पहली त्रुटि से बुरी तरह से ठीक हो जाता है, तो यह बाकी सब चीजों को गलत तरीके से पार्स करने और अनुपयोगी नकली त्रुटि संदेशों का एक समूह उत्पन्न करने की बहुत संभावना है।

हाँ और बाइसन पार्सर जनरेटर में, पार्सर के पास वर्तमान कथन को छोड़ने, त्रुटि के आसपास कुछ पार्स किए गए वाक्यांशों और लुकहेड टोकन को त्यागने और अर्धविराम या ब्रेसिज़ जैसे कुछ विश्वसनीय कथन-स्तर सीमांकक पर पार्स को पुन: सिंक्रनाइज़ करने के लिए एक तदर्थ तंत्र है। यह अक्सर पार्सर और कंपाइलर को बाकी प्रोग्राम को देखने की अनुमति देने के लिए अच्छा काम करता है।

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

एलआर पार्सर्स के वेरिएंट

एलआर पार्सर जनरेटर यह तय करता है कि पार्सर स्थिति और लुकहेड प्रतीक के प्रत्येक संयोजन के लिए क्या होना चाहिए। ये निर्णय सामान्यतः केवल-पढ़ने योग्य डेटा तालिकाओं में बदल दिए जाते हैं जो एक सामान्य पार्सर लूप चलाते हैं जो व्याकरण- और राज्य-स्वतंत्र होता है। किन्तु उन निर्णयों को सक्रिय पार्सर में बदलने के अन्य तरीके भी हैं।

कुछ एलआर पार्सर जेनरेटर पार्स टेबल के बजाय प्रत्येक राज्य के लिए अलग-अलग अनुकूलित प्रोग्राम कोड बनाते हैं। ये पार्सर टेबल-संचालित पार्सर में सामान्य पार्सर लूप की तुलना में कई गुना तेज चल सकते हैं। सबसे तेज़ पार्सर जनरेट किए गए असेंबलर कोड का उपयोग करते हैं।

पुनरावर्ती एसेंट पार्सर भिन्नता में, स्पष्ट पार्स स्टैक संरचना को सबरूटीन कॉल द्वारा उपयोग किए गए अंतर्निहित स्टैक द्वारा भी प्रतिस्थापित किया जाता है। कटौती से सबरूटीन कॉल के कई स्तर समाप्त हो जाते हैं, जो अधिकांश भाषाओं में अनाड़ी है। इसलिए पुनरावर्ती आरोहण पार्सर आम तौर पर धीमे, कम स्पष्ट होते हैं, और पुनरावर्ती वंश पार्सर की तुलना में हाथ से संशोधित करना कठिन होता है।

एक अन्य भिन्नता प्रोलॉग जैसी गैर-प्रक्रियात्मक भाषाओं में पैटर्न-मिलान नियमों द्वारा पार्स तालिका को प्रतिस्थापित करती है।

जीएलआर सामान्यीकृत एलआर पार्सर केवल एक सही पार्स नहीं बल्कि इनपुट टेक्स्ट के सभी संभावित पार्स ढूंढने के लिए एलआर बॉटम-अप तकनीकों का उपयोग करते हैं। यह मानव भाषाओं जैसे अस्पष्ट व्याकरण के लिए आवश्यक है। एकाधिक वैध पार्स ट्रीों की गणना एक साथ की जाती है, बिना बैकट्रैकिंग के। जीएलआर कभी-कभी उन कंप्यूटर भाषाओं के लिए सहायक होता है जिन्हें संघर्ष-मुक्त एलएएलआर(1) व्याकरण द्वारा आसानी से वर्णित नहीं किया जा सकता है।

एलसी बायां कोना पार्सर वैकल्पिक व्याकरण नियमों के बाएं छोर को पहचानने के लिए एलआर बॉटम-अप तकनीकों का उपयोग करते हैं। जब विकल्पों को एक संभावित नियम तक सीमित कर दिया जाता है, तो पार्सर उस नियम के बाकी हिस्सों को पार्स करने के लिए टॉप-डाउन एलएल (1) तकनीकों पर स्विच करता है। एलसी पार्सर्स में एलएएलआर पार्सर्स की तुलना में छोटी पार्स टेबल और बेहतर त्रुटि निदान होता है। नियतात्मक एलसी पार्सर्स के लिए व्यापक रूप से उपयोग किए जाने वाले जनरेटर नहीं हैं। बहु-पार्स एलसी पार्सर बहुत बड़े व्याकरण वाली मानव भाषाओं में सहायक होते हैं।

सिद्धांत

एलआर पार्सर्स का आविष्कार डोनाल्ड नथ द्वारा 1965 में सरल पूर्ववर्ती पार्सर्स के कुशल सामान्यीकरण के रूप में किया गया था। नुथ ने साबित किया कि एलआर पार्सर सबसे सामान्य-उद्देश्य वाले पार्सर थे जो सबसे खराब मामलों में भी कुशल होंगे।^{[citation needed]}

एलआर (के) व्याकरण को स्ट्रिंग की लंबाई के आनुपातिक निष्पादन समय के साथ कुशलतापूर्वक पार्स किया जा सकता है।^[8]

प्रत्येक k≥1 के लिए, एक भाषा को LR(k) व्याकरण द्वारा उत्पन्न किया जा सकता है यदि और केवल यदि यह नियतात्मक [और संदर्भ-मुक्त] है, यदि और केवल यदि इसे LR(1) व्याकरण द्वारा उत्पन्न किया जा सकता है।^[9]

दूसरे शब्दों में, यदि कोई भाषा एक कुशल वन-पास पार्सर की अनुमति देने के लिए पर्याप्त उचित थी, तो इसे एलआर (के) व्याकरण द्वारा वर्णित किया जा सकता है। और उस व्याकरण को हमेशा यांत्रिक रूप से समकक्ष (किन्तु बड़े) एलआर(1) व्याकरण में बदला जा सकता है। तो एक एलआर (1) पार्सिंग विधि, सिद्धांत रूप में, किसी भी उचित भाषा को संभालने के लिए पर्याप्त शक्तिशाली थी। व्यवहार में, कई प्रोग्रामिंग भाषाओं के प्राकृतिक व्याकरण एलआर(1) के करीब हैं।^{[citation needed]}

नथ द्वारा वर्णित कैनोनिकल एलआर पार्सर्स में बहुत अधिक राज्य और बहुत बड़ी पार्स टेबलें थीं जो उस युग के कंप्यूटरों की सीमित मेमोरी के लिए अव्यवहारिक रूप से बड़ी थीं। एलआर पार्सिंग तब व्यावहारिक हो गई जब फ्रैंक डेरेमर ने बहुत कम राज्यों के साथ सरल एलआर पार्सर और एलएएलआर पार्सर का आविष्कार किया।^[10]^[11] एलआर सिद्धांत पर पूरी जानकारी के लिए और एलआर पार्सर व्याकरण से कैसे प्राप्त होते हैं, पार्सिंग, अनुवाद और संकलन का सिद्धांत, खंड 1 (अहो और उल्मन) देखें।^[7]^[2]अर्ली पार्सर्स तकनीक लागू करते हैं और <बड़ा>• मानव भाषाओं जैसे अस्पष्ट व्याकरणों के लिए सभी संभावित पार्स उत्पन्न करने के कार्य के लिए एलआर पार्सर्स का नोटेशन।

जबकि LR(k) व्याकरण में सभी k≥1 के लिए समान उत्पादक शक्ति होती है, LR(0) व्याकरण का मामला थोड़ा अलग है। कहा जाता है कि एक भाषा L में उपसर्ग गुण होता है यदि L में कोई भी शब्द L में किसी अन्य शब्द का उपसर्ग (औपचारिक भाषा) नहीं है।^[12] एक भाषा L में LR(0) व्याकरण होता है यदि और केवल तभी जब L उपसर्ग संपत्ति के साथ एक नियतात्मक संदर्भ-मुक्त भाषा हो।^[13] परिणामस्वरूप, एक भाषा L नियतात्मक संदर्भ-मुक्त है यदि और केवल यदि स्ट्रिंग्स के सेटों का संयोजन#संयोजन|L$ में एक LR(0) व्याकरण है, जहां $ L का प्रतीक नहीं है's वर्णमाला (औपचारिक भाषाएँ)।^[14]

अतिरिक्त उदाहरण 1+1

File:LR Parser.png

1+1 का निचला-ऊपर पार्स

एलआर पार्सिंग का यह उदाहरण लक्ष्य प्रतीक ई के साथ निम्नलिखित छोटे व्याकरण का उपयोग करता है:

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1

निम्नलिखित इनपुट को पार्स करने के लिए:

1 + 1

कार्रवाई और गोटो टेबल

इस व्याकरण के लिए दो LR(0) पार्सिंग तालिकाएँ इस प्रकार दिखती हैं:

state	action					goto
	*	+	0	1	$	E	B
0			s1	s2		3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2			7
6			s1	s2			8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

क्रिया तालिका को पार्सर की स्थिति और एक टर्मिनल (एक विशेष टर्मिनल $ सहित जो इनपुट स्ट्रीम के अंत को इंगित करता है) द्वारा अनुक्रमित किया जाता है और इसमें तीन प्रकार की क्रियाएं होती हैं:

शिफ्ट, जिसे एसएन के रूप में लिखा जाता है और इंगित करता है कि अगला राज्य एन है
कम करें, जिसे rm के रूप में लिखा जाता है और इंगित करता है कि व्याकरण नियम m के साथ कमी की जानी चाहिए
स्वीकार करें, जिसे एसीसी के रूप में लिखा जाता है और इंगित करता है कि पार्सर इनपुट स्ट्रीम में स्ट्रिंग को स्वीकार करता है।

गोटो तालिका को पार्सर की एक स्थिति और एक नॉनटर्मिनल द्वारा अनुक्रमित किया जाता है और बस यह इंगित करता है कि पार्सर की अगली स्थिति क्या होगी यदि उसने एक निश्चित नॉनटर्मिनल को पहचान लिया है। प्रत्येक कमी के बाद अगली स्थिति का पता लगाने के लिए यह तालिका महत्वपूर्ण है। कमी के बाद, अगली स्थिति स्टैक के शीर्ष (यानी वर्तमान स्थिति) और कम किए गए नियम के एलएचएस (यानी गैर-टर्मिनल) के लिए गोटो तालिका प्रविष्टि को देखकर पाई जाती है।

पार्सिंग चरण

नीचे दी गई तालिका प्रक्रिया के प्रत्येक चरण को दर्शाती है। यहां स्थिति स्टैक के शीर्ष पर स्थित तत्व (सबसे दाहिनी ओर वाला तत्व) को संदर्भित करती है, और अगली कार्रवाई उपरोक्त क्रिया तालिका के संदर्भ में निर्धारित की जाती है। स्ट्रीम के अंत को दर्शाने के लिए इनपुट स्ट्रिंग में एक $ जोड़ा जाता है।

State	Input stream	Output stream	Stack	Next action
0	1+1$		[0]	Shift 2
2	+1$		[0,2]	Reduce 5
4	+1$	5	[0,4]	Reduce 3
3	+1$	5,3	[0,3]	Shift 6
6	1$	5,3	[0,3,6]	Shift 2
2	$	5,3	[0,3,6,2]	Reduce 5
8	$	5,3,5	[0,3,6,8]	Reduce 2
3	$	5,3,5,2	[0,3]	Accept

पूर्वाभ्यास

पार्सर केवल प्रारंभिक स्थिति ('0') वाले स्टैक से शुरू होता है:

[0]

इनपुट स्ट्रिंग से पहला प्रतीक जो पार्सर देखता है वह '1' है। अगली क्रिया (शिफ्ट, कम, स्वीकार या त्रुटि) खोजने के लिए, क्रिया तालिका को वर्तमान स्थिति (वर्तमान स्थिति स्टैक के शीर्ष पर जो कुछ भी है) के साथ अनुक्रमित किया जाता है, जो इस मामले में 0 है, और वर्तमान इनपुट प्रतीक, जो '1' है। क्रिया तालिका स्थिति 2 में बदलाव को निर्दिष्ट करती है, और इसलिए स्थिति 2 को स्टैक पर धकेल दिया जाता है (फिर से, राज्य की सभी जानकारी स्टैक में होती है, इसलिए स्थिति 2 में स्थानांतरित करना स्टैक पर 2 को धकेलने के समान है)। परिणामी स्टैक है

[0 '1' 2]

जहां स्टैक का शीर्ष 2 है। समझाने के लिए प्रतीक (उदाहरण के लिए, '1', बी) दिखाया गया है जो अगले राज्य में संक्रमण का कारण बनता है, हालांकि सख्ती से कहें तो यह स्टैक का हिस्सा नहीं है।

स्थिति 2 में, क्रिया तालिका व्याकरण नियम 5 के साथ कम करने के लिए कहती है (भले ही पार्सर इनपुट स्ट्रीम पर कौन सा टर्मिनल देखता है), जिसका अर्थ है कि पार्सर ने नियम 5 के दाईं ओर को पहचान लिया है। इस मामले में, पार्सर आउटपुट स्ट्रीम में 5 लिखता है, स्टैक से एक स्थिति को पॉप करता है (क्योंकि नियम के दाईं ओर एक प्रतीक है), और राज्य 0 और बी के लिए गोटो तालिका में सेल से राज्य को स्टैक पर धकेलता है, यानी, राज्य 4। परिणामी स्टैक है:

[0 बी 4]

हालाँकि, राज्य 4 में, क्रिया तालिका कहती है कि पार्सर को अब नियम 3 के साथ कम करना चाहिए। इसलिए यह आउटपुट स्ट्रीम में 3 लिखता है, स्टैक से एक राज्य को पॉप करता है, और राज्य 0 और ई के लिए गोटो तालिका में नया राज्य ढूंढता है, जो राज्य 3 है। परिणामी स्टैक:

[0 ई 3]

अगला टर्मिनल जो पार्सर देखता है वह '+' है और क्रिया तालिका के अनुसार इसे राज्य 6 पर जाना चाहिए:

[0 ई 3 '+' 6]

परिणामी स्टैक की व्याख्या एक परिमित राज्य ऑटोमेटन के इतिहास के रूप में की जा सकती है जिसने अभी-अभी एक नॉनटर्मिनल ई पढ़ा है और उसके बाद एक टर्मिनल '+' लिखा है। इस ऑटोमेटन की संक्रमण तालिका को एक्शन टेबल में शिफ्ट क्रियाओं और गोटो टेबल में गोटो क्रियाओं द्वारा परिभाषित किया गया है।

अगला टर्मिनल अब '1' है और इसका मतलब है कि पार्सर एक बदलाव करता है और राज्य 2 पर जाता है:

[0 ई 3 '+' 6 '1' 2]

पिछले '1' की तरह ही इसे भी घटाकर बी कर दिया गया है, जिससे निम्नलिखित स्टैक प्राप्त होता है:

[0 ई 3 '+' 6 बी 8]

स्टैक एक परिमित ऑटोमेटन के राज्यों की एक सूची से मेल खाता है जिसने एक नॉनटर्मिनल ई पढ़ा है, उसके बाद '+' और फिर एक नॉनटर्मिनल बी। राज्य 8 में पार्सर हमेशा नियम 2 के साथ कम करता है। स्टैक पर शीर्ष 3 राज्य नियम 2 के दाईं ओर 3 प्रतीकों के अनुरूप हैं। इस बार हम स्टैक से 3 तत्वों को हटाते हैं (चूंकि नियम के दाईं ओर 3 प्रतीक हैं) और ई और 0 के लिए गोटो स्थिति को देखते हैं, इस प्रकार राज्य 3 को स्टैक पर वापस धकेलना

[0 ई 3]

अंत में, पार्सर इनपुट स्ट्रीम से '$' (इनपुट प्रतीक का अंत) पढ़ता है, जिसका अर्थ है कि क्रिया तालिका (वर्तमान स्थिति 3 है) के अनुसार पार्सर इनपुट स्ट्रिंग को स्वीकार करता है। नियम संख्याएँ जो तब आउटपुट स्ट्रीम पर लिखी गई होंगी, [5, 3, 5, 2] होंगी जो वास्तव में स्ट्रिंग 1 + 1 की सबसे दाईं ओर उलटी व्युत्पत्ति है।

एलआर(0) पार्सिंग तालिकाओं का निर्माण

आइटम

इन पार्सिंग तालिकाओं का निर्माण एलआर (0) आइटम (बस यहां आइटम कहा जाता है) की धारणा पर आधारित है जो कि व्याकरण के नियम हैं जिनमें दाईं ओर कहीं एक विशेष बिंदु जोड़ा गया है। उदाहरण के लिए, नियम E → E + B में निम्नलिखित चार संगत आइटम हैं:

E → • E + B
E → E • + B
E → E + • B
E → E + B •

फॉर्म ए → ε के नियमों में केवल एक आइटम ए → <बड़ा> है•</बड़ा>. आइटम E → E <बड़ा>•</बड़ा>उदाहरण के लिए, + बी इंगित करता है कि पार्सर ने इनपुट स्ट्रीम पर ई के अनुरूप एक स्ट्रिंग को पहचान लिया है और अब '+' को पढ़ने की उम्मीद करता है जिसके बाद बी के अनुरूप एक और स्ट्रिंग आती है।

आइटम सेट

आम तौर पर किसी आइटम के साथ पार्सर की स्थिति को चिह्नित करना संभव नहीं है क्योंकि यह पहले से नहीं जानता होगा कि यह कमी के लिए किस नियम का उपयोग करने जा रहा है। उदाहरण के लिए, यदि कोई नियम E → E * B भी है तो आइटम E → E <बड़ा>•</बड़ा> + बी और ई → ई <बड़ा>• * E से संबंधित स्ट्रिंग पढ़ने के बाद B दोनों लागू होंगे। इसलिए, वस्तुओं के सेट द्वारा पार्सर की स्थिति को चिह्नित करना सुविधाजनक है, इस मामले में सेट { E → E •</बड़ा> + बी, ई → ई <बड़ा>•</बड़ा>*बी }.

गैर-टर्मिनलों के विस्तार द्वारा आइटम सेट का विस्तार

नॉनटर्मिनल से पहले बिंदु वाला आइटम, जैसे कि E → E + <बड़ा>•</बिग>बी, इंगित करता है कि पार्सर अगले नॉनटर्मिनल बी को पार्स करने की उम्मीद करता है। यह सुनिश्चित करने के लिए कि आइटम सेट में सभी संभावित नियम शामिल हैं, पार्सर पार्सिंग के बीच में हो सकता है, इसमें सभी आइटम शामिल होने चाहिए जो बताते हैं कि बी को कैसे पार्स किया जाएगा। इसका मतलब यह है कि यदि बी → 1 और बी → 0 जैसे नियम हैं तो आइटम सेट में आइटम बी → <बड़ा> भी शामिल होना चाहिए•</बड़ा>1 और बी → <बड़ा>•0. सामान्य तौर पर इसे इस प्रकार तैयार किया जा सकता है:

यदि फॉर्म ए → वी <बिग> का कोई आइटम है•आइटम सेट में बीडब्ल्यू और व्याकरण में बी → डब्ल्यू' फॉर्म का नियम है तो आइटम बी → <बिग>•आइटम सेट में 'w' भी होना चाहिए।

आइटम सेट को बंद करना

इस प्रकार, वस्तुओं के किसी भी सेट को सभी उपयुक्त वस्तुओं को पुनरावर्ती रूप से जोड़कर बढ़ाया जा सकता है जब तक कि डॉट्स से पहले के सभी गैर-टर्मिनलों का हिसाब नहीं दिया जाता है। न्यूनतम विस्तार को आइटम सेट का समापन कहा जाता है और इसे 'क्लोज़' (I) के रूप में लिखा जाता है जहां I आइटम सेट है। यह ये बंद आइटम सेट हैं जिन्हें पार्सर की स्थिति के रूप में लिया जाता है, हालांकि केवल वे चीजें जो वास्तव में शुरुआती स्थिति से पहुंच योग्य हैं उन्हें तालिकाओं में शामिल किया जाएगा।

संवर्धित व्याकरण

विभिन्न अवस्थाओं के बीच परिवर्तन निर्धारित करने से पहले, व्याकरण को अतिरिक्त नियम के साथ संवर्धित किया जाता है

(0) एस → ई इओफ़

जहां S नई शुरुआत का प्रतीक है और E पुराना शुरुआत का प्रतीक है। पार्सर इस नियम का उपयोग कटौती के लिए ठीक उसी समय करेगा जब उसने संपूर्ण इनपुट स्ट्रिंग को स्वीकार कर लिया हो।

इस उदाहरण के लिए, ऊपर जैसा ही व्याकरण इस प्रकार संवर्धित किया गया है:

(0) एस → ई इओफ़

(1) ई → ई * बी

(2) ई → ई + बी

(3) ई → बी

(4) बी → 0

(5) बी → 1

यह इस संवर्धित व्याकरण के लिए है कि आइटम सेट और उनके बीच के बदलाव निर्धारित किए जाएंगे।

टेबल निर्माण

पहुंच योग्य आइटम सेट और उनके बीच संक्रमण ढूँढना

तालिकाओं के निर्माण के पहले चरण में बंद आइटम सेटों के बीच संक्रमण का निर्धारण करना शामिल है। ये परिवर्तन ऐसे निर्धारित किए जाएंगे जैसे कि हम सीमित ऑटोमेटन पर विचार कर रहे हैं जो टर्मिनलों के साथ-साथ गैर-टर्मिनलों को भी पढ़ सकता है। इस ऑटोमेटन की आरंभिक स्थिति हमेशा जोड़े गए नियम के पहले आइटम का समापन है: S → <बड़ा>•ई ईओएफ:

आइटम सेट 0

एस → <बड़ा>•ई इओफ़

+ ई → <बड़ा>•ई*बी

+ ई → <बड़ा>•</बिग>ई+बी

+ ई → <बड़ा>•</बिग>बी

+ बी → <बड़ा>•</बड़ा>0

+ बी → <बड़ा>•</बड़ा>1

किसी आइटम के सामने बोल्ड अक्षरों + उन आइटम को इंगित करता है जो क्लोजर के लिए जोड़े गए थे (गणितीय '+' ऑपरेटर के साथ भ्रमित न हों जो टर्मिनल है)। + के बिना मूल आइटम को आइटम सेट का कर्नेल कहा जाता है।

आरंभिक अवस्था (S0) से शुरू करके, इस अवस्था से जिन सभी अवस्थाओं तक पहुंचा जा सकता है, वे सभी अब निर्धारित हो गए हैं। किसी आइटम सेट के लिए संभावित बदलाव बिंदुओं के बाद पाए जाने वाले प्रतीकों (टर्मिनलों और गैर-टर्मिनलों) को देखकर पाया जा सकता है; आइटम सेट 0 के मामले में वे प्रतीक टर्मिनल '0' और '1' और नॉनटर्मिनल ई और बी हैं। आइटम सेट को खोजने के लिए प्रत्येक प्रतीक ${\textstyle x\in \{0,1,E,B\}}$ प्रत्येक प्रतीक के लिए निम्नलिखित प्रक्रिया का पालन किया जाता है:

वर्तमान आइटम सेट में सभी आइटमों का सबसेट, एस, लें जहां रुचि के प्रतीक, एक्स के सामने बिंदु है।
S में प्रत्येक आइटम के लिए, बिंदु को x के दाईं ओर ले जाएं।
आइटम के परिणामी सेट को बंद करें.

टर्मिनल '0' के लिए (अर्थात जहां x = '0') इसका परिणाम यह होगा:

'आइटम सेट 1'

बी → 0 <बड़ा>•</बड़ा>

और टर्मिनल '1' के लिए (अर्थात जहां x = '1') इसका परिणाम यह होगा:

आइटम सेट 2

बी → 1 <बड़ा>•</बड़ा>

और नॉनटर्मिनल E के लिए (अर्थात जहां x = E) इसका परिणाम यह होता है:

आइटम सेट 3

एस → ई <बड़ा>•ईओएफ

ई → ई <बड़ा>•</बड़ा>* बी

ई → ई <बड़ा>•</बिग>+बी

और नॉनटर्मिनल बी के लिए (यानी जहां x = बी) इसका परिणाम यह होता है:

आइटम सेट 4

ई → बी <बड़ा>•</बड़ा>

क्लोजर सभी मामलों में नए आइटम नहीं जोड़ता है - उदाहरण के लिए, ऊपर दिए गए नए सेट में, डॉट के बाद कोई नॉनटर्मिनल नहीं है।

उपरोक्त प्रक्रिया तब तक जारी रहती है जब तक कोई नया आइटम सेट नहीं मिल जाता। आइटम सेट 1, 2, और 4 के लिए कोई बदलाव नहीं होगा क्योंकि बिंदु किसी प्रतीक के सामने नहीं है। हालाँकि आइटम सेट 3 के लिए, हमारे पास टर्मिनल '*' और '+' के सामने बिंदु हैं। प्रतीक के लिए ${\textstyle x={\texttt {*}}}$ संक्रमण यहाँ जाता है:

आइटम सेट 5

ई → ई * <बड़ा>•</बिग>बी

+ बी → <बड़ा>•</बड़ा>0

+ बी → <बड़ा>•</बड़ा>1

और के लिए ${\textstyle x={\texttt {+}}}$ संक्रमण यहाँ जाता है:

आइटम सेट 6

ई → ई + <बड़ा>•</बिग>बी

+ बी → <बड़ा>•</बड़ा>0

+ बी → <बड़ा>•</बड़ा>1

अब, तीसरी पुनरावृत्ति शुरू होती है।

आइटम सेट 5 के लिए, टर्मिनल '0' और '1' और नॉनटर्मिनल बी पर विचार किया जाना चाहिए, किन्तु परिणामी बंद आइटम सेट क्रमशः पहले से पाए गए आइटम सेट 1 और 2 के बराबर हैं। नॉनटर्मिनल बी के लिए, संक्रमण इस प्रकार है:

आइटम सेट 7

ई → ई * बी <बड़ा>•</बड़ा>

आइटम सेट 6 के लिए, टर्मिनल '0' और '1' और नॉनटर्मिनल बी पर विचार किया जाना चाहिए, किन्तु पहले की तरह, टर्मिनलों के लिए परिणामी आइटम सेट पहले से पाए गए आइटम सेट 1 और 2 के बराबर हैं। नॉनटर्मिनल बी के लिए संक्रमण इस प्रकार है:

आइटम सेट 8

ई → ई + बी <बड़ा>•</बड़ा>

इन अंतिम आइटम सेट 7 और 8 में उनके बिंदुओं से परे कोई प्रतीक नहीं है, इसलिए कोई और नया आइटम सेट नहीं जोड़ा गया है, इसलिए आइटम बनाने की प्रक्रिया पूरी हो गई है। परिमित ऑटोमेटन, आइटम सेट के साथ उसकी अवस्थाओं को नीचे दिखाया गया है।

ऑटोमेटन के लिए संक्रमण तालिका अब इस प्रकार दिखती है:

Item Set	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

कार्रवाई और गोटो तालिकाओं का निर्माण

इस तालिका और पाए गए आइटम सेट से, क्रिया और गोटो तालिका निम्नानुसार बनाई गई है:

# नॉनटर्मिनल्स के कॉलम को गोटो टेबल में कॉपी किया जाता है।

टर्मिनलों के कॉलम को शिफ्ट क्रियाओं के रूप में एक्शन टेबल पर कॉपी किया जाता है।
क्रिया तालिका में '$' (इनपुट का अंत) के लिए अतिरिक्त कॉलम जोड़ा गया है। प्रत्येक आइटम सेट के लिए '$' कॉलम में एसीसी कार्रवाई जोड़ी जाती है जिसमें फॉर्म एस → डब्ल्यू <बड़ा> का आइटम होता है•ईओएफ.
यदि किसी आइटम सेट i में फॉर्म A → w का आइटम शामिल है•</बड़ा>और ए → डब्ल्यू, एम > 0 के साथ नियम एम है तो एक्शन टेबल में स्थिति आई के लिए पंक्ति पूरी तरह से कम एक्शन आरएम से भरी हुई है।पाठक यह सत्यापित कर सकते हैं कि ये चरण पहले प्रस्तुत की गई क्रिया और गोटो तालिका उत्पन्न करते हैं।

एलआर(0) बनाम एसएलआर और एलएएलआर पार्सिंग के बारे में एक नोट

उपरोक्त प्रक्रिया का केवल चरण 4 ही कम करने वाली क्रियाएं उत्पन्न करता है, और इसलिए सभी कम करने वाली क्रियाओं को पूरी तालिका पंक्ति पर कब्जा करना चाहिए, जिससे इनपुट स्ट्रीम में अगले प्रतीक की परवाह किए बिना कमी हो सकती है। यही कारण है कि ये एलआर (0) पार्स टेबल हैं: वे यह तय करने से पहले कि कौन सा कटौती करना है, कोई भी लुक-आगे नहीं देखते हैं (अर्थात, वे शून्य प्रतीकों को देखते हैं)। एक व्याकरण जिसे कटौती को स्पष्ट करने के लिए आगे देखने की आवश्यकता है, उसे अलग-अलग कॉलम में अलग-अलग कम करने वाली क्रियाओं वाली एक पार्स तालिका पंक्ति की आवश्यकता होगी, और उपरोक्त प्रक्रिया ऐसी पंक्तियों को बनाने में सक्षम नहीं है। एलआर (0) तालिका निर्माण प्रक्रिया (जैसे कि सरल एलआर पार्सर और एलएएलआर पार्सर) के परिशोधन उन कम क्रियाओं का निर्माण करने में सक्षम हैं जो पूरी पंक्तियों पर कब्जा नहीं करते हैं। इसलिए, वे एलआर(0) पार्सर्स की तुलना में अधिक व्याकरणों को पार्स करने में सक्षम हैं।

निर्मित तालिकाओं में संघर्ष

ऑटोमेटन का निर्माण इस तरह से किया गया है कि इसके नियतात्मक होने की गारंटी है। हालाँकि, जब कार्रवाई तालिका में कम क्रियाएं जोड़ी जाती हैं तो ऐसा हो सकता है कि एक ही सेल एक कम कार्रवाई और एक शिफ्ट कार्रवाई (एक शिफ्ट-कम संघर्ष) या दो अलग-अलग कम क्रियाओं (एक कम-कम संघर्ष) से भरा हो। हालाँकि, यह दिखाया जा सकता है कि जब ऐसा होता है तो व्याकरण LR(0) व्याकरण नहीं है। शिफ्ट-रिड्यूस संघर्ष का एक क्लासिक वास्तविक दुनिया का उदाहरण लटकती हुई अन्य समस्या है।

शिफ्ट-रिड्यूस संघर्ष के साथ गैर-एलआर (0) व्याकरण का एक छोटा सा उदाहरण है:

(1) ई → 1 ई

(2) ई → 1

पाए गए आइटम सेटों में से एक है:

'आइटम सेट 1'

ई → 1 <बड़ा>•</बड़े>ई

ई → 1 <बड़ा>•</बड़ा>

+ ई → <बड़ा>•</बड़ा>1 ई

+ ई → <बड़ा>•</बड़ा>1

इस आइटम सेट में एक शिफ्ट-रिड्यूस संघर्ष है: उपरोक्त नियमों के अनुसार एक्शन टेबल का निर्माण करते समय, [आइटम सेट 1, टर्मिनल '1'] के लिए सेल में एस1 (स्टेट 1 में शिफ्ट) और आर2 (व्याकरण के साथ कम करें) होता है। नियम 2).

कम-कम करने वाले संघर्ष के साथ गैर-एलआर (0) व्याकरण का एक छोटा सा उदाहरण है:

(1) ई → ए 1

(2) ई → बी 2

(3) ए → 1

(4) बी → 1

इस स्थिति में निम्नलिखित आइटम सेट प्राप्त होता है:

Item set 1
A → 1 •
B → 1 •

इस आइटम सेट में एक कम-कम करने वाला संघर्ष है क्योंकि इस आइटम सेट के लिए क्रिया तालिका में कक्षों में नियम 3 के लिए एक कम कार्रवाई और नियम 4 के लिए एक दोनों कार्रवाई होगी।

ऊपर दिए गए दोनों उदाहरणों को यह तय करने के लिए पार्सर को नॉनटर्मिनल ए के फॉलो सेट (एलएल पार्सर देखें) का उपयोग करने की अनुमति देकर हल किया जा सकता है कि क्या वह कमी के लिए एएस नियमों में से किसी एक का उपयोग करने जा रहा है; यह कटौती के लिए केवल नियम ए → डब्ल्यू का उपयोग करेगा यदि इनपुट स्ट्रीम पर अगला प्रतीक ए के अनुवर्ती सेट में है। इस समाधान के परिणामस्वरूप तथाकथित सरल एलआर पार्सर होते हैं।

यह भी देखें

कैनोनिकल एलआर पार्सर
एसएलआर व्याकरण
एलएएलआर पार्सर|लुक-अहेड एलआर
जीएलआर पार्सर

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Knuth, D. E. (July 1965). "लैंग्वेज के बाएँ से दाएँ अनुवाद पर". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
↑ ^2.0 ^2.1 Aho, Alfred V.; Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (Repr. ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 978-0139145568.
↑ Language theoretic comparison of LL and LR grammars
↑ Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon, Morgan Kaufmann 2011.
↑ Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.
↑ Flex & Bison: Text Processing Tools, by John Levine, O'Reilly Media 2009.
↑ ^7.0 ^7.1 Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.
↑ Knuth (1965), p.638
↑ Knuth (1965), p.635. Knuth didn't mention the restriction k≥1 there, but it is required by his theorems he referred to, viz. on p.629 and p.630. Similarly, the restriction to context-free languages is tacitly understood from the context.
↑ 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.
↑ Hopcroft, John E.; Ullman, Jeffrey D. (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Addison-Wesley. ISBN 0-201-02988-X. Here: Exercise 5.8, p.121.
↑ Hopcroft, Ullman (1979), Theorem 10.12, p.260
↑ Hopcroft, Ullman (1979), Corollary p.260

अग्रिम पठन

Chapman, Nigel P., LR Parsing: Theory and Practice, Cambridge University Press, 1987. ISBN 0-521-30413-X
Pager, D., A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977)
"Compiler Construction: Principles and Practice" by Kenneth C. Louden. ISBN 0-534-939724

बाहरी संबंध

dickgrune.com, Parsing Techniques - A Practical Guide 1st Ed. web page of book includes downloadable pdf.
Parsing Simulator This simulator is used to generate parsing tables LR and to resolve the exercises of the book
Internals of an LALR(1) parser generated by GNU Bison - Implementation issues
Course notes on LR parsing
Shift-reduce and Reduce-reduce conflicts in an LALR parser
A LR parser example
Practical LR(k) Parser Construction
The Honalee LR(k) Algorithm

[Knuth_1965-1] 1.0 ^1.1 ^1.2 Knuth, D. E. (July 1965). "लैंग्वेज के बाएँ से दाएँ अनुवाद पर". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.

[AhoUllman_1972-2] 2.0 ^2.1 Aho, Alfred V.; Ullman, Jeffrey D. (1972). The Theory of Parsing, Translation, and Compiling (Volume 1: Parsing.) (Repr. ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN 978-0139145568.

[3] Language theoretic comparison of LL and LR grammars

[4] Engineering a Compiler (2nd edition), by Keith Cooper and Linda Torczon, Morgan Kaufmann 2011.

[5] Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.

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

[Compilers_2006-7] 7.0 ^7.1 Compilers: Principles, Techniques, and Tools (2nd Edition), by Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, Prentice Hall 2006.

[8] Knuth (1965), p.638

[9] Knuth (1965), p.635. Knuth didn't mention the restriction k≥1 there, but it is required by his theorems he referred to, viz. on p.629 and p.630. Similarly, the restriction to context-free languages is tacitly understood from the context.

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

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

[12] Hopcroft, John E.; Ullman, Jeffrey D. (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Addison-Wesley. ISBN 0-201-02988-X. Here: Exercise 5.8, p.121.

[13] Hopcroft, Ullman (1979), Theorem 10.12, p.260

[14] Hopcroft, Ullman (1979), Corollary p.260

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 29: / Line 29: @@
 ===बॉटम-अप पार्स स्टैक===
 [[File:Bottom-Up Parser.svg|thumb|x250px|दाएं|चरण 6 पर बॉटम-अप पार्सर]]अन्य शिफ्ट-रिड्यूस पार्सर्स की तरह, एलआर पार्सर तब तक प्रतीक्षा  करता है जब तक कि वह संयुक्त निर्माण के लिए प्रतिबद्ध होने से पूर्व  कुछ निर्माण के सभी भागो  को स्कैन और पार्स नहीं करता है। फिर पार्सर किसी और प्रतीक्षा के अतिरिक्त संयोजन पर शीघ्र  कार्य करता है। और पार्स ट्री उदाहरण में, जैसे ही लुकआहेड * दिखाई देता है, चरण 1-3 में वाक्यांश ए वैल्यू में और फिर उत्पादों में कम हो जाता है, अतः पार्स ट्री के उन भागो को व्यवस्थित करने के लिए पश्चात  में प्रतीक्षा करने के अतिरिक्त कार्य करता है। चूंकि ए को कैसे संभालना है इसका निर्णय केवल उस पर आधारित है जो पार्सर और स्कैनर ने पहले ही देखा है, उन वस्तु  पर विचार किए बिना जो दाईं ओर में  पुनः दिखाई देती हैं।
   इस प्रकार से कटौती सामान्य वर्तमान  में पार्स की गई वस्तु  को पुनर्गठित करती है, लुकहेड सिम्बल  के शीघ्र  बाईं ओर है । तब  पुनः से ही पार्स की गई वस्तु की सूची [[स्टैक (सार डेटा प्रकार)]] की तरह कार्य  करती है। यह पार्स स्टैक दाईं ओर बढ़ता है। और स्टैक का आधार या सतह  बायीं ओर है और सामान्य से  बायीं ओर, अधिक ओल्ड  पार्स टुकड़ा रखता है। प्रत्येक कटौती चरण केवल सामान्य दाहिने, नवीनतम पार्स अंशों पर कार्य करता है। (यह संचयी पार्स स्टैक [[ऊपर से नीचे पार्सर]] द्वारा उपयोग किए जाने वाले पूर्वानुमानित, बाईं ओर बढ़ने वाले पार्स स्टैक से अधिक अलग है।)
@@ Line 70: / Line 70: @@
 चरण 6 अनेक भागों के साथ व्याकरण नियम प्रयुक्त करता है:
 : उत्पाद → उत्पाद * मूल्य
 यह पार्स किए गए सिटैक्स को रखने वाले स्टैक टॉप से मेल खाता है ... उत्पाद * मान। कम करने का चरण नियम के दाईं ओर के इस उदाहरण को प्रतिस्थापित करता है, उत्पाद * मान को नियम के बाईं ओर के सिम्बल से, यहां उच्च  उत्पाद है। यदि पार्सर पूर्ण पार्स ट्री बनाता है, तो आंतरिक उत्पादों के लिए तीन ट्री, *, और मान को उत्पादों के लिए नवीन  ट्री  की रूट  से जोड़ दिया जाता है। अन्यथा, आंतरिक उत्पादों और मान से सिमेंटिक्स#प्रोग्रामिंग लैंग्वेज का विवरण के पश्चात  कंपाइलर पास में आउटपुट होता है, या नए उत्पाद सिम्बल में संयुक्त और सहेजा जाता है।<ref>
 Crafting and Compiler, by Charles Fischer, Ron Cytron, and Richard LeBlanc, Addison Wesley 2009.</ref>
 ===एलआर पार्स चरण उदाहरण के लिए ए*2 + 1 ===
@@ Line 224: / Line 224: @@
 उपरोक्त स्थिति 2 में, पार्सर ने अभी-अभी व्याकरण नियम का + पाया और स्थानांतरित किया है
 ::r1: सम्स → सम्स+ <बड़ा>{{color|#f7f|•}}</बड़े>उत्पाद
 अगला अपेक्षित वाक्यांश उत्पाद है। उत्पाद टर्मिनल सिम्बल  int या id से प्रारंभ  होते हैं। यदि लुकआहेड इनमें से कोई है, तो पार्सर उन्हें स्थानांतरित कर देता है और क्रमशः 8 या 9 स्थिति में ले जाता है। जब कोई उत्पाद मिल जाता है, तो पार्सर सारांश की पूर्ण  सूची जमा करने और नियम r0 का अंत खोजने के लिए अवस्था 3 पर आगे बढ़ता है। उत्पाद नॉनटर्मिनल वैल्यू से भी प्रारंभ  हो सकता है। किसी अन्य लुकअहेड या नॉनटर्मिनल के लिए, पार्सर सिंटैक्स त्रुटि की घोषणा करता है।
 राज्य 3 में, पार्सर को अभी उत्पाद वाक्यांश मिला है, जो दो संभावित व्याकरण नियमों से हो सकता है:
@@ Line 244: / Line 244: @@
 ::अगली स्थिति n को नई वर्तमान स्थिति के रूप में पार्स स्टैक पर पुश करें।
 *आर कम करें<sub>m</sub>: व्याकरण नियम प्रयुक्त  करें आर<sub>m</sub>: एलएचएस → एस<sub>1</sub> S<sub>2</sub> ... एस<sub>L</sub>
-::पार्स स्टैक से मिलान किए गए सबसे ऊपरी एल सिम्बल (और पेड़ों और संबंधित राज्य संख्याओं को पार्स करें) को हटा दें।
+::पार्स स्टैक से मिलान किए गए सबसे ऊपरी एल सिम्बल (और ट्रीों और संबंधित राज्य संख्याओं को पार्स करें) को हटा दें।
 ::यह पूर्व स्थिति p को उजागर करता है जो Lhs सिम्बल के उदाहरण की अपेक्षा कर रहा था।
-::एल पार्स ट्री  को नए मूल सिम्बल एलएचएस के साथ पार्स पेड़ के रूप में जोड़ें।
+::एल पार्स ट्री  को नए मूल सिम्बल एलएचएस के साथ पार्स ट्री के रूप में जोड़ें।
 ::एलएचएस गोटो टेबल  की पंक्ति पी और कॉलम एलएचएस से अगली स्थिति एन देखें।
-::पार्स स्टैक पर Lhs के लिए सिम्बल और पेड़ को पुश करें।
+::पार्स स्टैक पर Lhs के लिए सिम्बल और ट्री को पुश करें।
 ::अगली स्थिति n को नई वर्तमान स्थिति के रूप में पार्स स्टैक पर पुश करें।
 ::लुकहेड और इनपुट स्ट्रीम अपरिवर्तित रहते हैं।
@@ Line 263: / Line 263: @@
 उदाहरण पार्स तालिका में राज्य 2 आंशिक रूप से पार्स किए गए नियम के लिए है
 ::r1: रकम → रकम + <बड़ा>{{color|#f7f|•}}</बड़े>उत्पाद
-इससे पता चलता है कि पार्सर यहां तक कैसे पहुंचा, फिर सम्स को देखकर + बड़े सम्स की तलाश करते हुए। <बड़ा>{{color|#f7f|•}}</बड़ा>मार्कर नियम की शुरुआत से आगे बढ़ गया है। यह यह भी दर्शाता है कि कैसे पार्सर अंततः पूर्ण उत्पाद ढूंढकर नियम को पूरा करने की उम्मीद करता है। लेकिन उस उत्पाद के सभी हिस्सों को कैसे पार्स किया जाए, इस पर अधिक विवरण की आवश्यकता है।
+इससे पता चलता है कि पार्सर यहां तक कैसे पहुंचा, फिर सम्स को देखकर + बड़े सम्स की तलाश करते हुए। <बड़ा>{{color|#f7f|•}}</बड़ा>मार्कर नियम की शुरुआत से आगे बढ़ गया है। यह यह भी दर्शाता है कि कैसे पार्सर अंततः पूर्ण उत्पाद ढूंढकर नियम को पूरा करने की उम्मीद करता है। किन्तु  उस उत्पाद के सभी हिस्सों को कैसे पार्स किया जाए, इस पर अधिक विवरण की आवश्यकता है।
 किसी राज्य के लिए आंशिक रूप से पार्स किए गए नियमों को उसके मूल LR(0) आइटम कहा जाता है। पार्सर जनरेटर अपेक्षित उत्पादों के निर्माण में सभी संभावित अगले चरणों के लिए अतिरिक्त नियम या आइटम जोड़ता है:
@@ Line 302: / Line 302: @@
 एसएलआर पार्सर्स में, ये लुकहेड सेट अलग-अलग राज्यों और बदलावों पर विचार किए बिना सीधे व्याकरण से निर्धारित होते हैं। प्रत्येक नॉनटर्मिनल एस के लिए, एसएलआर जनरेटर सभी टर्मिनल प्रतीकों के सेट फॉलो (एस) पर काम करता है, जो तुरंत एस की कुछ घटनाओं का पालन कर सकता है। पार्स तालिका में, एस में प्रत्येक कमी फॉलो (एस) को अपने एलआर (1) के रूप में उपयोग करती है। ) लुकअहेड सेट। ऐसे फॉलो सेट का उपयोग जेनरेटर द्वारा एलएल टॉप-डाउन पार्सर्स के लिए भी किया जाता है। एक व्याकरण जिसमें फॉलो सेट का उपयोग करते समय कोई बदलाव/घटाव या विरोध कम/कम नहीं होता है, उसे एसएलआर व्याकरण कहा जाता है।
-एलएएलआर पार्सर्स में एसएलआर पार्सर्स के समान ही स्थिति होती है, लेकिन प्रत्येक व्यक्तिगत स्थिति के लिए न्यूनतम आवश्यक कमी की संभावनाओं को पूरा करने के लिए अधिक जटिल, अधिक सटीक तरीके का उपयोग किया जाता है। व्याकरण के विवरण के आधार पर, यह एसएलआर पार्सर जनरेटर द्वारा गणना किए गए फॉलो सेट के समान हो सकता है, या यह एसएलआर लुकहेड्स का सबसेट बन सकता है। कुछ व्याकरण एलएएलआर पार्सर जनरेटर के लिए ठीक हैं लेकिन एसएलआर पार्सर जनरेटर के लिए नहीं। ऐसा तब होता है जब व्याकरण में फॉलो सेट का उपयोग करके विरोधाभासों को गलत बदलाव / कम या कम किया जाता है, लेकिन एलएएलआर जनरेटर द्वारा गणना किए गए सटीक सेटों का उपयोग करते समय कोई टकराव नहीं होता है। व्याकरण को तब LALR(1) कहा जाता है, लेकिन SLR नहीं।
+एलएएलआर पार्सर्स में एसएलआर पार्सर्स के समान ही स्थिति होती है, किन्तु  प्रत्येक व्यक्तिगत स्थिति के लिए न्यूनतम आवश्यक कमी की संभावनाओं को पूरा करने के लिए अधिक जटिल, अधिक सटीक तरीके का उपयोग किया जाता है। व्याकरण के विवरण के आधार पर, यह एसएलआर पार्सर जनरेटर द्वारा गणना किए गए फॉलो सेट के समान हो सकता है, या यह एसएलआर लुकहेड्स का सबसेट बन सकता है। कुछ व्याकरण एलएएलआर पार्सर जनरेटर के लिए ठीक हैं किन्तु  एसएलआर पार्सर जनरेटर के लिए नहीं। ऐसा तब होता है जब व्याकरण में फॉलो सेट का उपयोग करके विरोधाभासों को गलत बदलाव / कम या कम किया जाता है, किन्तु  एलएएलआर जनरेटर द्वारा गणना किए गए सटीक सेटों का उपयोग करते समय कोई टकराव नहीं होता है। व्याकरण को तब LALR(1) कहा जाता है, किन्तु  SLR नहीं।
-एक एसएलआर या एलएएलआर पार्सर डुप्लिकेट स्थिति होने से बचाता है। लेकिन यह न्यूनतमकरण आवश्यक नहीं है, और कभी-कभी अनावश्यक पूर्वव्यापी टकराव पैदा कर सकता है। कैनोनिकल एलआर पार्सर्स नॉनटर्मिनल के उपयोग के बाएँ और दाएँ संदर्भ को बेहतर ढंग से याद रखने के लिए डुप्लिकेट (या स्प्लिट) स्थितियों का उपयोग करते हैं। व्याकरण में प्रतीक एस की प्रत्येक घटना को अपने स्वयं के लुकहेड सेट के साथ स्वतंत्र रूप से व्यवहार किया जा सकता है, ताकि कम करने वाले संघर्षों को हल करने में मदद मिल सके। यह कुछ और व्याकरणों को संभालता है। दुर्भाग्य से, यदि व्याकरण के सभी भागों के लिए ऐसा किया जाए तो यह पार्स तालिकाओं के आकार को बहुत बढ़ा देता है। कुछ गैर-टर्मिनलों की दो या अधिक नामित प्रतियां बनाकर, राज्यों का यह विभाजन किसी भी एसएलआर या एलएएलआर पार्सर के साथ मैन्युअल रूप से और चुनिंदा रूप से किया जा सकता है। एक व्याकरण जो एक कैनोनिकल एलआर जनरेटर के लिए संघर्ष-मुक्त है, लेकिन एलएएलआर जनरेटर में विरोधाभास है, उसे एलआर (1) कहा जाता है, लेकिन एलएएलआर (1) नहीं, और एसएलआर नहीं।
+एक एसएलआर या एलएएलआर पार्सर डुप्लिकेट स्थिति होने से बचाता है। किन्तु  यह न्यूनतमकरण आवश्यक नहीं है, और कभी-कभी अनावश्यक पूर्वव्यापी टकराव पैदा कर सकता है। कैनोनिकल एलआर पार्सर्स नॉनटर्मिनल के उपयोग के बाएँ और दाएँ संदर्भ को बेहतर ढंग से याद रखने के लिए डुप्लिकेट (या स्प्लिट) स्थितियों का उपयोग करते हैं। व्याकरण में प्रतीक एस की प्रत्येक घटना को अपने स्वयं के लुकहेड सेट के साथ स्वतंत्र रूप से व्यवहार किया जा सकता है, ताकि कम करने वाले संघर्षों को हल करने में मदद मिल सके। यह कुछ और व्याकरणों को संभालता है। दुर्भाग्य से, यदि व्याकरण के सभी भागों के लिए ऐसा किया जाए तो यह पार्स तालिकाओं के आकार को बहुत बढ़ा देता है। कुछ गैर-टर्मिनलों की दो या अधिक नामित प्रतियां बनाकर, राज्यों का यह विभाजन किसी भी एसएलआर या एलएएलआर पार्सर के साथ मैन्युअल रूप से और चुनिंदा रूप से किया जा सकता है। एक व्याकरण जो एक कैनोनिकल एलआर जनरेटर के लिए संघर्ष-मुक्त है, किन्तु  एलएएलआर जनरेटर में विरोधाभास है, उसे एलआर (1) कहा जाता है, किन्तु  एलएएलआर (1) नहीं, और एसएलआर नहीं।
 एसएलआर, एलएएलआर, और कैनोनिकल एलआर पार्सर बिल्कुल समान बदलाव करते हैं और इनपुट स्ट्रीम सही भाषा होने पर निर्णय कम करते हैं। जब इनपुट में सिंटैक्स त्रुटि होती है, तो एलएएलआर पार्सर कैनोनिकल एलआर पार्सर की तुलना में त्रुटि का पता लगाने से पहले कुछ अतिरिक्त (हानिरहित) कटौती कर सकता है। और एसएलआर पार्सर और भी अधिक कर सकता है। ऐसा इसलिए होता है क्योंकि एसएलआर और एलएएलआर पार्सर उस विशेष स्थिति के लिए वास्तविक, न्यूनतम लुकहेड प्रतीकों के लिए एक उदार सुपरसेट सन्निकटन का उपयोग कर रहे हैं।
 ===सिंटेक्स त्रुटि पुनर्प्राप्ति===
-एलआर पार्सर किसी प्रोग्राम में पहली सिंटैक्स त्रुटि के लिए कुछ हद तक उपयोगी त्रुटि संदेश उत्पन्न कर सकते हैं, बस उन सभी टर्मिनल प्रतीकों की गणना करके जो अप्रत्याशित खराब लुकहेड प्रतीक के बजाय आगे दिखाई दे सकते थे। लेकिन इससे पार्सर को आगे, स्वतंत्र त्रुटियों को देखने के लिए इनपुट प्रोग्राम के शेष भाग को पार्स करने में मदद नहीं मिलती है। यदि पार्सर पहली त्रुटि से बुरी तरह से ठीक हो जाता है, तो यह बाकी सब चीजों को गलत तरीके से पार्स करने और अनुपयोगी नकली त्रुटि संदेशों का एक समूह उत्पन्न करने की बहुत संभावना है।
+एलआर पार्सर किसी प्रोग्राम में पहली सिंटैक्स त्रुटि के लिए कुछ हद तक उपयोगी त्रुटि संदेश उत्पन्न कर सकते हैं, बस उन सभी टर्मिनल प्रतीकों की गणना करके जो अप्रत्याशित खराब लुकहेड प्रतीक के बजाय आगे दिखाई दे सकते थे। किन्तु  इससे पार्सर को आगे, स्वतंत्र त्रुटियों को देखने के लिए इनपुट प्रोग्राम के शेष भाग को पार्स करने में मदद नहीं मिलती है। यदि पार्सर पहली त्रुटि से बुरी तरह से ठीक हो जाता है, तो यह बाकी सब चीजों को गलत तरीके से पार्स करने और अनुपयोगी नकली त्रुटि संदेशों का एक समूह उत्पन्न करने की बहुत संभावना है।
 [[ हाँ ]] और बाइसन पार्सर जनरेटर में, पार्सर के पास वर्तमान कथन को छोड़ने, त्रुटि के आसपास कुछ पार्स किए गए वाक्यांशों और लुकहेड टोकन को त्यागने और अर्धविराम या ब्रेसिज़ जैसे कुछ विश्वसनीय कथन-स्तर सीमांकक पर पार्स को पुन: सिंक्रनाइज़ करने के लिए एक तदर्थ तंत्र है। यह अक्सर पार्सर और कंपाइलर को बाकी प्रोग्राम को देखने की अनुमति देने के लिए अच्छा काम करता है।
@@ Line 314: / Line 314: @@
 कई वाक्य-विन्यास कोडिंग त्रुटियाँ साधारण टाइपो या एक तुच्छ प्रतीक की चूक हैं। कुछ एलआर पार्सर इन सामान्य मामलों का पता लगाने और स्वचालित रूप से मरम्मत करने का प्रयास करते हैं। पार्सर त्रुटि बिंदु पर प्रत्येक संभावित एकल-प्रतीक सम्मिलन, विलोपन या प्रतिस्थापन की गणना करता है। कंपाइलर प्रत्येक परिवर्तन के साथ एक परीक्षण पार्स करता है यह देखने के लिए कि क्या यह ठीक से काम कर रहा है। (इसके लिए पार्स स्टैक और इनपुट स्ट्रीम के स्नैपशॉट पर बैकट्रैकिंग की आवश्यकता होती है, आमतौर पर पार्सर द्वारा इसकी आवश्यकता नहीं होती है।) कुछ सर्वोत्तम मरम्मत को चुना जाता है। यह एक बहुत ही उपयोगी त्रुटि संदेश देता है और पार्स को अच्छी तरह से पुन: सिंक्रनाइज़ करता है। हालाँकि, मरम्मत इनपुट फ़ाइल को स्थायी रूप से संशोधित करने के लिए पर्याप्त भरोसेमंद नहीं है। सिंटैक्स त्रुटियों की मरम्मत उन पार्सर्स (जैसे एलआर) में लगातार करना सबसे आसान है जिनमें पार्स टेबल और एक स्पष्ट डेटा स्टैक होता है।
 ===एलआर पार्सर्स के वेरिएंट===
-एलआर पार्सर जनरेटर यह तय करता है कि पार्सर स्थिति और लुकहेड प्रतीक के प्रत्येक संयोजन के लिए क्या होना चाहिए। ये निर्णय आमतौर पर केवल-पढ़ने योग्य डेटा तालिकाओं में बदल दिए जाते हैं जो एक सामान्य पार्सर लूप चलाते हैं जो व्याकरण- और राज्य-स्वतंत्र होता है। लेकिन उन निर्णयों को सक्रिय पार्सर में बदलने के अन्य तरीके भी हैं।
+एलआर पार्सर जनरेटर यह तय करता है कि पार्सर स्थिति और लुकहेड प्रतीक के प्रत्येक संयोजन के लिए क्या होना चाहिए। ये निर्णय सामान्यतः केवल-पढ़ने योग्य डेटा तालिकाओं में बदल दिए जाते हैं जो एक सामान्य पार्सर लूप चलाते हैं जो व्याकरण- और राज्य-स्वतंत्र होता है। किन्तु  उन निर्णयों को सक्रिय पार्सर में बदलने के अन्य तरीके भी हैं।
 कुछ एलआर पार्सर जेनरेटर पार्स टेबल के बजाय प्रत्येक राज्य के लिए अलग-अलग अनुकूलित प्रोग्राम कोड बनाते हैं। ये पार्सर टेबल-संचालित पार्सर में सामान्य पार्सर लूप की तुलना में कई गुना तेज चल सकते हैं। सबसे तेज़ पार्सर जनरेट किए गए असेंबलर कोड का उपयोग करते हैं।
@@ Line 322: / Line 322: @@
 एक अन्य भिन्नता [[प्रोलॉग]] जैसी गैर-प्रक्रियात्मक भाषाओं में पैटर्न-मिलान नियमों द्वारा पार्स तालिका को प्रतिस्थापित करती है।
-जीएलआर सामान्यीकृत एलआर पार्सर केवल एक सही पार्स नहीं बल्कि इनपुट टेक्स्ट के सभी संभावित पार्स ढूंढने के लिए एलआर बॉटम-अप तकनीकों का उपयोग करते हैं। यह मानव भाषाओं जैसे अस्पष्ट व्याकरण के लिए आवश्यक है। एकाधिक वैध पार्स पेड़ों की गणना एक साथ की जाती है, बिना बैकट्रैकिंग के। जीएलआर कभी-कभी उन कंप्यूटर भाषाओं के लिए सहायक होता है जिन्हें संघर्ष-मुक्त एलएएलआर(1) व्याकरण द्वारा आसानी से वर्णित नहीं किया जा सकता है।
+जीएलआर सामान्यीकृत एलआर पार्सर केवल एक सही पार्स नहीं बल्कि इनपुट टेक्स्ट के सभी संभावित पार्स ढूंढने के लिए एलआर बॉटम-अप तकनीकों का उपयोग करते हैं। यह मानव भाषाओं जैसे अस्पष्ट व्याकरण के लिए आवश्यक है। एकाधिक वैध पार्स ट्रीों की गणना एक साथ की जाती है, बिना बैकट्रैकिंग के। जीएलआर कभी-कभी उन कंप्यूटर भाषाओं के लिए सहायक होता है जिन्हें संघर्ष-मुक्त एलएएलआर(1) व्याकरण द्वारा आसानी से वर्णित नहीं किया जा सकता है।
 एलसी [[ बायां कोना पार्सर ]] वैकल्पिक व्याकरण नियमों के बाएं छोर को पहचानने के लिए एलआर बॉटम-अप तकनीकों का उपयोग करते हैं। जब विकल्पों को एक संभावित नियम तक सीमित कर दिया जाता है, तो पार्सर उस नियम के बाकी हिस्सों को पार्स करने के लिए टॉप-डाउन एलएल (1) तकनीकों पर स्विच करता है। एलसी पार्सर्स में एलएएलआर पार्सर्स की तुलना में छोटी पार्स टेबल और बेहतर त्रुटि निदान होता है। नियतात्मक एलसी पार्सर्स के लिए व्यापक रूप से उपयोग किए जाने वाले जनरेटर नहीं हैं। बहु-पार्स एलसी पार्सर बहुत बड़े व्याकरण वाली मानव भाषाओं में सहायक होते हैं।
@@ Line 329: / Line 329: @@
 : एलआर (के) व्याकरण को स्ट्रिंग की लंबाई के आनुपातिक निष्पादन समय के साथ कुशलतापूर्वक पार्स किया जा सकता है।<ref>Knuth (1965), p.638</ref>
 :प्रत्येक k≥1 के लिए, एक भाषा को LR(k) व्याकरण द्वारा उत्पन्न किया जा सकता है यदि और केवल यदि यह नियतात्मक [और संदर्भ-मुक्त] है, यदि और केवल यदि इसे LR(1) व्याकरण द्वारा उत्पन्न किया जा सकता है।<ref>Knuth (1965), p.635. Knuth didn't mention the restriction ''k''≥1 there, but it is required by his theorems he referred to, viz. on p.629 and p.630. Similarly, the restriction to [[context-free language]]s is tacitly understood from the context.</ref>
-दूसरे शब्दों में, यदि कोई भाषा एक कुशल वन-पास पार्सर की अनुमति देने के लिए पर्याप्त उचित थी, तो इसे एलआर (के) व्याकरण द्वारा वर्णित किया जा सकता है। और उस व्याकरण को हमेशा यांत्रिक रूप से समकक्ष (लेकिन बड़े) एलआर(1) व्याकरण में बदला जा सकता है। तो एक एलआर (1) पार्सिंग विधि, सिद्धांत रूप में, किसी भी उचित भाषा को संभालने के लिए पर्याप्त शक्तिशाली थी। व्यवहार में, कई प्रोग्रामिंग भाषाओं के प्राकृतिक व्याकरण एलआर(1) के करीब हैं।{{citation needed|date=June 2012}}
+दूसरे शब्दों में, यदि कोई भाषा एक कुशल वन-पास पार्सर की अनुमति देने के लिए पर्याप्त उचित थी, तो इसे एलआर (के) व्याकरण द्वारा वर्णित किया जा सकता है। और उस व्याकरण को हमेशा यांत्रिक रूप से समकक्ष (किन्तु  बड़े) एलआर(1) व्याकरण में बदला जा सकता है। तो एक एलआर (1) पार्सिंग विधि, सिद्धांत रूप में, किसी भी उचित भाषा को संभालने के लिए पर्याप्त शक्तिशाली थी। व्यवहार में, कई प्रोग्रामिंग भाषाओं के प्राकृतिक व्याकरण एलआर(1) के करीब हैं।{{citation needed|date=June 2012}}
 नथ द्वारा वर्णित कैनोनिकल एलआर पार्सर्स में बहुत अधिक राज्य और बहुत बड़ी पार्स टेबलें थीं जो उस युग के कंप्यूटरों की सीमित मेमोरी के लिए अव्यवहारिक रूप से बड़ी थीं। एलआर पार्सिंग तब व्यावहारिक हो गई जब [[फ्रैंक डेरेमर]] ने बहुत कम राज्यों के साथ [[सरल एलआर पार्सर]] और [[एलएएलआर]] पार्सर का आविष्कार किया।<ref>
@@ Line 580: / Line 580: @@
 अब, तीसरी पुनरावृत्ति शुरू होती है।
-आइटम सेट 5 के लिए, टर्मिनल '0' और '1' और नॉनटर्मिनल बी पर विचार किया जाना चाहिए, लेकिन परिणामी बंद आइटम सेट क्रमशः पहले से पाए गए आइटम सेट 1 और 2 के बराबर हैं। नॉनटर्मिनल बी के लिए, संक्रमण इस प्रकार है:
+आइटम सेट 5 के लिए, टर्मिनल '0' और '1' और नॉनटर्मिनल बी पर विचार किया जाना चाहिए, किन्तु  परिणामी बंद आइटम सेट क्रमशः पहले से पाए गए आइटम सेट 1 और 2 के बराबर हैं। नॉनटर्मिनल बी के लिए, संक्रमण इस प्रकार है:
 : आइटम सेट 7
 : ई → ई * बी <बड़ा>{{color|#f7f|•}}</बड़ा>
-आइटम सेट 6 के लिए, टर्मिनल '0' और '1' और नॉनटर्मिनल बी पर विचार किया जाना चाहिए, लेकिन पहले की तरह, टर्मिनलों के लिए परिणामी आइटम सेट पहले से पाए गए आइटम सेट 1 और 2 के बराबर हैं। नॉनटर्मिनल बी के लिए संक्रमण इस प्रकार है:
+आइटम सेट 6 के लिए, टर्मिनल '0' और '1' और नॉनटर्मिनल बी पर विचार किया जाना चाहिए, किन्तु  पहले की तरह, टर्मिनलों के लिए परिणामी आइटम सेट पहले से पाए गए आइटम सेट 1 और 2 के बराबर हैं। नॉनटर्मिनल बी के लिए संक्रमण इस प्रकार है:
 : आइटम सेट 8
@@ Line 645: / Line 645: @@
 एलआर (0) तालिका निर्माण प्रक्रिया (जैसे कि सरल एलआर पार्सर और [[एलएएलआर पार्सर]]) के परिशोधन उन कम क्रियाओं का निर्माण करने में सक्षम हैं जो पूरी पंक्तियों पर कब्जा नहीं करते हैं। इसलिए, वे एलआर(0) पार्सर्स की तुलना में अधिक व्याकरणों को पार्स करने में सक्षम हैं।
 === निर्मित तालिकाओं में संघर्ष ===
 ऑटोमेटन का निर्माण इस तरह से किया गया है कि इसके नियतात्मक होने की गारंटी है। हालाँकि, जब कार्रवाई तालिका में कम क्रियाएं जोड़ी जाती हैं तो ऐसा हो सकता है कि एक ही सेल एक कम कार्रवाई और एक शिफ्ट कार्रवाई (एक शिफ्ट-कम संघर्ष) या दो अलग-अलग कम क्रियाओं (एक कम-कम संघर्ष) से भरा हो। हालाँकि, यह दिखाया जा सकता है कि जब ऐसा होता है तो व्याकरण LR(0) व्याकरण नहीं है। शिफ्ट-रिड्यूस संघर्ष का एक क्लासिक वास्तविक दुनिया का उदाहरण लटकती हुई अन्य समस्या है।
 शिफ्ट-रिड्यूस संघर्ष के साथ गैर-एलआर (0) व्याकरण का एक छोटा सा उदाहरण है:

v t e Parsing algorithms
Top-down	LL Recursive descent Tail recursive
Bottom-up	Precedence Simple Operator Shunting-yard LR Simple Look-ahead Canonical Generalized CYK Recursive ascent Shift-reduce
Mixed, other	Combinator Chart Earley
Related topics	PEG Definite clause grammar Deterministic parsing Dynamic programming Memoization Parser generator LALR Parse tree AST Scannerless parsing History of compiler construction Comparison of parser generators Operator-precedence grammar

Anonymous

Search

एलआर पार्सर: Difference between revisions

Revision as of 14:07, 4 August 2023

अवलोकन

उदाहरण के लिए बॉटम-अप पार्स ट्री A*2 + 1

कार्यों को परिवर्तन और कम करें

बॉटम-अप पार्स स्टैक

उदाहरण के लिए नीचे से ऊपर पार्स चरण ए*2 + 1

एलआर पार्स चरण उदाहरण के लिए ए*2 + 1

उदाहरण के लिए व्याकरण ए*2 + 1

उदाहरण व्याकरण के लिए पार्स टेबल

एलआर पार्सर लूप

एलआर जनरेटर विश्लेषण

एलआर राज्य

परिमित अवस्था मशीन

लुकहेड सेट

सिंटेक्स त्रुटि पुनर्प्राप्ति

एलआर पार्सर्स के वेरिएंट

सिद्धांत

अतिरिक्त उदाहरण 1+1

कार्रवाई और गोटो टेबल

पार्सिंग चरण

पूर्वाभ्यास

एलआर(0) पार्सिंग तालिकाओं का निर्माण

आइटम

आइटम सेट

गैर-टर्मिनलों के विस्तार द्वारा आइटम सेट का विस्तार

आइटम सेट को बंद करना

संवर्धित व्याकरण

टेबल निर्माण

पहुंच योग्य आइटम सेट और उनके बीच संक्रमण ढूँढना

कार्रवाई और गोटो तालिकाओं का निर्माण

एलआर(0) बनाम एसएलआर और एलएएलआर पार्सिंग के बारे में एक नोट

निर्मित तालिकाओं में संघर्ष

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories