MODEL KOMPILATOR

MODEL KOMPILATOR

BAB 1 PENDAHULUAN

 
1.1    Kompilator

            Kompilator adalah suatu program yang membaca program yang ditulis dengan bahasa tertentu (bahasa sumber) dan menerjemahkannya ke bahasa lain (bahasa tujuan). Contoh bahasa-bahasa sumber adalah bahasa-bahasa pemrograman tradisional seperti Fortran, Pascal, dan Cobol, sedangkan bahasa tujuan pada umumnya merupakan bahasa mesin atau bahasa assebly yang tergantung pada jenis mesinnya.

            Proses kompilasi dapat dibagi menjadi dua bagian, yaitu bagian analisis dan sintesis. Dalam proses analisis, program sumber diuraikan menjadi program dalam bahasa tingkat menengah. Proses sintesa akan mengubah representasi menengah tersebut menjadi program dalam bahasa tujuan.

            Bagian analisis dan sintesa dibagi-bagi lagi menjadi beberapa tahap. Salah satu bentuk umum dari pentahapan proses kompilasi dapat dilihat pada gambar

Mulai dari tahap analisis leksikal sampai pembentukan kode menengah adalah bagian analisis. Sedangkan tahap optimisasi kode dan pembentukan kode tujuan adalah bagian sintesa.

            Dalam implementasinya, tahap-tahap tersebut dapat dikerjakan secara berkelompok. Misalnya analisis leksikal, analisis sintak, analisis semantik, dan pembentukan kode menengah dikerjakan dalam suatu kelompok (pada pass pertama). Sedangkan mulai dari optimisasi kode dapat saja dihilangkan jika ingin membuat suatu kompilator yang relatif sederhana.

            Ada dua tahap penting lain yang bekerja secara interaktif dangan ketujuh tahap yang termasuk dalam bagian analisis dan sintesa, yaitu pengaturan tabel simbol dan penanganan kesalahan.

1.2    Analisis Leksikal

            Peranan utama dari analisis leksikal adalah membaca karakter masukan dari program sumber dan mengelopokkannya menjadi token-token yang akan dipergunakan untuk proses berikutnya, yaitu analisis sintak. Analisis leksikal juga berperan dalam membuang karakter-karakter tertentu, seperti spasi, tabulasi dan komentar.

            Dalam penanganan kesalahan pada saat kompilasi, analisis leksikal digunakan untuk menghubungkan pesan kesalahan dengan program sumbernya. Misalnya, nomor baris letak kesalahan dapat ditampilkan, karenan dalam analisis leksikal, nomor baris ini tetap disimpan.

            Ada beberapa istilah penting penting dalam masalah analisis leksikal, seperti "token", "leksim" dan "pola". Suatu himpunan karakter akan membentuk suatu jenis token. Misalnya deretan karakter 3.14 akan membentuk token bilangan, sedangkan deretan karakter JUMLAH akan membentuk token identifier. Sedangkan bilangan 3.14 dan identifier JUMLAH pada contoh di atas adalah suatu contoh leksim. Deretan karakter suatu leksim sesuai dengan pola suatu token. Token bilangan memiliki pola: deretan karakter yang merupakan gabungan angka dengan karakter 8xyz yang tidak dapat digolongkan dalam token identifier maupun token bilangan.

1.3    Analisis Sintak

            Analisis sintak lebih sering disebut penguraian (parsing). Tujuan utama dari analisis sintak adalah memeriksa apakah urutan token-token yang dihasilkan sesuai dengan tata bahasa dari bahasa yang bersangkutan. Misalnya bahasa C mengenal kalimat: jumlah++; yang berarti menaikkan harga variabel jumlah dengan angka satu. Tetapi kalimat di atas akan salah jika dikompilasi dengan kompilator bahasa Pascal, karena tidak sesuai dengan tata bahasa Pascal.

            Dalam analisis sintak, tata bahasa yang digunakan untuk mendefinisikan aturan sintak suatu bahasa disebut tata bahasa bebas konteks (Context Free Grammar). Tata bahasa ini memiliki empat komponen penting yaitu himpunan simbol terminal, himpunana non-terminal, himpunana produksi dan simbol awal. Dalam bahasa pemrograman, yang disebut terminal adalah token. Contoh terminal adalah token. Contoh terminal adalah if, while, identifier, bilangan. Sedangkan non-terminal merupakan variabel-variabel sintak yang menyatakan himpunan terminal maupun non-terminal. Contohnya non-terminal if_stmt

          Merupakan himpunan terminal if, then, else, dan non-terminal expr dan stmt, yang membentuk aturan produksi : if_stmt à if expr then stmt else stmt. Dari semua simbol non-terminal yang digunakan, ada satu simbol yang bertindak sebagai simbol awal, yaitu simbol yang pertama kalididerivasi. Aturan produksi menggambarkan bagaimana kombinasi non-terminal dan terminal yang benar menurut tata bahasa yanbg bersangkutan.  

Dalam proses penguraian, token-token yang dihasilkan dalam analisis leksikal dibentuk menjadi pohon urai (parse tree). Dalam implementasi kompilator, pohon urai ini belum tentu berbentuk pohon yang sebenarnya, misalnya dengan menggunakan fasilitas pointer.  

Pohon urai merupakan hasil derivasi dari aturan –aturan produksi. Contohnya tata bahasa berikut ini :  

E à E+E | E*E | (E) | -E | id (1.1)

Dengan masukan a*b+c dapat dibentuk satu contoh pohon urai seperti gambar 1.2. Pohon urai tersebut didapat dengan menderivasi aturan produksi di atas sebagai berikut :  

E è E+E è E*E+E è id*E+E è id*id+E è id*id+id  

Ada dua jenis derivasi, yaitu derivasi terkiri dan derivasi terkanan. Derivasi terkiri akan menderivasi suatu aturan produksi mulai dari non-terminal yang paling kiri. Sedangkan derivasi terkanan akan menderivasi suatu aturan produksi mulai dari non-terminal yang paling kanan. Contoh derivasi a*b+c di atas adalah derivasi terkiri. Derivasi terkanan dapat dilakukan sebagai berikut :  

E è E+E è E+id è E*E+id è E*id+id è id*id+id  

