Lemon parser generator adalah sebuah parser generator seperti YACC dan Bison yang pada awalnya dikembangkan untuk SQLite project. Namun Lemon Parser berbeda dengan YACC dan Bison, format grammarnya dibuat berbeda untuk mengurangi kesalahan coding. Selain itu Lemon Parser menghasilkan parser yang reentrant and thread-safe.

Tak ada pendefinisian terminal dan nonterminal dalam Lemon

Di dalam YACC/BISON, dikenal adanya terminal dan non terminal. Sebuah terminal simbol (token) adalah sebuah string yang tersusun dari karakter alphanumeric dan underscore yang diawali dengan huruf besar. Sebuah terminal dapat tersusun dari huruf kecil setelah huruf pertama, namun biasanya menurut konvensi semua huruf terminal adalah huruf besar. Kebalikannya adalah nonterminal yang diawali dengan huruf kecil. Namun sesuai konvensi umum, semua huruf nonterminal adalah huruf kecil.

Dalam lemon, simbol terminal dan nonterminal tidak harus dideklarasikan dalam bagian yang berbeda dalam sebuah file grammar. Lemon mampu menggenerate sebuah list yang berisi terminal dan nonterminal dengan cara ‘menyelidiki’ aturan grammar dan lemon juga selalu dapat membedakan terminal dan nonterminal dengan cara mengecek huruf pertama dari nama simbol.

YACC dan BISON mengijinkan simbol terminal disusun dari karakter yang bukan alphanumeric atau underscore dengan menyertakan single quotes misalnya ‘)’ atau ‘&’. Sedangkan lemon tidak mengijinkan hal ini. Semua simbol, baik terminal maupun non terminal harus tersusun atas karakter alphanumeric.

Aturan Grammar

Secara umum dapat grammar dalam lemon dideklarasikan dalam bentuk:

expr ::= expr PLUS expr.
expr ::= VALUE.

Dari contoh deklarasi diatas, dapet dilihat ada 1 simbol nonterminal yaitu expr dan 2 simbol terminal yaitu PLUS dan VALUE. Seperti YACC dan BISON, setelah pendefinisian rule, dapat didefinisikan sebuah fungsi yang akan dijalankan ketika rule tersebut terpenuhi. Misalnya saja:

expr ::= expr PLUS expr.   { printf("Doing an addition...\n"); }

Tidak seperti Yacc/Bison yang menggunakan karakter $ diikuti angka untuk mendefinisikan varibel, Lemon menggunakan variable yang dideklarasikan didalam rule misalnya:

Yacc/Bison:

expr -> expr PLUS expr  { $$ = $1 + $3; };

Lemon:

expr(A) ::= expr(B) PLUS expr(C).  { A = B+C; }

Hal ini untuk memudahkan dan mengurangi kesalahan yang  mungkin timbul akibat salah perhitungan variable seperti dalam Yacc/Bison. Selain itu akan mudah diingat dan dilihat.

Dan Greg Beaver membuat PHP_ParserGenerator, sebuah parser generator dari sebuah file dengan format Lemon Parser generator menjadi sebuah PHP5 parser. Namun ada sedikit perbedaan antara lain:

• %extra_argument dihilangkan, argument dapat didefinisikan dalam class constructor.
• %token_type tidak relevan dalam PHP, sehingga dihilangkan.
• %declare_class ditambahkan untuk mendefinisikan nama dari class Parser dan semua informasi implements/extend.
• %include_class ditambahkan agar memungkinkan untuk memasukkan informasi tambahan mengenai class, seperti constant, class constructor dan lain-lain.

Tentunya setelah kita mempunyai parser, kita membutuhkan lexer. Dan bisa saja sebenarnya membuat sendiri. Tapi Greg pun sudah membuatkan generator, yaitu PHP_LexerGenerator. Lexer ini bisa membuatkan parser PHP5 berdasarkan sebuah file dengan format re2c.

Secara umum, sebuah file minimal harus ada tiga bagian khusus yang seperti ini

<?php
class TermLexer
{

private $data;
public $counter;
public $token;
public $value;
public $node;
public $line;
private $state = 1;

function __construct($data)
{
$this->data = $data;
$this->counter = 0;
$this->line = 1;
}

/*!lex2php
%input $this->data
%counter $this->counter
%token $this->token
%value $this->value
%line $this->line
number = /[0-9]+(\.[0-9]+)?/
other=/./
*/
/*!lex2php
%statename START

number {
$this->token = TermParser::TP_NUMBER;
}
other {
return false;
}

*/

Bagian yang pertama adalah bagian deklarasi class. Minimal harus seperti itu, tapi bisa ditambahkan misalnya nama classnya bisa diganti, bisa menambahkan fungsi, variabel dan lain-lain.

Bagian yang kedua adalah deklarasi token apa yang akan diambil. Diatas dapat dilihat bahwa kita mengambil number. Formatnya adalah regular expression. Selain regular expression, dapet juga menggunakan quoted string. misalnya variable = “buaya”. Maka setiap ada string buaya, maka lexer akan mengembalikan token variable.

Bagian yang ketiga adalah deklarasi fungsi apa yang harus dieksekusi ketika token ditemukan/sesuai. Di bagian ini, kita harus menentukan minimal seperti

number {
$this->token = TermParser::TP_NUMBER;
}

Kode diatas berarti token yang didapatkan dari ‘number’, akan dijadikan simbol terminal dalam class TermParser, yang dalam kasus ini kita buat dengan PHP_ParserGenerator, dengan nama TP_NUMBER. Pada bagian other, mengembalikan nilai false. Ini artinya token yang sesuai akan diabaikan oleh lexer.

Setelah parser generator dan lexer generator ada, maka setelah ini kita membutuhkan parser kata dasar dalam Bahasa Indonesia yang akan dikolaborasikan dengan Lexer dari PHP_LexerGenerator. Kenapa begitu? Karena dalam kalimat bahasa indonesia, tidak semuanya tersusun dari kata dasar. Akan ada imbuhan dan sisipan.

Pertama saya menyusun parsing imbuhan. Sebelum menyusun parser, tentunya saya harus mengetahui ada imbuhan apa saja yang ada di dalam Bahasa Indonesia.

Postingan ini belum selesai. masih akan diedit dan dilanjutkan. Tapi bolehlah dibaca dulu.. 😀