teknik kompilasi mesin turing

Ø  MESIN TURING

          Mesin turing adalah otomata yang menjadi model computer yang  dikenal saat ini. Mesin turing memungkinkan untuk mempelajari decidability, yaitu pertanyaan mengenai apa yang dapat dan tidak dapat dikerjakan oleh computer. mesin ini juga memungkinkan  menbedakan tractable problem (dapat dipecahkan dalam waktu polynomial) dari intractable problem (tidak dapat dipecahkan dalam waktu polynomial).

·         Pembuktian Deduktif

    Metode pembuktian yang mendasar ini dilakukan dengan cara mendaftar statemant yang diketahui benar atau yang secara logika mengikuti beberapa statement sebelumnya.

·         Pembuktian stetement jika-maka

Banyak teorema memiliki bentuk “jika (sesuatu) maka (sesuatu yang lain)”. Statemant tersebut atau statemant yang mengikuti “jika” merupakan hipotesis dan yang mengikuti “maka” adalah kesimpulan. Pembuktian deduktif statement jika-maka dimulai dengan hipotesis dan dilanjutkan dengan statement yang mengikuti secara logika hipotesis dan statement sebelumnya, hingga kesimpulan dibuktikan sebagai salah satu statement.

·          Pembuktian statemant jika dan hanya jika

Ada teorima-teorema yang memiliki bentuk “(sesuatu) jika dan hanya jika (sesuatu yang lain)”. Statemen-statemen tersebut dibuktikan dengan cara statemen “jika-maka” pada kedua arah. Jenis teorema yang sama mengklain kasamaan himpunan-himpunan yang dideskripsikan dengan dua cara yang berbeda;

·          Pembuktian Kontrapositif

Pembuktian kontrapositif terkadang,  lebih mudah untuk membuktikan statement “jika H maka C” dengan membuktikan “jika hal dan bukan C maka (sesuatu yang diketahui salah).” Pembuktian dengan cara ini disebut sebagai pembuktian dengan kontradiksi.

·          Counter example:

Terkadang kita diminta untuk menunjukan bahwa suatu statement tertentu tidak benar. jika statement memiliki satu atau lebih para meter, maka kita dapat menunjukan bahwa statement tersebut salah sebagai suatu generalisasi dengan menyediakan satu saja counterexample, yaitu suatu penetapan/penyerahan nilai kepada parameter yang membuat statement tersebut salah.

·         Pembuktuan Induktif

Statemen yang memiliki parameter bilangan bulat n sering kali dapat dibuktikan dengan induksi pada n. kita membuktikan statemen tersebut benar atau basis, yaitu sejumblah berhingga kasus untuk nilai n tertentu dan kemudian membuktikan langkah induktif: bahwa jika statemen bernilai benar untuk nilai-nilai hingga n, maka ia juga bernilai benar untuk n + 1.

·         Intruksi Struktural

Pada beberapa situasi, teorema yang akan dibuktika secara induktif teorema mengenai suatu kontruksi yang didefinisikan secara rekursif , misalnya pohon (tree). Kita dapat membuktikan teorema mengenai obyek-obyek yang dikontruksi melalui induksi pada jumblah langkah yang digunakan untuk mengkontruksinya. Jenis intruksi ini dirujuk sebagai structural.

·          Alfabet

Alphabet adalah sembarang himpunan simbul-simbul.

·         Untai (string):

Untai adalah deretan simbul-simbul yang panjangnya berhingga.

·          Bahasa Dan Problema

Bahasa adalah himpunan (bisa jadi himpunan tak hingga) untai-untai, seluruhnya memilih timbulnya dari satu alphabet yang sama. Ketika suatu untai bahasa ditafsirkan denggan suatu cara pertanyaan mengenai apakah untai tersebut berada dibahasanya sering disebut sebagai problema.

Bahasa suatu Automata
Otomaton menerima untai-untai. Suatu untai diterima jika sejak dari stata mula, alihan yang disebabkan oleh pemrosesan sombol-simbol untai-untai tersebut. diagram alihan, untai diterima jika terdapat label lintasan dari stata mula kesuatu stata penerima.

