Грамматика: различие между вершиной вниз и вверх дном?
Каково различие между вершиной вниз и восходящей грамматикой? Пример был бы потрясающим.
2 ответа
Во-первых, сама грамматика не нисходящая или восходящая, а парсер (хотя есть грамматики, которые могут быть проанализированы одним, но не другой).
С практической точки зрения, основное отличие состоит в том, что большинство рукописных синтаксических анализаторов работают сверху вниз, в то время как гораздо больший процент машинно-генерируемых синтаксических анализаторов работает снизу вверх (хотя, конечно, возможно обратное).
Нисходящий синтаксический анализатор обычно использует рекурсивный спуск, что обычно означает такую структуру (используя в качестве примера типичные математические выражения):
expression() { term() [-+] expression }
term() { factor() [*/] term() }
factor() { operand() | '(' expression() ')' }
Нисходящий синтаксический анализатор работает в обратном направлении - где рекурсивный спуск синтаксический анализатор начинает с полного выражения и разбивает его на все более мелкие части, пока не достигнет уровня отдельных токенов, восходящий синтаксический анализатор начинает с отдельных токенов и использует таблицы правил о том, как эти токены объединяются в более высокие и более высокие уровни иерархии выражений, пока не достигнут верхний уровень (который представлен выше как «выражение»).
Edit: Для пояснения, возможно, имеет смысл добавить действительно тривиальный синтаксический анализатор.В этом случае я просто сделаю старую классику преобразования упрощенной версии типичного математического выражения из инфикса в постфикс:
#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;
}
Обратите внимание, что лексирование здесь довольно глупое (в основном оно просто принимает один символ в качестве токена) а допустимые выражения весьма ограничены (только + - * /). OTOH, его достаточно, чтобы обрабатывать ввод вроде:
1 + 2 * (3 + 4 * (5/6))
, из которого он действительно производит то, что я считаю правильным выводом:
1 2 3 4 5 6 / * + * +
Afaik это не имеет никакого значения для самой грамматики, но это имеет значение для синтаксического анализатора.
В Википедии есть довольно длинное объяснение как восходящего, так и нисходящего синтаксического анализа.
В целом (имхо) более интуитивный способ - нисходящий. Вы начинаете с начального символа и применяете подходящие правила преобразования, в то время как при разборе снизу вверх вам нужно применять правила преобразования назад (что обычно вызывало у меня головную боль).