Analisis leksikal dan Java: Bagian 1

Analisis leksikal dan parsing

Saat menulis aplikasi Java, salah satu hal umum yang harus Anda buat adalah parser. Parser berkisar dari yang sederhana hingga yang kompleks dan digunakan untuk segala hal mulai dari melihat opsi baris perintah hingga menafsirkan kode sumber Java. Dalam JavaWorld edisi Desember, saya menunjukkan Jack, generator parser otomatis yang mengubah spesifikasi tata bahasa tingkat tinggi menjadi kelas Java yang mengimplementasikan pengurai yang dijelaskan oleh spesifikasi tersebut. Bulan ini saya akan menunjukkan kepada Anda sumber daya yang disediakan Java untuk menulis penganalisis dan pengurai leksikal yang ditargetkan. Parser yang lebih sederhana ini mengisi celah antara perbandingan string sederhana dan tata bahasa kompleks yang dikompilasi Jack.

Tujuan dari penganalisis leksikal adalah untuk mengambil aliran karakter input dan mendekodekannya menjadi token tingkat yang lebih tinggi yang dapat dipahami oleh parser. Parser menggunakan keluaran dari penganalisis leksikal dan beroperasi dengan menganalisis urutan token yang dikembalikan. Pengurai mencocokkan urutan ini dengan status akhir, yang mungkin merupakan salah satu dari banyak status akhir. Status akhir menentukan tujuandari parser. Saat keadaan akhir tercapai, program yang menggunakan parser melakukan beberapa tindakan - baik menyiapkan struktur data atau menjalankan beberapa kode khusus tindakan. Selain itu, parser dapat mendeteksi - dari urutan token yang telah diproses - saat tidak ada status akhir legal yang dapat dicapai; pada saat itu pengurai mengidentifikasi keadaan saat ini sebagai keadaan kesalahan. Terserah aplikasi untuk memutuskan tindakan apa yang harus diambil ketika parser mengidentifikasi status akhir atau status kesalahan.

Basis kelas Java standar mencakup beberapa kelas penganalisis leksikal, namun ia tidak mendefinisikan kelas parser untuk keperluan umum. Di kolom ini saya akan melihat secara mendalam pada penganalisis leksikal yang disertakan dengan Java.

Penganalisis leksikal Java

Spesifikasi Bahasa Java, versi 1.0.2, mendefinisikan dua kelas penganalisis leksikal, StringTokenizerdan StreamTokenizer. Dari namanya, Anda dapat menyimpulkan bahwa StringTokenizermenggunakan Stringobjek sebagai inputnya, dan StreamTokenizermenggunakan InputStreamobjek.

Kelas StringTokenizer

Dari dua kelas penganalisis leksikal yang tersedia, yang paling mudah dipahami adalah StringTokenizer. Saat Anda membuat StringTokenizerobjek baru , metode konstruktor secara nominal mengambil dua nilai - string input dan string pembatas. Kelas kemudian membuat urutan token yang mewakili karakter antara karakter pembatas.

Sebagai penganalisis leksikal, StringTokenizersecara formal dapat didefinisikan seperti di bawah ini.

[~ pembatas1, pembatas2, ..., pembatas N ] :: Token

Definisi ini terdiri dari ekspresi reguler yang cocok dengan setiap karakter kecuali karakter pemisah. Semua karakter yang cocok yang berdekatan dikumpulkan menjadi satu token dan dikembalikan sebagai Token.

Penggunaan kelas yang paling umum StringTokenizeradalah untuk memisahkan sekumpulan parameter - seperti daftar angka yang dipisahkan koma. StringTokenizersangat ideal dalam peran ini karena menghapus pemisah dan mengembalikan data. The StringTokenizerkelas juga menyediakan mekanisme untuk mengidentifikasi daftar yang ada "null" token. Anda akan menggunakan token nol dalam aplikasi yang beberapa parameternya memiliki nilai default atau tidak diharuskan ada di semua kasus.

Applet di bawah ini adalah alat StringTokenizerolah raga sederhana . Sumber applet StringTokenizer ada di sini. Untuk menggunakan applet, ketikkan beberapa teks yang akan dianalisis ke dalam area string input, kemudian ketikkan string yang terdiri dari karakter pemisah di area String Pemisah. Terakhir, klik Tokenize! tombol. Hasilnya akan muncul dalam daftar token di bawah string input dan akan diatur sebagai satu token per baris.

Anda memerlukan browser yang mendukung Java untuk melihat applet ini.

