Teknik Kompilasi

          Merupakan Teknik dalam melakukan pembacaan suatu program yang ditulis dalam bahasa sumber, kemudian diterjemahkan ke dalam suatu bahasa lain yang disebut bahasa sasaran.

Tehnik Kompilasi mengajarkan kita untuk mengerti mengenai proses compiler dari sebuah bahasa pemprograman.Dalam melakukan proses penerjemahan tersebut, sudah barang tentu kompilator akan melaporkan adanya keanehan-keanehan atau kesalahan yang mungkin ditemukannya. Proses penerjemahan yang dilakukan oleh kompilator ini disebut proses kompilasi (compiling).

1.Apa itu tehnik kompilasi adalah sebuah tehnik bagaimana melakukan translasi atau penterjemahan dari bahasa pemprograman/bahasa tingkat tinggi menjadi sebuah bahas mesin/assembly language.

2.Kegunaan Tehnik Kompilasi àmempermudah programmer dalam menentukan hasil akhir dari sebuah program yang dia inginkan

3.Jenis bahasa Pemprograman berdasarkan tigkat ketergantungan terhdap mesin :
a.Bahasa Mesin
b.bahasa Assembly
c.Bahasa Tingkat Tinggi(User Oriented)
d.Problem Oriented.

4.Macam-Macam Translator
   a.Interpreter=suatu program yang mengeksekusi secara langsung intermediate code dari satu bahasa pemprograman.
   b.Assembler=suatu translator yang menterjemahkan program sumber yang ditulis dalam bahasa assembly menjadi bahasa mesin.
   c.Compiler=Menerima program sumber sebagai input dan menghasilkan sederatan instruksi mesin yang ekuivalen sebagai outputnya.

5.Proses Kompilasi

a.analisis leksikal/Analisis Linear/Pembacaan sekilas(Scanning)
b.Analisis Sintaksis
c.analisis Semantiks
d.Proses pembentukan kode.
e.Proses Optimasi Kode
f.Tabel manajemen(book keeping)
g.Penanganan kesalahan(Error Handling)

6.Hasil Dari 3 proses analisis adalah sebuah intermediate code /kode antara
      3 proses analisa yang terjadi dalam kompilasi adalah

a.Analisis Leksikal
b.analisis Sintaksis
c.Analisis Semantik

7.Optimasi program adalah sebuah tahap yang digunakan untuk menghasilkan kode program yang berukuran lebih kecil dan lebih cepat dalam proses eksekusinya.

8.Berdasarkan ketergantungannya pada mesin optimasi program dibagi menjadi :
a.Machine Dependent Optimizerà Kode Optimasi yang telah disediakan oleh processornya namun hanya dapat digunakan oleh satu jenis dan tipe processor sajah.
b.Machine Independent Optimizerà Kode Optimasi yang dapat digunakan oleh banyak tipe mesin dan processor.

9.Optimasi program terbagi atas : optimasi global dan optimasi local.
a.optimasi local adalah optimasi yang hanya dilakukan pada satu blok dan source kode.
b.optiimasi global adalah optimasi yang dilakukan setelah dilakukan analisis flow yaitu suatu graph berarah yang menunjukkan jalur yang mungkin selama proses eksekusi program.

10.Cara-cara optimasi Lokal :

a.Folding
b.Redundant subexpression elimination
c.Optimasi dalam sebuah Iterasi
*Loop Unrolling digantikan dengan penulisan langsung dengan syrat pengulangan tidak lebih dari 3
*frequency reduction pemindahan statement ke tempat yang lebih jarang diekseksekusi seandainya statement tersebut kurang dibutuhkan dalam sebuah iterasi.
d.Strength Reduction

11.Optimasi Global berguna bagi :

a.Programmer à untuk menginformasikan
*Dead Code-à Kode yang tidak pernah dieksekusi
*Unused Parameterà Parameter yang tidak pernah digunakan
*Unused VariabelàVariabel-variable yang tidak dipakai dalam program.
*VARIABEL yang dipakai tanpa nilai awal.

b.Kompilator
*Meningkatkan efisiensi eksekusi program
*Menghilangkan useless code/kode yg tidak terpakai.

Contoh kompilator adalah :Bahasa Pascal, C++. 

 Contoh Interpreter adalah : Bahasa Basica, Dbase / Foxbase  

Contoh Translator adalah : Bahasa Pascal, C++, 

Bahasa Basica Contoh Assembler adalah : TASM, MASM, NASM, FASM 

Contoh Emulator : emu8086  

       perbandingan antara Turbo Pascal 5 dan Turbo Pascal 6, di mana Turbo Pascal 6 lebih baik dari pada Turbo Pascal 5 bila program objek ( exe ) yang di hasilkan berukuran lebih kecil dan lebih cepat di eksekusi. Hal ini di pengaruhi oleh fungsi translasi yang di gunakan oleh kompilator tersebut ( cara untuk melakukan perubahan dari source kode ke object kode ).

          Penerjemah bahasa pemrograman dibedakan menjadi tiga macam, yaitu:

 Assembler adalah program yang digunakan untuk menerjemahkan kode sumber dalam bahasa rakitan (assembly) ke dalam bahasa mesin Referensi Pascal Tim Olimpiade Komputer Indonesia

       Kompiler adalah program penerjemah yang mengonversi semua kode sumber selain dalam bahasa rakitan menjadi kode objek. Hasil berupa kode objek inilah yang bisa dija lankan oleh komputer. Perlu diketahui, proses untuk melakukan penerjemahan ini biasa disebut kompilasi. Bahasa pemrograman yang menggunakan proses kompilasi adalah: Bahasa COBOL, Pascal ,.

         Bahasa C Intepreteradalah program yang menerjemahkan satu per satu instruksi dalam kode sumber dan kemudian segera menjalankan instruksi yang telah diterjemahkan tersebut. Bahasa seperti BASIC pada awalnya menggunakan konsep intepreter ini.  

