Apakah parser GCC dan Clang benar-benar ditulis tangan?

Tampaknya GCC dan LLVM-Clang menggunakan pengurai keturunan rekursif tulisan tangan , dan bukan parsing bawah-atas yang dihasilkan mesin, berbasis Bison-Flex.

Bisakah seseorang di sini mengonfirmasi bahwa ini masalahnya? Dan jika demikian, mengapa kerangka kerja kompilator utama menggunakan parser tulisan tangan?

Pembaruan : blog menarik tentang topik ini di sini

Iya:

• GCC menggunakan parser yacc (bison) sekali waktu, tetapi diganti dengan parser turunan rekursif tulisan tangan di beberapa titik dalam seri 3.x: lihat http://gcc.gnu.org/wiki/New_C_Parser untuk tautan ke pengiriman tambalan yang relevan.

• Clang juga menggunakan pengurai keturunan rekursif yang ditulis tangan: lihat bagian "Pengurai terpadu tunggal untuk C, Sasaran C, C ++, dan Sasaran C ++" di dekat akhir http://clang.llvm.org/features.html .

Ada teorema rakyat yang mengatakan C sulit untuk diurai, dan C ++ pada dasarnya tidak mungkin.

Itu tidak benar.

Yang benar adalah bahwa C dan C ++ cukup sulit diurai menggunakan parser LALR (1) tanpa meretas mesin parsing dan kusut dalam data tabel simbol. GCC sebenarnya dulu mem-parse mereka, menggunakan YACC dan peretasan tambahan seperti ini, dan ya itu jelek. Sekarang GCC menggunakan parser tulisan tangan, tetapi masih dengan hackery tabel simbol. Orang-orang Clang tidak pernah mencoba menggunakan generator parser otomatis; AFAIK the Clang parser selalu merupakan turunan rekursif dengan kode tangan.

Yang benar, adalah bahwa C dan C ++ relatif mudah diurai dengan parser otomatis yang lebih kuat, misalnya, pengurai GLR , dan Anda tidak memerlukan peretasan apa pun. The Elsa C ++ parser adalah salah satu contoh dari ini. Kami C ++ Front End adalah lain (seperti semua "compiler" ujung depan kami, GLR adalah teknologi parsing cukup indah).

Bagian depan C ++ kami tidak secepat GCC, dan tentunya lebih lambat dari Elsa; kami telah mencurahkan sedikit energi untuk menyesuaikannya dengan hati-hati karena kami memiliki masalah lain yang lebih mendesak (bahkan telah digunakan pada jutaan baris kode C ++). Elsa mungkin lebih lambat dari GCC hanya karena lebih umum. Mengingat kecepatan prosesor saat ini, perbedaan ini mungkin tidak terlalu menjadi masalah dalam praktiknya.

Tetapi "penyusun sebenarnya" yang didistribusikan secara luas saat ini berakar pada penyusun 10 atau 20 tahun yang lalu atau lebih. Inefisiensi kemudian menjadi lebih penting, dan tidak ada yang pernah mendengar tentang pengurai GLR, jadi orang melakukan apa yang mereka tahu bagaimana melakukannya. Dentang pasti lebih baru, tetapi teorema rakyat mempertahankan "persuasif" mereka untuk waktu yang lama.

Anda tidak harus melakukannya dengan cara itu lagi. Anda dapat menggunakan GLR dan pengurai lainnya dengan sangat wajar sebagai ujung depan, dengan peningkatan dalam pemeliharaan kompiler.

Apa yang benar, adalah bahwa mendapatkan tata bahasa yang sesuai perilaku ramah lingkungan Anda compiler sulit. Meskipun hampir semua kompiler C ++ menerapkan (sebagian besar) standar asli, mereka juga cenderung memiliki banyak ekstensi sudut gelap, misalnya, spesifikasi DLL dalam kompiler MS, dll. Jika Anda memiliki mesin parsing yang kuat, Anda dapat menghabiskan waktu Anda mencoba untuk mendapatkannya tata bahasa akhir agar sesuai dengan kenyataan, daripada mencoba mengubah tata bahasa Anda agar sesuai dengan batasan generator parser Anda.

