Analisis leksikal, Bahagian 2: Membina aplikasi

Bulan lalu saya melihat kelas yang disediakan Java untuk melakukan analisis leksikal asas. Bulan ini saya akan melalui aplikasi mudah yang digunakan StreamTokenizeruntuk melaksanakan kalkulator interaktif.

Untuk meninjau artikel bulan lalu secara ringkas, terdapat dua kelas penganalisis leksikal yang disertakan dengan taburan Java standard: StringTokenizerdan StreamTokenizer. Penganalisis ini menukar input mereka menjadi token diskrit yang dapat digunakan pengurai untuk memahami input yang diberikan. Pengurai menerapkan tatabahasa, yang ditakrifkan sebagai satu atau lebih keadaan matlamat yang dicapai dengan melihat pelbagai urutan token. Apabila keadaan tujuan pengurai tercapai, ia akan melaksanakan beberapa tindakan. Apabila penghurai mengesan bahawa tidak ada keadaan matlamat yang mungkin diberikan mengikut urutan token semasa, ia menentukan ini sebagai keadaan ralat. Apabila pengurai mencapai keadaan ralat, ia menjalankan tindakan pemulihan, yang menjadikan pengurai kembali ke titik di mana ia dapat mula mengurai semula. Biasanya, ini dilaksanakan dengan menggunakan token sehingga penghurai kembali ke titik permulaan yang sah.

Bulan lalu saya menunjukkan kepada anda beberapa kaedah yang menggunakan StringTokenizeruntuk menguraikan beberapa parameter input. Bulan ini saya akan menunjukkan kepada anda aplikasi yang menggunakan StreamTokenizerobjek untuk menguraikan aliran input dan melaksanakan kalkulator interaktif.

Membina aplikasi

Contoh kami adalah kalkulator interaktif yang serupa dengan perintah Unix bc (1). Seperti yang akan anda lihat, ia mendorong StreamTokenizerkelas tepat ke pinggir kegunaannya sebagai penganalisis leksikal. Oleh itu, ia berfungsi sebagai demonstrasi yang baik di mana garis antara penganalisis "sederhana" dan "kompleks" dapat dilukis. Contoh ini adalah aplikasi Java dan oleh itu berjalan terbaik dari baris arahan.

Sebagai ringkasan kemampuannya, kalkulator menerima ungkapan dalam bentuk

[nama pemboleh ubah] "=" ungkapan 

Nama pemboleh ubah adalah pilihan dan boleh menjadi rentetan watak dalam rangkai kata lalai. (Anda boleh menggunakan applet olahragawan dari artikel bulan lalu untuk menyegarkan ingatan anda mengenai watak-watak ini.) Jika nama pembolehubah dihilangkan, nilai ungkapan itu hanya dicetak. Sekiranya nama pemboleh ubah ada, nilai ungkapan diberikan kepada pemboleh ubah. Setelah pemboleh ubah ditugaskan, mereka boleh digunakan dalam ungkapan kemudian. Oleh itu, mereka mengisi peranan "kenangan" pada kalkulator genggam moden.

