Perbedaan Deterministic Finite Automata (DFA) dan Non-Deterministic Finite Automata (NFA )

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.

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

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

Perbedaan DFA dan NFA

Pada intinya, paling mendasar perbedaan DFA dan NFA, jika DFA apabila state diberi input, maka state akan selalu tepat menuju 1 state. Berbeda dengan NFA, jika state diberi input, mungkin saja bisa menuju ke beberapa state selanjutnya.

Sementara itu, berikut ini beberapa perbedaan DFA dan NFA yang disajikan dalam tabel:

DFA

DFA tidak dapat menggunakan transisi string kosong (empty string)

DFA 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)

Read

Analisis Leksikal

 Analisis leksikal atau scanner bertugas mengidentifikasi semua besaran pembangun bahasa (leksikal) yang ada pada kode sumber (source code).

Scanner menerima masukan kode sumber berupa serangkaian karakter kemudian memilah-milahnya ke dalam satuan leksikal, yaitu token.

Token-token ini akan menjadi masukan bagi analisis selanjutnya yaitu analisis sintaksis.

Dari fungsi scanner secara umum seperti telah disebutkan di atas, maka tugas scanner secara rinci adalah:

1. membaca serangkaian karakter dari kode sumber

2. mengenalinya ke dalam satuan leksikal

3. mengubahnya menjadi token dan menentukan jenis tokennya.

4. mengirimkan token ke proses analisis selanjutnya, yaitu analisis sintaksis

5. mengabaikan karakter white space (spasi, enter, ganti baris, penanda akhir file) dan komentar (remark) apabila ada di dalam kode sumber

6. menangani kesalahan

7. menangani tabel simbol

Scanner bekerja berdasarkan prinsip mesin finite state automata (FSA).

Diagram keadaan dapat digunakan untuk membantu mengkonstruksi scanner.

Besaran pembangun bahasa (leksikal) meliputi:

1. Identifier

Identifier atau pengenal dapat berupa:

a. kata tercadang atau kata kunci (reserve word) yang telah didefinisikan oleh bahasa pemrograman

b. kata yang dideklarasikan sendiri oleh pemakai (si pembuat program) disebut dengan variabel.

Contoh (dalam bahasa Pascal)

var

nama : string

alamat : string

jumlah_anak : byte

nominal_tabungan : real

begin

clrscr;

end.

Dari contoh di atas, maka identifier yang dideklarasikan sendiri oleh pemakai (variabel) adalah: nama, alamat, jumlah_anak, dan nominal_tabungan.

Sedangkan identifier kata tercadang (reserve word) adalah: var, string, byte, real, begin, clrscr, dan end. Selain contoh yang disebutkan di atas, masih banyak kata tercadang yang lainnya.

Untuk mendeklarasikan identifier oleh pemakai setiap bahasa pemrograman memiliki aturan yang berbeda-beda, demikian juga dengan identifier kata tercadang memiliki nama dan arti yang berbeda untuk setiap bahasa pemrograman.

Contoh

begin dan end

di bahasa Pascal  kata tercadang

di bahasa C  boleh digunakan untuk nama variabel

{ dan }

di bahasa Pascal  ‘kata’ lebih tepatnya delimiter atau pembatas untuk memberikan komentar pada kode sumber.

di bahasa C  delimiter untuk mengawali dan mengakhiri sebuah blok program

2. Nilai konstanta

Nilai konstanta disini dapat berupa: integer, real, boolean, character, string, dan sebagainya. Melalui contoh berikut ini, bedakan antara nilai (atau isi) dengan variabel yang digunakan untuk menyimpannya.

Contoh (dalam bahasa Pascal)

hitung_luas := panjang * lebar;

x := 1000;

ulang := false;

luas_lingkaran := 3.14 * jejari * jejari;

nama:= budi hartono;

Dari contoh di atas, maka: 1000, false, 3.14, ’budi hartono’ termasuk besaran leksikal berupa nilai konstanta. Sedangkan hirung_luas, panjang, lebar, x, ulang, luas_lingkaran, jejari, dan nama termasuk besaran leksikal identifier variabel.

3. operator dan delimineter

Operator aritmatika ( +, -, *, / )

Operator logika (<, =, >, <=, >=, !=, <>)

Delimiter berguna sebagai pemisah atau pembatas, contoh:

Karakter sebagai berikut ( ) { } ; . , :

Karakter white space, antara lain:

karakter spasi kode ASCII 32

karakter enter (carriage return) kode ASCII 13

karakter ganti baris (line feed)

karakter penanda akhir file (end of file)

Read

Teknik Kompilasi

1. APA ARTI DARI TEKNIK KOMPILASI

