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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Use dmy dates|date=October 2020}}
{{Use dmy dates|date=October 2020}}
[[Index.php?title=अभिकलित्र विज्ञान|अभिकलित्र विज्ञान]] में, एक '''एलएएलआर पार्सर{{efn|"LALR" is pronounced as the [[initialism]] "el-ay-el-arr"}}''' या '''लुक-अहेड, लेफ्ट-टू-राइट, राइटमोस्ट व्युत्पत्ति पार्सर''' संकलन प्रक्रिया का हिस्सा है जहाँ मानव पठनीय पाठ को कंप्यूटर निर्देशों में परिवर्तित किया जाता है। एलएएलआर पार्सर एक सॉफ्टवेयर टूल है जो कोड को एक बहुत ही विशिष्ट आंतरिक प्रतिनिधित्व में संसाधित (पार्स) करता है जिससे कंपाइलर काम कर सकता है। यह [[Index.php?title=अभिकलित्र भाषा|अभिकलित्र भाषा]] के लिए [[औपचारिक व्याकरण]] द्वारा निर्दिष्ट [[Index.php?title=उत्पादन (अभिकलित्र विज्ञान)|उत्पादन (अभिकलित्र विज्ञान)]] के एक सेट के अनुसार होता है।
[[Index.php?title=अभिकलित्र विज्ञान|अभिकलित्र विज्ञान]] में, एक '''एलएएलआर पार्सर{{efn|"LALR" is pronounced as the [[initialism]] "el-ay-el-arr"}}''' या '''लुक-अहेड, लेफ्ट-टू-राइट, राइटमोस्ट व्युत्पत्ति पार्सर''' संकलन प्रक्रिया का हिस्सा है जहाँ मानव पठनीय पाठ को अभिकलित्र निर्देशों में परिवर्तित किया जाता है। एलएएलआर पार्सर एक सॉफ्टवेयर टूल है जो कोड को एक बहुत ही विशिष्ट आंतरिक प्रतिनिधित्व में संसाधित (पार्स) करता है जिससे कंपाइलर काम कर सकता है। यह [[Index.php?title=अभिकलित्र भाषा|अभिकलित्र भाषा]] के लिए [[औपचारिक व्याकरण]] द्वारा निर्दिष्ट [[Index.php?title=उत्पादन (अभिकलित्र विज्ञान)|उत्पादन (अभिकलित्र विज्ञान)]] के एक सेट के अनुसार होता है।


एलएएलआर पार्सर एक [[कैनोनिकल एलआर पार्सर]] का सरलीकृत संस्करण है।
एलएएलआर पार्सर एक [[कैनोनिकल एलआर पार्सर]] का सरलीकृत संस्करण है।


एलएएलआर पार्सर का आविष्कार [[फ्रैंक डेरेमर]] ने अपने 1969 के पीएचडी शोध प्रबंध, ''एलआर(के) भाषाओं के लिए व्यावहारिक अनुवादक'' में किया था।{{sfn|DeRemer|1969}}एलआर(1) पार्सर्स को लागू करने के उस समय की व्यावहारिक कठिनाइयों के उपचार में। उन्होंने दिखाया कि एलएएलआर पार्सर में एलआर (0) पार्सर की तुलना में अधिक भाषा पहचान शक्ति है, जबकि एक भाषा के लिए एलआर (0) पार्सर के समान राज्यों की आवश्यकता होती है जिसे दोनों पार्सर्स द्वारा पहचाना जा सकता है। यह LALR पार्सर को LALR वाली भाषाओं के लिए LR(1) पार्सर का एक मेमोरी-कुशल विकल्प बनाता है। यह भी सिद्ध हुआ कि ऐसी LR(1) भाषाएँ मौजूद हैं जो LALR नहीं हैं। इस कमजोरी के बावजूद, एलएएलआर पार्सर की शक्ति कई मुख्यधारा की कंप्यूटर भाषाओं के लिए पर्याप्त है,<ref name=chapman>''LR Parsing: Theory and Practice,'' Nigel P. Chapman, [https://books.google.com/books?id=nEA9AAAAIAAJ&pg=PA87 p. 86–87]</ref> [[जावा प्रौद्योगिकी]] सहित,<ref>{{cite web|title=Generate the Parser
एलएएलआर पार्सर का आविष्कार [[फ्रैंक डेरेमर]] ने अपने 1969 के पीएचडी शोध प्रबंध, ''एलआर(के) भाषाओं के लिए व्यावहारिक अनुवादक'' में किया था।{{sfn|DeRemer|1969}}एलआर(1) पार्सर्स को लागू करने के उस समय की व्यावहारिक कठिनाइयों के उपचार में उन्होंने दिखाया कि एलएएलआर पार्सर में एलआर (0) पार्सर की तुलना में अधिक भाषा पहचान शक्ति है, जबकि एक भाषा के लिए एलआर (0) पार्सर के समान अवस्था की आवश्यकता होती है जिसे दोनों पार्सर्स द्वारा पहचाना जा सकता है। यह एलएएलआर पार्सर को एलएएलआर वाली भाषाओं के लिए एलआर(1) पार्सर का एक मेमोरी-कुशल विकल्प बनाता है। यह भी सिद्ध हुआ कि ऐसी एलआर(1) भाषाएँ मौजूद हैं जो एलएएलआर नहीं हैं। इस कमजोरी के बावजूद, एलएएलआर पार्सर की शक्ति कई मुख्यधारा की अभिकलित्र भाषाओं के लिए पर्याप्त है,<ref name=chapman>''LR Parsing: Theory and Practice,'' Nigel P. Chapman, [https://books.google.com/books?id=nEA9AAAAIAAJ&pg=PA87 p. 86–87]</ref> [[जावा प्रौद्योगिकी]] सहित,<ref>{{cite web|title=Generate the Parser
|url=http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html|publisher=Eclipse JDT Project|access-date=29 June 2012}}</ref> हालाँकि कई भाषाओं के संदर्भ व्याकरण [[अस्पष्ट व्याकरण]] होने के कारण LALR होने में विफल रहते हैं।<ref name=chapman />
|url=http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html|publisher=Eclipse JDT Project|access-date=29 June 2012}}</ref> हालाँकि कई भाषाओं के संदर्भ व्याकरण [[अस्पष्ट व्याकरण]] होने के कारण एलएएलआर होने में विफल रहते हैं।<ref name=chapman />


