Bangun bahasa Anda sendiri dengan JavaCC

Pernahkah Anda bertanya-tanya bagaimana kompilator Java bekerja? Apakah Anda perlu menulis parser untuk dokumen markup yang tidak berlangganan format standar seperti HTML atau XML? Atau apakah Anda ingin menerapkan bahasa pemrograman kecil Anda sendiri hanya untuk itu? JavaCCmemungkinkan Anda melakukan semua itu di Java. Jadi, apakah Anda hanya tertarik untuk mempelajari lebih lanjut tentang cara kerja compiler dan interpreter, atau Anda memiliki ambisi konkret untuk menciptakan penerus bahasa pemrograman Java, silakan bergabung dengan saya dalam pencarian bulan ini untuk menjelajah JavaCC, yang disorot oleh konstruksi sedikit berguna kalkulator baris perintah.

Dasar-dasar konstruksi penyusun

Bahasa pemrograman sering dibagi, agak artifisial, menjadi bahasa yang dikompilasi dan ditafsirkan, meskipun batas-batasnya menjadi kabur. Karena itu, jangan khawatir. Konsep yang dibahas di sini berlaku sama baiknya untuk bahasa yang dihimpun maupun ditafsirkan. Kami akan menggunakan kata compiler di bawah ini, tetapi untuk cakupan artikel ini, itu termasuk arti dari interpreter.

Penyusun harus melakukan tiga tugas utama saat disajikan dengan teks program (kode sumber):

  1. Analisis leksikal
  2. Analisis sintaksis
  3. Pembuatan atau eksekusi kode

Sebagian besar pekerjaan penyusun berpusat di sekitar langkah 1 dan 2, yang melibatkan pemahaman kode sumber program dan memastikan kebenaran sintaksisnya. Kami menyebutnya proses parsing , yang merupakan tanggung jawab parser .

Analisis leksikal (lexing)

Analisis leksikal mengambil pandangan sepintas pada kode sumber program dan membaginya menjadi token yang tepat . Token adalah bagian penting dari kode sumber program. Contoh token termasuk kata kunci, tanda baca, literal seperti angka, dan string. Nontoken menyertakan spasi, yang sering diabaikan tetapi digunakan untuk memisahkan token, dan komentar.

Analisis sintaksis (parsing)

Selama analisis sintaksis, parser mengekstrak makna dari kode sumber program dengan memastikan kebenaran sintaksis program dan dengan membangun representasi internal program.

Teori bahasa komputer berbicara tentang program, tata bahasa, dan bahasa. Dalam artian, program adalah urutan token. Literal adalah elemen bahasa komputer dasar yang tidak dapat direduksi lebih lanjut. Tata bahasa mendefinisikan aturan untuk membangun program yang benar secara sintaksis. Hanya program yang bermain sesuai aturan yang ditentukan dalam tata bahasa yang benar. Bahasa hanyalah kumpulan dari semua program yang memenuhi semua aturan tata bahasa Anda.

Selama analisis sintaksis, kompilator memeriksa kode sumber program sehubungan dengan aturan yang ditentukan dalam tata bahasa bahasa. Jika ada aturan tata bahasa yang dilanggar, kompilator menampilkan pesan kesalahan. Sepanjang jalan, saat memeriksa program, kompilator membuat representasi internal yang mudah diproses dari program komputer.

Aturan tata bahasa komputer dapat ditentukan dengan jelas dan secara keseluruhan dengan notasi EBNF (Extended Backus-Naur-Form) (untuk lebih lanjut tentang EBNF, lihat Sumber). EBNF mendefinisikan tata bahasa dalam hal aturan produksi. Aturan produksi menyatakan bahwa elemen tata bahasa - baik literal atau elemen tersusun - dapat terdiri dari elemen tata bahasa lain. Literal, yang tidak dapat direduksi, adalah kata kunci atau fragmen teks program statis, seperti simbol tanda baca. Elemen tersusun diturunkan dengan menerapkan aturan produksi. Aturan produksi memiliki format umum berikut:

GRAMMAR_ELEMENT: = daftar elemen tata bahasa | daftar alternatif elemen tata bahasa

Sebagai contoh, mari kita lihat aturan tata bahasa untuk bahasa kecil yang menjelaskan ekspresi aritmatika dasar:

expr: = angka | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | '(' expr ')' | - nomor expr: = digit + ('.' digit +)? digit: = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

Tiga aturan produksi menentukan elemen tata bahasa:

  • expr
  • number
  • digit