Teknik : Metode atau Cara

Kompilasi : Proses mengabungkan serta menterjermahkan sesuatu

(source program) menjadi bentuk lain

 

2.PERBEDAAN COMPILER DAN INTERPRETER:

COMPILER

1.)Source code adalah bahasa tingkat tinggi,

2.)object code adalah bahasa mesin atau bahasa assembly.

3.) Source code dan data diproses berbeda, 

4.)Compiler bisa menangkap berbagai kesalahan dalam 1 program kode sumber secara  sekaligus,

5.)Biasanya program yang dihasilkan compiler lebih cepat dari waktu pelaksanaan program dengan interpreter.

 Interpreter: 

1.)cuma bisa menangkap beberapa kesalahan pada 1 baris kode sumber pada suatu saat,

2.)Interpreter tidak menghasilkan bentuk object code,

3.)tetapi hasil translasinya hanya dalam bentuk internal,

4.)dimana program induk harus selalu ada-berbeda dengan compiler,

5.)Interpreter cocok untuk membuat / menguji coba modul / sub-routine / program-program kecil

 

3.Penganalisa Leksikal

membaca program sumber, karakter demi karakter. Sederetan (satu atau lebih) karakter dikelompokkan menjadi satu kesatuan mengacu kepada pola kesatuan kelompok karakter (token) yang ditentukan dalam bahasa sumber.

Penganalisa Semantik

memeriksa token dan ekspresi dari batasan-batasan yang ditetapkan. Batasan-batasan tersebut misalnya :

a. panjang maksimum token identifier adalah 8 karakter,

b. panjang maksimum ekspresi tunggal adalah 80 karakter,

c. nilai bilangan bulat adalah -32768 s/d 32767,

d. operasi aritmatika harus melibatkan operan-operan yang bertipe sama

 

4.Kenapa perlu Translator ?

-Dengan bahasa mesin adalah bahasa bentuk bahasa terendah komputer, berhubungan langsung dengan bagian bagian komputer seperti bits, register & sangat primitive

-Jawaban atas pertanyaan ini akan membingungkan bagi programmer yang membuat program dengan bahasa mesin.

-Bahasa mesin adalah tidak lebih dari urutan 0 dan 1

-Instruksi dalam bahasa mesin bisa saja dibentuk menjadi micro-code, semacam prosedur dalam bahasa mesin

-Bagaimana dengan orang tidak mengerti bahasa mesin

5.pembuatan compiler ada 3 sebutkan apa saja dan jelaskan

Bahasa mesin

-Sangat sukar dan sangat sedikit kemungkinannya untuk membuat compiler dengan bahasa ini, karena manusia susah mempelajari bahasa mesin,

-Sangat tergantung pada mesin,

-Bahasa Mesin kemungkinan digunakan pada saat pembuatan Assembler

 

Assembly

-Hasil dari program mempunyai Ukuran yang relatif kecil

-Sulit dimengerti karena statement/perintahnya singkat-singkat, butuh usaha yang besar untuk membuat

-Fasilitas yang dimiliki terbatas

Bahasa Tingkat Tinggi (high level language)

-Lebih mudah dipelajari

-Fasilitas yang dimiliki lebih baik (banyak)

-Memiliki ukuran yang relatif besar, misal membuat compiler pascal dengan menggunakan bahasa C

-Untuk mesin yang berbeda perlu dikembangkan tahapan-tahapan tambahan.

-Misal membuat compiler C pada Dos bedasarkan compiler C pada unix 

Read

Translator Pada Teknik Kompilasi

Jenis-Jenis Translator Beserta Fungsinya

#Translator

Translator adalah suatu program di mana mengambil input program dari source code kemudian dituliskan dalam bentuk object code. Atau translator dapat dikatakan sebagai perubahan dari source code ke object code. Proses penterjemahan dilakukan oleh kompilator disebut compiling atau kompilasi. Kompilator (compiler) bertugas untuk melaporkan jika kemungkinan terjadinya kesalahan/error.

Ada 3 jenis translator :

A. Assembler

·         Source Code : bahasa assembly

·         Object Code : bahasa mesin

contoh : Turbo assembler, marco assembler

B. Compiler / Kompilator

Sebuah program yang membaca suatu program yang dituliskan ke dalam suatu bahasa sumber dan menerjemahkannya ke dalam suatu bahasa.

·         Source Code : tingkat tinggi

·         Object Code : bahasa mesin/assembly

·         Source Code dan data diproses pada saat yang berbeda

 

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

Proses kompilasi dikelompokkan ke dalam dua kelompok besar :

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

2. Sintesa : membangun program sasaran yang diinginkan dari bentuk

Read