Bahasa rakitan (bahasa Inggris: assembly language) adalah bahasa pemrograman komputer tingkat rendah. Bahasa assembly merupakan notasi untuk bahasa mesin yang dapat dibaca oleh manusia dan berbeda-beda tergantung dari arsitektur komputer yang digunakan. Berbeda dengan bahasa pemrograman tingkat tinggi, bahasa assembly atau rakitan biasanya memiliki hubungan 1-1 dengan instruksi bahasa mesin. Misalnya, tiap julukan (mnemonic) yang ditulis di program dengan bahasa rakitan akan diterjemahkan menjadi tepat satu kode operasi yang dapat dimengerti langsung oleh komputer. Pada bahasa tingkat tinggi, satu perintah dapat diterjemahkan menjadi beberapa kode operasi dalam bahasa mesin. Proses pengubahan bahasa rakitan ke bahasa mesin dilakukan oleh assembler, dan proses balikannya dilakukan oleh disassembler. Setiap arsitektur komputer memiliki bahasa mesin yang berbeda-beda sehingga bahasa rakitannya pun berbeda-beda.

 Pemrograman AT89S51

 

          bahasa Assembly Bahasa Assembly adalah bahasa pemrograman tingkat rendah. Dalam pemrograman komputer dikenal dua jenis tingkatan bahasa, jenis yang pertama adalah bahasa pemrograman tingkat tinggi (high level language) dan jenis yang kedua adalah bahasa pemrograman tingkat rendah (low level language). Bahasa pemrograman tingkat tinggi lebih berorientasi kepada manusia yaitu bagaimana agar pernyataan-pernyataan yang ada dalam program mudah ditulis dan dimengerti oleh manusia. Sedangkan bahasa tingkat rendah lebih berorientasi ke mesin, yaitu bagaimana agar komputer dapat langsung mengintepretasikan pernyataan-pernyataan program.

 

Kelebihan Bahasa Assembly:  

1. Ketika di-compile lebih kecil ukuran 

2. Lebih efisien/hemat memori

 3. Lebih cepat dieksekusi

 Kesulitan Bahasa Assembly:

 1. Dalam melakukan suatu pekerjaan, baris program relatif lebih panjang dibanding bahasa tingkat tinggi

 2. Relatif lebih sulit untuk dipahami terutama jika jumlah baris sudah terlalu banyak 

3. Lebih sulit dalam melakukan pekerjaan rumit, misalnya operasi matematis. 

Compiler Compiler adalah suatu program yang menerjemahkan bahasa program ( source code) kedalam bahasa objek (obyek code). Compiler menggabungkan keseluruhan bahasa program, mengumpulkannya dan kemudian menyusunnya kembali.

 Tahap Kompilasi

: Ø Pertama source code (program yang ditulis) dibaca kememori computer).  

Ø Source code tersebut diubah menjadi objek code (bahasa Assembly).

 Ø Objek code di hubungkan dengan liberary yang dibutuhkan untuk membentuk file yang bisa dieksekusi. 

Ø Komplier memerlukan waktu untuk membuat suatu program dapat di eksekusi oleh computer, program yang dieksekusi oleh compiler adalah dapat berjalan lebih cepat disbanding program yang diperoduksi oleh interpreter, disamping itu juga bersifat independen.

 Ø Contoh program yang menggunakan compiler adalah Visual Basic, Visual Delvi, dan Pascal. Interpreter Berbeda dengan compiler, interpreter menganalisis dan mengeksekusi setiap baris program tanpa melihat program secara keseluruhan. Keutungan dari interpreter adalah bahwa eksekusi bisa dilakukan dengan segera tanpa melalui tahap komplasi. Untuk alas an ini interpreter digunakan pada saat pembuatan program skala besar. Contoh program yang menggunakan intpreter adalah Cobol, PHP, ASP, dan lain-lain.

 Perbedaan 1. Perbedaan antara Compiler dengan Interpreter :

 

 a. Jika hendak menjalankan program hasil kompilasi dapat dilakukan tanpa butuh source code. Kalau interpreter butuh source code.

 b. Jika dengan kompiler, maka pembuatan kode yang bisa dijalankan mesin dilakukan dalam 2 tahap terpisah, yaitu parsing ( pembuatan kode objek ) dan linking ( penggabungan kode objek dengan library ) . Kalau interpreter tidak ada proses terpisah.

 c. JIka compiler membutuhkan linker untuk menggabungkan kode objek dengan berbagai macam library demi menghasilkan suatu kode yang bisa dijalankan oleh mesin. Kalau interpreter tidak butuh linker untuk menggabungkan kode objek dengan berbagai macam library. 

d. Interpreter cocok untuk membuat / menguji coba modul ( sub-routine / program-program kecil ). Maka compiler agak repot karena untuk mengubah suatu modul / kode objek kecil, maka harus dilakukan proses linking / penggabungan kembali semua objek dengan library yang diperlukan.

 e. Pada kompiler bisa dilakukan optimisasi / peningkatan kualitas kode yang bisa dijalankan.

 Ada yang dioptimasi supaya lebih cepat, ada yang supaya lebih kecil, ada yang dioptimasi untuk sistem dengan banyak processor. Kalau interpreter susah atau bahkan tidak bisa dioptimasikan.

 2. Perbedaan antara Assembler,Interpreter dan Kompiler : 

a. Assembler mengubah kode assembly menjadi kode mesin.Interpreter mengubah kode tingkat tinggi menjadi real-time kode mesin dan menyimpannya di memori untuk pengeksekusian secara langsung.Kompiler mengubah kode tingkat tinggi menjadi real-time kode mesin atau beberapa kode tingkat menengah dan menyimpan ke dalam sebuah file untuk bisa dieksekusi kemudian. 

b. Interpreter merupakan translator yang menerjemahkan bahasa paling lambat dibandingkan assembler dan kompiler. 

c. Kompiler merupakan translator yang paling mudah untuk digunakan dalam menerjemahkan bahasa dibandingkan interpreter dan assembler. Interpreter menerjemahkan program baris per baris, artinya apabila suatu baris akan dieksekusi, maka baris tersebut diterjemahkan dulu dalam bahasa mesin, baru selanjutnya baris berikutnya yang akan dieksekusi. Contoh bahasa pemrograman yang menggunakan interpreter adalah Basic. Compiler menerjemahkan semua perintah dalam bahasa mesin baru kemudian menjalankan hasil penerjemahan. Hasil penerjemahan tersebut disimpan dalam file atau memori. Contoh bahasa yang menggunakan compiler adalah Pascal, C, dan C++.

