Apakah bahasa modern masih menggunakan generator parser?

Saya sedang meneliti tentang suite kompiler gcc di wikipedia di sini , ketika ini muncul:

GCC mulai menggunakan parser LALR yang dibuat dengan Bison, tetapi secara bertahap beralih ke parser rekursif-keturunan yang ditulis tangan; untuk C ++ pada tahun 2004, dan untuk C dan Objective-C pada tahun 2006. Saat ini semua ujung depan menggunakan parser recursive-descent yang ditulis tangan.

Jadi dengan kalimat terakhir itu, (dan sebanyak yang saya percayai wikipedia) saya pasti dapat mengatakan bahwa "C (gcc), C ++ (g ++), Objective-C, Objective-C ++, Fortran (gfortran), Java (gcj), Ada (GNAT), Go (gccgo), Pascal (gpc), ... Merkuri, Modula-2, Modula-3, PL / I, D (gdc), dan VHDL (ghdl) "semuanya adalah ujung depan yang tidak ada lagi gunakan generator parser. Artinya, mereka semua menggunakan parser tulisan tangan.

Pertanyaan saya kemudian, apakah praktik ini ada di mana-mana? Secara khusus, saya mencari jawaban yang tepat untuk "apakah implementasi standar / resmi x memiliki parser tulisan tangan" untuk x dalam [Python, Swift, Ruby, Java, Scala, ML, Haskell]? (Sebenarnya, informasi tentang bahasa lain juga diterima di sini.) Saya yakin saya dapat menemukannya sendiri setelah banyak menggali. Tapi saya juga yakin ini mudah dijawab oleh masyarakat. Terima kasih!

java ruby haskell parsing swift-language eatonphil
sumber

Titik data: CPython memiliki parser generator (pgen) buatan rumah bir. Tidak tahu sisanya.

Poin data: Ghc (haskell) menggunakan generator parser LALR (senang), seperti halnya OCaml.

Twan van Laarhoven

Harus "Melakukan kompiler berkinerja tinggi modern ..." atau serupa, karena bahasa adalah spec bukan implementasi, sementara itu adalah kompiler yang baik atau tidak menggunakan parser yang dihasilkan mesin.

dmckee

@ dmckee, ya Anda benar. Namun, penamaan mulai panjang dan kurang tepat sasaran. Jangan ragu untuk mengeditnya jika Anda lebih kreatif daripada saya!

eatonphil

Mengenai ML: MLton menggunakan generator parser yang khusus untuk ML, saya 90% yakin bahwa SML / NJ juga melakukannya walaupun saya kurang terbiasa dengannya. Anda mungkin atau mungkin tidak ingin menganggap itu "tulisan tangan."

Patrick Collins

Jawaban:

AFAIK, GCC menggunakan parser yang ditulis tangan khususnya untuk meningkatkan diagnostik kesalahan sintaksis (yaitu memberikan pesan bermakna pada manusia tentang kesalahan sintaksis).

Teori parsing (dan generator parsing turun darinya) sebagian besar tentang mengenali dan parsing frase input yang benar . Tetapi kami berharap dari kompiler bahwa mereka memberikan pesan kesalahan yang bermakna (dan bahwa mereka dapat mengurai secara bermakna sisa input setelah kesalahan sintaksis), untuk beberapa input yang salah.

Juga, bahasa lawas lama -seperti C11 atau C ++ 11- (yang secara konsep sudah lama, bahkan jika revisi terakhir mereka baru berusia tiga tahun) sama sekali tidak bebas konteks. Berurusan dengan sensitivitas konteks dalam tata bahasa untuk generator parser (yaitu bison atau bahkan menhir ) sangat sulit.

Basile Starynkevitch
sumber

Setuju. Memulihkan dengan baik dari kesalahan parsing (ketika Anda tidak ingin berhenti parsing pada kesalahan pertama, a la Borland Pascal lama) dan membuat pesan kesalahan kualitas yang baik (termasuk petunjuk dan saran untuk resolusi, seperti yang diinginkan manusia) keduanya secara inheren konteks -Sensitif, tugas heuristik. Mereka bisa dilakukan di atas output generator parser, agak, tapi itu adalah slog.

