ANTLR (ANother Tool for Language Recognation)

ANTLR (Another Tool for Language Recognation) adalah salah satu generator untuk mengenali bahasa, yang dibuat pertama kali oleh Terence Parr seorang Profesor dari Universitas San Francisco pada tahun 1989. ANTLR merupakan program bantu yang digunakan untuk menghasilkan program Parser, Lexer, ParserTokenTypes. Dimana input dari program tersebut berupa grammar file dan output berupa program Parser, Lexer, dan ParserTokenTypes dalam bahasa java, C++, dan C#. ANTLR menggunakan Hashtabel sebagai referensi penyimpanan data literal simbol. ANTLRWorks merupakan pengembangan lingkungan GUI untuk ANTLR grammar, sehingga lebih mudah untuk digunakan.                    ANTLR mengambil sebagai masukan suatu tata bahasa yang menentukan bahasa dan menghasilkan sebagai output kode sumber untuk recognizer untuk bahasa tersebut.

ANTLR Tree

Berdasarkan artikel “ANTRL Tree Construction”, ANTLR dapat membentuk intermediate form tree, atau abstract syntax tree, dengan menambahkan simbol-simbol tertentu pada grammar untuk mengindikasikan token yang menjadi root dari subtree, token yang menjadi leaves, dan token yang harus diabaikan pada saat pembentukan tree.

Root node untuk pembentukan AST pada ANTLR, ditentukan dengan menambahkan tanda “^” pada akhir dari sebuah token(sufix). Sedangkan untuk leaf node, setiap referensinya ke nonsuffixed token atau token-rangedianggap sebagai leaf node untuk rule tersebut.

ANTLR mengambil sebagai masukan tata bahasa yang menentukan bahasa dan menghasilkan  sebagai output kode sumber untuk recognizer untuk bahasa tersebut. Sementara versi 3 didukung kode menghasilkan dalam bahasa pemrograman Ada95, ActionScript, C, C #, Java, JavaScript, Objective-C, Perl, Python, Ruby, dan Standard ML, [1] rilis saat ini bisa hadir pada target Jawa saja. Sebuah bahasa ditentukan dengan menggunakan tata bahasa bebas konteks yang diekspresikan menggunakan diperpanjang Backus-Naur Form (EBNF).

ANTLR memungkinkan lexers menghasilkan, parser, parser pohon, dan gabungan lexer-parser. Parser otomatis dapat menghasilkan pohon sintaks abstrak yang dapat diproses lebih lanjut dengan parser pohon. ANTLR menyediakan notasi yang konsisten tunggal untuk menentukan lexers, parser, parser dan pohon. Hal ini berbeda dengan lainnya parser / lexer generator dan menambah besar terhadap kemudahan alat itu digunakan.

 Secara default, ANTLR membaca tata bahasa dan menghasilkan recognizer untuk bahasa yang didefinisikan oleh tata bahasa (yaitu sebuah program yang membaca aliran input dan menghasilkan kesalahan jika input stream tidak sesuai dengan sintaks yang ditentukan oleh tata bahasa). Jika tidak ada kesalahan sintaks, maka tindakan standar adalah hanya keluar tanpa mencetak pesan apapun. Dalam rangka untuk melakukan sesuatu yang berguna dengan bahasa, tindakan dapat melekat pada unsur-unsur tata bahasa dalam tata bahasa. Tindakan ini ditulis dalam bahasa pemrograman yang recognizer sedang dihasilkan. Ketika recognizer yang dihasilkan, tindakan yang tertanam dalam kode sumber dari recognizer di titik-titik yang tepat. Tindakan dapat digunakan untuk membangun dan memeriksa tabel simbol dan untuk memancarkan petunjuk dalam bahasa target, dalam kasus kompilator.

Serta lexers dan parser, ANTLR dapat digunakan untuk menghasilkan parser pohon. Ini adalah recognizers yang memproses pohon sintaks abstrak yang dapat secara otomatis dihasilkan oleh parser. Ini parser pohon yang unik untuk ANTLR dan sangat menyederhanakan pengolahan pohon sintaks abstrak.

ANTLR 3 adalah perangkat lunak bebas, yang diterbitkan di bawah Lisensi tiga klausul BSD. Versi sebelumnya yang dirilis sebagai perangkat lunak domain publik.

