Get best of the week

Melengkapi SQL. Bagian 1. Kompleksitas penguraian. Cerita tentang menyelesaikan file ANTLR

Saya menerbitkan artikel asli tentang Habr, yang terjemahannya diposting di blog Codingsight .

Apa yang akan terjadi pada artikel ini?


Saya telah bekerja di perusahaan selama lebih dari lima tahun, yang telah mengembangkan jalur IDE untuk bekerja dengan basis data. Ketika mulai mengerjakan artikel ini, saya tidak dapat membayangkan berapa banyak cerita menarik yang dapat saya ingat, karena ketika saya selesai saya mendapatkan lebih dari 30 halaman teks. Setelah berpikir sebentar, saya mengelompokkan cerita berdasarkan topik, dan membagi artikel menjadi beberapa.

Saat saya menerbitkan, saya akan menambahkan tautan ke bagian-bagian berikut:

Bagian 1. Kompleksitas penguraian. Cerita tentang menyelesaikan ANTLR dengan file
Bagian 2. Optimalisasi bekerja dengan string dan membuka file
Bagian 3. Kehidupan ekstensi untuk Visual Studio. Bekerja dengan IO. Penggunaan SQL
Bagian 4. Penggunaan yang tidak biasa, dengan pengecualian, dampak data pada proses pengembangan. Menggunakan ML.NET

Banyak hal menarik terjadi selama pekerjaan: kami menemukan beberapa bug di .NET, mengoptimalkan beberapa fungsi berkali-kali, dan beberapa hanya dengan persen, melakukan sesuatu yang sangat keren pertama kali, dan sesuatu yang kami tidak berhasil bahkan setelah beberapa upaya. Tim saya sedang mengembangkan dan mendukung fitur bahasa IDE, yang utama adalah penyelesaian kode. Karenanya nama seri artikel. Di setiap bagian mereka, saya akan menceritakan beberapa kisah: beberapa tentang kesuksesan, beberapa tentang kegagalan.

Pada bagian ini, saya akan fokus pada masalah parsing SQL, perang melawan masalah ini dan kesalahan yang dibuat dalam pertarungan ini.



Bagi mereka yang tertarik hanya pada bagian ini dan hanya untuk navigasi yang mudah, isi artikel:

Kandungan




Siapa saya?


Saya datang ke pekerjaan ini sebagai bulan Juni dengan sedikit pengalaman. Saya, seperti banyak orang, datang ke pemrograman karena saya ingin membuat mainan. Beberapa bahkan cukup berhasil dilakukan. Saya bahkan menulis tentang pengembangan satu di sini. Baru-baru ini, omong-omong, ia membangkitkannya di server lain. Masih ada selusin game yang dibuat atau ditinggalkan di berbagai tahap kesiapan. Selain game, sebelum mendapatkan pekerjaan ini, saya berhasil menyelesaikan beberapa proyek freelance. Yang terbesar adalah aplikasi media sosial, yang merupakan portal sepakbola dengan tabel turnamen, data pemain dan kemampuan untuk memberi tahu pengguna tentang skor akhir atau gol yang dicetak melalui SMS. Ini dilakukan hampir 10 tahun yang lalu. Pada saat itu, tidak semua orang pergi dengan smartphone, dan yang dulu lebih sering pergi tanpa Internet atau dengan EDGE yang dikutuk untuk membuka situs teks tidak selalu memungkinkan. Jadi ide itu tampak baik bagi saya.

Entah bagaimana ternyata selain permainan, saya juga tertarik untuk membuat tuning yang berbeda untuk saya atau pengembang lainnya. Kadang-kadang, dia dekat dengan apa yang harus saya lakukan di tempat kerja sedikit kemudian. Sebagai contoh, salah satu proyek yang saya lakukan ketika mempelajari Win32 API adalah program yang menyoroti kode XML di Rich Edit Control. Selain itu, dimungkinkan untuk mengunggah kode backlit ke kode BMP, HTML atau BB yang fashionable di forum yang berbeda.

Proyek lain yang ternyata sangat dekat dengan apa yang saya lakukan di tempat kerja adalah program yang menganalisis kode C / C ++ dan membangun diagram blok darinya. Diagram alir sangat sesuai dengan persyaratan satu guru di universitas. Itu dibuat dengan kikuk, di dahi, dengan nol pengetahuan tentang teori analisis sintaksis, dan bekerja secara eksklusif pada karakter jelek saya. Beberapa tahun kemudian, ketika membersihkan komputer sampah tua, saya menemukan dan tidak bisa menghapusnya, jadi saya mempostingnya di github demi sejarah.