Bahasa yang ditentukan oleh tata bahasa itu memungkinkan kita untuk menentukan ekspresi aritmatika. An expradalah bilangan atau salah satu dari empat operator infiks yang diterapkan ke dua exprs, an exprdalam tanda kurung, atau negatif expr. A numberadalah bilangan floating-point dengan pecahan desimal opsional. Kami mendefinisikan a digitmenjadi salah satu digit desimal yang sudah dikenal.

Pembuatan atau eksekusi kode

Setelah parser berhasil mem-parsing program tanpa kesalahan, itu ada dalam representasi internal yang mudah diproses oleh kompilator. Sekarang relatif mudah untuk menghasilkan kode mesin (atau bytecode Java dalam hal ini) dari representasi internal atau untuk menjalankan representasi internal secara langsung. Jika kita melakukan yang pertama, kita sedang menyusun; dalam kasus terakhir, kita berbicara tentang penafsiran.

JavaCC

JavaCC, tersedia secara gratis, adalah generator parser. Ini menyediakan ekstensi bahasa Java untuk menentukan tata bahasa bahasa pemrograman. JavaCCdikembangkan pada awalnya oleh Sun Microsystems, tetapi sekarang dikelola oleh MetaMata. Seperti alat pemrograman yang layak, JavaCCsebenarnya digunakan untuk menentukan tata bahasa dari JavaCCformat masukan.

Selain itu, JavaCCmemungkinkan kami untuk mendefinisikan tata bahasa dengan cara yang mirip dengan EBNF, sehingga mudah untuk menerjemahkan tata bahasa EBNF ke dalam JavaCCformat. Selanjutnya, JavaCCadalah generator parser paling populer untuk Java, dengan sejumlah JavaCCtata bahasa yang telah ditentukan tersedia untuk digunakan sebagai titik awal.

Mengembangkan kalkulator sederhana

Kami sekarang mengunjungi kembali bahasa aritmatika kecil kami untuk membuat kalkulator baris perintah sederhana di Java menggunakan JavaCC. Pertama, kita harus menerjemahkan tata bahasa EBNF ke dalam JavaCCformat dan menyimpannya di file Arithmetic.jj:

opsi {LOOKAHEAD = 2; } PARSER_BEGIN (Aritmatika) kelas publik Aritmatika {} PARSER_END (Aritmatika) SKIP: "\ t" TOKEN: double expr (): {} term () ("+" expr () double term (): {} "/" term ()) * unary ganda (): {} "-" elemen () elemen ganda (): {} "(" expr () ")"  

Kode di atas akan memberi Anda gambaran tentang cara menentukan tata bahasa JavaCC. The optionsBagian di atas menetapkan satu set pilihan untuk tata bahasa itu. Kami menetapkan tampilan 2. JavaCCFitur debugging kontrol opsi tambahan dan banyak lagi. Opsi tersebut dapat ditentukan sebagai alternatif pada JavaCCbaris perintah.

The PARSER_BEGINklausul menetapkan bahwa definisi kelas parser berikut. JavaCCmenghasilkan satu kelas Java untuk setiap parser. Kami menyebutnya kelas parser Arithmetic. Untuk saat ini, kami hanya memerlukan definisi kelas kosong; JavaCCakan menambahkan deklarasi terkait parsing nanti. Kami mengakhiri definisi kelas dengan PARSER_ENDklausa.

The SKIPBagian mengidentifikasi karakter kita ingin melompat. Dalam kasus kami, itu adalah karakter spasi putih. Selanjutnya, kami mendefinisikan token bahasa kami di TOKENbagian tersebut. Kami mendefinisikan angka dan angka sebagai token. Perhatikan bahwa JavaCCmembedakan antara definisi token dan definisi untuk aturan produksi lainnya, yang berbeda dari EBNF. Bagian SKIPdan TOKENmenentukan analisis leksikal tata bahasa ini.

Next, we define the production rule for expr, the top-level grammar element. Notice how that definition markedly differs from the definition of expr in EBNF. What's happening? Well, it turns out that the EBNF definition above is ambiguous, as it allows multiple representations of the same program. For example, let us examine the expression 1+2*3. We can match 1+2 into an expr yielding expr*3, as in Figure 1.

Or, alternatively, we could first match 2*3 into an expr resulting in 1+expr, as shown in Figure 2.

With JavaCC, we have to specify the grammar rules unambiguously. As a result, we break out the definition of expr into three production rules, defining the grammar elements expr, term, unary, and element. Now, the expression 1+2*3 is parsed as shown in Figure 3.

