Pembuatan Compiler Bagian 2 - Revision history

Gibransyah: /* Memahami langkah pembuatan interpreter */

2014-03-28T08:14:05Z

Memahami langkah pembuatan interpreter

Gibransyah: /* AST */

2014-03-28T08:13:03Z

AST

Gibransyah at 08:12, 28 March 2014

2014-03-28T08:12:40Z

Gibransyah at 08:11, 28 March 2014

2014-03-28T08:11:46Z

Gibransyah at 08:10, 28 March 2014

2014-03-28T08:10:04Z

Gibransyah: /* Menulis Kode */

2014-03-28T08:09:04Z

Menulis Kode

Gibransyah: /* Menulis Kode */

2014-03-28T08:08:51Z

Menulis Kode

Gibransyah: /* Menulis Kode */

2014-03-28T08:08:43Z

Menulis Kode

Gibransyah: /* Menulis Kode */

2014-03-28T08:05:39Z

Menulis Kode

Gibransyah: /* ANTLR */

2014-03-28T08:01:46Z

ANTLR

← Older revision		Revision as of 08:14, 28 March 2014
Line 1:		Line 1:
		+	== Indeks ==
		+	[[Tutorial_Pembuatan_Compiler \| Pendahuluan]] - [[Pembuatan_Compiler_Bagian_1 \| Bagian 1]] - [[Pembuatan_Compiler_Bagian_2 \| Bagian 2]] - [[Pembuatan_Compiler_Bagian_3 \| Bagian 3]] - [[Pembuatan_Compiler_Bagian_4 \| Bagian 4]] - [[Pembuatan_Compiler_Bagian_5 \| Bagian 5]] - [[Pembuatan_Compiler_Bagian_6 \| Bagian 6]] - [[Pembuatan_Compiler_Bagian_7 \| Bagian 7]] - [[Pembuatan_Compiler_Bagian_8 \| Bagian 8]] - [[Pembuatan_Compiler_Bagian_9 \| Bagian 9]]
		+
	== Memahami langkah pembuatan interpreter ==		== Memahami langkah pembuatan interpreter ==

@@ Line 127: / Line 127: @@
 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
+ // START:stat
   prog:   stat+ -> ^(EXPRESSION_LIST stat+);
   stat:   expr NEWLINE -> ^(EXPRESSION expr)

@@ Line 229: / Line 229: @@
 </pre>
 Kedua, jika isi node adalah operator ('+' atau '-' atau '*') berarti nilai ekspresi adalah nilai anak pertama dioperasikan (ditambah/dikurang/dikali) dengan anak kedua:
 == Cara Berpikir ==

@@ Line 212: / Line 212: @@
 kita melihat bahwa ada suatu node dengan nama EXPRESSION yang tidak terlalu berguna untuk saat ini. Gunanya hanyalah agar terlihat bahwa node di bawahnya adalah sebuah ekspresi. Saya sengaja membuat node ini untuk pengembangan versi berikutnya, di mana setiap baris belum tentu berisi ekspresi. Kita hanya perlu melewati node itu dengan mengambil anaknya yang pertama.
-<code>
+<pre>
 int evaluateExpression(CommonTree expr) {
          debug("Evaluate Expression "+expr.getText());
          return evaluateExpr((CommonTree)expr.getChild(0)) ;
+     }
-</code>
+</pre>
 Fungsi evaluateExpr adalah fungsi yang melakukan komputasi. Ini sangat mudah, karena pada dasarnya hanya ada dua kasus: INTEGER, dan OPERATOR.
@@ Line 223: / Line 223: @@
 Pertama, jika isi node adalah integer, maka hasilnya adalah nilai integer itu sendiri (di Java kita memakai Integer.parseInt untuk mengubah string menjadi integer)
-<code>
+<pre>
 if (expr.getType()==ExprLexer.INT) {
          return Integer.parseInt(expr.getText());
+     }
-</code>
+</pre>
 Kedua, jika isi node adalah operator ('+' atau '-' atau '*') berarti nilai ekspresi adalah nilai anak pertama dioperasikan (ditambah/dikurang/dikali) dengan anak kedua:
-<code>
+<pre>
 Kedua, jika isi node adalah operator ('+' atau '-' atau '*') berarti nilai ekspresi adalah nilai anak pertama dioperasikan (ditambah/dikurang/dikali) dengan anak kedua:
-</code>
+</pre>
 == Cara Berpikir ==

@@ Line 197: / Line 197: @@
 Mari kita mulai memproses tree. Kita memiliki banyak ekspresi dalam satu file, maka kita buat method evaluateExprList, method ini hanya akan memanggil evaluateExpression yang tugasnya adalah mengevaluasi ekspresi itu sendiri.
