sungmin

INTERMEDIATE CODE

Pembentukan intermediate code(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

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.

tahap 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.

§  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.

§  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’.

Analisis Semantik

Seperti yang kita ketahui bahwa semantik merupakan kata yang mempunyai banyak makna, baik dalam suatu bahasa maupun dalam kode pemograman.
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.
            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.
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

a)      Jenis operasi yang dilakukan dalam tabel simbol adalah

o   Operasi insert (append/add)

o   Operasi search (dengan hashing)

o   Operasi delete

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

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

d)       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
 Pada umumnya elemen-elemen tabel simbol:

·           No urut identifier (ID unik / auto increment)

·           Nama identifier: berisi nama-nama variabel, prosedure, fungsi, dan lain-lain yang akan   digunakan untuk referensi pada analisis semantik, intermediate code, dan code generation.

·           Tipe identifier: berisi keterangan tipe identifier.

·           Object Time Address: berisi address yang mengacu pada alamat tertentu di memori

·           Dimensi (ukuran) dari identifier yang bersangkutan

·            Nomor baris variabel yang dideklarasikan

·           Field link (opsional)

Jenis Tabel Simbol

Beberapa jenis Tabel Simbol:

Ø  Tabel identifier: berisi daftar identifier

Ø  Tabel array: berisi informasi tambahan untuk array

Ø   Tabel blok: berisi variabel-variabel dalam lingkup blok yang sama (lokal)

Ø   Tabel real: berisi elemen tabel bernilai real

Ø  Tabel string: berisi informasi string

Ø   Tabel display: berisi blok yang aktif

Ø  Tabel integer: berisi informasi elemen bernilai integer

Tabel Simbol Identifier

§    No urut identifier

§   Nama identifier

§  Jenis identifier : prosedur, fungsi, tipe, variabel, konstanta

§  Tipe identifier: integer, real, char, boolean, string, record

§   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.

§   Pada identifier, perlu dicatat juga:

§   Alamat dari identifier

§   Informasi acuan identifier ke tabel identifier lain yang menerangkannya

§  Link: menghubungkan identifier ke identifier lainnya, atau yang dideklarasikan pada level yang sama

§   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

§  No urut array dalam tabel

§  Tipe dari indeks array yang bersangkutan

§  Tipe elemen array

§   Alamat Referensi dari elemen array

§   Indeks batas atas dan bawah array

§  Jumlah elemen array

§   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

§   No urut blok

§  Batas awal blok

§  Batas akhir blok

§  Ukuran parameter

§   Ukuran variabel

§   Last variabel

§   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:

§  Berfungsi mencatat blok yang sedang aktif

§  No urut

§  Blok yang sedang aktif

§  Pengisiannya menggunakan konsep stack

Urutan Pemrosesan

§  Urutan pengaksesan: Tabel Dsiplay –Tabel Blok –Tabel Simbol

§  Pertama, tabel display akan mengetahui mana bagian yang aktif, maka akan diketahui identifier-identier yang aktif dalam blok tersebut.

§   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 akanv 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.

ADAPUN ILMU SEMANTIK OPERASIONAL
Inti denotasional Ilmu Semantik adalah terjemahan dari program konvensional ke dalam persamaan fungsional.
Tujuan Denotasional Semantik dari suatu bahasa adalah Menugaskan suatu nilai kepada setiap ekspresi dalam bahasa.
Ilmu semantik dapat dinyatakan dalam lambda calculus sebagai fungsi matematical, Eval, dari ekspresi ke nilai.

Teknik-teknik pendeskripsian Semantik bahasa pemrograman

a)       Operational Semantic
Pendekatan ini mendefinisikan suatu mesin buatan (abstract) dengan instruksi-intruksi promitif, tidak perlu realistik, tetapi cukup sederhana supaya tidak muncul kesalahpahaman. Deskripsi semantik dari bahasa pemrograman menentukan suatu trasnlasi ke kode.

b)      Denotational Semantic
Pada pendekatan ini, diberikan suatu fungsi yang memetakan program-program komputer yang ditunjuk kedalam bentuk nilai-nilai abstrak secara matematika (angka, nilai, kebenaran, fungsi matematika).

c)       Axiomatic Semantic
Pendekatan ini mendefinisikan suatu tindakan program yang dibangun dengan properti logika yang menyimpan status komputer sebelum dan sesudah eksekusi.

d)      Algebraic Semantic
Pendekatan ini dipertimbangkan suatu objek komputasi yang menjadi syarat-syarat dalam aljabar multi-sorted. Program mengimplementasikan fungsi yang dapat diwujudkan dengan suatu persamaan diantara syarat-syarat tersebut.

e)      Structured Operational atau Natural Semantic
Seperti dalam pengambilan keputusan secara alamiah dengan logika. Program diberi suatu arti dari aturan yang diturunkan yang menggambarkan penilaian gagasan suatu bahasa.

