टॉप-डाउन पार्सिंग क्या है? | 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 का उदाहरण:

नॉन-टर्मिनल id + $
E E → T + E E → T
T T → id

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)

विशेषता टॉप-डाउन पार्सिंग बॉटम-अप पार्सिंग
व्युत्पत्ति **Leftmost Derivation** का अनुसरण करता है। **Rightmost Derivation in Reverse** का अनुसरण करता है।
पार्स ट्री निर्माण रूट से शुरू होता है और लीफ नोड्स तक जाता है। लीफ नोड्स से शुरू होता है और रूट तक जाता है।
एप्रोच Recursive Descent या Predictive Parsing Shift-Reduce या LR Parsing
उदाहरण LL(1) पार्सर LR(0), SLR(1), LALR(1) पार्सर

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** को सीधे संभाल नहीं सकता।

Related Post

Comments

Comments