मूल शोध प्रबंध में औपचारिक व्याकरण दिए गए ऐसे पार्सर के निर्माण के लिए कोई एल्गोरिदम नहीं दिया गया था। एलएएलआर पार्सर पीढ़ी के लिए पहला एल्गोरिदम 1973 में प्रकाशित किया गया था।<ref>{{cite journal| first1=T.| last1=Anderson| first2=J.| last2=Eve| first3=J.| last3=Horning| title=कुशल एलआर(1) पार्सर| journal=Acta Informatica| issue=2| year=1973| pages= 2–39}}</ref> 1982 में, डीरेमर और टॉम पेनेलो ने एक एल्गोरिदम प्रकाशित किया जो अत्यधिक मेमोरी-कुशल एलएएलआर पार्सर उत्पन्न करता था।<ref name="DeRemer82">{{cite journal |first1=Frank |last1=DeRemer |first2=Thomas |last2=Pennello |date=October 1982 |title=एलएएलआर(1) लुक-अहेड सेट की कुशल गणना|url=http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR%281%29%20Look-Ahead%20Sets.pdf |journal=ACM Transactions on Programming Languages and Systems |volume=4 |issue=4 |pages=615–649|doi=10.1145/69622.357187}}</ref> एलएएलआर पार्सर स्वचालित रूप से एक व्[[ हाँ ]]रण से [[एलएएलआर पार्सर जनरेटर]] जैसे वाईएसीसी या [[जीएनयू बाइसन]] द्वारा उत्पन्न किया जा सकता है। परिणामी पार्सर की शक्ति को बढ़ाने के लिए स्वचालित रूप से उत्पन्न कोड को हाथ से लिखे गए कोड द्वारा संवर्धित किया जा सकता है।
मूल शोध प्रबंध में औपचारिक व्याकरण दिए गए ऐसे पार्सर के निर्माण के लिए कोई कलन विधि नहीं दिया गया था। एलएएलआर पार्सर पीढ़ी के लिए पहला कलन विधि 1973 में प्रकाशित किया गया था।<ref>{{cite journal| first1=T.| last1=Anderson| first2=J.| last2=Eve| first3=J.| last3=Horning| title=कुशल एलआर(1) पार्सर| journal=Acta Informatica| issue=2| year=1973| pages= 2–39}}</ref> 1982 में, डीरेमर और टॉम पेनेलो ने एक कलन विधि प्रकाशित किया जो अत्यधिक मेमोरी-कुशल एलएएलआर पार्सर उत्पन्न करता था।<ref name="DeRemer82">{{cite journal |first1=Frank |last1=DeRemer |first2=Thomas |last2=Pennello |date=October 1982 |title=एलएएलआर(1) लुक-अहेड सेट की कुशल गणना|url=http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR%281%29%20Look-Ahead%20Sets.pdf |journal=ACM Transactions on Programming Languages and Systems |volume=4 |issue=4 |pages=615–649|doi=10.1145/69622.357187}}</ref> 1982 में, डीरेमर और टॉम पेनेलो ने एक कलन विधि प्रकाशित किया जिसने अत्यधिक मेमोरी-कुशल एलएएलआर पार्सर उत्पन्न किया। एलएएलआर पार्सर स्वचालित रूप से एक व्याकरण से एलएएलआर पार्सर जनरेटर जैसे वाईएसीसी या जीएनयू बाइसन द्वारा उत्पन्न किया जा सकता है। परिणामी पार्सर की शक्ति को बढ़ाने के लिए स्वचालित रूप से उत्पन्न कोड को हाथ से लिखे गए कोड द्वारा संवर्धित किया जा सकता है


