Bina bahasa anda sendiri dengan JavaCC

Adakah anda pernah tertanya-tanya bagaimana penyusun Java berfungsi? Adakah anda perlu menulis pengurai untuk dokumen markup yang tidak melanggan format standard seperti HTML atau XML? Atau adakah anda mahu menerapkan bahasa pengaturcaraan kecil anda sendiri hanya untuk mengatasi itu? JavaCCmembolehkan anda melakukan semua itu di Jawa. Oleh itu, sama ada anda hanya berminat untuk mempelajari lebih lanjut mengenai bagaimana penyusun dan jurubahasa berfungsi, atau anda mempunyai cita-cita konkrit untuk mencipta penerus bahasa pengaturcaraan Java, sila sertai saya dalam usaha untuk meneroka bulan ini JavaCC, yang diserlahkan oleh pembinaan karya kecil yang berguna kalkulator baris perintah.

Asas pembinaan penyusun

Bahasa pengaturcaraan sering dibahagikan, agak artifisial, menjadi bahasa yang disusun dan ditafsirkan, walaupun sempadannya menjadi kabur. Oleh itu, jangan risau. Konsep yang dibincangkan di sini berlaku sama dengan bahasa yang disusun dan juga yang ditafsirkan. Kami akan menggunakan penyusun kata di bawah ini, tetapi untuk skop artikel ini, ini merangkumi makna jurubahasa.

Penyusun harus melakukan tiga tugas utama ketika disajikan dengan teks program (kod sumber):

  1. Analisis leksikal
  2. Analisis sintaksis
  3. Penjanaan atau pelaksanaan kod

Sebilangan besar kerja penyusun berpusat di sekitar langkah 1 dan 2, yang melibatkan memahami kod sumber program dan memastikan kebenaran sintaksisnya. Kami memanggil proses penghuraian , yang menjadi tanggungjawab penghurai .

Analisis leksikal (lexing)

Analisis leksikal melihat sepintas lalu kod sumber program dan membaginya menjadi token yang betul . Token adalah bahagian penting dari kod sumber program. Contoh token merangkumi kata kunci, tanda baca, literal seperti nombor, dan rentetan. Nontokens merangkumi ruang putih, yang sering diabaikan tetapi digunakan untuk memisahkan token, dan komen.

Analisis sintaksis (penghuraian)

Semasa analisis sintaksis, penghurai mengambil makna dari kod sumber program dengan memastikan kebenaran sintaksis program dan dengan membina perwakilan dalaman program.

Teori bahasa komputer bercakap mengenai program, tatabahasa, dan bahasa. Dalam erti kata itu, program adalah urutan token. Literal adalah elemen asas bahasa komputer yang tidak dapat dikurangkan lagi. Tatabahasa menentukan peraturan untuk membina program yang betul secara sintaksis. Hanya program yang mengikut peraturan yang ditentukan dalam tatabahasa yang betul. Bahasa adalah sekumpulan semua program yang memenuhi semua peraturan tatabahasa anda.

Semasa analisis sintaksis, penyusun meneliti kod sumber program berkenaan dengan peraturan yang ditentukan dalam tatabahasa bahasa. Sekiranya peraturan tatabahasa dilanggar, penyusun akan memaparkan mesej ralat. Sepanjang perjalanan, semasa memeriksa program, penyusun membuat perwakilan dalaman program komputer yang mudah diproses.

Peraturan tatabahasa bahasa komputer dapat ditentukan dengan jelas dan keseluruhannya dengan notasi EBNF (Extended Backus-Naur-Form) (untuk lebih lanjut mengenai EBNF, lihat Sumber). EBNF menentukan tatabahasa dari segi peraturan pengeluaran. Peraturan pengeluaran menyatakan bahawa unsur tatabahasa - sama ada unsur literal atau tersusun - boleh terdiri daripada unsur tatabahasa yang lain. Literal, yang tidak dapat direduksi, adalah kata kunci atau pecahan teks program statik, seperti simbol tanda baca. Unsur-unsur yang disusun dihasilkan dengan menerapkan peraturan pengeluaran. Peraturan pengeluaran mempunyai format umum berikut:

GRAMMAR_ELEMENT: = senarai unsur tatabahasa | senarai ganti unsur tatabahasa

Sebagai contoh, mari kita lihat peraturan tatabahasa untuk bahasa kecil yang menerangkan ungkapan aritmetik asas:

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

Tiga peraturan pengeluaran menentukan unsur tatabahasa:

  • expr
  • number
  • digit

Bahasa yang ditentukan oleh tatabahasa itu membolehkan kita menentukan ungkapan aritmetik. An expradalah nombor atau salah satu daripada empat pengendali infiks yang digunakan untuk dua exprs, exprdalam kurungan, atau negatif expr. A numberialah nombor titik terapung dengan pecahan perpuluhan pilihan. Kami menentukan digituntuk menjadi salah satu digit perpuluhan yang biasa.

