Teknik Kompilasi - Model Kompilator

Model Kompilator

Proses kompilasi dikelompokkan dalam dua kelompok besar :

1.      Analisa     :    Program sumber dipecah-pecah dan dibentuk menjadi bentuk antara                                    (Intermediate Representation)

2.      Sintesa     :    Membangun program sasaran yang diingkan dari bentuk antara

Berikut adalah bagan pokok proses kompilasi.

Bagan Pokok Proses Kompilasi

Keterangan

1.      Program Sumber ditulis dalam bahasa sumber, misal Pascal, Assembler, dsb.

2.      Program sasaran dapat berupa bahasa pemrograman lain atau bahasa mesin pada suatu komputer.

3.      Scanner : Memecah program sumber menjadi besaran leksik/token.

4.      Parser : Memeriksa kebenaran dan urutan kemunculan token.

5.      Penganalisa semantik : Melakukan analisa semantik, biasanya dalam realisasi akan digabungkan dengan intermediate code generator (bagian yang berfungsi membangkitkan kode antara).

6.      Pembentuk kode : Membangkitkan kode objek.

7.      Pengoptimal kode :memperkecil hasil dan mempercepat proses.

8.      Tabel : Menyimpan semua informasi yang berhubungan dengan proses kompilasi.

Berikut adalah model struktur compiler

Model Struktur Compiler

Keterangan

1.      Lexical analysis = scanner, syntax analysis, dan intermediate code merupakan fungsi analisis dalam compiler, yang bertugas mendekomposisi program sumber menjadi bagian-bagian kecil.

2.      Code optimation dan code generation adalah merupakan fungsi synthetis yang berfungsi melakukan pembangkitan/pembuatan dan optimasi program (object program).

3.      Scanner adalah mengelompokkan program asal/sumber menjadi token.

4.      Parser (mengurai) bertugas memeriksa kebenaran dan urutan dari token-token yang terbentuk oleh scanner.

Lexical Analysis

Berhubungan dengan bahasa sering disebut dengan scanner, bertugas sebelum proses syntax analysis, dan intermediate code dilakukan, dimana tugas lexical analysis ini mendekomposisi program sumber menjadi bagian-bagian kecil.

Token-token ini sebagai inputan untuk syntax analysis. Token-token ini bisa berbentuk pasangan item. Dimana item pertama menunjukkan alamat atau lokasi dari token pada tabel simbol. Item kedua adalah representasi internal dari token. Semua token direpresentasikan dengan informasi yang panjangnya tetap (konstan), suatu alamat (address atau pointer) dan sebuah integer (bilangan bulat).

Tugas-tugasnya secara detail adalah :

·         Mengidentifikasi semua besaran yang membangun suatu bahasa.

·         Mentransformasikan ke token-token.

·         Menangani kesalahan.

·         Menangani tabel simbol.

·         Scanner, dirancang untuk mengenali keyword, operator, identifier.

·         Token : Karakter pemisah yang ada dalam bahasa sumber program didalam grup yang termasuk bersama secara logika.

·         Misalnya : Konstanta, nama variabel ataupun operator dan delimeter (besaran leksikal)

Contoh besaran leksikal :

·         Identifier dapat berupa keyword atau nama kunci, seperti IF..ELSE, BEGIN..END (pada pascal), INTEGER (pascal), INT, FLOAT (bahasa C).

·         Konstanta : Besaran yang berupa bilangan bulat (integer), bilangan pecahan (float/real), boolean (true/false), karakter, string dan sebagainya.

·         Operator : Operator arithmatika ( + - * / ), operator logika ( < = > ).

·         Delimeter : Berguna sebagai pemisah/pembatas, seperti kurung-buka, kurung-tutup, titik, koma, titik dua, white space.

·         White space : pemisah yang diabaika oleh program, seperti enter, spasi, garis bawah, akhir file.

Syntax Analysis

Bagian kedua compiler bertugas memeriksa kebenaran dan urutan dari token-token yang terbentuk oleh lexical analysis.

Tugas dari syntax analysis adalah :

·         Pengelompokan token-token kedalam class syntax (bentuk syntax), seperti procedure, statement dan expression.

·         Grammer : Sekumpulan aturan-aturan, untuk mendefinisikan bahasa sumber.

·         Grammer dipakai oleh syntax analysis untuk menentukan struktur dari program sumber.

