एलआर पार्सर

कंप्यूटर विज्ञान में, एलआर पार्सर एक प्रकार का नीचे से ऊपर का विश्लेषण|बॉटम-अप पार्सर है जो रैखिक समय में नियतात्मक संदर्भ-मुक्त भाषाओं का विश्लेषण करता है।^[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]

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

चरण 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 पर आगे बढ़ती है।

Template:Rule

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

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

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

Template:Rule

चरण 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 पर आगे बढ़ता है। एक उत्पाद नॉनटर्मिनल वैल्यू से भी शुरू हो सकता है। किसी अन्य लुकअहेड या नॉनटर्मिनल के लिए, पार्सर एक सिंटैक्स त्रुटि की घोषणा करता है।

Template:Rule

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

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

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

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

Template:Rule

उपरोक्त स्थिति 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

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

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

(1) ई → ई * बी

(2) ई → ई + बी

(3) ई → बी

(4) बी → 0

(5) बी → 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 <बड़ा>•</बड़ा>उदाहरण के लिए, + बी इंगित करता है कि पार्सर ने इनपुट स्ट्रीम पर ई के अनुरूप एक स्ट्रिंग को पहचान लिया है और अब '+' को पढ़ने की उम्मीद करता है जिसके बाद बी के अनुरूप एक और स्ट्रिंग आती है।

आइटम सेट

आम तौर पर किसी एक आइटम के साथ पार्सर की स्थिति को चिह्नित करना संभव नहीं है क्योंकि यह पहले से नहीं जानता होगा कि यह कमी के लिए किस नियम का उपयोग करने जा रहा है। उदाहरण के लिए, यदि कोई नियम 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

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

आइटम सेट 1

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

बी → 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]

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

एलआर पार्सर

सिंहावलोकन

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

कार्यों को बदलें और कम करें

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

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

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

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

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

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

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

एलआर राज्य

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

लुकहेड सेट

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

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

सिद्धांत

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

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

पार्सिंग चरण

पूर्वाभ्यास

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

आइटम

आइटम सेट

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

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

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

टेबल निर्माण

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories