Analisis Leksikal / Scanner Teknik Kompilasi Universitas Pamulang

 

Analisis Leksikal adalah aliran karakter yang membentuk program sumber dibaca dari kiri ke kanan dan dikelompokkan dalam apa yang disebut token yaitu barisan dari karakter yang dalam suatu kesatuan mempunyai suatu arti tersendiri.

Analisis ini melakukan penerjemahan masukan menjadi bentuk yang lebih berguna untuk tahap-tahap kompilasi berikutnya.

Analisis Leksikal merupakan antarmuka antara kode program sumber dan analisis sintaktik (parser). Scanner melakukan pemeriksaan karakter per karakter pada teks masukan, memecah sumber program menjadi bagian-bagian disebut Token.

Analisis 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 Analisis Sintaktik.

Kira-kira seperti itulah pengertian Analisis Leksikal.

Token adalah satuan terkecil dari bahasa sumber yaitu deretan karakter

terpendek yang mengandung arti.

  Token dikelompokkan menjadi beberapa jenis sbb.:

identifier

keyword

label

operator aritmetika dan assignment

operator relasional - tanda baca, dan sebagainya.

  Masing-masing token diberikan nomor penyajian internal atau sering disebut nomor token, misalnya sebagai berikut : nama variabel

 konstanta 

2 label

3 keyword 4 operator penambahan

5 operator pemberian (assignment) 

6 operator pengurangan

7 operator perkalian 

8 operator pembagian 

9 tanda baca koma

10 tanda baca : 

11 tanda baca ; 

12 dan lain-lain.

Perbedaan DFA dan NFA, jika DFA state diberi input, selanjutnya tepat menuju 1 state, berbeda dengan NFA bisa saja menuju ke beberapa state selanjutnya.

Berbagai perbedaan DFA dan NFA lain, terkait ruang (space) dan eksekusi string yang dilakukan.

Finite automata merupakan mesin automata dari bahasa reguler. Seperti yang kita ketahui, finite automata terbagi menjadi 2:

Deterministic Finite Automata (DFA)

Non-Deterministic Finite Automata (NFA)

Baik itu DFA maupun NFA, memiliki ciri-ciri atau karakteristik yang berbeda.

Berikut ini beberapa perbedaan DFA dan NFA, dengan disertai pengertian dan contoh dari masing-masing DFA dan NFA.

Deterministic Finite Automata (DFA)

Deterministic Finite Automata (DFA) menerima masukan (input) yang hanya memiliki 1 busur keluar.

Deterministic Finite Automata (DFA) sering dikenal juga sebagai Deterministic Finite-State Machine (DFSM) dan Deterministic Finite-State Automaton (DFSA).

DFA diperkenalkan oleh Warren McCulloch dan Walter Pitts sebagai peneliti pertama yang memperkenalkan konsep yang mirip dengan finite automata di tahun 1943.

DFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

Q, himpunan state, contohnya {q0, q1, q2}

Σ, input alphabet, contohnya {a, b}

δ, fungsi transisi

q0, state awal

F, state akhir

Contoh DFA

Q = {q0, q1, q2}

∑ = {0, 1}

q0 = {q0}

F = {q2}

Non-Deterministic Finite Automata (NFA)

Non-Deterministic Finite Automata (NFA) menerima masukan (input) dengan memiliki lebih dari 1 busur keluar atau bahkan tidak memiliki busur keluar.

Non-Deterministic Finite Automata (NFA) sering dikenal juga sebagai Non-Deterministic Finite-State Machine (NFSM) dan Non-Deterministic Finite-State Automaton (NFSA).

NFA diperkenalkan pada tahun 1959 oleh Michael O. Rabin dan Dana Scott.

NFA sendiri merupakan finite automata dengan memiliki 5 tuple yang direpresentasikan sebagai berikut:

Q, himpunan state, contohnya {q0, q1, q2}

Σ, input alphabet, contohnya {a, b}

δ, fungsi transisi

q0, state awal

F, state akhir

Contoh NFA

Q = {q0, q1, q2}

∑ = {0, 1}

q0 = {q0}

F = {q2}