Eksperimen ini, ditambah dengan freelance, memberikan pengalaman yang cukup bagus dan memungkinkan untuk mendapatkan pekerjaan. Seiring waktu, setelah beberapa lusin direndam dalam ulasan darah dan air mata saya bahkan mulai memberi manfaat bagi perusahaan dan produk. Berbalik, agak lucu untuk memahami bahwa sebagai hasil dari beberapa kecelakaan, saya mulai melakukan apa yang saya sukai.

Apa kesulitannya?


Blok ini diperlukan untuk membenamkan pembaca dalam konteks apa yang sebenarnya kita lakukan.



Pengembangan desktop


Mungkin ini bahkan bukan kompleksitas, karena sudah menjadi bidang yang sangat matang di mana tidak banyak yang tidak diketahui, perpustakaan stabil, praktik terbaik diketahui. Fitur dari proyek kami ada di sini, karena saya, seperti banyak programmer lain, rentan terhadap hal-hal baru, dan hal-hal baru sekarang semuanya hilang di web. Ada hari-hari ketika, di tengah hujan, saya naik ke ambang jendela, ditutupi dengan selimut, dengan cangkir cokelat, dan memikirkan sistem redis, reaksi, beban tinggi, dan distribusi yang sedang dikembangkan di suatu tempat tanpa saya saat ini. Sisi lain dari masalah ini adalah tidak mudah untuk menggambarkan kompleksitas proyek kepada pengembang yang akrab dengan bir, dan ketika Anda bekerja pada aplikasi yang beroperasi sesuai dengan undang-undang yang berbeda secara mendasar, itu menjadi semakin sulit.


Parsing SQL dan Dialek


Saya juga telah menulis parser kecil untuk berbagai bahasa sebelum karya ini. Untuk beberapa waktu saya mengajar kursus .NET. Untuk beberapa kelompok, sebagai tugas tambahan, sebagai bagian dari topik "string", mereka menyarankan untuk menulis parser JSON sederhana mereka sendiri. Hanya SQL dan variannya yang jauh dari XML atau JSON yang dirancang agar dapat dipahami oleh parser dan orang. Selain itu, SQL secara sintaksis lebih kompleks daripada C / C ++, dengan banyak fungsinya terakumulasi dalam sejarah yang panjang. SQL terstruktur secara berbeda, mereka mencoba membuatnya terlihat seperti bahasa alami, cukup berhasil. Bahasa ini memiliki beberapa ribu kata kunci (tergantung pada dialek). Seringkali, untuk membedakan satu ekspresi dari yang lain, Anda perlu mengintip dua atau lebih kata (token) ke depan. Pendekatan ini disebut lookahead. Ada klasifikasi parser menurutseberapa jauh mereka dapat mengintip ke depan: LA (1), LA (2), atau LA (*), yang berarti bahwa parser dapat melihat sejauh yang dapat dilakukan untuk menentukan cabang yang benar. Kadang-kadang akhir opsional satu klausa dalam satu pernyataan SQL bertepatan dengan awal klausa lain, yang juga opsional: situasi seperti itu membuat parser jauh lebih rumit. T-SQL menuangkan air ke dalam api, di mana titik koma adalah opsional, dan mungkin, tetapi tidak wajib akhir dari beberapa pernyataan SQL dapat bertentangan dengan permulaan yang lain.situasi seperti itu sangat menyulitkan parser. T-SQL menuangkan air ke dalam api, di mana titik koma adalah opsional, dan mungkin, tetapi tidak wajib akhir dari beberapa pernyataan SQL dapat bertentangan dengan permulaan yang lain.situasi seperti itu sangat menyulitkan parser. T-SQL menuangkan air ke dalam api, di mana titik koma adalah opsional, dan mungkin, tetapi tidak wajib akhir dari beberapa pernyataan SQL dapat bertentangan dengan permulaan yang lain.