Jika proses derivasi aturan-aturan produksi suatu tata bahasa terhadap suatu masukan menghasilkan lebih dari satu pohon urai maka tata bahasa tersebut dikatakan rancu (ambiguous).  

Tata bahasa (1.1) di atas termasuk rancu, karena selain dapat membentuk pohon urai pada gambar 1.2 juga adapat membentuk pohon urai lain yang dapat dilihat pada gambar 1.3. Pohon urai pada gambar 1.3 berasal dari derivasi sebagai berikut :  

E è E*E è id*E è id*E+E è id*id+E è id*id+id  
 

Tata bahasa yang rancu dapat diperbaiki dengan cara menghilangkan rekursi kiri dan melakukan faktorisasi kiri.Rekursi kiri adalah aturan produksi dengan simbol non-terminal pada sisi kiri produksi sama dengan simbol awal sisi kanan produksi, seperti E è E+E. Rekursi kiri dapat menyebabkan pengulangan tak hingga. Faktorisasi kiri adalah pengubahan aturan-aturan produksi memiliki simbol awal sisi kanan produksi yang sama.

Contohnya E è E+E dan E  èE*E.

Faktorisasi kiri perlu dilakukan untuk memastikan pilihan aturan produksi yang akan dipakai.

    Tidak rancu dan tidak memiliki rekursi kiri merupakan ciri-ciri dari tata bahasa yang disebut tata bahasa LL(1). Kedua huruf L berasal dari left (kiri). Huruf L pertama berarti tiap karakter masukan diproses satu per satu mulai dari kiri ke kanan. Huruf L kedua berarti pemakain derivasi derivasi terkiri. Sedangkan angka 1 berarti pada setiap langkah penguraian hanya membutuhkan satu token.

    Penguraian tata bahasa LL(1) menggunakan teknik top-down. Dalam teknik tersebut dilakukan proses derivasi terkiri terhadap suatu masukan . Dalam proses derivasi tersebut dilakukan pembentukan pohon urai yang dimulai dari akar dan membentuk simpul-simpul baru dengan urutan preorder. Contohnya tata bahasa berikut

    S è aBC
    B èbc |  d
    C è e | f

  

    Selain pengurai top-down, ada satu jenis pengurai yang disebut pengurai bottom-up, yaitu proses pembentukan   pohonnya merupakan kebalikan dari pengurai top-down. Pengurai top-down lebih mudah digunakan untuk pembentukan pengurai yang efisien. Pengurai bottom-up dapat menangani tata bahasa yang lebih besar, tetapi   implementasi pengurai ini lebih sukar dibandingkan pengurai top-down.
 

 1.4 Analisis Semantik

    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. Contohnya, untuk mengubah ekspresi matematika menjadi bentuk prefiks dapat dilihat pada DBS yang digambarkan pada gambar 1.5.

                        Produksi                            Aturan Semantik
 
             expr  èexpr + term                       expr.t = + | expr.t | term.t
             expr  è expr - term                       expr.t = - | expr.t | term.t
             expr  è term                                 expr.t = term.t
             term  è0                                       term.t = 0
             term  è 1                                      term.t = 1
             dst.                                                dst
                          Gambar 1.5. DBS untuk mengubah ekspresi ke dalam bentuk prefik
 

    Evaluasi aturan semantik dilakukan dengan pelacakan terdalam (depth first traversal).

Skema Translasi adalah suatu tata bahasa bebas konteks dengan penyisipan suatu bagian program, yang disebut aksi semantik, pada sisi kanan produksi. Secara prinsip, skema translasi hampir sama dengan DBS. Perbedaannya terletak pada urutan evaluasi aturan semantik yang ada pada skema translasi dinyatakan dengan jelas, sedangkan pada DBS tidak. Contoh bentuk skema translasi dapat dilihat pada gambar 1.6.
 

                                Produksi dan aksi semantiknya
                        expr  è {print ('+')} expr1 + term
                        expr  è {print ('-')} expr1 - term
                        expr  è term
                        term  è 0 {print ('0')}
                        term  è 1 {print ('1')}
                        dst.
 
 
                       Gambar 1.6. Skema Translasi untuk mengubah ekspresi ke dalam bentuk prefik
 

    Pada gambar 1.6. terlihat bahwa posisi aksi-aksi semantik diketahui dengan jelas.

 1.5 Pembentukan Kode Menengah
 

    Pembentukan kode menengah merupakan tahap lanjutan setelah analisis semantik. Hasil pembentukan kode menengah dapat dianggap sebagai program dengan instruksi-instruksi bahasa mesin abstrak. Bentuk representasi kode menengah harus mudah pembuatannya dan mudah diterjemahkan dalam bahasa tujuan. Salah satu bentuk representasi kode menengah 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 menengah adalah dalam bentuk representasi grafik, seperti pohon maupun graf.

1.6 Optimisasi Kode

Tujuan dari optimisasi kode adalah meningkatkan performansi dari program tujuan, seperti kecepatan eksekusi program dan efisiensi pemakaian memori.

Optimisasi kode dapat dilakukan pada instruksi berikut : x := a * b - c + a * b

Perhitungan a*b dapat dilakukan satu kali saja sehingga hasilnya adalah dua instruksi :

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

Optimisasi kode dapat dilakukan terhadap kode menengah pada saat pembentukan kode menengah dan juga terhadap kode tujuan pada saat pembentukan kode tujuan. Berbeda dengan optimisasi pada kode menengah, optimisasi yang dilakukan pada kode tujuan tergantung pada mesin tujuan yang digunakan.

1.7 Pembentukan Kode Tujuan

Setelah proses optimisasi dilakukan, kode yang dihasilkan diterjemahkan dalam instruksi bahasa mesin atau bahasa assembly. Pada tahap ini, setiap variabel telah ditentukan lokasi memorinya. Kemudian, setiap instruksi yang dibuat dalam kode menengah diterjemahkan satu per satu menjadi deretan instruksi mesin atau assembly.

Contohnya kalimat berikut : c := a * b + 5

Melalui tahap pembentukan kode tujuan, akan dihasilkan kode :

MOV R1,a
MOV R2,b
MUL R1,R2
ADD R1,#5
MOV c,R1

1.8 Pembentukan Tabel Simbol

