Analisis leksikal, Bagian 2: Buat aplikasi

Bulan lalu saya melihat kelas-kelas yang disediakan Java untuk melakukan analisis leksikal dasar. Bulan ini saya akan membahas aplikasi sederhana yang digunakan StreamTokenizeruntuk mengimplementasikan kalkulator interaktif.

Untuk meninjau artikel bulan lalu secara singkat, ada dua kelas penganalisis leksikal yang disertakan dengan distribusi Java standar: StringTokenizerdan StreamTokenizer. Penganalisis ini mengubah masukan mereka menjadi token terpisah yang dapat digunakan pengurai untuk memahami masukan yang diberikan. Parser mengimplementasikan tata bahasa, yang didefinisikan sebagai satu atau lebih status tujuan yang dicapai dengan melihat berbagai urutan token. Ketika status tujuan pengurai tercapai, ia menjalankan beberapa tindakan. Ketika parser mendeteksi bahwa tidak ada kemungkinan status tujuan yang diberikan urutan token saat ini, pengurai mendefinisikannya sebagai status kesalahan. Saat parser mencapai status kesalahan, tindakan pemulihan akan dijalankan, yang mengembalikan parser ke titik di mana ia dapat mulai mengurai lagi. Biasanya, ini diimplementasikan dengan menggunakan token hingga parser kembali ke titik awal yang valid.

Bulan lalu saya menunjukkan kepada Anda beberapa metode yang digunakan StringTokenizeruntuk mengurai beberapa parameter input. Bulan ini saya akan menunjukkan kepada Anda aplikasi yang menggunakan StreamTokenizerobjek untuk mengurai aliran input dan mengimplementasikan kalkulator interaktif.

Membangun aplikasi

Contoh kami adalah kalkulator interaktif yang mirip dengan perintah Unix bc (1). Seperti yang akan Anda lihat, ini mendorong StreamTokenizerkelas ke tepi utilitasnya sebagai penganalisis leksikal. Dengan demikian, ini berfungsi sebagai demonstrasi yang baik tentang di mana garis antara penganalisis "sederhana" dan "kompleks" dapat ditarik. Contoh ini adalah aplikasi Java dan oleh karena itu berjalan paling baik dari baris perintah.

Sebagai ringkasan singkat dari kemampuannya, kalkulator menerima ekspresi dalam formulir

[nama variabel] "=" ekspresi 

Nama variabel bersifat opsional dan dapat berupa string karakter apa pun dalam rentang kata default. (Anda dapat menggunakan applet latihan dari artikel bulan lalu untuk menyegarkan ingatan Anda pada karakter ini.) Jika nama variabel dihilangkan, nilai ekspresi akan dicetak. Jika nama variabel ada, nilai ekspresi ditetapkan ke variabel. Setelah variabel ditetapkan, variabel tersebut dapat digunakan dalam ekspresi selanjutnya. Dengan demikian, mereka mengisi peran "kenangan" pada kalkulator genggam modern.