• Kontruksi himpunan bagian
Dengan memperlakukan himpunan stata NFA sebagai stata suatu DFA, kita dapat mengkonfersi sembarang NFA menjadi DFA penerima bahasa yang sama.
Teori Bahasa Automata Dalam Ilmu Komputer
Suatu teori hanya menarik jika dapat membantu dalam mencari solusi terbaik. Tanpa penerapan timbul pertanyaan, mengapa mempelajari teori?
Teori memberikan konsep dan prinsip yang menolong untuk memahami perilaku dari suatu persoalan yang berkorelasi dengan teori tersebut. Bidang ilmu komputer meliputi topik yang luas, dari perancangan mesin sampai pemrograman. Disamping perbedaan yang ada, terdapat keseragaman prinsip-prinsip umum yang dipakai. Untuk mempelajari prinsip-prinsip dasar tersebut, kita mengkonstruksi suatu mesin otomata sebagai model abstrak dari komputer dan komputasi.

Teori bahasa membicarakan bahasa formal (formal language), yang terdiri dari kumpulan kalimat. Sebuah kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama oleh dua atau lebih tata bahasa yang berbeda terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).

Bahasa dalam hal ini berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar yang mempunyai nilai/ manfaat sangat besar di ilmu informatika/ computer karena untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lain dan dapat diterapkan pada perancangan kompilator.
Sedangkan otomata (Automata) adalah suatu sistem yang terdiri atas sejumlah berhingga state yang mempelajari tentang mesin abstrak yang menerima input dan mengeluarkan output dalam bentuk diskret (satu per satu). Dimana state adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu sedangkan input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin.

Bahasa sasaran

Program sumber merupakan rangkaian karakter. Berikut ini hal-hal yang dilakukan oleh
setiap fase pada proses kompilasi terhadap program sumber tersebut :

1. 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. Kelompok karakter yang membentuk sebuah token dinamakan lexeme untuk token tersebut. Setiap token yang dihasilkan disimpan di dalam tabel simbol. Sederetan karakter yang tidak mengikuti pola token akan dilaporkan sebagai token tak dikenal (unidentified token)

.
Contoh : Misalnya pola token untuk identifier I adalah : I = huruf(hurufangka)*.
Lexeme ab2c dikenali sebagai token sementara lexeme 2abc atau abC tidakdikenal.

2. Penganalisa sintaks : memeriksa kesesuaian pola deretan token dengan aturan sintaks
yang ditentukan dalam bahasa sumber. Sederetan token yang
tidak mengikuti aturan sintaks akan dilaporkan sebagai
kesalahan sintaks (sintax error). Secara logika deretan token
yang bersesuaian dengan sintaks tertentu akan dinyatakan
sebagai pohon parsing (parse tree).

Contoh : Misalnya sintaks untuk ekspresi if-then E adalah : E → if L then, L → IOA,
I = huruf(hurufangka)*, O → <=><=>=, A → 01...9. Ekspresi
if a2 < 9 then adalah ekspresi sesuai sintaks; sementara ekspresi if a2 < 9 do
atau if then a2B < 9 tidak sesuai. Perhatikan bahwa contoh ekspresi terakhir
juga mengandung token yang tidak dikenal.

3. 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. Pembangkit kode antara : membangkitkan kode antara (intermediate code) berdasarkan
pohon parsing. Pohon parse selanjutnya diterjemahkan oleh suatu penerjemah yang dinamakan penerjemah berdasarkan sintak (syntax-directed translator). Hasil penerjemahan ini biasanya merupakan perintah tiga alamat (three-address code) yang merupakan representasi program untuk suatu mesin abstrak. Perintah tiga alamat bisa berbentuk quadruples (op, arg1, arg2, result), tripels (op, arg1, arg2). Ekspresi dengan satu argumen dinyatakandengan menetapkan arg2 dengan - (strip, dash)

5. Pengoptimal kode : melakukan optimasi (penghematan space dan waktu komputasi),
jika mungkin, terhadap kode antara.

6. Pembangkit kode : membangkitkan kode dalam bahasa target tertentu (misalnya

bahasa mesin).