व्याकरण रूपांतरण और प्रेडिक्टिव पार्सिंग (Grammar Transformations & Predictive Parsing)

कंपाइलर के Syntax Analysis चरण में, व्याकरण (Grammar) को इस प्रकार रूपांतरित किया जाता है कि वह आसानी से पार्स (Parse) किया जा सके। यदि किसी Grammar में Left Recursion या Ambiguity हो, तो उसे Transform किया जाता है ताकि पार्सिंग बिना Backtracking के की जा सके। इसके बाद Predictive Parsing (LL(1) Parsing) लागू किया जाता है, जो सबसे तेज़ और प्रभावी Top-Down Parsing तकनीक है।

📘 Grammar Transformation क्या है?

Grammar Transformation का उद्देश्य Grammar को इस रूप में बदलना है कि Parser उसे आसानी से process कर सके। यह मुख्य रूप से दो कार्यों में किया जाता है:

• 1️⃣ Left Recursion को हटाना
• 2️⃣ Left Factoring करना

⚙️ Left Recursion Removal (बाएँ पुनरावृत्ति हटाना)

Left Recursion तब होती है जब कोई non-terminal स्वयं को अपनी production के बाएँ ओर reference करता है। यह Recursive Descent Parser में infinite recursion का कारण बनती है।

उदाहरण:

E → E + T | T

यह Left Recursive Grammar है क्योंकि E → E + T अपने आप को फिर से reference कर रहा है। इसे हटाने के लिए हम इसे निम्न प्रकार से transform करते हैं:

Transformation:

E → T E'
E' → + T E' | ε

अब यह grammar Left Recursion से मुक्त है और Predictive Parsing के लिए उपयुक्त है।

🧩 Left Factoring (लेफ्ट फैक्टोरिंग)

जब किसी grammar में ambiguity होती है या जब दो या अधिक productions की शुरुआत समान होती है, तो parser को निर्णय लेने में कठिनाई होती है कि कौन सा rule लागू करना है। इसे हल करने के लिए Left Factoring का उपयोग किया जाता है।

उदाहरण:

S → if E then S else S | if E then S

यहाँ ambiguity है। इसे left factoring द्वारा ठीक किया जा सकता है:

Transformation:

S → if E then S S'
S' → else S | ε

📗 Predictive Parsing क्या है?

Predictive Parsing एक non-backtracking parsing तकनीक है जो grammar rules और lookahead symbol के आधार पर निर्णय लेती है। इसे LL(1) Parsing भी कहा जाता है।

• 🔹 L → Input को Left से पढ़ना।
• 🔹 L → Leftmost derivation बनाना।
• 🔹 1 → एक lookahead symbol का उपयोग करना।

🧮 LL(1) Parsing Table Construction:

Predictive Parser FIRST और FOLLOW sets का उपयोग करके Parsing Table बनाता है।

Algorithm:

1. प्रत्येक non-terminal के FIRST set निकालें।
2. प्रत्येक non-terminal के FOLLOW set निकालें।
3. Parsing Table बनाएं।
4. Parsing के दौरान stack और input की तुलना करें।

📊 Example Grammar:

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

FIRST Sets:

FIRST(E) = ( , id
FIRST(E') = + , ε
FIRST(T) = ( , id
FIRST(T') = * , ε
FIRST(F) = ( , id

FOLLOW Sets:

FOLLOW(E) = ) , $
FOLLOW(E') = ) , $
FOLLOW(T) = + , ) , $
FOLLOW(T') = + , ) , $
FOLLOW(F) = * , + , ) , $

📘 LL(1) Parsing Table (Simplified):

Non-Terminal	Input Symbol	Production
E	(, id	E → T E'
E'	+	E' → + T E'
E'	) , $	E' → ε
T	(, id	T → F T'
T'	*	T' → * F T'
T'	+ , ) , $	T' → ε
F	(	F → (E)
F	id	F → id

📗 Predictive Parsing Algorithm (Stack-Based):

1. Initialize stack with $S
2. Read next input symbol
3. If top of stack = input → pop and advance
4. Else if top is non-terminal → replace using parsing table entry
5. Else error
6. Repeat until stack empty and input = $

📘 उदाहरण (Example Parsing):

Input: id + id * id

Derivation Steps:

Stack       | Input         | Action
-----------------------------------------
$E           | id + id * id$ | E → T E'
$E' T        | id + id * id$ | T → F T'
$E' T' F     | id + id * id$ | F → id
...
✅ Successfully Parsed

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

• 🔹 AI-driven Parser Generators (ANTLR, LLGen)।
• 🔹 Dynamic LL(k) Parsing with adaptive lookahead।
• 🔹 Cloud-based Parsing Tools for language design।

📙 निष्कर्ष:

Grammar Transformations और Predictive Parsing Compiler Design में सबसे महत्वपूर्ण हैं। Left Recursion और Ambiguity को दूर करके हम Grammar को LL(1) Parser के लिए उपयुक्त बना सकते हैं। 2025 में Predictive Parsing AI और Cloud Tools के साथ और अधिक बुद्धिमान व तेज़ हो गया है।