== इतिहास ==
== इतिहास ==


1965 में, [[डोनाल्ड नुथ]] ने [[एलआर पार्सर]] (बाएं से दाएं, सबसे दाहिनी व्युत्पत्ति) का आविष्कार किया। एलआर पार्सर किसी भी नियतात्मक संदर्भ-मुक्त भाषा को रैखिक-बद्ध समय में पहचान सकता है।<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | author-link = Donald Knuth | title = भाषाओं के बाएँ से दाएँ अनुवाद पर| doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | url = http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | access-date = 29 May 2011 | archive-url = https://web.archive.org/web/20120315152151/http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | archive-date = 15 March 2012 | url-status = dead | doi-access = free }}</ref> सबसे दाईं ओर की व्युत्पत्ति में बहुत बड़ी मेमोरी आवश्यकताएं होती हैं और उस समय [[स्मृति]] सीमित मेमोरी के कारण एलआर पार्सर को लागू करना अव्यावहारिक था। इस कमी को दूर करने के लिए, 1969 में, फ्रैंक डीरेमर ने एलआर पार्सर के दो सरलीकृत संस्करण प्रस्तावित किए, अर्थात् लुक-अहेड एलआर (एलएएलआर){{sfn|DeRemer|1969}} और [[एसएलआर पार्सर]] जिसमें कम भाषा-पहचान शक्ति की कीमत पर बहुत कम मेमोरी आवश्यकताएं थीं, एलएएलआर पार्सर सबसे शक्तिशाली विकल्प था।{{sfn|DeRemer|1969}} 1977 में, एलआर पार्सर के लिए मेमोरी ऑप्टिमाइज़ेशन का आविष्कार किया गया था<ref>{{citation|title=A Practical General Method for Constructing LR(k) Parsers|volume=7|issue=3|author=Pager, D.|work=Acta Informatica 7|pages=249–268|year=1977|doi=10.1007/BF00290336}}</ref> लेकिन फिर भी एलआर पार्सर सरलीकृत विकल्पों की तुलना में कम मेमोरी-कुशल था।
1965 में, [[डोनाल्ड नुथ]] ने [[एलआर पार्सर]] (लेफ्ट-टू-राइट, राइटमोस्ट व्युत्पत्ति) का आविष्कार किया। एलआर पार्सर किसी भी नियतात्मक संदर्भ-मुक्त भाषा को रैखिक-बद्ध समय में पहचान सकता है।<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | author-link = Donald Knuth | title = भाषाओं के बाएँ से दाएँ अनुवाद पर| doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | url = http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | access-date = 29 May 2011 | archive-url = https://web.archive.org/web/20120315152151/http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf | archive-date = 15 March 2012 | url-status = dead | doi-access = free }}</ref> सबसे दाईं ओर की व्युत्पत्ति में बहुत बड़ी मेमोरी आवश्यकताएं होती हैं और उस समय [[स्मृति]] सीमित मेमोरी के कारण एलआर पार्सर को लागू करना अव्यावहारिक था। इस कमी को दूर करने के लिए, 1969 में, फ्रैंक डीरेमर ने एलआर पार्सर के दो सरलीकृत संस्करण प्रस्तावित किए, अर्थात् लुक-अहेड एलआर (एलएएलआर){{sfn|DeRemer|1969}} और [[एसएलआर पार्सर]] जिसमें कम भाषा-पहचान शक्ति की कीमत पर बहुत कम मेमोरी आवश्यकताएं थीं, एलएएलआर पार्सर सबसे शक्तिशाली विकल्प था।{{sfn|DeRemer|1969}} 1977 में, एलआर पार्सर के लिए मेमोरी ऑप्टिमाइज़ेशन का आविष्कार किया गया था<ref>{{citation|title=A Practical General Method for Constructing LR(k) Parsers|volume=7|issue=3|author=Pager, D.|work=Acta Informatica 7|pages=249–268|year=1977|doi=10.1007/BF00290336}}</ref> लेकिन फिर भी एलआर पार्सर सरलीकृत विकल्पों की तुलना में कम मेमोरी-कुशल था।


