Грамматика: разница между сверху вниз и снизу вверх? - PullRequest
Новая
       63

Грамматика: разница между сверху вниз и снизу вверх?

6 голосов
/ 06 июля 2010

В чем разница между грамматикой сверху вниз и снизу вверх?Пример был бы потрясающим.

Ответы [ 2 ]

8 голосов
/ 06 июля 2010

Прежде всего, сама грамматика не сверху вниз или снизу вверх, синтаксический анализатор (хотя есть грамматики, которые могут быть проанализированы одной, но не другой).

С практической точки зрения основное отличие состоит в том, что большинство рукописных синтаксических анализаторов являются нисходящими, тогда как гораздо больший процент генерируемых машиной синтаксических анализаторов являются восходящими (хотя, конечно, обратное, безусловно, возможно).

В синтаксическом анализаторе сверху вниз обычно используется рекурсивный спуск, что обычно означает структуру, подобную этой (используя типичные математические выражения в качестве примера): 

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;
}

Обратите внимание, что лексизм здесь довольно глупый (он в основном просто принимает один символ в качестве токена) и допустимые выражения весьма ограничены (только + - * /). ОТО, это достаточно хорошо для обработки ввода, как:

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

из которого он производит то, что я считаю правильным выводом:

1 2 3 4 5 6 / * + * +

4 голосов
/ 06 июля 2010

Afaik, это не имеет никакого значения для самой грамматики, но делает для синтаксического анализатора.

В Википедии есть довольно длинное объяснение обоих снизу вверх и синтаксический анализ сверху вниз .

Обычно (imho) более интуитивно понятный способ - сверху вниз.Вы начинаете с начального символа и применяете подходящие правила преобразования, в то время как снизу вверх вам нужно применять правила преобразования в обратном направлении (которые обычно вызывали у меня головную боль).

...