k17-18 kode intermediate-a

Chapter 17

Pembentukan Kode Intermediate

Kode intermediate:

representasi lanjutan/intermediate dari suatu sumber program.

Jenis representasi intermediate:- pohon sintak - notasi posfik - kode tiga alamat

Kode tiga alamat :

barisan statement-statement yang masing-masing biasanya memuat tiga alamat, dua alamat untuk operand dan satu alamat untuk hasil.

Bentuk umumnya: x := y op z

Kode tiga alamat (cont.)

Bentuk umumnya: x := y op z

dimana x,y dan z adalah nama-nama, konstanta atau nama sementara yang dibentuk oleh compiler. op adalah sembarang operator seperti operator aritmetika atau logikal.

Kode tiga alamat (cont.)

Contoh : a := b * -c + b * -c, kode tiga alamatnya sbb:t1 := -c

t2 := b * t1

t3 := -c

t4 := b * t3

t5 := t2 + t4

a := t5

Jenis-jenis statement tiga alamat

Statement tiga alamat: sejenis kode asembel. Bisa terdiri dari label simbol dan statement flow of control (if, while, dsb).

Label simbol merepresentasikan indeks dari statement tiga alamat dalam suatu array yang menyimpan kode intermediate.

Jenis-jenis statement tiga alamat

x := y op z, dimana op adalah operator biner. x := op y, dimana op adalah operator unari. x := y goto L, lompatan tak bersyarat. if x relop y goto L, lompatan bersyarat. param x dan call p,n untuk pemanggilan

prosedur dan juga return y. statement berindeks x := y[i] dan x[i] := y. x := &y, x := *y, *x := y.

Jenis-jenis statement tiga alamat (cont.)

Pembentukan kode tiga alamat didefinisikan dalam bentuk Definisi berdasarkan sintaks atau Skema Translasi.

Dalam prosesnya, nama sementara dibuatkan untuk setiap node interior di dalam pohon sintaksnya.

Jenis-jenis statement tiga alamat (cont.)

Dalam pembentukan kode tiga alamat untuk ekspresi: E.place merupakan nama yang akan

menyimpan nilai dari E. E.code merupakan barisan statement

tiga alamat untuk mengevaluasi E. Newtemp memberikan sebarisan nama-

nama yang berbeda.

Produksi Aturan Semantik

S id := E S.code := E.code || gen(id.place ':=' E.place)

E E1 + E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place

':=' E1.place '+' E2.place)

E E1 * E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place

':=' E1.place '*' E2.place)

Produksi Aturan Semantik (cont.)

E - E1 E.place := newtemp; E.code := E1.code || gen(E.place ':=' 'uminus'

E1.place)

E (E1) E.place := E1.place;

E.code := E1.code

E id E.place := id.place; E.code := ' '

Produksi Aturan Semantik (cont.)

S while E do S1 S.begin := newlabel; S.after := newlabel; S.code := gen(S.begin ':') || E.code ||

gen('if' E.place '=' '0' 'goto' S.after) || S1.code ||

gen('goto' S.begin) || gen(S.after ':')

Implementasi statement tiga alamat

Implementasi statement tiga alamat dilakukan dalam bentuk record- record dengan field-field untuk operator dan operand. Quadruples Tripels Tripels tidak langsung

Quadrupels

Struktur record dengan empat field untuk op, arg1, arg2, dan result. op memuat kode untuk op. x := y op z, y di arg1, z di arg2, x di result. x := x := -y atau x := y tidak memakai arg2. param tidak memakai arg2 atau result. label target dari lompatan bersyarat ataupun

tidak ditempatkan pada result. isi pada arg1, arg2, dan result biasanya pointer

ke tabel simbol.

Quadrupels (cont.)

Contoh: z := b * -c + b * -c

Op Arg1 Arg2 Result

(0) uminus c t1

(1) * b t1 t2

(2) uminus c t3

(3) * b t3 t4

(4) + t2 t4 t5

(5) := t5 a

Tripels

Memakai 3 field, tidak memakai field result op, arg1, arg2. arg1 dan arg2 bisa berupa pointer ke tabel simbol (untuk nama atau konstan) atau pointer ke struktur tripel (untuk nilai sementara).

Tripels (cont.)

Contoh :

op Arg1 Arg2

(0) uminus c

(1) * b (0)

(2) uminus c

