Mencari lex dan yacc untuk Java? Anda tidak tahu Jack

Sun telah merilis Jack, alat baru yang ditulis di Java yang secara otomatis menghasilkan parser dengan menyusun spesifikasi tata bahasa tingkat tinggi yang disimpan dalam file teks. Artikel ini akan berfungsi sebagai pengantar alat baru ini. Bagian pertama dari artikel ini mencakup pengantar singkat tentang pembuatan parser otomatis, dan pengalaman pertama saya dengannya. Kemudian artikel akan fokus pada Jack dan bagaimana Anda dapat menggunakannya untuk menghasilkan parser dan aplikasi yang dibangun dengan parser tersebut, berdasarkan tata bahasa tingkat tinggi Anda.

Pembuatan pengurai kompiler otomatis

Parser adalah salah satu komponen aplikasi komputer yang paling umum. Ini mengubah teks yang dapat dibaca oleh manusia menjadi struktur data yang dikenal sebagai pohon parse, yang dipahami oleh komputer. Saya ingat dengan jelas perkenalan saya dengan generasi pengurai otomatis: Di perguruan tinggi, saya telah menyelesaikan kelas tentang konstruksi kompiler. Dengan bantuan istri saya, saya telah menulis kompiler sederhana yang dapat mengubah program yang ditulis dalam bahasa yang dibuat untuk kelas menjadi program yang dapat dieksekusi. Saya ingat merasa sangat berhasil pada saat itu.

Dalam pekerjaan "nyata" pertama saya setelah lulus kuliah, saya mendapat tugas untuk membuat bahasa pemrosesan grafis baru untuk dikompilasi menjadi perintah untuk koprosesor grafis. Saya mulai dengan tata bahasa yang baru disusun dan bersiap untuk meluncurkan proyek multi-minggu dalam menyusun kompiler. Kemudian seorang teman menunjukkan kepada saya utilitas Unix lex dan yacc . Lex membangun penganalisis leksikal dari ekspresi reguler, dan yacc mengurangi spesifikasi tata bahasa menjadi kompilator berbasis tabel yang dapat menghasilkan kode ketika berhasil mengurai produksi dari tata bahasa tersebut. Saya menggunakan lex dan yacc, dan dalam waktu kurang dari seminggu compiler saya sudah aktif dan berjalan! Kemudian, proyek GNU dari Free Software Foundation menghasilkan versi lex dan yacc yang "ditingkatkan" - bernama flex dan bison - untuk digunakan pada platform yang tidak menjalankan turunan dari sistem operasi Unix.

Dunia pembuatan parser otomatis maju lagi ketika Terrence Parr, seorang mahasiswa di Purdue University, menciptakan Purdue Compiler Construction Tool Set atau PCCTS. Dua komponen PCCTS - DFA dan ANTLR - menyediakan fungsi yang sama seperti lex dan yacc ; namun tata bahasa yang diterima ANTLR adalah tata bahasa LL (k) sebagai lawan dari tata bahasa LALR yang digunakan oleh yacc . Lebih lanjut, kode yang dihasilkan PCCTS jauh lebih mudah dibaca daripada kode yang dihasilkan oleh yacc. Dengan menghasilkan kode yang lebih mudah dibaca, PCCTS memudahkan manusia membaca kode untuk memahami apa yang dilakukan berbagai bagian. Pemahaman ini dapat menjadi penting saat mencoba mendiagnosis kesalahan dalam spesifikasi tata bahasa. PCCTS dengan cepat mengembangkan pengikut yang merasa filenya lebih mudah digunakan daripada yacc.

Kekuatan generasi parser otomatis adalah memungkinkan pengguna untuk berkonsentrasi pada tata bahasa dan tidak khawatir tentang kebenaran implementasi. Ini bisa menjadi penghemat waktu yang luar biasa baik dalam proyek sederhana maupun kompleks.

Jack melangkah ke piring

Saya menilai alat berdasarkan umum dari masalah yang mereka pecahkan. Karena persyaratan untuk mengurai input teks muncul berulang kali, tingkat pembuatan parser otomatis cukup tinggi di kotak peralatan saya. Dikombinasikan dengan siklus pengembangan Java yang cepat, pembuatan parser otomatis menyediakan alat untuk desain kompiler yang sulit dikalahkan.

Jack (berima dengan yacc) adalah generator parser, dalam semangat PCCTS, yang telah dirilis Sun secara gratis ke komunitas pemrograman Java. Jack adalah alat yang sangat mudah untuk dideskripsikan: Sederhananya, Anda memberikannya seperangkat aturan gramatikal dan lexing gabungan dalam bentuk file .jack dan menjalankan alat tersebut, dan ini memberi Anda kembali kelas Java yang akan mengurai tata bahasa itu. Apa yang lebih mudah?