Pertimbangkan sebagai contoh string, "a, b, d", diteruskan ke StringTokenizerobjek yang telah dibangun dengan koma (,) sebagai karakter pemisah. Jika Anda meletakkan nilai-nilai ini di applet latihan di atas Anda akan melihat bahwa Tokenizerobjek mengembalikan string "a," "b," dan "d." Jika niat Anda adalah untuk mencatat bahwa satu parameter hilang, Anda mungkin terkejut tidak melihat indikasi ini dalam urutan token. Kemampuan untuk mendeteksi token yang hilang diaktifkan oleh boolean Return Separator yang dapat disetel saat Anda membuat Tokenizerobjek. Dengan parameter ini disetel saat Tokenizerdibuat, setiap pemisah juga dikembalikan. Klik kotak centang untuk Return Separator di applet di atas, dan biarkan string dan pemisahnya sendiri. SekarangTokenizermengembalikan "a, koma, b, koma, koma, dan d." Dengan mencatat bahwa Anda mendapatkan dua karakter pemisah secara berurutan, Anda dapat menentukan bahwa token "null" disertakan dalam string input.

Trik agar berhasil menggunakan StringTokenizerdalam parser adalah mendefinisikan input sedemikian rupa sehingga karakter pembatas tidak muncul dalam data. Jelas Anda dapat menghindari batasan ini dengan mendesainnya di aplikasi Anda. Definisi metode di bawah ini dapat digunakan sebagai bagian dari applet yang menerima warna dalam bentuk nilai merah, hijau, dan biru dalam aliran parameternya.

