KELOMPOK 3 DEPOK

TEKNIK KOMPILASI

Nama Anggota :

DAFTAR ANGGOTA :

NAMA NIM

Husni D.J 0844190060

Eko Kuncoro 0844190033

Lilik Wahyudi 0844190066

BAB 3

Konsep dan Notasi Bahasa

3.1 HIRARKY CHOMSKY

Pada bagian ini akan dibahas beberapa konsep pada Teori Bahasa yang akan kita

perlukan nanti. Teknik Kompilasi sebenarnya bias dianggap sebagai kelanjutan dari

konsep – konsep yang dipelajari dalam Teori Bahasa, dan dalam implementasinya

mengambil sebagian dari konsep – kosep tersebut.

Tata Bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari

himpunan – himpunan variable , symbol – symbol terminal. Symbol awal, yang dibatasi

oleh aturan – aturan produksi. Pada tahun 1959 seorang ahlo yang bernama Noam

Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut

Hirarki Chomsky. Penggolongan tersebut bisa dilihat pada table berikut.

Bahasa Mesin Otomata Batasan Aturan Produksi

Regular / Tipe 3 Finite State Automata

(FSA) meliputi

Deterministic Finite

Automata (DFA) & Non

deterministic Finite

Automata (NFA)

α adalah sebuah symbol

variable

β maksimal memiliki

sebuah symbol variable

yang bila ada terletak di

posisi paling kanan

Bebas Kontes / Context free

Tipe 2

Push Down Automata

(PDA)

α adalah sebuah symbol

variable

Context Sensitive / Tipe 1 Linier Bounded Automata | α | ≤ | β |

Unrestricted/ Phase

Structure / Natural

Language

Mesin Turing Tidak ada batasan

Bisa kita lihat penggolongan di atas berdasarkan pembatasan yang dilakukan pada

aturan produksinya. Aturan produksi merupakan pusat dari tata bahsa, yang

menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi suatu string ke

bentuk lainnya, dan melalui aturan produksi tersebut didefinisikan suatu bahasa yang

berhubungan dengan tata bahasa tersebut. Disini semua tata bahasa dinyatakan dalam

bentuk “ a b “ (bisa dibaca: a menghasilkan b, atau dibaca a menurunkan b), dimana a

menyatakan symbol – symbol oada ruas kiri aturan produksi (sebelah kiri tanda “” )

dan b menyatakan symbol – symbol pada ruas kanan aturan produksi (sebelah kanan

tanda “”, dan bisa disebut juga sebagai hasil produksi). Simbol – symbol tersebut bisa

berupa symbol terminal atau symbol non terminal / variable. Symbol variable / non

terminal adalah symbol yang masih bisa diturunkan, symbol terminal sudah tidak bisa

diturunkan lagi. Symbol terminal biasanya ( dan pada buku ini) dinyatakan dengan huruf

kecil. misal ‘a’,’b’,’c’. symbol non terminal / variable biasanya dinyatakan dengan huruf

besar misal ‘A’, ‘B’, ‘C’.

Dengan menerapkan aturan produksi suatu tata bahasa bisa menghasilkan

sejumlah string. Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh

tata bahasa tersebut.

Contoh aturan produksi :

T a

Bisa dibaca : “T menghasilkan a”

E T | T+ E

Bisa dibaca : “E menghasilkan T atau E menghasilkan T + E “

Simbol ‘|’ menyatakan ‘atau’, biasa digunakan untuk mempersingkat penulisan

aturan produksi yang mempunyai ruas kiri yang sama. Pada contoh di atas :

E T | T+ E

Merupakan pemendekan dari aturan produksi :

E T

E T + E

Bahasa manusia / bahasa alami termasuk kedalam grammar (tata bahasa). Tipe 0 /

unrestricted, dimana tidak ada batasan pada aturan produksinya . misalkan saja :

Abc De

Pada bahasa Context Sensitive, panjang string pada ruas kiri ≤ panjang ruas kanan (| α |

≤ | β | ) . Contoh aturan produksi yang context sensitive :

Ab Def

CD eF

Perhatikan aturan produksi seperti :

S ε

Kita ketahui |S| = 1, sedang | ε | = 0, menurut aturan context sensitive aturan

produksiitu tidak diperkenankan, tetapi di sini kita buat suatu pengecualian, sehingga

S ε dianggap memenuhi context sensitive grammar.

Batasan context sensitive biasanya turut digunakan dalam proses analisis semantic

pada tahapan kompilasi.

Pada bahasan bebasa konteks, batasannya bertambah lagi dengan ruas kiri

haruslah tepat satu symbol variable. Misalnya :

B CDeFg

D BcDe

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser / proses

analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam

tata bahasa bebas konteks ( context free grammar). Yang dideskripsikan secara formal

dengan notasi BNF (Backus Naur Form atau Backus Normal Form).

Pada bahasa regulear, batasannya bertambah dengan ruas kanan maksimal

memiliki sebuah symbol variable yang terletak di paling kanan Artinya, bisa memiliki

symbol terminal saja dalam jumlah tidak dibatasi, tetapi bila terdapat symbol variable.

Maka symbol variable tersebut hanya berjumlah 1 (satu) dan terletak di posisi paling

kanan Misalnya

A e

A efg

A efgH

C D

Bisa kita lihat batasannya makin bertambah dari tipe 0 ke tipe 3. Berdasarkan

