टॉप-डाउन पार्सिंग क्या है? | Top-Down Parsing in Compiler Design in Hindi

टॉप-डाउन पार्सिंग क्या है? (What is Top-Down Parsing in Compiler Design?)

टॉप-डाउन पार्सिंग (Top-Down Parsing) कंपाइलर डिज़ाइन में उपयोग की जाने वाली **पार्सिंग तकनीक** है, जिसमें पार्स ट्री (Parse Tree) का निर्माण **रूट (Root) से लेकर लीफ (Leaf) नोड तक** किया जाता है। यह विधि स्टार्ट सिंबॉल (Start Symbol) से शुरू होती है और धीरे-धीरे इनपुट स्ट्रिंग का मिलान करके टोकन्स को संसाधित करती है।

1. टॉप-डाउन पार्सिंग की विशेषताएँ (Characteristics of Top-Down Parsing)

• यह **Recursive Descent** या **Predictive Parsing** पर आधारित हो सकती है।
• यह **Leftmost Derivation** (बाएं से दाएं व्युत्पत्ति) का अनुसरण करता है।
• इनपुट स्ट्रिंग के **पहले टोकन्स** से पार्सिंग शुरू होती है।
• यह एक **Predictive Parser Table** का उपयोग कर सकता है।

2. टॉप-डाउन पार्सिंग के प्रकार (Types of Top-Down Parsing)

मुख्य रूप से टॉप-डाउन पार्सिंग को निम्नलिखित दो प्रकारों में विभाजित किया जाता है:

1. रिकर्सिव डिसेंट पार्सिंग (Recursive Descent Parsing)

इस पार्सिंग तकनीक में प्रत्येक नॉन-टर्मिनल (Non-Terminal) के लिए एक **रिकर्सिव फंक्शन** होता है, जो टोकन्स का मिलान करता है और पार्स ट्री का निर्माण करता है।

उदाहरण:

मान लीजिए कि हमारे पास निम्नलिखित व्याकरण (Grammar) है:

E → T + E | T
T → id

यदि इनपुट स्ट्रिंग id + id है, तो रिकर्सिव डिसेंट पार्सिंग निम्नलिखित **रिकर्सिव फंक्शन्स** का उपयोग करेगा:

void E() {
    T();
    if (nextToken == "+") {
        match("+");
        E();
    }
}

void T() {
    match("id");
}

2. प्रिडिक्टिव पार्सिंग (Predictive Parsing)

प्रिडिक्टिव पार्सिंग में **रिकर्सन को हटाकर** **पार्सिंग टेबल** (Parsing Table) का उपयोग किया जाता है। यह **LL(1) Parsing** तकनीक पर आधारित होता है।

Parsing Table का उदाहरण:

3. टॉप-डाउन पार्सिंग के चरण (Steps in Top-Down Parsing)

टॉप-डाउन पार्सिंग को निम्नलिखित चरणों में निष्पादित किया जाता है:

1. **इनपुट स्ट्रिंग** को टोकन्स में विभाजित किया जाता है।
2. **स्टार्ट सिंबॉल** से पार्सिंग शुरू होती है।
3. हर नॉन-टर्मिनल के लिए **रिकर्सिव कॉल या टेबल लुकअप** किया जाता है।
4. इनपुट से मेल खाने वाले टोकन्स को स्वीकार (Accept) किया जाता है।
5. गलत टोकन्स मिलने पर **सिंटैक्स एरर** जनरेट किया जाता है।

4. टॉप-डाउन पार्सिंग का उदाहरण (Example of Top-Down Parsing)

मान लीजिए कि हमें निम्नलिखित व्याकरण (Grammar) को पार्स करना है:

S → a A
A → b | ε

और इनपुट **"ab"** है, तो **टॉप-डाउन पार्सिंग** का निष्पादन कुछ इस प्रकार होगा:

S
|
a   A
    |
    b

5. टॉप-डाउन पार्सिंग बनाम बॉटम-अप पार्सिंग (Top-Down vs Bottom-Up Parsing)

6. टॉप-डाउन पार्सिंग की सीमाएँ (Limitations of Top-Down Parsing)

• यह **Left Recursion** को सीधे तौर पर नहीं संभाल सकता।
• यदि व्याकरण **Ambiguous** है, तो यह सही से कार्य नहीं करता।
• LL(1) व्याकरण में केवल एक टोकन की Lookahead सुविधा होती है।

7. टॉप-डाउन पार्सिंग के फायदे (Advantages of Top-Down Parsing)

• यह **आसान और सरलीकृत** होता है।
• रिकर्सिव डिसेंट पार्सर को **मैन्युअली कोड किया जा सकता है**।
• Predictive Parsing **टेबल-बेस्ड एपरोच** का उपयोग करता है, जिससे यह तेज़ और कुशल होता है।

8. निष्कर्ष (Conclusion)

टॉप-डाउन पार्सिंग कंपाइलर डिज़ाइन की एक महत्वपूर्ण तकनीक है, जिसका उपयोग **लेफ्टमॉस्ट व्युत्पत्ति** (Leftmost Derivation) को लागू करने के लिए किया जाता है। यह **Recursive Descent** और **Predictive Parsing** विधियों के माध्यम से किया जाता है। हालाँकि, यह केवल **LL(1) व्याकरण** के लिए उपयुक्त है और **Left Recursion** को सीधे संभाल नहीं सकता।