(3) * b (2)

(4) + (1) (3)

(5) assign a (4)

Tripels tidak langsung

Memakai list yang terdiri dari pointer yang menunjuk pada tripel [array statement].

Statement

(0) (14)

(1) (15)

(2) (16)

(3) (17)

(4) (18)

(5) (19)

Op Arg1 Arg2

(14) uminus c

(15) * b (14)

(16) Uminus c

(17) * b (16)

(18) + (15) (17)

(19) assign a (18)

Kebaikan vs. Keburukan

Quadrupel Lokasi tempat sementara dapat diakses

secara langsung melalui tabel simbol. Statement-statement dengan mudah

dapat dipindahpindahkan lokasinya, menguntungkan optimisasi compiler.

Butuh space lebih banyak.

Kebaikan vs. Keburukan

Tripel Semua acuan (referensi) terhadap

statement harus diubah, jika statement-statement dipindah-pindah untuk optimisasi sulit untuk dioptimisasi.

Space, lebih sedikit dibanding quadrupel.

Kebaikan vs. Keburukan

Tripel tidak langsung (TTL) Mirip seperti quadrupel Pemindahan statement dilakukan

dengan merubah susunan list statement.

Jika nama sementara dipakai berulang-ulang, TTL ini sangat menghemat space.

Deklarasi

Dalam prosedur yang tidak nested. Offset :

dipakai untuk memonitor address relatif

setiap deklarasi suatu id baru dilakukan, offset ditambah dengan 'panjang' type id tersebut.

Deklarasi

Enter(name,type,offset)} : membuat entri tabel simbol dengan nama

'name', memberikan 'type'nya dan juga 'offset'nya.

P = , {offset := 0} D

D P ; D D id : T {enter(id.name, T.type, offset);}

offset := offset + T.widthT integer {T.type := integer; T.width := 4}T real {T.type := real; T.width := 8}

Prosedur nested

1 tabel simbol utk 1 prosedur Aturan semantik:

mktable(previous): membentuk tabel simbol baru dan mengembalikan suatu pointer yang menunjuk pada tabel baru.previous :

menunjuk pada tabel simbol sebelumnya (milik prosedur pengurungnya).

ditempatkan pada header dalam tabel simbol yang baru.

Prosedur nested (cont.)

enter(table,name,type,offset) : membentuk entri baru untuk name pada tabel simbol table. Juga disimpan type dan offset milik name.

addwidth(table,width)} : mencatat panjang (besar) kumulatif dari semua entri di dalam tabel pada headernya.

enterproc(table,name,newtable)} : membentuk entri baru untuk prosedur name pada tabel simbol table. Newtable menunjuk pada tabel simbol untuk prosedur name.

Prosedur nested (cont.)

Prosedur nested (cont.)

Contoh : program sort; a : integer; x : integer; proc readarray;

i : integer; proc exchange; proc quicksort;

k : …..v : ….. proc partition;

i : ….. j : …..

Chapter 18

Pembentukan Kode Intermediate(lanjutan)

Ekspresi boolean

E E or E | E and E | not E | (E) | id relop id | true | false

relop <, >, ≤, =, ≠, ≥ Asumsi :

or dan and asosiatif kiri or presedensinya lebih rendah dari and,

lalu not.

Representasi boolean:

True := 1, false := 0 Nilai ekspresi boolean berupa posisi

yang dicapai dalam program misalE1 or E2,

maka jika E1 true, sisa ekspresi tidak perlu dievaluasi optimisasi compiler.

Representasi boolean (cont.):

Contoh: a or b and not ct1 := not ct2 := b and t1 t3 := a or t2

Sedangkan ‘a < b’ ekivalen dengan if a < b then 1 else 0. Hal ini bisa ditulis dalam kode tiga alamat berikut (misal dimulai pada statement 100) : 100: if a < b goto 103 101: t := 0 102: goto 104 103: t := 1 104:

Representasi boolean (cont.):

Contoh lalu dibuat berdasarkan skema translasi berikut dimana:emit - mencetak statement tiga alamat

pada file output lalu menaikkan 'nextstat'.

nextstat - adalah indek dari statement tiga alamat berikutnya didalam output.

newtemp - memberikan nama sementara yang baru.

Representasi boolean (cont.):

E E1 or E2

{E.place := newtemp; emit(E.place ':=' E1.place 'or' E2.place)}

