القواعد: الفرق بين أعلى لأسفل وأسفل إلى أعلى؟

Question

ما هو الفرق بين النحوية من أعلى لأسفل وأسفل إلى أعلى؟ مثال سيكون رائعا.

Answer 1

بادئ ذي بدء ، فإن القواعد نفسها ليست من أعلى إلى أسفل أو من أسفل إلى أعلى ، محلل هو (على الرغم من وجود قواعد يمكن تحليلها من قبل واحد ولكن ليس الآخر).

من وجهة نظر عملية ، فإن الفرق الرئيسي هو أن معظم المحللين المكتوبة يدويًا من أعلى إلى أسفل ، في حين أن نسبة أكبر بكثير من المحلات التي تم إنشاؤها بواسطة الرشاشات هي من القاعدة إلى القمة (على الرغم من ذلك ، بالطبع ، فإن العكس ممكن بالتأكيد).

يستخدم محلل من أعلى إلى أسفل عادةً النسب العودية ، مما يعني عادةً وجود بنية مثل هذا (باستخدام تعبيرات رياضية نموذجية كمثال):

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

يعمل محلل محلل من أسفل إلى أعلى في الاتجاه المعاكس-حيث يبدأ محلل النسب المتكرر من التعبير الكامل ، ويقوم بتقسيمه إلى قطع أصغر وأصغر حتى يصل إلى مستوى الرموز الفردية ، يبدأ محلل من القاعدة إلى القمة من الفرد الرموز ، وتستخدم جداول القواعد حول كيفية ملاءمة هذه الرموز مع وجود مستويات أعلى وأعلى من التسلسل الهرمي للتعبير حتى يصل إلى المستوى الأعلى (ما يمثل "تعبير" أعلاه).

تحرير: للتوضيح ، ربما سيكون من المنطقي إضافة محلل تافهة حقًا. في هذه الحالة ، سأقوم فقط بالكلاسيكي القديم المتمثل في تحويل نسخة مبسطة من تعبير رياضي نموذجي من Infix إلى Postfix:

#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

afaik لا يحدث أي فرق بالنسبة للقواعد نفسها ، ولكنها يفعل للمحلل.

ويكيبيديا لديها تفسير طويل جدا لكليهما تصاعدي و من أعلى إلى أسفل.

عموما (IMHO) طريقة أكثر بديهية من أعلى إلى أسفل. تبدأ برمز البدء وتطبيق قواعد التحول التي تناسبها ، بينما تحتاج إلى تطبيق قواعد التحول من أسفل إلى أعلى للخلف (الذي عادة ما خلق صداع تماما بالنسبة لي).