Buku Teknik Kompilasi

disusun oleh :

AGUS MAKMUR MANURUNG

BAB I

A.Teknik Kompilasi

Merupakan Teknik dalam melakukan pembacaan suatu program yang ditulis dalam bahasa sumber, kemudian diterjemahkan ke dalam suatu bahasa lain yang disebut bahasa sasaran. Dalam melakukan proses penerjemahan tersebut, sudah barang tentu kompilator akan melaporkan adanya keanehan-keanehan atau kesalahan yang mungkin ditemukannya. Proses penerjemahan yang dilakukan oleh kompilator ini disebut proses kompilasi (compiling).Bila dipandang sepintas lalu, maka akan timbul beranekaragam kompilator yang dapat dibuat,

- Bahasa Sumber seperti bahasa FORTRAN, PASCAL, C dan juga bahasa-bahasa lainnya yang sifat dan pemakaiannya agak spesifik atau khusus, seperti bahasa untuk program DBASE, SPSS dan lain sebagainya.

- Bahasa Sasaran dapat berupa bahasa sumber lain seperti C, FORTRAN dan lain sebagainya atau Bahasa Mesin (Machine Language) yang digunakan oleh suatu prosessor mikro atau sumber komputer besar maupun komputer super.

Sejarah perkembangan suatu kompilator sudah dimulai sejak lama, yaitu pada saat mulai ditemukannya computer pada awal 1950-an. Sejak waktu tersebut teknik dan cara pembentukan suatu kompilator telah berkembang dengan sangat pesat dan pembentukkan suatu kompilator dapat dilakukan makin mudah.Demikian pula program bantu (tools) untuk membuat suatu kompilator sudah dapat diperoleh sehingga pembentukan suatu kompilator dapat dilakukan dengan cepat. Kompilator pertama yang dibuat adalah kompilator untuk bahasa FORTRAN yang pada saat itu dikembangkan dengan memakan sejumlah tenaga ahli yang setara dengan pekerjaan yang dilakukan oleh 18 orang.

Dengan adanya program bantu dan tata cara pembentukan yang sistematis dan tertata dengan baik serta pendefinisian struktur bahasa yang cermat, maka suatu kompilator untuk bahasa yang terstruktur seperti PASCAL atau C dapat dikembangkan.Proses kompilasi dari suatu kompilator pada dasarnya dapat dibagi ke dalam 2 bagian utama yaitu bagian analisis dan bagian sintesis. 

- Tahap analisis program yang ditulis dalam bahasa sumber dibagi dan dipecah ke dalam beberapa bagian yang kemudian akan dipresentasikan ke dalam suatu bentuk antara dari program sumber. Operasi-operasi yang dilakukan oleh program sumber ditentukan dan dicatat dalam suatu struktur pohon (tree) yang disebut dengan nama pohon sintaks (sintax tree) Dalam hal ini setiap nodal pada tree tersebut menyatakan suatu operasi, sedangkan anak dari nodal (titik) tersebut memberikan argument yang diperlukan Secara umum proses dalam tahap analis terdiri dari 3 bagian utama, yaitu

a.Proses analisis leksikal

b.Proses analisis sintaktik

c.Proses analisis semantik 

- Tahap sintesis yang berikutnya program sasaran dibentuk berdasarkan representasi antara yang dihasilkan pada tahap analisis.Untuk tahap sintetis terdiri dari 2 bagian utama, yaitu

a.Proses yang menghasilkan kode (code generator)

b.Proses optimasi kode (code optimizer) 

Sebelum Bahasa sasaran dapat dihasilkan, dalam melakukan ini tiap bagian utama akan berhubungan dan berkomunikasi dengan suatu berkas tabel yang disebut tabel simbol (symbol table) yaitu suatu tabel yang berisi semua simbol yang digunakan dalam bahasa sumber.Selain kompilator masih diperlukan beberapa program lainnya sebelum dapat dibentuk bahasa sasaran yang dapat dijalankan. Seperti suatu bahasa sumber dapat dituliskan dalam beberapa modul yang terpisah dan disimpan dalam beberapa file yang terpisah.Untuk menanggulangi hal ini, maka suatu program khusus yang disebut dengan suatu praprosesor digunakan untuk mengumpulkan modul-modul yang saling lepas ini ke dalam suatu program baru. Praposesor dapat pula melengkapi singkatan-singkatan atau ungkapan-ungkapan maupun kependekan-kependekan yang digunakan dalam bahasa sumber seperti pendefinisian makro dan lain sebagainya.

