एलएएलआर पार्सर
अभिकलित्र विज्ञान में, एक एलएएलआर पार्सर[lower-alpha 1] या लुक-अहेड, लेफ्ट-टू-राइट, राइटमोस्ट व्युत्पत्ति पार्सर संकलन प्रक्रिया का हिस्सा है जहाँ मानव पठनीय पाठ को कंप्यूटर निर्देशों में परिवर्तित किया जाता है। एलएएलआर पार्सर एक सॉफ्टवेयर टूल है जो कोड को एक बहुत ही विशिष्ट आंतरिक प्रतिनिधित्व में संसाधित (पार्स) करता है जिससे कंपाइलर काम कर सकता है। यह अभिकलित्र भाषा के लिए औपचारिक व्याकरण द्वारा निर्दिष्ट उत्पादन (अभिकलित्र विज्ञान) के एक सेट के अनुसार होता है।
एलएएलआर पार्सर एक कैनोनिकल एलआर पार्सर का सरलीकृत संस्करण है।
एलएएलआर पार्सर का आविष्कार फ्रैंक डेरेमर ने अपने 1969 के पीएचडी शोध प्रबंध, एलआर(के) भाषाओं के लिए व्यावहारिक अनुवादक में किया था।[1]एलआर(1) पार्सर्स को लागू करने के उस समय की व्यावहारिक कठिनाइयों के उपचार में। उन्होंने दिखाया कि एलएएलआर पार्सर में एलआर (0) पार्सर की तुलना में अधिक भाषा पहचान शक्ति है, जबकि एक भाषा के लिए एलआर (0) पार्सर के समान राज्यों की आवश्यकता होती है जिसे दोनों पार्सर्स द्वारा पहचाना जा सकता है। यह LALR पार्सर को LALR वाली भाषाओं के लिए LR(1) पार्सर का एक मेमोरी-कुशल विकल्प बनाता है। यह भी सिद्ध हुआ कि ऐसी LR(1) भाषाएँ मौजूद हैं जो LALR नहीं हैं। इस कमजोरी के बावजूद, एलएएलआर पार्सर की शक्ति कई मुख्यधारा की कंप्यूटर भाषाओं के लिए पर्याप्त है,[2] जावा प्रौद्योगिकी सहित,[3] हालाँकि कई भाषाओं के संदर्भ व्याकरण अस्पष्ट व्याकरण होने के कारण LALR होने में विफल रहते हैं।[2]
मूल शोध प्रबंध में औपचारिक व्याकरण दिए गए ऐसे पार्सर के निर्माण के लिए कोई एल्गोरिदम नहीं दिया गया था। एलएएलआर पार्सर पीढ़ी के लिए पहला एल्गोरिदम 1973 में प्रकाशित किया गया था।[4] 1982 में, डीरेमर और टॉम पेनेलो ने एक एल्गोरिदम प्रकाशित किया जो अत्यधिक मेमोरी-कुशल एलएएलआर पार्सर उत्पन्न करता था।[5] एलएएलआर पार्सर स्वचालित रूप से एक व्हाँ रण से एलएएलआर पार्सर जनरेटर जैसे वाईएसीसी या जीएनयू बाइसन द्वारा उत्पन्न किया जा सकता है। परिणामी पार्सर की शक्ति को बढ़ाने के लिए स्वचालित रूप से उत्पन्न कोड को हाथ से लिखे गए कोड द्वारा संवर्धित किया जा सकता है।
इतिहास
1965 में, डोनाल्ड नुथ ने एलआर पार्सर (बाएं से दाएं, सबसे दाहिनी व्युत्पत्ति) का आविष्कार किया। एलआर पार्सर किसी भी नियतात्मक संदर्भ-मुक्त भाषा को रैखिक-बद्ध समय में पहचान सकता है।[6] सबसे दाईं ओर की व्युत्पत्ति में बहुत बड़ी मेमोरी आवश्यकताएं होती हैं और उस समय स्मृति सीमित मेमोरी के कारण एलआर पार्सर को लागू करना अव्यावहारिक था। इस कमी को दूर करने के लिए, 1969 में, फ्रैंक डीरेमर ने एलआर पार्सर के दो सरलीकृत संस्करण प्रस्तावित किए, अर्थात् लुक-अहेड एलआर (एलएएलआर)[1] और एसएलआर पार्सर जिसमें कम भाषा-पहचान शक्ति की कीमत पर बहुत कम मेमोरी आवश्यकताएं थीं, एलएएलआर पार्सर सबसे शक्तिशाली विकल्प था।[1] 1977 में, एलआर पार्सर के लिए मेमोरी ऑप्टिमाइज़ेशन का आविष्कार किया गया था[7] लेकिन फिर भी एलआर पार्सर सरलीकृत विकल्पों की तुलना में कम मेमोरी-कुशल था।
1979 में, फ्रैंक डेरेमर और टॉम ब्रश ने एलएएलआर पार्सर के लिए अनुकूलन की एक श्रृंखला की घोषणा की जो इसकी मेमोरी दक्षता में और सुधार करेगी।[8] उनका काम 1982 में प्रकाशित हुआ था।[5]
सिंहावलोकन
आम तौर पर, एलएएलआर पार्सर एलएएलआर(1) पार्सर को संदर्भित करता है,[lower-alpha 2] जिस तरह एलआर पार्सर आम तौर पर एलआर(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) पार्सर से प्राप्त किया जा सकता है,[9] लेकिन इनका व्यावहारिक उपयोग नजर नहीं आता.
अन्य प्रकार के एलआर पार्सर्स की तरह, एक एलएएलआर पार्सर इनपुट स्ट्रीम पर एक बाएं से दाएं स्कैन में एकल सही नीचे से ऊपर का विश्लेषण | बॉटम-अप पार्स को खोजने में काफी कुशल है, क्योंकि इसमें बैक ट्रैकिंग का उपयोग करने की आवश्यकता नहीं होती है। परिभाषा के अनुसार एक लुकहेड पार्सर होने के नाते, यह हमेशा एक लुकहेड का उपयोग करता है LALR(1) सबसे आम मामला है।
अन्य पार्सर्स से संबंध
एलआर पार्सर्स
एलएएलआर(1) पार्सर एलआर(1) पार्सर से कम शक्तिशाली है, और एसएलआर(1) पार्सर से अधिक शक्तिशाली है, हालांकि वे सभी एक ही औपचारिक व्याकरण #व्याकरण के वाक्यविन्यास का उपयोग करते हैं। एलएएलआर पार्सर द्वारा प्रस्तुत सरलीकरण में समान कर्नेल आइटम सेट वाले विलय नियमों को शामिल किया गया है, क्योंकि एलआर (0) राज्य-निर्माण प्रक्रिया के दौरान लुकहेड्स ज्ञात नहीं हैं। इससे पार्सर की शक्ति कम हो जाती है क्योंकि लुकअहेड प्रतीकों को न जानने से पार्सर भ्रमित हो सकता है कि अगला कौन सा व्याकरण नियम चुनना है, जिसके परिणामस्वरूप टकराव कम/कम हो जाता है। एक स्पष्ट एलआर(1) व्याकरण में एलएएलआर(1) पार्सर को लागू करने में उत्पन्न होने वाले सभी टकराव टकराव को कम/कम करने वाले होते हैं। एसएलआर(1) पार्सर आगे विलय करता है, जो अतिरिक्त टकराव पेश करता है।
एलआर (1) व्याकरण का मानक उदाहरण जिसे एलएएलआर (1) पार्सर के साथ पार्स नहीं किया जा सकता है, जो इस तरह के कम/घटाने वाले संघर्ष को प्रदर्शित करता है, वह है:[10][11] एस → ए ई सी
→ एक एफ डी
→ बी एफ सी
→ बी ई डी
ई → ई
एफ → ई
एलएएलआर तालिका निर्माण में, दो राज्यों को एक राज्य में विलय कर दिया जाएगा और बाद में लुकहेड्स अस्पष्ट पाए जाएंगे। पूर्वानुमानों वाला एक राज्य है:
ई → ई. {सी,डी}
एफ → ई. {सी,डी}
एक LR(1) पार्सर दो अलग-अलग स्थितियाँ बनाएगा (गैर-परस्पर विरोधी लुकहेड्स के साथ), जिनमें से कोई भी अस्पष्ट नहीं है। एलएएलआर पार्सर में इस एक स्थिति में विरोधाभासी क्रियाएं होती हैं (लुकहेड सी या डी, ई या एफ को कम करें), संघर्ष को कम/कम करें; उपरोक्त व्याकरण को एलएएलआर पार्सर जनरेटर द्वारा अस्पष्ट घोषित किया जाएगा और टकराव की सूचना दी जाएगी।
पुनर्प्राप्त करने के लिए, इस अस्पष्टता को E चुनकर हल किया जाता है, क्योंकि यह व्याकरण में F से पहले आता है। हालाँकि, परिणामी पार्सर वैध इनपुट अनुक्रम को पहचानने में सक्षम नहीं होगा b e c, अस्पष्ट अनुक्रम के बाद से e c को कम कर दिया गया है (E → e) c, बजाय सही के (F → e) c, लेकिन b E c व्याकरण में नहीं है.
एलएल पार्सर्स
एलएएलआर(जे) पार्सर एलएल पार्सर|एलएल(के) पार्सर के साथ अतुलनीय हैं: किसी भी जे और के दोनों के लिए 0 से अधिक, एलएएलआर(जे) व्याकरण हैं जो एलएल व्याकरण नहीं हैं|एलएल(के) व्याकरण और इसके विपरीत। वास्तव में, यह अनिर्णीत है कि दिया गया LL(1) व्याकरण किसी के लिए LALR(k) है या नहीं .[2]
खाली व्युत्पत्तियों की उपस्थिति के आधार पर, एक एलएल(1) व्याकरण एक एसएलआर(1) या एक एलएएलआर(1) व्याकरण के बराबर हो सकता है। यदि एलएल(1) व्याकरण में कोई खाली व्युत्पत्ति नहीं है तो यह एसएलआर(1) है और यदि खाली व्युत्पत्ति वाले सभी प्रतीकों में गैर-रिक्त व्युत्पत्ति है तो यह एलएएलआर(1) है। यदि केवल खाली व्युत्पत्ति वाले प्रतीक मौजूद हैं, तो व्याकरण LALR(1) हो भी सकता है और नहीं भी।[12]
यह भी देखें
- पार्सर जनरेटर की तुलना
- प्रसंग-मुक्त व्याकरण
- आगे की ओर देखें (विश्लेषण)
- पार्सर जनरेटर
- टोकन स्कैनर
टिप्पणियाँ
- ↑ "LALR" is pronounced as the initialism "el-ay-el-arr"
- ↑ "LALR(1)" is pronounced as the initialism "el-ay-el-arr-one"
संदर्भ
- ↑ 1.0 1.1 1.2 DeRemer 1969.
- ↑ 2.0 2.1 2.2 LR Parsing: Theory and Practice, Nigel P. Chapman, p. 86–87
- ↑ "Generate the Parser". Eclipse JDT Project. Retrieved 29 June 2012.
- ↑ Anderson, T.; Eve, J.; Horning, J. (1973). "कुशल एलआर(1) पार्सर". Acta Informatica (2): 2–39.
- ↑ 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.
- ↑ 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.
- ↑ 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
- ↑ Frank DeRemer, Thomas Pennello (1979), "Efficient Computation of LALR(1) Look-Ahead Sets", Sigplan Notices - SIGPLAN, vol. 14, no. 8, pp. 176–187
- ↑ Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs, "9.7 LALR(1)", p. 302
- ↑ "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
- ↑ "Why is this LR(1) grammar not LALR(1)?"
- ↑ (Beatty 1982)
- DeRemer, Franklin L. (1969). Practical Translators for LR(k) languages (PDF) (PhD). MIT. Archived from the original (PDF) on 19 August 2013. Retrieved 13 November 2012.
- Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars" (PDF). Journal of the ACM. 29 (4 (Oct)): 1007–1022. doi:10.1145/322344.322350.
बाहरी संबंध
- Parsing Simulator This simulator is used to generate parsing tables LALR and resolve the exercises of the book.
- JS/CC JavaScript based implementation of a LALR(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 LALR(1) parsing.
