首先,语法本身不是自上而下或自下而上的,parser是(尽管有些语法可以被一种语法解析,但不能被另一种语法解析)。
从实践的角度来看,主要区别在于大多数手写解析器是自上而下的,而更大比例的机器生成的解析器是自下而上的(当然,相反也是可能的)。
自上而下的解析器通常使用递归下降,这通常意味着类似这样的结构(使用典型的数学表达式作为示例):
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 / * + * +