Intermediate Code Generation

Diposting oleh Yudi Herdiana 20.57

Dalam model analisis-sintesis dari suatu kompiler, bagian depan menerjemahkan source program ke dalam suatu intermediate representation di mana bagian belakan akan meng-generate target code.

Detail dari target language diketahui dari bagian belakang. Walaupun source program dapat diterjemahkan langsung ke dalam target language, keuntungan yang didapat dari penggunaan machine-independent intermediate form adalah:

Retargeting sangat dimungkinkan, yaitu suatu kompiler untuk mesin yang berlainan dapat dibuat dengan menempelkan bagian belakang mesin baru tersebut dengan bagian depan yang telah ada lebih dulu.
Machine-Independent Code Optimizer dapat diterapkan dalam Intermediate Representation.

Posisi dari Intermediate Code Generator dalam kompiler adalah sebagai berikut: Untitled Diagram

Implementasi Three-Address Statement

Three-Address Statement adalah bentuk abstrak dari Intermediate Code. Dalam kompiler, statement ini dapat diimplementasikan sebagai record yang field-fieldnya berupa operator dan operand.

Ada 3 macam representation, yaitu quadruple, triple dan indirect triple.

Quadruple

Quadruple adalah record dengan 4 field yang disebut OP, arg1, arg2 dan result,

OP field berisi internal code untuk operator

Three-address statement x:=y op z direpresentasikan dengan menempatkan y dalam arg1, z dalam arg2, dan x dalam result.

Statement dengan unary operator seperti x:= -y atau x:=y tidak menggunakan arg2.

Contoh quadruple untuk statement:

a:=b*-c+b*-c

adalah:

	OP	arg1	arg2	result
(0)	uminus	c		t1
(1)	*	b	t1	t2
(2)	uminus	c		t3
(3)	*	b	t3	t4
(4)	+	t2	t4	ts
(5)	:=	ts		a

Untuk menghindari memasukkan temporary name ke r dalam symbol table, kita bisa merefer ke temporary value dari posisi statment yang menghitungnya. Dengan demikian three-address statement dapat direpresentasikan dengan record yang mempunyai 3 field, yaitu OP, arg1, dan arg2.

Field arg1 dan arg2 untuk argumen OP bisa berupa pointer ke symbol table atau pointer ke triple structure.

Karena menggunakan 3 field, maka format intermediate code ini disebut Triple.

Contoh:

a:=b*-c+b*-c

adalah:

	OP	arg1	arg2
(0)	uminus	c
(1)	*	b	(0)
(2)	uminus	c
(3)	*	b	(2)
(4)	+	(1)	(3)
(5)	assign	a	(4)

Indirect Triple

Sama dengan triple tetapi di sini menggunakan pointer yang menunjuk kepada suatu alamat tertentu.

Merupakan pengembangan dengan menambahkan tabel indeks. Contoh, dari triple, dengan menambahkan tabel indeks:

	index	OP	arg1	arg2
(0)	0	uminus	c
(1)	1	*	b	(0)
(2)	2	uminus *	c
(3)	3	+ assign	b	(2)
(4)	4		(1)	(3)
(5)	5		a	(4)

Deklarasi

Beberapa informasi mengenai suatu deklarasi yang disimpan di dalam symbol table:

1. Jenis data
2. Alamat penyimpanan data

Alamat penyimpanan ditunjukkan dengan offset dari suatu basis untuk menyimpan data static.

P→D {offset=0}

D→D;D

D→id;T {enter (id.name, T.type, offset};offset:=offset+T.width}

T→integer {T.type:=integer;T.width:=4}

T→real {T.type:=real;T.width:=8}

T→array[num] of T1 {T.type=array(num.val, T.type):T.width=num.val x T1.width}

T→^T1 {T.type:=pointer(T1.type);T.width:=4

3. Deklarasi suatu record

P→MD {addwidth(top(tblptr),top(offset));pop(tblptr); pop(offset)}

M→ε {t:=mktable(nil); push (t.tblptr); push (0, offset)}

D→D1,D2

D→proc Id; N D1; S {t:=top (tblptr);addwidth(t, top(offset));pop(tblptr), pop(offset);
enterproc(top(tblprt), Id name, t)}

D→Id : T {enter(top(tblptr), Id.name,
T.type,top(offset);top(offset):=top(offset)+T.width}

N→ε {t:=mktable(top(tblptr));push(t.tblptr);push(0,offset)}

Di dalam record dimungkinkan deklarasi beberapa field.

⇒Perhitungan alamat/offset mengikuti metode deklarasi yang biasa.

1. Assignment

Nama yang digunakan di dalam three address code merupakan pointer menuju symbol table. Translation scema untuk assignment.

S→ id:=E {p:=lookup(id.name); If p ≠ ^ nil then emit (p':='E.prace) else error}

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

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

E1→-E1 {E.place:=newtemp;emit(E.place':=' unimus' E1.place)}

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

E→id {p:=lookup(Id.name): if p ≠ nil then E.place:=p else error}

NewTemp digunakan ketika kompiler memerlukan suatu variabel temporary untuk optimasi program.

Contoh:

Statement X:=a*b+c*d-e*f
maka three address code beserta stack temporary:

STATEMENT		VALUE OF C
		0
$0	:=a*b	1
$1	:=c*d	2
$2	:=$0+$1	1
$1	:=e*f	2
$0	:=$0-$1	1
x	:=$0	0

2. Ekspresi boolean

Translasi boolean secara numerik
1 translasi dari true
0 translasi dari false

Contoh:

a or b and not c

maka three-address code:

t1=not c
t2=b and t1
t3=a or t1

ekspresi a < b akan ditranslasikan dalam

100:if a<b goto 103
101:t:=0
102:goto 104
103:t:=1
104:

Translation schema ekspresi boolean.

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

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

E1→ not E1 {E.place:=newtemp;emit(E.place':=' not' E1.place)}

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')}

E→ true {E.place ;+newtemp;emit (E.place ':=' '1')}

E→ false {E.place ;+newtemp;emit (E.place ':=' '0')}