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

Teknik Kompilasi

Ø  Bahasa Pemrograman

Manusia dapat melakukan interaksi secara efektif dengan menggunakan media

bahasa. Bahasa memungkinkan penyampaian gagasan dan pemikiran, tanpa itu

komunikasi akan sulit terjadi. Dalam lingkungan pemrograman komputer, bahasa

pemrograman bertindak sebagai sarana komunikasi antara manusia dan

permasalahannya dengan komputer yang dipakai untuk membantu memperoleh

pemecahan. 

Bahasa pemrograman berdasarkan tingkat ketergantungannya dengan mesin bisa

meliputi: 1. Bahasa Mesin

Merupakan bentuk terendah dari bahasa komputer. Setiap instruksi dalam program

direpresentasikan dengan kode numerik, yang secara fisik berupa deretan angka 0

dan 1.  2. Bahasa Assembly

Merupakan bentuk simbolik dari bahasa mesin. Setiap kode operasi memiliki kode

simbolik, misalnya ADD untuk penjumlahan (Addition) dan MUL untuk perkalian

(Multiplication). Pada bahasa assembly tersedia alat bantu untuk diagnostik atau

debug yang tidak terdapat pada bahasa mesin. Contoh produk yang ada untuk

pengembangan dan debug bahasa assembly di pasaran saat ini, misalnya Turbo

Assembler dari Borland, Macro Assembler dari Microsoft, Debug yang tersedia

pada DOS, dan lain – lain.  

3. Bahasa tingkat tinggi (User Oriented)

Disebut tingkat tinggi karena lebih dekat dengan manusia. Memberikan fasilitas

yang lebih banyak, kontrol program yang terstruktur, kalang (nested), block, dan

prosedur. Contohnya : Pascal, C, Basic, dan lain – lain. 4. Bahasa yang Problem Oriented

Memungkinkan penyelesaian untuk suatu masalah atau aplikasi yang spesifik.

Contohnya : SQL (Structured Query Language) untuk aplikasi database, COGO

untuk aplikasi teknik sipil. Bahasa yang problem oriented kadang dimasukkan

pula sebagai bahasa tingkat tinggi.

Keuntungan bahasa tingkat tinggi dibandingkan bahasa tingkat rendah adalah sebagai

berikut. 1. Kemudahan untuk dipelajari. 2. Lebih mendekati permasalahan yang akan diselesaikan. 3. Pemrogram tidak perlu mengetahui bagaimana representasi data ke dalam bentuk

internal di memory

. 4. Memberikan banyak pilihan struktur kontrol seperti :

·         Kondisional (IF – THEN – ELSE)

·         Looping

·         Struktur Blok (Begin ... End)

·         Nested Statement

·          5. kompabilitas dan dokumentasi yang lebih baik dalam pengembangan program. 

Translator

Sebuah translator melakukan pengubahan source code / source program (program

sumber) ke dalam target code / object code / object program (program objek). Source

code ditulis dalam bahasa sumber, sedang object code bisa berupa suatu bahasa

pemrograman lain atau bahasa mesin pada suatu komputer. Ada beberapa macam

translator.

 1. Assembler

Menerjemahkan langsung dari source code ke object code. Source Code adalah

bahasa assembly sedangkan object code adalah bahasa mesin. Contohnya adalah

TASM. 

Contoh yang menghasil .Com adalah : Debug, TASM (bila linker dilakukan

dengan perintah Tlink/x/t), emu8086, 

Contoh yang menghasilkan .Exe adalah : TASM dengan perintah linker Tlink,

HLA, MASM32, FASM

Khusus TASM terkadang file .Com yang dihasilkan akan lebih baik daripada file

.Exe yang dihasilkan sebagai contoh adalah pada program berikut :

.Model Small ,Code ,Org 100h ,Main : , Jmp Mulai , Pesan db 'Selamat Datang!','$' , Mulai : ,  Mov Ah,09H ,  Mov dx,offset pesan , int 21h , mov ah,4ch ,  int 21h ,end Main. 

2. Kompilator (Compiler)

Source Code adalah bahasa tingkat tinggi (misal bahasa Pascal), object code

adalah bahasa mesin atau bahasa assembly. Source Code dan data diproses pada

saat yang berbeda. Contohnya : Turbo Pascal, C++.   

3. Interpreter

Interpreter tidak membangkitkan Object Code, hasil translasi hanya dalam bentuk

Run Time Code.

Contohnya : Bahasa Basica, Dbase/Foxbase 

File.ASM

Assembler File .Exe  atau .Com

Source File

Compiler Object Code

File Executable 

Perbedaan antara Interpreter dengan Compile

Interpreter 1. Menerjemahkan instruksi per instruksi 2. Tidak menghasilkan objek program 3. Tidak menghasilkan executable program 4. Source program terus dipergunakan karena tidak dihasilkan executable program. 

Compiler 1. Menerjemahkan secara keseluruhan sekaligus 2. Dihasilkan objek program 3. Dihasilkan executable program 4. Source program tidak dipergunakan lagi untuk menjalankan program. 

Model Kompilator

Pengembangan kompilator untuk sebuah bahasa merupakan pekerjaan yang

kompleks. Kompleksitas kompilator bisa dikurangi bila perancang bahasa