Ungkapan ini terdiri daripada operan dalam bentuk pemalar numerik (ketepatan berganda, pemalar titik terapung) atau nama pemboleh ubah, operator, dan tanda kurung untuk mengelompokkan pengiraan tertentu. Pengendali sah adalah penambahan (+), pengurangan (-), pendaraban (*), pembahagian (/), bitwise AND (&), bitwise OR (|), bitwise XOR (#), exponentiation (^), dan negation unary dengan sama ada tolak (-) untuk hasil pelengkap dua atau bang (!) untuk hasil pelengkap yang sama.

Sebagai tambahan kepada pernyataan ini, aplikasi kalkulator kami juga dapat menggunakan salah satu dari empat perintah: "dump," "clear," "help," dan "quit." The dumpcetakan arahan keluar semua pembolehubah yang ditentukan pada masa ini serta nilai-nilai mereka. The cleararahan memadamkan semua pembolehubah kini jelas. The helpcetakan arahan daripada beberapa baris teks bantuan untuk pengguna bermula. The quitarahan menyebabkan permohonan untuk keluar.

Aplikasi contoh keseluruhan terdiri daripada dua penghurai - satu untuk perintah dan pernyataan, dan satu untuk ungkapan.

Membina penghurai arahan

Penghurai arahan dilaksanakan di kelas aplikasi untuk contoh STExample.java. (Lihat bahagian Sumber untuk penunjuk kod.) mainKaedah untuk kelas itu ditentukan di bawah. Saya akan meneliti kepingan untuk anda.

1 public static void main (String args []) melemparkan IOException {2 pemboleh ubah Hashtable = Hashtable baru (); 3 StreamTokenizer st = StreamTokenizer baru (System.in); 4 st.eolIsSignificant (benar); 5 st.lowerCaseMode (benar); 6 st. Luar Biasa ('/'); 7st. Luar Biasa ('-');

Dalam kod di atas perkara pertama yang saya lakukan adalah memperuntukkan java.util.Hashtablekelas untuk menahan pemboleh ubah. Selepas itu saya memperuntukkan a StreamTokenizerdan menyesuaikannya sedikit dari lalai. Rasional perubahan adalah seperti berikut:

  • eolIsSignificant ditetapkan ke true sehingga tokenizer akan mengembalikan petunjuk akhir baris. Saya menggunakan hujung baris sebagai titik di mana ungkapan berakhir.

  • lowerCaseMode diset ke true sehingga nama pemboleh ubah akan selalu dikembalikan dengan huruf kecil. Dengan cara ini, nama pemboleh ubah tidak peka huruf besar kecil.

  • Karakter slash (/) diatur menjadi karakter biasa sehingga tidak akan digunakan untuk menunjukkan permulaan komentar, dan dapat digunakan sebagai operator bahagian.

  • Karakter tolak (-) ditetapkan menjadi watak biasa sehingga rentetan "3-3" akan terbahagi kepada tiga token - "3", "-", dan "3" - bukan hanya "3" dan "-3." (Ingat, penghuraian nombor ditetapkan ke "aktif" secara lalai.)

Setelah tokenizer disiapkan, penghurai perintah berjalan dalam gelung tak terhingga (sehingga ia mengenali perintah "berhenti" pada titik keluar) Ini ditunjukkan di bawah.

8 sementara (benar) {9 Penyataan ekspresi; 10 int c = StreamTokenizer.TT_EOL; 11 rentetan varName = null; 12 13 System.out.println ("Masukkan ungkapan ..."); 14 cuba {15 sambil (benar) {16 c = st.nextToken (); 17 jika (c == StreamTokenizer.TT_EOF) {18 System.exit (1); 19} lain jika (c == StreamTokenizer.TT_EOL) {20 teruskan; 21} lain jika (c == StreamTokenizer.TT_WORD) {22 if (st.sval.compareTo ("dump") == 0) {23 dumpVariables (pemboleh ubah); 24 teruskan; 25} lain jika (st.sval.compareTo ("clear") == 0) {26 pemboleh ubah = Hashtable baru (); 27 bersambung; 28} lain jika (st.sval.compareTo ("quit") == 0) {29 System.exit (0); 30} yang lain jika (st.sval.compareTo ("exit") == 0) {31 System.exit (0); 32} yang lain jika (st.sval.compareTo ("help") == 0) {33 help (); 34 teruskan; 35} 36 varName = st.sval; 37 c = st.nextToken ();38} 39 rehat; 40} 41 if (c! = '=') {42 lemparkan SyntaxError baru ("hilang awal '=' tanda."); 43}

Seperti yang anda lihat dalam talian 16, token pertama dipanggil dengan memohon nextTokenpada StreamTokenizerobjek. Ini mengembalikan nilai yang menunjukkan jenis token yang diimbas. Nilai pulangan sama ada akan menjadi salah satu pemalar yang ditentukan dalam StreamTokenizerkelas atau ia akan menjadi nilai watak. Token "meta" (yang bukan sekadar nilai watak) ditakrifkan seperti berikut:

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

  • TT_EOL - Ini memberitahu anda bahawa objek tersebut baru saja melewati urutan akhir.

  • TT_NUMBER - Jenis token ini memberitahu kod penghurai anda bahawa nombor telah dilihat pada input.

  • TT_WORD - Jenis token ini menunjukkan keseluruhan "perkataan" telah diimbas.

Apabila hasilnya bukan salah satu pemalar di atas, ia adalah nilai watak yang mewakili watak dalam julat watak "biasa" yang diimbas atau salah satu watak petikan yang telah anda tetapkan. (Dalam kasus saya, tidak ada karakter kutipan yang diatur.) Ketika hasilnya adalah salah satu karakter petikan anda, rentetan yang dikutip dapat ditemukan dalam variabel contoh rentetan svaldari StreamTokenizerobjek.

Kod dalam baris 17 hingga 20 berkaitan dengan petunjuk akhir dan akhir fail, sedangkan pada baris 21 klausa if diambil jika tanda kata dikembalikan. Dalam contoh mudah ini, perkataan itu adalah perintah atau nama pemboleh ubah. Garis 22 hingga 35 menangani empat perintah yang mungkin. Sekiranya garis 36 dicapai, maka mestilah nama berubah-ubah; akibatnya, program menyimpan salinan nama pemboleh ubah dan mendapat token seterusnya, yang mesti menjadi tanda sama.

Sekiranya di baris 41 token itu bukan tanda yang sama, penghurai ringkas kami mengesan keadaan ralat dan membuang pengecualian untuk memberi isyarat. Saya membuat dua pengecualian generik, SyntaxErrordan ExecError, untuk membezakan ralat masa parsi dari ralat masa jalan. The mainkaedah terus dengan garis 44 di bawah.

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

Pada baris 44 ungkapan di sebelah kanan tanda sama diuraikan dengan penghurai ungkapan yang ditentukan di ParseExpressionkelas. Perhatikan bahawa garis 14 hingga 44 dibungkus dalam blok cubaan / tangkapan yang memerangkap kesilapan sintaks dan mengatasinya. Apabila ralat dikesan, tindakan pemulihan pengurai adalah menggunakan semua token hingga dan termasuk token akhir baris seterusnya. Ini ditunjukkan pada baris 49 dan 50 di atas.

Pada ketika ini, jika pengecualian tidak dilemparkan, aplikasi berjaya menguraikan pernyataan. Pemeriksaan terakhir adalah untuk melihat bahawa token seterusnya adalah akhir baris. Sekiranya tidak, ralat tidak dapat dikesan. Kesalahan yang paling biasa adalah kurungan yang tidak sesuai. Pemeriksaan ini ditunjukkan dalam baris 53 hingga 60 kod di bawah.

53 c = st.nextToken (); 54 if (c! = StreamTokenizer.TT_EOL) {55 if (c == ')') 56 System.out.println ("\ n Ralat sintaksis dikesan! - Kepada banyak penutupan penutup."); 57 yang lain 58 System.out.println ("\ nBogus token pada input -" + c); 59 sementara (c! = StreamTokenizer.TT_EOL) 60 c = st.nextToken (); 61} yang lain {

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 statik (StreamTokenizer st) melemparkan hasil Sintaksis Kesalahan {2 Ekspresi; 3 boolean selesai = salah; 4 5 hasil = jumlah (st); 6 sementara (! Selesai) {7 cuba {8 suis (st.nextToken ()) 9 case '&': 10 result = Ungkapan baru (OP_AND, hasil, jumlah (st)); 11 rehat; 12 kes '23} tangkapan (IOException mula) {24 lemparkan SyntaxError baru ("Mendapat Pengecualian I / O."); 25} 26} 27 hasil pulangan; 28}