Mencari definisi yang jelas tentang "tokenizer", "parser" dan "lexers" apa dan bagaimana mereka terkait satu sama lain dan digunakan?

151

Saya mencari definisi yang jelas tentang apa itu "tokenizer", "parser" dan "lexer" dan bagaimana mereka terkait satu sama lain (misalnya, apakah parser menggunakan tokenizer atau sebaliknya)? Saya perlu membuat program akan melalui c / h file sumber untuk mengekstrak deklarasi dan definisi data.

Saya telah mencari contoh dan dapat menemukan beberapa info, tetapi saya benar-benar berjuang untuk memahami konsep dasar seperti aturan tata bahasa, pohon parse dan pohon sintaksis abstrak dan bagaimana mereka saling berhubungan satu sama lain. Akhirnya konsep-konsep ini perlu disimpan dalam program yang sebenarnya, tetapi 1) seperti apa bentuknya, 2) apakah ada implementasi yang umum.

Saya telah melihat Wikipedia tentang topik dan program ini seperti Lex dan Yacc, tetapi karena belum pernah melalui kelas kompiler (EE mayor), saya merasa sulit untuk sepenuhnya memahami apa yang sedang terjadi.

parsing lexer tokenize tuan
sumber

Jawaban:

166

Tokenizer memecah aliran teks menjadi token, biasanya dengan mencari spasi putih (tab, spasi, baris baru).

Lexer pada dasarnya adalah tokenizer, tetapi biasanya menempel konteks tambahan ke token - token ini adalah angka, token itu adalah string literal, token lain ini adalah operator kesetaraan.

Parser mengambil aliran token dari lexer dan mengubahnya menjadi pohon sintaksis abstrak yang mewakili program (biasanya) yang diwakili oleh teks asli.

Terakhir saya periksa, buku terbaik tentang subjek ini adalah "Penyusun: Prinsip, Teknik, dan Peralatan" yang biasanya hanya dikenal sebagai "Buku Naga".

Roger Lipscombe
sumber
8
Tidak diragukan "The Dragon Book" adalah buku yang bagus, tetapi buku ini mengharuskan pembaca untuk memiliki landasan yang bagus dalam CS. Beberapa buku dengan daya tarik yang lebih praktis adalah "Penulis Kompiler dan Penerjemah" oleh Ronald Mak, "Implementasi Kompiler Modern", Andrew Appel; "Konstruksi Kompiler", Niklaus Wirth; "Kompilasi dengan C # dan Java" dan "Kompiler dan Generator Kompiler: Pengantar dengan C ++" oleh Pat Terry; dan, tentu saja, "Referensi ANTLR Definitif" oleh Terrence Parr.
Andre Artus
5
Hanya untuk memastikan, saya tidak mengetuk rekomendasi Anda. "The Dragon Book" adalah buku pertama saya tentang teknologi kompiler, tetapi sulit dibandingkan dengan, katakanlah, buku Wirth, yang merupakan buku yang dapat Anda grok dalam beberapa jam. Saat itu saya memiliki beberapa pilihan karena itu adalah satu-satunya buku yang bisa saya dapatkan (saat itu tahun 1991, sebelum Amazon dan WWW). Saya memiliki itu dan koleksi file teks yang diproduksi oleh Jack W. Crenshaw disebut "LET'S BUILD A COMPILER" (terima kasih Jack!). Ini masih buku untuk mendapatkan pemahaman yang lebih lengkap tentang prinsip-prinsip, tetapi kebanyakan programmer hanya perlu pengenalan pragmatis.
Andre Artus
10
Saya tidak akan setuju bahwa parser / menurut definisi / menghasilkan pohon sintaksis abstrak. Parser dapat menghasilkan segala macam output yang berbeda. Misalnya, adalah umum bahwa parser menghasilkan urutan panggilan ke beberapa antarmuka pembangun - lihat Pola Pembangun di buku Pola Empat Geng. Poin kuncinya adalah bahwa pengurai menganalisis urutan token untuk menentukan apakah urutan sesuai dengan beberapa tata bahasa (biasanya bebas konteks) dan dapat menghasilkan beberapa output berdasarkan pada struktur tata bahasa urutan itu.
Theodore Norvell
2
"Let's Build a Compiler" ada di sini: compilers.iecc.com/crenshaw . Saya menemukan tautan dari sini: prog21.dadgum.com/30.html
Roger Lipscombe
1
@Pithkos: jika itu adalah satu-satunya kendala, yang Anda katakan adalah fungsi mengambil input dalam satu domain (matematik) yang tidak disebutkan namanya dan menghasilkan dan output di domain lain yang tidak dikenal, misalnya, F (X) -> Y Cukup banyak artinya Anda hanya dapat menyebutnya "fungsi". Jika Anda bersikeras bahwa domain X adalah <StreamOfCharacter, Grammar> dan domain Y adalah Tree dengan properti yang mencerminkan bentuk tata bahasa, maka F (X, G) -> T akan menjadi sesuatu yang saya sebut pengurai. Seringkali kita menjilat F sehubungan dengan G karena G tidak sering berubah, jadi F [G] (X) -> T adalah apa yang biasa Anda lihat sebagai parser.
Ira Baxter
18