Masih belum percaya? Ada mekanisme untuk menggambarkan bahasa formal melalui tata bahasa . Tata bahasa adalah kode dalam satu bahasa yang menggambarkan bahasa lain. Dari tata bahasa, Anda sering dapat menghasilkan parser menggunakan alat. Alat bantu tata bahasa dan bahasa yang paling terkenal adalah YACC dan ANTLR . Parser yang dihasilkan YACC digunakan langsung di mesin MySQL , MariaDB , PostgreSQL. Anda dapat mencoba mengambilnya langsung dari sumber terbuka dan mengembangkan penyelesaian kode dan fungsi lain berdasarkan analisis SQL berdasarkan pada mereka. Selain itu, implementasi seperti itu akan menerima pembaruan gratis dalam hal pengembangan, dan parser akan berperilaku dijamin identik dengan mesin database. Jadi mengapa kita menggunakan ANTLR? Secara kualitatif mendukung C # /. NET, ada alat yang bagus untuk bekerja dengannya, sintaksnya jauh lebih mudah untuk dibaca dan ditulis. Sintaks ANTLR ternyata sangat nyaman sehingga microsoft baru-baru ini menggunakannya dalam dokumentasi C # resmi .

Mari kita kembali ke bukti saya tentang kompleksitas SQL, dibandingkan dengan bahasa lain, dalam hal penguraian. Untuk melakukan ini, saya ingin membandingkan ukuran tata bahasa untuk berbagai bahasa yang tersedia untuk umum. Di dbForge kami menggunakan tata bahasa kami sendiri, mereka lebih lengkap daripada yang tersedia untuk umum, tetapi, sayangnya, sangat tersumbat dengan sisipan kode C # untuk mendukung fungsi yang berbeda, lebih lanjut tentang hal ini di bagian “Mengurai tanpa pohon” di bagian “Kesalahan”.

Berikut ini adalah ukuran tata bahasa untuk berbagai bahasa:

JS - 475 baris parser + 273 lexer = 748 baris
Java - 615 baris parser + 211 lexer = 826 baris
C # - 1159 baris parser + 433 lexer = 1592 baris
C ++ - 1933 baris

MySQL- 2515 baris parser + 1189 lexer = 3704 baris
T-SQL - 4035 baris parser + 896 lexer = 4931 baris
PL SQL - 6719 baris parser + 2366 lexer = 9085 baris

Pada akhir beberapa lexer ada penghitungan karakter Unicode yang tersedia dalam bahasa, ini tidak berguna dalam penilaian kompleksitas bahasa. Saya mengambil jumlah baris sebelum memulai transfer tersebut.

Mungkin ada pertanyaan mengenai kompleksitas penguraian bahasa berdasarkan jumlah baris dalam tata bahasanya. Pertanyaan juga dapat berupa kepenuhan tata bahasa terbuka dibandingkan dengan sintaksis bahasa yang sebenarnya. Meskipun demikian, saya masih menganggap berguna untuk memberikan angka-angka ini, karena spreadnya terlalu besar.

Ini tidak semua, karena kita tidak perlu hanya mem-parsing beberapa file ke dalam SQL. Kami sedang melakukan IDE, yang berarti kami harus mengerjakan skrip yang tidak lengkap atau tidak valid. Bahkan jika Anda menulis skrip tanpa kesalahan, mungkin Anda menulisnya secara tidak konsisten, kecil kemungkinan skrip tersebut valid selama proses pengembangannya. Sebagai contoh, saya pertama kali menulis "SELECT FROM", setelah itu saya akan senang melihat daftar tabel yang tersedia. Ketika saya memilih tabel, saya akan mengatur ulang carriage ke SELECT, tekan bilah spasi dan tunggu daftar kolom dari tabel khusus ini. Ini adalah contoh yang sangat sederhana, tetapi itu menunjukkan bahwa parser yang menyediakan Penyelesaian Kode dalam IDE tidak dapat crash dengan pengecualian menemukan skrip yang tidak valid. Kami harus menemukan banyak trik untuk memastikan bahwa tooltip berfungsi dengan benar dalam banyak skenario seperti itu,tetapi pengguna masih mengirim skenario yang berbeda untuk bekerja dengan skrip yang belum selesai, yang berarti kita harus membuat trik baru.

Predikat perang


