Proses penguraian struktur kalimat memiliki dua sub proses, yaitu proses analisa leksikal dan proses analisa sintaks. Proses analisa leksikal ini dilakukan oleh penganalisa leksikal yang dihasilkan oleh alat bantu Lex, sedangkan proses analisa sintaks dilakukan oleh alat bantu YACC.
Analisa Leksikal (Scanner) merupakan antarmuka antara kode program sumber dan analisa sintaktik (parser). Atau dalam pengertiannya adalah sebuah proses yang mendahului parsing sebuah rangkaian karakter. Scanner melakukan pemeriksaan karakter per karakter pada teksmasukan, memecah sumber program menjadi bagian-bagian disebut Token. Proses parsing akan lebih mudah dilakukan bila inputnya sudah berupa token.
Analisa Leksikal mengerjakan pengelompokkan urutan-urutan karakter ke dalam komponen pokok: identifier, delimeter, simbol-simbol operator, angka, keyword, noise word, blank, komentar, dan seterusnya menghasilkan suatu Token Leksikal yang akan digunakan pada
Analisa Sintaktik. Model dasar untuk membentuk suatu Analisa Leksikal adalah Finite-
State Automata.
Analisa leksikal terdiri dari dua tahap:
Tahap pertama adalah pemindaian (scanning); scanner biasanya dibuat berdasarkan prinsip Finite State Machine ("mesin dengan jumlah keadaan terbatas"). Pada tahap ini, scanner akan membaca input karakter-ke-karakter, mengubah keadaannya sendiri berdasarkan karakter yang tengah dibaca. Setiap kondisi final (input dianggap valid) akan dicatat, bersama dengan lokasi input. Pada akhirnya scanner akan menemui keadaan penolakan, yang tidak akan berubah dengan input karakter apapun. Deteksi rekursi semacam ini akan mengakhiri proses pemindaian dan memindahkan keadaan scanner ke keadaan final terakhir, dan karenanya menyimpan informasi jenis dan besar lexeme valid yang terpanjang di dalam input.
Namun lexeme tersebut belum punya nilai semantik apapun; pemberian nilai semantik pada setiap unit leksikal adalah tugas dari evaluator yang memeriksa semua karakter setiap lexeme dan memberinya nilai tertentu. Saat sebuah lexeme telah memiliki informasi mengenai tipe dan nilainya, ia dapat secara valid disebut sebagai token.
Analisis leksikal membuat pekerjaan membuat sebuah parser jadi lebih mudah; ketimbang 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 penganalisa leksikal sebagai sub-sistem yang paling intensif melakukan komputasi, terutama bila digunakan dalam sebuah kompilator.
Kompilator adalah sebuah program yang membaca suatu program yang ditulis dalam suatu bahasa sumber (source language) dan menterjemah-kannya ke dalam suatu bahasa sasaran (target language).
Dalam penguraian struktur kalimat, penganalisa leksikal menganalisa setiap kata dalam kalimat, kemudian menentukan jenis kelas katanya. Hasil dari penganalisa leksikal ini digunakan oleh penganalisa sintaks yang akan memeriksa urutan simbol-simbol kelas kata tersebut dalam kalimat. Analisa kata dalam kalimat ini dilakukan oleh penganalisa leksikal berdasarkan kecocokan kata dengan aturan-aturan leksikal berupa ekspresi regular yang sudah didefinisikan. Bentuk aturan-aturan leksikal ini sudah didefinisikan oleh Iskak Hendrawan pada penelitiannya.
Rancangan aturan-aturan sintaks menggunakan bentuk backus naur form (BNF) yang sangat cocok digunakan untuk algoritma pengurai yang memiliki sifat context free [Sage81]. String tata bahasa yang didefinisikan BNF adalah kelas-kelas string yang merefleksikan kategori dari string analysis [Sage81]. Oleh karena itu, string inti (center string), adjunct string, atau adjunct set hasil analisa linguistic string terhadap bahasa Indonesia didefinisikan dalam BNF. Linguistic string dalam bahasa Indonesia dapat berupa rangkaian satu atau lebih kata misalnya frasa nominal, kelas-kelas kata misalnya kata benda, nama unsur gramatikal misalnya subjek atau objek. Berikut ini contoh penulisan dengan menggunakan BNF.
Definisi di atas adalah aturan sintaks suatu kalimat dan elemen subjeknya. Penulisan aturan sintaks terdiri dari suatu konstituen yang ditulis dalam kurung siku (
Dua aspek penting pembuatan Analisa Leksikal adalah :
- Menentukan token-token bahasa.
- Mengenali token-token bahasa dari program sumber.
Token-token dihasilkan dengan cara memisahkan program sumber tersebut
dilewatkan ke parser. Analisa Leksikal harus mengirim token ke parser. Untuk mengirim
token, scanner harus mengisolasi barisan karakter pada teks sumber yang merupakan
token valid. Scanner juga menyingkirkan informasi seperti komentar, blank, batas-batas
baris dan lain-lain yang tidak penting (tidak mempunyai arti) bagi parsing dan Code
Generator.
Scanner juga harus dapat mengidentifikasi token secara lengkap dan membedakan keyword dan identifier. Untuk itu scanner memerlukan tabel simbol. Scanner memasukkan identifier ke tabel simbol, memasukkan konstanta literal dan numerik ke tabel symbol sendiri setelah konversi menjadi bentuk internal.
Analisa Leksikal merupakan komponen kompilasi independen yang berkomunikasi dengan parser lewat antarmuka yang terdefinisi bagus dan sederhana sehingga pemeliharaan analisa leksikal menjadi lebih mudah dimana perubahan-perubahan terhadap analisa leksikal tidak berdampak pada pengubahan kompilator secara keseluruhan. Agar dapat memperoleh fitur ini, maka antarmuka harus tidak berubah. Kebanyakan kode yang menyusun analisa leksikal adalah sama untuk seluruh kompilator, tidak peduli bahasa.
Pada analisa leksikal yang dituntun tabel (table-driven lexical analyzer), maka satu-satunya yang berubah adalah tabel itu sendiri. Kadang diperlukan interaksi analisa leksikal dan analisa sintaktik yang lebih kompleks. Sehingga analisa leksikal harus dapat menganggap string sebagai token bertipe, bukan identifier. Untuk itu perlu komunikasi tingkat lebih tinggi yang biasanya dilakukan suatu struktur data dipakai bersama seperti tabel simbol.
Analisa Sintaktik dapat memasukkan string ke tabel simbol, mengidentifikasi
sebagai Type atau typedef, sehingga analisa leksikal dapat memeriksa tabel simbol untuk menentukan apakah lexeme adalah tipe token atau identifier.
Tugas Analisa leksikal
Tugas – tugas analisa leksikal antara lain :
a. Melakukan pembacaan kode sumber dengan merunut karakter demi karakter.
b. Mengenali besaran leksik (identifier, keywords, dan konstanta).
c. Mentransformasi menjadi sebuah token dan menentukan jenis tokennya.
d. Mengirimkan token.
e. Membuang atau mengabaikan white-space dan komentar dalam program.
f. Menangani kesalahan.
g. Menangani tabel symbol
Tahap Pelaksanaan Analisa Leksikal
- Pada single one pass
Terjadi interaksi antara scanner dan parser. Scanner dipanggil saat parser memerlukan
token berikutnya. Pendekatan ini lebih baik karena bentuk internal program sumber
yang lengkap tidak perlu dibangun dan disimpan di memori sebelum parsing dimulai.
- Pada separate pass / multi pass
Scanner memproses secara terpisah, dilakukan sebelum parsing. Hasil scanner
disimpan dalam file. Dari file tersebut, parsing melakukan kegiatannya. Scanner
mengirim nilai-nilai integer yang mempresentasikan bentuk internal token, bukan nilainilai
string. Keunggulan cara ini adalah ukurannya kecil dan tetap. Parser sangat lebih efisien bekerja dengan nilai integer yang mempresentasikan simbol daripada string
nyata dengan panjang variabel.
Implementasi Analisa Leksikal
a. Pengenalan Token
- Scanner harus dapat mengenali token
- Terlebih dahulu dideskripsikan token-token yang harus dikenali
b. Pendeskripsian Token
- Menggunakan reguler grammar. Menspesifikasikan aturan-aturan pembangkit
token-token dengan kelemahan reguler grammar menspesifikasikan token berbentuk
pembangkit, sedang scanner perlu bentuk pengenalan.
- Menggunakan ekspresi grammar. Menspesifikasikan token-token dengan ekspresi
reguler.
- Model matematis yang dapat memodelkan pengenalan adalah finite-state acceptor
(FSA) atau finite automata.
c. Implementasi Analisa Leksikal sebagai Finite Automata
Pada pemodelan analisa leksikal sebagai pengenal yang menerapkan finite automata,
analisa leksikal tidak cuma hanya melakukan mengatakan YA atau TIDAK. Dengan
demikian selain pengenal, maka analisa leksikal juga melakukan aksi-aksi tambahan
yang diasosiasikan dengan string yangsedang diolah. Analisa leksikal dapat dibangun
dengan menumpangkan pada konsep pengenal yang berupa finite automata dengan
cara menspesifikasikan rutin-rutin (aksi-aksi) tertentu terhadap string yang sedang
dikenali.
d. Penanganan Kesalahan di Analisa Leksikal
Hanya sedikit kesalahan yang diidentifikasi di analisa leksikal secara mandiri karena
analisa leksikal benar-benar merupakan pandangan sangat lokal terhadap program
sumber. Bila ditemui situasi dimana analisa leksikal tidak mampu melanjutkan proses
karena tidak ada pola token yang cocok, maka terdapat beragam alternatif pemulihan,
yaitu:
- "Panic mode" dengan menghapus karakter-karakter berikutnya sampai analisa
leksikal menemukan token yang terdefinisi bagus
- Menyisipkan karakter yang hilang
- Mengganti karakter yang salah dengan karakter yang benar
- Mentransposisikan 2 karakter yang bersebelahan.
Salah satu cara untuk menemukan kesalahan-kesalahan di program adalah menghitung
jumlah transformasi kesalahan minimum yang diperlukan untuk mentransformasikan
program yang salah menjadi program yag secara sintaks benar.
Input Buffering
Perancangan analisa leksikal seharusnya dapat membuat buffering masukkan yang
membantu mempercepat proses pembacaan dari file serta mempunyai fleksibelitas yang
tinggi agar analisa leksikal tidak bergantung platform sehingga mempunyai portabilitas
yang tinggi.
Membangun Analisa Leksikal
Scanner diimplementasikan dengan Automata Hingga Deterministik (AHD). Pada
kuliah Teori Bahasa dan Automata (atau Pengantar Automata, Bahasa Formal, dan
Kompilasi) telah dipelajari siklus transformasi : GR ® ER ® AHN ® AHD ® GR.