METODE PARSING

Ada 2 metoda parsing : top-down dan bottom-up. 

Parsing top-down	:	Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon parsing jika dibaca dari kiri ke kanan.
Parsing bottom-up	:	Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x

yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke kanan sampai tiba di simbol awal S (atau tidak sampai di S jika kalimat x memang tidak bisa diturunkan dari S) .

Parsing Top-Down

Ada 2 kelas metoda parsing top-down, yaitu kelas metoda dengan backup dan kelas metoda tanpa backup. Contoh metoda kelas dengan backup adalah metoda Brute-Force, sedangkan contoh metoda kelas tanpa backup adalah metoda recursive descent.

a. Metoda Brute-Force

Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor urut produksi.

Contoh Soal : 

Diberikan grammar G = {S → aAd|aB,  A → b|c,  B → ccd|ddc}. Gunakan metoda BruteForce untuk melakukan analisis sintaks terhadap kalimat x = accd.

Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang mengandung produksi rekursi kiri (left recursion) : A → A∝. Produksi rekursi kiri akan menyebabkan parsing mengalami looping tak hingga.

Contoh Soal : 

Diberikan grammar G = {S → aAc,  A → Abε}. Gunakan metoda Brute-Force untuk melakukan analisis sintaks terhadap kalimat x = ac.

Agar tidak menghasilkan looping tak hingga, grammar rekursi kiri harus ditransformasi.

Untuk contoh di atas transformasi berarti merubah produksi A → Ab menjadi A → bA.

b. Metoda Recursive-Descent

Recursive Descent Parser adalah salah satu cara mengaplikasikan bahasa bebas konteks untuk melakukan analisa sintaksis suatu source code. Ciri dari recursive descent parser yang menonjol adalah secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur (no backtrack).

Berbeda dengan mesin turing yang dapat maju dan mundur dalam melakukan parsing. Ciri lain dari recursive descent parser adalah sangat bergantung pada algoritma scan dalam mengambil token.

Syarat grammar yang dapat di-parse dengan RDP adalah :

• Context free grammar
• Tidak memiliki left recursion
• Menerapkan alternative aturan produksi yang terpanjang (bila terdapat dari satu alternative aturan produksi)

Kelemahan RDP:

• Mereka tidak secepat beberapa metode lain
• Sulit untuk memberikan pesan kesalahan yang baik
• Mereka tidak dapat melakukan parsing yang membutuhkan sembarangan  lookaheads panjang

Kelebihan RDP:

• Mereka sangat sederhana
• Mereka dapat dibangun dari recognizers hanya dengan melakukan beberapa tambahan pekerjaan-spesifik, membangun pohon parse

naah, sekarang kita coba mecahin kasus RDP......

Langkah RDP:

1. Jika produksi A mempunyai dua buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah produksi dengan symbol pertama ruas kanannya sama dengan input yang sedang dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak dapat dilakukan.
2. Jika terdapat dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari semua ruas kanan produksi tidak boleh sama. Ketentuan ini tidak melarang adanya produksi yang bersifat rekursif kiri.

Soal 1:

Grammar G={S → aB | A, A → a, B → b | d}. Gunakan metode Recursive Descent Parsing untuk melakukan analisis sintaks terhadap kalimat x = ac!

Soal 2:

Grammar G={S → bA | c, A → dSd | e}. Gunakan metode Recursive Descent Parsing untuk melakukan analisis sintaks terhadap kalimat x = bdcd.

Parsing Bottom-Up 

Salah satu contoh menarik dari parsing bottom-up adalah parsing pada grammar preseden sederhana (GPS). Sebelum sampai ke parsing tersebut, akan dikemukakan beberapa pengertian dasar serta relasi yang ada pada GPS.

Pengertian Dasar

•      Jika α dan x keduanya diderivasi dari simbol awal grammar tertentu, maka α disebut sentensial jika α ∈ (V T VN)*, dan x disebut kalimat jika x ∈ (V T)*

•      Misalkan α = Q1β Q2  adalah sentensial dan A ∈ VN :

-  β adalah frase dari sentensial α jika : S ⇒ … ⇒ Q1A Q 2 dan A⇒ … ⇒ β

-  β adalah simple frase dari sentensial α jika : S ⇒ … ⇒ Q1A Q 2 dan A⇒ β

-  Simple frase terkiri dinamakan handel

-  frase, simple frase, dan handel adalah string dengan panjang 0 atau lebih..

Contoh Soal : 

(1)    I ⇒ I H       Hb adalah sentensial dan b adalah simple frase 

⇒ H H     (dibandingkan dengan Q1β Q2 maka Q1= H, β = b, dan Q 2 = ε)

⇒ H b     Perhatikan : simple frase (b) adalah yang terakhir diturunkan

(2)    I ⇒ I H        Hb adalah sentensial dan H adalah simple frase 

⇒ I b        (dibandingkan dengan Q1β Q2 maka Q1= ε, β = H, dan Q 2 = b) 

⇒ H b      Perhatikan : simple frase (H) adalah yang terakhir diturunkan

Sentensial Hb mempunyai dua simple frase (b dan H), sedangkan handelnya adalah H.

Relasi Preseden dan Grammar Preseden Sederhana

•      Relasi preseden adalah relasi antara 2 simbol grammar (baik V T maupun  VN) dimana paling tidak salah satu simbol tersebut adalah komponen handel.

•      Misalkan S dan R adalah 2 simbol. Ada 3 relasi preseden yang : ←, ↔, dan →

 Perhatikan : komponen handel selalu ‘menunjuk’ yang simbol lainnya.

Contoh Soal :  

