Tutorial AST

Jika diperhatikan karakter yang tidak penting juga masuk dalam pohon ini, yaitu karakter '\n'. Ada juga node yang tidak penting, yaitu atom. Jika Anda membuat bahasa yang lebih rumit, misalnya bahasa C, maka karakter seperti '{', '}', ';' yang tidak penting juga akan masuk dalam parse tree. Kita mengatakan karakter itu tidak penting karena gunanya hanya untuk memisahkan blok, dan dalam bentuk pohon, sudah jelas bahwa blok-blok tersebut terpisah.
Sebelum masuk tahap pemrosesan, kita perlu mengubah pohon tersebut ke bentuk AST (abstract syntax tree) dengan membuang hal-hal yang tidak perlu, dan mungkin mengorganisasi tree menjadi bentuk yang lebih baik (lebih mudah diproses, misalnya menukar node kiri dan kanan, dsb). Jika kita menggunakan tools tertentu (misalnya Bison) kita menulis kode untuk mengubah parse tree menjadi AST, tapi untungnya ANTLR sudah cukup canggih, sehingga kita cukup menambahkan aturan untuk membuat pohon.
AST yang saya inginkan untuk 1 + 2 * 3 adalah:


Dan jika ada dua baris (saya menambahkan satu baris baru: 2 * 5 + (6 - 8)) :

  1 + 2 * 3
  2 * 5 + (6 - 8) 

Saat ini parse tree sudah terlalu kompleks:

Sedangkan AST yang diharapkan adalah seperti ini:

Perhatikan bahwa tanda kurung juga tidak ada lagi (tidak lagi penting, karena dalam bentuk tree sudah jelas presedensinya).
Ada beberapa perubahan yang diperlukan untuk menghasilkan AST. Pertama di bagian options, kita tambahkan opsi output = AST, dan ASTLabelType = CommonTree. Ini artinya kita meminta ANTLR menghasilkan AST, dengan tipe node AST-nya adalah CommonTree. Jika kita mau, kita juga bisa membuat sendiri jenis node untuk tree kita sendiri, tapi saat ini hal tersebut tidak diperlukan.
Berikutnya, kita perlu menentukan seperti apa bentuk tree kita. Dalam kasus ini, karena ada banyak ekspresi, saya ingin di bagian akar (root) adalah EXPRESSION_LIST, dan terdiri atas banyak EXPRESSION. Jika dilihat kembali, tidak ada rule yang bernama EXPRESSION ataupun EXPRESSION_LIST, jadi kita perlu mendefinisikan kedua nama tersebut di bagian tokens. Kita juga ingin agar INT menjadi nama node untuk literal integer. Setiap nama yang didefinisikan di bagian tokens akan memiliki konstanta bertipe integer di file parser yang dihasilkan ANTLR.

options {
 output = AST;
 ASTLabelType =CommonTree;
}

tokens {
       EXPRESSION_LIST;
       EXPRESSION;
       INT;
}

Kita perlu mengubah pohon stat menjadi pohon EXPRESSION_LIST, yang terdiri atas banyak EXPRESSION. Caranya kita gunakan operator -> milik ANTLR. Operator ini digunakan setelah sebuah rule, untuk menentukan bentuk tree untuk rule tersebut. Umumnya bentuknya adalah ^(ROOT rules), yang artinya, jadikan ROOT sebagai akar dan rules sebagai anak-anaknya. Contohnya seperti ini:

// START:stat
prog:   stat+ -> ^(EXPRESSION_LIST stat+);

stat:   expr NEWLINE -> ^(EXPRESSION expr)
    |   NEWLINE
    ;
// END:stat

Bagian pertama stat+ -> ^(EXPRESSION_LIST stat+); artinya, node-node yang berupa stat, dikumpulkan dibawah node yang bernama EXPRESSION_LIST. Bagian kedua expr NEWLINE -> ^(EXPRESSION expr) artinya Node expr ditaruh dibawah node EXPRESSION, dan kita mengabaikan karakter NEWLINE.
Kita juga ingin agar '+' dan '-' memiliki nodenya sendiri. Jadi jika ada 11+12, kita ingin agar punya Node '+' yang anak kirinya adalah node 11 dan anak kanannya adalah node 12. Untuk hal ini, ANTLR memiliki shortcut. Agar '+' dan '-' menjadi node, cukup tambahkan karakter ^ di bagian grammar yang ingin dijadikan root node.

// START:expr
expr:   multExpr (('+'|'-')^ multExpr)*
    ; 

Sama halnya dengan '*', kita juga ingin agar * memiliki nodenya sendiri

    
multExpr
    :   atom ('*'^ atom)*
    ; 

Dan terakhir, kita ingin membuang kurung buka dan kurung tutup, karena urutan evaluasi sudah jelas dalam tree. Untuk membuangnya, kita nyatakan bahwa '(' expr ')' -> expr, yang artinya: jika ada kurung buka, lalu expr, lalu kurung tutup, cukup hasilkan expr saja (dengan kata lain buang kurung buka dan tutupnya).

atom:   INT 
    |   '(' expr ')' -> expr
    ;
// END:expr

Sekarang kita bisa mengklik tab AST di ANTLRWorks, dan hasil AST-nya adalah seperti ini.

Nah sekarang kita sudah punya tree yang bagus. Berikutnya adalah bagaimana mengeksekusi tree tersebut? Ada dua cara: pertama adalah interpretasi, dan kedua adalah kompilasi. Namun kita perlu menghasilkan dulu source code parsernya, caranya cukup klik menu Generate lalu pilih Generate Code. ANTLR akan membuat tiga buah file, yaitu file Lexer, file Parser, dan file Tokens.

Catatan: Java hanyalah salah satu bahasa yang didukung ANTLR. ANTLR juga bisa membuat parser dalam bahasa C, C#, Python, JavaScript, dan ActionScript.

Sumber : Yohan.es