Saat mem-parsing kode, kadang-kadang ada situasi ketika kata berikutnya tidak memperjelas dua alternatif yang harus dipilih. Terkadang cukup untuk mengintip sejumlah kata yang telah ditentukan sebelumnya dan Anda pasti dapat memilih alternatif. Mekanisme untuk menyelesaikan ketidaktepatan jenis ini disebut pencarian ANTLR. Metode parser dalam hal ini dikonstruksikan sebagai rantai ifs tertanam, yang masing-masing terlihat satu kata lebih jauh. Di bawah ini adalah contoh dari tata bahasa yang menghasilkan ketidakpastian semacam ini.

rule1:
    'a' rule2 | rule3
    ;

rule2:
    'b' 'c' 'd'
    ;

rule3:
    'b' 'c' 'e'
    ;

Di tengah rule1, setelah melewati token 'a', parser harus melihat 2 token di depan untuk memilih aturan mana yang harus diikuti. Sekali lagi, pemeriksaan ini akan dilakukan di dalam aturan. Tata bahasa ini dapat ditulis ulang sehingga lookahead ini tidak ada, sayangnya struktur sering mengalami optimasi seperti itu, dan peningkatan kinerja relatif tidak tinggi.

Ada mekanisme yang lebih kompleks untuk menyelesaikan ketidakpastian yang lebih kompleks. Salah satunya adalah mekanisme predikat sintaksis (synpred) di ANTLR3.

Dia datang untuk menyelamatkan dalam kasus-kasus ketika, misalnya, penyelesaian opsional dari satu klausa berpotongan dengan awal opsional berikut lainnya. Predikat, dalam hal ANTLR3, adalah metode yang dihasilkan, yang membuat bagian virtual melalui teks sesuai dengan salah satu alternatif dan, jika berhasil, mengembalikan true, penyelesaian predikat ini disebut berhasil. Virtual pass juga disebut backtracking pass. Jika predikat berhasil, maka pass nyata dibuat. Ini menjadi masalah ketika predikat lain dimulai di dalam satu predikat, maka satu bagian dapat dilalui seratus dan seribu kali.

Pertimbangkan contoh sederhana. Ada 3 poin ketidakpastian (A, B, C).

  1. Parser memasuki A, mengingat posisi dalam teks, memulai bagian virtual level 1.
  2. B, , 2- .
  3. C, , 3- .
  4. 3- , 2 .
  5. 2 , 1 B .
  6. , A, B .

Dengan demikian, semua pemeriksaan di dalam C akan dilakukan 4 kali, B - 3 kali, A - 2 kali. Tetapi bagaimana jika alternatif yang sesuai adalah yang kedua atau ketiga dalam daftar? Kemudian pada beberapa tahap salah satu predikat akan gagal, posisi dalam teks akan mundur dan predikat lain akan mulai dijalankan.

Berulang kali menganalisis penyebab pembekuan aplikasi, kami menemukan kasus ketika "ekor" sintaks dieksekusi beberapa ribu kali. Synpred sangat bermasalah dalam aturan rekursif. Sayangnya, berdasarkan sifatnya, SQL bersifat rekursif, yang setidaknya merupakan kemampuan untuk menggunakan subquery hampir di mana-mana. Terkadang dengan bantuan berbagai trik dan trik ternyata ternyata aturan sehingga predikatnya hilang.

Jelas, synpred memiliki efek negatif pada kinerja. Pada tahap tertentu, perlu untuk menempatkan populasi mereka di bawah kendali ketat. Satu-satunya masalah adalah bahwa ketika menulis kode tata bahasa, tampilan synpred mungkin tidak jelas. Selain itu, kadang-kadang perubahan dalam satu aturan menyebabkan munculnya predikat di aturan lain. Ini tidak dapat dikontrol secara manual. Untuk mengontrol jumlah predikat, kami menulis sebuah reguler sederhana, yang disebut oleh Tugas MsBuild khusus. Jika jumlah predikat berbeda dari jumlah yang ditentukan dalam file terpisah, maka Tugas memotong perakitan dan melaporkan kesalahan. Melihat kesalahan seperti itu, pengembang harus menulis ulang kode aturan beberapa kali, mencoba menyingkirkan predikat yang tidak perlu, mungkin melibatkan pengembang lain dalam masalah tersebut. Jika predikat tidak bisa dihindari,kemudian pengembang memperbarui jumlah predikat dalam file yang sesuai. Perubahan pada file ini menarik perhatian ekstra pada ulasan.