Tabel simbol merupakan suatu struktur data yang menyimpan informasi nama-nama simbol, seperti nama variabel, konstanta, prosedur, fungsi, dan informasi atribut-atribut tiap simbol, seperti tipe, parameter, nilai konstanta, dan lokasi memorinya.

Informasi yang terdapat dalam tabel simbol dapat digunakan untuk pemeriksaan kesalahan pada saat tahap analisis, seperti pemeriksaan nama dan tipe variabel. Selain itu, informasi lokasi memori dipergunakan dalam pembentukan kode tujuan.

Struktur data tabel simbol dapat berbentuk list linier maupun tabel hash.

1.9 Penanganan Kesalahan

Penanganan kesalahan mencakup pendeteksian kesalahan, pemberian pesan kesalahan dan perbaikan kesalahan.

Prosedur untuk menangani kesalahan dibuat dalam setiap tahap kompilasi yang membutuhkannya. Misalnya dalam analisis leksikal, dibuat prosedur untuk menangani kesalahan-kesalahan leksikal. Demikian pula untuk analisis sintak dan analisis semantik. Sedangkan kesalahan pada waktu program berjalan (run time error) juga harus dapat ditangani dengan memasukkan prosedur penanganan kesalahan dalam program tujuan.

BAB 2 BAHASA IKI40800

2.1 Pendahuluan

Bahasa IKI40800 diperkenalkan pada mata kuliah Teknik Kompilator di Program Studi Ilmu Komputer Universitas Indonesia sejak tahun 1990. Nama bahasa ini berasal dari kode mata kuliah Teknik Kompilator yaitu IKI40800 (pada saat pertama kali diperkenalkan pada tahun 1990, ia masih bernama IKI336).

Karakteristik dari tata bahasa IKI40800 (tata bahasa secara lengkap dapat dilihat pada lampiran 1) dapat dijabarkan sebagai berikut :

• merupakan tata bahasa bebas kontek dengan simbol awal program, memiliki himpunan terminal yaitu identifier dan semua yang berada dalam tanda kutip, dan simbol-simbol lain yang merupakan himpunan non terminal, kecuali yang diawali 'C' atau 'R' dan diikuti angka, serta memiliki 85 aturan produksi.
• termasuk dalam bahasa LL(1), dimana karakteristik dari tata bahasa ini adalah tidak bersifat rancu dan tidak memiliki rekursi kiri.
• berbentuk skema translasi, karena di dalam penulisan tata bahasanya disisipkan bagian-bagian program berupa aksi-aksi semantik. Aksi-aksi semantik ini adalah simbol-simbol yang diawali dengan huruf 'C' atau 'R' diikuti oleh angka. Yang diawali huruf 'C' adalah aksi semantik untuk melakukan analisis semantik, sedangkan yang diawali huruf 'R' digunakan untuk membentuk kode tujuan.

Kata-kata kunci (keywords)

Beberapa kata-kata kunci yang dikenal dalam tata bahasa IKI40800 adalah if, then, else, end if, repeat, until, loop. end loop, exit, var, proc, func, put, get, skip. Tipe variabel yang dikenal ada dua, yaitu integer dan boolean. Nilai integer memiliki interval di antara -32767 sampai +32767, sedangkan nilai boolean berkisar antara true atau false. Tanda ; digunakan untuk menyatakan akhir deklarasi variable. Untuk menyatakan awal dan akhir dari suatu scope digunakan tanda { dan }.

Operator Aritmetika

Operator -operator aritmetika dan presedensinya dapat dilihat pada tabel 2.1

 

Operator	Presedensi	Kategori
+, -, ~(NOT)	1 (tertinggi)	unari
*, /, &(AND)	2	pengali
+, -, |(OR)	3	penambah
=, #, <, , <=, =	4	relasi

Tabel 2.1 Presedensi Operator

Contoh program dalam bahasa IKI40800 dapat dilihat pada gambar 2.1.a, sedangkan gambar 2.1.b adalah program dalam bahasa Pascal yang ekivalen dengan program pada gambar 2.1.a

   { 

      var A     : integer                       var

      var B[10] : integer;                      A : integer

                                                B : array{1..10] of integer

                                                begin

      A := 0                                    A := 0;

      repeat                                    repeat

         B[A] := A*2                               B[A] := A*2;

         A := A+1                                  A := A+1;

      until A = 10                             until A = 10;

      put B[A]                                  write (B[A]);

   }                                            end;

Gambar 2.1. Program dalam bahasa IKI40800 (a) dan Pascal (b)

2.2 Struktur Kompilator IKI40800

Tahap-tahap kompilasi yang dilakukan oleh kompilator IKI40800 dimulai dari analisis leksikal (scanner), analisis sintaks (parser), analisis semantik (context checker) kemudian langsung dibentuk kode tujuan. Keseluruhan proses kompilasi tersebut dilakukan pada satu pass.

Model kompilator bahasa IKI40800 ini merupakan suatu simulasi. Program sumber merupakan program dalam bahasa IKI40800 yang dibuat dalam bentuk file teks. Sedangkan program tujuan berada dalam suatu "memori" berbentuk array satu dimensi. Memori tersebut digunakan untuk menyimpan kode tujuan, alokasi variabel, dan memori run time.

Kode tujuan yang berada dalam memori dapat dieksekusi. Instruksi-instruksi kode tujuan dilakukan terhadap memori, dengan menggunakan instruksi dalam bahasa Pascal. Deskripsi mesin dan instruksi-instruksi kode tujuan IKI40800 secara lengkap dapat dilihat pada lampiran.

Selain memori, terdapat "register" display yang merupakan pointer ke lokasi variabel untuk setiap tingkat leksikal (lexic level). "Register" display ini juga merupakan array satu dimensi.

 
2.3 Scanner (Lexical analyzer)

Untuk melakukan analisis leksikal, di dalam program kompilator IKI40800 terdapat pengelompokan jenis-jenis karakter dan token. Untuk karakter, bentuk pengelompokan karakter adalah sebagai berikut:

- karakter yang diabaikan (ignore), yaitu spasi, tabulasi
- karakter ilegal
- karakter komentar yaitu %
- huruf dan digit
- awal teks, yaitu "
- karakter spesial, yaitu karakter-karakter yang dipakai dalam tata bahasa selain huruf dan digit.
- karakter akhir baris
- karakter akhir file

