Apakah parsing dan lexing terpisah melewati praktik yang baik dengan combinator parser?

Ketika saya mulai menggunakan kombinator parser, reaksi pertama saya adalah rasa pembebasan dari apa yang terasa seperti perbedaan buatan antara parsing dan lexing. Tiba-tiba semuanya hanya parsing!

Namun, saya baru-baru ini menemukan posting ini di codereview.stackexchange menggambarkan seseorang mengembalikan perbedaan ini. Pada awalnya saya pikir ini sangat konyol bagi mereka, tetapi kemudian fakta bahwa fungsi ada di Parsec untuk mendukung perilaku ini membuat saya mempertanyakan diri saya sendiri.

Apa keuntungan / kerugian dari penguraian pada aliran yang sudah lexed di combinator parser?

Dalam penguraian, kami paling sering memahami analisis bahasa bebas konteks. Bahasa bebas konteks lebih kuat daripada bahasa biasa, karenanya parser dapat (paling sering) melakukan pekerjaan penganalisa leksikal dengan segera.

Tapi, ini a) cukup tidak wajar b) sering tidak efisien.

Untuk a), jika saya berpikir tentang bagaimana misalnya ifekspresi terlihat, saya pikir JIKA expr THEN expr ELSE expr dan bukan 'i' 'f', mungkin beberapa spasi, maka karakter apa pun yang dapat dimulai dengan ekspresi, dll. Anda mendapatkan ide.

Untuk b) ada alat yang kuat yang melakukan pekerjaan yang sangat baik untuk mengenali entitas leksikal, seperti pengidentifikasi, literal, kurung dari semua jenis, dll. Mereka akan melakukan pekerjaan mereka dalam waktu singkat dan memberi Anda antarmuka yang bagus: daftar token. Jangan khawatir tentang melewatkan spasi di parser lagi, parser Anda akan jauh lebih abstrak ketika berurusan dengan token dan bukan dengan karakter.

Lagi pula, jika Anda pikir seorang parser harus sibuk dengan hal-hal tingkat rendah, mengapa kemudian memproses karakter? Orang bisa menulisnya juga pada level bit! Anda lihat, parser seperti itu yang bekerja pada level bit akan hampir tidak bisa dipahami. Itu sama dengan karakter dan token.

Hanya 2 sen saya.

Semua orang menyarankan bahwa memisahkan lexing dan parsing adalah "praktik yang baik" - saya harus tidak setuju - dalam banyak kasus melakukan lexing dan parsing dalam sekali jalan memberikan lebih banyak kekuatan, dan implikasi kinerja tidak seburuk yang disajikan dalam jawaban lain (lihat Packrat ).

Pendekatan ini bersinar ketika seseorang harus mencampur sejumlah bahasa yang berbeda dalam aliran input tunggal. Ini tidak hanya dibutuhkan oleh bahasa berorientasi metaprogramming yang aneh seperti Katahdin dan sejenisnya , tetapi untuk aplikasi yang lebih umum juga, seperti pemrograman literasi (pencampuran lateks dan, katakanlah, C ++), menggunakan HTML dalam komentar, memasukkan Javascript ke dalam HTML, dan begitu seterusnya.

Alat analisis leksikal mengenali bahasa biasa dan parser mengenali bahasa bebas konteks. Karena setiap bahasa reguler juga bebas konteks (dapat didefinisikan oleh apa yang disebut tata bahasa linier-kanan ), pengurai juga dapat mengenali bahasa biasa dan perbedaan antara penganalisa parser dan leksikal tampaknya menambah beberapa kompleksitas yang tidak perlu: satu konteks tunggal tata bahasa gratis (parser) bisa melakukan pekerjaan parser dan penganalisa leksikal.

Di sisi lain, dapat berguna untuk menangkap beberapa elemen dari bahasa bebas konteks melalui bahasa reguler (dan karena itu penganalisa leksikal) karena

1. Seringkali elemen-elemen ini muncul begitu sering sehingga mereka dapat ditangani dengan cara standar: mengenali angka dan string literal, kata kunci, pengidentifikasi, melewatkan ruang putih, dan sebagainya.
2. Mendefinisikan bahasa token secara teratur membuat tata bahasa bebas konteks yang dihasilkan menjadi lebih mudah, misalnya seseorang dapat beralasan dalam hal pengidentifikasi, bukan dalam hal karakter individu, atau seseorang dapat mengabaikan ruang putih sepenuhnya jika itu tidak relevan untuk bahasa tertentu.

Jadi memisahkan parsing dari analisis leksikal memiliki keuntungan bahwa Anda dapat bekerja dengan tata bahasa bebas konteks yang lebih sederhana dan merangkum beberapa tugas dasar (sering rutin) dalam penganalisa leksikal (divide et impera).

EDIT

Saya tidak terbiasa dengan kombinator parser jadi saya tidak yakin bagaimana pertimbangan di atas berlaku dalam konteks itu. Kesan saya adalah bahwa bahkan jika dengan kombinator parser satu hanya memiliki satu tata bahasa bebas konteks, membedakan antara dua tingkat (analisis leksikal / parsing) dapat membantu membuat tata bahasa ini lebih modular. Seperti yang dikatakan, lapisan analisis leksikal yang lebih rendah dapat berisi parser dasar yang dapat digunakan kembali untuk pengidentifikasi, literal, dan sebagainya.

Sederhananya, lexing dan parsing harus dipisahkan karena kompleksnya berbeda. Lexing adalah DFA (deterministic finite automaton) dan parser adalah PDA (push-down automaton). Ini berarti bahwa parsing secara inheren mengkonsumsi lebih banyak sumber daya daripada lexing, dan ada teknik optimasi khusus yang tersedia untuk DFA saja. Selain itu, menulis mesin keadaan terbatas jauh lebih kompleks, dan lebih mudah untuk diotomatisasi.

Anda menjadi boros dengan menggunakan algoritma parsing ke lex.

Salah satu keuntungan utama parse / lex yang terpisah adalah representasi perantara - aliran token. Ini dapat diproses dengan berbagai cara yang tidak mungkin dilakukan dengan lex / parse gabungan.

Yang mengatakan, saya telah menemukan bahwa yang baik layak rekursif bisa lebih rumit dan lebih mudah untuk bekerja dengan belajar beberapa generator parser, dan harus mencari cara untuk mengekspresikan kelemahan grammer dalam aturan generator parser.