Dalam kasus yang jarang terjadi, kami bahkan menulis predikat kami sendiri di C # untuk menyiasati predikat yang dihasilkan ANTLR. Untungnya, mekanisme semacam itu juga ada.

Solusi sepeda keren




Warisan Tata Bahasa


Setelah pengumuman setiap perubahan dalam setiap DBMS yang kami dukung, pekerjaan kami untuk mendukungnya dimulai. Hampir selalu, titik awal untuk ini adalah untuk mendukung konstruksi sintaksis dalam tata bahasa. Untuk setiap dialek SQL, kami menulis tata bahasa kami sendiri, ini menghasilkan beberapa pengulangan kode, tetapi pada akhirnya lebih mudah daripada mencari kesamaan di antara mereka. Hanya beberapa tahun yang lalu, MySQL dan MariaDB sangat mirip, menulis tata bahasa terpisah tidak praktis. Karena beberapa konstruksi yang ada di MariaDB, tetapi tidak di MySQL, kami mendukung tata bahasa MySQL. Ini adalah momen yang tidak menyenangkan: untuk pengguna MySQL, kami dapat menyarankan konstruksi yang tidak valid. Dalam beberapa tahun terakhir, MariaDB dan MySQL telah menjadi sangat berbeda dalam hal sintaks dan banyak lagi. Itu menjadi jelassalah mendukung dua bahasa berbeda dalam tata bahasa yang sama.

Solusi yang mungkin bisa berupa salinan tata bahasa yang lengkap, setelah itu masing-masing didukung secara terpisah. Sebagai hasil dari diskusi yang panjang, kami membuat keputusan yang berani. Saya sangat senang bahwa kami tidak menyalin kode, setiap sel di dalam saya menolak keputusan ini. Diputuskan untuk menulis ANTLR preproses tata bahasa Anda sendiri, yang mengimplementasikan mekanisme pewarisan tata bahasa. Beberapa waktu yang lalu, saya menemukan tata bahasa ANTLR3 di repositori resmi tata bahasa ANTLR4. Saya pikir kalimat ini perlu dibaca beberapa kali untuk menyadari kedalaman kegilaan.

Membahas gagasan pewarisan, kami segera menyadari bahwa kami ingin memiliki mekanisme polimorfisme. Kemampuan dalam tata bahasa ahli waris tidak hanya untuk mendefinisikan kembali aturan, tetapi juga untuk memanggil basis. Selain itu, saya ingin mengontrol posisi panggilan aturan dasar: awal, tengah atau akhir. Kami memutuskan bahwa semua aturan dapat didefinisikan ulang, untuk ini Anda tidak perlu menentukan tambahan apa pun. Untuk mendefinisikan kembali aturan, cukup untuk mendeklarasikan aturan dengan nama yang sama dalam tata bahasa penggantinya. Setelah itu, aturan dari tata bahasa induk akan tersedia dengan nama yang berbeda.

ANTLR membuat alat yang menyenangkan untuk pengembangan dengan menyetel - ada ekstensi untuk VS, ada ANTLRWorks. Memperkenalkan mekanisme pewarisan, saya tidak ingin kehilangan kesempatan ini. Tetapi bagaimana kemudian untuk menunjukkan tata bahasa dasar? Anda dapat membuat semacam konvensi untuk penamaan file, tetapi ini sama sekali tidak jelas. Pilihan lain mungkin untuk menunjukkan informasi tambahan seperti itu dalam file terpisah, tetapi bahkan sekarang, mengetikkan baris ini, saya merasakan bau dari solusi ini. Outputnya adalah indikasi tata bahasa dasar dalam tata bahasa ahli waris dalam format komentar ANTLR. Semua alat hanya akan mengabaikan teks ini, dan kita dapat dengan mudah menarik kode yang menarik bagi kita.

Persyaratan telah terbentuk, sekarang saatnya untuk mengimplementasikannya. Kami menulis Tugas MsBuild, yang dibangun ke dalam sistem pembangunan umum sebagai tindakan pra-bangun. Tugas melakukan pekerjaan preprocessor tata bahasa ANTLR, menghasilkan tata bahasa yang dihasilkan dari basis dan diwarisi. Tata bahasa yang dihasilkan sudah diproses oleh ANTLR sendiri. Jika aturan dengan nama yang sama dengan orang tua ditemukan dalam tata bahasa penerus, aturan dasar diubah namanya: nama tata bahasa induk ditambahkan ke namanya setelah garis bawah. Dengan nama ini dia bisa dihubungi di ahli waris.

