Bagaimana tepatnya Pohon Sintaksis Abstrak dibuat?

Saya pikir saya mengerti tujuan AST, dan saya telah membangun beberapa struktur pohon sebelumnya, tetapi tidak pernah AST. Saya sebagian besar bingung karena node adalah teks dan bukan angka, jadi saya tidak bisa memikirkan cara yang bagus untuk memasukkan token / string karena saya parsing beberapa kode.

Sebagai contoh, ketika saya melihat diagram AST, variabel dan nilainya adalah node daun untuk tanda yang sama. Ini masuk akal bagi saya, tetapi bagaimana saya bisa menerapkan ini? Saya kira saya bisa melakukannya satu per satu, sehingga ketika saya menemukan "=" Saya menggunakannya sebagai simpul, dan menambahkan nilai yang diuraikan sebelum "=" sebagai daun. Kelihatannya salah, karena saya mungkin harus membuat case untuk banyak hal, tergantung pada sintaksisnya.

Dan kemudian saya menemukan masalah lain, bagaimana pohon itu dilalui? Apakah saya pergi jauh-jauh ke ketinggian, dan naik kembali ke simpul ketika saya mencapai bagian bawah, dan melakukan hal yang sama untuk tetangga itu?

Saya telah melihat banyak diagram pada AST, tetapi saya tidak dapat menemukan contoh yang cukup sederhana dari satu dalam kode, yang mungkin akan membantu.

Jawaban singkatnya adalah Anda menggunakan tumpukan. Ini adalah contoh yang baik, tetapi saya akan menerapkannya pada AST.

FYI, ini adalah Algoritma Shunting-Yard milik Edsger Dijkstra .

Dalam hal ini, saya akan menggunakan tumpukan operator dan tumpukan ekspresi. Karena angka dianggap sebagai ekspresi dalam sebagian besar bahasa, saya akan menggunakan tumpukan ekspresi untuk menyimpannya.

class ExprNode:
    char c
    ExprNode operand1
    ExprNode operand2

    ExprNode(char num):
        c = num
        operand1 = operand2 = nil

    Expr(char op, ExprNode e1, ExprNode e2):
        c = op
        operand1 = e1
        operand2 = e2

# Parser
ExprNode parse(string input):
    char c
    while (c = input.getNextChar()):
        if (c == '('):
            operatorStack.push(c)

        else if (c.isDigit()):
            exprStack.push(ExprNode(c))

        else if (c.isOperator()):
            while(operatorStack.top().precedence >= c.precedence):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            operatorStack.push(c)

        else if (c == ')'):
            while (operatorStack.top() != '('):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            # Pop the '(' off the operator stack.
            operatorStack.pop()

        else:
            error()
            return nil

    # There should only be one item on exprStack.
    # It's the root node, so we return it.
    return exprStack.pop()

(Harap bersikap baik tentang kode saya. Saya tahu itu tidak kuat; itu hanya seharusnya pseudocode.)

Bagaimanapun, seperti yang Anda lihat dari kode, ekspresi sewenang-wenang dapat menjadi operan ke ekspresi lain. Jika Anda memiliki input berikut:

5 * 3 + (4 + 2 % 2 * 8)

kode yang saya tulis akan menghasilkan AST ini:

     +
    / \
   /   \
  *     +
 / \   / \
5   3 4   *
         / \
        %   8
       / \
      2   2

Dan kemudian ketika Anda ingin menghasilkan kode untuk AST itu, Anda melakukan Traversal Post Order Tree . Ketika Anda mengunjungi simpul daun (dengan angka), Anda menghasilkan konstanta karena kompiler perlu mengetahui nilai operan. Ketika Anda mengunjungi sebuah simpul dengan operator, Anda menghasilkan instruksi yang sesuai dari operator. Misalnya, operator '+' memberi Anda instruksi "tambah".

Ada perbedaan yang signifikan antara bagaimana AST biasanya digambarkan dalam tes (pohon dengan angka / variabel di node daun dan simbol di node interior) dan bagaimana sebenarnya diterapkan.

Implementasi khas AST (dalam bahasa OO) banyak menggunakan polimorfisme. Node dalam AST biasanya diimplementasikan dengan berbagai kelas, semua berasal dari ASTNodekelas umum . Untuk setiap konstruk sintaksis dalam bahasa yang Anda proses, akan ada kelas untuk mewakili konstruk itu di AST, seperti ConstantNode(untuk konstanta, seperti 0x10atau 42), VariableNode(untuk nama variabel), AssignmentNode(untuk operasi penugasan), ExpressionNode(untuk generik ekspresi), dll.
Setiap jenis simpul spesifik menentukan apakah simpul tersebut memiliki anak, berapa banyak dan mungkin jenis apa. A ConstantNodebiasanya tidak memiliki anak, AssignmentNodeakan memiliki dua dan ExpressionBlockNodedapat memiliki jumlah anak yang banyak.