BAB II

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

I. 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 keparser 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 mempunyaiarti) 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.

B.Tugas-tugas Analisis leksikal 

1.Konversi Program Sumber Menjadi Barisan Token Mengubah program sumber yang dipandang sebagai barisan byte/karaktermenjadi 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.

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

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

E. 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 alternative 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.

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

BAB III

A. Teknik Optimasi

Teknik Optimasi ada tiga yaitu;

1.Dependensi Optimasi.

2.Optimasi Lokal.

3.Optimasi Global.

Berikut penjelasannya

· Dependensi optimasi bertujuan untuk menghasilkan kode program yang berukuran lebih kecil dan lebih cepat.

· Optimasi lokal adalah optimasi yang dilakukan hanya pada bagian blok tertentu dari source code.di dalam optimasi lokal terdapat lima(5) cara pengomptimasiannya.

a. Folding yaitu mengganti konstanta atau ekspresi yang bisa dievaluasi pada saat compile time dengan nilai komputasinya. misalnya : A = 5+4+B bisa di ganti dengan A=9+B karena 9 dapat menggantikan ekspresi 5+4.

b. Redundant-Subexpression Elimination : hasilnya digunakan lagi dari pada dilakukan komputasi ulang, contohnya;

A=B+C

X=Y+B+C

dapat diganti dengan 

A=B+C

X=Y+A (karena isi dari A sudah bias mengganti B+C).

c. Loop Unrolling : mengganti suatu loop dengan menulis statement yang ada di dalam loop ditulis beberapa kali, contoh:

For i=1 to 2 do

A[i]=0;

dapat diganti dengan

A[1]=0;

A[2]=0;

d. Frequency Reduction : pemindahan statement ke tempat yang lebih jarang dieksekusi. contoh

for i=1 to 10 do

begin

X=5

A=A+1

end

karena X itu diisi dengan nilai yang tetap yaitu 5 maka bisa dipindahkan menjadi

x=5

for i=1 to 10 do

begin

A=A+1 

end

e.Strength Reduction : penggantian suatu operasi dengan operasi lain yang lebih cepat dieksekusi, contoh

A=A+1

dapat diganti dengan 

INC(A)

· Optimasi Global : dilakukan dengan suatu graph terarah yang menunjukan jalur yang mungkin selama eksekusi program. ada 2 kegunaan optimasi global yaitu bagi programer dan juga bagi copiler itu sendiri.

Ø bagi programer

a. Unreachable/dead code : kode yang tidak pernah dieksekusi contoh

x=5

if x=0 then

A=A+1

intruksi A=A+1 tidak pernah dikerjakan karena kondisi x tidak pernah menjadi 0

b. Unused parameter : parameter yang tidak pernah digunakan dalam procedure. contoh

procedure penjumlahan (a,b,c :integer)

var x:integer;

begin

x=a+b; 

end;

parameter c tidak pernah dugunakan sehingga tidak perlu diikut sertakan pada procedure

c. Unused variable : variable yang tidak pernah dipergunakan. contoh

var a,b : integer;

begin

a=5 

end

variable b tidak pernah dipergunakan dalam manipulasi sehingga tidak perlu dideklarasikan.

d Variable : variable yang dipakai tanpa nilai awal. contoh

var a,b : integer

begin

a=5

a=a+b

end

variable b di pergunakan tetapi tidak memiliki harga awal

Ø bagi compiler

a. meningkatkan efisiensi eksekusi program

b. menghilangkan useless code/kode yang tidak terpakai.

BAB IV

A. Analisis Semantik

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. 

Contoh : A := (A + B)*(C + D)

