Bagaimana cara menyederhanakan DFA prediksi token?

Lexer DFA menghasilkan kesalahan "kode terlalu besar".

Saya mencoba mengurai Halaman Server Java menggunakan ANTLR 3.

Java memiliki batas 64k untuk kode byte dari satu metode, dan saya terus mengalami kesalahan "kode terlalu besar" saat mengkompilasi sumber Java yang dihasilkan oleh ANTLR.

Dalam beberapa kasus, saya dapat memperbaikinya dengan mengkompromikan lexer saya. Misalnya, JSP menggunakan token XML "Nama", yang dapat menyertakan berbagai macam karakter. Saya memutuskan untuk hanya menerima karakter ASCII di token "Nama" saya, yang secara drastis menyederhanakan beberapa pengujian di dan lexer mengizinkannya untuk dikompilasi.

Namun, saya sudah sampai pada titik di mana saya tidak dapat mengambil jalan pintas lagi, namun DFA masih terlalu rumit.

Apa yang harus saya lakukan?

Apakah ada kesalahan umum yang mengakibatkan DFA kompleks?

Apakah ada cara untuk menghambat pembuatan DFA, mungkin dengan mengandalkan predikat semantik atau pandangan ke depan untuk membantu prediksi?

Menulis lexer ini dengan tangan akan mudah, tapi sebelum saya menyerah pada ANTLR, saya ingin memastikan saya tidak melewatkan sesuatu yang sudah jelas.

Latar belakang

Lexer ANTLR 3 menggunakan DFA untuk memutuskan cara memberi token pada input. Di DFA yang dihasilkan, ada metode yang disebut specialStateTransition(). Metode ini berisi pernyataan switch dengan kasus untuk setiap negara bagian di DFA. Dalam setiap kasus, terdapat serangkaian if pernyataan, satu untuk setiap transisi dari keadaan. Kondisi setiap pernyataan if menguji karakter masukan untuk melihat apakah cocok dengan transisi.

Kondisi pengujian karakter ini bisa sangat kompleks. Mereka biasanya memiliki bentuk berikut:

int ch = … ; /* "ch" is the next character in the input stream. */
switch(s) { /* "s" is the current state. */
  …
  case 13 :
    if ((('a' <= ch) && (ch <= 'z')) || (('A' <= ch) && (ch <= 'Z')) || … )
      s = 24; /* If the character matches, move to the next state. */
    else if …

Perubahan kecil pada lexer saya dapat menghasilkan lusinan perbandingan untuk satu transisi, beberapa transisi untuk setiap negara bagian, dan sejumlah negara bagian. Saya pikir beberapa negara bagian yang sedang dipertimbangkan tidak mungkin dijangkau karena predikat semantik saya, tetapi sepertinya predikat semantik diabaikan oleh DFA. (Saya mungkin salah membaca karena mengira kodenya jelas bukan yang bisa saya tulis dengan tangan!)

Saya menemukan tata bahasa ANTLR 2 di alat Jsp2x, tetapi saya tidak puas dengan pohon parsingnya, dan saya ingin menyegarkan kembali keterampilan ANTLR saya, jadi saya pikir saya akan mencoba menulis sendiri. Saya menggunakan ANTLRWorks, dan saya mencoba membuat grafik untuk DFA, tetapi tampaknya ada bug di ANTLRWorks yang mencegahnya.

erickson 22.09.2011 sumber

comment

Lihat pertanyaan ini untuk contoh kode terlalu besar, sehingga perubahan tata bahasa akan menghapus specialStateTransition sepenuhnya. - Gunther 22.09.2011

comment

@Gunther, ah, ya, predikat di dalam tata bahasa itu yang menyebabkannya! Saya benar-benar lupa Q&A itu! Saya akan menjadikannya favorit. - Bart Kiers 23.09.2011

Jawaban (2)

arrow_upward
4
arrow_downward

Sayangnya, tata bahasa yang sangat besar (banyak token berbeda) memiliki masalah tersebut (tata bahasa SQL juga mengalami hal ini).

Kadang-kadang hal ini dapat diperbaiki dengan membuat aturan lexer tertentu fragments berlawanan dengan aturan lexer "penuh" yang menghasilkan token dan/atau mengatur ulang cara pencocokan karakter di dalam aturan, tetapi dengan melihat cara Anda sudah mencobanya sendiri, saya ragu disana dapat memperoleh banyak manfaat dalam kasus Anda. Namun, jika Anda ingin memposting tata bahasa lexer Anda di sini di SO, saya, atau orang lain, mungkin melihat sesuatu yang dapat diubah.

Secara umum, masalah ini diperbaiki dengan membagi tata bahasa lexer menjadi 2 atau lebih tata bahasa lexer terpisah dan kemudian mengimpor tata bahasa tersebut ke dalam satu tata bahasa "master". Dalam istilah ANTLR, ini disebut tata bahasa komposit. Lihat halaman Wiki ANTLR tentang mereka: http://www.antlr.org/wiki/display/ANTLR3/Composite+Grammars

Sunting

Seperti yang disebutkan oleh @Gunther dalam komentar di bawah OP, lihat Tanya Jawab: Mengapa kelas java antlr lexer saya kodenya terlalu besar? di mana perubahan kecil (penghapusan predikat tertentu) menyebabkan kesalahan "kode terlalu besar" ini hilang.

Bart Kiers 22.09.2011

arrow_upward
3
arrow_downward

Sebenarnya tidak selalu mudah untuk membuat tata bahasa gabungan. Dalam banyak kasus, AntTask ini membantu untuk memperbaiki masalah ini (ini harus dijalankan setiap kali setelah mengkompilasi ulang tata bahasa, tetapi proses ini tidak terlalu membosankan).

Sayangnya, skrip ajaib ini pun tidak membantu dalam beberapa kasus rumit. Kompiler dapat mulai mengeluh tentang blok transisi DFA (bidang String[] statis) yang terlalu besar.

Saya menemukan cara mudah untuk mengatasinya, dengan memindahkan (menggunakan fitur pemfaktoran ulang IDE) bidang tersebut ke kelas lain dengan nama yang dibuat secara sewenang-wenang. Itu selalu membantu ketika memindahkan satu atau lebih bidang dengan cara seperti itu.

Andremoniy 18.09.2012