Site hosted by Angelfire.com: Build your free website today!
Kirim surat ke "iyesn@usa.net"

CATATAN KULIAH

Menu Utama

 

   JURUSAN / BIDANG STUDI
    TEKNIK INFORMATIKA
 
    TEKNIK KOMPILASI
  
   
Catatan Kuliah Teknik Kompilasi  
 
 
 
Rujukan
1. Jean Paul Tremblay and Paul G Sorenson, Theory and Practise of Compiler Writing, McGraw Hill, 1985.
2. Alfred V Aho and Jeffrey D Ullman, Compilers Principles, Technique and Tools, Addison-Wesley, 1988.
3. Alfed V Aho and Jeffrey D Ullman, Principles of Compilers Design, Addison-Weley, 1974.
 
PENGANTAR TEKNIK KOMPILASI
Bahasa pemrograman berdasarkan pada tingkat ketergantungan mesin :
1. Bahasa mesin
2. Bahasa assembly
3. Bahasa tingkat tinggi (user oriented) : Pascal, Basic
4. Bahasa yang problem oriented : SQL
 
Translator
Mengubah source code menjadi target/object code.
1. Assembler : source code adalah bahasa assembly.
2. Compiler : source code adalah bahasa tingkat tinggi (misal Pascal).
3. Interpreter : tidak membangkitkan object code, hasil translasi dalam bentuk internal (misal Basic, LISP).
 
Proses Kompilasi
Source Code -> Compiler -> Object Code -> Eksekusi Komputer (+Data) -> Hasil
Source code dan data diproses pada saat yang berbeda.
Compile time : saat source code diubah ke object code.
Run time : saat object code dieksekusi.
 
Proses Interpretasi
Source Code -> Interpreter (+Data) -> Hasil
Source code dan data diproses pada saat yang sama.
 
Model Kompilator
Sebuah kompilator memiliki dua fungsi :
1. Fungsi Analis : dekomposisi program sumber menjadi bagian-bagian dasarnya.
Source Code -> Lexical Analyzer : Scanner -> Syntactic Analyzer : Parser -> Semantic Analyzer : Intermediate Code Generator
2. Fungsi Sintesis : pembangkitan dan optimasi kode.
Code Generator -> Code Optimizer -> Object Code
Keterangan :
Scanner : memecah program sumber menjadi besaran leksik/token.
Parser : memeriksa urutan kemunculan token.
Analisis Semantik : biasanya digabungkan dengan intermediate code generator (bagian yang berfungsi membangkitkan kode antara).
Code Generator : membangkitkan kode objek.
Code Optimizer : memperkecil hasil dan mempercepat proses.
Tabel Simbol : menyimpan semua informasi yang berhubungan dengan kompilasi.
 
Model Kompilator seperti di atas disebut Multi Pass Compiler / Separate Compiler yaitu Scanner dan Parser bekerja terpisah. Scanner menghasilkan semua token, baru diproses oleh Parser.
Berbeda dengan One Pass Compiler dimana Scanner baru bekerja menghasilkan tiap token setelah mendapatkan perintah dari Parser.
Token : besaran pembangun bahasa/representasi dari besaran leksik.
 
Mutu Kompilator
1. Kecepatan dan waktu proses kompilasi.
    Tergantung pada :
    a. Penulisan algoritma kompilator, yaitu algoritma yang digunakan untuk menuliskan program kompilator tersebut.
    b. Kompilator pengkompilasi, sebuah program khusus yang menghasilkan kompilator tersebut.
2. Mutu program objek : ukuran dan kecepatan eksekusi dari program objek.
    Tergantung pada :
    Fungsi translasi yang digunakan (cara untuk melakukan perubahan dari source code ke object code).
3. Integrated Environment, yaitu fasilitas-fasilitas terintegrasi yang dimiliki oleh kompilator tersebut. Misalnya untuk melakukan editing, debugging, maupun testing.
 
Pembuatan Kompilator
Dapat dilakukan dengan :
1. Bahasa mesin, kesulitan sangat tinggi.
2. Bahasa assembly, biasa digunakan sebagai tahap awal.
    Keuntungan : object code berukuran kecil.
    Kerugian : memerlukan usaha yang besar.
3. Bahasa tingkat tinggi lain pada mesin yang sama.
    Keuntungan : pemrograman mudah.
    Kerugian : program hasil.
