Rangkuman Analisis Leksikal

 Analisis Leksikal

Analisis leksikal merupakan antarmuka antara kode program sumber dan analisis sintatik (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 yaitu identifier, delimeter, simbol-simbol operator, angka, keyword, noise word, blank, komentar, dan seterusnya menghasilkan suatu token leksikal yang akan digunakan pada analisis semantik.

Model dasar untuk membentuk suatu analisis leksikal adalah Finite-State Automata, 2 aspek penting pembuatan analisis leksikal adalah :

Menentukan token-token bahasa.

Mengenali token-token bahasa dari program sumber.

Tahap-tahap pelaksanaan analisis leksikal

1. 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.

2. Pada separate pass

Scanner memproses secara terpisah, dilakukan sebelum parsing.Hasil scanner disimpan dalam file. Dari file tersebut, parsing melakukan kegiatannya. Scanner mengirim niulai-nilai integer yang mempresentasikan bentuk internal token, bukan nilai-nilai string. Keunggulan cara ini adalah ukurannya kecil dan tetap.

Input Buffering

Perancangan analisis leksikal seharusnya dapat membuat buffering masukkan yang membantu mempercepat proses pembacaan dari file serta mempunyai fleksibelitas yang tinggi agar analisis leksikal tidak bergantung platform sehingga mempunyai portabilitas yang tinggi.

Ekspresi Reguler

Bahasa reguler dapat dinyatakan sebagai ekspresi reguler dengan menggunakan 3 operator : concate, alternate, dan slosure.

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}