keterkaitannya antar tipe bahasa tersebut, bisa pula dilihat secara sederhana pada gambar

3.1

Gambar 3.1 Keterkaitan bahasa pada Hirarki Chomsky

*Perhatikan :

Aturan Produksi seperti

ε Abd

bukan aturan produksi yang legal, karena symbol ε tidak boleh berada pada ruas kiri

Aturan produksi yang ruas kirinya hanya memuat symbol terminal saja seperti

a bd

ab bd

bukan aturan produksi legal (untuk unrestricted grammar sekalipun), karena ruas

kiri haris juga memuat symbol yang bisa diturunkan, sementara contoh di atas ruas kiri

hanya terdiri dari symbol terminal saja padahal sesuai definisinya symbol terminal sudah

tidak bisa diturunkan lagi, berbeda dengan aturan produksi seperti L

aA bd

3.2 DIAGRAM KEADAAN

Diagram keadaan ( state Transition Diagram ) digunakan untuk mendapatkan

token (token adalah symbol terminal pada teori bahasa), yaitu melakukan analisis

leksikal terhadapa program sumber. Misalkan suatu bahasa memiliki himpunan symbol

terminal / token (berikut, (t_PLUS, t_MIN, t_ID, t_INT). Token t_ID (identifier) bisa

berupa nama atau keyword (kata kunci yang sudah didefinisikan oleh suatu bahasa).

Misal terdapat statement :

VAR jumlah : integer

Maka VAR dan integer adalah keyoword , jumlah adalah sebuah nama yang

dideklarasikan sendiri oleh pemrogram. Token t_ID harus diawali dengan karakter huruf

(A-Z, a-z), dan bisa diikuti digit (0-9) atau huruf. Token t_INT harus diawali dengan digit

dan bisa diikuti dengan digit. Blank merupakan bagian program sumber yang diabaikan

(dilewati) saja, misalkan spasi kosong.

Gambar 3.2 Diagram keadaan untuk bahasa di atas

Bisa dilihat diagram keadaan memiliki kemiripan dengan finite state automata. Dengan

menggunakan Diagram keadaan akan mempermudah kita dalam melakukan analisis

leksikal.

3.3 NOTASI BNF

Aturan – aturan produksi dapat dinyatakan dalam bentuk BNF (Backus Naur

Form / Backus Norm Form). Notasi BNF telah banyak dipakai untuk melakukan definisi

formal bahasa pemograman. Beberapa symbol yang dipakan dalam notasi BNF

::= Identik dengan symbol pada aturan produksi

| Idem dengan symbol serupa pada aturan produksi

< > Mengapit symbol variable / non terminal

{ } Pengulangan 0 sampai n kali

T T

*

/

F

Contoh :

Terdapat aturan produksi :

E T | T + E | T- E , T a

Notasi BNF :

E ::= <T> | <T> + <E> | <T> - <E>, T ::= a

3.3 DIAGRAM SINTAKS

Diagram sintaks merupakan alat Bantu dalam pembentukan parser / analisis

sintaksis. Notasi yang terdapat pada diagram sintaks :

Empat persegi panjang melambangkan symbol variable / non terminal

Bulatan melambangkan symbol terminal

Misal terdapat aturan produksi :

T F*T | F/T |F

Diagram sintaksnya dapat dilihat pada gambar 3.3

S

S

S

S

S

S

TAMBAHAN CATATAN DARI BU DIAN

Contoh Diagram Keadaan

Program Hitung Luas_segitiga;Var A,T,Luas : Integer;Begin

Readln (A);Readln (T);Luas := (A*T)*0.5;Write (Luas);

End

Gambar diagram keadaan :

Keyword (Program var, int, begin, readln, end, write)

A, T, luas huruf Huruf (A,T,luas)

Int digit (A,T,luas)

* operan (*) ;

:= Titik dua sama dengan

Gambar diagram Sintaks :

- Simbol VN (Variabel non Terminal)

- Simbol VT (Variabel Terminal)

S

t_id

t_int

t_mul

t_titik dua sama dgn

T_titik

koma dua

sama dgn

Simbol Terminal (VT) Simbol Non Terminal (VN)1) Huruf Kecil 1) Huruf besar 2) Tanda baca 2) huruf s3) Operator 3) Ekspresi / statement4) Keyword

Diagram sintaks merupakan alat bantu dalam pembentukan parser / analisis sintaks. Notasi yang terdapat dalam diagram sintaks :

• Empat persegi panjang melambangkan simbol variabel / non terminal.

• Bulatan melambangkan simbol terminal

Contoh : Terdapat aturan produksi sbb :

T --> F * T \ F / T / FDiagram Syntax :

Contoh :

Begin

If

Ekspresi then

Statement 1;

Else

Statement 2;

End

T T

*

/

F

Diagram Syntax :

Notasi BNF :

Aturan-aturan produksi dapat dinyatakan dalam bentuk BNF (Backus naur Form)

Beberapa simbol yang digunakan dalam notasi BNF

;:= Identik dengan simbol pada aturan produksi

| Menyatakan “atau”

< > Mengapit simbol variabel

{ } Pengulangan 0 sampai n kali

Contoh, terdapat aturan produksi sebagai berikut :

E T | T+E | T-E, T a

Notasi BNF :

E ::= <T> | <T> + <E> | <T> - <E>, T ::= a

EkspresiBegin

else

end

Statement

Statement

Then

if

;

:.