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