Karakter-karakter dikelompokkan menjadi token gabungan/komposit, token spesial, dan token keyword. Token gabungan misalnya Tidentifier, Ttext, untuk nama identifier dan teks. Token spesial misalnya Tcolon untuk tanda ';', Tcomma untuk ',' dst. Token keyword misalnya Tif untuk 'if', Tvar untuk 'var', dst.

Yang dilakukan oleh program scanner adalah:
 

• Melakukan pembacaan karakter perkarakter pada berkas masukan.
• Mengklasifikasikan karakter, apakah spesial, huruf, atau lainnya. Jika karakter tersebut tidak termasuk dalam kelompok manapun, maka prosese kompilasi akan berhenti dan memberi pesan kesalahan dan baris posisi kesalahan.
• Mengklasifikasikan karakter atau beberapa karakter menjadi suatu token.
• Token yang didapat akan diproses pada tahap berikutnya, yaitu analisis sintaks oleh program parser.

Program scanner tersebut akan dipanggil oleh parser, setiap kali suatu token yang dihasilkannya telah dproses oleh parser.

2.4  Parser (sintax analyzer)
 

Dalam bab 2 telah dijelaskan bahwa tatabahasa IKI40800 adalah tata bahasa LL(1). Cara penguraian yang dipakai adalah top-down, karena itu teknik derivasi yang dilakukan adalah derivasi terkiri. Beberapa konstanta penting yang didefinisikan pada program parser kompilator IKI40800 :

1. Pendefinisian nama jenis token untuk token terminal, non terminal, token untuk context checker, dan token untuk code generator.

2. Pendefinisian konstanta untuk simbol-simbol non terminal, seperti Nscope untuk non terminal scope, Ndcls untuk non terminal declarations, dst. (Simbol terminal sudah didefinisikan pada program scanner).

3. Himpunan aturan produksi yang berisi seluruh tata bahasa dari IKI40800 yang ditulis menurut simbol-simbol yang telah didefinisikan sebelumnya. Urutan aturan produksi ditulis sesuai dengan tata bahasa IKI40800 pada lampiran. Himpunan aturan produksi ini berupa array satu dimensi yang berukuran sebesar tata bahasa IKI40800, dimana setiap aturan produksi ditulis berurutan dan masing-masing diakhiri token EndRule.

4. Tabel berisi indeks dari posisi aturan produksi pertama untuk setiap non teminal, berdasarkan himpunan aturan produksi di atas.

5. Himpunan FIRST dari tata bahasa IKI40800, yaitu himpunan simbol-simbol awal dari setiap aturan produksi.

Selain konstanta-konstanta di atas, suatu stack dibutuhkan untuk menyimpan simbol-simbol aturan produksi pada suatu saat. Elemen stack parser teratas diinisialisasi simbol awal dari tata bahasa, yaitu Nprog.

Yang dilakukan oleh program parser adalah mengambil elemen stack parser teratas dan melakukan pemeriksaan jenis token elemen tersebut :

a. Jika terminal, maka periksa apakah jenis token terminal tersebut sama dengan yang dibaca. Jika tidak sama, akan ditampilkan pesan kesalahan dan kompilasi berakhir. Jika sama, maka proses scanner dilanjutkan.

b. Jika non terminal, maka dilakukan pencarian aturan produksi yang sesuai untuk menggantikan non terminal tersebut. Pencarian dilakukan dengan bantuan himpunan FIRST yang telah didefinisikan sebelumnya. Setelah ditemukan, maka simbol-simbol awal aturan prosuksi yang mungkin berlaku dimasukkan ke dalam stack. Pada tahap ini dapat dideteksi jika token yang didapatkan tidak sesuai dengan aturan produksi yang ada.

c. Jika token contect checker (bentuknya 'Cx', dimana x adalah bilangan), jalankan program contect checker.

d. Jika token code generator (bentuknya 'Rx', dimana x adalah bilangan), jalankan program code generator.

Hal tersebut dilakukan terus sampai ditemukan kesalahan.

2.5  Contect checker (semantic analyzer)

Analisis semantik dilakukan dengan menyisipkan aksi-aksi semantik pada tata bahasa. Program contect checker akan dipanggil oleh parser pada saat parser menemukan token berawalan dalam bentuk 'Cx' (x = bilangan). Fungsi-fungsi yang dilakukan oleh program contect checker, adalah :

1. Manajemen tabel simbol (akan dijelaskan pada sub bab 3.5).
2. Pemeriksaan deklarasi variabel ganda.
3. Pemeriksaan pemakaian variabel, meliputi :

o        pemeriksaan apakah variabel telah dideklarasikan

o        pemeriksaan kesesuaian tipe variabel yang digunakan, baik pada kalimat assignment maupun kalimat perbandingan.

o        pemeriksaan jenis variabel.

4. Pemeriksaan pemakaian fungsi dan prosedur, termasuk kesesuaian jumlah dan tipe parameter.

Jika suatu kesalahan ditemukan, maka pesan kesalahan akan ditampilkan dengan nomor barisnya, dan proses kompilasi akan berhenti.

2.6  Manajemen table simbol

Struktur data tabel simbol yang dipergunakan dalam kompilasi ini adalah dalam bentuk tabel hash. Tabel hash ini berbentuk array berukuran hash_size, dimana hash_size merupakan bilangan prima. Tiap entri dari array menunjuk ke suatu linked-list linier, dimana setiap node dari linked-list adalah suatu record yang menyimpan informasi satu identifier.

Setiap record dari suatu identifier berisi informasi:

 

• nama identifier
• order number (nomor urutan identifier pada suatu scope)
• lexic level (tingkat leksikal)
• tipe identifier (integer, boolean)
• jenis identifier (skalar, array, prosedur, atau fungsi)
• pointer ke node berikutnya.
• jenis identifier (skalar, array, prosedur, atau fungsi)
• pointer ke node berikutnya

Ada dua prosedur utama yang digunakan untuk manajemen tabel simbol :
 

• Menambah entri

Posisi suatu identifier di dalam tabel simbol berada pada indeks array yang dihitung dengan cara:

