LR Parsers (SLR, LALR, LR) in Compiler Design in Hindi - एलआर पार्सर क्या है?


LR पार्सर क्या है? (What is LR Parser?)

LR पार्सर (LR Parser) बॉटम-अप पार्सिंग की एक उन्नत तकनीक है, जो सिंटैक्स एनालिसिस के लिए उपयोग की जाती है। LR का पूरा नाम Left to Right, Rightmost Derivation in Reverse है। यह पार्सर शिफ्ट-रिड्यूस पार्सिंग पर आधारित होता है और इसे डेटा ड्रिवन पार्सिंग भी कहा जाता है।

LR पार्सर के प्रकार (Types of LR Parsers)

LR पार्सर के मुख्यतः तीन प्रकार होते हैं:

LR पार्सर का नामविवरण
SLR (Simple LR)यह सबसे सरल प्रकार का LR पार्सर है, जिसमें फॉलो सेट का उपयोग करके पार्सिंग टेबल तैयार की जाती है।
LALR (Look-Ahead LR)यह SLR पार्सर से अधिक शक्तिशाली होता है, और इसमें LR(1) पार्सर की क्षमता को कम स्टेट्स में संयोजित किया जाता है।
CLR (Canonical LR)यह सबसे शक्तिशाली और विस्तृत प्रकार का LR पार्सर होता है, जिसमें पूरी तरह से LR(1) तकनीक का उपयोग किया जाता है।

SLR पार्सर (Simple LR Parser)

  • यह सबसे सरल प्रकार का LR पार्सर होता है।
  • यह फॉलो सेट का उपयोग करके पार्सिंग टेबल बनाता है।
  • इसका उपयोग छोटे और सिंपल व्याकरणों (Grammar) के लिए किया जाता है।
  • यह कुछ जटिल व्याकरणों के लिए शिफ्ट-रिड्यूस और रिड्यूस-रिड्यूस संघर्ष (Conflict) उत्पन्न कर सकता है।

LALR पार्सर (Look-Ahead LR Parser)

  • यह SLR पार्सर से अधिक शक्तिशाली होता है।
  • इसमें LR(1) पार्सर की क्षमता होती है लेकिन कम स्टेट्स में।
  • यह बहुत से प्रोग्रामिंग लैंग्वेज कंपाइलर्स में उपयोग किया जाता है।
  • इसमें SLR पार्सर की तुलना में कम मेमोरी की आवश्यकता होती है।

CLR पार्सर (Canonical LR Parser)

  • यह सबसे शक्तिशाली प्रकार का LR पार्सर है।
  • इसमें प्रत्येक आइटम के लिए लुक-अहेड का उपयोग किया जाता है।
  • इसमें बहुत अधिक संख्या में स्टेट्स होते हैं, जिससे मेमोरी की आवश्यकता अधिक होती है।
  • इसका उपयोग बड़े और जटिल व्याकरणों (Grammar) के लिए किया जाता है।

LR पार्सर के चरण (Steps of LR Parsing)

LR पार्सर निम्नलिखित चरणों में कार्य करता है:

  1. शिफ्ट (Shift): इनपुट से एक टोकन स्टैक में जोड़ा जाता है।
  2. रिड्यूस (Reduce): स्टैक में मौजूद टोकन को नॉन-टर्मिनल में बदल दिया जाता है।
  3. स्वीकृति (Accept): यदि पूरी स्ट्रिंग सही पार्स हो जाती है, तो इसे स्वीकार कर लिया जाता है।
  4. त्रुटि (Error): यदि इनपुट व्याकरण से मेल नहीं खाता, तो त्रुटि उत्पन्न होती है।

LR पार्सर का उपयोग (Applications of LR Parsing)

  • प्रोग्रामिंग लैंग्वेज के कम्पाइलर में।
  • कृत्रिम बुद्धिमत्ता (Artificial Intelligence) में।
  • डेटाबेस क्वेरी प्रोसेसिंग में।
  • स्वचालित भाषा प्रोसेसिंग (Automated Language Processing) में।

निष्कर्ष (Conclusion)

LR पार्सर एक शक्तिशाली बॉटम-अप पार्सिंग तकनीक है, जिसमें तीन मुख्य प्रकार होते हैं: SLR, LALR, और CLR। यह कम्पाइलर डिजाइन में महत्वपूर्ण भूमिका निभाता है और जटिल व्याकरणों को भी प्रभावी ढंग से पार्स कर सकता है।

Related Post