AST akan dibangun oleh parser, yang tahu apa konstruk yang baru saja diuraikan, sehingga dapat membangun jenis AST Node yang tepat.

Ketika melintasi AST, polimorfisme dari simpul-simpul tersebut benar-benar berperan. Basis ASTNodemendefinisikan operasi yang dapat dilakukan pada node, dan setiap tipe node spesifik mengimplementasikan operasi tersebut dengan cara spesifik untuk konstruksi bahasa tertentu.

Membangun AST dari teks sumber adalah "hanya" parsing . Bagaimana tepatnya itu dilakukan tergantung pada bahasa formal yang diurai dan implementasinya. Anda dapat menggunakan generator parser seperti menhir (untuk Ocaml) , GNU bisondengan flex, atau ANTLR dll. Hal ini sering dilakukan secara "manual" dengan mengkode beberapa parser keturunan rekursif (lihat jawaban ini menjelaskan alasannya). Aspek kontekstual parsing sering dilakukan di tempat lain (tabel simbol, atribut, ....).

Namun, dalam praktiknya AST jauh lebih kompleks daripada apa yang Anda yakini. Misalnya, dalam kompiler seperti GCC , AST menyimpan informasi lokasi sumber dan beberapa informasi pengetikan. Baca tentang Generic Trees di GCC dan lihat di dalamnya gcc / tree.def . BTW, lihat juga di dalam GCC MELT (yang telah saya desain & implementasikan), ini relevan dengan pertanyaan Anda.

Saya tahu pertanyaan ini berumur 4+ tahun tetapi saya merasa saya harus menambahkan jawaban yang lebih terperinci.

Abstrak Sintaksis Pohon dibuat tidak berbeda dari pohon lain; pernyataan yang lebih benar dalam hal ini adalah bahwa node Sintaks Pohon memiliki jumlah node variadic SEPERTI YANG DIPERLUKAN.

Contohnya adalah ekspresi biner seperti Ekspresi 1 + 2 sederhana seperti itu akan membuat simpul akar tunggal memegang simpul kanan dan kiri yang menyimpan data tentang angka-angka. Dalam bahasa C, itu akan terlihat seperti

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod,
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

Pertanyaan Anda juga bagaimana cara melintasi? Traversing dalam hal ini disebut Visiting Nodes . Mengunjungi setiap Node mengharuskan Anda menggunakan setiap jenis simpul untuk menentukan cara mengevaluasi data masing-masing simpul Sintaks.

Berikut ini contoh lain dari itu di C di mana saya cukup mencetak konten dari setiap node:

void AST_PrintNode(const ASTNode *node)
{
    if( !node )
        return;

    char *opername = NULL;
    switch( node->Type ) {
        case AST_IntVal:
            printf("AST Integer Literal - %lli\n", node->Data->llVal);
            break;
        case AST_Add:
            if( !opername )
                opername = "+";
        case AST_Sub:
            if( !opername )
                opername = "-";
        case AST_Mul:
            if( !opername )
                opername = "*";
        case AST_Div:
            if( !opername )
                opername = "/";
        case AST_Mod:
            if( !opername )
                opername = "%";
            printf("AST Binary Expr - Oper: \'%s\' Left:\'%p\' | Right:\'%p\'\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right);
            AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node.
            AST_PrintNode(node->Data->BinaryExpr.right);
            break;
    }
}

Perhatikan bagaimana fungsi secara rekursif mengunjungi setiap node sesuai dengan jenis node yang kita hadapi.

Mari kita tambahkan contoh yang lebih kompleks, ifkonstruksi pernyataan! Ingatlah bahwa jika pernyataan juga dapat memiliki klausa opsional lain. Mari kita tambahkan pernyataan if-else ke struktur simpul asli kami. Ingat bahwa jika pernyataan itu sendiri dapat memiliki pernyataan if, maka semacam rekursi dalam sistem simpul kita dapat terjadi. Pernyataan lain bersifat opsional sehingga elsestmtbidang dapat NULL yang dapat diabaikan oleh fungsi pengunjung rekursif.

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
    struct {
        struct ASTNode *expr, *stmt, *elsestmt;
    } IfStmt;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

kembali di fungsi cetak pengunjung simpul kami disebut AST_PrintNode, kami dapat mengakomodasi ifpernyataan AST membangun dengan menambahkan kode C ini:

case AST_IfStmt:
    puts("AST If Statement\n");
    AST_PrintNode(node->Data->IfStmt.expr);
    AST_PrintNode(node->Data->IfStmt.stmt);
    AST_PrintNode(node->Data->IfStmt.elsestmt);
    break;

Sesimpel itu! Sebagai kesimpulan, Sintaksis Pohon tidak lebih dari sebatang pohon dari gabungan tagged pohon dan datanya sendiri!