Mengapa memisahkan lexing dan parsing?

15

Dimungkinkan untuk menguraikan dokumen menggunakan pass tunggal dari mesin negara. Apa manfaatnya memiliki dua lintasan, yaitu. memiliki lexer untuk mengonversi teks menjadi token, dan memiliki pengurai untuk menguji aturan produksi pada token itu? Mengapa tidak memiliki satu pass yang menerapkan aturan produksi langsung ke teks?

compilers parsers Brent
sumber
2
Terkait: programmers.stackexchange.com/questions/128888/...
Pengguna
2
Ini sudah dibahas di CS, stackexchange, dengan banyak komentar yang sangat teknis dalam jawaban untuk kekuatan ekspresif dari lexer + parser . Tetapi mungkin ada ruang di sana untuk jawaban lebih lanjut.
babou
Saya bertanya-tanya apakah paralelisme gaya-pipeline (walaupun tahapannya sangat tidak seimbang) mungkin menjadi keuntungan sampingan. Instruksi dan perilaku cache data mungkin juga menarik. Berapa banyak (jika sama sekali) seperti itu akan mengurangi waktu kompilasi akan tergantung pada perangkat keras tertentu.
Paul A. Clayton
Salah satu alasan yang cukup jelas (setidaknya bagi saya) adalah bahwa Anda kemudian dapat menggunakan alat pemindai secara terpisah. Dalam praktiknya, saya sering menggunakan flex untuk memindai input, tetapi jarang membutuhkan kekuatan penuh yacc.
jamesqf

Jawaban:

13

Anda tidak harus memisahkan mereka. Orang menggabungkannya menjadi parser tanpa pemindai .

Kerugian utama parser tanpa pemindai tampaknya adalah bahwa tata bahasa yang dihasilkan agak rumit - lebih rumit daripada kombinasi yang sesuai dari ekspresi reguler yang melakukan lexing dan tata bahasa bebas konteks yang melakukan parsing pada token-stream. Secara khusus, tata bahasa untuk parsing tanpa pemindai cenderung mengarah pada ambiguitas. Lebih mudah untuk menghapus ambiguitas bagi tata bahasa yang bekerja pada token-stream.

Manfaat pragmatis menggunakan fase lexing dimuka yang didedikasikan adalah bahwa Anda tidak memasangkan parser berikutnya dengan detail leksikal. Ini berguna selama pengembangan bahasa pemrograman awal, ketika detail leksikal dan sintaksis masih sering berubah.

Martin Berger
sumber
1
Memiliki satu lintasan alih-alih dua lintasan melibatkan sifat penutupan. Jika Anda menganggap bahwa lexers adalah transduser milik keluarga formalT, yang dapat dikombinasikan dengan parser milik keluarga formal P, Anda harus bertanya-tanya apakah menggubahnya tetap berada di keluarga yang sama P, atau membutuhkan keluarga formal yang lebih kompleks PT, sehingga membutuhkan algoritme yang berbeda, dan mungkin penyetelan sintaksis lebih sulit. Teknologi parsing sering bergantung pada keluarga khusus (seperti varian LR atau LL) yang mungkin tidak memiliki properti penutupan yang tepat.
babou
@ Babou Ya itu benar. Saya tidak tahu hasil formal dari bentuk regular-expression yang dibuat dengan LL (k) keluar dari LL (k), atau serupa. Selain itu, lexing biasanya tidak dilakukan dengan bahasa biasa, tetapi dengan sesuatu yang lebih kuat, yaitu bahasa biasa diperluas dengan prioritas yang paling cocok dengan kata kunci pertama. Saya tidak yakin kelas bahasa apa itu dan apa sifat penutupannya.
Martin Berger
2
Jika penglihatan Anda melibatkan pembacaan pengidentifikasi, komposisi akan memerlukan penglihatan yang tidak terikat, karena (pada prinsipnya) tidak ada batasan pada panjang pengidentifikasi.
babou
@ Babou, saya tidak yakin. Jika kata kunci terpanjang adalah 17 karakter, maka setiap string yang lebih panjang harus merupakan pengidentifikasi, atau secara leksikal tidak valid.
Martin Berger
Tetapi Anda pengidentifikasi, atau mungkin string, angka atau literal lainnya, adalah urutan lebih dari 17 simbol individu, yang mungkin berdiri di depan token yang sebenarnya Anda butuhkan. Itu adalah pandangan ke depan yang besar, tanpa batas. Anda mungkin berakhir dengan bahasa yang tidak menentukan.
babou