टॉप-डाउन पार्सिंग (Top-Down Parsing)

Top-Down Parsing कंपाइलर में उपयोग की जाने वाली parsing तकनीक है, जिसमें parsing प्रक्रिया Parse Tree के रूट (Start Symbol) से शुरू होकर leaves (Terminals) तक जाती है। यह चरण Syntax Analysis का एक भाग है और इसका उपयोग grammar rules के आधार पर कोड की संरचना को समझने में किया जाता है।

📘 Top-Down Parsing क्या है?

Top-Down Parsing का उद्देश्य है — start symbol से शुरू करके input string को grammar rules का उपयोग करते हुए derive करना। यह विधि input को recognize करने के लिए विभिन्न grammar productions को apply करती है।

⚙️ टॉप-डाउन पार्सिंग की प्रक्रिया:

1. Start Symbol से शुरुआत होती है।
2. Grammar के production rules को recursively apply किया जाता है।
3. Derivation तब तक चलता है जब तक input tokens पूरी तरह match न हो जाएं।
4. यदि कोई mismatch होता है, तो backtracking किया जाता है।

उदाहरण:

Grammar:

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

Input: id + id * id

Top-Down Parser E से शुरुआत करता है और grammar rules के अनुसार derivations बनाता है।

🧩 Brute Force Parsing:

Brute Force Parsing सबसे सरल लेकिन अक्षम (inefficient) parsing तकनीक है। इसमें parser हर संभव production rule को apply करता है ताकि वह input से match हो जाए। यह तरीका Backtracking पर आधारित होता है।

📗 विशेषताएँ:

• 🔹 सभी संभावित derivations को आज़माता है।
• 🔹 Efficiency बहुत कम होती है।
• 🔹 Ambiguity और Left Recursion को संभालना मुश्किल होता है।

Algorithm (Brute Force Parsing):

1. Start from the start symbol (S).
2. Replace non-terminals with their productions one by one.
3. If derived string = input → success.
4. Else backtrack and try another rule.

उदाहरण:

Grammar:

S → aSb | ab

Input: aabb

Derivation:

S → aSb → aaSbb → aabb ✅

⚙️ Recursive Descent Parsing:

Recursive Descent Parsing एक structured form है जो recursive functions का उपयोग करके parsing करता है। यह Top-Down Parsing का practical implementation है। हर non-terminal symbol के लिए एक अलग function लिखा जाता है जो उस symbol के grammar rules को handle करता है।

📘 Recursive Descent Parser की विशेषताएँ:

• 🔹 हर non-terminal के लिए एक recursive function।
• 🔹 Predictive parsing के लिए backtracking की आवश्यकता हो सकती है।
• 🔹 Easy to implement but suffers from Left Recursion.

📊 Recursive Descent Parsing Example:

Grammar:

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

Equivalent Recursive Functions:

void E() {
    T();
    if (lookahead == '+') {
        match('+');
        E();
    }
}

void T() {
    F();
    if (lookahead == '*') {
        match('*');
        T();
    }
}

void F() {
    if (lookahead == '(') {
        match('(');
        E();
        match(')');
    } else if (lookahead == 'id') {
        match('id');
    }
}

🧮 Recursive Descent Parsing का Working Example:

Input: id + id * id

Execution Steps:

1. E() → calls T()
2. T() → calls F() → matches id
3. Next token + → calls E() again
4. E() → T() → F() → matches id
5. Next token * → calls T() → matches id

⚠️ Left Recursion Problem:

Recursive Descent Parser Left Recursive Grammar को handle नहीं कर सकता। जैसे:

E → E + T | T

यह grammar infinite recursion का कारण बनती है। इसलिए इसे Left Recursion से मुक्त करना आवश्यक है।

Left Recursion Removal:

Original Grammar:

E → E + T | T

Transformed Grammar:

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

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

• 🔹 AI-assisted grammar analyzers (ANTLR, PEG.js)।
• 🔹 Predictive Recursive Parsers in Compiler AI Engines।
• 🔹 Error-tolerant Recursive Parsing used in IDEs।

📙 निष्कर्ष:

Top-Down Parsing प्रोग्राम की संरचना को ऊपर से नीचे तक पहचानने की प्रक्रिया है। Brute Force Parsing सैद्धांतिक है जबकि Recursive Descent Parsing इसका व्यावहारिक रूप है। 2025 में, इन तकनीकों का उपयोग आधुनिक compilers और AI-driven parser systems में व्यापक रूप से किया जा रहा है।