Diketahui grammar dengan G = {Z → bMb, M → (L a, L → Ma)}. Dari 3 sentensial : bab, b(Lb, b(Ma)b, tentukan handel dan relasi yang ada.

 •      Secara umum : jika A → aBc adalah sebuah produksi maka :

-  aBc adalah handel dari sentensial yang mengandung string “aBc”

-  relasi preseden antara a, B, dan c adalah : a ↔ B, B ↔ c

•      Dengan memperhatikan ruas kanan produksi yang ada serta berbagai sentensial yang dapat diderivasi dari Z maka semua relasi preseden tercantum dalam tabel berikut :

 Grammar G disebut grammar preseden sederhana, jika :

1.  paling banyak terdapat satu relasi antara setiap dua simbolnya

2.  tidak terdapat dua produksi produksi dengan ruas kanan yang sama

Parsing Grammar Preseden Sederhana Prosedur parsing :

1.   Buat tabel 3 kolom dengan label : sentensial dan relasi, handel, dan ruas kiri produksi.

2.   Tuliskan kalimat (atau sentensial) yang diselidiki pada baris pertama kolom pertama. 

3.   Dengan menggunakan tabel relasi preseden cantumkan relasi preseden antara setiap dua simbol yang bertetangga.

4.   Tentukan handel dari sentensial tersebut. Handel adalah string yang dibatasi “←“ terakhir dan “→ “ pertama jika dilakukan penelusuran dari kiri atau yang saling mempunyai relasi “↔“. Handel tersebut pastilah merupakan ruas kanan produksi, karena

itu tentukan ruas kiri dari handel tersebut.

5.   Ganti handel dengan ruas kiri produksinya. GOTO 3.

6.   Kalimat yang diselidiki adalah benar dapat diderivasi dari simbol awal jika kolom “ruas kiri produksi” menghasilkan simbol awal.

Tugas Teknik Kompilasi - Proses Analisis Leksikal, Sintaktik, dan Semantik

Analisis Leksikal

Analisis Leksikal/Analisis Linier/Pembacaan Sekilas (Scanner)

Dalam kaitan ini aliran karakter yang membentuk program sumber dibaca dari kiri ke kanan dan dikelompokkan dalam apa yang disebut token yaitu barisan dari karakter yang dalam suatu kesatuan mempunyai suatu arti tersendiri.

Analisis ini melakukan penerjemahan masukan menjadi bentuk yang lebih berguna untuk tahap-tahap kompilasi berikutnya.

Analisis Leksikal merupakan antarmuka antara kode program sumber dan analisis sintaktik (parser). Scanner melakukan pemeriksaan karakter per karakter pada teks masukan, memecah sumber program menjadi bagian-bagian disebut Token.

Analisis Leksikal mengerjakan pengelompokkan urutan-urutan karakter ke dalam komponen pokok: identifier, delimeter, simbol-simbol operator, angka, keyword, noise word, blank, komentar, dan seterusnya menghasilkan suatu Token Leksikal yang akan digunakan pada Analisis Sintaktik.

Model dasar untuk membentuk suatu Analisis Leksikal adalah Finite-State Automata.

2 aspek penting pembuatan Analisis Leksikal adalah:
- Menentukan token-token bahasa.
- Mengenali token-token bahasa dari program sumber.

Token-token dihasilkan dengan cara memisahkan program sumber tersebut dilewatkan ke parser

Analisis Leksikal harus mengirim token ke parser. Untuk mengirim token, scanner harus mengisolasi barisan karakter pada teks sumber yang merupakan 1 token valid. Scanner juga menyingkirkan informasi seperti komentar, blank, batas-batas baris dan lain-lain yang tidak penting (tidak mempunyai arti) bagi parsing dan Code Generator.

Scanner juga harus dapat mengidentifikasi token secara lengkap dan membedakan keyword dan identifier. Untuk itu scanner memerlukan tabel simbol. Scanner memasukkan identifier ke tabel simbol, memasukkan konstanta literal dan numerik ke tabel simbol sendiri setelah konversi menjadi bentuk internal.

Analisis Leksikal merupakan komponen kompilasi independen yang berkomunikasi dengan parser lewat antarmuka yang terdefinisi bagus dan sederhana sehingga pemeliharaan analisis leksikal menjadi lebih mudah dimana perubahan-perubahan terhadap analisis leksikal tidak berdampak pada pengubahan kompilator secara keseluruhan.

Agar dapat memperoleh fitur ini, maka antarmuka harus tidak berubah. Kebanyakan kode yang menyusun analisis leksikal adalah sama untuk seluruh kompilator, tidak peduli bahasa.

Pada analisis leksikal yang dituntun tabel (table-driven lexical analyzer), maka satu-satunya yang berubah adalah tabel itu sendiri.

Kadang diperlukan interaksi analisis leksikal dan analisis sintaktik yang lebih kompleks. Sehingga analisis leksikal harus dapat menganggap string sebagai token bertipe, bukan identifier.

Untuk itu perlu komunikasi tingkat lebih tinggi yang biasanya dilakukan suatu struktur data dipakai bersama seperti tabel simbol.

Analisis Sintaktik dapat memasukkan string ke tabel simbol, mengidentifikasi sebagai Type atau typedef, sehingga analisis leksikal dapat memeriksa tabel simbol untuk menentukan apakah lexeme adalah tipe token atau identifier.


Tugas-tugas Analisis leksikal

1. Konversi Program Sumber Menjadi Barisan Token
Mengubah program sumber yang dipandang sebagai barisan byte/karakter menjadi token

2. Menangani Kerumitan Sistem Masukkan/Keluaran
Karena analisis leksikal biasanya berhubungan langsung dengan kode sumber yang diwadahi file, maka analisis leksikal juga bertindak sebagai benteng untuk komponen-komponen lain di kompilator dalam mengatasi keanehan-keanehan sistem masukkan/keluaran sistem operasi dan sistem komputer.

Optimasi perlu dilakukan agar analisis leksikal membaca karakter degan sekaligus membaca sejumlah besar bagian file.

Perangkat masukkan/keluaran benar-benar diisolasi agar tidak terlihat oleh parser dan komponen-komponen kompilator yang lain.


Tugas-tugas tambahan Analisis Leksikal

1. Penghilangan komentar dan whitespace (tab,spasi,karakter lainnya)
Tindakan housekeeping dilakukan scanner sehingga mengisolasikan dari parser dan komponen-komponen kompilator lain.

Peran ini menyederhanakan perancangan parser (dan grammar bahasa pemrograman).

Scanner juga mencatat nomor baris saat itu sehingga penanganan kesalahan yang cerdas dapat mengirim pesan kesalahan dengan lebih akurat.

2. Konversi literal/konstanta numerik menjadi tipe data tertentu
Analisis leksikal dapat mengirim token, dan nilainya. Nilai ini biasa disebut atribut.

Namun demikian, bila analisis leksikal ditambahin dengan tugas-tugas tambahan yang terlalu banyak juga akan menjadi tidak baik. Karena itu membatasi analisis leksikal hanya untuk melakukan tugas pengenalan pola token (ditambah membuang komentar) adalah mempermudah pemeliharaan.


Tahap Pelaksanaan Analisis Leksikal
- Pada single one pass
Terjadi interaksi antara scanner dan parser. Sacnner dipanggil saat parser memerlukan token berikutnya. Pendekatan ini lebih baik karena bentuk internal program sumber yang lengkap tidak perlu dibangun dan disimpan di memori sebelum parsing dimulai.

- Pada separate pass
Scanner memproses secara terpisah, dilakukan sebelum parsing. Hasil scanner disimpan dalam file. Dari file tersebut, parsing melakukan kegiatannya.

Scanner mengirim nilai-nilai integer yang mempresentasikan bentuk internal token, bukan nilai-nilai string.

Keunggulan cara ini adalah ukurannya kecil dan tetap. Parser sangat lebih efisien bekerja dengan nilai integer yang mempresentasikan simbol daripada string nyata dengan panjang variabel.


Implementasi Analisis Leksikal

1. Pengenalan Token
- Scanner harus dapat mengenali token
- Terlebih dahulu dideskripsikan token-token yang harus dikenali

2. Pendeskripsian Token
- Menggunakan reguler grammar. Menspesifikasikan aturan-aturan pembangkit token-token dengan kelemahan reguler grammar menspesifikasikan token berbentuk pembangkit, sedang scanner perlu bentuk pengenalan.

- Menggunakan ekspresi grammar. Menspesifikasikan token-token dengan ekspresi reguler.

- Model matematis yang dapat memodelkan pengenalan adalah finite-state acceptor (FSA) atau finite automata.

3. Implementasi Analisis Leksikal sebagai Finite Automata
Pada pemodelan analisis leksikal sebagai pengenal yang menerapkan finite automata, analisis leksikal tidak cuma hanya melakukan mengatakan YA atau TIDAK. Dengan demikian selain pengenal, maka analisis leksikal juga melakukan aksi-aksi tambahan yang diasosiasikan dengan string yangsedang diolah.

Analisis leksikal dapat dibangun dengan menumpangkan pada konsep pengenal yang berupa finite automata dengan cara menspesifikasikan rutin-rutin (aksi-aksi) tertentu terhadap string yang sedang dikenali.

4. Penanganan Kesalahan di Analisis Leksikal
Hanya sedikit kesalahan yang diidentifikasi di analisis leksikal secara mandiri karena analisis leksikal benar-benar merupakan pandangan sangat lokal terhadap program sumber.

Bila ditemui situasi dimana analisis leksikal tidak mampu melanjutkan proses karena tidak ada pola token yang cocok, maka terdapat beragam alternatif pemulihan. yaitu:

- "Panic mode" dengan menghapus karakter-karakter berikutnya sampai analisis leksikal menemukan token yang terdefinisi bagus

- Menyisipkan karakter yang hilang

- Mengganti karakter yang salah dengan karakter yang benar

- Mentransposisikan 2 karakter yang bersebelahan.

Salah satu cara untuk menemukan kesalahan-kesalahan di program adalah menghitung jumlah transformasi kesalahan minimum yang diperlukan untuk mentransformasikan program yang salah menjadi program yag secara sintaks benar.


Input Buffering

Perancangan analisis leksikal seharusnya dapat membuat buffering masukkan yang membantu mempercepat proses pembacaan dari file serta mempunyai fleksibelitas yang tinggi agar analisis leksikal tidak bergantung platform sehingga mempunyai portabilitas yang tinggi.

Analisis Sintaktik

Analisis Sintaktik/Analisis Hirarki/Parsing

Dalam tahap ini karakter atau token yang diperoleh pada analisis leksikal disusun dan dikelompokkan dalam suatu hirarki tertentu yang secara keseluruhan mempunyai arti tertentu.

Disinilah struktur program yang lebih besar diidentifikasi (statement, deklarasi, ekspresi, dan lainnya) menggunakan token leksikal yang dihasilkan Analisis Leksikal.

Analisis Sintaktik selalu bekerja bergantian dengan Analisis Semantik.
- Pertama, Analisis Sintaktik mengidentifikasikan urutan Token Leksikal seperti ekspresi, statement, subprogram, dan lainnya.
- Analisis Semantik kemudian dipanggil untuk proses unit ini.

Analisis Sintaktik berfungsi menghasilkan pohon sintaks program sumber yang didefinisi grammar.

Simbol terminal pohon sintaks adalah token-token yang dihasilkan scanner.

Analisis Semantik

Kata Semantik berasal dari Bahasa Yunani: semantikos,artinya memberikan tanda, penting, dari kata sema, tanda) adalah cabang linguistik yang mempelajari makna yang terkandung pada suatu bahasa, kode, atau jenis representasi lain.

