Download Materi Kuliah | POtomata dan Pengantar Kompilasi Objek Matakuliah Otomata dan pengantar kompilasi membahas mengenai otomata dan teori bahasa formal beserta penerapannya pada suatu kompilator.
Pertemuan I - III
Detail :
Pengantar Otomata dan pengantar kompilasi
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
Suatu kalimat dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah simbol ‘akar’. Proses penerapan aturan produksi dapat digambarkan sebagai suatu diagram pohon.
Proses kompilasi dan bahasa formal
Jenisnya menurut tingkat ketergantungan mesin
Bahasa mesin
Bahasa Assembly
Bahasa tingkat tinggi
Bahasa problem oriented
Keuntungan bahasa tingkat tinggi
Mudah dipelajari
Lebih dekat pada permasalahan
Tidak perlu harus tahu representasi internal
Lebih mudah didebug
Tidak bergantung pada mesin
Dokumentasi yang baik.
(Selanjutnya dapat didownload)
Pertemuan IV-VI
Detail :
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.
Ekuivalensi NFA-DFA
Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer sepenuhnya deterministic.
Kenapa dipelajari ? Lebih dekat ke sistem nyata
Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu -> nondeterministic
Non deterministik dapat menyelesaikan problem tanpa backtrack, namun dapat diekuivalensikan ke DFA.
Algoritma
1. Buat semua state yang merupakan subset dari state semula. jumlah state
menjadi 2Q
2. Telusuri transisi state–state yang baru terbentuk, dari diagram transisi.
3. Tentukan state awal : {q0}
4. Tentukan state akhir adalah state yang elemennya mengandung state akhir.
5. Reduksi state yang tak tercapai oleh state awal.
Ekspresi reguler
Bahasa disebut reguler jika terdapat FSA yang dapat menerimanya.
Bahasa reguler dinyatakan secara sederhana dengan ekspresi reguler/regular expression (RE).
Contoh penerapan : searching string pada file
RE -> NFA dengan Move -> DFA
Def :Jika merupakan himpunan simbol, maka
1. , , dan a adalah ekspresi reguler dasar
2. jika r dan t masing masing merupakan ekspresi reguler maka komposisi berikut merupakan ekspresi reguler :
(Selanjutnya dapat didownload)
Pertemuan VII-IX
Detail :
Penyederhanaan Tatabahasa Bebas Konteks
Analisa Leksikal
Tatabahasa Bebas Konteks
Analisa Leksikal
Tatabahasa Bebas Konteks
(Selanjutnya dapat didownload)
Pertemuan X-XII
Detail :
Bentuk Normal ChomskySuatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas kontesk tersebut:
Tidak memiliki produksi useless
Tidak memiliki produksi unit
Tidak memiliki produksi Īµ
Penanganan kesalahan dan tabel simbol
OptimasiMetode untuk meningkatkan unjuk kerja, menghemat memory atau ukuran kode program dengan mengganti serangkaian instruksi dengan instruksi yang lebih efisien
Penanganan kesalahan dan tabel simbol
OptimasiMetode untuk meningkatkan unjuk kerja, menghemat memory atau ukuran kode program dengan mengganti serangkaian instruksi dengan instruksi yang lebih efisien
Jenis :
Optimasi tak bergantung mesin (independent)
Optimasi bergantung mesin (dependent)
(Selanjutnya dapat didownload)
Pertemuan XIII-XV
Detail :
Analisa semantik, kode Antara dan Pembangkitan Kode
Pengecekan struktur disesuaikan dengan komponen yang ada.
Menentukan makna dari serangkaian instruksi yang terdapat dalam program sumber
Tag :
0 komentar:
Posting Komentar