/ ** * Parse parameter bentuk "10,20,30" sebagai * RGB tuple untuk nilai warna. * / 1 Warna getColor (Nama string) {2 Data string; 3 StringTokenizer st; 4 int merah, hijau, biru; 5 6 data = getParameter (nama); 7 jika (data == null) 8 mengembalikan null; 9 10 st = new StringTokenizer (data, ","); 11 coba {12 red = Integer.parseInt (st.nextToken ()); 13 hijau = Integer.parseInt (st.nextToken ()); 14 biru = Integer.parseInt (st.nextToken ()); 15} catch (Exception e) {16 return null; // (ERROR STATE) tidak bisa mengurai 17} 18 return new Color (merah, hijau, biru); // (END STATE) selesai. 19}

Kode di atas mengimplementasikan parser yang sangat sederhana yang membaca string "number, number, number" dan mengembalikan Colorobjek baru . Di baris 10, kode membuat StringTokenizerobjek baru yang berisi data parameter (anggap metode ini adalah bagian dari applet), dan daftar karakter pemisah yang terdiri dari koma. Kemudian pada baris 12, 13, dan 14, setiap token diekstraksi dari string tersebut dan diubah menjadi angka menggunakan parseIntmetode Integer . Konversi ini dikelilingi oleh try/catchblok jika string angka bukanlah angka yang valid atau Tokenizermelontarkan pengecualian karena token telah habis. Jika semua angka dikonversi, status akhir tercapai dan Colorobjek dikembalikan; jika tidak, status kesalahan tercapai dan null dikembalikan.

Salah satu fitur StringTokenizerkelas ini adalah mudah ditumpuk. Lihatlah metode yang disebutkan di getColorbawah ini, yaitu baris 10 hingga 18 dari metode di atas.

/ ** * Parsing tupel warna "r, g, b" menjadi Colorobjek AWT . * / 1 Color getColor (String data) {2 int red, green, blue; 3 StringTokenizer st = new StringTokenizer (data, ","); 4 coba {5 red = Integer.parseInt (st.nextToken ()); 6 hijau = Integer.parseInt (st.nextToken ()); 7 biru = Integer.parseInt (st.nextToken ()); 8} catch (Exception e) {9 return null; // (ERROR STATE) tidak dapat mengurai 10} 11 return new Color (merah, hijau, biru); // (END STATE) selesai. 12}

Parser yang sedikit lebih kompleks ditunjukkan pada kode di bawah ini. Parser ini diimplementasikan dalam metode getColors, yang didefinisikan untuk mengembalikan larik Colorobjek.

/ ** * Parsing sekumpulan warna "r1, g1, b1: r2, g2, b2: ...: rn, gn, bn" ke dalam * larik objek AWT Color. * / 1 Warna [] getColors (Data string) {2 Vektor akumulasi = Vektor baru (); 3 Warna cl, hasil []; 4 StringTokenizer st = new StringTokenizer (data, ":"); 5 while (st.hasMoreTokens ()) {6 cl = getColor (st.nextToken ()); 7 jika (cl! = Null) {8 acc.addElement (cl); 9} lain {10 System.out.println ("Kesalahan - warna buruk."); 11} 12} 13 jika (akum.size () == 0) 14 mengembalikan nol; 15 hasil = Warna baru [akum.size ()]; 16 untuk (int i = 0; i <akum.size (); i ++) {17 result [i] = (Color) akum.elementAt (i); 18} 19 hasil pengembalian; 20}

Pada metode di atas, yang hanya sedikit berbeda dari getColormetode, kode pada baris 4 hingga 12 membuat Tokenizertoken baru untuk mengekstrak yang dikelilingi oleh karakter titik dua (:). Seperti yang dapat Anda baca di komentar dokumentasi untuk metode tersebut, metode ini mengharapkan tupel warna dipisahkan oleh titik dua. Setiap panggilan ke nextTokendalam StringTokenizerkelas akan mengembalikan token baru hingga string habis. Token yang dikembalikan akan menjadi rangkaian angka yang dipisahkan dengan koma; string token ini diumpankan getColor, yang kemudian mengekstrak warna dari tiga angka. Membuat StringTokenizerobjek baru menggunakan token yang dikembalikan oleh StringTokenizerobjek lain memungkinkan kode parser yang telah kita tulis menjadi sedikit lebih canggih tentang cara menafsirkan input string.

Meskipun berguna, Anda pada akhirnya akan kehabisan kemampuan StringTokenizerkelas dan harus beralih ke kakaknya StreamTokenizer.

Kelas StreamTokenizer

Seperti yang disarankan oleh nama kelas, sebuah StreamTokenizerobjek mengharapkan masukannya berasal dari InputStreamkelas. Seperti di StringTokenizeratas, kelas ini mengubah aliran input menjadi potongan-potongan yang dapat diinterpretasikan oleh kode parsing Anda, tetapi di situlah kesamaan berakhir.

StreamTokenizeradalah penganalisis leksikal berbasis tabel . Ini berarti bahwa setiap karakter input yang mungkin diberikan signifikansi, dan pemindai menggunakan signifikansi karakter saat ini untuk memutuskan apa yang harus dilakukan. Dalam pelaksanaan kelas ini, karakter diberikan salah satu dari tiga kategori. Ini adalah:

  • Karakter spasi - signifikansi leksikal mereka terbatas pada kata-kata pemisah

  • Karakter kata - mereka harus dikumpulkan saat bersebelahan dengan karakter kata lain

  • Karakter biasa - mereka harus segera dikembalikan ke parser

Bayangkan implementasi kelas ini sebagai mesin status sederhana yang memiliki dua status - idle dan terakumulasi . Di setiap negara bagian, masukan adalah karakter dari salah satu kategori di atas. Kelas membaca karakter, memeriksa kategorinya dan melakukan beberapa tindakan, dan melanjutkan ke status berikutnya. Tabel berikut menunjukkan mesin status ini.

Negara Memasukkan Tindakan Negara bagian baru
diam karakter kata mendorong kembali karakter mengumpulkan
karakter biasa karakter kembali diam
karakter spasi mengkonsumsi karakter diam
mengumpulkan karakter kata tambahkan ke kata saat ini mengumpulkan
karakter biasa

mengembalikan kata saat ini

mendorong kembali karakter

diam
karakter spasi

mengembalikan kata saat ini

mengkonsumsi karakter

diam

Di atas mekanisme sederhana ini, StreamTokenizerkelas menambahkan beberapa heuristik. Ini termasuk pemrosesan angka, pemrosesan string kutipan, pemrosesan komentar, dan pemrosesan akhir baris.

The first example is number processing. Certain character sequences can be interpreted as representing a numerical value. For example, the sequence of characters 1, 0, 0, ., and 0 adjacent to each other in the input stream represent the numerical value 100.0. When all of the digit characters (0 through 9), the dot character (.), and the minus (-) character are specified as being part of the word set, the StreamTokenizer class can be told to interpret the word it is about to return as a possible number. Setting this mode is achieved by calling the parseNumbers method on the tokenizer object that you instantiated (this is the default). If the analyzer is in the accumulate state, and the next character would not be part of a number, the currently accumulated word is checked to see if it is a valid number. If it is valid, it is returned, and the scanner moves to the next appropriate state.

Contoh berikutnya adalah pemrosesan string yang dikutip. Seringkali diinginkan untuk meneruskan string yang diapit oleh karakter kutipan (biasanya tanda kutip ganda (") atau tunggal (')) sebagai token tunggal. StreamTokenizerKelas memungkinkan Anda menentukan karakter apa pun sebagai karakter kutipan. Secara default, mereka adalah karakter petik tunggal (') dan petik ganda ("). Mesin status dimodifikasi untuk menggunakan karakter dalam status terakumulasi hingga karakter kutipan lain atau karakter akhir baris diproses. Untuk memungkinkan Anda mengutip karakter kutipan, penganalisis memperlakukan karakter kutipan yang diawali dengan garis miring ke belakang (\) di aliran input dan di dalam kutipan sebagai karakter kata.