EDIT November 2012: Sejak menulis jawaban ini, kami telah meningkatkan front end C ++ kami untuk menangani C ++ 11 lengkap, termasuk dialek varian ANSI, GNU, dan MS. Meskipun ada banyak hal tambahan, kami tidak perlu mengubah mesin parsing kami; kami baru saja merevisi aturan tata bahasa. Kami memang harus mengubah analisis semantik; C ++ 11 secara semantik sangat rumit, dan pekerjaan ini membebani upaya untuk menjalankan parser.

EDIT Februari 2015: ... sekarang menangani C ++ 14 penuh. (Lihat mendapatkan AST yang dapat dibaca manusia dari kode c ++ untuk parse GLR dari sedikit kode sederhana, dan C ++ yang terkenal "parse paling menjengkelkan").

EDIT April 2017: Sekarang menangani (draf) C ++ 17.

Parser Clang adalah parser rekursif-keturunan yang ditulis tangan, seperti juga beberapa frontend C dan C ++ sumber terbuka dan komersial lainnya.

Clang menggunakan parser keturunan rekursif karena beberapa alasan:

• Kinerja : pengurai yang ditulis tangan memungkinkan kita untuk menulis pengurai cepat, mengoptimalkan jalur panas sesuai kebutuhan, dan kita selalu mengontrol kinerja itu. Memiliki fast parser memungkinkan Clang untuk digunakan dalam alat pengembangan lain di mana parser "asli" biasanya tidak digunakan, misalnya, penyorotan sintaks dan penyelesaian kode dalam IDE.
• Diagnostik dan pemulihan kesalahan : karena Anda memegang kendali penuh dengan parser keturunan rekursif yang ditulis tangan, mudah untuk menambahkan kasus khusus yang mendeteksi masalah umum dan memberikan diagnostik yang hebat dan pemulihan kesalahan (misalnya, lihat http: //clang.llvm .org / features.html # expressivediags ) Dengan parser yang dibuat secara otomatis, Anda terbatas pada kemampuan generator.
• Kesederhanaan : parser keturunan rekursif mudah ditulis, dipahami, dan di-debug. Anda tidak perlu menjadi ahli parsing atau mempelajari alat baru untuk memperluas / meningkatkan parser (yang sangat penting untuk proyek sumber terbuka), namun Anda masih bisa mendapatkan hasil yang bagus.

Secara keseluruhan, untuk kompiler C ++, itu tidak terlalu menjadi masalah: bagian penguraian C ++ tidak sepele, tetapi ini masih merupakan salah satu bagian yang lebih mudah, jadi ada baiknya untuk membuatnya tetap sederhana. Analisis semantik --- terutama pencarian nama, inisialisasi, resolusi overload, dan instansiasi template --- lebih rumit daripada penguraian. Jika Anda ingin bukti, periksa distribusi kode dan komit di komponen "Sema" Clang (untuk analisis semantik) vs. komponen "Parse" (untuk penguraian).

parser gcc adalah tulisan tangan. . Saya menduga hal yang sama untuk dentang. Ini mungkin karena beberapa alasan:

• Kinerja : sesuatu yang telah Anda optimalkan secara manual untuk tugas khusus Anda hampir selalu akan bekerja lebih baik daripada solusi umum. Abstraksi biasanya memiliki kinerja yang sukses
• Waktu : setidaknya dalam kasus GCC, GCC mendahului banyak alat pengembang gratis (keluar tahun 1987). Tidak ada versi gratis yacc, dll. Pada saat itu, yang menurut saya akan menjadi prioritas bagi orang-orang di FSF.

Ini mungkin bukan kasus sindrom "tidak ditemukan di sini", tetapi lebih seperti "tidak ada yang dioptimalkan secara khusus untuk apa yang kami butuhkan, jadi kami menulis sendiri".

Jawaban aneh di sana!

Tata bahasa C / C ++ tidak bebas konteks. Mereka peka konteks karena bilah Foo *; kemenduaan. Kita harus membuat daftar typedef untuk mengetahui apakah Foo adalah sebuah tipe atau bukan.

Ira Baxter: Saya tidak mengerti maksudnya dengan GLR Anda. Mengapa membangun pohon parse yang terdiri dari ambiguitas. Parsing berarti menyelesaikan ambiguitas, membangun pohon sintaks. Anda menyelesaikan ambiguitas ini dalam sekejap, jadi ini tidak kalah buruknya. Bagi saya itu jauh lebih jelek ...

Yacc adalah generator parser LR (1) (atau LALR (1)), tetapi dapat dengan mudah dimodifikasi agar peka konteks. Dan tidak ada yang jelek di dalamnya. Yacc / Bison telah dibuat untuk membantu penguraian bahasa C, jadi mungkin ini bukan alat paling jelek untuk menghasilkan pengurai C ...

Hingga GCC 3.x, parser C dibuat oleh yacc / bison, dengan tabel typedefs dibuat selama penguraian. Dengan membangun tabel typedefs "in parse", tata bahasa C menjadi bebas konteks lokal dan selanjutnya "LR lokal (1)".

Sekarang, di Gcc 4.x, ini adalah parser keturunan rekursif. Ini adalah parser yang sama persis seperti di Gcc 3.x, masih LR (1), dan memiliki aturan tata bahasa yang sama. Perbedaannya adalah parser yacc telah ditulis ulang secara manual, shift / reduce sekarang disembunyikan di tumpukan panggilan, dan tidak ada "state454: if (nextsym == '(') goto state398" seperti pada gcc 3.x yacc's parser, sehingga lebih mudah untuk menambal, menangani kesalahan dan mencetak pesan yang lebih bagus, dan untuk melakukan beberapa langkah kompilasi berikutnya selama parsing. Dengan harga yang jauh lebih sedikit dari kode "mudah dibaca" untuk noob gcc.

Mengapa mereka beralih dari yacc ke keturunan rekursif? Karena sangat penting untuk menghindari yacc untuk mengurai C ++, dan karena GCC ingin menjadi kompiler multi bahasa, yaitu berbagi kode maksimum antara bahasa yang berbeda yang dapat dikompilasinya. Inilah mengapa pengurai C ++ dan C ditulis dengan cara yang sama.

C ++ lebih sulit untuk diurai daripada C karena bukan LR "lokal" (1) sebagai C, bahkan bukan LR (k). Lihat func<4 > 2>yang merupakan fungsi template yang dipakai dengan 4> 2, yaitu func<4 > 2> harus dibaca sebagai func<1>. Ini jelas bukan LR (1). Sekarang pertimbangkan func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>,. Di sinilah penurunan rekursif dapat dengan mudah menyelesaikan ambiguitas, dengan harga beberapa pemanggilan fungsi lagi (parse_template_parameter adalah fungsi parser ambigu. Jika parse_template_parameter (17tokens) gagal, coba lagi parse_template_parameter (15tokens), parse_template_parameter (13tokens) ... berhasil).

Saya tidak tahu mengapa tidak mungkin menambahkan sub tata bahasa rekursif yacc / bison, mungkin ini akan menjadi langkah selanjutnya dalam pengembangan parser gcc / GNU?

Tampaknya GCC dan LLVM-Clang menggunakan parser keturunan rekursif tulisan tangan, dan bukan parsing bawah-atas yang dihasilkan mesin, berbasis Bison-Flex.

Bison khususnya, saya tidak berpikir dapat menangani tata bahasa tanpa mengurai beberapa hal secara ambigu dan melakukan operan kedua nanti.

Saya tahu Haskell's Happy memungkinkan parser monadik (yaitu bergantung pada status) yang dapat menyelesaikan masalah tertentu dengan sintaks C, tetapi saya tahu tidak ada generator parser C yang mengizinkan monad status yang disediakan pengguna.

Secara teori, pemulihan kesalahan akan menjadi poin yang mendukung parser tulisan tangan, tetapi pengalaman saya dengan GCC / Clang adalah bahwa pesan kesalahan tidak terlalu bagus.

Adapun kinerja - beberapa klaim tampaknya tidak berdasar. Menghasilkan mesin negara bagian besar menggunakan generator parser harus menghasilkan sesuatu yang O(n)dan saya ragu parsing adalah penghambat dalam banyak perkakas.