·         Proses pendeteksiannya (pengenalan token) disebut dengan parsing. Maka syntax analysis sering disebut dengan parser.

·         Pohon sintaks yang dihasilkan digunakan untuk semantics analyser yang bertugas untuk menentukan ‘maksud’ dari program sumber, misalnya operator penjumlahan maka semantics analyser akan mengambil aksi apa yang harus dilakukan.

·         Terdapat statement : ( A + B ) * ( C + D ).

·         Akan menghasilkan bentuk sintaksis : <faktor>, <term> & <expression>.

Statement : ( A + B ) * ( C + D )

Syntax Tree

·         Pohon syntax / pohon penurunan (syntax tree / parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal.

·         Misalnya :

S → AB

A→ aA | a

B→ bB | B

Parsing (Proses Penurunan)

Parsing dapat dilakukan dengan cara :

·         Penurunan terkiri (leftmost derivation) : simbol variabel yang paling kiri diturunkan (tuntas) dahulu.

·         Penurunan terkanan (rightmost derivation) : simbol variabel yang paling kanan diturunkan (tuntas) terlebih dahulu.

·         Misalnya  : ingin menurunkan string aabbaa dari :

·         Context free language :

S → aAS | a

A→ SbA | ba

Penurunan kiri :

S => aAS, aSbAS, aabAS, aaabbaS, aabbaa.

Penurunan kanan :

S => aAS, aAa, aSbAa, aSbAa, aSbbaa, aabbaa.

Metode Parsing perlu memperhatikan 3 hal yaitu :

1. Waktu eksekusi.
2. Penanganan kesalahan.
3. Penanganan kode.

Parsing digolong menjadi :

• Top down parsing

Penelusuran dari root ke leaf atau simbol awal ke simbol terminal

Metode inimeliputi :

1.      Backtrack/backup : Brute Force

-          Memilih aturan produksi dari kiri.

-          Meng-expand simbol non terminal sampai pada simbol terminal.

-          Bila terjadi kesalahan (string tidak sesuai) maka dilakukan backtrack

-          Algoritma ini membuat pohon parsing secara top-down, yaitu dengan cara mencoba segala kemungkinan untuk setiap simbol non-terminal.

-          Contoh :

S → aAd | aB                                      B → ccd | ddc

A→ b | c

                        Kelemahan Brute Force yaitu :

-          Mencoba untuk semua aturan produksi yang ada sehingga menjadi lambat (waktu eksekusi).

-          Mengalami kesukaran untuk melakukan pembetulan kesalahan.

-          Banyak memakai memori, karena membuat backup lokasi backtrack.

-          Grammer yang memiliki rekursif kiri tidak bisa diperiksa, sehingga harus diubah dulu, karena rekursif kiri akan mengalami loop  yang terus-menerus.

2.      No backtrack : recursive descent parser

-          Salah satu cara untuk mengaplikasikan bahasa context free.

-          Simbol terminal maupun simbol variabelnya sudah bukan karakter.

-          Besaran leksikal sebagai simbol terminalnya, besaran syntax sebagai simbol variabelnya / non terminal.

-          Dengan cara penurunan secara recursif untuk semua variabel dari awal sampai ketemu terminal.

-          Tidak pernah mengambil token secara mundur (back tracking).

• Buttom up parsing

Metode ini melakukan penelusuran dari leaf ke root.

Semantic Analysis

Proses ini merupakan proses kelanjutan dari proses kompilasi sebelumnya, yaitu lexical analysis dan syntax analysis. Bagian terakhir dari tahapan analisis. Memanfaatkan pohon syntax yang dihasilkan dari parsing. Proses syntax analysis dan semantic analysis merupakan dua proses yang sangat erat kaitannya dan sulit dipisahkan.

Contoh :

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

Parser hanya akan mengenali simbol-simbol ‘:=’, ‘+’ dan ‘*’, parser tidak mengetahui makna dari simbol-simbol tersebut. Untuk mengenali makna dari simbol-simbol tersebut, compiler memanggil routine semantics.

Untuk mengetahui makna, maka routine ini akan memeriksa :

·         Apakah variabel yang ada telah didefinisikan sebelumnya?

·         Apakah variabel-variabel tersebut tipenya sama?

·         Menggunakan tabel simbol.

·         Pemeriksaan bisa dilakukan pada tabel identifier, tabel display, dan tabel block.