-<code>
+<pre>
 void evaluateExprList(CommonTree exprlist) {
          for (Object e: exprlist.getChildren()) {
@@ Line 204: / Line 204: @@
+         }
+     }
-</code>
+</pre>
 Kalau kita lihat dari gambar AST yang dihasilkan oleh Antlr, misalnya pohon ini:

@@ Line 170: / Line 170: @@
 Nah sekarang kita perlu menuliskan kode dalam bahasa Java. Kode-kode berikut ini ada pada file ExprLang.java. Setiap parser pasti punya kode inisialisasi, kode inisialisasi ini akan sama untuk aneka jenis bahasa, sehingga tidak akan dijelaskan lagi di bagian berikutnya.
-<code>public static void main(String argv[]) throws Exception {
+<pre>public static void main(String argv[]) throws Exception {
          ExprLexer lex = new ExprLexer(new ANTLRFileStream(argv[0]));
          CommonTokenStream tokens = new CommonTokenStream(lex);
@@ Line 177: / Line 177: @@
          CommonTree ct = (CommonTree)r.getTree();
+     }
-</code>
+</pre>
 Baris pertama dalam sebuah fungsi main membuat sebuah lexer (dalamkasus ini ExprLexer), yang fungsinya memecah string menjadi bagian-bagiannya (menjadi INT, '*', '+', '-', dsb). Baris kedua membuat object CommonTokenStream yang diberikan ke parser (ini adalah sebuah adapter, Anda tidak perlu mengetahui internalnya kecuali ingin mengubah kode ANTLR). Baris ketiga adalah bagian untuk mengkonstruksi parser, dan baris ke empat adalah baris yang penting, baris di mana proses parsing itu sendiri dipanggil:

@@ Line 176: / Line 176: @@
          ExprParser g = new ExprParser(tokens);
          ExprParser.prog_return r = g.prog();
          CommonTree ct = (CommonTree)r.getTree();
+     }

← Older revision		Revision as of 08:05, 28 March 2014
Line 207:		Line 207:
	}		}
	</code>		</code>
		+
		+	Kalau kita lihat dari gambar AST yang dihasilkan oleh Antlr, misalnya pohon ini:
		+
		+	[[Image:Ast_1_plus_2_times_3.jpg]]
		+
		+	kita melihat bahwa ada suatu node dengan nama EXPRESSION yang tidak terlalu berguna untuk saat ini. Gunanya hanyalah agar terlihat bahwa node di bawahnya adalah sebuah ekspresi. Saya sengaja membuat node ini untuk pengembangan versi berikutnya, di mana setiap baris belum tentu berisi ekspresi. Kita hanya perlu melewati node itu dengan mengambil anaknya yang pertama.
		+
		+	<code>
		+	int evaluateExpression(CommonTree expr) {
		+	debug("Evaluate Expression "+expr.getText());
		+	return evaluateExpr((CommonTree)expr.getChild(0)) ;
		+	}
		+	</code>
		+
		+	Fungsi evaluateExpr adalah fungsi yang melakukan komputasi. Ini sangat mudah, karena pada dasarnya hanya ada dua kasus: INTEGER, dan OPERATOR.
		+
		+	Pertama, jika isi node adalah integer, maka hasilnya adalah nilai integer itu sendiri (di Java kita memakai Integer.parseInt untuk mengubah string menjadi integer)
		+
		+	<code>
		+	if (expr.getType()==ExprLexer.INT) {
		+	return Integer.parseInt(expr.getText());
		+	}
		+	</code>
		+
		+	Kedua, jika isi node adalah operator ('+' atau '-' atau '*') berarti nilai ekspresi adalah nilai anak pertama dioperasikan (ditambah/dikurang/dikali) dengan anak kedua:
		+
		+	<code>
		+	Kedua, jika isi node adalah operator ('+' atau '-' atau '*') berarti nilai ekspresi adalah nilai anak pertama dioperasikan (ditambah/dikurang/dikali) dengan anak kedua:
		+	</code>
		+
		+	== Cara Berpikir ==
		+	Perhatikan bahwa algoritma ini sangat sederhana, Anda hanya perlu berpikir: di Node ini saya harus melakukan apa? Anda jangan melihat kompleksitas semu. Jika Anda berpikir bahwa untuk membuat kalkulator seperti ini Anda harus memikirkan aneka kombinasi yang ada, seperti 4*7, 4+7, 4+(7), (4)+7, dst, maka cara berpikir Anda masih salah. Ingatlah bahwa proses parsing menghasilkan pohon, sehingga Anda harus berpikir bagaimana melakukan aksi dalam suatu node di pohon tersebut.
		+
		+	== Mengkompilasi ==
		+	Untuk mengkompilasi interpreter ini, Anda perlu file antlr-runtime-3.1.3.jar (tergantung versi terbaru saat ini). Anda perlu memberikan path ke file tersebut, di Linux/Mac/BSD, kira-kira seperti ini:
		+
		+	javac -classpath /path/to/antlr-runtime-3.1.3.jar:. ExprLang.java
		+
		+	di Windows, kira-kira seperti ini:
		+
		+	java -classpath /path/to/antlr-runtime-3.1.3.jar:. ExprLang test.e
		+
		+	Di mana test.e adalah file teks yang berisi baris-baris ekspresi.
		+
		+	Selesai sudah interpreter yang sangat sederhana. Saya sengaja menyertakan pernyataan debug agar pembaca dapat memahami alur eksekusi. Total baris, tanpa debug hanyalah 60 baris, ditambah dengan file grammar Expr.g totalnya hanya 100 baris. Mudah bukan?

