语法:自上而下和自下而上的区别? [英] Grammar: difference between a top down and bottom up?

问题描述

自上而下和自下而上的语法有什么区别?一个例子太棒了.

What is the difference between a top down and bottom up grammar? An example would be awesome.

推荐答案

首先，语法本身不是自上而下或自下而上的， parser 是(尽管有语法可以由一个解析，但不能由另一个解析.)

First of all, the grammar itself isn't top-down or bottom-up, the parser is (though there are grammars that can be parsed by one but not the other).

从实际的角度来看，主要的区别是大多数手写解析器是自上而下的，而更大比例的机器生成的解析器是自下而上的(当然，当然可以相反).

From a practical viewpoint, the main difference is that most hand-written parsers are top-down, while a much larger percentage of machine-generated parsers are bottom-up (though, of course, the reverse is certainly possible).

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

A top-down parser typically uses recursive descent, which typically means a structure something like this (using typical mathematical expressions as an example):

expression() { term() [-+] expression }
term() { factor() [*/] term() }
factor() { operand() | '(' expression() ')' }

自下而上的解析器以相反的方向工作-递归下降解析器从完整表达式开始，然后将其分解成越来越小的片段，直到达到单个令牌的级别为止，自下而上的解析器开始从各个标记中提取出来，并使用规则表，说明这些标记如何与越来越高级别的表达式层次结构配合在一起，直到达到最高级别为止(上面表示为表达式").

A bottom-up parser work in the reverse direction -- where a recursive descent parser starts from the full expression, and breaks it down into smaller and smaller pieces until it reaches the level of individual tokens, a bottom-up parser starts from the individual tokens, and uses tables of rules about how those tokens fit together into higher and higher levels of the expression hierarchy until it reaches the top level (what's represented as "expression" above).

为澄清起见，添加一个真正平凡的解析器也许很有意义.在这种情况下，我将采用将经典数学表达式的简化版本从infix转换为postfix的旧经典方法:

To clarify, perhaps it would make sense to add a really trivial parser. In this case, I'll just do the old classic of converting a simplified version of a typical mathematical expression from infix to 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;
}

请注意，这里的词法很愚蠢(它基本上只接受单个字符作为标记)，并且允许的表达式也很有限(仅+-*/). OTOH，足以处理如下输入:

Note that the lexing here is pretty stupid (it basically just accepts a single character as a token) and the expressions allowed are quite limited (only +-*/). OTOH, it's good enough to handle an input like:

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

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

它确实会产生我认为是正确的输出:

from which it does produce what I believe is correct output:

1 2 3 4 5 6/* + * +

1 2 3 4 5 6 / * + * +

这篇关于语法:自上而下和自下而上的区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！