Contoh:

int x = 1;

Seorang lexer atau tokeniser akan membaginya menjadi token 'int', 'x', '=', '1', ';'.

Pengurai akan mengambil token tersebut dan menggunakannya untuk memahami dengan cara tertentu:

  • kami punya pernyataan
  • itu adalah definisi bilangan bulat
  • bilangan bulat disebut 'x'
  • 'x' harus diinisialisasi dengan nilai 1
Gra
sumber
9
Seorang lexer akan mencatat bahwa "int", "=", dan ";" adalah token tanpa makna lebih lanjut, bahwa "x" adalah nama pengenal atau sesuatu, nilai "x", dan "1" adalah bilangan bulat atau angka, nilai "1". Tokenizer tidak harus melakukan itu.
David Thornley
5

Saya akan mengatakan bahwa lexer dan tokenizer pada dasarnya adalah hal yang sama, dan bahwa mereka menghancurkan teks menjadi bagian-bagian komponennya ('token'). Pengurai kemudian menginterpretasikan token menggunakan tata bahasa.

Saya tidak akan terlalu terpaku pada penggunaan terminologis yang tepat - orang sering menggunakan 'parsing' untuk menggambarkan tindakan apa pun menafsirkan segumpal teks.

Will Dean
sumber
1
Dengan PEG parser perbedaan antara tokenizer dan parser bahkan lebih tidak jelas.
Andre Artus
0

( menambah jawaban yang diberikan )

  • Tokenizer juga akan menghapus komentar apa pun, dan hanya mengembalikan token ke Lexer.
  • Lexer juga akan menentukan cakupan untuk token tersebut (variabel / fungsi)
  • Parser kemudian akan membangun struktur kode / program
mcha
sumber
1
Halo @ downvoter, dapatkah Anda menjelaskan mengapa Anda benar-benar downvote?
Koray Tugay
1
Saya bukan downvoter, tapi saya pikir downvote mungkin karena jawaban Anda sepertinya tidak benar. Tokenizer dapat menghilangkan noise (biasanya spasi putih tapi mungkin juga komentar), tetapi seringkali tidak memberi makan lexer. Lexer berbasis DFA akan memberi tokenize dan mengidentifikasi token apa itu (misalnya angka, string, pengidentifikasi, tetapi juga spasi putih atau komentar), tetapi tidak dapat menentukan ruang lingkup ini karena ini akan memerlukan pohon sintaks yang kemudian dibangun oleh pengurai.
Lucero
1) Saya tidak mengerti perbedaan Anda antara "lexer" dan "tokenizer". Saya telah membangun parser untuk lebih dari 50 bahasa dan saya tidak pernah memiliki dua mekanisme terpisah yang memecah teks sumber menjadi atom, jadi bagi saya ini hanyalah sinonim. 2) Jika Anda mengkompilasi, menghapus komentar dan spasi putih masuk akal di lexer. Jika Anda sedang membangun alat transformasi sumber-ke-sumber, Anda tidak dapat kehilangan komentar karena mereka harus muncul kembali dalam teks yang diubah. Jadi SELALU menghapus komentar adalah salah; kita bisa berdebat tentang bagaimana kita mengelola pelestarian ruang putih. ...
Ira Baxter
1
... [Alat yang saya buat (lihat bio saya) menangkap keduanya dengan kesetiaan yang memadai untuk mereproduksi mereka dalam kode yang diubah; kita melangkah lebih jauh, dan menangkap format atom, termasuk hal-hal aneh seperti tanda kutip yang digunakan pada string karakter dan radix / memimpin angka nol pada angka, semuanya untuk menghindari pengguna menolak hasil transformasi. Jadi yang Anda lewatkan adalah tidak hanya para lexer tidak selalu menghapus informasi, tetapi sebenarnya mereka mungkin perlu menangkap informasi di atas dan di luar token mentah]. ....
Ira Baxter
... 3) Lexers hanya mendefinisikan "cakupan" dalam parser yang sangat canggung yang sulit menangani ambiguitas sintaksis. Parser C dan C ++ adalah contoh kanonik; lihat diskusi saya di stackoverflow.com/a/1004737/120163 ). Seseorang tidak harus melakukannya dengan cara (jelek). Jadi saya menemukan jawaban Anda salah arah.
Ira Baxter