TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 16
4. ANALISIS LEKSIKAL Struktur Kompiler Analisis Leksikal – Apa itu? Masukan bagi sebuah compiler/interpreter adalah program sumber yang strukturnya berupa deretan dari karakter-karakter o or rather unstructured Pemrosesan individual karakter yang ketidakefisiennya sangat tinggi o Imagine recognizing ‘while’ as ‘w’ ‘h’ ‘i’ ‘l’ ‘e’ Oleh karenanya, hal pertama yang kita perhatikan adalah bentuk kode sumbernya A Lexical Analyzer (scanner) mengubah deretan karakter-karakter menjadi deretan tokentoken o i.e. a scanner “tokenizes” the input Sebuah token (lexeme or syntactic unit) adalah komponen dasar leksikal dari program Analisis Leksikal–Token Token adalah level entitas yang paling rendah dalam diagram sintaks Jenis-jenis token antara lain: o identifiers (e.g. variable & function names, etc.) o keywords (like while, if, function, etc.) o operators (like +, -, *, ++, +=, etc.) o literals (constant values like 27.3, “Hello”, etc.) o punctuation (like ‘;’, ‘:’, ‘,’, etc.) Consider a simple program and its tokens:
Fungsi Scanner o Melakukan pembacaan kode sumber dengan merunut karakter demi karakter o Mengenali besaran leksik o Mentransformasi menjadi sebuah token dan menentukan jenis tokennya o Mengirim token o Membuang blank dan komentar dalam program o Menangani kesalahan o Beberapa scanners memasukkan simbol ke dalam tabel simbol
TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 17 Membaca Program Sumber
TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 18 Scanning berdasarkan MSH (Mesin Stata Hingga = Finite State Automata (FSA)) Hampir sebagian besar teknik yang digunakan untuk membangun scanners menggunakan mesin stata hingga (MSHs) atau Finite State Automata (FSA) MSHs dapat dengan mudah digunakan untuk mengenali kontruksi bahasa (i.e. tokens) yang digambarkan dengan bahasa regular Membangun Scanner Bagaimana scanner berinteraksi dengan parser? – parser akan menjadi bagian selanjutnya dari kompilasi Perhatikan gambar berikut:
Aksi Scanner Karena scanner mengubah dari stata ke stata, maka harus dilakukan sesuatu dengan karakter-karakter tersebut untuk mengenali sesuai dengan pembentukan token yang akan dikembalikan pada tahap parser Dalam beberapa kasus, harus menambahkan character seperti terlihat pada pembentukan token dan memanfaatkannya (menjadikan karakter masukan berikutnya menjadi kelihatan) – E.g. when scanning characters in an identifier Dalam kasus lainnya harus menjaga character dan mengembalikan dalam token lengkap
Aksi kemungkinan lainnya adalah menghilangkan karakter agar lebih sederhana – E.g. karakter pada komentar
Besaran Leksik Besaran pembangun bahasa/leksik meliputi hal-hal sebagai berikut : 1. Identifier Identifier dapat berupa keywords atau nama. Keywords adalah kata kunci yang sudah didefinisikan oleh suatu bahasa seperti Begin, End, If, Else dalam Pascal. Nama dideklarasikan sendiri oleh pemakai seperti nama variabel. Contoh bila pada suatu program Pascal terdapat deklarasi: Var Nomor: Integer; Suhu: Real; Maka Nomor dan Suhu akan dikenali sebagai besaran leksik berupa nama variabel yang terdapat pada program tersebut. Sedangkan Var, Integer dan Real merupakan keyword
TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 19 pada program tersebut. Nama bisa berupa nama program, procedure, var, type, constant. Keyword pada Pascal, misalnya : and, array, begin, case, const, div, do, downto, else, not, of, or, procedure, program, record, repeat, for, function, goto. 2. Nilai Konstanta Nilai konstanta adalah suatu konstanta yang terdapat pada program. Bisa berupa konstanta integer, real, boolean, character, string dan sebagainya. Misalkan saja dalam Pascal pada suatu program terdapat statement. N := R + 5 * 10 kata := kata1 + ‘makan’ A := 0.333 selesai := True Maka 5, 10, ‘makan’, 0.333, True, termasuk besaran leksik berupa nilai konstan yang terdapat pada program sumber tersebut. 3. Operator dan Delimiter Operator, misalnya operator aritmatika (+, - , * , /), operator logika (<, =, >) 4. Delimiter Delimiter berguna sebagai pemisal/ pembatas, misalnya: ( ) , . ; : (kurung buka/tutup, koma, titik, titik koma, titik dua), white-space (pemisah yang diabaikan di program seperti spase, karakter enter, ganti baris, akhir file. Contoh 1: Misalkan terdapat sebuat source program: Program coba; Var A : integer; Begin A := A + 2; End. Pada contoh di atas, besaran leksik (token) nya adalah simbol yang bernilai ‘Program’, ‘Coba’, ‘Var’, ‘A’, ‘Integer’, ‘;’, ‘:’, ‘+’, ‘.’,’2’, ‘:=‘, ‘Begin’, ‘End’. Contoh 2 : Ada urutan karakter yang disebut dengan statement Fahrenheit := 32 + celcius * 1,8 Maka akan diterjemahkan ke dalam token-token di bawah ini: identifier fahrenheit operator := integer 32 operator + identifier celcius operator perkalian * real / float 1,8 Setiap bentuk dari token direpresentasi sebagai angka dalam bentuk internal, dan angkanya adalah unik. Misalnya nilai 1 untuk variabel, 2 untuk konstanta, 3 untuk label, 4 untuk operator, dst.
TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 20 Contoh : Kondisi : If A > B then C = D; Maka Scanner akan mentransformasikan ke dalam token-token sbb: kondisi3 : 26 If 20 A 1 > 15 B 1 then 21 C 1 D 1 ; 27 Token-token ini sebagai inputan untuk syntax analyser, token-token ini bisa berbentuk pasangan item. Dimana item pertama menunjukkan alamat atau lokasi dari token pada tabel simbol. Item kedua adalah representasi internal dari token. Semua token direpresentasikan dengan informasi yang panjangnya tetap (konstan), suatu alamat (address atau pointer) dan sebuah integer (bilangan bulat). Misalkan sebuah bahasa memiliki himpunan simbol terminal/token : ‘<‘ , ‘>’, ‘=‘, ‘<=‘, ‘>=‘ , ‘<>’ Atau bisa dibaca sebagai token-token : t_L, t_G, t_E, t_LE, t_GE, t_NE (G=greater, L=Less, E=Equal, N=Not). Bahasa tersebut juga mendukung penulisan komentar yang diawali dengan ‘{‘ dan diakhiri dengan ’}‘. Kita lihat Diagram Keadaan untuk kumpulan token di atas pada gambar berikut : <
Start
=
>
t_L
=
t_LE
> t_E
t_G
t_NE
=
apa saja selain } { }
komentar
t_GE
TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 21 Tabel State T(stata,karakter) dari Diagram State di atas : Karakter Stata <
>
=
{
}
apa saja
Start
t_L
t_G
t_E
komentar
x
x
t_L
x
t_NE
t_LE
x
x
x
t_LE
x
x
x
x
x
x
t_E
x
x
x
x
x
x
t_NE
x
x
x
x
x
x
t_G
x
x
t_GE
x
x
x
t_GE
x
x
x
x
x
x
x
x
x
Start
komentar
Komentar
x
Formula tabel tersebut adalah : j, jika ada transisi berlabel a dari i ke j T(i,a)= x, jika tidak ada transisi berlabel a dari i Jika T(i,a) = x, maka ada 2 kemungkinan : Jika stata i merupakan stata akhir berarti pada stata i telah ditemukan sebuah token. Jika stata i bukan stata akhir berarti pada stata i telah terdeteksi token tidak dikenal.
Dalam Pascal, komentar tidak diperlukan lagi pada proses selanjutnya, karena itu komentar tidak dimasukkan sebagai token. Setiap scanner menemukan awal komentar, scanner hanya mengambil simbol yang didapat tanpa disimpan ke dalam token. Setelah ditemukan akhir dari komentar, state dikembalikan ke state awal (serupa dengan white space) Scanner biasanya diimplementasikan sebagai sebuah prosedur yang dipanggil oleh Parser. Contoh Prosedur scan sederhana yang akan membaca sebuah file input dan memberikan token hasilnya dapat dilihat pada : Procedure GetChar; Begin Read(FileInput, Kar); end; dimana : FileInput : text, Kar: character
TEKNIK KOMPILASI Tony Darmanto,ST / Smt V – S1 – TI / STMIK WIDYA DHARMA/ Hal 22 Procedure Scan Begin While Kar=‘ ‘ do GetChar ; {selama ketemu spasi maju terus} Repeat Case Kar Of ‘<‘ : begin GetChar ; Case Kar Of ‘=‘ : begin token:=t_LE; exit; end; ‘>’ : begin token:=t_NE; exit; end; else begin token:=t_L; exit; end; end; ‘=‘ : begin token:=t_E; exit; end; ‘>’ : begin GetChar ; If Kar = ‘=‘ then begin token:=t_GE; exit; end else begin token:=t_G; exit; end; end; ‘ { ‘: begin Repeat GetChar ; {maju sampai ketemu penutup komentar} Until Kar = ‘ } ‘ GetChar ; {lanjutkan maju, tanpa memperoleh token} end; EOF:exit; {akhir file} Until False; {sampai ketemu sebuah token atau akhir file } End;