Mendapatkan Jack juga cukup mudah. Pertama, Anda mengunduh salinan dari beranda Jack. Ini datang kepada Anda dalam bentuk kelas Java yang membongkar sendiri yang disebut install. Untuk menginstal Jack Anda perlu memanggil ini installkelas, yang, pada Windows 95 mesin dilakukan dengan menggunakan perintah: C:>java install.

Perintah yang ditampilkan di atas mengasumsikan bahwa javaperintah ada di jalur perintah Anda dan bahwa jalur kelas telah disiapkan dengan benar. Jika perintah di atas tidak berhasil, atau jika Anda tidak yakin apakah Anda telah mengatur dengan benar atau tidak, buka jendela MS-DOS dengan menelusuri item menu Start-> Programs-> MS-DOS Prompt. Jika Anda menginstal Sun JDK, Anda dapat mengetikkan perintah ini:

C:> jalur C: \ java \ bin;% jalur% C:> setel CLASSPATH = .; c: \ java \ lib \ class.zip 

Jika Symantec Cafe versi 1.2 atau yang lebih baru diinstal, Anda dapat mengetikkan perintah ini:

C:> jalur C: \ cafe \ java \ bin;% jalur% 

Jalur kelas seharusnya sudah disiapkan dalam file bernama sc.ini di direktori bin Cafe.

Selanjutnya, ketikkan java installperintah dari atas. Program penginstalan akan menanyakan direktori mana yang ingin Anda instal, dan subdirektori Jack akan dibuat di bawahnya.

Menggunakan Jack

Jack seluruhnya ditulis dalam Java, jadi memiliki kelas Jack berarti alat ini langsung tersedia di setiap platform yang mendukung mesin virtual Java. Namun, ini juga berarti bahwa pada kotak Windows Anda harus menjalankan Jack dari baris perintah. Katakanlah Anda memilih nama direktori JavaTools saat Anda menginstal Jack di sistem Anda. Untuk menggunakan Jack, Anda perlu menambahkan kelas Jack ke jalur kelas Anda. Anda dapat melakukan ini di file autoexec.bat Anda atau di file .cshrc Anda jika Anda adalah pengguna Unix. Perintah kritis adalah seperti baris yang ditunjukkan di bawah ini:

C:> setel CLASSPATH = .; C: \ JavaTools \ Jack \ java; C: \ java \ lib \ class.zip 

Perhatikan bahwa pengguna Symantec Cafe dapat mengedit file sc.ini dan menyertakan kelas Jack di sana, atau mereka dapat mengatur CLASSPATHsecara eksplisit seperti yang ditunjukkan di atas.

Menetapkan variabel lingkungan seperti yang ditunjukkan di atas menempatkan kelas Jack di CLASSPATHantara "." (direktori saat ini) dan kelas sistem dasar untuk Java. Kelas utama untuk Jack adalah COM.sun.labs.jack.Main. Kapitalisasi itu penting! Tepat ada empat huruf kapital dalam perintah ('C', 'O', 'M', dan lainnya 'M'). Untuk menjalankan Jack secara manual, ketik perintah:

C:> java COM.sun.labs.jack.Main parser-input.jack

Jika Anda tidak memiliki file Jack di jalur kelas Anda, Anda dapat menggunakan perintah ini:

C:> java -classpath.; C: \ JavaTools \ Jack \ java; c: \ java \ lib \ class.zip COM.sun.labs.jack.Main parser-input.jack 

Seperti yang Anda lihat, ini agak lama. Untuk meminimalkan pengetikan, saya memasukkan permintaan tersebut ke dalam file .bat bernama Jack.bat . Di masa mendatang, program pembungkus C sederhana akan tersedia, bahkan saat Anda membaca ini. Lihat halaman beranda Jack untuk ketersediaan program ini dan program lainnya.

Ketika Jack dijalankan, itu membuat beberapa file di direktori saat ini yang nantinya akan Anda kompilasi ke dalam parser Anda. Sebagian besar diawali dengan nama parser Anda atau umum untuk semua parser. Namun, salah satunya ASCII_CharStream.javamungkin bertabrakan dengan parser lain, jadi mungkin ide yang bagus untuk memulai di direktori yang hanya berisi file .jack yang akan Anda gunakan untuk membuat parser.

Setelah Anda menjalankan Jack, jika pembuatannya berjalan lancar, Anda akan memiliki banyak .javafile di direktori saat ini dengan berbagai nama yang menarik. Ini adalah parser Anda. Saya mendorong Anda untuk membukanya dengan editor dan memeriksanya. Saat Anda siap, Anda dapat mengkompilasinya dengan perintah

C:> javac -d. ParserName.java

di mana ParserNamenama yang Anda berikan pada pengurai Anda di file input. Lebih lanjut tentang itu sebentar lagi. Jika semua file untuk parser Anda tidak dapat dikompilasi, Anda dapat menggunakan metode brute force untuk mengetik:

C:> javac * .java 

Ini akan mengkompilasi semua yang ada di direktori. Pada titik ini pengurai baru Anda siap digunakan.

Deskripsi pengurai Jack

Jack parser description files have the extension .jack and are divided into three basic parts: options and base class; lexical tokens; and non-terminals. Let's look at a simple parser description (this is included in the examples directory that comes with Jack).

options { LOOKAHEAD = 1; } PARSER_BEGIN(Simple1) public class Simple1 { public static void main(String args[]) throws ParseError { Simple1 parser = new Simple1(System.in); parser.Input(); } } PARSER_END(Simple1) 

The first few lines above describe options for the parser; in this case LOOKAHEAD is set to 1. There are other options, such as diagnostics, Java Unicode handling, and so on, that also can be set here. Following the options comes the base class of the parser. The two tags PARSER_BEGIN and PARSER_END bracket the class that becomes the base Java code for the resulting parser. Note that the class name used in the parser specification must be the same in the beginning, middle, and ending part of this section. In the example above, I've put the class name in bold face to make this clear. As you can see in the code above, this class defines a static main method so that the class can be invoked by the Java interpreter on the command line. The main method simply instantiates a new parser with an input stream (in this case System.in) and then invokes the Input method. The Input method is a non-terminal in our grammar, and it is defined in the form of an EBNF element. EBNF stands for Extended Backus-Naur Form. The Backus-Naur form is a method for specifying context-free grammars. The specification consists of a terminal on the left-hand side, a production symbol, which is typically "::=", and one or more productions on the right-hand side. The notation used is typically something like this:

 Keyword ::= "if" | "then" | "else" 

This would be read as, "The Keyword terminal is one of the string literals 'if', 'then', or 'else.'" In Jack, this form is extended to allow the left-hand part to be represented by a method, and the alternate expansions may be represented by regular expressions or other non-terminals. Continuing with our simple example, the file contains the following definitions:

void Input() : {} { MatchedBraces() "\n"  } void MatchedBraces() : {} { "{" [ MatchedBraces() ] "}" } 

This simple parser parses the grammar shown below:

Input ::= MatchedBraces "\n"
MatchedBraces ::= "{" [ MatchedBraces ] "}"

I've used italics to show the non-terminals on the right side of the productions and boldface to show literals. As you can see, the grammar simply parses matched sets of brace "{" and "}" characters. There are two productions in the Jack file to describe this grammar. The first terminal, Input, is defined by this definition to be three items in sequence: a MatchedBraces terminal, a newline character, and an end-of-file token. The token is defined by Jack so that you don't have to specify it for your platform.

When this grammar is generated, the left-hand sides of the productions are turned into methods inside the Simple1 class; when compiled, the Simple1 class reads characters from System.in and verifies that they contain a matching set of braces. This is accomplished by invoking the generated method Input, which is transformed by the generation process into a method that parses an Input non-terminal. If the parse fails, the method throws the exception ParseError, which the main routine can catch and then complain about if it so chooses.

Of course there's more. The block delineated by "{" and "}" after the terminal name -- which is empty in this example -- can contain arbitrary Java code that is inserted at the front of the generated method. Then, after each expansion, there is another optional block that can contain arbitrary Java code to be executed when the parser successfully matches that expansion.

A more complicated example

So how about an example that's a bit more complicated? Consider the following grammar, again broken down into pieces. This grammar is designed to interpret mathematical equations using the four basic operators -- addition, multiplication, subtraction, and division. The source can be found here:

options { LOOKAHEAD=1; } PARSER_BEGIN(Calc1) public class Calc1 { public static void main(String args[]) throws ParseError { Calc1 parser = new Calc1(System.in); while (true) { System.out.print("Enter Expression: "); System.out.flush(); try { switch (parser.one_line()) { case -1: System.exit(0); default: break; } } catch (ParseError x) { System.out.println("Exiting."); throw x; } } } } PARSER_END(Calc1) 

The first part is nearly the same as Simple1, except that the main routine now calls the terminal one_line repeatedly until it fails to parse. Next comes the following code:

IGNORE_IN_BNF : {}  " "  TOKEN : { } {  } TOKEN : /* OPERATORS */ { }    TOKEN : { }    

Definisi ini mencakup terminal dasar di mana tata bahasa ditentukan. Yang pertama, bernama IGNORE_IN_BNF , adalah token khusus. Setiap token yang dibaca oleh parser yang cocok dengan karakter yang ditentukan dalam token IGNORE_IN_BNF akan dibuang secara diam-diam. Seperti yang Anda lihat dalam contoh kami, ini menyebabkan parser mengabaikan karakter spasi, tab, dan karakter kembali carriage dalam input.