(nilai ASCII nama identifier) mod hash_size

Sehingga entri identifier a berada pada indeks 65 (nilai ASCII a = 65), jika nilai hash_size = 211.

Jika pada indeks ke-I, sudah ada list yang terbentuk ,maka perlu diperiksa apakah ada nama identifier yang sama pada tingkat leksikal yang sama. Jika tidak ada, entri baru sebaiknya disisipkan dikepala list. Alasannya, nama identifier yang terakhir dideklarasi akan lebih dulu ditemukan. Jadi, jika ada dua nama identier yang sama dalam dua tingkat leksikal, l1 dan l2, dimana l1l2, maka pada l2, identifier yang dipergunakan adalah identifier yang dideklarasi di l2 (yang pertama ditemukan pada waktu pencarian entri pada tabel simbol).

 

• Menghapus entri

Entri suatu identifier pada suatu tingkat leksikal dihapus pada saat keluar dari skope pada tingkat leksikal tersebut.

Penghapusan dilakukan dengan menelusuri setiap linked list yang ditunjuk oleh pointer pada tiap tabel simbol dan menghapus node yang memiliki tingkat leksikal tersebut.
 

• Mencari entri

Prosedur ini dipakai pada saat menambah entri, pemeriksaan nama, tipe dan jenis suatu identifier, pemeriksaan nama prosedur dan fungsi, pemeriksaan nama dan jumlah parameter pada prosedur dan fungsi.

Dalam pencarian entri, terlebih dahulu dihitung indeks tabel simbol untuk nama identifier yang dicari. Kemudian dilakukan pencarian pada linked list yang ditunjuk oleh pointer pada indeks tersebut.

 

• Mencetak tabel simbol

Fasilitas ini merupakan pilihan bagi pemakai kompilator. Isi tabel simbol dapat dicetak pada saat deklarasi variabel pada suatu tingkat leksikal selesai.

2.7 Pembentukan kode tujuan (code generator)

Telah dijelaskan pada suatu Bab 3.1, bahwa kode tujuan yang dihasilkan oleh kompilator ini adalah kode mesin IKI4336 yang dapat dilihat pada lampiran. Kode tujuan dimasukkan ke dalam "memory" yang diinisialisasi terlebih dahulu sebelum proses kompilasi dimulai.

Program code generator ini dipanggil oleh program parser pada saat ditemukan token berbentuk ‘Rx’. Jenis-jenis instruksi yang dibentuk oleh code generator untuk masing-masing x dapat dilihat pada lampiran.

Beberapa hal penting yang dibutuhkan dalam program code generator ini adalah :
 

• Stack untuk menyimpan informasi jumlah variabel dalam setiap tingkat lenksikal, dibutuhkan untuk melakukan dealokasi variabel pada saat keluar dari suatu scope.
• Stack untuk menyimpan alamat lompatan bersyarat (untuk if). Lompatan tidak bersyarat (biasanya dipakai sebelum deklarasi suatu prosedur/fungsi), dan lompatan mundur untuk loop. Stack diperlukan karena if dan loop bisa bersarang (nested).
• Prosedur untuk cetak tekas yang hanya disisipkan dalam kode tujuan jika ada kalimat put text.
• Prosedur untuk pemeriksaan pembagian dengan nol yang hanya disisipkan dalam kode tujuan jika ada operasi aritmatika yang menggunakan ‘/’.

Kode tujuan yang dihasilkan dapat dieksekusi oleh suatu program tambahan yang akan menjalankan kode tujuan dalam instruksi Pascal.

 

BAB 3

CARA PEMAKAIAN KOMPILATOR IKI40800

3.1 Perangkat keras dan perangkat lunak

Perangkat keras yang dibutuhkan adalah Personal Computer IBM/Compatible dengan kebutuhan memori sesuai dengan kebutuhan kompilator Turbo Pascal versi 5.5 yaitu minimal 448 KB RAM untuk menjalankan integrated environment.

Sedangkan perangkat lunak yang digunakan adalah kompilator Turbo Pascal versi 5.5, dengan sistem operasi MS-DOS versi 3.0 ke atas.

Program kompilator IKI336 ini memiliki 18 file, dengan rincian sebagai berikut :

1. File-file header terdiri atas :

• HSCNPARS.PAS : berisi konstanta yang mendefinisikan token yang merupakan interface antara scanner dan parser.
• HPARSER.PAS : berisi konstanta-konstanta untuk parser.
• HPARSCON.PAS : berisi konstanta untuk context checker (Cx), yang akan dibaca oleh parser.
• HSYMBOL.PAS : berisi konstanta untuk tabel simbol.
• HPARSGEN.PAS : berisi konstanta untuk code generator (Rx), yang akan dibaca oleh parser.
• HMACHINE.PAS : berisi kode mesin semu IKI41366.
• HTKNCODE.PAS : berisi konstanta global untuk mendefinisikan bermacam jenis token.
• HGLOBAL.PAS : berisi konstanta dan variabel global.

2. File-file program terdiri atas :

• IKI40800.PAS : program utama yang akan menjalankan rutin-rutin inisialisasi dan menjalankan program parser.
• SCANNER.PAS : program scanner.
• PARSER.PAS : program parser yang akan memanggil program scanner, context dan generate.
• CONTEXT.PAS : program context checker yang berisi rutin-rutin untuk tiap token 'Cx'.
• SYMBOL.PAS : program berisi rutin-rutin manajemen tabel simbol yang digunakan oleh context checker.
• GENERATE.PAS : program untuk pembentukan kode tujuan, berisi rutin-rutin untuk tiap token 'Rx'.
• MACHINE.PAS : program yang mengatur pemakaian "memori" dan melakukan eksekusi kode tujuan.
• ONSTACK.PAS : stack yang dibutuhkan untuk pengaturan order number (urutan variable)
• SYMSTACK.PAS : stack yang dibutuhkan untuk pengaturan symbol (nama)
• TYPSTACK.PAS : stack yang dibutuhkan untuk pengaturan type variable

3.2 Cara menggunakan kompilator IKI40800

