एलआर पार्सर

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

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

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

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

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

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

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

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

चरण	पार्स स्टैक	अनपार्सड	शिफ्ट/रेडियूस
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 अनेक भागों के साथ ग्रामर नियम प्रयुक्त करता है:

Products → Products * Value

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

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

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

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

चरण	पार्स स्टैक _state [सिम्बल _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 ईओफ़ का पूर्वाभास देखती है, तो वह पूर्ण ग्रामर नियम को प्रयुक्त करती है

Sums → Sums + Products

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

उदाहरण के लिए ग्रामर A*2 + 1

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

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

r0: Goal → Sums eof

r1: Sums → Sums + Products

r2: Sums → Products

r3: Products → Products * Value

r4: Products → Value

r5: Value → int

r6: Value → id

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

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

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

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

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

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

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

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

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

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

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

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

कर्र		लुक एहेड					एलएचएस Goto
अवस्था	वर्तमान नियम	आईएनटी	आईडी	*	+	ईओएफ	सम्स	उत्पाद	मान
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: Sums → Sums + •Products

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

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

r1: Sums → Sums + Products•

r3: Products → Products• * Value

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

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

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

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

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

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

शिफ्ट एन:

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

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

R_m कम करें: ग्रामर नियम प्रयुक्त करें R_m: एलएचएस → S₁ S₂ ... S_L

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

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

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

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

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

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

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

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

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

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

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

एलआर अवस्था

उदाहरण पार्स टेबल में अवस्था 2 आंशिक रूप से पार्स किए गए नियम के लिए है

r1: Sums → Sums +• Products

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

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

r3: Products →• Products * Value

r4: Products →• Value

r5: Value →• int

r6: Value →• id

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

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

r5: Value → int •

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

r1: Sums → Sums + Products •

r3: Products → Products • * Value

शब्दों में, इसका अर्थ है कि यदि पार्सर ने एक ही उत्पाद देखा है, तो यह किया जा सकता है, या इसमें अभी भी एक साथ गुणा करने के लिए और भी वस्तु हो सकती हैं। सभी मुख्य वस्तुओं में से पहले एक ही सिम्बल होता है•marker; इस अवस्था में सभी परिवर्तन सदैव एक ही सिम्बल के साथ होते हैं।कुछ परिवर्तन कोर और अवस्था में होंगे जिनकी गणना पहले ही की जा चुकी है। अन्य परिवर्तन नए अवस्था की ओर ले जाते हैं। जनरेटर व्याकरण के लक्ष्य नियम से प्रारंभ होता है। वहां से यह तब तक ज्ञात अवस्थाओं और संक्रमणों की खोज करता रहता है जब तक कि सभी आवश्यक अवस्थाएं नहीं मिल जातीं है।इन अवस्था को LR(0) अवस्था कहा जाता है क्योंकि वे k=0 के लुकहेड का उपयोग करते हैं, अर्थात कोई लुकहेड नहीं। इनपुट सिम्बल की एकमात्र जांच तब होती है जब सिम्बल को स्थानांतरित किया जाता है। कमी के लिए लुकहेड्स की जांच पार्स टेबल द्वारा अलग से की जाती है, न कि गणना किए गए अवस्था द्वारा।

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

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

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

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

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

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

लुकहेड सेट

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

सिद्धांत

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

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

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

दूसरे शब्दों में, यदि कोई लैंग्वेज एक कुशल 1-पास पार्सर की अनुमति देने के लिए पर्याप्त उचित थी, तो इसे LR(k) व्याकरण द्वारा वर्णित किया जा सकता है। और उस व्याकरण को सदैव यांत्रिक रूप से समकक्ष (किन्तु बड़े) एलआर(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

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

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

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

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

1 + 1

कार्रवाई और goto टेबल

इस व्याकरण के लिए दो 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

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

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

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

पार्सिंग चरण

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

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 और बी के लिए goto टेबल में सेल से अवस्था को स्टैक पर धकेलता है, अर्थात , अवस्था 4। परिणामी स्टैक है:

[0 B 4]

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

[0 E 3]

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

[0 E 3 '+' 6]

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

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

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

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

[0 E 3 '+' 6 B 8]

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

[0 E 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 • + B और E → E • * E से संबंधित स्ट्रिंग पढ़ने के पश्चात B दोनों प्रयुक्त होते है। इसलिए, वस्तुओं के सेट द्वारा पार्सर की स्थिति को चिह्नित करना सुविधाजनक है, इस स्तिथि में सेट { E → E • + B, E → E •*B }.

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

नॉनटर्मिनल से पूर्व बिंदु वाली वस्तु , जैसे कि E → E + •बी, इंगित करता है कि पार्सर अगले नॉनटर्मिनल B को पार्स करने की प्रतीक्षा करता है। यह सुनिश्चित करने के लिए कि वस्तु सेट में सभी संभावित नियम सम्मिलित हैं, पार्सर पार्सिंग के मध्य में हो सकता है, इसमें सभी वस्तु सम्मिलित होने चाहिए जो बताते हैं कि बी को कैसे पार्स किया जाएगा। इसका अर्थ यह है कि यदि B→ 1 और B→ 0 जैसे नियम हैं तो वस्तु सेट में वस्तु B → भी सम्मिलित होना चाहिए•1 और B → •0. सामान्य रूप से इसे इस प्रकार तैयार किया जा सकता है:

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

वस्तु सेट को विवृत करना

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

संवर्धित ग्रामर

विभिन्न अवस्थाओं के मध्य परिवर्तन निर्धारित करने से पूर्व, ग्रामर को अतिरिक्त नियम के साथ संवर्धित किया जाता है

(0) S → E EOF

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

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

(0) S → E EOF

(1)E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

यह इस संवर्धित ग्रामर के लिए है कि वस्तु सेट और उनके मध्य के परिवर्तन निर्धारित किए जाते है।

टेबल निर्माण

पहुंच योग्य वस्तु सेट और उनके मध्य संक्रमण खोजना

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

वस्तु सेट 0 है

S → •E EOF

+ E → •E*B

+ E → •E+B

+ E → •B

+ B → •0

+ B → •1

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

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

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

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

'वस्तु सेट 1'

B → 0 •

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

वस्तु सेट 2

B → 1 •

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

वस्तु सेट 3

S → E •ईओएफ

E → E •* ब

E → E •+बी

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

वस्तु सेट 4

E → B •

क्लोजर सभी स्तिथ्यो में नए वस्तु नहीं जोड़ता है - उदाहरण के लिए, ऊपर दिए गए नए सेट में, डॉट के पश्चात कोई नॉनटर्मिनल नहीं है।

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

वस्तु सेट 5

E→ E * •बी

+ B → •0

+ B→ •1

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

वस्तु सेट 6

E→ E + •बी

+ B → •0

+ B → •1

अब, तृतीय पुनरावृत्ति प्रारंभ होती है।

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

वस्तु सेट 7

E→ E * B •

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

वस्तु सेट 8

E→ E + B •

इन अंतिम वस्तु सेट 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

कार्रवाई और goto टेबल ओं का निर्माण

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

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

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

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

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

निर्मित टेबल ओं में संघर्ष

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

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

(1) E → 1 E

(2) E → 1

पाए गए वस्तु सेटों में से एक है:

'वस्तु सेट 1'

ई → 1 •ई

ई → 1 •

+ ई → •1 ई

+ ई →•1

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

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

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 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]

Anonymous

Search

एलआर पार्सर

अवलोकन

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

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

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

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

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

उदाहरण के लिए ग्रामर A*2 + 1

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

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

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

एलआर अवस्था

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

लुकहेड सेट

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

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

सिद्धांत

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

कार्रवाई और goto टेबल

पार्सिंग चरण

पूर्वाभ्यास

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

वस्तु

वस्तु सेट

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

वस्तु सेट को विवृत करना

संवर्धित ग्रामर

टेबल निर्माण

पहुंच योग्य वस्तु सेट और उनके मध्य संक्रमण खोजना

कार्रवाई और goto टेबल ओं का निर्माण

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

निर्मित टेबल ओं में संघर्ष

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories