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