Kompilator IKI40800 dapat dipergunakan dengan terlebih dahulu mengkompilasi kelima belas file di atas. Dengan Turbo Pascal 5.5, program kompilator tersebut dapat dikompilasi sekaligus dengan menggunakan fasilitas BUILD yang ada pada menu COMPILE, pada saat file IKI336.PAS dibuka. Kompilasi dilakukan terhadap DISK, sehingga terbentuk IKI336.EXE.

Kompilator IKI40800 dapat digunakan dengan menjalankan pada DOS prompt :

IKI336 [d:]<file-program

dimana < file-program adalah file berisi program dalam bahasa IKI40800 dalam bentuk file teks. (dalam file zipnya, terdapat contoh1.txt sebagai file input, dan outputnya adalah file contoh.out).

3.3 Contoh masukan dan keluaran

Contoh isi program masukan :

{ var a : integer

  var b : integer

  var c : boolean;

  get a

  b := 0

  if a  b then

     c := true

  else 

     c := false

  end if

  { var a : integer

    a := 5

    if c then

       repeat

          put b

          b := b+1

       until b = a

    end if

  }

}

Keluaran kompilasi program di atas adalah sebagai berikut :

Cetak tabel simbol? ( y/t ) y

Kompilasi mulai

Identifier : a    Order Number : 0    Lexic Level : 0

Tipe : integer    Jenis : skalar

Identifier : b    Order Number : 1    Lexic Level : 0

Tipe : integer    Jenis : skalar

Identifier : c    Order Number : 2    Lexic Level : 0

Tipe : boolean    Jenis : skalar

Identifier : a    Order Number : 0    Lexic Level : 1

Tipe : integer    Jenis : skalar

Cetak kode yang ada di memory? (y/t) y
Cetak kode, pc=0 mt=117
objek cell
0 PUSHMT
1 SETD 0
3 PUSH -32768
5 PUSH 3
7 DUP
8 NAME
11 READI
12 STORE
13 NAME 0 1
16 PUSH 0
18 STORE
19 NAME 0 0
22 LOAD
23 NAME 0 1
26 LOAD
27 FLIP
28 LT
29 PUSH 41
31 BF
32 NAME 0 2
35 PUSH 1
37 STORE
38 PUSH 47
40 BR
41 NAME 0 2
44 PUSH 0
46 STORE
47 PUSHMT
48 SETD 1
50 PUSH -32768
52 NAME 1 0
55 PUSH 5
57 STORE
58 NAME 0 2
61 LOAD
62 PUSH 110
64 BF
65 NAME 1 0
68 LOAD
69 PRINTI
70 PUSH 10
72 PRINTC
73 PUSH 13
75 PRINTC
76 NAME 0 1
79 NAME 0 1
82 LOAD
83 PUSH 1
85 ADD
86 STORE
87 NAME 0 1
90 LOAD
91 NAME 1 0
94 LOAD
95 LT
98 FLIP
99 SUB
100 PUSH 1
102 FLIP
103 SUB
104 PUSH 110
106 BF
107 PUSH 65
109 BR
110 PUSH 1
112 POP
113 PUSH 3
115 POP
116 HALT
Akhir pencetakan kode
Eksekusi kode yang ada di memory? (y/t) y
0 %Input dari pemakai
1
2
3
4

Bab 4. Kemungkinan Pengembangan

Model kompilator IKI40800 yang telah dijelaskan di atas adalah suatu model yang relatif sederhana dari suatu kompilator. Beberapa pengembangan yang dapat dilakukan terhadap model ini adalah sebagai berikut:

1.     Pembentukan kode tujuan dikembangkan lagi sehingga menghasilkan kode dalam bahasa mesin atau Assembly, bukan lagi bahasa mesin semu.

2.     Pengembangan tata bahasa IKI40800 dan kompilatornya, misalnya penambahan kalimat case, for loop, array multi-dimensi, dan sebagainya.

3.     Penambahan prosedur untuk optimisasi kode tujuan. Optimisasi ini akan sangat berguna untuk mengurangi ukuran program tujuan, atau pun mempercepat eksekusi program tujuan.

Penambahan tahap pembentukan kode menengah, supaya dapat dilakukan optimisasi kode yang lebih baik.

Lampiran:

Tata Bahasa (Grammar) IKI40800

program:    scope R38 R0

scope:        '{' C0 R1 declarations C1 R3 ';' statements C2 R5 '}'

statements:    ,
                    statement  statements

statement:    identifier C6 assignOrCall,
                    'if' expression C13 C11 R8 'then' statements optElse 'end' 'if',
                    'repeat' R11 statements 'until' expression C13 C11 R18 R8 R12 R10,
                    'loop' R11 R53 statements R12 'end' 'loop' R51,
                    'exit' R52,
                    'put' outputs,
                    'get' inputs,
                    scope

optElse:        R10,
                    'else' R7 R10 statements R9

assignOrCall:    C28 C29 R45 R44 C7,
                        '(' R45 C28 C30 arguments ')' C32 R44 C7,
                        ':' '=' C20 R31 assignExpression,
                        '[' C21 R40 subscript ']' ':' '=' assignExpression

assignExpression:    expression C16 C11 R33 C7

subscript:        simpleExpression C12 C11 R41

expression:        simpleExpression optRelation

optRelation:        ,
                        '=' simpleExpression C14 C11 C11 C10 R21,
                        '#' simpleExpression C14 C11 C11 C10 R22,

'<'  lessOrLessEq,

'>' greaterOrGreaterEq
 

lessOrLessEq:            simpleExpression C15 C11 C11 C10 R23,
                          '=' simpleExpression C15 C11 C11 C10 R24,

greaterOrGreaterEq:    simpleExpression C15 C11 C11 C10 R25,
                            '=' simpleExpression C15 C11 C11 C10 R26

simpleExpression:    term moreTerms

moreTerms:            ,
                            '+' C12 C11 term C12 R14 moreTerms,
                            '-' C12 C11 term C12 R15 moreTerms,
                            '|'  C13 C11 term C13 R20 moreTerms

term: factor moreFactors

moreFactors: ,

'*' C12 C11 factor C12 R16 moreFactors,
'/' C12 C11 factor C12 R17 moreFactors,
'&' C13 C11 factor C13 R19 moreFactors
 

factor: primary,

'+' factor C12,
'-' factor C12 R13,
'~' factor C13 R18
 