Semantik biasanya dikontraskan dengan dua aspek lain dari ekspresi makna: sintaksis, pembentukan simbol kompleks dari simbol yang lebih sederhana, serta pragmatika, penggunaan praktis simbol oleh agen atau komunitas pada suatu kondisi atau konteks tertentu.

Disini dilakukan pengecekan pada struktur akhir yang telah diperoleh dan diperiksa kesesuainnya dengan komponen program yang ada.
Merupakan pusat dari tahapan translasi, struktur sintaktik yang dikenali oleh Analisis Sintaktik diproses, dan struktur objek eksekusi sudah mulai dibentuk. Analisis Semantik kemudian menjadi jembatan antara analisis dan sintesis dari translasi.
Analisis Semantik menghasilkan suatu kode objek yang dapat dieksekusi dalam translasi sederhana, tetapi biasanya bentuk dari kode objek yang dapat dieksekusi ini merupakan bentuk internal dari final program eksekusi, yang kemudian dimanipulasi oleh tahap optimisasi dari translator sebelum akhirnya kode eksekusi benar-benar dihasilkan.
Analisis semantik berperan dalam memeriksa kesalahan-kesalahan yang bersifat semantik. Salah satu peranan analisis semantik yang penting adalah pemeriksaan tipe variabel. Contohnya operator * hanya digunakan untuk operand dengan tipe integer ataupun real. Sedangkan operator and, or, digunakan hanya untuk operand dengan dengan tipe boolean.
Peranan lain dari analisis semantik adalah memeriksa keunikan suatu nama. Misalnya dalam Pascal, nama variabel global tidak boleh sama dengan prosedur atau nama fungsi. Dalam bahasa C, jika suatu nama konstanta didefinisikan lebih dari satu kali, maka akan diperiksa kesamaan nilai kedua konstanta.
Analisis semantik dapat dilakukan dengan menggunakan salah satu dari dua bentuk notasi, yaitu Definisi Berdasarkan Sintak (DBS) dan Skema Translasi. Definisi Berdasarkan Sintak (DBS) merupakan gabungan tata bahasa dengan himpunan aturan semantik yang akan menentukan struktur sintak dari suatu masukan. Aturan semantik digunakan untuk menghitung atribut, misalnya tipe atau nilai konstanta, yang berkaitan dengan simbol dalam aturan produksi.