4. Bahasa tingkat tinggi yang sama pada mesin yang berbeda.
5. Bootstrap (diperkenalkan oleh Wirth).
    Ide : kita bisa membangun sesuatu yang besar dengan dimulai dari bagian intinya.

 

KONSEP DAN NOTASI BAHASA
Bahasa : himpunan semua string yang dapat dibentuk dari himpunan alphabet.
Klasifikasi bahasa menurut hirarki Chomsky :
- Bahasa Regular
   Pada mesin otomata Finite State Automata (NFA dan DFA).
- Bahasa Bebas Konteks (Context Free)
   Pada mesin otomata Push Down Automata.
- Context Sensitive
   Bekerja pada mesin otomata Linier Bounded Automata.
- Unrestrieted / Tipe 0 / Phase Structure
   Pada mesin turing, tidak ada batasan.
 
Diagram Status / State Transition Diagram
Berguna untuk mendapatkan token, yaitu melakukan analisis leksikal. Misal suatu bahasa memiliki himpunan simbol terminal/token berikut : (t_PLUS, t_MIN, t_ID, t_INT).
Maka diagram state-nya :
*t_ID(identifier) bisa berupa nama atau keyword.
Keyword/kata kunci yang sudah didefinisikan oleh suatu bahasa. Misal VAR jumlah : integer
maka VAR, integer adalah keyword, jumlah adalah nama.
 
Notasi BNF (Backus Naur Form)
Aturan-aturan produksi dapat dinyatakan dalam bentuk BNF.
< >  mengapit non terminal.
{ }  pengulangan 0 sampai n kali.
[ ]  0 atau 1 kali muncul.
( )  contoh x(yz) = xy | xz.
Contoh :
    Aturan Produksi     E -> T | T + E | T - E,  T -> a
    Notasi BNF           E ::= <T> | <T>+<E> | <T>-<E>
 
Diagram Sintaks
Membantu pembuatan parser/analisis sintaksis.
Kotak = variabel/nonterminal, bulat = terminal.

 

ANALISIS LEKSIKAL / SCANNER
Melakukan analisis leksikal, mengidentifikasikan semua besaran yang membangun suatu bahasa.
Tugas Scanner :
1. Merunut karakter demi karakter.
2. Mengenali besaran leksik.
3. Mentransformasi menjadi suatu token.
4. Mengirimkan token.
5. Membuang semua komentar dalam program.
6. Menangani kesalahan.
7. Menangani tabel simbol.
 
Scanner bekerja berdasarkan mesin Finite State Automata pada Regular Grammar. Untuk membantu mengkonstruksi Scanner dapat mempergunakan Diagram State.
Yang termasuk besaran pembangun bahasa/leksik :
1. Keywords : Begin, End, If, Else.
2. Nama
3. Nilai konstanta
4. Operator dan delimiter : +, -, *, /, ( ), :, ;, dsb.

 

ANALISIS SINTAKSIS / PARSER
- Top Down : dari root menuju leave (simbol awal sampai simbol terminal).
   a. Backtrack : Brute Force
   b. No backtrack : Recursive Descent Parser
- Bottom Up
 
Parsing dengan Brute Force
Contoh : bahasa dengan aturan produksi 
    S -> aAd | aB          A -> b | c          B -> ccd | ddc
untuk mem-parsing string 'accd' (dengan S simbol awal).
Kelemahan :
- Mencoba untuk semua aturan produksi yang ada sehingga menjadi lambat (rentang waktu eksekusi tidak jelas).
- Menyulitkan untuk melakukan pemulihan kesalahan.
- Memakan banyak memori karena perlu mencatat lokasi backtrack.
Grammar left recursive tidak dapat diperiksa, dan harus diubah dulu sehingga tidak left recursive.
 
Parsing dengan Recursive Descent Parser
Secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur.
- Semua simbol variabel dijadikan prosedur/fungsi.
- Bertemu simbol terminal, panggil prosedur Scan.
- Bertemu simbol variabel, panggil prosedur tersebut.
<iYAN,301099>

 

    Pilihan Mata Kuliah :

  1. Rekayasa Perangkat Lunak
  2. Teknik Kompilasi
  3.  

 

 

 

Copyright(c) 1999 by Yanuar Firdaus A.W