primary: integer C9 R36,

'true' C10 R35,
'false' C10 R34,
'(' expression ')',
'{' C0 R2 declarations C1 R3 ';' statements ';' expression C2 R6 '}',
identifier C6 subsOrCall
 

subsOrCall: C37 R49 C29 C8 R50 C7,

'(' C33 R46 C30 arguments ')' C32 C8 R47 C7,
'[' C21 R40 subscript ']' C8 R32 C7
 

arguments: expression C34 C31 C11 R48 moreArguments

moreArguments: ,

',' expression C34 C31 C11 R48 moreArguments
 

declarations: declaration moreDeclarations

moreDeclarations: ,

declaration moreDeclarations
 

declaration: 'var' identifier C3 C4 optArrayBound ':' type C5 C11 C7,

type 'func' identifier C3 C26 R7 C22 C23 C5 C0 R2 funcBody,
'proc' identifier C3 C24 R7 C22 C0 R1 procBody
 

funcBody: '=' expression C36 C11 C11 C2 R6 R43 R9 C7,

'(' C30 parameters C35 C1 ')' '=' expression C36 C11 C11 C27 R6 R43 R9 C7
 

procBody: scope C2 R5 R42 R9 C7,

'(' C30 parameters C35 C1 ')' scope C27 R5 R42 R9 C7
 

type: 'integer' C9,

'boolean' C10

optArrayBound: C18 R37,

'[' simpleExpression C12 C11 R39 ']' C19
 

parameters: identifier C3 C4 C25 ':' type C5 C11 C7 C34 moreParameters

moreParameters: ,

',' identifier C3 C4 C25 ':' type C5 C11 C7 C34 moreParameters
 

Outputs: output moreOutput R30

output: expression C12 C11 R28,

Text R29,

'skip' R30

moreOutput: ,

',' output moreOutput
 

inputs: input moreInputs

moreInputs: ,

',' input moreInputs
 

input: identifier C6 optSubscript C17 R27 C7

optSubscript: C20 R31,

'[' C21 R40 subscript ']'

Context Checking Rules IKI40800

C0 masuk ke suatu scope.
C1 option mencetak tabel simbol scope yang bersangkutan.
C2 keluar dari suatu scope.
C3 periksa bahwa identifier belum dideklarasi di dalam scope ini,
     masukkan identifier ke dalam tabel simbol, Push index dari tabel simbol.
C4 masukkan lexic level dan order number ke dalam tabel simbol.
C5 masukkan type ke dalam tabel simbol.
C6 periksa bahwa identifier sudah dideklarasi. Push indek tabel simbolnya.
C7 Pop indek tabel simbol.
C8 Push type.
C9 Push type Int.
C10 Push type bool.
C11 Pop type.
C12 Periksa bahwa type adalah int.
C13 Periksa bahwa type adalah bool.
C14 Periksa type untuk perbandingan kesamaan (equality comparison).
C15 Periksa type untuk perbandingan urutan (order comparison).
C16 Periksa type untuk assignment.
C17 Periksa bahwa type variable adalah integer.

Array.

C18 beri tanda, entry tabel simbol sebagai skalar.
C19 beri tanda, entry tabel simbol sebagai variable array.
C20 Periksa bahwa identifier adalah nama variable skalar.
C21 Periksa bahwa identifier adalah nama variable array.

Fungsi dan prosedur.

C22 masukkan lexic level dan order number ke dalam tabel simbol
C23 masukkan type int atau bool.
C36 periksa bahwa type dari ekspresi sama dengan type dari fungsi.

Parameter.

C24 masukkan prosedur ke dalam tabel simbol.
C25 masukkan parameter ke dalam tabel simbol.
C26 masukkan fungsi ke dalam tabel simbol.
C27 keluar dari scope yang mengandung parameter.
C28 periksa bahwa identifier merupakan nama prosedure.
C29 periksa bahwa fungsi atau prosedur tak punya parameter.
C30 Push jumlah argument = 0
C31 periksa argument terhadap parameter.
C32 periksa bahwa semua argumen sudah dilihat. Pop jumlah argument.
C33 periksa bahwa identifier adalah nama fungsi.
C34 tambah nilai jumlah argument.
C35 masukkan jumlah argument (parameter) ke dalam tabel simbol. Pop jumlah argument.
C37 if identifier suatu fungsi maka C33 else C20

Code Generation Rules IKI40800

R0 tentukan pc dan mt
R1 periksa bahwa lexic level <displaySize. Buat instruksi untuk memasuki scope statement.
R2 periksa bahwa lexic level <displaySize. Buat instruksi untuk memasuki scope ekspresi.
R3 buat instruksi untuk mengalokasi variable.
R4 buat instruksi untuk mendapatkan address untuk hasil perhitungan.
R5 buat instruksi untuk menghapus variable dan keluar dari scope statement.
R6 buat instruksi untuk memindahkan hasil perhitungan, hapus variable, dan keluar dari scope ekspresi.
R7 buat instruksi untuk forward branch (BR).
R8 buat instruksi untuk forward bersyarat (BF).
R9 buat instruksi untuk membetulkan address dari forward branc-2 (forward branch-2 bersyarat).
R10 buat instruksi untuk membetulkan address dari forward branch bersyarat.
R11 simpan address untuk backward branch.
R12 buat instruksi untuk backward branch.
R13-R26 buat instruksi yang sesuai dengan operator.
R27 buat instruksi untuk membaca dan menyimpan integer.
R28 buat instruksi untuk mencetak integer.
R29 buat instruksi untuk mencetak teks.
R30 buat instruksi untuk memindahkan kursor ke baris baru.
R31 buat instruksi untuk mendapatkan address variable.
R32 buat instruksi untuk memperoleh nilai dari suatu variable.
R33 STORE.
R34 PUSH 0.
R35 PUSH 1.
R36 PUSH nilai integer.
R37 alokasi space untuk variabel
R38 HALT

Array.

R39 buat instruksi untuk memeriksa bahwa batas array adalah non-negatif. buat instruksi untuk mengalokasikan array.
R40 buat instruksi untuk memperoleh address array.
R41 buat instruksi untuk memeriksa bahwa indek array berada pada batasnya.

Fungsi, prosedur dan parameter.