maka penganalisis semantik harus mampu menentukan aksi apa yang akan dilakukan oleh operator-operator tersebut. Dalam sebuah proses kompilasi, andaikata parser menjumpai ekspresi seperti diatas, parser hanya akan mengenali simbol-simbol ':=' , '+' , dan '*'. Parser tidak tahu makna apa yang tersimpan dibalik simbol simbol tersebut. Untuk mengenalinya, kompiler akan memanggil rutin semantik yang akan memeriksa :

l Apakah variabel-variabel yang ada telah didefinisikan sebelumnya?

l Apakah variabel-variabel tersebut tipenya sama?

l Apakah operand yang akan dioperasikan tersebut ada nilainya?, dan seterusnya.

Fungsi ini terkait dengan tabel simbol. Pengecekan yang dilakukan oleh analisis semantik adalah sebagai berikut :

a) Memeriksa keberlakuan nama-nama meliputi pemeriksaan berikut. 

 Duplikasi : pada tahap ini dilakukan pengecekan apakah sebuah nama terjadi pendefinisian lebih dari dua kali. Pengecekan dilakukan pada bagian pengelola blok.

 Terdefinisi : Melakukan pengecekan apakah sebuah nama yang dipakai pada tubuh program sudah terdefinisi atau belum. Pengecekan dilakukan pada semua tempat kecuali blok.

b) Memeriksa tipe. Melakukan pemeriksaan terhadap kesesuaian tipe dalam statement-statement yang ada. Misalkan bila terdapat suatu operasi, diperiksa tipe operand. Contohnya bila ekspresi yang mengikuti instruksi IF berarti tipenya boolean, akan diperiksa tipe identifier dan tipe ekspresi. Bila ada operasi antara dua operand, maka tipe operand pertama harus bisa dioperasikan dengan operand kedua.

Analisa semantik sering juga digabungkan pada pembangkitan kode antara yang menghasilkan Output intermediate code, yang nantinya akan digunakan pada proses kompilasi berikutnya.

B. 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. Sebelum akhirnya kode eksekusi benar-benar dihasilkan.

C. Code Generation

Code Generator/Pembentukan Kode. Dimana dalam tahap ini dibentuk antara dari bahasa sumber yang berupa suatu pohon sintaks diterjemahkan ke dalam suatu bahasa assembler atau bahasa mesin.

Bentuk antara yang diperoleh biasanya merupakan suatu perintah 3 alamat atau suatu kuadrupel (3-address code atau quadruples), sedangkan bahasa mesin yang dihasilkan adalah suatu bahasa assembler yang merupakan suatu perintah 1 alamat, 1 akumulator.

D. Code Optimizer

Code Optimizer/Optimasi Kode. Hasil pembentukan kode yang diperoleh kemudian dibuat kompak lagi dengan melakukan beberapa teknik optimasi supaya dapat diperoleh program yang lebih efesien.

Dalam hal ini dilakukan beberapa hal seperti pendeteksian suatu ekspresi yang sering terjadi, sehingga pengulangan tidak perlu terjadi dan lain sebagainya.

BAB V

A. Sintaks

Pendefisian Sintaks suatu bahasa dilakukan dengan menggunakan suatu notasi tata bahasa bebas konteks (context-free grammar) atau untuk memudahkan disebut tata bahasa saja.

Suatu tata bahasa secara alamiah menerangkan struktur hirarki dari banyak bentuk bahasa pemrograman. Misalkan perintah if-else dari bahasa C mempunyai bentuk:

if (ekspresi) perintah else perintah

Ket :

Dalam hal ini suatu perintah adalah gabungan dari :

ü kata kunci if

ü kurung buka

ü ekspresi

ü kurung tutup

ü perintah

ü kata kunci else

ü perintah lainnya

(Dalam bahasa C tidak ada kata kunci then).

Bila digunakan nama variabel expr untuk menyatakan suatu ekspresi dan variabel stmt untuk menyatakan suatu perintah, maka struktur aturan ini dapat dinyatakan sebagai berikut :

stmt → if (expr) stmt else stmt

Ket:

→ (tanda panah dibaca sebagai) "Dapat berbentuk suatu".

Aturan diatas disebut juga suatu produksi (production). Dalam suatu produksi seperti ini unsur leksikal seperti kata kunci if dan tanda kurung "(",")" disebut suatu token

