语法：自上而下和自下而上的区别？

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

请注意，这里的词法分析非常愚蠢（它基本上只接受单个字符作为标记）和表达式允许的数量非常有限（仅+-*/）。 OTOH，它足以处理如下输入：

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

从中它确实会产生我认为正确的输出：

1 2 3 4 5 6 / * + * +

Answer 2

据我所知，它对语法本身没有任何影响，但对解析器有任何影响。

维基百科对 bottom-up 和 自顶向下解析。

一般来说（恕我直言）更直观的方法是自上而下。您从开始符号开始并应用适合的转换规则，而自下而上则需要向后应用转换规则（这通常让我很头疼）。