Apa sumber yang bagus tentang cara menulis lexer di C ++ (buku, tutorial, dokumen), apa sajakah teknik dan praktik yang baik?
Saya telah melihat di internet dan semua orang mengatakan untuk menggunakan generator lexer seperti lex. Saya tidak ingin melakukan itu, saya ingin menulis lexer dengan tangan.
Jawaban:
Perlu diingat bahwa setiap mesin status terbatas berhubungan dengan ekspresi reguler, yang sesuai dengan program terstruktur yang digunakan
if
danwhile
pernyataan.Jadi, misalnya, untuk mengenali bilangan bulat, Anda dapat memiliki mesin status:
atau ekspresi reguler:
atau kode terstruktur:
Secara pribadi, saya selalu menulis lexers menggunakan yang terakhir, karena IMHO tidak kurang jelas, dan tidak ada yang lebih cepat.
sumber
*pc
, kan? Sepertiwhile(isdigit(*pc)) { value += pc; pc++; }
. Kemudian setelah}
Anda mengonversi nilainya menjadi angka dan menetapkannya sebagai token.n = n * 10 + (*pc++ - '0');
. Ia mendapat sedikit lebih kompleks untuk floating point dan notasi 'e', tetapi tidak buruk. Saya yakin saya bisa menyimpan sedikit kode dengan mengemas karakter ke buffer dan panggilanatof
atau apa pun. Itu tidak akan berjalan lebih cepat.Lexer adalah mesin negara yang terbatas. Oleh karena itu, mereka dapat dibangun oleh perpustakaan FSM tujuan umum. Namun, untuk keperluan pendidikan saya sendiri, saya menulis sendiri, menggunakan templat ekspresi. Inilah lexer saya:
Ini didukung oleh pustaka mesin negara berbasis iterator, pelacakan-kembali, hingga yang panjangnya ~ 400 baris. Namun, mudah untuk melihat bahwa yang harus saya lakukan adalah membangun operasi boolean sederhana, seperti
and
,,or
dannot
, dan beberapa operator gaya regex seperti*
nol atau lebih,eps
berarti "cocokkan apa saja" danopt
berarti "cocokkan" apapun tetapi jangan mengkonsumsinya ". Perpustakaan sepenuhnya generik dan didasarkan pada iterator. Hal-hal MakeEquality adalah tes sederhana untuk kesetaraan antara*it
dan nilai yang diteruskan, dan MakeRange adalah<= >=
tes sederhana .Akhirnya, saya berencana untuk beralih dari mundur ke prediktif.
sumber
MakeEquality
cuplikan? Secara khusus objek dikembalikan oleh fungsi itu. Terlihat sangat menarik.Pertama-tama, ada beberapa hal berbeda yang terjadi di sini:
Secara umum, kami mengharapkan lexer untuk melakukan semua 3 langkah sekaligus, namun yang terakhir secara inheren lebih sulit dan ada beberapa masalah dengan otomatisasi (lebih lanjut tentang ini nanti).
Lexer paling menakjubkan yang saya tahu adalah Boost.Spirit.Qi . Ini menggunakan templat ekspresi untuk menghasilkan ekspresi lexer Anda, dan setelah terbiasa dengan sintaksnya, kode terasa sangat rapi. Ini mengkompilasi dengan sangat lambat (template berat), jadi yang terbaik adalah mengisolasi berbagai bagian dalam file khusus untuk menghindari kompilasi ulang ketika mereka belum disentuh.
Ada beberapa jebakan dalam kinerja, dan penulis kompilator Epoch menjelaskan bagaimana ia mendapat kecepatan 1000x dengan profiling intensif dan investigasi tentang bagaimana Qi bekerja dalam sebuah artikel .
Akhirnya, ada juga kode yang dihasilkan oleh alat eksternal (Yacc, Bison, ...).
Tetapi saya berjanji akan menulis tentang apa yang salah dengan mengotomatiskan verifikasi tata bahasa.
Jika Anda memeriksa Dentang, misalnya, Anda akan menyadari bahwa alih-alih menggunakan parser yang dihasilkan dan sesuatu seperti Boost.Spirit, sebagai gantinya mereka berangkat untuk memvalidasi tata bahasa secara manual menggunakan teknik Descent Parsing generik. Tentunya ini sepertinya terbelakang?
Bahkan, ada alasan yang sangat sederhana: pemulihan kesalahan .
Contoh khas, di C ++:
Perhatikan kesalahannya? Semi-colon hilang tepat setelah deklarasi
Foo
.Ini adalah kesalahan umum, dan Clang pulih dengan rapi dengan menyadari bahwa itu hanya hilang dan
void
bukan merupakan contohFoo
tetapi bagian dari deklarasi berikutnya. Ini menghindari kesulitan untuk mendiagnosis pesan kesalahan kriptik.Sebagian besar alat otomatis tidak memiliki (setidaknya jelas) cara untuk menentukan kemungkinan kesalahan tersebut dan cara memulihkannya. Seringkali pemulihan memerlukan sedikit analisis sintaksis sehingga jauh dari bukti.
Jadi, ada trade-off yang terlibat dalam menggunakan alat otomatis: Anda mendapatkan parser Anda dengan cepat, tetapi itu kurang ramah pengguna.
sumber
Karena Anda ingin mempelajari cara kerja lexer, saya kira Anda sebenarnya ingin tahu cara kerja lexer generator.
Generator lexer mengambil spesifikasi leksikal, yang merupakan daftar aturan (pasangan regular-ekspresi-token), dan menghasilkan lexer. Lexer yang dihasilkan ini kemudian dapat mengubah string input (karakter) menjadi string token sesuai dengan daftar aturan ini.
Metode yang paling umum digunakan terutama terdiri dari mengubah ekspresi reguler menjadi automata terbatas deterministik (DFA) melalui automata nondeterministic automata (NFA), ditambah beberapa detail.
Panduan terperinci untuk melakukan transformasi ini dapat ditemukan di sini . Perhatikan bahwa saya belum membacanya sendiri, tetapi terlihat cukup bagus. Juga, hampir semua buku tentang konstruksi kompiler akan menampilkan transformasi ini dalam beberapa bab pertama.
Jika Anda tertarik dengan slide kuliah tentang topik ini, tidak ada keraguan jumlah mereka yang tak ada habisnya dari kursus konstruksi kompiler. Dari universitas saya, Anda dapat menemukan slide seperti itu di sini dan di sini .
Ada beberapa hal lagi yang biasanya tidak digunakan dalam lexers atau diperlakukan dalam teks, tetapi tetap sangat berguna:
Pertama, menangani Unicode agak tidak trivial. Masalahnya adalah input ASCII hanya selebar 8 bit, yang berarti Anda dapat dengan mudah memiliki tabel transisi untuk setiap keadaan di DFA, karena mereka hanya memiliki 256 entri. Namun, Unicode, dengan lebar 16 bit (jika Anda menggunakan UTF-16), membutuhkan tabel 64k untuk setiap entri di DFA. Jika Anda memiliki tata bahasa yang rumit, ini mungkin mulai memakan banyak ruang. Mengisi tabel ini juga mulai memakan sedikit waktu.
Atau, Anda dapat membuat pohon interval. Pohon rentang dapat berisi tupel ('a', 'z'), ('A', 'Z') misalnya, yang jauh lebih efisien memori daripada memiliki tabel penuh. Jika Anda mempertahankan interval yang tidak tumpang tindih, Anda dapat menggunakan pohon biner seimbang untuk tujuan ini. Waktu berjalan linear dalam jumlah bit yang Anda butuhkan untuk setiap karakter, jadi O (16) dalam kasus Unicode. Namun, dalam kasus terbaik, biasanya akan sedikit lebih sedikit.
Satu masalah lagi adalah bahwa lexers seperti yang biasa dihasilkan sebenarnya memiliki kinerja kuadratik terburuk. Meskipun perilaku terburuk ini tidak umum terlihat, ini mungkin menggigit Anda. Jika Anda mengalami masalah dan ingin menyelesaikannya, makalah yang menjelaskan cara mencapai waktu linier dapat ditemukan di sini .
Anda mungkin ingin dapat menggambarkan ekspresi reguler dalam bentuk string, seperti yang biasanya muncul. Namun, menguraikan deskripsi ekspresi reguler ini ke dalam NFA (atau mungkin struktur menengah rekursif pertama) adalah sedikit masalah ayam-telur. Untuk menguraikan deskripsi ekspresi reguler, algoritma Shunting Yard sangat cocok. Wikipedia tampaknya memiliki halaman yang luas tentang algoritme .
sumber