Perbedaan DFA dan NFA

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

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

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

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

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

Perbedaan DFA dan NFA

DFA

• DFA tidak dapat menggunakan transisi string kosong (empty string)
• Dipahami sebagai sebuah mesin
• DFA untuk state selanjutnya bisa ditetapkan dengan jelas
• DFA lebih sulit dibuat
• Waktu yang dibutuhkan untuk mengeksekusi string input lebih sedikit
• Semua DFA merupakan NFA
• DFA membutuhkan lebih banyak ruang (space)

NFA

• NFA dapat menggunakan transisi string kosong (empty string)
• NFA dipahami sebagai beberapa mesin kecil yang melakukan komputasi di waktu bersamaan
• NFA untuk state selanjutnya mempunyai banyak kemungkinan
• NFA lebih mudah dibuat
• Waktu yang dibutuhkan untuk mengeksekusi string input lebih banyak
• Tidak semua NFA adalah DFA
• NFA membutuhkan lebih sedikit ruang (space)

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.

TRANSLATOR PADA TEKNIK KOMPILASI

 Pengertian Translator

Translator yaitu mengubah source code / program sumber ke dalam target code / object code. Source code ditulis dalam sumber sedangkan object code bisa dalam bahasa pemrograman lain atau bahasa mesin pada suatu komputer. Proses penerjemahan dilakukan oleh kompilator disebut compiling atau kompilasi. Kompilator (compilator) bertugas untuk melaporkan jika kemungkinan terjadinya kesalahan atau error.

Macam-macam Translator

1. Assembler

Source code : bahasa assembly

Object code : bahasa mesin

Contoh : Turbo Assembler dan Macro Assembler

2. Kompilator (Compiler)

Sebuah program yang membaca suatu program yang dituliskan ke dalam suatu bahasa sumber dan menerjemahkannya ke dalam suatu bahasa. Source code dan data diproses pada waktu yang berbeda.

Source code : Bahasa tingkat tinggi

Object code : bahasa mesin / bahasa assembly

Contoh : Turbo Pascal.

3. Interpreter

Sebuah program yang digunakan untuk menterjemahkan, mengeksekusi dan memberikan hasil dari eksekusi instruksi masukannya. Interpreter tidak membangkitkan object code, hasil translasinya dalam bentuk internal. Source code dan data diproses pada saat yang sama.

Contoh : BASICA/GW-BASIC, LIPS, SMALLTALK.

Proses kompilasi dikelompokkan ke dalam dua kelompok besar :

1. Analisa : Program sumber dipecah-pecah dan dibentuk menjadi bentuk antara (inter-mediate representation)

2. Sintesa : Membanggun program sasaran yang diinginkan dari bentuk.