Analisis Leksikal tanpa ekspresi reguler

9

Saya telah melihat beberapa lexer di berbagai bahasa tingkat yang lebih tinggi ( Python , PHP , Javascript antara lain) dan mereka semua tampaknya menggunakan ekspresi reguler dalam satu bentuk atau lainnya. Walaupun saya yakin regex mungkin adalah cara terbaik untuk melakukan ini, saya bertanya-tanya apakah ada cara untuk mencapai lexing dasar tanpa ekspresi reguler, mungkin semacam penguraian string langsung atau sesuatu.

Jadi ya, apakah mungkin untuk menerapkan semacam lexing dasar dalam bahasa tingkat yang lebih tinggi * tanpa menggunakan ekspresi reguler dalam bentuk apa pun?

* Bahasa tingkat tinggi menjadi hal-hal seperti Perl / PHP / Python / Javascript dll. Saya yakin ada cara untuk melakukannya di C

theory regular-expressions lexer Noda
sumber
2
Sepertinya "apakah ada buku tentang kalkulus yang tidak menggunakan semua huruf Yunani dan hal-hal berlekuk aneh?"
kevin cline
@kevincline Mengapa orang mendayung melintasi Atlantik ketika ada pesawat yang sangat bagus di langit?
Smudge
1
mendayung dan mengendarai memiliki efek samping yang berbeda.
kevin cline

Jawaban:

3

Pertama-tama, ada pustaka ekspresi reguler untuk C karena sebelum bahasa "tingkat yang lebih tinggi" ditemukan. Hanya mengatakan, program C tidak podunk seperti beberapa orang tampaknya berpikir.

Bagi kebanyakan tata bahasa, lexing adalah masalah mencari spasi putih dan beberapa karakter lain seperti () [] {}; untuk membagi kata, dan kemudian mencocokkan dengan daftar kata kunci untuk melihat apakah ada yang cocok.

Karl Bielefeldt
sumber
1
Maksud saya C tidak bisa melakukan regex, maksud saya C memiliki fitur yang lebih kuat untuk melakukan hal-hal semacam ini. Saya membayangkan lebih mudah untuk membangun lexer canggih dan berkinerja dalam bahasa C daripada bahasa tingkat yang lebih tinggi.
Smudge
1
@sam, kompleksitas dan kinerja lexer atau parser lebih merupakan fungsi dari kompleksitas bahasa yang diurai daripada bahasa yang digunakan parser, jadi tidak.
jk.
+1. Lexer sangat sederhana; Anda hanya perlu string, tipe data untuk token Anda, dan tabel kata kunci yang telah ditentukan. Bagian tersulit adalah berurusan dengan spasi putih dan komentar: P
Mason Wheeler
2

Anda mungkin tertarik pada "parser tanpa pemindai", yang tidak memiliki langkah tokenization terpisah. Salah satu penjelasan tentang manfaat parser tanpa pemindai diberikan pada awal makalah ini: Filter Disambiguasi untuk Parser LR Parser Generalized . (Ada juga kelemahannya.)

(PEG, yang telah disebutkan dalam jawaban lain, juga dapat digunakan untuk membuat parser tanpa pemindai.)

Ryan Culpepper
sumber
1

Tidak ada yang spesifik tentang ekspresi reguler. Mereka hanya singkatan yang memungkinkan Anda untuk menghasilkan kode lebih mudah, dan implementasi biasanya dikirimkan. Namun, pada dasarnya, lexer adalah FSM dan ekspresi reguler hanyalah salah satu cara untuk mencapai tujuan itu.

DeadMG
sumber
0

Tentu saja Anda dapat menggunakan parser lain, karena setiap bahasa reguler juga bebas konteks. Pertanyaannya benar-benar turun ke mengapa Anda ingin.

Sebenarnya tidak ada yang lebih sederhana daripada ekspresi reguler (bagaimana Anda bisa meningkatkan O (N)?) Dan mencoba menyederhanakan tidak akan membantu. Anda selalu dapat menggunakan backtracking sederhana seperti yang ditunjukkan Jetti, meskipun saya sarankan untuk menghindarinya jika memungkinkan.

Jika Anda akan menggunakan parser yang lebih canggih untuk lexing maka Anda mungkin tidak memerlukan fase lexing sama sekali. Faktanya, alasan mengapa kita memiliki fase lexing adalah bahwa lebih cepat untuk mengurai token lexed daripada untuk mengurai karakter, bersama dengan itu secara drastis menyederhanakan langkah penguraian kita. Jadi, dengan menggunakan parser yang lebih canggih Anda hanya kehilangan semua manfaat dari lexing di tempat pertama.

Pubby
sumber
Jadi bagaimana regex melakukannya? Bukankah masih harus pergi karakter demi karakter (untuk sebagian besar pola paling tidak digunakan dalam lexing)?
Jetti
@ Jetti Ya, tentu saja.
Pubby
Akan mudah untuk membaca setiap karakter dan mundur jika diperlukan untuk mengeluarkan token. Akan lebih banyak kode tetapi tidak lebih sulit.
Jetti
@ Jetti, saya gagal melihat bagaimana luputnya naif lebih baik.
Pubby
Saya tidak pernah mengatakan yang lebih baik. Tetapi OP bertanya apakah ada cara lain dan itu adalah cara lain yang bukan pengurai canggih.
Jetti
0

Masuk akal untuk melakukan analisis leksikal dengan ekspresi reguler, atau melewatkan pass ini sama sekali dan melakukan parsing tanpa lexer yang jauh lebih fleksibel dan kuat dengan PEG atau GLR.

Logika SK
sumber