Mendefinisikan arti dari program yang benar secara syntax dari bahasa tersebut.

int nilai[10]

Semantik akan menentukan deklarasi diatas akan menyebabkan ruang sebanyak 10 elemen integer yang diberikan kepada variabel nilai

if (a > b) max = a else max = b;

Ekspresi a > b harus dievaluasi terlebih dulu, tergantung dari nilai ini satu dari dua statement di belakangnya akan dieksekusi

Analisa Semantik pusat dari tahapan translasi struktur syntatic hasil dari syntatic analyzer diproses menghasilkan suatu kode objek yang executable sederhana akan dimanipulasi oleh tahap optimasi sampai jadi kode executable.

Analisis semantik menganalisis kebenaran source program. Analisis semantik akan memanfaatkan pohon sintaks yang dihasilkan oleh proses parsing. Bagian ini berfungsi menentukan makna dari serangkaian instruksi dari source code.

Tujuan: menentukan makna dari serangkaian instruksi yang terdapat pada source code.

Yang dilakukan oleh analisis semantik:
1. Type Checking
2. Dilakukan pengecekan tipe ekspresi dan variabel.
3. Static Checking: pengecekan dilakukan oleh kompiler

Contoh: pengecekan operator dan operand sesuai dengan tipe, flow of control check, uniqueness check (apakah ada duplikasi), name-related check (apakah sudah terdefinisi)

Dynamic Checking: pengecekan dilakukan oleh target program.
1. Type Conversion
2. Implicit, dilakukan oleh kompiler
3. Explicit, dilakukan oleh programmer

Contoh:

Analisis Semantik adalah proses setelah melewati proses scanning dan parsing. Pada tahap ini dilakukan pengecekan pada struktur akhir yang telah diperoleh dan diperiksa kesesuaiannya dengan komponen program yang ada. Secara global, fungsi dari semantic analyzer adalah untuk menentukan makna dari serangkaian instruksi yang terdapat dalam program sumber.

A:=(A+B)*(C+D)

Pada proses parsing, parser akan menjumpai ekspresi-ekspresi diatas seperti atas, seperti simbol ‘:=’, ‘+’, dan ‘*’. Namun parser tidak tahu makna yang tersimpan di dalam simbol-simbol tersebut.

Oleh karena itu Analisis Semantik akan melakukan:
- Apakah variabel yang ada telah didefinisikan sebelumnya.

- Apakah variabel tersebut tipenya sama dan benar.

-Apakah operan yang akan dioperasikan ada nilainya.

Menentukan derajat operator

Untuk dapat menjalankan aksinya, analisis semantik akan membutuhkan tabel simbol.

Tabel Simbol berfungsi untuk:
Menyimpan informasi tentang:
1. Nama variabel dan tipe datanya
2. Informasi detail untuk record dan array
3. Nama prosedur dan fungsi yang ada
4. Jumlah, nama, tipe data dan paramter fungsi/prosedur
5. Nama label
a. Konstanta dan String
b. Membantu pemeriksaan kebenaran semantik dari source code
c. Membantu mempermudah dalam pembuatan intermediate code dan code generation

Operasi Tabel Simbol
1. Jenis operasi yang dilakukan dalam tabel simbol adalah
a. Operasi insert (append/add)
b. Operasi search (dengan hashing)
c. Operasi delete

2. Biasanya tabel simbol dibuat pada tahap analisis lexical dan masing-masing data di dalam tabel simbol diberi indeks tertentu yang bersifat unik.

3. Oleh analisis sintaks, tabel simbol digunakan untuk memeriksa kebenaran sintaks dan membangkitkan pohon sintaks untuk proses parsing.

4. Hasilnya akan dianalisa kebenaran semantiksnya dan digunakan pada tahapan code generation untuk menghasilkan sekumpulan instruksi object code.

Tabel Simbol

- Pada dasarnya tabel simbol berisi daftar dan informasi indentifier pokok yang terdapat pada source code.

- Tabel ini disebut sebagai tabel pokok.

- Dari tabel pokok ini kemungkinan besar dapat terjadi tidak semua informasi tercover semuanya. Jadi diperlukan tabel lagi yang berfungsi sebagai tabel pembantu.

- Di dalam tabel utama harus terdapat field yang menjembatani identifier dari tabel utama ke tabel lain yang bersesuaian (analogikan dengan konsep basis data atau senarai pointer)

Elemen Tabel Simbol
1. Pada umumnya elemen-elemen tabel simbol:
2. No urut identifier (ID unik / auto increment)
3. Nama identifier: berisi nama-nama variabel, prosedure, fungsi, dan lain-lain yang akan digunakan untuk referensi pada analisis semantik, intermediate code, dan code generation.
4. Tipe identifier: berisi keterangan tipe identifier.
5. Object Time Address: berisi address yang mengacu pada alamat tertentu di memori
6. Dimensi (ukuran) dari identifier yang bersangkutan
7. Nomor baris variabel yang dideklarasikan
8. Field link (opsional)

