Tutorial Membuat Interpreter dan Compiler (bagian 4)

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

Source code untuk artikel ini: expr2.zip

Input, Output, dan Variabel

Bahasa yang kita buat dalam bagian 2 dan bagian 3 sangat sederhana, sampai-sampai tidak berguna secara praktis. Kita bisa menambah sedikit kegunaan dengan mengijinkan adanya VARIABEL dan instruksi untuk membaca INPUT, serta memberikan OUTPUT. Tujuannya adalah, kita bisa membuat interpreter dan compiler untuk bahasa seperti ini:

 var panjang,lebar,luas,keliling
 print 'input panjang'
 input panjang
 print 'input lebar'
 input lebar
 luas=panjang*lebar
 print 'luas adalah '
 print luas
 keliling=(2*panjang)+(2*lebar)
 print 'Keliling adalah '
 print keliling

Perhatikan bahwa dalam bagian ini, kita akan memakai evaluator ekspresi yang sudah dibahas di bagian 2, jadi bagian sebelumnya berguna untuk membentuk sebuah compiler, meski bahasa yang dihasilkan tidak berguna secara praktis.

Saya juga akan menambahkan Unary Operator (+ dan -) sehingga lebih berguna (sekaligus sebagai jawaban untuk latihan di bagian sebelumnya). Operator pembagian silahkan ditambahkan sendiri (ini sangat mudah). Saat ini kita hanya menangani integer, jadi bahasa ini akan saya namakan BULAT. Grammarnya sekarang menjadi 79 baris. Anda dapat melihat sendiri grammar lengkap di source code, saya hanya akan membahas yang berubah saja.

Sekarang ada lebih banyak token.

 tokens {
    STATEMENT_LIST;
    DECLARATION;
    ASSIGNMENT;
    INPUT;  
    PRINT;      
    INT;
    STRING;
    ID;
 }

Token yang penting adalah DECLARATION untuk deklarasi variabel (var panjang, lebar, luas, keliling), ASSIGNMENT untuk operasi assignment (luas = panjang*lebar), PRINT untuk mencetak string dan variabel (print luas dan print print 'luas adalah'), serta INPUT untuk meminta masukan (input panjang). Karena kita sekarang memiliki variabel, kita memperkenalkan token ID, dan karena print bisa digunakan untuk mencetak selain variabel (print 'hello'), kita definisikan juga tipe STRING.

Sebuah program terdiri atas deklarasi (satu baris), diikuti oleh satu atau lebih statement

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

Sebuah statement bisa berupa assignment, input, atau print, dan boleh juga baris kosong

 stat:   assignment NEWLINE -> assignment
     | input NEWLINE -> input
     | print NEWLINE ->print
     | NEWLINE
     ;

Sebuah deklarasi diawali dengan var dan diikuti dengan daftar variabel yang dipisahkan dengan koma

     
declaration
    :   
    'var' ID ( ',' ID)* NEWLINE -> ^(DECLARATION ID)

Untuk meminta input dari pengguna, kita menggunakan input diikuti nama variabel:

input  :   
    'input' ID -> ^(INPUT ID)
    ;

Instruksi print boleh diikuti oleh sebuah variabel atau sebuah string:

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

Assignment dilakukan dalam bentuk namavar = ekspresi. Ekspresi ini sangat mirip dengan di tutorial sebelumnya.

     
assignment
    :           
    ID '=' expr -> ^(ASSIGNMENT ID expr)
    ;

Secara visual, contoh tree adalah seperti ini:

bulat.jpg

Satu-satunya perbedaan di dalam ekspresi adalah dukungan terhadap unary operator

 multExpr
     :   unaryExpr ('*'^ unaryExpr)*
     ; 
 
 unaryExpr
    : unary_op atom
    | atom
    ;    
 
 unary_op:  
    PLUS
    |MINUS
    ;
 
 PLUS   :    '+';
 MINUS :     '-';

Sebenarnya bisa saja plus/minus digunakan langsung seperti ini

unaryExpr
    : ('+'|'-')^ atom
    | atom
    ;    

Tapi saya menggunakan cara sebelumnya untuk menunjukkan cara penulisan grammar yang baik (karena mungkin suatu hari Anda ingin menambah operator unary yang lain).

Untuk variabel, hanya karakter a-z saja yang diijinkan:

ID:    'a'..'z'+ ;

Untuk string, apapun yang ada antara tanda kutip diijinkan (kita tidak mendukung escape character apapun, seperti \n atau \t)

STRING :    '\''( ~('\'') )*'\'' ;

CATATAN: Mungkin Anda mulai berpikir bahwa menulis grammar akan butuh waktu sangat lama, dan akan membosankan. Untuk aneka ekspresi dasar, biasanya Anda hanya perlu copy-paste dari aneka bahasa yang sudah tersedia grammarnya di Internet. Jadi jika Anda mengimplementasikan bahasa baru yang grammarnya mirip dengan bahasa yang sudah ada, Anda bisa dengan cepat dan mudah membuat grammarnya.

Menyimpan variabel

Karena semua tipe data hanyalah integer, kita bisa menggunakan hashtable seperti ini:

     Hashtable<String, Integer> variables;

Jika Anda ingin mendukung aneka tipe data, Anda bisa menggantikan Integer dengan kelas Anda sendiri (misalnya kelas Variable), dan Anda perlu menyimpan tipe variabel serta nilainya.

Eksekusi

