PANDUAN PRAKTIKUM INSTITUT KEUANGAN PERBANKAN DAN INFORMATIKA ASIA PERBANAS. Disusun oleh: DR. NIDJO SANDJOJO, M.SC

PANDUAN PRAKTIKUM

TEKNIK KOMPILASI

Disusun oleh: DR. NIDJO SANDJOJO, M.SC

INSTITUT KEUANGAN PERBANKAN DAN INFORMATIKA ASIA PERBANAS JAKARTA SEPTEMBER 2011

Dr. Nidjo Sandjojo, M.Sc

PEMBUATAN KOMPILATOR FRONT END Maksud dan Tujuan Maksud pembuatan kompilator ini adalah untuk mendalami dan memahami teori dan konsep kampilasi Front End

yang diajarkan di kelas.

Adapun

tujuannya adalah agar mahasiswa dapat benar-benar merasakan bagaimana membuat sebuah kompilator sehingga dapat digunakan sebagai acuan untuk pengembangan lebih lanjut.

Alat peraga/bantu 1.

Sebuah komputer PC

2.

Perangkat lunak: Operating System, C Compiler

Kompilator Front End Seringkali fase-fase dalam suatu kompilator di kelompokkan kedalam dua bagian besar, yaitu: front end dan back end. Front end terdiri dari fase-fase atau bagian dari fase yang pada pokoknya tergantung kepada bahasa sumber dan sama sekali tidak tergantung kepada mesin target.

Fase-fase di dalam

kompilator front end pada umumnya terdiri dari: (i) penganalis leksikal; (ii) penganalisis sintaksis; (iii) pembentukan tabel simbol; (iv) penganalisis semantik; (v) pembentukan kode antara; dan (vi) pengendali kesalahan.

Setelah mengetahui konsep umum kompilasi, terutama syntax-directed techniques untuk membentuk suatu kompilator front end, maka perlu ditindak lanjuti dengan pembuatan kompilator sederhana.

Kompilator sederhana tersebut

cenderung merupakan penerjemah atau translator yang ditulis dalam bahasa C

1


dan berfungsi untuk merobah notasi infix menjadi postfix. Penerjemah ini dapat berisi suatu rangkaian ekspresi yang dipisahkan dengan semicolons, ekspresi yang terdiri dari angka, identifiers, dan operator-operator +, -, *, /, div, dan mod. Output dari translator tersebut adalah suatu representasi postfix bagi setiap ekspresi.

2


PENGGABUNGAN BERBAGAI TEKNIK KE DALAM SATU PROGRAM Disini dijelaskan sejumlah cara pembentukan bagian depan dari kompilator (compiler front end) yang berdasarkan sintaks (syntax-directed). Kita telah mengenalkan sejumlah teknik berdasarkan sintak untuk membentuk compiler front end. Untuk merangkum teknik-teknik tersebut, pada bagian ini kita tuliskan program dalam bahasa C yang menerjemahkan notasi infix ke notasi postfix untuk bahasa yang terdiri dari barisan ekspresi yang diakhiri dengan titik-koma. Ekspresi tersebut terdiri dari bilangan-bilangan identifier dan operator +, -, *, /, div dan mod. Output translator tersebut adalah suatu representasi postfix untuk tiap ekspresi. Translator ini merupakan suatu ekstensi dari program yang dikembangkan di bagian terdahulu (Section 2.5 – 2.7 buku Compiler: Principles, Techniques, and Tools). Listing program C selengkapnya ada pada akhir bagian ini.

Diskripsi Tentang Penterjemah Penerjemah

(translator)

tersebut

dirancang

dengan

menggunakan

pola

penerjemahan berdasarkan sintaks (syntax-directed translation) seperti pada Gambar 2.35. Token id menyatakan barisan yang tidak kosong dari huruf-huruf dan angka-anka yang dimulai dengan satu huruf, num adalah barisan angkaangka, dan eof adalah karakter end-of-file. Token-token tersebut dipisahkan oleh barisan spasi (blank), tabulasi dan baris baru (white space). Atribut lexeme dari token id memberikan rangkaian karakter yang membentuk token; atribut value dari token num memberikan bilangan bulat yang dinyatakan oleh num.

3


Gambar 2.35 Spesifikasi penerjemah infix ke postfix

Kode untuk penterjemah ini disusun dalam tujuh modul yang masing-masing disimpan dalam berkas yang terpisah. Eksekusi dimulai pada modul main.c yang terdiri dari pemanggilan terhadap init() untuk inisialisasi yang diikuti dengan pemanggilan pada parse() untuk penterjemahan.

