1.
TATA BAHASA (GRAMMAR)
Bahasa merupakan himpunan kalimat (baik terhingga maupun tak terhingga). Bahasa dapat
disajikan dengan menyebut kalimatnya satu persatu. Untuk bahasa tak hingga,
penyebutan seperti itu tidak mungkin. Oleh karena itu diciptakan cara penyajian
yang mendeskripsikan bahasa secara efisien. Cara penyajian tersebut adalah Tata Bahasa atau Grammar.
Sebuah Tata Bahasa
(Grammar) didefinisikan sebagai 4 tupel :
G = (Vn, Vt, S, Q)
Vn dan Vt adalah simbol Non Terminal dan Simbol
Terminal.
S adalah sebuah elemen anggota Vn yang disebut Simbol Start.
Q merupakan himpunan Produksi.
Chomsky mengelompokkan Grammar menjadi 4 kelompok :
1.
Tipe nol : UnRestricted
Grammar (Tata Bahasa Tidak Terbatasi)
Tata Bahasa UnRestricted yang tidak merupakan anggota dari klasifikasi lainnya ditandai dengan aturan produksi yang bagian sebelah kirinya lebih panjang dari bagian sebelah kanan. Aturan produksi yang mengandung simbol hampa (^) pasti merupakan Tata Bahasa UnRestricted dan tidak termasuk klasifikasi lainnya.
2
Tipe satu : Context
Sensitive Grammar (Tata Bahasa Tergantung Konteks)
Tata bahasa
ini terdiri dari produksi berbentuk :
a ® b dengan
½a½ <== ½b½
dimana a adalah string dan ½a½ adalah panjang string a demikian juga b adalah string dan ½b½ adalah panjang string b. String adalah merupakan
deretan simbol baik terminal maupun non terminal.
Contoh :
G = ( {S, B, C},
{a, b, c}, S, Q )
Dimana Q terdiri dari
produksi berikut :
1.
S ® aSBC ½ abC
2.
bB ® bb
3.
BC ® bc
4.
CB ® BC
5.
CC ® cc
1.
Tipe dua : Context Free
Grammar ( Tata Bahasa Bebas konteks)
Tata bahasa
ini terdiri dari produksi berbentuk :
a ® b dengan
½a½ <== ½b½
dimana a adalah anggota Vn
sedangkan b adalah string. Berarti Context Free Grammar seluruh produksi
ruas kirinya hanya terdiri dari satu simbol yaitu simbol non terminal.
Contoh :
G = ( {S, C}, {a,
b}, S, Q )
Dimana Q terdiri dari
produksi berikut :
1.
S ® aSa
2.
S ® aCa
3.
C ® b
2.
Tipe tiga : Regular
Grammar
Tata bahasa
ini terdiri dari produksi berbentuk :
a ® b dengan
½a½ <== ½b½
dimana a adalah anggota Vn
dan b mempunyai bentuk aB atau a dengan a anggota Vt
dan B anggota Vn.
Contoh :
G = ( {S, A, B,
C}, {a, b}, S, Q )
Dimana Q terdiri dari
produksi berikut :
1.
S ® aS ½ aB
2.
B ® bC
3.
C ® aC
4.
C ® a
Regular Grammar merupakan
subset dari Context Free Grammar.
Context Free Grammar
merupakan subset dari Context Sensitive Grammar.
Context Sensitive Grammar
merupakan subset dari UnRestricted Grammar.
Definisi : Kompilator (compiler) adalah sebuah program yang membaca suatu program yang
ditulis dalam suatu bahasa sumber (source language) dan menterjemah-kannya
ke dalam suatu bahasa sasaran (target language).
Proses kompilasi dapat digambarkan melalui sebuah
kotak hitam (black box) berikut :
 |