Jonathan Eunice

Dealing with that context sensitiveness in grammars for parser generators is boringly difficult. Ini juga kurang lebih mungkin karena alat ini menghasilkan parser bebas konteks. Tempat yang benar untuk memeriksa apakah semua kendala peka konteks ada setelah Anda membuat parse tree jika Anda menggunakan alat seperti ini.

dtech

Generator Parser dan mesin parser cukup umum. Keuntungan dari generalitas adalah membangun parser yang akurat dengan cepat dan membuatnya berfungsi dengan mudah, dalam skema keseluruhan.

Mesin parser sendiri mengalami masalah kinerja karena sifatnya yang umum. Kode tulisan tangan apa pun akan selalu jauh lebih cepat daripada mesin parser yang digerakkan oleh tabel.

Area kedua di mana generator parser / mesin mengalami kesulitan adalah bahwa semua bahasa pemrograman nyata adalah konteks sensitif, seringkali dengan cara yang cukup halus. Bahasa LR bebas konteks, artinya ada banyak seluk-beluk tentang penentuan posisi dan lingkungan yang tidak mungkin disampaikan dengan benar dalam sintaksis. Grammers yang dikaitkan mencoba untuk mengatasi aturan bahasa dasar seperti "menyatakan sebelum digunakan", dll. Pengkabelan sensitivitas konteks ini menjadi kode tulisan tangan sangat mudah.

BobDalgleish
sumber

Kutipan untuk klaim kinerja? Menjadi tabel-driven dapat menjadi optimasi kinerja yang signifikan dan generator memiliki akses ke algoritma yang sangat efisien tetapi hampir tidak pernah diimplementasikan dengan tangan (justru karena mereka adalah kekacauan tabel dan angka ajaib yang tidak dapat ditembus).

Dan tentang area kedua: Banyak banyak bahasa pemrograman utama yang nyata tidak peka konteks dalam arti apa pun yang berlaku (Anda harus merujuk ke sekumpulan semua program yang valid setelah pengecekan jenis dan semacamnya, yang tidak pernah merupakan tulisan tangan atau tulisan tangan). parser yang dihasilkan mencoba mengurai). Benar bahwa parser tulisan tangan lebih fleksibel, dan ini berguna untuk beberapa bahasa, tetapi sebagian besar di bidang pemulihan kesalahan dan pelaporan, inkrementalitas, dll. - generator parser jarang dihindari karena kekuatan pengenalan (apakah Anda lebih suka ingin menulis tata bahasa seperti itu adalah cerita yang berbeda). -1

Jika Anda menggunakan informasi tabel simbol selama parsing, maka Anda mungkin menyebutnya sensitif konteks. Tata bahasa yang dikaitkan jelas bukan bebas konteks, walaupun saya pikir mereka tidak sepenuhnya peka konteks. Poin Anda lainnya tentang pemulihan kesalahan dan pelaporan diambil dengan baik.

BobDalgleish

C dan C ++ memerlukan informasi tabel simbol selama parsing (atau menerima pohon parse jauh lebih spesifik di mana tidak ada perbedaan yang dibuat antara, misalnya, pernyataan ekspresi dan deklarasi variabel). Tapi saya tidak memikirkan itu. Bahasa seperti Java, Lisps, JavaScript, Ruby, Python, Go, Rust, Scala, Swift, Haskell (dan mungkin beberapa lagi, mungkin C # dan ML juga?) Tidak memerlukan informasi seperti itu untuk membangun jenis AST yang Anda inginkan inginkan pula. Banyak dari mereka sebenarnya memiliki tata bahasa LL (1), atau bahkan tata bahasa LALR.

kutipan untuk semua bahasa nyata tolong bantu konteksnya?

psr