एलआर पार्सर्स (LR Parsers) - SLR, LALR और Canonical LR

LR Parsers Compiler Design में सबसे शक्तिशाली और व्यापक रूप से प्रयोग की जाने वाली Bottom-Up Parsing तकनीकें हैं। ये पार्सर्स बड़े और जटिल प्रोग्रामिंग भाषाओं की syntactic संरचना को बिना ambiguity और backtracking के पहचानने में सक्षम होते हैं।

📘 LR Parser क्या है?

LR Parser का अर्थ है – Left-to-right scan और Rightmost derivation in reverse। यह parser input को बाएँ से पढ़ता है और grammar rules को नीचे से ऊपर (Bottom-Up) लागू करता है। यह technique deterministic parsing के लिए उपयोग की जाती है।

मुख्य विशेषताएँ:

• 🔹 Non-backtracking parsing method।
• 🔹 Error detection के लिए अत्यधिक सक्षम।
• 🔹 सभी programming languages के लिए उपयुक्त।

⚙️ LR Parsing का कार्य सिद्धांत:

LR Parser दो मुख्य डेटा संरचनाओं का उपयोग करता है:

• 1️⃣ Stack: Symbols (terminals और non-terminals) को store करता है।
• 2️⃣ Input Buffer: Tokens को रखता है।

LR Parsing Steps:

1. Input को बाएँ से पढ़ा जाता है।
2. Stack में symbols push किए जाते हैं (Shift Operation)।
3. जब grammar rule match हो, तब reduction की जाती है (Reduce Operation)।
4. Parsing तब समाप्त होती है जब start symbol stack में रह जाए और input समाप्त हो जाए।

📗 LR Parser के प्रकार:

• 1️⃣ SLR Parser (Simple LR)
• 2️⃣ LALR Parser (Look-Ahead LR)
• 3️⃣ Canonical LR Parser

🧩 1️⃣ SLR Parser (Simple LR Parser)

SLR Parser सबसे सरल प्रकार का LR Parser है। यह FOLLOW sets का उपयोग करके parsing table बनाता है।

निर्माण प्रक्रिया:

1. Grammar को augmented form में बदलें (नया start symbol जोड़ें)।
2. LR(0) items बनाएँ।
3. Canonical Collection of LR(0) items तैयार करें।
4. Parsing Table (ACTION और GOTO) बनाएं।
5. Parsing करें और stack की स्थिति के अनुसार actions लें।

📘 उदाहरण:

Grammar:
S' → S
S → C C
C → c C | d

Input: cdcd

SLR Table Entries:

• ACTION Table → Shift, Reduce, Accept operations।
• GOTO Table → State transitions।

🧮 Limitations:

• ❌ Ambiguous grammars को handle नहीं कर सकता।
• ❌ कुछ conflicts (shift/reduce) हो सकते हैं।

🧠 2️⃣ LALR Parser (Look-Ahead LR)

LALR Parser SLR Parser से अधिक powerful होता है। यह same states को merge करता है लेकिन lookahead symbols को ध्यान में रखता है।

मुख्य विशेषताएँ:

• 🔹 अधिक compact parsing table।
• 🔹 अधिकांश conflicts समाप्त हो जाते हैं।
• 🔹 LALR Parser आधुनिक compilers (जैसे GCC, Java) में उपयोग किया जाता है।

📗 निर्माण प्रक्रिया:

1. SLR Parser की तरह LR(0) items बनाएँ।
2. LOOKAHEAD symbols को जोड़ें।
3. Similar states को merge करें।
4. Parsing Table तैयार करें।

📘 उदाहरण:

Grammar:

E → E + T | T
T → T * F | F
F → (E) | id

LALR Parser इस grammar के लिए conflict-free table बनाता है, जबकि SLR Parser में shift/reduce conflicts हो सकते हैं।

🚀 3️⃣ Canonical LR Parser

Canonical LR Parser सबसे powerful और precise LR parser है। यह प्रत्येक item set में full lookahead symbols रखता है।

मुख्य विशेषताएँ:

• ✅ सबसे कम conflicts।
• ✅ Deterministic और Accurate parsing।
• ❌ Table बहुत बड़ा होता है।

📗 निर्माण प्रक्रिया:

1. Augmented Grammar तैयार करें।
2. LR(1) Items बनाएँ।
3. Closure और GOTO functions लागू करें।
4. Canonical Collection बनाएं।
5. Parsing Table तैयार करें।

उदाहरण:

Grammar:

S' → S
S → aA | bB
A → c
B → d

Canonical LR Parser प्रत्येक state के लिए lookahead maintain करता है, जिससे कोई ambiguity नहीं रहती।

🧮 Parsing Table Structure:

LR Parser दो tables का उपयोग करता है:

• ACTION Table: Shift, Reduce, Accept या Error बताता है।
• GOTO Table: Non-terminals के transitions दर्शाता है।

Table Example:

⚙️ Error Detection in LR Parsing:

• 🔹 Immediate detection of syntax errors।
• 🔹 Parser invalid states को reject करता है।
• 🔹 Error recovery के लिए Panic Mode और Phrase-Level Techniques।

🚀 आधुनिक दृष्टिकोण (2025 में LR Parsing):

• 🔹 AI-Optimized LR Parsing – Conflict prediction और grammar correction।
• 🔹 Parallel LR Parsing – Multi-core parsing execution।
• 🔹 Dynamic Parser Generation – Cloud compilers के लिए।

📙 निष्कर्ष:

LR Parsing Compiler Design का सबसे मजबूत और विश्वसनीय भाग है। SLR सरल है, LALR व्यावहारिक और Canonical LR सबसे सटीक है। 2025 में आधुनिक compilers इन तकनीकों को AI और Parallelism के साथ मिलाकर और अधिक सशक्त बना चुके हैं।