TUGAS DARI ANALISA SEMANTIK:

 Pohon sintaks yang dihasilkan  digunakan untuk semantics analiyser yang bertugas untuk menentukan ‘maksud’ dari program sumber, misalnya operator penjumlahan maka semantics analiyser akan mengambil aksi apa yang harus dilakukan.
 Terdapat statement: (A+B) * (C+D)
 Akan menghasilkan bentuk sintaksis dan Melakukan pengecekan pada struktur akhir yang telah diperoleh  dan diperiksa kesesuainnya dengan komponen program yang ada.
 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.
 Berperan dalam memeriksa kesalahan-kesalahan yang bersifat semantik. Salah satu peranan analisis semantik yang penting adalah pemeriksaan tipe variabel.
 Memeriksa keunikan suatu nama.
 Menganalisis kebenaransource program.

Pembangkitan Kode-Antara

Setelah melihat desain dari perser, tabel simbol dan strategi organisasi penyimpanan, di bab ini kita akan mempelajari teknik pembangkitan kode.Ketika kompiler mengkompile program dengan bahasa tingkat tinggi.Hal ini menghasilkan kode mesin yang ditujukan untuk beberapa prosesor.Walaupun demikian,banyak waktu digunakan untukmendesain kompiler untuk menghasilkan keluaran-antara (intermediate output) yang merepresentasikan masukan program di beberapa bahasa hypothhetical/Struktur data.Misalnya representasi yang kita ketahuisebagai kode-antara untuk menandai bahwa kode tersebut merepresentasikanantara bahasa sumber dengan program bahasa mesin yang dituju.Kode-antara menawarkan diri sebagai media kegunaan untukmembandingkan dengan pembangkitan kode secara langsung. Sebagaimana yang disebutkan dibawah ini

§  Kode-antara lebih dekat dengan mesin yang dituju/yanng ditargertkan daripada bahasa sumber.Oleh karena itu, kode-antara lebih mudah untukdigunakan sebagai pembangkitan kode.

§  Tidak seperti bahasa mesin,kode-antara dapat dikatakan kurang lebih sama denganmesin independen.Hal ini lemembuat kita lebih mudah untukpenargetan ulang kompiler untuk berbagai jenis prosesor target yang berbeda.

§  Mengizinkan berbagai macam proses optimasi berjalan di ata modelmesin independen.

§  Secara khusus, pembentukan kode-antara dapat diimplementasikan lewat sintax-directed translation ,hal ini berarti sejalan dengan parser yang dilakukan denagn berbagai jenis reduksi dan jadi dapat dibungkus denagn proses parsingdenagn cara pemberian argumen pada parser.

 Bahasa-antara

Teknik reperesentasi dalam bahasa-antara dapat dikategorikan menjadi 2 kategori:

a)      representasi-antara tingkat tinggi

b)       representasi-antara tingkat rendah.

Representasi-antara tingkat tinggimenggambarkan struktur tingkat tinggi dari sebuah program.Contoh dari kategori ini adalah pohon sintaks yang dihasilkan oleh parser.berikut ini fitur fitur pentingdari representasi ini:

a)      Lebih dekat dengan bahasa progra sehingga menjaga struktur program.

b)      lebih mudah membangkitkan dari masukan program.

c)      Walaupun begitu,proses optimasi kodetidak dapat secara langsung dilakukan, hal ini karena masukan program tidak dimungkinkanuntuk memperoleh tingkat pembagian kode dan proses optimasi lebih baik.

Di kategotri lain representasi tingkat rendah,sebaliknya menggambarka struktur tingkat rendah sebuah program.Fitur yang penting dari representasi ini adalah ebagai berikut:

1.      Lebih dekat dengan mesin yang dituju.Contonya RTLyang digunakan dalam GCC dan pengkodean tiga-alamat, yang akan kita diskusikan nanti.

2.      Lebih mudah membangkitakan kode terakhir dari representasi ini.

3.      Walaupun begitu, pembangkitan dari representasi ini dari masukan program memerlukan banyak usaha.Kita akan mendiskusikannya di bagian lain dari bab ini.

 Penerbitan Desain Bahasa-antara

Tiap desain bahasa memiliki memiliki tujuan tertentu berkorespondensi dengan fitur fitur yang dibutuhkan untuk direpresentasikan Contohnya baha tingkat tinggi mencoba untuk mengandung kekuatan ekspresi.sehingga keperluan perhitungan pengguna dapat secara singkat dan efisien. Semantara itu pendesain bahasa assembyberkorespondensi pada hardware yang tersedia dan peta instruksipada operasi di atas beralaskan hardware.Sama seperti hal tersebut, bahasa-antara memikiki sebuah desain yang menegaskan sebagai jembatan antara bahasa-antara dan bahasa target.Hal hal dibawah ini adalah beberapa poin yang menyolok mengenai bahasa-antara.

§  Perangkat operator di bahasa-antara harus cukupkaya untuk mnengizinkan    bahasa sumber agar dapat diimplementasikan.

§  Perangkat kecil operasidi bahasa-antara membuatkemudahan untuk penargetan ulang.

§  Operasi kode-antara lebih dekat disewa bagi mesin khusus/ arsitektur ,sehingga lebih sulit dengan port.

§  Perangkat kecil kode-antara mungkin memimpin untuk beberapa konstruksi   bahasa-antara.Penerapan ini lebih bekerja pada saat proses optimasi.