From the command line we can run JavaCC to check our grammar:

javacc Arithmetic.jj Java Compiler Compiler Version 1.1 (Parser Generator) Copyright (c) 1996-1999 Sun Microsystems, Inc. Copyright (c) 1997-1999 Metamata, Inc. (type "javacc" with no arguments for help) Reading from file Arithmetic.jj . . . Warning: Lookahead adequacy checking not being performed since option LOOKAHEAD is more than 1. Set option FORCE_LA_CHECK to true to force checking. Parser generated with 0 errors and 1 warnings. 

The following checks our grammar definition for problems and generates a set of Java source files:

TokenMgrError.java ParseException.java Token.java ASCII_CharStream.java Arithmetic.java ArithmeticConstants.java ArithmeticTokenManager.java 

Together these files implement the parser in Java. You can invoke this parser by instantiating an instance of the Arithmetic class:

public class Arithmetic implements ArithmeticConstants { public Arithmetic(java.io.InputStream stream) { ... } public Arithmetic(java.io.Reader stream) { ... } public Arithmetic(ArithmeticTokenManager tm) { ... } static final public double expr() throws ParseException { ... } static final public double term() throws ParseException { ... } static final public double unary() throws ParseException { ... } static final public double element() throws ParseException { ... } static public void ReInit(java.io.InputStream stream) { ... } static public void ReInit(java.io.Reader stream) { ... } public void ReInit(ArithmeticTokenManager tm) { ... } static final public Token getNextToken() { ... } static final public Token getToken(int index) { ... } static final public ParseException generateParseException() { ... } static final public void enable_tracing() { ... } static final public void disable_tracing() { ... } } 

If you wanted to use this parser, you must create an instance using one of the constructors. The constructors allow you to pass in either an InputStream, a Reader, or an ArithmeticTokenManager as the source of the program source code. Next, you specify the main grammar element of your language, for example:

Arithmetic parser = new Arithmetic(System.in); parser.expr(); 

However, nothing much happens yet because in Arithmetic.jj we've only defined the grammar rules. We have not yet added the code necessary to perform the calculations. To do so, we add appropriate actions to the grammar rules. Calcualtor.jj contains the complete calculator, including actions:

options { LOOKAHEAD=2; } PARSER_BEGIN(Calculator) public class Calculator { public static void main(String args[]) throws ParseException { Calculator parser = new Calculator(System.in); while (true) { parser.parseOneLine(); } } } PARSER_END(Calculator) SKIP :  "\t"  TOKEN:    void parseOneLine(): { double a; } { a=expr()  { System.out.println(a); } |  |  { System.exit(-1); } } double expr(): { double a; double b; } { a=term() ( "+" b=expr() { a += b; } | "-" b=expr() { a -= b; } )* { return a; } } double term(): { double a; double b; } { a=unary() ( "*" b=term() { a *= b; } | "/" b=term() { a /= b; } )* { return a; } } double unary(): { double a; } { "-" a=element() { return -a; } | a=element() { return a; } } double element(): { Token t; double a; } { t= { return Double.parseDouble(t.toString()); } | "(" a=expr() ")" { return a; } } 

The main method first instantiates a parser object that reads from standard input and then calls parseOneLine() in an endless loop. The method parseOneLine() itself is defined by an additional grammar rule. That rule simply defines that we expect every expression on a line by itself, that it is OK to enter empty lines, and that we terminate the program if we reach the end of the file.

Kami telah mengubah jenis kembalian dari elemen tata bahasa asli untuk dikembalikan double. Kami melakukan penghitungan yang tepat tepat di tempat kami mengurai dan meneruskan hasil penghitungan ke pohon panggilan. Kami juga telah mengubah definisi elemen tata bahasa untuk menyimpan hasilnya dalam variabel lokal. Misalnya, a=element()mem-parsing elementdan menyimpan hasilnya dalam variabel a. Itu memungkinkan kita untuk menggunakan hasil elemen yang diurai dalam kode tindakan di sisi kanan. Tindakan adalah blok kode Java yang dijalankan ketika aturan tata bahasa terkait telah menemukan kecocokan dalam aliran masukan.

Harap perhatikan betapa sedikit kode Java yang kami tambahkan untuk membuat kalkulator berfungsi penuh. Selain itu, menambahkan fungsionalitas tambahan, seperti fungsi bawaan atau bahkan variabel itu mudah.