← Older revision		Revision as of 08:01, 28 March 2014
Line 68:		Line 68:
	WS : (' '\|'\t'\|'\n'\|'\r')+ {skip();} ;		WS : (' '\|'\t'\|'\n'\|'\r')+ {skip();} ;
	// END:tokens		// END:tokens
		+
		+	Mari kita bahas grammarnya. Sebuah program <prog> terdiri atas banyak pernyataan <stat>+ (simbol plus artinya satu atau lebih), sebuah pernyataan boleh sebuah ekpresi <expr> atau sebuah baris kosong (NEWLINE). Anda juga bisa melihat Syntax Diagram dari sebuah rule, misalnya prog akan tampak seperti ini:
		+
		+	[[Image:Prog plus.jpg]]
		+
		+	Karena Anda bisa melihat sendiri syntax diagram-nya di ANTLRWorks, saya tidak akan menampilkan sisanya.
		+
		+	Sebuah ekspresi terdiri dari pernyataan perkalian <multExpr> yang diikuti oleh plus/minus ekpresi yang lain. Tapi plus dan minus itu tidak wajib, jadi kita tambahkan * yang artinya nol atau lebih.
		+
		+	Pernyataan perkalian sendiri terdiri atas <atom> yang (mungkin) dikalikan dengan atom lain, karena tidak harus dikalikan atom lain, maka kita tambahkan juga *. Aturan terakhir adalah <atom> yang bisa berupa sebuah integer, atau ekspresi lain dalam tanya kurung.
		+
		+	Berikutnya kita perlu mendefinisikan token. Dalam kasus ini yang menjadi token adalah INT (0-9), NEWLINE (boleh \r\n yang merupakan versi DOS atau \n saja yang merupakan versi UNIX). Kita juga mengijinkan spasi ada di antara ekspresi, jadi 1+2 sama dengan 1 + 2, untuk itu kita perlu mendefinisikan karakter apa saja yang perlu dilewatkan (skip), dalam kasus ini kita mengabaikan spasi, tab, dan karakter baris baru.
		+
		+	Kita bisa langsung mencoba grammar ANTLR ini, dengan menggunakan ANTLRWorks. Coba pilih menu Debugger, lalu pilih Debug. Masukkan teks, misalnya 1+2. Perhatikan bahwa Anda harus mengakhiri sebuah ekspresi dengan karakter baris baru (enter) setelah ekspresi. Anda bisa menjalankan grammar langkah per langkah, atau langsung saja klik pada tombol END. Hasilnya sebuah pohon akan ditampilkan, pohon ini dinamakan Pohon Parsing (Parsing Tree). Silakan Anda mencoba-coba aneka ekspresi lain, termasuk ekspresi multi baris, supaya bisa melihat bagaimana pohon untuk setiap ekspresi.
		+
		+	Berikut ini adalah gambar pohon yang dihasilkan oleh 1 + 2 * 3. Gambar pohon ini dihasilkan langsung oleh ANTLRWorks (saya tidak menggambarnya manual).
		+
		+	[[Image:1 plus 2 times 3.jpg]]
		+
		+	== 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:
		+
		+	[[Image:Ast 1 plus 2 times 3.jpg]]
		+
		+	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:
		+
		+	[[Image:660x310-parse tree 2.jpg]]
		+
		+	Sedangkan AST yang diharapkan adalah seperti ini:
		+
		+	[[Image:2 times 5 plus x 6 minus 8 x.jpg]]
		+
		+	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.
		+
		+	[[Image:Ast 1 plus 2 times 3.jpg]]
		+
		+	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.
		+
		+	[[Image:Antlr.png]]
		+
		+	Catatan: Java hanyalah salah satu bahasa yang didukung ANTLR.
		+	ANTLR juga bisa membuat parser dalam bahasa C, C#, Python,
		+	JavaScript, dan ActionScript.
		+
		+	== Menulis Kode ==
		+	Nah sekarang kita perlu menuliskan kode dalam bahasa Java. Kode-kode berikut ini ada pada file ExprLang.java. Setiap parser pasti punya kode inisialisasi, kode inisialisasi ini akan sama untuk aneka jenis bahasa, sehingga tidak akan dijelaskan lagi di bagian berikutnya.
		+
		+	<code>
		+	public static void main(String argv[]) throws Exception {
		+	ExprLexer lex = new ExprLexer(new ANTLRFileStream(argv[0]));
		+	CommonTokenStream tokens = new CommonTokenStream(lex);
		+	ExprParser g = new ExprParser(tokens);
		+	ExprParser.prog_return r = g.prog();
		+
		+	CommonTree ct = (CommonTree)r.getTree();
		+	}
		+	</code>
		+
		+	Baris pertama dalam sebuah fungsi main membuat sebuah lexer (dalamkasus ini ExprLexer), yang fungsinya memecah string menjadi bagian-bagiannya (menjadi INT, '*', '+', '-', dsb). Baris kedua membuat object CommonTokenStream yang diberikan ke parser (ini adalah sebuah adapter, Anda tidak perlu mengetahui internalnya kecuali ingin mengubah kode ANTLR). Baris ketiga adalah bagian untuk mengkonstruksi parser, dan baris ke empat adalah baris yang penting, baris di mana proses parsing itu sendiri dipanggil:
		+
		+	ExprParser.prog_return r = g.prog();
		+
		+	Kita meminta nilai kembalian parser dimulai dari aturan prog. Setelah itu kita bisa mendapatkan Tree (AST) dengan menggunakan r.getTree(). Tree yang kita pakai adalah Tree standar bawaan ANTLR, jadi kita memakai CommonTree. Setelah memiliki root dari tree, kita bisa mengevaluasi ekspresi dengan mudah. Saya tidak akan menjelaskan semua method milik CommonTree, penjelasan lengkap ada di dokumentasinya di:
		+
		+	http://www.antlr.org/api/Java/classorg_1_1antlr_1_1runtime_1_1tree_1_1_common_tree.html
		+
		+	Method-method yang akan saya pakai adalah: getChildren, getChilCount, getChild, getType, dan getText. Berikut ini penjelasan singkatnya:
		+
		+	# Method getChildren untuk mendapatkan List of children yang bisa diiterasi menggunakan format loop Java (for (Tree x: e.getChildren()) {}). Sebagai catatan, Anda akan melihat banyak casting tipe Object ke CommonTree, ketika ANTLR ditulis, Java 1.5 belum dirilis, sehingga fitur Generic milik Java belum dipakai. Mereka saat ini sudah mulai beralih ke JDK 1.5.
		+	# Method getChildCount digunakan untuk mendapatkan jumlah anak. Berguna untuk menentukan apakah misalnya pernyataan if memiliki else atau tidak.
		+	# Method getChild digunakan untuk mendapatkan anak ke-n.
		+	# Method getType digunakan untuk mendapatkan konstanta integer tipe node. Nilainya terdefinisi (tidak nol) jika node tersebut diberi nama dibagian tokens. Hasil kembalian method ini bisa dibandingkan dengan konstanta integer yang dihasilkan ANTLR dalam format NamaGrammarLexer.KONSTANTA (dalam contoh ini misalnya ExprLexer.INT)
		+	# Method getText digunakan untuk mendapatkan teks node (misalnya node + akan memiliki teks +). Ketika nanti node variabel diperkenalkan, getText bisa digunakan untuk mendapatkan nama variabel.
		+
		+	Mari kita mulai memproses tree. Kita memiliki banyak ekspresi dalam satu file, maka kita buat method evaluateExprList, method ini hanya akan memanggil evaluateExpression yang tugasnya adalah mengevaluasi ekspresi itu sendiri.
		+
		+	<code>
		+	void evaluateExprList(CommonTree exprlist) {
		+	for (Object e: exprlist.getChildren()) {
		+	System.out.println("Result: " +
		+	evaluateExpression((CommonTree)e));
		+	}
		+	}
		+	</code>