Ekspresi tersebut terdiri dari operan dalam bentuk konstanta numerik (presisi ganda, konstanta floating-point) atau nama variabel, operator, dan tanda kurung untuk mengelompokkan komputasi tertentu. Operator resmi adalah penjumlahan (+), pengurangan (-), perkalian (*), pembagian (/), bitwise AND (&), bitwise OR (|), bitwise XOR (#), exponentiation (^), dan negasi unary dengan minus (-) untuk hasil pelengkap dua atau bang (!) untuk hasil pelengkap satuan.

Selain pernyataan ini, aplikasi kalkulator kami juga dapat mengambil salah satu dari empat perintah: "dump," "clear," "help," dan "exit." The dumpperintah print semua variabel yang saat ini didefinisikan serta nilai-nilai mereka. The clearperintah menghapus semua variabel saat ini ditetapkan. The helpperintah print beberapa baris teks bantuan untuk mendapatkan pengguna mulai. The quitperintah menyebabkan aplikasi untuk keluar.

Seluruh aplikasi contoh terdiri dari dua parser - satu untuk perintah dan pernyataan, dan satu lagi untuk ekspresi.

Membangun parser perintah

Parser perintah diimplementasikan dalam kelas aplikasi untuk contoh STExample.java. (Lihat bagian Resources untuk pointer ke kode.) mainMetode untuk kelas tersebut didefinisikan di bawah ini. Aku akan menjelaskannya untukmu.

1 public static void main (String args []) melempar IOException {2 variabel Hashtable = new Hashtable (); 3 StreamTokenizer st = StreamTokenizer baru (System.in); 4 st.eolIsSignificant (benar); 5 st.lowerCaseMode (benar); 6 st .ordinaryChar ('/'); 7 st.ordinaryChar ('-');

Dalam kode di atas, hal pertama yang saya lakukan adalah mengalokasikan java.util.Hashtablekelas untuk menampung variabel. Setelah itu saya mengalokasikan StreamTokenizerdan menyesuaikannya sedikit dari defaultnya. Alasan perubahan tersebut adalah sebagai berikut:

  • eolIsSignificant disetel ke true sehingga tokenizer akan mengembalikan indikasi akhir baris. Saya menggunakan akhir baris sebagai titik di mana ekspresi berakhir.

  • lowerCaseMode disetel ke true sehingga nama variabel akan selalu dikembalikan dalam huruf kecil. Dengan cara ini, nama variabel tidak peka huruf besar kecil.

  • Karakter garis miring (/) disetel menjadi karakter biasa sehingga tidak akan digunakan untuk menunjukkan awal komentar, dan dapat digunakan sebagai operator pembagian.

  • Karakter minus (-) disetel menjadi karakter biasa sehingga string "3-3" akan menyegmentasikan menjadi tiga token - "3", "-", dan "3" - bukan hanya "3" dan "-3." (Ingat, penguraian angka disetel ke "aktif" secara default.)

Setelah tokenizer disiapkan, parser perintah berjalan dalam loop tak terbatas (hingga ia mengenali perintah "berhenti" di titik mana ia keluar). Ini ditunjukkan di bawah.

8 while (true) {9 Expression res; 10 int c = StreamTokenizer.TT_EOL; 11 String varName = null; 12 13 System.out.println ("Masukkan ekspresi ..."); 14 coba {15 while (true) {16 c = st.nextToken (); 17 jika (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} lain jika (c == StreamTokenizer.TT_EOL) {20 lanjutkan; 21} lain jika (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (variabel); 24 melanjutkan; 25} lain jika (st.sval.compareTo ("clear") == 0) {26 variabel = baru Hashtable (); 27 melanjutkan; 28} lain jika (st.sval.compareTo ("berhenti") == 0) {29 System.exit (0); 30} lain jika (st.sval.compareTo ("exit") == 0) {31 System.exit (0); 32} lain jika (st.sval.compareTo ("help") == 0) {33 help (); 34 melanjutkan; 35} 36 varName = st.sval; 37 c = st.nextToken ();38} 39 istirahat; 40} 41 if (c! = '=') {42 throw new SyntaxError ("missing initial '=' sign."); 43}

Seperti yang Anda lihat di baris 16, token pertama disebut dengan menerapkan nextTokenpada StreamTokenizerobjek. Ini mengembalikan nilai yang menunjukkan jenis token yang dipindai. Nilai yang dikembalikan akan menjadi salah satu konstanta yang ditentukan di StreamTokenizerkelas atau itu akan menjadi nilai karakter. Token "meta" (yang bukan sekadar nilai karakter) ditentukan sebagai berikut:

  • TT_EOF- Ini menunjukkan Anda berada di akhir aliran input. Tidak seperti StringTokenizer, tidak ada hasMoreTokensmetode.

  • TT_EOL - Ini memberi tahu Anda bahwa objek baru saja melewati urutan akhir baris.

  • TT_NUMBER - Jenis token ini memberi tahu kode parser Anda bahwa sebuah nomor telah terlihat pada input.

  • TT_WORD - Jenis token ini menunjukkan seluruh "kata" telah dipindai.

Jika hasilnya bukan salah satu dari konstanta di atas, itu adalah nilai karakter yang mewakili karakter dalam rentang karakter "biasa" yang dipindai atau salah satu karakter kutipan yang telah Anda setel. (Dalam kasus saya, tidak ada karakter kutipan diatur.) Ketika hasilnya adalah salah satu karakter kutipan Anda, string dikutip dapat ditemukan di variabel string instance svaldari StreamTokenizerobjek.

Kode pada baris 17 sampai 20 berhubungan dengan indikasi end-of-line dan end-of-file, sedangkan pada baris 21 klausa if diambil jika sebuah token kata dikembalikan. Dalam contoh sederhana ini, kata tersebut bisa berupa perintah atau nama variabel. Baris 22 hingga 35 berhubungan dengan empat kemungkinan perintah. Jika baris 36 tercapai, maka itu harus berupa nama variabel; akibatnya, program menyimpan salinan nama variabel dan mendapatkan token berikutnya, yang harus berupa tanda sama dengan.

Jika di baris 41 token bukan tanda sama dengan, pengurai sederhana kami mendeteksi status kesalahan dan membuat pengecualian untuk menandakannya. Saya membuat dua pengecualian umum, SyntaxErrordan ExecError, untuk membedakan kesalahan parse-time dari kesalahan run-time. The mainMetode berlanjut dengan garis 44 di bawah ini.

44 res = ParseExpression.expression (st); 45} menangkap (SyntaxError se) {46 res = null; 47 varName = null; 48 System.out.println ("\ nKesalahan Sintaks terdeteksi! -" + se.getMsg ()); 49 sementara (c! = StreamTokenizer.TT_EOL) 50 c = st.nextToken (); 51 lanjutkan; 52}

Pada baris 44 ekspresi di sebelah kanan dari tanda sama dengan diurai dengan ekspresi parser yang ditentukan di ParseExpressionkelas. Perhatikan bahwa baris 14 hingga 44 dibungkus dalam blok coba / tangkap yang menjebak kesalahan sintaks dan menanganinya. Saat kesalahan terdeteksi, tindakan pemulihan parser adalah menggunakan semua token hingga dan termasuk token akhir baris berikutnya. Ini ditunjukkan pada baris 49 dan 50 di atas.

Pada titik ini, jika pengecualian tidak dilemparkan, aplikasi telah berhasil mengurai pernyataan. Pemeriksaan terakhir adalah untuk melihat bahwa token berikutnya adalah akhir baris. Jika tidak, kesalahan tidak terdeteksi. Kesalahan paling umum adalah tanda kurung yang tidak cocok. Pemeriksaan ini ditunjukkan pada baris 53 hingga 60 dari kode di bawah ini.

53 c = st.nextToken (); 54 if (c! = StreamTokenizer.TT_EOL) {55 if (c == ')') 56 System.out.println ("\ nSyntax Error terdeteksi! - Ke banyak tanda kurung penutup."); 57 lainnya 58 System.out.println ("\ nToken palsu pada masukan -" + c); 59 sementara (c! = StreamTokenizer.TT_EOL) 60 c = st.nextToken (); 61} lagi {

When the next token is an end of line, the program executes lines 62 through 69 (shown below). This section of the method evaluates the parsed expression. If the variable name was set in line 36, the result is stored in the symbol table. In either case, if no exception is thrown, the expression and its value are printed to the System.out stream so that you can see what the parser decoded.

62 try { 63 Double z; 64 System.out.println("Parsed expression : "+res.unparse()); 65 z = new Double(res.value(variables)); 66 System.out.println("Value is : "+z); 67 if (varName != null) { 68 variables.put(varName, z); 69 System.out.println("Assigned to : "+varName); 70 } 71 } catch (ExecError ee) { 72 System.out.println("Execution error, "+ee.getMsg()+"!"); 73 } 74 } 75 } 76 } 

