INTERMEDIATE
CODE GENERATOR
Proses
kompilasi dari suatu kompilator pada dasarnya dapat dibagi ke dalam 2 bagian
utama yaitu bagian analisis dan bagian sintesis.Pada saat proses compiler ada
tahap di mana pembentukan program sasaran dibentuk berdasarkan reprensentasi
antara yang dihasilkan pada tahap analisis,tahap yang di maksud adalah tahap sintesis
dimana tahapa sintesis terbagi dalam 3 bagian yaitu
- intermediate code generator
- code optimizer
- code generator.
Sintesis adalah membangun program sasaran yang diinginkan
dari bentuk antara . Pada bagian ini kita akan menjelaskan sedikit tentang
bagian pertama dari tahap sintesis yaitu intermediate code generator,yaitu
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
dinyatakan dengan menetapkan arg2 dengan - (strip, dash).
Intermediate adalah adalah sebuah representasi yang
disiapkan untuk mesin abstrak tertentu.Di mana intermediatae tersebut harus
memiliki dua sifat yang harus terpenuhi yaitu:
·
Dapat dihasilkan dengan mudah
· Mudah ditranslasikan menjadi program sasaran(target
program)
Representasi kode antara biasanya berbentuk perintah tiga
alamat (three-address code),
baik berbentuk quadruples ataupun triples.Jika kita ingin
mengambil sedikit contoh tentang cara kerja intermediate maka kita bisa melihat
bagaimana intermediate bekerja dalam mengcompile sebuah bahasa pemrograman yang
sederhana,dimana Tahap-tahap compiler yang dianalisa meliputi tahap scanner,
parser, constrainer dan tahap code generator. Scanner mengambil
karakter-karakter input dan mengelompokkannya menjadi token-token. Parser pada
compiler ini merupakan program-driven parser yang mewujudkan grammar dalam
bentuk algoritma, bersifat top-down dan termasuk recursive-descent parser untuk
grammar LL(1). Constrainer memeriksa aturan pendeklarasian variabel, sedangkan
tahap intermediate code generator menghasilkan bentuk positifinya yang
memudahkan proses pembentukan kode output pada tahap code generator.
Bentuk dari intermediate code generator tergantung
bagaimana pemrosesan yang dilakukan selama tahap sintesis,
temp1 := inttoreal(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3
Implementasi
dari bentuk intermediate code generator dapat kita lihat seperti contoh
berikut:
Syntax-Directed Translation
Bagian yang akan
menghasilkan intermediate form dari source code. Fungsinya untuk
menentukan maksud dari suatu source code. Meskipun secara konseptual sintaks
dari suatu program dipisahkan dari semantiknya, mereka bekerja sama secara
dekat. Keluaran dari bagian ini akan diberikan ke code genereator.
Kode-antara (intermediate code) dibentuk dari sebuah
kalimat x dalam bahasa
context free. Kalimat x ini adalah keluaran dari parser.
Syntax-directed transalation
adalah suatu urutan proses yang mentranslasikan parse
tree menjadi kode-antara. Tahap
pertama dari pembentukan kode antara adalah evaluasi
atribut setiap token dalam
kalimat x. Yang dapat menjadi atribut setiap token adalah
semua informasi yang
disimpan di dalam tabel symbol. Evaluasi dimulai dari parse tree. Kumpulan aturan yang
menetapkan aturanaturan semantik untuk setiap produksinya dinamakan
syntax-directed definition. syntax-directed translation yang mentranslasikan
ekspresi intinya menjadi ekspresi positfinya. Ekspresi intinya ini dapat dilihat sebagai sebuah kalimat
yang dihasilkan oleh parser.
Contoh 1:
Diketahui : 1. kalimat x : 9 - 5 + 2
2. grammar Q = {E . E + T.E - T.T, T . 0.1.3.....9}
3. syntax-directed
definition :
Produksi Aturan Semantik
E . E 1 + T E := E 1 .t ¦ T.t ¦ ‘+ ‘
E . E 1 - T E := E 1 .t¦ T.t ¦ ‘-‘
E . T E := T.t
E . 0 E := ‘0’
E . 1 E := ‘1’
... ...
E . 9 E := ‘9’
catatan : 1. Lambang ‘¦‘ menyatakan concatenation.
2. Mengingat catatan 1, aturan semantik kedua produksi
pertama
adalah concate dua operan diikuti sebuah operator.
Langkah-langkah translasi
1. pembentukan parse
tree : 2. pembentukan annonated parse tree :
E E = 95-2+
E + T E.t = 95- + T.t = 2
E - T 2 E.t = 9 - T.t = 5 2
T 5 T.t = 9 5
9 9
Translation Scheme
Translation scheme
adalah grammar context free dimana sebuah frase yang
disebut semantic
actions disertakan di sisi kanan setiap produksinya. Semantic actions ini
adalah sebuah nilai sebagai hasil evaluasi atribut pada sebuah node. Dalam translation schemes, frase yang menyatakan action
diapit dengan kurung kurawal. . Pada syntax-directed translation hasil akhir
evaluasi atribut ditetapkan pada root dari parse tree melalui kunjungan
dept-first traversal sedangkan pada translation scheme hasil tersebut
ditetapkan pada setiap node (termasuk leaf) juga secara dept-first traversal. Contoh
sebuah translation scheme dengan semantic action-nya adalah :
rest . + term
{print(‘+’)} rest 1 ,
Pada contoh di atas,
aksi {print(‘+’)} akan dilakukan setalah evaluasi terhadap term
selesai dan evaluasi
terhadap rest 1 belum dilakukan. Dalam representasi parse tree,
semantic action pada
translation scheme digambarkan dengan garis putus-putus sebagai
leaf tambahan. Dari
penjelasan di atas terlihat bahwa translation scheme mirip dengan
syntax-directed translation kecuali dalam prosedur evaluasi nilai atribut pada
setiap nodenya. Pada syntax-directed translation hasil akhir evaluasi atribut
ditetapkan pada root dari parse tree melalui kunjungan dept-first traversal
sedangkan pada translation scheme hasil tersebut ditetapkan pada setiap node
(termasuk leaf) juga secara dept-first traversal. Gramar dan kalimat pada contoh 1 di atas mempunyai
translation schemes dan parse tree sebagai berikut
E
E . E + T {print(‘+’)}
E . E - T {print(‘-’)}
E . T E T
T . 0 {print(‘0’)}
E . 1 {print(‘1’)}
E - {print(‘-’)}2 {print(‘2’)}
...
T
E . 9 {print(‘9’)} T
5{print(‘5’)}
9 print(‘9’)}
+ {print(‘+’)}
Syntax Tree
Parse tree seringkali
disebut sebagai concrete syntax tree. Parse tree tidak efisien
karena mengandung informasi yang berlebihan; sebagai
gantinya, kalimat dinyatakan
sebagai abstract
syntax tree atau sering disingkat sebagai syntax tree saja. Dalam syntax
tree setiap operator
maupun keyword tidak muncul sebagai leaf.
contoh :
syntax tree untuk
kalimat x : 9 - 5 + 2 dan y : if B then S 1 else S 2 :
+ if-then-else
- 2
B S 1 S 2
9 5
Membentuk Syntax Tree Sebuah
Ekspresi
Pada pasal ini akan
dibentuk sebuah syntax tree dimana setiap node-nya dinyata-
kan sebagai data record. Setiap record paling tidak
mengandung sebuah label yang dapat berupa identifier, konstanta, atau operator.
Proses pembentukan ini memerlukan tiga buah
function berikut :
1. mknode(op, left,
right) : membentuk node operator dengan label op dan dua field
lainnya berupa pointer ke anak kiri dan anak kanan,
2. mkleaf(id, entry) : membentuk node identifier dengan
label id dan sebuah field berupa pointer ke symbol table. Pelacakan identifier
pada symbol table.
3. mkleaf(num, val) : membentuk node konstanta dengan
label id dan sebuah field yang mengandung nilai bilangan.
Contoh: Diberikan ekspresi : a - 4 + c, dengan a dan c
adalah identifier. Syntax tree akan dibentuk secara bottom-up. Berikut ini
adalah algoritma pembentukan syntax tree untuk ekspresi yang diinginkan beserta
bentuk syntax tree yang dihasilkannya :
(1) p1 := mkleaf(id, entrya); dimana :
(2) p2 := mkleaf(num, 4); -p1, p2, p3, p4, p5 : pointer
ke node
(3) p3 := mknode(‘-‘, p1, p2); -entrya, entryc : pointer
ke symbol table
(4) p4 := mkleaf(id, entryc); masing-masing untuk
identifier a dan c
(5) p5 := mknode(‘+‘,
p3, p4);
+
- id
id num 4 entry untuk
c
entry untuk a
Grammar untuk ekspresi contoh 2 adalah : Q = {E . E + T.E-T.T, T. (E).id.num},
sedangkan syntax directed definition-nya adalah :
Produksi Aturan Semanti
E . E 1 + T E.nptr := mknode(‘+’, E 1 .nptr, T.nptr)
E . E 1 - T E.nptr := mknode(‘-’, E 1 .nptr, T.nptr)
E . T E.nptr := T.nptr
E . (E) T.nptr := E.nptr
E . id T.nptr := mkleaf(id, id.entry)
E . num T.nptr := mkleaf(num, num.val)
pada tabel di atas nptr adalah synthesized attribute,
masing-masing untuk E dan T.
Sebuah atribut di sebuah node adalah synthesized
attribute jika nilai atribut pada node tersebut ditentukan dari nilai-nilai
atribut anak-anaknya.
Three
Address Code
Bentuk umum three address code bagi
sebuah pernyataan adalah : x := y op z,
dimana x, y, z adalah nama atau konstanta, sedangkan op
adalah operator aritmatika atau operator logika. Ekspresi panjang seperti v :=
x + y * z dapat dinyatakan dengan three address code menjadi : t1 := y * z; t2
:= x + t1; v := t2. Terdapat dua format untuk three address
code, yaitu format quadruple (op, arg1, arg2, result) dan format triple (op,
arg1, arg2). Isi dari arg1,
arg2, dan result adalah pointer ke symbol table. Jika isi tersebut adalah temporary
identifier, maka nama tersebut harus dimasukkan ke dalam symbol table begitu
nama tersebut dideklarasikan atau diciptakan.
Contoh:Diberikan
pernyataan : a := b * - c + b * - c.
Rangkaian three address code dari
pernyataan ini adalah :
t1 := - c; t2 := b * t1; t3 := - c; t4
:= b * t3; t5 := t2 := t4; a := t5
Pernyataan quadruple dan triple dari
pernyataan di atas adalah :
Tabel format quadruple Tabel format
truple :
|
NO
|
OP arg1 arg2 result
|
Op arg1 arg2
|
|
0
|
uminus c t1
|
uminus c
|
|
1
|
* b t1 t2
|
* b (0)
|
|
2
|
uminus c t3
|
uminus c
|
|
3
|
* b t3 t4
|
(3) * b (2)
|
|
4
|
+ t2 t4 t5
|
+ (1) (3)
|
|
5
|
:= t5 a
|
:= a (4)
|
Format quadruple untuk opearor unary
seperti ‘- c’ menyebabkan arg2 tidak digunakan.
Format triple digunakan untuk
menghindari penggunaan temporary identifier seperti
yang terjadi pada format quadruple. Format triple ini benar-benar mendayagunakan posisi
baris pernyataan.
Sebagai contoh, pada baris kedua dari tabel format triple terlihat bahwa
isi arg2 adalah
(0), yang tak lain dari ‘uminus c’.
Tidak ada komentar:
Posting Komentar