Variabel seperti expr dan stmt disebut dengan non-terminal.

Secara lengkap suatu tata bahasa bebas konteks dapat mempunyai 4 komponen berikut:

ü Himpunan dari token yang dikenal dengan simbol token.

ü Himpunan dari unsur non-terminal

ü Himpunan dari produksi, di mana masing-masing produksi terdiri dari unsur non-terminal (bagian kiri tanda panah dari suatu produksi). Bagian kanan produksi berupa → (tanda panah) dan barisan dari token dan/atau non-terminal (sebelah kanan tanda panah).

ü Salah satu unsur non-terminal yang telah ditentukan sebagai awal tata bahasa disebut sebagai simbol awal.

Aturan umum yang digunakan dalam menentukan suatu tata bahasa adalah dengan menuliskan produksi yang ada dengan dimulai dari produksi yang mengandung simbol awal.Terminal dapat berupa angka-angka, tanda-tanda seperti <=, dan rangkaian karakter yang ditulis huruf tebal seperti while dan lain-lainnya juga nama lain yang tidak dicetak miring.

Non-teminal dapat berupa nama yang dicetak miring.

Untuk memudahkan penulisan, maka produksi yang mempunyai simbol non-teminal disebelah kiri yang sama bagian kanannya dapat dikelompokkan dengan menggunakan tanda "|" yang memisahkan pilihan bagian kanan yang ada. pengelompokkan seperti ini dapat dibaca sebagai "atau"

Contoh 1:

9-5+2, 3-1, 7 merupakan barisan dari angka-angka yang dipisahkan oleh tanda '+' atau '-'. Tata bahasa berikut memberkan sintaks dari ekspresi-ekspresi di atas. Produksi yang ada adalah:

list → list + digiT

list → list – digit

list → digit

digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Bagian kanan dari produksi untuk unsur non-terminal list

list → list + digit

list → list – digit

list → digit

di bagian kiri dapat dikelompokkan menjadi 1 produksi yang setara, yaitu:

list → list + digit | list - digit | digit

ü Penulisan Produksi menjadi:

list → list + digit | list - digit | digit

digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

ü Token yang menjadi terminal digunakan adalah simbol +,-,0,1,2,3,4,5,6,7,8,9

ü Sedangkan unsur non-terminal adalah nama-nama yang digaris miring seperti list dan digit

ü Simbol Awal adalah produksi non-terminal list

Suatu unsur non-terminal dapat merupakan suatu produksi bila unsur non-terminal tersebut timbul dibagian kiri dari produksi.Barisan token adalah barisan dari nol atau lebih token. Unsur yang mengandung nol token ditulis sebagai ε, dan disebut dengan nama barisan kosong.

Suatu bahasa diperoleh dari :

ü barisan-barisan yang dimulai dari simbol awal 

ü bagian kanan yang masih berupa non-terminal (bukan token/terminal) dari produksi dapat diganti dengan mencari acuan pada bagian kiri dari produksi yang ada dengan non-terminal yang sama.

ü mengganti unsur non-terminal pada bagian kiri produksi dengan bagian kanan dari produksi non-terminal tersebut. 

ü Barisan token pada bagian kanan produksi yang menjadi pengganti unsur non terminal acuan pada bagian kiri produksi merupakan akhir dalam pembentukan bahasa.

Contoh 2:

Bahasa yang didefinisikan oleh tata bahasa pada contoh 1 terdiri dari barisan angkaangka yang dipisahkan oleh tanda '-' atau '+'.

Kesepuluh produksi dari unsur nonterminal digit (digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) dapat digunakan sebagai penganti token-token yang berhubungan dengan angka yaitu 0,1,2,3,4,5,6,7,8,9 dari produksi list → digit, maka dapat dikatakan bahwa 1 angka yang berdiri sendiri adalah suatu list juga, yaitu :

Pada produksi list → digit

0 merupakan bahasa yang dibentuk list

1 merupakan bahasa yang dibentuk list

2 merupakan bahasa yang dibentuk list

3 merupakan bahasa yang dibentuk list

4 merupakan bahasa yang dibentuk list