program
sumber kompilator bahasa sasaran |
pesan-pesan kesalahan
(error
messages)
Proses kompilasi dikelompokkan ke dalam dua kelompok
besar :
1. analisa : program sumber dipecah-pecah dan dibentuk menjadi bentuk
antara (inter-mediate representation)
2. sintesa : membangun program sasaran yang diinginkan
dari bentuk antara
Fase-fase proses sebuah kompilasi adalah sebagai
berikut :
program sumber
penganalisa leksikal
(scanner)
 |
penganalisa sintaks
(parser)
 |
pengelola
tabel simbol penganalisa semantik
penanganan kesalahan |
|||||
 |
|||||
 |
|||||
pembangkit
kode
antara |
pengoptimal kode
pembangkit kode
bahasa sasaran
Program sumber merupakan rangkaian karakter. Berikut
ini hal-hal yang dilakukan oleh setiap fase pada proses kompilasi terhadap
program sumber tersebut :
1. Penganalisa leksikal :
membaca program sumber, karakter demi karakter. Sederetan (satu atau lebih)
karakter dikelompokkan menjadi satu kesatuan mengacu kepada pola kesatuan kelompok karakter (token) yang ditentukan dalam bahasa
sumber. Kelompok karakter yang membentuk sebuah token dinamakan lexeme untuk token tersebut. Setiap
token yang dihasilkan disimpan di dalam tabel
simbol. Sederetan karakter yang tidak mengikuti pola token akan dilaporkan
sebagai token tak dikenal (unidentified token).
Contoh : Misalnya pola token
untuk identifier I adalah : I = huruf(huruf½angka)*. Lexeme ab2c dikenali
sebagai token sementara lexeme 2abc atau
abC tidak dikenal.
2. Penganalisa sintaks :
memeriksa kesesuaian pola deretan token dengan
aturan sintaks yang ditentukan dalam bahasa
sumber. Sederetan token yang tidak mengikuti aturan sintaks akan dilaporkan
sebagai kesalahan sintaks (sintax error). Secara logika deretan
token yang bersesuaian dengan sintaks tertentu akan dinyatakan sebagai pohon
parsing (parse tree).
Contoh : Misalnya sintaks
untuk ekspresi if-then E adalah : E ® if L then,
L ® IOA, I = huruf(huruf½angka)*,
O ® <½=½>½<=½>=,
A ® 0½1½...½9. Ekspresi
if a2 < 9 then adalah ekspresi sesuai sintaks; sementara ekspresi if a2 < 9 do atau if then a2B <
9 tidak sesuai. Perhatikan bahwa
contoh ekspresi terakhir juga mengandung token yang tidak dikenal.
3. Penganalisa semantik :
memeriksa token dan ekspresi dari batasan-batasan yang ditetapkan.
Batasan-batasan tersebut misalnya :
a. panjang maksimum token identifier adalah 8 karakter,
b.
panjang maksimum ekspresi tunggal adalah 80 karakter,
c. nilai bilangan bulat adalah -32768 s/d
32767,
d. operasi aritmatika harus
melibatkan operan-operan yang bertipe sama.
4. Pembangkit kode antara :
membangkitkan kode antara (intermediate
code) berdasar-kan pohon parsing. Pohon parse selanjutnya diterjemahkan
oleh suatu penerjemah yang dinamakan penerjemah
berdasarkan sintak (syntax-directed
translator). Hasil penerjemahan ini biasanya merupakan perintah tiga alamat (three-address
code) yang merupakan representasi program untuk suatu mesin abstrak. Perintah tiga alamat bisa berbentuk quadruples (op, arg1, arg2, result), tripels
(op, arg1, arg2). Ekspresi dengan
satu argumen dinyatakan dengan menetapkan arg2
dengan - (strip, dash)
5. Pengoptimal kode : melakukan optimasi
(penghematan space dan waktu komputasi), jika mungkin, terhadap
kode antara.
6. Pembangkit kode : membangkitkan kode dalam
bahasa target tertentu (misalnya bahasa mesin).
