Tutorial Membuat Interpreter dan Compiler (bagian 6)

part 1 part 2 part 3 part 4 part 5 part 6 part 7 part 8 part 9

Source code untuk artikel ini: expr3.zip

Bahasa baru: KASUS

Bahasa BULAT di bagian 4 dan bagian 5 sudah ada gunanya, misalnya digunakan untuk kalkulator. Namun bahasa tersebut masih terlalu sederhana, karena tidak ada pernyataan kondisional if, dan tidak ada kemungkinan untuk membuat loop. Mari kita lengkapi bahasa tersebut dengan if, else, while, dan operator perbandingan (<, <=, >, >=, ==, dan !=). Kita juga akan mengubah delimiter pernyataan menjadi ;, bukan enter. Dengan tambahan tersebut, kita bisa membuat program untuk menghitung persekutuan terbesar, seperti ini:

 var a,b,t;
 print 'masukkan nilai untuk a: '; input a;
 print 'masukkan nilai untuk b: '; input b;
 while b!=0 {
       t = b;
       b = a % b;
       a = t;
 }
 print 'Faktor persekutuan terbesar adalah '; println a;

Grammar baru

Grammar yang baru ini mengandung ambiguitas dalam pernyataan else, sehingga kita perlu memberi opsi backtrack = true di bagian options.

options {
  output = AST;
  ASTLabelType =CommonTree;
  backtrack = true;
}

Dari mana kita bisa mengetahui adanya ambiguitas? Anda bisa melihatnya dari grammarnya, atau dengan meminta ANTRLWorks memeriksanya menggunakan menu Grammar, lalu Check Grammar. Kebanyakan grammar bahasa membutuhkan opsi ini.

Berikutnya kita perlu menambahkan beberapa token baru

