5

だから私は言語設計について何ヶ月も研究し、実験してきました.2、3ヶ月前よりもはるかに理解が深まりました. 私はまだいくつかのことについて混乱しています...調査なしでいくつかの悪いパーサーをハッキングしましたが、もっと良いものが必要です。そのため、手動で書くのが最も論理的なものであると読んだので、再帰降下パーサーを作成しようとしています。私の理解では、各ルールは独自の機能に実装されています。前半だけですが… パーサーの仕事は、構文木などを作ることですよね？私もこのトピックを調査しようとしましたが、ツリーが言語でどのように表現されているかの例を見つけることができませんでした. D は私のお気に入りの言語なので、D で書いていますが、

私が見たものの中には、互いに継承するクラスがたくさんあるので、たとえば IfStatement クラスが拡張するステートメント クラスがあるかもしれません。しかし、これらすべてがツリーでどのように表現されているか、または後でそれがどのように移動するかさえ見つけることができませんでした.

誰かが私に例を示したり、これらのことについてもう少し詳しく話したりできれば素晴らしいことです. どんな助けも本当に大きな意味があり、私の好奇心と目標を助けてくれます。よろしくお願いします!

4

1 に答える 1

9

ツリーは通常、その子へのポインターを含む構造体として表され、nodeノード型を格納するメンバーを持っているか、実際の型を導出できるように特定のクラスになっています (つまり、算術式を保持している場合は、 if ステートメント、ループなど)。

あなたが言及したように、簡単な例は確かにifステートメントです。そのためには、次のようにします (疑似 C が続きます)。

enum AST_Node {
    Node_if,
    Node_and,
    Node_or,
    Node_not,
    Node_equal,
    Node_less,
    // etc., other node types follow
};

struct AST {
    struct AST *children[MAX_CHILDREN]; // don't do this
    enum AST_Node node;
};

struct AST *parse_if_statement()
{
    // expect tokens in order
    expect("if");

    // parse condition
    expect("(");
    struct AST *condition = parse_expression();
    expect(")");

    // parse two child statements
    struct AST *then_branch = parse_statement();
    struct AST *else_branch = NULL;
    if (accept("else")) {
        else_branch = parse_statement();
    }

    // create AST, fill in children
    struct AST *if_statement = new_AST_node(Node_if);
    if_statement->children[0] = condition;
    if_statement->children[1] = then_branch;
    if_statement->children[2] = else_branch;

    return if_statement;
}

したがって、基本的には、永続的な字句要素 (「if」、条件を囲む括弧など) を期待/受け入れるだけで、サブツリー (条件と 2 つの分岐) の解析を適切なパーサー関数に渡します。

これがツリーをたどる方法です。基本的には深さ優先のウォークを行い、各子を順番にコンパイルまたは解釈します。次に、現在解釈/コンパイルされているサブツリーのノード タイプが意味する追加のセマンティクスを追加します。

Value *interpret_if_statement(struct AST *ast)
{
    assert(ast->node == Node_if);

    struct AST *condition = ast->children[0];
    struct AST *then_branch = ast->children[1];
    struct AST *else_branch = ast->children[2];

    // evaluate condition
    Value *condval = interpret_expression(condition);

    if (condval->bool_value == TRUE) {
        // if condition is true, interpret "then" branch
        return interpret_statement(then_branch);
    } else if (else_branch != NULL) {
        // otherwise interpret "else" branch, if any
        return interpret_statement(else_branch);
    } else {
        return NULL;
    }
}
于 2013-10-27T17:57:27.337 に答える