व्याकरण: ऊपर और नीचे ऊपर के बीच अंतर?

Question

शीर्ष नीचे और नीचे व्याकरण के बीच क्या अंतर है? एक उदाहरण भयानक होगा।

Answer 1

सबसे पहले, व्याकरण स्वयं ऊपर या नीचे नहीं है, पार्सर है (हालांकि वहां व्याकरण हैं जिन्हें एक द्वारा पार्स किया जा सकता है लेकिन दूसरे नहीं)।

एक व्यावहारिक दृष्टिकोण से, मुख्य अंतर यह है कि अधिकांश हाथ से लिखे गए पार्सर्स टॉप-डाउन होते हैं, जबकि मशीन से उत्पन्न पार्सर्स का एक बड़ा प्रतिशत नीचे-नीचे होता है (हालांकि, निश्चित रूप से, रिवर्स निश्चित रूप से संभव है) ।

एक ऊपर से नीचे पार्सर आम तौर पर पुनरावर्ती वंश, जो आम तौर पर इस तरह की एक संरचना कुछ (एक उदाहरण के रूप ठेठ गणितीय अभिव्यक्ति का उपयोग करते हुए) का अर्थ है उपयोग करता है:

expression() { term() [-+] expression } 
term() { factor() [*/] term() } 
factor() { operand() | '(' expression() ')' } 

विपरीत दिशा में एक नीचे-ऊपर पार्सर काम - - जहां एक रिकर्सिव वंश पार्सर पूर्ण अभिव्यक्ति से शुरू होता है, और इसे छोटे और छोटे टुकड़ों में तोड़ देता है जब तक कि यह व्यक्तिगत टोकन के स्तर तक नहीं पहुंच जाता है, एक तल-अप पार्सर व्यक्तिगत टोकन से शुरू होता है, और नियमों की सारणी का उपयोग करता है कि उन टोकन कैसे अभिव्यक्ति पदानुक्रम के उच्च और उच्च स्तरों में एक साथ फिट होने तक यह शीर्ष स्तर तक पहुंच जाता है (जिसे उपरोक्त "अभिव्यक्ति" के रूप में दर्शाया जाता है)।

संपादित करें: स्पष्टीकरण के लिए, शायद यह वास्तव में मामूली पार्सर जोड़ने का अर्थ होगा। इस मामले में, मैं सिर्फ पोस्टफ़िक्स को इन्फ़िक्स से एक विशिष्ट गणितीय अभिव्यक्ति का एक सरलीकृत संस्करण में परिवर्तित करने का पुराने क्लासिक करेंगे:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

void expression(void); 

void show(int ch) { 
    putchar(ch); 
    putchar(' '); 
} 

int token() { 
    int ch; 
    while (isspace(ch=getchar())) 
     ; 
    return ch; 
} 

void factor() { 
    int ch = token(); 
    if (ch == '(') { 
     expression(); 
     ch = token(); 
     if (ch != ')') { 
      fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch); 
      exit(EXIT_FAILURE); 
     } 
    } 
    else 
     show(ch); 
} 

void term() { 
    int ch; 
    factor(); 
    ch = token(); 
    if (ch == '*' || ch == '/') { 
     term(); 
     show(ch); 
    } 
    else 
     ungetc(ch, stdin); 
} 

void expression() { 
    int ch; 
    term(); 
    ch = token(); 
    if (ch == '-' || ch=='+') { 
     expression(); 
     show(ch); 
    } 
    else 
     ungetc(ch, stdin); 
} 

int main(int argc, char **argv) { 
    expression(); 
    return 0; 
} 

ध्यान दें कि lexing यहाँ बहुत बेवकूफ है (यह मूल रूप से बस एक ही चरित्र को स्वीकार करता है एक टोकन के रूप में) और अनुमत अभिव्यक्ति काफी सीमित हैं (केवल + - * /)। OTOH, यह जैसा एक इनपुट को संभालने के लिए काफी अच्छा है:

1 + 2 * (3 + 4 * (5/6))

जिसमें से यह पैदा करता है कि मैं क्या विश्वास है सही उत्पादन होता है:

1 2 3 4 5 6/* + * +

Answer 2

अफैक यह व्याकरण के लिए कोई फर्क नहीं पड़ता है, लेकिन पार्सर के लिए करता है।

विकिपीडिया में bottom-up और top-down parsing दोनों की काफी लंबी व्याख्या है।

आम तौर पर (imho) अधिक सहज ज्ञान युक्त तरीका शीर्ष-नीचे है। आप प्रारंभ प्रतीक के साथ शुरू करते हैं और फिट नियमों को लागू करते हैं, जबकि नीचे-नीचे आपको रूपांतरण नियम पीछे की ओर (जो आमतौर पर मेरे लिए काफी सिरदर्द पैदा करता है) लागू करने की आवश्यकता होती है।