Jenis Tabel Simbol
1. Beberapa jenis Tabel Simbol:
2. Tabel identifier: berisi daftar identifier
3. Tabel array: berisi informasi tambahan untuk array
4. Tabel blok: berisi variabel-variabel dalam lingkup blok yang sama (lokal)
5. Tabel real: berisi elemen tabel bernilai real
6. Tabel string: berisi informasi string
7. Tabel display: berisi blok yang aktif
8. Tabel integer: berisi informasi elemen bernilai integer

Tabel Simbol Identifier
1. No urut identifier
2. Nama identifier
3. Jenis identifier : prosedur, fungsi, tipe, variabel, konstanta
4. Tipe identifier: integer, real, char, boolean, string, record
5. Level : berupa kedalaman identifier (blok program). Misal main program = level 0, prosedur dan fungsi dalam main program = level 1. Field ini digunakan pada saat runtime untuk mengetahuicurrent activation record yang bisa diakses.
6. Pada identifier, perlu dicatat juga:
7. Alamat dari identifier
8. Informasi acuan identifier ke tabel identifier lain yang menerangkannya
9. Link: menghubungkan identifier ke identifier lainnya, atau yang dideklarasikan pada level yang sama
10. Normal: digunakan pada pemanggilan parameter by value dan by reference (berupa variabel boolean)

Contoh Tabel Identifier
Program A;
var B : integer;
Procedure X(Z:char);
var C : integer;
begin
. . . .

Pada tabel identifier akan muncul:
0A
1B
2X
3Z
4C

Contoh implementasi tabel identifier:
Table : array [0..tabmax] of
Record
Name : string;
Link: integer;
Obj: objek;
Tipe: types;
Ref: integer;
Normal: Boolean;
Level: 0..maxlevel;
Address: integer;
End;

Dimana :
Ø Objek = { konstant, variabel, prosedure, fungsi }
Ø Types = { notipe, int, reals, booleans, chars, arrays, records }

Tabel Array
1. No urut array dalam tabel
2. Tipe dari indeks array yang bersangkutan
3. Tipe elemen array
4. Alamat Referensi dari elemen array
5. Indeks batas atas dan bawah array
6. Jumlah elemen array
7. Ukuran total array = (atas –bawah + 1) * elemen size

Contoh implementasi:
TabArray: array [1..tabmax] of
Record
Indextype, elementype: types;
Elemenref, low, high, tabsize:integer;
End;

Tabel Blok
1. No urut blok
2. Batas awal blok
3. Batas akhir blok
4. Ukuran parameter
5. Ukuran variabel
6. Last variabel
7. Last parameter

Contoh Tabel Blok
TabBlok: array[1..tabmax] of
Record
Lastvar, lastpar, parsize, varsize:integer;
End;
Dengan contoh program di atas maka untuk program A:
Last variabel: 2 (lihat dari tabel idenfier, last variable adalah X = 2)
Variabel size: 2 (integer = 2 byte)
Last parameter: 0 (tanpa paramter)
Parameter size: 0
Untuk procedure X:
Last variabel: 4 (lihat dari tabel idenfier, last variable adalah C = 4)
Variabel size: 2 (integer = 2 byte)
Last parameter: 3 (Z = 3)
Parameter size: 1 (char = 1 byte)

Contoh Tabel Simbol lain
Tabel Real dan Tabel String:
1. No urut
2. Untuk real: nilai real sedangkan untuk string: karakter-karakter yang ada dalam string

Tabel Display:
1. Berfungsi mencatat blok yang sedang aktif
2. No urut
3. Blok yang sedang aktif
4. Pengisiannya menggunakan konsep stack

Urutan Pemrosesan
1. Urutan pengaksesan: Tabel Dsiplay –Tabel Blok –Tabel Simbol
2. Pertama, tabel display akan mengetahui mana bagian yang aktif, maka akan diketahui identifier-identier yang aktif dalam blok tersebut.
3. Informasi identifier yang ada mungkin belum lengkap sehingga diperlukan melihat referensi ke tabel-tabel pelengkap lainnya.

Implementasi Tabel Simbol
1. Jelas tidak menggunakan database, Tapi menggunakan:
2. Linked List
3. Tree
4. Hash table

Hash
Contoh fungsi hash:
maxtabel = 9
h(string) = Σ(ASCII(Ci)) mod (maxtabel+1)
h(“ABC”) = 65+66+67 = 198 mod 10 = 8
h(“AA”) = 65+65 = 130 mod 10 = 0
h(“BAC”) = 66+65+67 = 198 mod 10 = 8 terjadi collision
Maka :
0AA
1
2
3
4
5
6
7
8ABC -> BAC
9


Untuk mengetahui makna, maka rutin analisa semantik akan memeriksa:
- Apakah variabel yang ada telah didefinisikan sebelumnya,
- Apakah variabel – variabel tersebut tipenya sama,
- Apakah operan yang akan dioperasikan tersebut ada nilainya dan seterusnya.

Untuk dapat menjalankan fungsi tersebut dengan baik, semantic analyzer seringkali menggunakan tabel simbol. Pemeriksaan bisa dilakukan pada tabel identifier, tabel display dan tabel blok, misal pada field link.

Pengecekan yang dilakukan oleh analisis semantik adalah :
- Memeriksa keberlakuan nama – nama meliputi pemeriksaan :
- Duplikasi
Pengecekan apakah sebuah nama terjadi pendefinisian lebih dari dua kali. Pengecekan dilakukan pada bagian pengelola blok.
- Terdefinisi
Pengecekan apakah sebuah nama yang dipakai pada tubuh program sudah terdefinisi atau belum. Pengecekan dilakukan pada semua tempat kecuali blok.
- Memeriksa tipe
Melakukan pemeriksaan terhadap kesesuaian tipe dalam statement – statement yang ada.

Misal : Bila ada operasi antara dua operan, maka tipe operan pertama harus bisa dioperasikan dengan operan kedua.

Analisa semantik sering juga digabungkan pada pembangkitan kode antara yang menghasilkan Output intermediate code, yang nantinya akan digunakan pada proses kompilasi berikutnya.