Mekanisme preprocessor itu sendiri tidak membutuhkan banyak waktu, tetapi bersama dengan generasi parser ternyata memperlambat setiap pemasangan kembali proyek dengan 10-20 detik. Pada titik tertentu, ini tidak lagi cocok untuk kita. Kami memutuskan untuk memikirkan bagaimana ini dapat dioptimalkan. Solusinya adalah menambahkan hash dari jumlah semua tata bahasa yang bergantung pada bentuk komentar pada header file parser CS. Sebelum melakukan sesuatu, preprocessor membandingkan hash ini dengan hash file pada disk, dan jika tidak berbeda, maka file parser dianggap relevan. Pada tahap pengembangan awal, kami harus menginjak penggaruk parser dan tata bahasa yang tidak valid yang dikumpulkan oleh versi lama dari preprosesor lebih dari sekali. Akibatnya, jumlah hash perakitan dengan preprocessor muncul di komentar header.

ANTLR pasca pemrosesan lainnya


Dalam banyak bahasa pemrograman, jika kata adalah kunci, maka kata itu tidak lagi dapat digunakan sebagai nama objek. Dalam SQL, tergantung pada dialek, dari 800 hingga 3000 kata kunci. Sebagian besar dari mereka terkait erat dengan bidang subjek, di samping itu, tidak semua diperkenalkan segera, sehingga larangan menggunakan mereka semua sebagai nama objek akan menemui kesibukan. SQL memperkenalkan konsep kata kunci yang dipesan dan tidak dicadangkan. Anda tidak dapat memberi nama objek dengan cara yang sama seperti kata kunci yang dipesan (PILIH, DARI dll) tanpa mengutipnya, karena itu bukan kata kunci yang dipesan (KONVERSI, KETERSEDIAAN, dll.) - Anda bisa. Perilaku ini mempersulit pengembangan parser. Pada saat analisis leksikal, konteksnya tidak diketahui, tetapi pengurai memerlukan angka yang berbeda untuk pengidentifikasi dan kata kunci. Untuk mengatasi masalah ini, kami menambahkan satu lagi postprocessing ke parser ANTLR.Postprocessing menggantikan semua pemeriksaan eksplisit dengan pengidentifikasi, dengan panggilan ke metode khusus. Metode ini mengimplementasikan pemeriksaan yang lebih rumit. Jika pengenal adalah input dan pengidentifikasi diharapkan lebih lanjut, maka semuanya baik-baik saja, tetapi jika kata kunci tanpa pagu adalah input, maka itu perlu diperiksa tambahan. Pemeriksaan tambahan adalah bahwa metode ini diperiksa dalam konteks saat ini dalam pencarian cabang, di mana kata kunci tanpa pagu harga ini dapat digunakan secara tepat sebagai kata kunci, dan jika tidak ada cabang seperti itu, maka dapat digunakan sebagai pengidentifikasi.tetapi jika kata kunci tanpa pagu masuk, maka perlu diperiksa tambahan. Pemeriksaan tambahan adalah bahwa metode ini diperiksa dalam konteks saat ini dalam mencari cabang, di mana kata kunci tanpa pagu harga ini dapat digunakan tepat sebagai kata kunci, dan jika tidak ada cabang seperti itu, maka dapat digunakan sebagai pengidentifikasi.tetapi jika kata kunci tanpa pagu masuk, maka perlu diperiksa tambahan. Pemeriksaan tambahan adalah bahwa metode ini diperiksa dalam konteks saat ini dalam mencari cabang, di mana kata kunci tanpa pagu harga ini dapat digunakan secara tepat sebagai kata kunci, dan jika tidak ada cabang seperti itu, maka dapat digunakan sebagai pengidentifikasi.

Sebenarnya, masalah ini hanya dapat diselesaikan dengan ANTLR, tetapi solusi seperti itu tidak akan optimal. Solusi klasik untuk masalah ini adalah membuat aturan yang mencantumkan semua kata kunci tanpa pagu harga dan token pengenal. Lebih lanjut, di mana pun diizinkan untuk menggunakan pengidentifikasi, itu tidak lagi menggunakan token pengidentifikasi, tetapi ini adalah aturan khusus. Solusi semacam itu tidak hanya membuat Anda ingat untuk menambahkan kata kunci ketika Anda memasukkannya, tidak hanya di mana itu digunakan, tetapi juga dalam aturan khusus ini, ia juga bekerja jauh lebih lambat.