R42 buat instruksi unutk kembali dari prosedure.
R43 buat instruksi untuk kembali dari fungsi.
R44 buat instruksi untuk memanggil suatu prosedur.
R45 buat instruksi untuk membentuk tanda block untuk pemanggilan prosedur.
R46 buat instruksi untuk membentuk tanda block untuk pemanggilan fungsi.
R47 buat instruksi untuk memanggil fungsi.
R48 buat instruksi untuk menyimpan argument untuk pemanggilan prosedu/fungsi.
R49 if identifier suatu fungsi maka R46 else R31
R50 if identifier suatu fungsi maka R47 else R32

Deskripsi mesin.

Mesin yang dipakai mempunyai komponen-komponen berikut :

memory utama yang terdiri dari word sebanyak memorySize dengan indeks dari 0 sampai memorySize-1. Suatu bilangan yang mewakili suatu word di dalam memory disebut dengan address. Masing-masing word berukuran 16 bit (karena integer biasa). Bentuk bit tersebut di dalam memory dapat diartikan sebagai berikut:

• Suatu nilai integer antara -32767 sampai +32767.
• Suatu nilai boolean. False direpresentasikan oleh integer 0, sedangkan true direpresentasikan oleh integer 1.
• Suatu nilai karakter (satu karakter per satu word).
• Nilai data tak terdefinisi direpresentasikan oleh 1000000000000000.
• Kode operasi. Operasi dan kodenya akan diberikan setelah ini.
• Suatu address.

pc (program counter) memuat address dari pada instruksi berikutnya yang akan dieksekusi.

mt (memory top) memuat address dari pada word berikutnya yang kosong.

Register display uyang berindek dari 0 sampai displaySize-1. Register ini dipakai agar variabel yang berada pada level lexic tertentu dapat ditemukan addressnya.

Pada awal eksekusi, hal-hal berikut akan terjadi

• Instruksi dari suatu program akan menempati memory yang bersambungan, dimulai pada word 0.
• Register mt memuat address dari pada word pertama tepat setelah word milik instruksi-2.
• Sisa memory memuat sampah.
• Display memuat sampah.
• pc memuat address dari pada instruksi pertama yang akan dieksekusi.

Pada tempat setelah instruksi-instruksi, space dialokasikan untuk variabel-variabel dan dapat diakses melalui display. Space yang dibutuhkan untuk hasil sementara evaluasi suatu ekspresi berada pada puncak memory yang sudah dipakai (dinamakan Stack Evaluasi).

Suatu instruksi dapat menempati satu, dua, atau tiga word memory. Word pertama memuat kode operasi yang menentukan operasi apa yang akan dilakukan. Word kedua dan ketiga (jika ada) memuat operand-operandnya. Pada penjelasan berikut, push, pop, dan top mengacu pada memory yang dianggap sebagai satu stack yang pointer topnya adalah mt. Variabel a, v, n, x, dan y adalah bersifat lokal.

 

0	NAME LL ON	Push(display[LL]+ON)
1	LOAD	a:=top; pop;   jika memory[a]=undefined maka error;   push(memory[a]);
2	STORE	v:=top; pop;   a:=top; pop;   memory[a]:=v
3	PUSH V	Push(v)
4	PUSHMT	Push(mt)
5	SETD LL	Display[LL]:=top; pop;
6	POP	n:=top; pop; popn
7	DUP	n:=top; pop; v:=top; pop; pushn(v)
8	BR	a:=top; pop; goto a
9	BF	a:=top; pop; v:=top; pop; jika Bv maka goto a
10	ADD	Untuk operasi 10-16
11	SUB	y:=top; pop;
12	MUL	x:=top; pop;
13	DIVI	push(x op y)
14	EQ	jika overflow atau division by zero maka error
15	LT
16	ORI
17	FLIP	x:=top; pop; y:=top; pop; push(x); push(y);
18	READC	Satu karakter input dibaca dan dipush
19	PRINTC	Catak top sebagai karakter; pop;
20	READI	Baca integer n; push(n);
21	PRINTI	Catak top sebagai integer; pop;
22	HALT	Halt (berhenti)

 Program Model  Kompilator 

Apendik ini mengandung program model kompilator yang dibuat dalam bahasa pemrograman Pascal. Program ini dapat dikompilasi dan dijalankan dengan memakai Turbo Pascal Versi 5.0 ke atas dan bekerja di atas sistem pengoperasian DOS versi 2.0 ke atas. Model kompilator ini dibuat dalam tiga belas unit subprogram Pascal, sehingga jika ada perubahan pada satu unit tidak akan banyak mempengaruhi unit-unit lainnya. Unit-unit ini (berakhiran .pas) adalah sebagai berikut :

• IKI336 - Berfungsi sebagai program utama model kompilator, unit ini memerlukan semua informasi yang berada pada unit-unit lainnya.
• HGLOBAL - Berfungsi mendeklarasikan beberapa variabel global (publik) yang dapat diakses oleh seluruh unit.
• HSYMBOL - Adalah unit pendefinisian beberapa informsi yang dibutuhkan dalam struktur data Tabel Simbol. Dimana tabel simbol ini menyimpan informasi yang berkenaan dengan suatu identifier bise berupa tipe, jenis variabel apakah variabel biasa atau array, prosedur dan sebagainya.
• HPARSGEN - Adalah unit yang mendefinisikan beberapa informasi yang akan dipakai oleh unit PARSER dan GENERATE.
• HMACHINE - Adalah unit yang mendefinisikan beberapa instruksi simulasi yang akan dipakai pada MACHINE untuk menjalankan (mengeksekusi) kode hasil kompilasi.
• HPARSER -   Adalah unit yang mendefinisikan beberapa informasi yang dibutuhkan pada unit PARSER.
• HTKNCODE - Adalah unit yang mendefinisikan kode-kode token.
• SCANNER - Adalah unit yang berperan sebagai penganalisa leksikal, dimana unit ini membaca karakter dan membentuk suatu token. Kemudian token tersebut akan diberikan kepada PARSER yang selanjutnya diproses untuk memeriksa apakah barisan token-token yang ditulis oleh pemrogram sesuai tidak dengan tata-bahasa yang didefinisikan pada HPARSER.