Kita review lagi perubahan grammar: baris-baris program tidak lagi berupa ekspresi saja. Di bagian awal harus ada deklarasi (lihat bagian declaration). Tepatnya, sebuah program adalah deklarasi yang diikuti oleh banyak statement. Sebuah statement bisa berupa: assignment, yaitu memberi nilai pada suatu variabel, input, yaitu meminta input dari user, dan print yaitu mencetak sebuah string, atau sebuah variabel. Untuk lebih jelasnya, Anda bisa melihat Syntax Diagram menggunakan ANTLRWorks. Supaya tidak perlu scroll ke atas, saya tampilkan lagi gambar sebelumnya:

bulat.jpg

Catatan: Kode-kode berikut ini ada pada file BulatLang.java

Mengevaluasi daftar statement sangat mudah, Anda cukup meloop semua statement, dan mengevaluasi masing-masing statement:

    void evaluateStatementList(CommonTree exprlist) throws Exception{
        for (Object e: exprlist.getChildren()) {
            evaluateStatement((CommonTree)e);
        }
    }

Tapi ada banyak statement, jadi kita perlu mendelegasikan ke method yang sesuai. Kalau program sudah semakin rumit, delegasi bisa dilakukan ke kelas lain.

    void evaluateStatement(CommonTree expr) throws Exception{
        switch (expr.getType()) {
        case BulatLexer.DECLARATION:
            evaluateDeclaration(expr);
            break;
        case BulatLexer.INPUT:
            evaluateInput((CommonTree)expr.getChild(0));
            break;
        case BulatLexer.PRINT:
            evaluatePrint((CommonTree)expr.getChild(0));
            break;
        case BulatLexer.ASSIGNMENT:
            evaluateAssignment(expr);
            break;
        }
    }

Pertama kita bahas dulu evaluasi deklarasi. Supaya terdeklarasi, setiap variabel dimasukkan ke hash table dan diberi nilai nol.

    void evaluateDeclaration(CommonTree  decl) {
        for (Object e: decl.getChildren()) {
            CommonTree et = (CommonTree)e;
            variables.put(et.getText(), 0);
        }
    }

Berikutnya, evaluasi input. Pertama kita cek dulu apakah variabelnya sudah dideklarasikan atau belum (jika belum, exception akan dilemparkan, dan program akan berhenti):

    void evaluateInput(CommonTree expr) throws Exception {
        String var = expr.getText();
        checkVar(var);
        int i = scanner.nextInt();
        variables.put(var, i);
    }

Kita akan memakai fitur Java 5, yaitu kelas Scanner untuk membaca input dari keyboard. Memakai kelas ini cukup mudah dibanding pendekatan Java versi sebelumnya yang memerlukan BufferedReader. Contoh memakai kelas scanner seperti ini:

    Scanner scanner;
    scanner = new Scanner(System.in);

    int i = scanner.nextInt();

Supaya tidak penasaran, pemeriksaan apakah variabel sudah dideklarasikan dilakukan dengan memanggil method containsKey milik Hashtable.

    void checkVar(String var) throws Exception {
        if (!variables.containsKey(var)) {
            throw new Exception("Variable '"+var+"' not declared");
        }
    }

Setelah itu kita bahas bagaimana mengevaluasi print. Ada dua bentuk, yang mencetak variabel dan yang mencetak string. Sebenarnya ini bisa dibuat lebih generik, tapi versi ini demi kesederhanaan tutorial. Jika tipenya adalah string, maka kita perlu menghapus tanda petik di awal dan di akhir string. Mudahnya, gunakan regex di Java. Setelah itu cetak stringnya dengan System.out.println. Jika yang dicetak akan variabel, kita cek dulu apakah variabelnya ada atau tidak. Jika ada, kita ambil nilainya dengan get, dan kita cetak ke layar.

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

Dan yang terakhir adalah assignment. Anak pertama adalah variabel dan anak kedua adalah ekspresi. Kita sudah punya kode untuk evaluasi ekspresi dari tutorial sebelumnya, jadi yang diperlukan adalah: cek apakah variabel sudah dideklarasikan, evaluasi ekspresi, dan masukkan hasilnya dengan put.

    void evaluateAssignment(CommonTree astmt) throws Exception {
        CommonTree var = (CommonTree)astmt.getChild(0);
        checkVar(var.getText());
        CommonTree expr = (CommonTree)astmt.getChild(1);
        int res = evaluateExpr(expr);
        variables.put(var.getText(), res);
    }

Karena sekarang kita mendukung variabel dan unary operator, maka evaluasi ekspresi sedikit berubah. Jika kita bertemu dengan variabel, kita cek apakah variabel tersebut ada, lalu kita kembalikan nilainya:

        if (expr.getType()==BulatLexer.ID) {
            checkVar(expr.getText());
            return variables.get(expr.getText());
        }

Untuk unary plus dan minus juga tidak sulit. Kita tambahkan satu buah if untuk memeriksa jumlah anak. Jika jumlahnya satu, maka itu unary, selain itu pasti punya dua anak (binary).

        if (expr.getText().equals("+")) {
            if (expr.getChildCount()==1) {
                return evaluateExpr((CommonTree)expr.getChild(0));
            } else {
                return evaluateExpr((CommonTree)expr.getChild(0)) + 
                    evaluateExpr((CommonTree)expr.getChild(1));
            }
        }
        if (expr.getText().equals("-")) {
            if (expr.getChildCount()==1) {
                return -evaluateExpr((CommonTree)expr.getChild(0));
            } else {
                return evaluateExpr((CommonTree)expr.getChild(0)) - 
                    evaluateExpr((CommonTree)expr.getChild(1));
            }
        }

Anda bisa melihat sendiri source code lengkapnya di file zip yang saya sediakan (kira-kira 133 baris kode). Jika Anda mengikuti tutorial ini dari awal, tentunya tidak sulit mengikuti perubahan source codenya.

blog comments powered by Disqus

Copyright © 2009-2010 Yohanes Nugroho