Selebihnya yang

terdiri dari 6 modul terlihat pada Gambar 2.36. Terdapat juga satu file header global.h yang berisi definisi-definisi umum untuk lebih dari satu modul; statement pertama pada setiap modul

#include “global.h”

menyebabkan berkas (file) header dimasukkan sebagai bagian dari modul tersebut. Sebelum diperlihatkan keseluruhan program dari penerjemah, maka setiap modul dibahas terlebih dahulu dan bagaimana modul tersebut dibuat.

4


Gambar 2.36 Modul-modul penerjemah infix ke postfix Modul Analisis Leksikal: lexer.c Penganalisis leksikal adalah suatu bagian program (routine) yang disebut lexan() yang dipanggil oleh pengurai (parser) untuk mencari token. Implementasi dari kerangka kode (pseudo-code) pada Gambar 2.301, routine tersebut membaca input 1 karakter setiap saat dan memberikan token yang telah diketemu-kan kepada pengurai. Nilai dari atribut yang berhubungan dengan token tersebut diberikan pada variabel global tokenval.

Token-token berikut adalah token yang diharapkan diterima oleh pengurai: + - * / DIV MOD ( ) ID NUM DONE

Disini ID merupakan identifier, NUM adalah bilangan, dan DONE adalah karakter end-of-file. Tempat kosong (white space) dihapus oleh peng-analisis 1

Alfred V. Aho dkk: Compiler: Principles, Techniques, and Tools

5


leksikal. Tabel pada gambar 2.37 berikut menunjukkan token dan nilai atribut yang dihasilkan oleh penganalisis leksikal untuk setiap lexeme bahasa sumber.

TOKEN

LEXEME

ATTRIBUTE VALUE

white space sequence of digits

NUM

div

DIV

mod

MOD

other sequences of a letter then letters and digits

ID

end-of-file character

DONE

any other character

that character

numeric value of sequence

index into symtable

NONE

Gambar 2.37 Diskripsi token

Penganalisis leksikal menggunakan routine tabel simbol lookup untuk menentukan apakah suatu lexeme identifier sudah pernah dilihat sebe-lumnya dan routine insert menyimpan satu lexeme baru kedalam tabel simbol. Hal yang juga dilakukan adalah menambahkan satu nilai variabel global lineno setiap saat melihat satu karakter baris baru. Module Parser: parser.c Pengurai dibuat dengan tehnik pada bagian (section) 2.52 Pertama-tama dengan menghilang-kan pengulangan kiri (left-recursion) dari pola penerjemahan pada Gambar 2.35, sehingga tata bahasa yang ditekankan (underlying) dapat diuraikan dengan pengurai turun berulang

(recursive-descent).

ditranformasikan terlihat pada Gambar 2.38.

6

Pola

yang telah


Kemudian dibentuk fungsi untuk unsur bukan terminal (non-terminal) expr, term, dan factor seperti dilakukan pada Gambar 2.243.

Fungsi parse()

mengimplementasikan simbol awal dari tata bahasa, dan memanggil lexan bilamana memerlukan token baru. Pengurai tersebut menggunakan fungsi emit untuk membentuk output dan fungsi error untuk melaporkan suatu kesalahan sintaks. start list expr moreterms

term morefactors

factor

⇒ ⇒ | ⇒ ⇒ | | ⇒ ⇒ | | | | ⇒ | |

list eof expr ; list ε term moreterms + term { print (‘+’) } moreterms - term { print (‘-’) } moreterms ε factor morefactors * factor { print( ‘*’ ) } morefactors / factor { print( ‘/’ ) } morefactors div factor { print (‘DIV’) } morefactors mod factor { print (‘MOD’) } morefactors ε ( expr ) id { print (id.lexeme) } num { print (num.value) }

Gambar 2.38 Pola translasi berdasarkan sintak tanpa pengulangan kiri Module Emitter: emitter.c Module emitter terdiri dari satu fungsi emit(t,tval) yang membentuk output untuk token t dengan nilai atribut tval.

2 3

Alfred V. Aho dkk: Compiler: Principles, Techniques, and Tools Alfred V. Aho dkk: Compiler: Principles, Techniques, and Tools

7


Modul Tabel Simbol: symbol.c dan init.c Modul tabel simbol mengimplementasikan struktur data yang terlihat pada Gambar 2.294. Entry pada array symtable adalah pasangan yang terdiri dari pointer pada array lexeme dan sebuah bilangan (integer) yang menunjukan token yang disimpan.