Kesalahan



Parsing Tanpa Pohon




Hasil parser, sebagai aturan, adalah pohon sintaks. Pohon sintaksis ( abstrak atau konkret ) adalah struktur data yang mencerminkan teks program melalui prisma tata bahasa formal. Jika Anda ingin menerapkan editor kode dengan pelengkapan otomatis untuk bahasa yang baru-baru ini Anda buat, setelah mempelajari masalah ini, Anda cenderung menerapkan sekitar algoritma berikut:

  1. Parsing teks dalam editor. Dapatkan sintaksis pohon.
  2. Temukan simpul di bawah kereta. Cocokkan dengan tata bahasa. Cari tahu kata kunci dan jenis objek apa yang akan tersedia saat ini.

Dalam hal ini, tata bahasa direpresentasikan dengan mudah sebagai grafik atau mesin keadaan terbatas.

Sayangnya, pada awal pengembangan, ANTLR IDE ada di versi ketiga. Versi keempat telah ditulis ulang dari awal dan secara fundamental berbeda dari yang ketiga, dengan meneruskan kode, parser akan secara otomatis menghasilkan pohon parse tanpa satu baris tambahan. Pada versi ketiga, ada mekanisme di mana orang bisa memberi tahu ANTLR cara membangun pohon, tetapi tidak menyenangkan untuk menggunakannya. Selain itu, banyak contoh dan artikel tentang topik ini disarankan menggunakan mekanisme tindakan untuk mengeksekusi kode pada saat parser melewati aturan. Mekanisme ini sangat nyaman dan memungkinkan Anda dengan cepat mendapatkan hasil. Sayangnya, solusi ini menyebabkan masalah arsitektur utama dengan pengembangan produk dan peningkatan kompleksitas mendukung fungsi baru. Faktanya adalah bahwa dalam satu file, dalam file tata bahasa,tindakan mulai terakumulasi terkait dengan sejumlah besar fungsi yang berbeda, yang akan menyenangkan untuk menyebar ke majelis yang berbeda. Di masa depan, kami dapat mendistribusikan penangan tindakan sendiri untuk majelis yang berbeda, menerapkan versi yang agak rumit dari pola pemberi notifikasi pelanggan, tetapi panggilan itu sendiri, dengan transmisi informasi yang diperlukan, masih mengacaukan tata bahasa kami, menyulitkan dukungan fungsi baru dan memaksakan pembatasan yang serius dan tidak menyenangkan pada arsitektur.mempersulit dukungan fungsionalitas baru dan memaksakan pembatasan serius dan tidak menyenangkan pada arsitektur.mempersulit dukungan fungsionalitas baru dan memaksakan pembatasan serius dan tidak menyenangkan pada arsitektur.

Tapi semuanya tidak sejelas kelihatannya. Faktanya adalah bahwa ANTLR3 jauh lebih cepat daripada ANTLR4. Menurut pengukuran kami, perbedaannya sekitar 6 kali. Selain itu, pohon sintaksis untuk skrip besar dapat memakan banyak ruang RAM, dan selama kita harus bertahan di ruang alamat 32-bit dari studio Visual dan SqlServer Management studio ini bisa sangat penting.

Kesimpulan


Subtotal mungkin sebagai berikut:

  • ANTLR alat yang ampuh untuk membangun parser
  • Keuntungannya dibandingkan yang lain adalah alat, sintaksis yang mudah digunakan, sejumlah besar bahasa yang didukung
  • ANTLR4 ditulis ulang dari awal dan menyiratkan bekerja dengan parser yang berbeda dari versi ketiga
  • Selalu ada cara untuk mendapatkan sedikit lebih banyak dari perpustakaan ThirdParty daripada yang mereka berikan
  • SQL bahasa spesifik, membangun parser untuk itu bukanlah tugas yang mudah
  • Parsing kode untuk tugas yang berkaitan dengan membangun IDE memiliki kekhasan tersendiri: Anda perlu mempertimbangkan untuk mengerjakan skrip yang tidak terenkripsi atau tidak valid

Sampai jumpa di bagian selanjutnya!

More articles:


All Articles