5 merupakan bahasa yang dibentuk list

6 merupakan bahasa yang dibentuk list

7 merupakan bahasa yang dibentuk list

8 merupakan bahasa yang dibentuk list

9 merupakan bahasa yang dibentuk list

Pada produksi lainnya

list → list + digit

list → list – digit

menyatakan bahwa list yang diikuti oleh tanda '+' atau '-' dan diikuti oleh list akanmembentuk suatu list baru.Ternyata semua produksi yang digunakan pada contoh 1 adalah produksi-produksi yang diperlukan untuk dapat mendefinisikan bahasa yang diinginkan untuk ekspresi 9-5+2, 31, 7 .9-5+2 merupakan salah satu anggota dari bahasa yang dibentuk list, dimana list adalah simbol awal. Hal ini dapat ditunjukkan sebagai berikut:

ü 9 merupakan list dari produksi "list → digit" dimana digit membentuk 9 pada

"digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9" atau secara terpisah menjadi

digit → 0

digit → 1

digit → 2

digit → 3

digit → 4

digit → 5

digit → 6

digit → 7

digit → 8

digit → 9.

ü 9-5 merupakan list dari produksi "list → list - digit" dimana 9 sudah berupa list dan digit membentuk 5 pada "digit → 5".

ü 9-5+2 merupakan list dari produksi "list → list + digit" = (9-5) + 2. Dimana 9-5 sudah berupa list dan digit membentuk 2 pada "digit → 2".

Hal ini dapat dilihat pada gambar 1 berikut ini

Gambar 1 Pohon urai dari ekspresi 9-5+2 menurut tata bahasa contoh 1

Pada gambar ini setiap nodal (titik pertemuan antar garis) pada pohon urai diberi label salah satu simbol tata bahasa.Nodal dalam (internal node / nodal di atas nodal yang lain) dan anak-anaknya (nodal yang terletak di bawah nodal dalam) berhubungan dengan suatu produksi.

Nodal dalam berhubungan dengan bagian kiri dari produksi, sedangkan anak-anaknya berhubungan dengan bagian kanan dari produksi yang sama.

Pohon demikian disebut pohon urai dari ekspresi yang diberikan.

Contoh 3 

Pada bahasa Pascal dapat dijumpai dalam cakupan blok begin-end. Salah satu perbedaan yang sangat mencolok yang terdapat pada contoh adalah adanya list dari perintah-perintah yang mungkin kosong diantara token-token begin dan end.Untuk itu dikembangkan suatu tata bahasa yang mengandung produksi berikut:

block → begin opt_stmts end

opt_stmts → stmt_list | ε

stmt_list → stmt_list εstmt | stmt

Pada produksi opt_stmts, kemungkinan ke-2 bagian kanan pada "opt_stmts → stmt_list | ε" adalah perintah yang boleh memilih "ε", yang mengartikan rangkaian kosong dari simbol-simbol. Jadi suatu blok dapat hanya terdiri dari 2 token yaitu begin dan end Pada produksi stmt_list sangat mirip dengan produksi list pada contoh 1, dimana tanda "|" menggantikan operator "+" dan "-" (list → list + digit | list - digit | digit). Unsur non-terminal stmt menggantikan unsur non-terminal digit.

B. Token

Token merupakan unit atau elemen dasar bahasa komputer (seperti 'kata' di bahasa manusia), dimana unit tersebut tidak terbagi lagi. Token merupakan bagian hasil dari pemecahan sumber program yaitu penerjemahan lexeme pada saat melakukan scanner.

Token mereprentasikan nama :

ü identifier -> nama variabel, fungsi, tipe atau nama yang didefinisikan pemakai.

ü Keyword

ü literal string 

ü operator 

ü label 

ü simbol tanda -> tanda kurung, koma, titik koma.

BAB VI

A. CARA PENANGANAN KESALAHAN

Sebuah kompilator akan sering menemui program yang mengandung kesalahan, maka kompilator harus memiliki strategi apa yang harus dilakukan untuk menangani kesalahan-kesalahan tersebut.

Unsur Penanganan Kesalahan

• Kesalahan Program 