Operasi insert(s,t) mengembalikan indek symtable untuk

lexeme s yang membentuk token t. Fungsi lookup(s) mengembalikan indek dari entri tersebut pada symtable untuk lexeme s atau 0 bila s tidak ada.

Modul init.c digunakan untuk mengisi symtable dengan kata-kata kunci. Representasi lexeme dan token untuk semua kata-kunci disimpan dalam array keywords, yang mempunyai type yang sama dengan array symtable. Fungsi init() bekerja berurutan melalui array keyword, dengan menggunakan fungsi insert untuk menempatkan kata-kata kunci pada tabel simbol.

Pengaturan

(arrangement) seperti ini memungkinkan kita untuk merobah representasi dari token-token tersebut untuk kata-kunci dengan cara yang mudah.

Modul Kesalahan: error.c Modul error mengelola pelaporan kesalahan, yang sangat sederhana. Bila berhasil diketemukan satu kesalahan sintak, kompilator mencetak pesan yang mengatakan bahwa suatu kesalahan telah terjadi pada baris input yang sedang dibaca dan berhenti. Teknik recovery yang lebih baik mungkin langsung loncat ke titik-koma (semicolon) berikutnya dan melanjutkan penguraian.

Para

mahasiswa dianjurkan untuk memodifikasi teknik tersebut. Sedangkan teknik error recovery yang lebih komplek (sophisticated) dibahas di Bab 45.

4 5

Alfred V. Aho dkk: Compiler: Principles, Techniques, and Tools Alfred V. Aho dkk: Compiler: Principles, Techniques, and Tools

8


Pembuatan Kompilator Pembuatan kode untuk modul-modul sebuah kompilator, seperti yang tertulis pada tujuh file: lexer.c, parser.c, emittter.c, symbol.c, init.c, error.c, dan main.c. File main.c berisi routine utama didalam program C yang memanggil init( ), kemudian parse( ), dan setelah selesai serta sukses exit(0).

Didalam sistem operasi UNIX, kompilator dapat dibuat dengan mengekse-kusi perintah: cc lexer.c parser.c emitter.c symbol.c init.c error.c main.c

atau

dengan

mengkompilasi

secara

terpisah

file-file

tersebut,

dengan

menggunakan: cc -c filename.c

dan menghubungkan (linking) hasil filename.o file-file: cc lexer.o parser.o emitter.o symbol.o init.o error.o main.o

Perintah cc membuat sebuah file a.out yang berisi penerjemah. Pener-jemah tersebut kemudian dapat dicoba dengan mengetik a.out diikuti oleh ekspresi yang diterjemahkan; seperti contoh., 2+3*5; 12 div 5 mod 2;

atau ekspresi apapun yang anda mau.

Listing Berikut adalah listing program dalam bahasa C yang mengimplementa-sikan penerjemah.

Seperti yang terlihat pada berkas (file) header global global.h,

diikuti oleh tujuh file sumber. Untuk kejelasan, program tersebut ditulis dalam suatu cara penulisan bahasa C yang sederhana yang masih tingkat dasar atau pemula.

9


/ ******* global.h ***********************************/ #include <stdio.h> #include

/* load i/o routines */ /* load character test routines */

#define BSIZE 128 #define NONE -1 #define EOS '\0'

/* buffer size */

#define #define #define #define #define

NUM DIV MOD ID DONE

256 257 258 259 260

int tokenval; int lineno;

/* value of token attribute */

struct entry { char *lexptr; int token; };

/* form of symbol table entry */

struct entry symtable[];

/* symbol table */

/***** lexer.c *******************************************/ #include "global.h" char lexbuf[BSIZE]; int lineno = 1; int tokenval = NONE; int lexan() /* lexical analyzer */ { int t; while(1) { t = getchar(); if (t == ' ' || t == '\ t') ; / * strip out white space */ else if (t == '\n') lineno = lineno + 1; else if (isdigit(t)) { /* t is a digit */ ungetc(t, stdin); scanf("%d", &tokenval); return NUM; } else if (isalpha(t)) { /* t is a letter */ int p, b = 0; while (isalnum(t)) { /* t is alphanumeric lexbuf[b] = t; t = getchar (); b = b + 1 if (b >= BSIZE) error (“compiler error”); } lexbuf [b] = EOS;

10

*/