Kode Antara.
Pembentukan kode antara merupakan tahap lanjutan setelah analisis semantik. Hasil pembentukan kode antara dapat dianggap sebagai program dengan instruksi-instruksi bahasa mesin abstrak. Bentuk representasi kode antara harus mudah pembuatannya dan mudah diterjemahkan dalam bahasa tujuan. Salah satu bentuk representasi kode antara adalah kode tiga alamat. Misalnya, suatu kalimat matematik a := b * c + d memiliki bentuk kode tiga alamat sebagai berikut :
t1 := b * c t2 := t1 + d a := t2
Representasi kode tiga alamat memiliki bentuk yang menyerupai kode dalam bahasa Assembly, sehingga memudahkan proses penterjemahannya, jika bahasa tujuan adalah bahasa Assembly. Bentuk kode tiga alamat di atas memiliki karakteristik: mengandung paling banyak tiga operand dan dua operator, serta memiliki variabel sementara. Bentuk lain dari representasi kode antara adalah dalam bentuk representasi grafik, seperti pohon maupun graf. Salah satu manfaat pembentukan kode antara adalah ia berfungsi sebagai input untuk proses optimisasi. Salah satu contoh adalah jika terdapat sub ekspresi yang sama muncul dalam program pemakai, maka kompilator dengan fasilitas optimisasi tidak akan mengeksekusi ekspresi itu berulang kali, tapi cukup sekali.
Kode antara/Intermediate Code merupakan hasil dari tahapan analisis, yang dibuat oleh kompilator pada saat mentranslasikan program dari bahasa tingkat tinggi. Kegunaan dari Kode Antara / intermediate code :
- Untuk memperkecil usaha dalam membangun kompilator dari sejumlah bahasa ke sejumlah mesin. Dengan adanya kode antara yang lebih machine independent maka kode antara yang dihasilkan dapat digunakan lagi pada mesin lainnya.
- Proses optimasi lebih mudah. Beberapa strategi optimisasi lebih mudah dilakukan pada kode antara daripada pada program sumber atau pada kode assembly dan kode mesin.
- Bisa melihat program internal yang gampang dimengerti. Kode antara ini akan lebih mudah dipahami dari pada kode assembly atau kode mesin.

Notasi Postfix.
Sehari-hari kita biasa menggunakan operasi dalam notasi infix (letak operator di tengah). Pada notasi Postfix operator diletakkan paling akhir maka disebut juga dengan notasi Sufix atau Reverse Polish.
Sintaks notasi Postfix :
&nb sp;
&nb sp; &nb sp;
Misalkan ekspresi :
&nb sp; &nb sp; (a + b)*(c + d)


Mudah dibangkitkan dari parse bottom-up
Misalkan aksi semantik untuk produksi
S _ i=E { Output (‘=‘,i.leksemes)}
E _ E + E { Output(‘+’) }
E _ E * E { Output(‘*’)}
E _(E) { Tak ada kerja}
E _ I { Output(i.leksemes)}

Sebelum mendaftar operator, terlebih dulu mendaftar semua
operandnya
Pada notasi postfix operator diletakkan paling akhir, maka disebut juga dengan notasi Sufix atau Reverse Polish. Sintaks notasi postfix :

Contoh ekspresi:
(a+b)*(c+d)
Dinyatakan dengan notasi postfix :
ab+cd+*
Kontrol program yang ada dapat diubah ke dalam notasi postfix. Misal :
IF THEN ELSE
Diubah ke dalam postfix :
BZ BR
↑ ↑
label1 label2
Keterangan :
BZ : branch if zero (zero = salah) {bercabang/meloncat jika kondisi yang dites salah}
BR : branch {bercabang/meloncat tanpa ada kondisi yang dites}

Arti dari notasi postfix diatas adalah :
“ Jika kondisi ekspresi salah, maka instruksi akan meloncat ke label1 dan menjalankan statement2. Bila kondisi ekspresi benar, maka statement1 akan dijalankan lalu meloncat ke label2. Label1 dan label2 sendiri menunjukkan posisi tujuan loncatan, untuk label1 posisinya tepat sebelum statement2, dan label2 adalah statement2.”
Contoh lain:
WHILE DO
Diubah ke postfix :
BZBR
↑ ↑
label1 label2

Notasi N–Tuple.
Bila pada postfix setiap baris instruksi hanya terdiri dari satu tuple, pada notasi N–tuple setiap baris bisa terdiri dari beberapa tuple. Format umum notasi N-tuple adalah :
operator.......................N-1 operan
Notasi N-Tuple yang biasa digunakan adalah notasi 3 tupel dan 4 tupel.

Triples Notation
Notasi ini memiliki format sebagai berikut :

Contoh instruksi :
A := D * C + B / E
Kode antara tripel :
1. *, D, C
2. /, B, E
3. +, (1), (2)
4. :=, A, (3)

operasi perkalian/pembagian lebih prioritas dibandingkan penjumlahan/pengurangan
Contoh lain:
IF x > y THEN
x:= a – b
ELSE
x:= a + b
kode antara tripelnya :
1. >,x,y
2. BZ,(1),(6) {bila kondisi (1) salah satu loncat ke no (6)}
3. –,a,b
4. :=,x,(3)
5. BR, ,(8)
6. +,a,b
7. :=,x,(6)
Contoh :
&nb sp; A:= B+C*D/E
F:= C*D
List Instruksinya:
1. &nb sp; *, C, D
2. &nb sp; /, (1), E
3. &nb sp; +, B, (2)
4. &nb sp; :=, A, (3)
5. &nb sp; :=, F, (1)
List Eksekusinya :
1. &nb sp; 1
2. &nb sp; 2
3. &nb sp; 3
4. &nb sp; 4
5. &nb sp; 1
6. &nb sp; 5 

Kekurangan dari notasi tripel adalah sulit pada saat melakukan optimasi, maka dikembangkan Indirect Triples yang memiliki dua list, yaitu list instruksi dan list eksekusi. List instruksi berisi notasi tripel, sedang list eksekusi mengatur urutan eksekusinya.

Quadruples Notation
Format notasi quadruples :

Hasil adalah temporary variabel yang bisa ditempatkan pada memory atau register. Masalah yang ada bagaimana mengelola temporary variabel (hasil) seminimal mungkin
Contoh instruksi :
A := D * C + B / E
Dibuat dalam kode antara :
1. *, D, C, T1
2. /, B, E, T2
3. +, T1, T2, A