E E1 and E2 {E.place := newtemp;

emit(E.place ':=' E1.place 'and‘ E2.place)}

E not E1 {E.place := newtemp;

emit(E.place ':=' 'not' E1.place)}

Representasi boolean (cont.):

E ( E1 ){E.place := E1.place}

E id1 relop id2

{E.place := newtemp;emit('if' id1.place relop.op id2.place 'goto‘

nextstat+3);emit(E.place ':=' '0')emit('goto' nextstat+2)emit(E.place ':=' '1')}

Representasi boolean (cont.):

E true {E.place := newtemp;

emit(E.place ':=' '1')}

E false {E.place := newtemp;

emit(E.place ':=' '0')}

a < b or c < d and e < f Translasinya sbb:

100 if a < b goto 103 107 t2 := 1

101 t1 := 0 108 if e < f goto 111

102 goto 104 109 t3 := 0

103 t1 := 1 110 goto 112

104 if c < d goto 107 111 t3 := 1

105 t2 := 0 112 t4 := t2 and t3

106 goto 108 113 t5 := t1 or t4

Statement flow of control

Dengan grammar :S if E then S1 |

if E then S1 else S2 | while E do S

Untuk semua E: E.true adalah label yang akan dituju jika E

adalah true. E.false adalah label yang akan dituju jika e

adalah false.

Statement flow of control (cont.)

Contoh: a < b or c < d and e < fMisalkan label Ltrue dan Lfalse sudah dibuat, Ltrue label yang akan dituju jika ekspresi benar, Lfalse label yang akan dituju jika ekspresi salah.

if a < b goto Ltruegoto L1 redundant

L1: if c < d goto L2

goto Lfalse

L2: if e < f goto Ltrue

goto Lfalse

Statement flow of control (cont.)

Redundant dapat dihilangkan dengan: Optimisasi peephole Merubah bentuk ekspresi, misal

id1 < id2 menjadi if id1 ≥ id2 goto E.false.

Contoh: while a < b do

if c < d thenx := y + z

else x := y + z

Statement flow of control (cont.)

Case statement/switch

hampir mirip/bentuk umum dari if-then-else switch E

begincase V1 : S1

case V2 : S2

.

.

.case V(n-1) : S(n-1)

default : Sn

end

Case statement/switch

Pada saat switch terbaca: buat label 'test' dan 'next' buat nama sementara 't' buat kode E, evaluasi E, simpan di t goto test

Saat case terbaca: buat label Li masukkan ke tabel simbol

pointer ke entri tabel simbol itu dan nilai Vi disimpan pada stack. (untuk mengatasi switch di dalamnya).

Dua versi statement 3-alamat switch:

Dua versi statement 3-alamat switch:

Backpatching :

proses pemberian nilai pada label, dilakukan setelah nilai ini diketahui.

Untuk memudahkan, implementasinya mamakai quadrupels, yang berbentuk array of record. Label merupakan indek array.

Backpatching : (cont.)

Fungsi-fungsi yang dipakai: makelist(i), membuat list baru yang hanya

memuat indek/label i, lalu menghasilkan pointer yang menunjuk pada list itu.

merge(p1, p2), menggabung list yang ditunjuk oleh p1 dan p2 , menghasilkan pointer yang menunjuk pada gabungan list ini.

backpatch(p,i), memasukkan i sebagai label untuk masing-masing statement pada list yang ditunjuk oleh p.

Backpatching : (cont.)

Atribut tersintesa truelist dan falselist dipakai untuk membentuk kode lompatan ekspresi boolean.

M.quad : mencatat angka/indek statement pertama pada E2.

Contoh: a < b or c < d and e < f Produksi E a < b membentuk:

100 : if a < b goto ...101 : goto ...

Backpatching : (cont.)

M pada E E1 or M E2 sudah terlihat, M mencatat nextquad sebagai 102.E c < d membentuk

102: if c < d goto ...103: goto ...

M pada E E1 and M E2 sudah terlihat, M mencatat nextquad sebagai 104.E e < f membentuk

104: if e < f goto ...105: goto ...

Backpatching : (cont.)

E1 E1 and M E2 melakukan backpatch({102}, 104). Ini mengakibatkan:

100: if a < b goto ...101: goto ...102: if c < d goto 104 103: goto ...104: if c < f goto ...105: goto ...