if (t != EOF) ungetc (t, stdin); p = lookup(lexbuf); if (p == 0) p = insert(lexbuf, ID); tokenval = p; return symtable[p].token; } else if (t == EOF) return DONE; else { tokenval = NONE; return t; } } } /*******

parser . c

*************************/

#include "global. h" int lookahead; parse() /* parses and translates expression list { lookahead = lexan(); while (lookahead ! = DONE ) { expr(); match(';'); } }

*/

expr() { int t; term(); while(1) switch (lookahead) { case '+': case '-': t = lookahead; match (lookahead); term(); emit(t, NONE); continue; default: return; } } term() { int t; factor(); while(1) switch (lookahead) { case '*' : case '/' : case DIV: case MOD: t = lookahead; match (lookahead); factor(); emit(t, NONE); continue; default: return;

11


} } factor() { switch (lookahead) { case '(': match ('('); expr(); match(')'); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit (ID, tokenval); match (ID); break; default: error ("syntax error"); } } match(t) int t; { if (lookahead == t) lookahead = lexan(); else error ("syntax error"); } / ******

emitter.c

**********************************/

#include "global.h" emit(t, tval) /* generates output */ int t, tval; { switch(t) { case '+': case '-': case '*': case '/': printf("%c\n", t); break; case DIV: printf("DIV\n"); break; case MOD: printf("MOD\n"); break; case NUM: printf("%d\n", tval); break; case ID: printf("%s\n", symtable[tval].lexptr); break; default: printf("token %d, tokenval %d\n”, t, tval); } } / ********* symbol.c

**********************************/

#include "global.h" #define STRMAX 999 #define SYMMAX 100

/* size of lexemes array /* size of symtable */

*/

char lexemes [STRMAX]; int lastchar = - 1; /* last used position in lexemes */ struct entry symtable[SYMMAX]; int lastentry = 0; /* last used position in symtable */

12


int lookup (s) /* returns position of entry for char s[]; { int p; for (p = lastentry; p > 0; p = p - 1) if (strcmp(symtable[p].lexptr, s) == 0) return p; return 0; } int insert (s, tok) /* returns position of entry char s[]; int tok; { int len; len = strlen(s); /* strlen computes length of if (lastentry + 1 >= SYMMAX) error (“symbol table full”); if (lastchar + len + 1 >= STRMAX) error ("lexemes array full"); lastentry = lastentry + 1; symtable[lastentry].token = tok; symtable[lastentry].lexptr = &lexemes[lastchar lastchar = lastchar + len + 1; strcpy(symtable[lastentry].lexptr, s); return lastentry; } /*********

init.c

s */

for s */

s */

+ 1];

**************************************/

#include "global.h" struct entry keywords[] = { "div", DIV, "mod", MOD, 0, 0 }; init() /* loads keywords into symtable */ { struct entry *p; for (p = keywords; p -> token; p++) insert(p(r) -> lexptr, p -> token); } /**********

error.c **************************************/

#include " global.h" error(m) /* generates all error messages */ char *m; { fprintf (stderr, "line %d: %s\n", lineno, m); exit(1); /* unsuccessful termination */ }

13


/******** main.c ****************************************/ #include "global.h" main() { init(); parse(); exit(0); }

/* successful termination */

/********************************************************/

14


DAFTAR PUSTAKA Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. 1986. Compiler: Principles, Techniques, and Tools. Reading, Massachusetts: Addison-Wesley. Aho, Alfred V., Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2007. Compiler: Principles, Techniques, and Tools. Boston: Pearson Education, Inc. Bornat, Richard. 2008. Understanding and Writing Compilers: A do-it-yourself guide. London: Macmillan Press Ltd. Fisher, Charles, Richard LeBlanc, and Ron Cytron. 1991. Crafting a Compiler with C. Reading, Massachusetts: Addison-Wesley. Louden, Kenneth C. 1997. Compiler Construction: Principles and Practice. Boston: PWS Publishing Company. Sediyono, Eko. 2005. Teknik Kompilasi: Teori dan Praktik. Yogyakarta: Penerbit Andi. Slamet, Sumantri dan Heru Suhartono. 1993. Teknik Kompilasi. Jakarta: PT Elek Media Komputindo, Kelompok Gramedia. Utdirartatmo, Firrar. 2001. Teknik Kompilasi. Yogyakarta. J & J Learning.

15

PANDUAN PRAKTIKUM INSTITUT KEUANGAN PERBANKAN DAN INFORMATIKA ASIA PERBANAS. Disusun oleh: DR. NIDJO SANDJOJO, M.SC

Recommend Documents