OTOMATA PENGANTAR KOMPILASI

Otomata, teori bahasa, kompilasi,
itu apa dan hubungannya bagaimana ?

• Otomata, berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit.
Contoh :Mesin Jaja / vending machine,Kunci kombinasi, Parser/compiler, dll.
• Teori bahasa formal, membahas mengenai pembentukan bahasa dengan suatu aturan tatabahasa.Teori Otomata dan bahasa formal, berkaitan dalam hal :
– Pembangkitan kalimat/generation : menghasilkan semua kalimat dalam bahasa L berdasarkan aturan yang dimilikinya
– Pengenalan kalimat / recognition : menentukan suatu string (kalimat) termasuk sebagai salah satu anggota bahasa L
• Kompilasi ; Proses penterjemahan program dari suatu bahasa sumber (source language) menjadi bahasa sasaran (target language).

Teori dasar, tatabahasa dan kelas bahasa
1. Memahami tatabahasa, aturan produksi.
Tata Bahasa : Aturan yang disebutkan pada proses pengenalan dan pembangkitan kalimat.
Secara formal, tata bahasa terdiri dari 4 komponen yaitu :
1. Himpunan berhingga, tidak kosong dari simbol-simbol non terminal T
2. Himpunan berhingga, dari simbol-simbol non-terminal N
3. Simbol awal S Î N, yang merupakan salah satu anggota dari himpunan simbol non-terminal.
4. Himpunan berhingga aturan produksi P yang setiap elemennya dituliskan dalam bentuk :
a ® b
dimana a dan b adalah string yang dibentuk dari himpunan T È N dan a harus berisi paling sedikit satu simbol non-terminal.
Keempat komponen tersebut sering dituliskan sbb :
G = (T,N,S,P)

Aturan Produksi : Aturan produksi a®b yang diterapkan pada suatu string w=aac mengganti kemunculan. a menjadi b, sehingga string tersebut berubah menjadi w=abc, sehingga dapat dituliskan aac Þ abc (aac memproduksi abc).
Produksi tersebut dapat diterapkan berkali-kali
w1 Þ w2 Þ w3 Þ ... Þ wn
atau dapat dituliskan
w1 Þ* wn
jika minimal harus ada 1 aturan produksi yang diterapkan :
w1 Þ+ wn
2. Memahami hirarki bahasa
Proses kompilasi dan bahasa formal
1. Memahami proses kompilasi.
2. Memahami hal yang dilakukan kompilator pada fase analisa (leksikal, sintaks, dan semantik)
3. Memahami hal yang dilakukan kompilator pada fase sintesa (pembentukan dan optimalisasi kode)

Proses kompilasi dari suatu kompilator



• Klasifikasi menurut cara pembentukan ;
single pass, multi pass, load and go

Proses kompilasi

Apa itu Finite State Automata?
Model matematika yang dapat menerima input dan mengeluarkan output
Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi
Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity.

Definisi Formal: Finite State Automata
M=(Q , S , d , S , F )
Q = himpunan state
S = himpunan simbol input
d = fungsi transisi d : Q ´ S
S = state awal / initial state , SÎQ
F = state akhir, F Í Q
Contohnya..
M=(Q , S , d , S , F )
Q = {Genap, Ganjil}
S = {0,1}
S = Genap
F = {Ganjil }

Nama : Rinda lisna wulandari
NIM : 120911042 (B)
sumber : http://rustamaji.himatif.or.id/detail_download.php?aksi=detail&matakuliah=8

0 komentar:

Poskan Komentar