Penjanaan atau pelaksanaan kod

Setelah pengurai berjaya menguraikan program tanpa ralat, program tersebut dapat dibuat dalam perwakilan dalaman yang mudah diproses oleh penyusun. Sekarang agak mudah untuk menghasilkan kod mesin (atau Java bytecode dalam hal ini) dari perwakilan dalaman atau untuk melaksanakan perwakilan dalaman secara langsung. Sekiranya kita melakukan yang pertama, kita menyusun; dalam kes yang terakhir, kita bercakap mengenai penafsiran.

JavaCC

JavaCC, tersedia secara percuma, adalah penjana penghurai. Ini menyediakan peluasan bahasa Java untuk menentukan tata bahasa bahasa pengaturcaraan. JavaCCdikembangkan pada mulanya oleh Sun Microsystems, tetapi kini dikendalikan oleh MetaMata. Seperti alat pengaturcaraan yang layak, JavaCCsebenarnya digunakan untuk menentukan tatabahasa JavaCCformat input.

Lebih-lebih lagi, JavaCCmembolehkan kita mendefinisikan tatabahasa dengan cara yang serupa dengan EBNF, menjadikannya mudah untuk menerjemahkan tatabahasa EBNF ke dalam JavaCCformat. Selanjutnya, JavaCCadalah penghasil parser yang paling popular untuk Java, dengan sejumlah JavaCCtatabahasa yang telah ditentukan untuk digunakan sebagai titik permulaan.

Membangunkan kalkulator ringkas

Kami sekarang melihat semula bahasa aritmetik kecil kami untuk membina kalkulator baris perintah mudah di Java menggunakan JavaCC. Pertama, kita harus menterjemahkan tatabahasa EBNF ke dalam JavaCCformat dan menyimpannya dalam fail Arithmetic.jj:

pilihan {LOOKAHEAD = 2; } PARSER_BEGIN (Aritmetik) Aritmetik kelas awam {} PARSER_END (Aritmetik) SKIP: "\ t" TOKEN: double expr (): {} term () ("+" expr () double term (): {} "/" term ()) * double unary (): {} "-" element () double element (): {} "(" expr () ")"  

Kod di atas akan memberi anda idea tentang cara menentukan tatabahasa JavaCC. The optionsseksyen di atas menetapkan satu set pilihan untuk tatabahasa itu. Kami menentukan pandangan 2. ciri pilihan JavaCCdebugging kawalan tambahan dan banyak lagi. Pilihan-pilihan tersebut secara alternatif boleh ditentukan pada JavaCCbaris perintah.

The PARSER_BEGINfasal menyatakan bahawa definisi kelas penghurai berikut. JavaCCmenghasilkan satu kelas Java untuk setiap penghurai. Kami memanggil kelas penghurai Arithmetic. Buat masa ini, kami hanya memerlukan definisi kelas kosong; JavaCCakan menambah pengisytiharan berkaitan penghuraian untuknya kemudian. Kami mengakhiri definisi kelas dengan PARSER_ENDklausa.

The SKIPseksyen mengenal pasti watak-watak kami mahu skip. Dalam kes kami, itu adalah watak ruang kosong. Seterusnya, kami menentukan token bahasa kami di TOKENbahagian. Kami menentukan nombor dan digit sebagai token. Perhatikan bahawa JavaCCmembezakan antara definisi token dan definisi untuk peraturan pengeluaran lain, yang berbeza dengan EBNF. Bahagian SKIPdan TOKENbahagian menentukan analisis leksikal tatabahasa 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 pengembalian unsur tatabahasa yang asal untuk dikembalikan double. Kami melakukan pengiraan yang tepat di mana kami menghuraikannya dan lulus hasil pengiraan ke atas pohon panggilan. Kami juga telah mengubah definisi elemen tatabahasa untuk menyimpan hasilnya dalam pemboleh ubah tempatan. Contohnya, a=element()menguraikan elementdan menyimpan hasilnya dalam pemboleh ubah a. Itu membolehkan kita menggunakan hasil elemen yang dihuraikan dalam kod tindakan di sebelah kanan. Tindakan adalah blok kod Java yang dijalankan ketika peraturan tatabahasa yang berkaitan telah menemukan kecocokan dalam aliran input.

Harap perhatikan berapa sedikit kod Java yang kami tambahkan untuk menjadikan kalkulator berfungsi sepenuhnya. Lebih-lebih lagi, menambahkan fungsi tambahan, seperti fungsi terbina dalam atau bahkan pemboleh ubah adalah mudah.