In the STExample class, the StreamTokenizer is being used by a command-processor parser. This type of parser commonly would be used in a shell program or in any situation in which the user issues commands interactively. The second parser is encapsulated in the ParseExpression class. (See the Resources section for the complete source.) This class parses the calculator's expressions and is invoked in line 44 above. It is here that StreamTokenizer faces its stiffest challenge.

Building an expression parser

The grammar for the calculator's expressions defines an algebraic syntax of the form "[item] operator [item]." This type of grammar comes up again and again and is called an operator grammar. A convenient notation for an operator grammar is:

id ( "OPERATOR" id )* 

The code above would be read "An ID terminal followed by zero or more occurrences of an operator-id tuple." The StreamTokenizer class would seem pretty ideal for analyzing such streams, because the design naturally breaks the input stream into word, number, and ordinary character tokens. As I'll show you, this is true up to a point.

The ParseExpression class is a straightforward, recursive-descent parser for expressions, right out of an undergraduate compiler-design class. The Expression method in this class is defined as follows:

1 ekspresi Ekspresi statis (StreamTokenizer st) menampilkan SyntaxError {2 Expression result; 3 boolean selesai = salah; 4 5 result = jumlah (st); 6 while (! Done) {7 try {8 switch (st.nextToken ()) 9 case '&': 10 result = new Expression (OP_AND, result, sum (st)); 11 istirahat; 12 case '23} catch (IOException ioe) {24 throw new SyntaxError ("Got an I / O Exception."); 25} 26} 27 hasil pengembalian; 28}