语法:自上而下和自下而上的区别?

首先,语法本身不是自上而下或自下而上的, 语法分析器 是的(尽管有些语法可以由一个语法来解析,但另一个语法不能)。

从实践的角度来看,主要的区别在于大多数手工编写的解析器是自顶向下的,而机器生成的解析器中有很大一部分是自底向上的(当然,反过来也是可能的)。

自顶向下的解析器通常使用递归下降,这通常意味着类似这样的结构(以典型的数学表达式为例):

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/*+*+

它对语法本身没有任何影响,但是它 做 对于解析器。

维基百科对两者都有很长的解释 bottom-up 和 top-down parsing .

通常(imho)更直观的方式是自上而下。从开始符号开始,并应用适合的转换规则,而从下至上,则需要应用转换规则。 向后的 (这通常让我很头疼)。