Analisis leksikal

Analisis leksikal (bahasa Inggris: lexical analysis) adalah sebuah proses yang mendahului parsing. Ia menerima masukan serangkaian karakter (seperti dalam dokumen berbentuk teks biasa atau kode sumber) dan menghasilkan deretan simbol yang masing-masing dinamakan token; proses penguraian akan lebih mudah dilakukan bila inputnya sudah berupa token.

Analisis leksikal terdiri dari dua tahap. Tahap pertama adalah pemindaian. Pemindai biasanya dibuat berdasarkan prinsip: mesin dengan jumlah keadaan terbatas. Pada tahap ini, pemindai akan membaca masukan karakter-ke-karakter, mengubah keadaannya sendiri berdasarkan karakter yang sedang dibaca. Pencatatan akan dilakukan pada setiap kondisi akhir berupa masukan yang dianggap valid bersama dengan lokasi masukan. Pada akhirnya, pemindai akan menemui keadaan penolakan yang tidak akan berubah dengan masukan karakter apapun. Deteksi rekursi semacam ini akan mengakhiri proses pemindaian dan memindahkan keadaan pemindai ke keadaan akhir yang terakhir. Karena ini, informasi jenis dan besar leksem valid yang terpanjang di dalam masukan akan disimpan.

Leksem yang tersimpan belum memiliki nilai semantik apapun. Pemberian nilai semantik pada setiap unit leksikal adalah tugas dari pengevaluasi yang memeriksa semua karakter setiap leksem dan memberinya nilai tertentu. Saat sebuah leksem telah memiliki informasi mengenai tipe dan nilainya, ia dapat secara valid disebut sebagai token.

Analisis leksikal membuat pekerjaan parser jadi lebih mudah; daripada membangun nama setiap fungsi dan variabel dari karakter-karakter yang menyusunnya, dengan analisis leksikal, parser cukup hanya berurusan dengan sekumpulan token dan nilai sintaksis masing-masing. Terlepas dari efisiensi pemrograman yang dapat dicapai dengan penggunaannya, proses kerja analisis leksikal yang membaca lebih dari sekali setiap karakter dari input yang diberikan menjadikan penganalisis leksikal sebagai sub-sistem yang paling intensif melakukan komputasi, terutama bila digunakan dalam sebuah kompilator.