6

トップダウン文法とボトムアップ文法の違いは何ですか? 例は素晴らしいでしょう。

4

2 に答える 2

8

まず第一に、文法自体はトップダウンでもボトムアップでもなく、パーサーはそうです (ただし、一方では解析できても他方では解析できない文法があります)。

実際的な観点から見ると、主な違いは、ほとんどの手書きパーサーがトップダウンであるのに対し、機械で生成されたパーサーのはるかに多くの割合がボトムアップであるということです (もちろん、その逆は確かに可能です)。

トップダウン パーサーは通常、再帰的降下を使用します。これは通常、次のような構造を意味します (例として典型的な数式を使用)。

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 文字をトークンとして受け入れるだけです)、許可される式はかなり制限されています (+-*/ のみ)。OTOH、次のような入力を処理するのに十分です：

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

そこから、正しい出力であると私が信じているものが生成されます。

1 2 3 4 5 6 / * + * +

于 2010-07-05T20:42:28.567 に答える
4

私の知る限り、文法自体には何の違いもありませんが、パーサーには違いがあります。

ウィキペディアには、ボトムアップ解析とトップダウン解析の両方について非常に長い説明があります。

一般的に、(imho) より直感的な方法はトップダウンです。開始記号から始めて、適合する変換ルールを適用しますが、ボトムアップでは、変換ルールを逆方向​​に適用する必要があります(これは通常、私にとってかなりの頭痛の種でした)。

于 2010-07-05T20:28:53.110 に答える