Petunjuk dan cakupan
Rancang parser kecil untuk ekspresi aritmatika dan deklarasi variabel. Input mungkin berisi beberapa kesalahan sintaksis, namun parser harus melaporkan posisi, melanjutkan dengan pernyataan berikutnya, dan menyediakan AST parsial untuk IDE.
Ini menguji batasan antara lexing, parsing, pemulihan, dan struktur data. Bison merekomendasikan untuk membuang input hingga ke titik sinkronisasi lalu melanjutkan; IDE juga membutuhkan node kesalahan, rentang yang stabil, dan pemulihan di luar kesalahan pertama.
Apa yang dievaluasi oleh pewawancara
Kandidat harus mendefinisikan token dan tata bahasa sebelum memilih recursive descent atau LR, membedakan kesalahan leksikal dari kesalahan sintaksis, memilih titik sinkronisasi yang aman, menekan kesalahan berjenjang (cascading), mempertahankan AST parsial, serta menguji pembatas bersarang, pemisah yang hilang, dan string yang tidak ditutup.
Kerangka jawaban 30 detik
“Saya memisahkan lexer, parser, dan diagnostik. Parser melacak kursor token dan rentang sumber; setelah terjadi kesalahan, ia mencatat token yang diharapkan dan aktual, melompat ke titik koma, pembatas penutup, atau EOF, menyisipkan ErrorNode, dan melanjutkan. Pemulihan menekan duplikat hingga beberapa token berhasil diproses. Node AST mempertahankan rentang yang hilang sehingga pemanggil dapat memilih mode ketat (strict) atau toleran.”
Jawaban mendalam langkah demi langkah
Langkah 1: Tentukan token dan tata bahasa
Lexer menghasilkan jenis, teks, offset, serta posisi baris dan kolom untuk pengenal (identifier), angka, operator, pembatas, titik koma, dan karakter tidak valid. Tata bahasa menentukan presedensi dan asosiativitas sehingga pemulihan tidak tersebar di seluruh fungsi ekspresi.
Langkah 2: Pilih struktur parser
Recursive descent mudah dibaca untuk tata bahasa kecil; precedence climbing menangani ekspresi. Tata bahasa yang lebih besar dapat menggunakan generator dengan strategi kesalahan eksplisit. Bagaimanapun, parser memerlukan lookahead, pemulihan token terbatas, dan rentang sumber.
Langkah 3: Pisahkan kesalahan leksikal dan sintaksis
Karakter tidak valid atau string yang tidak ditutup adalah kesalahan leksikal: hasilkan token kesalahan dan lanjutkan pemindaian. Operand, pembatas, atau titik koma yang hilang adalah kesalahan sintaksis yang dilaporkan oleh parser dalam konteksnya. Jangan melabeli setiap masalah sebagai “Unexpected token”.
Langkah 4: Pilih titik sinkronisasi
Titik tingkat pernyataan adalah titik koma, kurung kurawal tutup, atau EOF. Di dalam ekspresi, sinkronkan pada koma, tanda kurung tutup, atau batas operator. Melewati token harus selalu memajukan kursor atau mencapai EOF, jika tidak, kesalahan yang sama akan berulang tanpa henti.
Langkah 5: Bangun AST parsial
Pertahankan rentang kesalahan pada node. Representasikan turunan (child) yang hilang dengan MissingNode dan rentang yang tidak dapat dipulihkan dengan ErrorNode yang berisi token asli. Pemformatan, penyorotan, dan pelengkapan otomatis harus menangani node-node ini alih-alih mengasumsikan pohon yang lengkap.
Langkah 6: Tekan diagnostik berjenjang
Sebuah pemulihan dapat memunculkan banyak kesalahan di permukaan. Lacak titik sinkronisasi terakhir dan jumlah token yang berhasil; tunggu beberapa pergeseran (shift) yang berhasil sebelum melaporkan diagnostik lain. Batasi kesalahan per file agar log dan UI tetap dapat digunakan.
Langkah 7: Dukung parsing inkremental
Saat teks editor berubah, lakukan parse ulang pada rentang token yang terpengaruh dan konteks tata bahasa di sekitarnya sambil menggunakan kembali sub-pohon yang tidak berubah. Jaga agar rentang node dan ID token tetap stabil; batalkan cache berdasarkan batas induk dan status parser, bukan berdasarkan offset karakter saja.
Langkah 8: Uji dan ukur
Uji input yang valid, satu kesalahan, banyak kesalahan, kesalahan bersarang, string panjang, dan ekspresi yang sangat besar. Pastikan (assert) posisi, jumlah, node kesalahan, dan terminasi. Ukur pemindaian linier, kedalaman rekursi, memori, dan biaya pemulihan kasus terburuk pada input yang panjang.
Pertukaran (Trade-offs) dan batasan
Gagal cepat (Fail fast) versus melanjutkan
Kompilator batch dapat melanjutkan setelah diagnostik untuk memberikan umpan balik yang lebih baik; validasi konfigurasi dapat langsung menolak setelah kesalahan pertama. Jadikan ini sebagai mode sambil berbagi lexer, token, dan diagnostik untuk menghindari perbedaan perilaku.
Banyak versus sedikit titik sinkronisasi
Lebih banyak titik membatasi cakupan kesalahan tetapi dapat melewati token yang dapat dipulihkan; lebih sedikit titik mempertahankan konteks tetapi meningkatkan kesalahan berjenjang. Tentukan titik berdasarkan pernyataan dan pembatas, lalu uji dengan korpus yang representatif.
Recursive descent versus generator
Recursive descent memudahkan diagnostik kustom; generator cocok untuk tata bahasa yang besar dan stabil. Pemulihan harus berupa antarmuka eksplisit daripada mengandalkan bawaan generator yang belum teruji.
Latihan kegagalan dan evolusi
Tanda kurung tutup hilang
Tambahkan pernyataan berikutnya dan verifikasi sinkronisasi pada titik koma atau EOF-nya, satu diagnostik pembatas yang hilang, dan pelestarian pernyataan berikutnya.
Karakter tidak valid dan string tidak ditutup
Verifikasi bahwa lexer menghasilkan token kesalahan dan mencapai akhir baris atau akhir string tanpa membuat parser macet pada satu karakter.
Badai kesalahan beruntun
Berikan input di mana setiap token tidak valid. Kursor harus maju, jumlah kesalahan harus dibatasi, dan CPU tidak boleh meningkat secara kuadratik.
Kesalahan umum dan tindak lanjut
Kesalahan 1: Mengembalikan null pada kesalahan pertama
Tanyakan bagaimana IDE melanjutkan penyorotan dan pelengkapan otomatis; kembalikan ErrorNode atau MissingNode dengan rentang sebagai gantinya.
Kesalahan 2: Tidak memajukan kursor selama pemulihan
Minta argumen terminasi yang mengesampingkan pengulangan pada token yang sama.
Kesalahan 3: Melaporkan setiap kesalahan di parser
Tanyakan apakah string yang tidak ditutup dan karakter tidak valid termasuk dalam diagnostik lexer atau parser.
Kesalahan 4: Mengabaikan penekanan kesalahan berjenjang
Tanyakan mengapa satu titik koma yang hilang tidak boleh mencetak sepuluh kesalahan yang berulang.
Kesalahan 5: Melakukan cache parse inkremental hanya berdasarkan offset
Tanyakan node induk dan status parser mana yang menjadi tidak valid setelah menyisipkan satu pembatas.
Tindak lanjut tambahan dan jawaban referensi
Mengapa mempertahankan node kesalahan?
Pemformatan, pelengkapan otomatis, dan penyorotan tetap memerlukan struktur dan rentang. Node kesalahan memungkinkan alat hilir menangani input yang tidak lengkap secara eksplisit alih-alih mengalami crash.
Bagaimana Anda menjamin pemulihan berakhir (terminates)?
Setiap pemulihan mengonsumsi token atau mencapai EOF, dengan batas maksimum kesalahan dan rekursi.
Bagaimana Anda memvalidasi kualitas diagnostik?
Gunakan korpus yang berisi beberapa kesalahan independen dan pastikan posisi, jumlah, AST lanjutan, dan waktu proses daripada hanya menguji kesalahan pertama.