• Penanganan Kesalahan 

• Reaksi Kompilator Pada Kesalahan 

• Error Recovery 

• Error Repair 

1. Kesalahan Program

ü Kesalahan Leksikal 

▪ Misalnya kesalahan mengetik/mengeja keyword, 

contoh: THEN ditulis TEN atau THN

ü Kesalahan Sintaks 

Misalnya pada operasi aritmatika dengan tanda kurung 

ü Kesalahan Semantik 

▪ Tipe data yang salah, misal tipe data integer digunakan untuk variabel string.

Contoh : C : Integer;

C := 1.38 * 0.78

▪ Variabel belum didefinisikan tetapi digunakan dalam operasi.

Contoh : B := B + 1

tapi B belum didefinisikan 

▪ yang jumlahnya kurang,

contoh : A:=X+(B*(C+D)

2. Penanganan Kesalahan

Langkah-langkah penanganan kesalahan: 

1. Mendeteksi kesalahan 

2. Melaporkan kesalahan 

3. Tindak lanjut perbaikan 

v Kompiler menemukan kesalahan, meliputi: 

· Kode kesalahan 

· Pesan kesalahan dalam bahasa natural

· Nama dan atribut identifier

· Type checking 

Contoh : Error 162 jumlah: unknown identifier

Ø Kode kesalahan = 162

Ø Pesan kesalahan = unknown identifier

Ø Nama identifier = jumlah

3. Reaksi Kompilator Pada Kesalahan

Beberapa reaksi yang dilakukan oleh kompiler :

o Reaksi yang tidak dapat diterima (tidak melaporkan error)

· Kompilator crash : berhenti atau hang

· Looping

· Kompilator melanjutkan proses sampai selesai tapi program program objek yang dihasilkan salah.

o Reaksi yang benar tapi kurang dapat diterima dan kurang bermanfaat.

Pemrogram membuang waktu untuk melakukan pengulangan kompilasi untuk setiap kali terdapat sebuah error. 

4. Error Recovery

Tujuannya mengembalikan parser ke kondisi stabil (supaya bisa melanjutkan proses parsing ke posisi selanjutnya).

Strategi yang dilakukan sebagai berikut :

§ Mekanisme Ad Hoc

§ Syntax Directed Recovery

§ Secondary Error Recovery

§ Context Sensitive Recovery

5. Error Repair

¡ Bertujuan untuk memodifikasi source program dari kesalahan dan membuatnya valid.

¡ Mekanisme error repair meliputi :

▪ Mekanisme Ad Hoc

Tergantung dari pembuat kompilator sendiri 

▪ Syntax Directed Repair

Menyisipkan simbol terminal yang dianggap hilang atau membuang terminal penyebab kesalahan 

Contoh :

While a<1

I:=I+1;

Kompilator akan menyisipkan DO karena kurang simbol DO.

BAB VII

A. Struktur Compiler

Adalah Tahapan-tahapan dari sebuah program komputer yang berguna untuk menerjemahkan program komputer yang ditulis dalam bahasa pemrograman tertentu menjadi program yang ditulis dalam bahasa pemrograman lain. 

B. Fungsi Compilator

Fungsi compiler atau kompilator, yaitu untuk menyelesaikan problema penterjemahan bahasa tingkat tinggi ke dalam bahasa yang dimngerti oleh mesin.

Cara Kerja compiler

Compiler atau Kompilator mengambil program sumber sebagai input dan menghasilkan sederetan instruksi mesin yang ekivalen sebagai output.

C. Gambar Struktur compiler

BAB VIII

A. TABEL INFORMASI/SIMBOL

1. Fungsi Tabel Informasi atau Tabel Simbol :

• Membantu pemeriksaan kebenaran semantik dari program sumber.
• Membantu dan mempermudah pembuatan intermediate code dan proses pembangkitan kode.
• Untuk mencapai fungsi tersebut dilakukan dengan menambah dan mengambil atribut variabel yang dipergunakan pada program dari tabel. Atribut, misalnya nama, tipe, ukuran variabel.
• Tabel Simbol berisi daftar dan informasi identifier pokok yang terdapat dalam program sumber, disebut Tabel Pokok / Utama.
• Tabel Pokok belum mengcover semua informasi, untuk itu disediakan tabel lagi sebagai pelengkap Tabel Pokok.
• Untuk mengacu pada tabel simbol yang bersesuaian dengan suatu indentifier tertentu, maka pada Tabel Pokok harus disediakan field yang bisa menjembatani identifier dari Tabel Pokok ke tabel-tabel lain yang bersesuaian.
• Untuk itu, pemilihan elemen tabel pada Tabel Pokok maupun tabel lainnya, merupakan sesuatu yang sangat penting
• Elemen pada Tabel Simbol bermacam-macam, tergantung pada jenis bahasanya 

Misalnya :

• No urut identifier : Menentukan nomor urut identifier dalam tabel simbol.
• Nama identifier : Berisi nama-nama identifier (nama variabel, nama tipe, nama konstanta, nama procedure, nama fungsi, dll) yang terdapat pada program sumber. Nama-nama ini akan dijadikan referensi pada waktu analisa semantik, pembuatan intermediate code, serta pembangkitan kode.
• Tipe identifier : Berisi keterangan/informasi tipe dari record dan string, maupun procedure dan function.
• Object time address : address yang mengacu ke alamat tertentu.
• Dimensi dari identifier yang bersangkutan.
• Nomor baris variabel dideklarasikan.
• Nomor baris variabel direferensikan.
• Field link.

B.Implementasi Tabel Simbol

1. Beberapa jenis : 

• Tabel Identifier : Berfungsi menampung semua dentifier yang terdapat dalam program. 
• Tabel Array : Berfungsi menampung informasi tambahan untuk sebuah array. 
• Tabel Blok : Mencatat variabel-variabel yang ada pada blok yang sama. 
• Tabel Real : menyimpan elemen tabel bernilai real. 
• Tabel String : Menyimpan informasi string. 
• Tabel Display : Mencatat blok yang aktif. 

C. Tabel Identifier

1. Memiliki field :

• No urut identifier dalam tabel 
• Nama identifier
• Jenis/obyektif dari identifier : Prosedur, fungsi, tipe, variabel, konstantaa
• Tipe dari identifier yang bersangkutan : integer, char, boolean, array, record, file, no-type
• Level : Kedalaman identifier tertentu, hal ini menyangkut letak identifier dalam program. Konsepnya sama dengan pembentukan tree, misal main program = level 0. Fiel ini digunakan pada run time untuk mengetahui current activation record dan variabel yang bisa diakses.

Untuk identifier yang butuh penyimpanan dicatat pula :

• Alamat relatif/address dari identifier untuk implementasi 
• Informasi referensi (acuan) tertentu ke alamat tabel lain yang digunakan untuk mencatat informasi-informasi yang diperlukan yang menerangkannya.
• Link : Menghubungkan identifier ke identifier lainnya, atau yang dideklarasikan pada level yang sama.
• Normal : Diperlukan pada pemanggilan parameter, untuk membedakan parameter by value dan reference (berupa suatu variabel boolean

Contoh implementasi tabel identifier :

TabId: array [0..tabmax] of

record

name: string;

link: integer;

obj: objek;

tipe : types;

ref :integer;

normal: boolean;

level : 0..maxlevel;

address : integer;

end;

Di mana : objek = (kontant, variabel, prosedur, fungsi)

types = (notipe, int, reals, booleans, chars, arrays, record) 

D. Tabel Array 

1. Memiliki field :

• No urut suatu array dalam tabel 
• Tipe dari indeks array yang bersangkutan 
• Tipe elemen array
• Referensi dari elemen array
• Indeks batas bawah array
• Indeks batas atas array
• Jumlah elemen array
• Ukuran total array ( total size = (atas-bawah+1) x elemen size) 
• Elemen size (ukuran tiap elemen)
• Tabel Array diacu dengan field referensi pada Tabel Identifier

Contoh implementasi Tabel Array :

TabArray : array [1...tabmax] of

record

indextype, elementype : types;

elemenref, low, high, elemensize, tabsize : integer

end;

Tabel Blok Memiliki field :

• No urut blok 
• Batas awal blok 
• Batas akhir blok 
• Ukuran parameter / parameter size
• Ukuran variabel / variabel size
• Last variable
• Last parameter

Contoh implementasi tabel blok :

TabBlok: array [1..tabmax] of

record

lastvar, lastpar, parsize, varsize: integer;

end;

Dari contoh listing program berikut :

Program a;

var B: integer;

Procedure X(Z:char);

var C : integer

Begin

…….

Akan diperoleh, untuk blok Program A :

last variable = 2

variable size = 2 (dianggap integer butuh dua byte)

last parameter = 0 (tanpa parameter)

parameter size = 0

Untuk blok Procedure X :

last variable = 4

variable size = 2 

last parameter = 3 

parameter size = 1 (dianggap char butuh satu byte)

E. Tabel Real

Elemen tabel real :

No urut elemen 

Nilai real suatu variabel real yang mengacu ke indeks tabel ini 

Contoh implementasi tabel real :

TabReal : array [1..tabmax] of real

(pemikiran : setiap tipe yang dimiliki oleh suatu bahasa akan memeiliki tabelnya sendiri)

F.Tabel String

Elemennya :

• No urut elemen 
• Karakter-karakter yang merupakan konstanta 

Contoh implementasi tabel string :

TabString : array [1..tabmax] of string

G. Tabel Display

Elemennya :

• No urut tabel 
• Blok yang aktif 

Pengisian tabel display dilakukan dengan konsep stack. Urutan pengaksesan : 

Tabel 

Display – Tabel Blok – Tabel Simbol.

Contoh implementasi Tabel Display :

TabDisplay : array [1..tabmax] of integer

H.Interaksi Antar Tabel

Pertama kali tabel display akan menunjuk blok mana yang sedang aktif. Dari blok yang aktif ini, akan diketahui identifier-identifier yang termasuk dalam blok tersebut. Untuk pertama kalinya, yang akan diacu adalah identifier yang paling akhir, kemudian identifier sebelumnya, dan seterusnya. Informasi suatu identifier ini mungkin belum lengkap. Untuk itu dari tabel identifier ini mungkin akan dicari kelengkapan informasi dari suatu identifier ke tabel yang sesuai (tabel real, tabel string, atau tabel array).

BAB IX

KESIMPULAN DAN SARAN

A. KESIMPULAN

Pada awal 1950-an. Sejak waktu tersebut teknik dan cara pembentukan suatu kompilator telah berkembang dengan sangat pesat dan pembentukkan suatu kompilator dapat dilakukan makin mudah.Demikian pula program bantu (tools) untuk membuat suatu kompilator sudah dapat diperoleh sehingga pembentukan suatu kompilator dapat dilakukan dengan cepat. Kompilator pertama yang dibuat adalah kompilator untuk bahasa FORTRAN yang pada saat itu dikembangkan dengan memakan sejumlah tenaga ahli yang setara dengan pekerjaan yang dilakukan oleh 18 orang.

B. SARAN 

Dalam tulisan ini Masih banyak kesalahan dari penulisan saya, karena saya adalah seorang manusia tempat salah dan khilaf yang tidak luput dari salah dan dosa, dan kami juga butuh kritik dan saran yang sifatnya membangun agar bisa menjadi motivasi di masa depan yang lebih baik daripada masa sebelumnya. Saya juga mengucapkan terima kasih kepada dosen mata kuliah teknik kompilasi dengan Bapak Dedi Abdullah karena telah memberi saya tugas demi kebaikan diri saya sendiri dan untuk negara dan bangsa.

Daftar Pustaka

Ilmu Komputer.htm, Ilmu Kompyre (http://3onoikom.wordpress.com/materi-kuliah/teknik-kompilasi-2/)2011
Tehnik-kompilasi.htm, Global Komputer (http://globalkomputer.com/), 2008.
Nurfarani iin, Kuis-tehnik-kompilasi (http://i2n.juve.blogspot.com/), 2008.
Analisis-Leksikal.htm, Global Komputer (http://globalkomputer.com/), 2008.
Analisis-Sintaktk.htm, Global Komputer (http://globalkomputer.com/), 2008.