ANTLR menyediakan bahasa mark-up tingkat  tinggi untuk mendefinisikan grammar dari  sebuah bahasa, kemudian membuat lexer dan parser untuk mengenali grammar dari bahasa tersebut. Bahasa mark-up tersebut adalah grammar  pecification. Grammar  specification merupakan sekumpulan rule-rule yang mirip regular expression. Seperti yang telah dibahas dalam perancangan, terdapat dua jenis rule, yaitu lexer rule dan parser rule. Lexer rule digunakan untuk mendefinisikan bagaimana memotong-motong karakter menjadi token, berikut ini contoh implementasi dari lexer rule untuk mengenali Identifier :

IDENTIFIER

: Letter (Letter|'0'..'9')*

;

fragment

Letter

:

'a'..'z'

|'A'..'Z'

|'$'

|'_'

;

Dua buah lexer rule di atas digunakan untuk mendefinisikan token dengan tipe Identifier. Identifier adalah token yang terdiri darikombinasi huruf a-z, A–Z, $dan _. Dalam konsep bahasa, Lexer rule digunakan untuk mengubah huruf menjadi kata. Parser rule digunakan untuk memeriksa apakah urutan dari token sudah sesuai dengan grammar (tata bahasa) atau belum. Setiap bahasa, termasuk C, mempunyai tata bahasa yang harus dipatuhi, kesalahan urutan token membuat program tersebut melanggar tata bahasa yang sudah ditentukan.

Jadi Pada kesimpulan nya ANTLR ini merupakan aplikasi dari Terence Parr yang di buat dengan bahasa java,untuk memundahkan pembuatan program Parse,Lexer,serta ParserTokenTypes.

Teori Parsing

            Pada ilmu komputer, penguraian atau parsing adalah suatu cara memecah-mecah suatu rangkaian masukan (misalnya dari berkas atau keyboard) yang akan menghasilkan suatu pohon uraian (parse tree) yang akan digunakan pada tahap kompilasi berikutnya yaitu analisis semantik.

Jenis-jenis Metode Parsing

            Pada umumnya metode parsing dapat dimasukkan ke dalam dua jenis, dengan nama metode top-down dan bottom-up parsing.

1.      Metode Top-down Parsing

Top-down parsing, menurut Aho (2003, p181), dapat dilihat sebagai usaha untuk menemukan leftmost derivation untuk sebuah masukan string. Dengan kata lain, usaha untuk membentuk sebuah parse tree untuk sebuah masukan string dimulai dari root dan

membentuk node-node dari   parse tree  secara preorder. Bentuk umum dari top-down parsing disebut recursive descent, yang memungkinkan backtracking.

Menurut Tremblay,  J.P.  (1985,  p208)  ada  3  metode  umum untuk top-down parsing yaitu  brute force approach, recursive descent parser, dan top-down parsing dengan partial atau limited backup.

2.      Recursive Descent Parser

Recursive descent parser menurut Tremblay J.P. (1985, p219) adalah metode top-down parsing yang tidak mengijinkan adanya backup, namun teknik ini tidak dapat bekerja pada semua context free grammar. Beberapa grammar tetap memerlukan backup agar parsing berhasil.

Pada metode recursive descent parsing, production diimplementasikan dalam function call  untuk setiap nonterminal. Tiap function memiliki return value true atau false, tergantung apakah  substring yang mewakili nonterminal tersebut dapat dikenali atau tidak. Mekanisme pemrograman  untuk  menangani pemanggilan fungsi recursive menyediakan kemampuan untuk menangani stack yang diperlukan pada parsing, hal ini membebaskan user untuk membuat dan memanipulasi stack secara terpisah.

3.      Metode Bottom-up Parsing

Bentuk umum dari bottom-up parsing dikenal dengan nama shift-reduce parsing. Shift-reduce  parsing menurut Aho (2003, p195) berusaha untukmembentuk sebuah parse tree untuk sebuah input  string dimulai dari leave (bottom) dan bekerja menuju root (top). Proses ini dapat dilihat sebagai  “reducing” sebuah string w menjadi start symbol dari grammar. Pada setiap langkah reduction  sebuah  substring tertentu yang cocok dengan right side dari sebuah production digantikan dengan symbol dari leftsideproductio tersebut.

  

Sumber :

http://library.binus.ac.id/eColls/eThesis/Bab2/2006-2-01257-IF-Bab%202.pdf

Wikipedia

http://repository.ipb.ac.id/bitstream/handle/123456789/33139/Bab%20IV.%20Hasil%20%26%20Pembahasan%20G07ibf.pdf?sequence=12