1979 में, फ्रैंक डेरेमर और [[टॉम ब्रश]] ने एलएएलआर पार्सर के लिए अनुकूलन की एक श्रृंखला की घोषणा की जो इसकी मेमोरी दक्षता में और सुधार करेगी।<ref>{{citation|title=Efficient Computation of LALR(1) Look-Ahead Sets|author=Frank DeRemer, Thomas Pennello|work=Sigplan Notices - SIGPLAN, vol. 14, no. 8|pages=176–187|year=1979}}</ref> उनका काम 1982 में प्रकाशित हुआ था।<ref name="DeRemer82"/>
1979 में, फ्रैंक डेरेमर और [[टॉम ब्रश]] ने एलएएलआर पार्सर के लिए अनुकूलन की एक श्रृंखला की घोषणा की जो इसकी मेमोरी दक्षता में और सुधार करेगी।<ref>{{citation|title=Efficient Computation of LALR(1) Look-Ahead Sets|author=Frank DeRemer, Thomas Pennello|work=Sigplan Notices - SIGPLAN, vol. 14, no. 8|pages=176–187|year=1979}}</ref> उनका काम 1982 में प्रकाशित हुआ था।<ref name="DeRemer82"/>
Line 17: Line 17:


== सिंहावलोकन ==
== सिंहावलोकन ==
आम तौर पर, एलएएलआर पार्सर एलएएलआर(1) पार्सर को संदर्भित करता है,{{efn|"LALR(1)" is pronounced as the [[initialism]] "el-ay-el-arr-one"}} जिस तरह एलआर पार्सर आम तौर पर एलआर(1) पार्सर को संदर्भित करता है। (1) पार्सिंग के दौरान नियम पैटर्न के बीच अंतर को हल करने के लिए एक-टोकन लुकअहेड को दर्शाता है। इसी तरह, दो-टोकन लुकअप के साथ एक एलएएलआर (2) पार्सर और के-टोकन लुकअप के साथ एलएएलआर (के) पार्सर हैं, लेकिन ये वास्तविक उपयोग में दुर्लभ हैं। LALR पार्सर LR(0) पार्सर पर आधारित है, इसलिए इसे LALR(1) = LA(1)LR(0) (लुकहेड का 1 टोकन, LR(0)) या अधिक सामान्यतः LALR(k) = LA(k)LR(0) (लुकहेड का k टोकन, LR(0)) भी दर्शाया जा सकता है। वास्तव में j और k के सभी संयोजनों के लिए LA(k)LR(j) पार्सर का एक दो-पैरामीटर परिवार है, जिसे LR(j + k) पार्सर से प्राप्त किया जा सकता है,<ref>''Parsing Techniques: A Practical Guide,'' by Dick Grune and Ceriel J. H. Jacobs, "9.7 LALR(1)", [https://books.google.com/books?id=05xA_d5dSwAC&pg=PA302 p. 302]</ref> लेकिन इनका व्यावहारिक उपयोग नजर नहीं आता.
आम तौर पर, एलएएलआर पार्सर एलएएलआर(1) पार्सर को संदर्भित करता है,{{efn|"LALR(1)" is pronounced as the [[initialism]] "el-ay-el-arr-one"}} जिस तरह एलआर पार्सर आम तौर पर एलआर(1) पार्सर को संदर्भित करता है। (1) पार्सिंग के दौरान नियम पैटर्न के बीच अंतर को हल करने के लिए एक-टोकन लुकअहेड को दर्शाता है। इसी तरह, दो-टोकन लुकअप के साथ एक एलएएलआर (2) पार्सर और के-टोकन लुकअप के साथ एलएएलआर (के) पार्सर हैं, लेकिन ये वास्तविक उपयोग में दुर्लभ हैं। एलएएलआर पार्सर एलआर(0) पार्सर पर आधारित है, इसलिए इसे एलएएलआर(1) = एलए(1)एलआर(0) (लुकहेड का 1 टोकन, एलआर(0)) या अधिक सामान्यतः एलएएलआर(k) = एलए(k)एलआर(0) (लुकहेड का k टोकन, एलआर(0)) भी दर्शाया जा सकता है। वास्तव में j और k के सभी संयोजनों के लिए एलए(k)एलआर(j) पार्सर का एक दो-पैरामीटर परिवार है, जिसे एलआर(j + k) पार्सर से प्राप्त किया जा सकता है,<ref>''Parsing Techniques: A Practical Guide,'' by Dick Grune and Ceriel J. H. Jacobs, "9.7 LALR(1)", [https://books.google.com/books?id=05xA_d5dSwAC&pg=PA302 p. 302]</ref> लेकिन इनका व्यावहारिक उपयोग नजर नहीं आता है।


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


== अन्य पार्सर्स से संबंध ==
== अन्य पार्सर्स से संबंध ==


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


एलआर (1) व्याकरण का मानक उदाहरण जिसे एलएएलआर (1) पार्सर के साथ पार्स नहीं किया जा सकता है, जो इस तरह के कम/घटाने वाले संघर्ष को प्रदर्शित करता है, वह है:<ref>"[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht 7.9 LR(1) but not LALR(1)] {{webarchive|url=https://web.archive.org/web/20100804231352/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht |date=4 August 2010 }}", ''[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht CSE 756: Compiler Design and Implementation] {{webarchive|url=https://web.archive.org/web/20100723153301/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht |date=23 July 2010 }},'' Eitan Gurari, Spring 2008</ref><ref>"[https://stackoverflow.com/questions/8496065/why-is-this-lr1-grammar-not-lalr1 Why is this LR(1) grammar not LALR(1)?]"</ref>
एलआर (1) व्याकरण का मानक उदाहरण जिसे एलएएलआर (1) पार्सर के साथ पार्स नहीं किया जा सकता है, जो इस तरह के कम/घटाने वाले संघर्ष को प्रदर्शित करता है, वह है:<ref>"[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht 7.9 LR(1) but not LALR(1)] {{webarchive|url=https://web.archive.org/web/20100804231352/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756su56.xht |date=4 August 2010 }}", ''[http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht CSE 756: Compiler Design and Implementation] {{webarchive|url=https://web.archive.org/web/20100723153301/http://www.cse.ohio-state.edu/~gurari/course/cse756/cse756.xht |date=23 July 2010 }},'' Eitan Gurari, Spring 2008</ref><ref>"[https://stackoverflow.com/questions/8496065/why-is-this-lr1-grammar-not-lalr1 Why is this LR(1) grammar not LALR(1)?]"</ref>
एस → ए ई सी
एस → ए ई सी
    → एक एफ डी
    S → a E c
    → बी एफ सी
    → बी ई डी
  ई → ई
  एफ → ई


एलएएलआर तालिका निर्माण में, दो राज्यों को एक राज्य में विलय कर दिया जाएगा और बाद में लुकहेड्स अस्पष्ट पाए जाएंगे। पूर्वानुमानों वाला एक राज्य है:
    → a F d
    → b F c
    → b E d
  E → e


   ई → ई. {सी,डी}
   F → e
  एफ → ई. {सी,डी}
एलएएलआर तालिका निर्माण में, दो अवस्था को एक अवस्था में विलय कर दिया जाएगा और बाद में लुकहेड्स अस्पष्ट पाए जाएंगे। पूर्वानुमानों वाला एक अवस्था है:


एक LR(1) पार्सर दो अलग-अलग स्थितियाँ बनाएगा (गैर-परस्पर विरोधी लुकहेड्स के साथ), जिनमें से कोई भी अस्पष्ट नहीं है। एलएएलआर पार्सर में इस एक स्थिति में विरोधाभासी क्रियाएं होती हैं (लुकहेड सी या डी, ई या एफ को कम करें), संघर्ष को कम/कम करें; उपरोक्त व्याकरण को एलएएलआर पार्सर जनरेटर द्वारा अस्पष्ट घोषित किया जाएगा और टकराव की सूचना दी जाएगी।
  E → e. {c,d}
 
  F → e. {c,d}
एक एलआर(1) पार्सर दो अलग-अलग स्थितियाँ बनाएगा (गैर-परस्पर विरोधी लुकहेड्स के साथ), जिनमें से कोई भी अस्पष्ट नहीं है। एलएएलआर पार्सर में इस एक स्थिति में विरोधाभासी क्रियाएं होती हैं (लुकहेड c या d, E या F को कम करें), संघर्ष को कम/कम करें; उपरोक्त व्याकरण को एलएएलआर पार्सर जनरेटर द्वारा अस्पष्ट घोषित किया जाएगा और टकराव की सूचना दी जाएगी।


पुनर्प्राप्त करने के लिए, इस अस्पष्टता को E चुनकर हल किया जाता है, क्योंकि यह व्याकरण में F से पहले आता है। हालाँकि, परिणामी पार्सर वैध इनपुट अनुक्रम को पहचानने में सक्षम नहीं होगा <code>b e c</code>, अस्पष्ट अनुक्रम के बाद से <code>e c</code> को कम कर दिया गया है <code>(E → e) c</code>, बजाय सही के <code>(F → e) c</code>, लेकिन <code>b E c</code> व्याकरण में नहीं है.
पुनर्प्राप्त करने के लिए, इस अस्पष्टता को E चुनकर हल किया जाता है, क्योंकि यह व्याकरण में F से पहले आता है। हालाँकि, परिणामी पार्सर वैध इनपुट अनुक्रम को पहचानने में सक्षम नहीं होगा <code>b e c</code>, अस्पष्ट अनुक्रम के बाद से <code>e c</code> को कम कर दिया गया है <code>(E → e) c</code>, बजाय सही के <code>(F → e) c</code>, लेकिन <code>b E c</code> व्याकरण में नहीं है.


=== एलएल पार्सर्स ===
=== एलएल पार्सर्स ===
एलएएलआर(जे) पार्सर एलएल पार्सर|एलएल(के) पार्सर के साथ अतुलनीय हैं: किसी भी जे और के दोनों के लिए 0 से अधिक, एलएएलआर(जे) व्याकरण हैं जो एलएल व्याकरण नहीं हैं|एलएल(के) व्याकरण और इसके विपरीत। वास्तव में, यह अनिर्णीत है कि दिया गया LL(1) व्याकरण किसी के लिए LALR(k) है या नहीं <math>k > 0</math>.<ref name=chapman/>
एलएएलआर(''j'') पार्सर एलएल पार्सर एलएल(''k'') पार्सर के साथ अतुलनीय हैं: किसी भी ''j'' और ''k'' दोनों के लिए 0 से अधिक, एलएएलआर(''j'') व्याकरण हैं जो एलएल व्याकरण नहीं हैं। एलएल(''k'') व्याकरण और इसके विपरीत। वास्तव में, यह अनिर्णीत है कि दिया गया LL(1) व्याकरण किसी के लिए एलएएलआर(k) है या नहीं <math>k > 0</math> है।<ref name=chapman/>


खाली व्युत्पत्तियों की उपस्थिति के आधार पर, एक एलएल(1) व्याकरण एक एसएलआर(1) या एक एलएएलआर(1) व्याकरण के बराबर हो सकता है। यदि एलएल(1) व्याकरण में कोई खाली व्युत्पत्ति नहीं है तो यह एसएलआर(1) है और यदि खाली व्युत्पत्ति वाले सभी प्रतीकों में गैर-रिक्त व्युत्पत्ति है तो यह एलएएलआर(1) है। यदि केवल खाली व्युत्पत्ति वाले प्रतीक मौजूद हैं, तो व्याकरण LALR(1) हो भी सकता है और नहीं भी।<ref>{{harv|Beatty|1982}}</ref>
खाली व्युत्पत्तियों की उपस्थिति के आधार पर, एक एलएल(1) व्याकरण एक एसएलआर(1) या एक एलएएलआर(1) व्याकरण के बराबर हो सकता है। यदि एलएल(1) व्याकरण में कोई खाली व्युत्पत्ति नहीं है तो यह एसएलआर(1) है और यदि खाली व्युत्पत्ति वाले सभी प्रतीकों में गैर-रिक्त व्युत्पत्ति है तो यह एलएएलआर(1) है। यदि केवल खाली व्युत्पत्ति वाले प्रतीक मौजूद हैं, तो व्याकरण एलएएलआर(1) हो भी सकता है और नहीं भी।<ref>{{harv|Beatty|1982}}</ref>




Line 81: Line 83:


== बाहरी संबंध ==
== बाहरी संबंध ==
* [http://www.supereasyfree.com/software/simulators/compilers/principles-techniques-and-tools/parsing-simulator/parsing-simulator.php Parsing Simulator] This simulator is used to generate parsing tables LALR and resolve the exercises of the book.
* [http://www.supereasyfree.com/software/simulators/compilers/principles-techniques-and-tools/parsing-simulator/parsing-simulator.php Parsing Simulator] This simulator is used to generate parsing tables एलएएलआर and resolve the exercises of the book.
* [http://jscc.brobston.com/ JS/CC] JavaScript based implementation of a LALR(1) parser generator, which can be run in a web-browser or from the command-line.
* [http://jscc.brobston.com/ JS/CC] JavaScript based implementation of a एलएएलआर(1) parser generator, which can be run in a web-browser or from the command-line.
* {{webarchive |url=https://web.archive.org/web/20210507215636/http://web.cs.dal.ca:80/~sjackson/lalr1.html |date=May 7, 2021 |title=LALR(1) tutorial}}, a flash card-like tutorial on LALR(1) parsing.
* {{webarchive |url=https://web.archive.org/web/20210507215636/http://web.cs.dal.ca:80/~sjackson/lalr1.html |date=May 7, 2021 |title=LALR(1) tutorial}}, a flash card-like tutorial on एलएएलआर(1) parsing.


{{Parsers}}
{{Parsers}}

Revision as of 23:29, 3 August 2023

अभिकलित्र विज्ञान में, एक एलएएलआर पार्सर[lower-alpha 1] या लुक-अहेड, लेफ्ट-टू-राइट, राइटमोस्ट व्युत्पत्ति पार्सर संकलन प्रक्रिया का हिस्सा है जहाँ मानव पठनीय पाठ को अभिकलित्र निर्देशों में परिवर्तित किया जाता है। एलएएलआर पार्सर एक सॉफ्टवेयर टूल है जो कोड को एक बहुत ही विशिष्ट आंतरिक प्रतिनिधित्व में संसाधित (पार्स) करता है जिससे कंपाइलर काम कर सकता है। यह अभिकलित्र भाषा के लिए औपचारिक व्याकरण द्वारा निर्दिष्ट उत्पादन (अभिकलित्र विज्ञान) के एक सेट के अनुसार होता है।

एलएएलआर पार्सर एक कैनोनिकल एलआर पार्सर का सरलीकृत संस्करण है।

एलएएलआर पार्सर का आविष्कार फ्रैंक डेरेमर ने अपने 1969 के पीएचडी शोध प्रबंध, एलआर(के) भाषाओं के लिए व्यावहारिक अनुवादक में किया था।[1]एलआर(1) पार्सर्स को लागू करने के उस समय की व्यावहारिक कठिनाइयों के उपचार में उन्होंने दिखाया कि एलएएलआर पार्सर में एलआर (0) पार्सर की तुलना में अधिक भाषा पहचान शक्ति है, जबकि एक भाषा के लिए एलआर (0) पार्सर के समान अवस्था की आवश्यकता होती है जिसे दोनों पार्सर्स द्वारा पहचाना जा सकता है। यह एलएएलआर पार्सर को एलएएलआर वाली भाषाओं के लिए एलआर(1) पार्सर का एक मेमोरी-कुशल विकल्प बनाता है। यह भी सिद्ध हुआ कि ऐसी एलआर(1) भाषाएँ मौजूद हैं जो एलएएलआर नहीं हैं। इस कमजोरी के बावजूद, एलएएलआर पार्सर की शक्ति कई मुख्यधारा की अभिकलित्र भाषाओं के लिए पर्याप्त है,[2] जावा प्रौद्योगिकी सहित,[3] हालाँकि कई भाषाओं के संदर्भ व्याकरण अस्पष्ट व्याकरण होने के कारण एलएएलआर होने में विफल रहते हैं।[2]

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

इतिहास

1965 में, डोनाल्ड नुथ ने एलआर पार्सर (लेफ्ट-टू-राइट, राइटमोस्ट व्युत्पत्ति) का आविष्कार किया। एलआर पार्सर किसी भी नियतात्मक संदर्भ-मुक्त भाषा को रैखिक-बद्ध समय में पहचान सकता है।[6] सबसे दाईं ओर की व्युत्पत्ति में बहुत बड़ी मेमोरी आवश्यकताएं होती हैं और उस समय स्मृति सीमित मेमोरी के कारण एलआर पार्सर को लागू करना अव्यावहारिक था। इस कमी को दूर करने के लिए, 1969 में, फ्रैंक डीरेमर ने एलआर पार्सर के दो सरलीकृत संस्करण प्रस्तावित किए, अर्थात् लुक-अहेड एलआर (एलएएलआर)[1] और एसएलआर पार्सर जिसमें कम भाषा-पहचान शक्ति की कीमत पर बहुत कम मेमोरी आवश्यकताएं थीं, एलएएलआर पार्सर सबसे शक्तिशाली विकल्प था।[1] 1977 में, एलआर पार्सर के लिए मेमोरी ऑप्टिमाइज़ेशन का आविष्कार किया गया था[7] लेकिन फिर भी एलआर पार्सर सरलीकृत विकल्पों की तुलना में कम मेमोरी-कुशल था।

1979 में, फ्रैंक डेरेमर और टॉम ब्रश ने एलएएलआर पार्सर के लिए अनुकूलन की एक श्रृंखला की घोषणा की जो इसकी मेमोरी दक्षता में और सुधार करेगी।[8] उनका काम 1982 में प्रकाशित हुआ था।[5]


सिंहावलोकन

आम तौर पर, एलएएलआर पार्सर एलएएलआर(1) पार्सर को संदर्भित करता है,[lower-alpha 2] जिस तरह एलआर पार्सर आम तौर पर एलआर(1) पार्सर को संदर्भित करता है। (1) पार्सिंग के दौरान नियम पैटर्न के बीच अंतर को हल करने के लिए एक-टोकन लुकअहेड को दर्शाता है। इसी तरह, दो-टोकन लुकअप के साथ एक एलएएलआर (2) पार्सर और के-टोकन लुकअप के साथ एलएएलआर (के) पार्सर हैं, लेकिन ये वास्तविक उपयोग में दुर्लभ हैं। एलएएलआर पार्सर एलआर(0) पार्सर पर आधारित है, इसलिए इसे एलएएलआर(1) = एलए(1)एलआर(0) (लुकहेड का 1 टोकन, एलआर(0)) या अधिक सामान्यतः एलएएलआर(k) = एलए(k)एलआर(0) (लुकहेड का k टोकन, एलआर(0)) भी दर्शाया जा सकता है। वास्तव में j और k के सभी संयोजनों के लिए एलए(k)एलआर(j) पार्सर का एक दो-पैरामीटर परिवार है, जिसे एलआर(j + k) पार्सर से प्राप्त किया जा सकता है,[9] लेकिन इनका व्यावहारिक उपयोग नजर नहीं आता है।

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

अन्य पार्सर्स से संबंध

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

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

एलआर (1) व्याकरण का मानक उदाहरण जिसे एलएएलआर (1) पार्सर के साथ पार्स नहीं किया जा सकता है, जो इस तरह के कम/घटाने वाले संघर्ष को प्रदर्शित करता है, वह है:[10][11] एस → ए ई सी 

   S → a E c

    → a F d
    → b F c
    → b E d
  E → e

  F → e

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

  E → e. {c,d}

  F → e. {c,d}

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

पुनर्प्राप्त करने के लिए, इस अस्पष्टता को E चुनकर हल किया जाता है, क्योंकि यह व्याकरण में F से पहले आता है। हालाँकि, परिणामी पार्सर वैध इनपुट अनुक्रम को पहचानने में सक्षम नहीं होगा b e c, अस्पष्ट अनुक्रम के बाद से e c को कम कर दिया गया है (E → e) c, बजाय सही के (F → e) c, लेकिन b E c व्याकरण में नहीं है.

एलएल पार्सर्स

एलएएलआर(j) पार्सर एलएल पार्सर एलएल(k) पार्सर के साथ अतुलनीय हैं: किसी भी j और k दोनों के लिए 0 से अधिक, एलएएलआर(j) व्याकरण हैं जो एलएल व्याकरण नहीं हैं। एलएल(k) व्याकरण और इसके विपरीत। वास्तव में, यह अनिर्णीत है कि दिया गया LL(1) व्याकरण किसी के लिए एलएएलआर(k) है या नहीं है।[2]

खाली व्युत्पत्तियों की उपस्थिति के आधार पर, एक एलएल(1) व्याकरण एक एसएलआर(1) या एक एलएएलआर(1) व्याकरण के बराबर हो सकता है। यदि एलएल(1) व्याकरण में कोई खाली व्युत्पत्ति नहीं है तो यह एसएलआर(1) है और यदि खाली व्युत्पत्ति वाले सभी प्रतीकों में गैर-रिक्त व्युत्पत्ति है तो यह एलएएलआर(1) है। यदि केवल खाली व्युत्पत्ति वाले प्रतीक मौजूद हैं, तो व्याकरण एलएएलआर(1) हो भी सकता है और नहीं भी।[12]


यह भी देखें

टिप्पणियाँ

  1. ↑ "LALR" is pronounced as the initialism "el-ay-el-arr"
  2. ↑ "LALR(1)" is pronounced as the initialism "el-ay-el-arr-one"


संदर्भ

  1. ↑ 1.0 1.1 1.2 DeRemer 1969.
  2. ↑ 2.0 2.1 2.2 LR Parsing: Theory and Practice, Nigel P. Chapman, p. 86–87
  3. ↑ "Generate the Parser". Eclipse JDT Project. Retrieved 29 June 2012.
  4. ↑ Anderson, T.; Eve, J.; Horning, J. (1973). "कुशल एलआर(1) पार्सर". Acta Informatica (2): 2–39.
  5. ↑ 5.0 5.1 DeRemer, Frank; Pennello, Thomas (October 1982). "एलएएलआर(1) लुक-अहेड सेट की कुशल गणना" (PDF). ACM Transactions on Programming Languages and Systems. 4 (4): 615–649. doi:10.1145/69622.357187.
  6. ↑ Knuth, D. E. (July 1965). "भाषाओं के बाएँ से दाएँ अनुवाद पर" (PDF). Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2. Archived from the original (PDF) on 15 March 2012. Retrieved 29 May 2011.
  7. ↑ Pager, D. (1977), "A Practical General Method for Constructing LR(k) Parsers", Acta Informatica 7, vol. 7, no. 3, pp. 249–268, doi:10.1007/BF00290336
  8. ↑ Frank DeRemer, Thomas Pennello (1979), "Efficient Computation of LALR(1) Look-Ahead Sets", Sigplan Notices - SIGPLAN, vol. 14, no. 8, pp. 176–187
  9. ↑ Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs, "9.7 LALR(1)", p. 302
  10. ↑ "7.9 LR(1) but not LALR(1) Archived 4 August 2010 at the Wayback Machine", CSE 756: Compiler Design and Implementation Archived 23 July 2010 at the Wayback Machine, Eitan Gurari, Spring 2008
  11. ↑ "Why is this LR(1) grammar not LALR(1)?"
  12. ↑ (Beatty 1982)


बाहरी संबंध

  • Parsing Simulator This simulator is used to generate parsing tables एलएएलआर and resolve the exercises of the book.
  • JS/CC JavaScript based implementation of a एलएएलआर(1) parser generator, which can be run in a web-browser or from the command-line.
  • LALR(1) tutorial at the Wayback Machine (archived May 7, 2021), a flash card-like tutorial on एलएएलआर(1) parsing.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एलएएलआर_पार्सर&oldid=241355’