tokens {   
        /*tokentoken sebelumnya/
    PRINTLN;    
    IF_STATEMENT;
    WHILE_STATEMENT;
 }

Agar tampilan kelihatan lebih cantik, sekarang akan ada pernyataan print dan println, pernyataan print tidak akan mencetak baris baru (newline) setelah mencetak string atau variabel, sedangkan println akan mencetak baris baru.

Kita hapus definisi token untuk NEWLINE, karena kita akan menggunakan ;. Gantikan NEWLINE dengan ;, misalnya prog menjadi:

 prog:   declaration ';' stat+ -> ^(STATEMENT_LIST declaration stat+);

Bisa ada lebih dari satu pernyataan di bagian if, jadi kita perlu membuat rule baru untuk blok. Untuk mudahnya, kita gunakan blok { dan }, seperti bahasa C (dan aneka bahasa lain yang diinspirasi oleh C).

block  : '{'
        stat
      '}' -> ^(STATEMENT_LIST stat)
    ;

Selain itu, kita perlu menambahkan pernyataan untuk if (dalam rule ifstat) dan untuk while (dalam rule whilestat). Perhatikan bahwa semua NEWLINE kita ubah menjadi ;.

stat:   assignment ';' -> assignment
     | ifstat
     | whilestat
     | input ';' -> input
     | print ';' ->print   
     | block 
     ;

Pernytaan if tanpa else terdiri atas 2 bagian, bagian ekspresi, dan bagian pernyataan. Untuk if dengan else, maka ada 3 bagian (ada bagian pernyataan else).

Perhatikan bahwa ini sangat membingungkan, karena ada dua pernyataan (rule block), jadi kurang jelas rule block yang mana yang merupakan bagian pertama dan kedua.

ifstat :   'if' expr block ('else' block)? 
                       -> ^(IF_STATEMENT expr block block)
     ;

Agar lebih jelas, kita ubah menjadi berikut:

ifstat :   'if' expr ablock ('else' bblock)? 
                       -> ^(IF_STATEMENT expr $a $b)
     ;

Kita beri nama block dengan nama a dan b (perhatikan a=block, dan b=block). Lalu kita bisa merujuk ke block dengan $a (untuk bagian aksi if) dan $b (untuk bagian aksi else). Akhiran tanda tanya di bagian else menyatakan bahwa bagian itu sifatnya opsional (muncul 0 atau 1 kali).

Berikutnya rule untuk pernyataan while:

whilestat
    :    'while' expr block -> ^(WHILE_STATEMENT expr block)
    ;

Untuk masalah print dan println, cara penanganannya mudah, cukup tambahkan di rule print:

print   :  
    'print' ID -> ^(PRINT ID)
    | 'print' STRING -> ^(PRINT STRING)
    | 'println' STRING -> ^(PRINTLN STRING)
    | 'println' ID -> ^(PRINTLN ID)      
    ;

Dan terakhir, kita lengkapi ekspresi agar mendukung perbandingan, serta operator % (modulo) dan / (pembagian):

expr   : condExpr;
 
condExpr:  aexpr (relationalOp aexpr)*
                 ;
 
aexpr:   multExpr (('+'|'-')^ multExpr)*
     ; 
 
multExpr
     :   unaryExpr (('*'|'%'|'/')^ unaryExpr)*
     ; 
 
 
relationalOp 
     :    '<='
     |    '>='
     |   '<'
     |   '>'
     |    '=='
     |    '!='    
     ;

Karena bahasa KASUS hanya mendukung integer, maka kita gunakan aturan seperti pada bahasa C: nol artinya false, dan selain nol artinya true.

Kode untuk interpreter

Hal pertama yang perlu ditambahkan adalah menambahkan operator-operator yang ada. Ini sangat membosankan, karena semua barisnya mirip, misalnya seperti ini:

        if (expr.getText().equals("<")) {
            return (evaluateExpr(left)<evaluateExpr(right))?1:0;
        }
        if (expr.getText().equals(">")) {
            return (evaluateExpr(left)>evaluateExpr(right))?1:0;
        }
        /*dan seterusnya*/

Di bagian evaluateStatement, kita tambahkan penanganan untuk PRINT, PRINTLN, IF_STATEMENT, dan WHILE_STATEMENT:

    void evaluateStatement(CommonTree expr) throws Exception{
        switch (expr.getType()) {
        /*bagian DECLARATION, INPUT dan ASSIGNMENT  sama seperti
         dalam bahasa Bulat, sehingga tidak ditampilkan
       */
        case KasusLexer.PRINT:
        case KasusLexer.PRINTLN:
            evaluatePrint(expr.getType(), (CommonTree)expr.getChild(0));
            break;
        case KasusLexer.IF_STATEMENT:
            evaluateIf(expr);
            break;
        case KasusLexer.WHILE_STATEMENT:
            evaluateWhile(expr);
            break;
        }
    }

Bagian yang paling mudah adalah bagian PRINT dan PRINTLN. Kita hanya perlu menambahkan sebuah pengecekan. Jika tipe statement adalah PRINTLN, kita panggil System.out.println, sedangkan jika PRINT, kita panggil Sytem.out.print:

    void evaluatePrint(int type, CommonTree expr) throws Exception {
        if (expr.getType()==KasusLexer.STRING) {
            String s = expr.getText();
            /*remove first ' and last ' from string*/
            s = s.replaceAll("^'", "");
            s = s.replaceAll("'$", "");
            if (type==KasusLexer.PRINTLN) {
                System.out.println(s);
            } else {
                System.out.print(s);
            }
        } else {
            String var = expr.getText();
            checkVar(var);
            if (type==KasusLexer.PRINTLN) {
                System.out.println(variables.get(var));
            } else {
                System.out.print(variables.get(var));
            }
        }
    }

Kondisional

Berikutnya adalah bagian if. Pertama kita evaluasi dulu ekspresi yang diberikan (if expr). Jika hasilnya adalah true (alias tidak sama dengan nol), maka jalankan bagian ifpart. Jika if memiliki 3 anak, berarti ada bagian else. Jika bagian ifpart tidak dieksekusi, berarti bagian elsepart harus dieksekusi.

    void evaluateIf(CommonTree astmt) throws Exception {
        CommonTree expr = (CommonTree)astmt.getChild(0);
        CommonTree ifpart = (CommonTree)astmt.getChild(1);
        int res = evaluateExpr(expr);
        if (res!=0) {
            evaluateStatementList(ifpart);
            return;
        }
        if (astmt.getChildCount()==3) { /*else part*/
            CommonTree elsepart = (CommonTree)astmt.getChild(2);
            evaluateStatementList(elsepart);
        }
    }

Loop

Dan terakhir adalah untuk evaluasi while expr. Eksekusinya seperti if yang berulang, selama hasil dari expr masih true, kita ulangi:

    void evaluateWhile(CommonTree astmt) throws Exception {
        CommonTree expr = (CommonTree)astmt.getChild(0);
        CommonTree whileblock = (CommonTree)astmt.getChild(1);
        while (evaluateExpr(expr)!=0) {
            evaluateStatementList(whileblock);
        }
    }

Anda bisa menambahkan tipe loop yang lain, misalnya loop for atau repeat..until. Implementasinya tidak sulit.

Demikian pembahasan bahasa KASUS. Saya tidak akan membuatkan compiler untuk bahasa ini, dan kita akan maju terus untuk mengimplementasikan interpreter dengan menambahkan beberapa fitur bahasa yang lain (array, fungsi, dan aneka tipe data). Setelah pembahasan interpreter sudah cukup lengkap, kita akan kembali meneruskan untuk membuat compilernya.

Catatan: Jika Anda tertarik untuk membuat compiler untuk bahasa Kasus, Anda hanya perlu mengetahui beberapa pernyataan assembly untuk komparasi (JZ, JNZ, dsb), dan untuk meloncat ke suatu alamat (instruksi jump).

blog comments powered by Disqus

Copyright © 2009-2010 Yohanes Nugroho