pemrograman mempertimbangkan bermacam – macam faktor perancangan. Karena

kita berhubungan dengan bahasa tingkat tinggi, bagaimanapun suatu model dasar dari

kompilator dapat diformulasikan.  

Sebuah kompilator umumnya memiliki 2 tugas pokok : 1. Fungsi Analisis

Fungsi analisis biasa disebut sebagai Front End. Tugasnya melakukan

dekomposisi program sumber menjadi bagian – bagian dasarnya. 2. Fungsi Sintesis

Fungsi sintesis biasa disebut sebagai Back End. Tugasnya melakukan

pembangkitan dan optimasi program objek.    

Source Code

Interpreter Run Time Code

Model sebuah kompilator bisa dilihat pada gambar di bawah ini.                

Keterangan gambar :

·         Scanner : memecah program sumber menjadi besaran leksikalnya.

Beberapa kegiatan pada tahap scanner ini diantaranya adalah : - Menangani kesalahan

Contohnya : A = +B 1 - Membuang Blank

Contohnya : A = B     +       1 - Mengenali besaran leksikal

Contohnya di sini adalah mengenali apakah huruf atau angka - Dan lain – lain 

·         Parser : Memeriksa kebenaran dan urutan kemunculan token

Seperti : - Samping kiri ”=” pasti variabel - Samping kanan ”=” pasti ekspresi - Tiap operator +, -, *, /, tidak boleh double. Contohnya : A = 3++7

Source Code

Lexical Analyzer (Scanner)

Syntetic Analyzer (Parser)

Code Optimizer

Sematic Analyzer Intermediate Code Generator

Object Code

Intermediate Code

Code Generator

Tabel Informasi

Analysis Synthesis

·         Analisis semantik : Melakukan analisa semantik, biasanya dalam realisasi akan

digabungkan dengan intermediate code generator (bagian yang berfungsi

membangkitkan kode antara.

Seperti : - Triples Notation - Quadruples Notation

·         Code Generator : Membangkitkan kode objek. Bagian ini merupakan bagian yang

bersifat abstrak, artinya tidak dilaksanakan oleh programmer. Tetapi dilakukan

oleh bahasa pemrograman yang dilakukan oleh programmer dalam perancangan

compiler. Di sini kode antara dari program biasanya ditranslasi ke bahasa

assembly atau bahasa mesin.

·         Code Optimizer : Upaya untuk memperkecil hasil dan mempercepat proses

·         Tabel Informasi : Menyimpan semua informasi yang berhubungan dengan proses

kompilasi. 

Pada beberapa kompilator, bagaimanapun, fase – fase kompilasi tersebut bisa

dikombinasikan. Bisa kita lihat, misalnya interaksi antara scanner dan parser terdapat

dua kemungkinan : 1. Scanner menghasilkan suatu token untuk diproses oleh parser. Parser akan

memanggil scanner bila token berikutnya diperlukan. 2. Scanner menghasilkan semua token yang berhubungan dengan source program

sebelum memneruskan ke parser. Pada kasus ini scanner telah memeriksa

keseluruhan source program. 

Mutu Kompilator

Misalkan saja kita pernah menggunakan kompilator untuk bahasa Basic seperti Turbo

Basic dan Quick Basic. Kemudian kita bisa mengatakan bahwa salah satu lebih baik

dari lainnya. Tentu ada beberapa hal yang menjadi pertimbangan kita, dalam hal ini

bisa kita sebut sebagai mutu dari kompilator yang bersangkutan. Mutu sebuah

kompilator bergantung dari beberapa faktor, yaitu : 1. Kecepatan dan waktu proses kompilasi.

Bisa Anda bayangkan misalkan saat Anda menekan F9 (Compile) dalam

kompilator Turbo Pascal untuk melakukan kompilasi suatu program. Berapa lama

kita harus menunggu untuk memperoleh hasil kompilasi itu merupakan waktu

proses kompilasi. 

Mutu ini tergantung dari :

·         Penulisan algoritma kompilator : yaitu algoritma yang digunakan untuk

menuliskan program kompilator tersebut. Misalkan saja bisa dikatakan bahwa

suatu kompilator lebih cepat melakukan kompilasi dibandingkan lainnya,

karena para pemrogramnya menggunakan algoritma yang lebih baik saat

membuat kompilator tersebut.

·         Kompilator pengkompilasi : sebuah program khusus yang menghasilkan

kompilator tersebut. Bisa kita bayangkan kompilator Turbo Basic, misalnya,

tentu saja tidak dibuat dengan bahasa Basic, tetapi menggunakan bahasa lain

dan dikompilasi.dengan kompilator lain. Kalau sebuah kompilator dibuat

dengan bahasa C, misalnya , kompilator C tersebut juga ikut menentukan mutu

kompilator yang dibuat.   

v  Bootstrap

Gagasan dari Bootstrap adalah kita bisa membangun sesuatu yang besar dengan

lebih dulu membuat bagian intinya. Cara ini diperkenalkan oleh Niklaus Wirth

saat membuat kompilator untuk bahasa Pascal.      

Pada gambar di atas, P0 dibangun dengan assembly, P1 dibangun dengan P0, P2

dibangun dengan P1. Jadi kompilator untuk bahasa P bisa dibuat tanpa harus

secara keseluruhan menggunakan assembly.