TEKNIK KOMPILASI Bahasa Regular Sekolah Manajemen Informatika dan Komputer (STMIK) Palangkaraya 2012
Tata bahasa reguler Sebuah bahasa dinyatakan regular jika terdapat Finite State
Automata (FSA) yang dapat menerimanya. Ekspresi reguler memungkinkan menspesifikasi atau mendefinisikan bahasa-bahasa Ekspresi reguler memberikan suatu pola (pattern) atau template untuk string dari suatu bahasa. Untai yang menyusun suatu bahasa regular akan cocok (match) dengan pola bahasa itu.
Ekspresi Regular Dalam suatu kompilator, ekspresi regular bisa diaplikasikan
untuk melakukan analisis leksikal yang dikenal dalam program (token). Token-token dalam sautu bahasa pemrograman dinyatakan sebagai ekspresi regular.
Notasi Ekspresi Regular *
Karakter asterik
Bisa tidak muncul Bisa muncul berhingga kali (0-n)
+
Pada posisi superscirpt (di atas)
Minimal muncul satu kali (1-n)
+ atau
Union
Gabungan untai/string
Titik
Konkatenasi, biasanya tanda titik bisa dihilangkan
ᴜ .
Operasi dalam Bahasa Regular Dalam analisis lexical, operasi yang paling penting adalah
union, concatenation, dan closure
Union : penggunaannya sama dengan himpunan. Concatenation : pembentukan string dengan mengambil
sebuah string dari bahasa pertama dan bahasa kedua, dalam semua kemungkinan yang ada.
Operasi dalam Bahasa Regular (Kleene) closure dari bahasa L, dilambangkan dengan L*,
himpunan string dengan hasil gabungan 0 atau lebih L. L0 merupakan "concatenation L sebanyak 0 kali," didefinisikan menjadi {ε} , dan secara induktif, Li adalah
Li - 1 L. Positive closure, dilambangkan L+, sama dengan Kleene
closure, tapi tanpa L0 . ε tidak ada dalam L+ kecuali berada dalam L itu sendiri
Finite State Automata (FSA) model matematika yang dapat menerima input dan
mengeluarkan output Analisis leksikal lebih mudah diimplementasikan pada FSA. Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity.
Finite State Automata (FSA) Finite State Automata dinyatakan oleh 5 tuple M=(Q , Σ , δ , S , F )
Q = himpunan state Σ = himpunan simbol input δ = fungsi transisi δ : Q × Σ S = state awal / initial state , S ∈ Q F = state akhir, F ⊆ Q
Jenis FSA Deterministic Finite Automata (DFA) dari suatu state ada tepat satu state berikutnya untuk setiap
simbol masukan yang diterima Non-deterministic Finite Automata (NFA) dari suatu state ada 0, 1 atau lebih state berikutnya untuk
setiap simbol masukan yang diterima
Finite State Diagram (FSD) Menggambarkan kerja FSA, disebut juga dengan State-
Transition Diagram Lingkaran menyatakan state, Lingkaran bergaris tunggal = state sementara Lingkaran bergaris ganda = state akhir Lingkaran diberi label sesuai dengan nama state
Anak panah menyatakan transisi. Label di anak panah menyatakan simbol input (yg membuat
transisi dari satu state ke state lain)
Finite State Automata (FSA) Contoh pencek parity ganjil
Misal input : 1101 Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil diterima mesin
Misal input : 1100 Genap 1 Ganjil 1 Genap 0 Genap 0 Genap ditolak mesin
Dari contoh tersebut : Q = {Genap, Ganjil} Σ = {0,1} S = Genap F = {Ganjil } Tabel transisinya : Fungsi transisinya : δ(Genap,0) = Genap δ(Genap,1) = Ganjil δ(Ganjil,0) = Ganjil δ(Ganjil,1) = Genap
Tata bahasa reguler & hubungannya sebagai scanner (penganalisis leksikal) Dalam suatu kompilator, ekspresi reguler bisa diaplikasikan
untuk melakukan analisis leksikal. Source code dipindai dan mengidentifikasi unit-unit leksikal yang dikenal dalam program. Unit leksikal tersebut dinamakan token. Token-token pada bahasa pemrograman dinyatakan sebagai ekspresi reguler dan menghasilkan Deterministic Finite Automata (DFA) yg mengenali token mana yg muncul berikutnya pada input.
Tata bahasa reguler & hubungannya sebagai scanner (penganalisis leksikal) Contoh : token identifier : terdiri dari huruf (kecil maupun kapital), bisa diikuti
huruf atau digit, tanpa batas panjang dapat dinyatakan : (huruf)(huruf+digit)*
Huruf berupa A..Z atau a..z Digit berupa 0..9 huruf atau digit q0
huruf
q1
FSA mengenali identifier FSA akan diterjemahkan menjadi kode dlm sebuah bahasa pemrograman
Tata bahasa reguler & hubungannya sebagai scanner (penganalisis leksikal) Contoh : Otomata untuk mengenali keyword then. Otomata memerlukan 5 state, masing-masing melambangkan posisiposisi berbeda pada kata then. Posisi-posisi ini berkorespondensi dgn prefiks kata, mulai dari string
kosong (empty string) di mana tidak ada satu kata yg muncul, sampai satu kata penuh tampil. start
t
h t
e th
n the
then
FSA untuk mengenali keyword then
State awal berkoresponden dgn string kosong. Setiap state mengalami transisi pada huruf berikutnya dari kata then,
berkoresponden dgn prefiks berikutnya.
Contoh : suatu tata bahasa memiliki himpunan simbol terminal/token berikut (ID, PLUS, MINUS, dan INT) token ID untuk karakter huruf a-z, 0-9, token INT untuk digit, token PLUS untuk Penjumlahan dan token MINUS untuk Pengurangan
PLUS
huruf
+
Huruf, Digit
S MINUS
ID
Digit
-
INT Blank
Digit
Contoh FSA untuk token relop dan komentar Misalkan sebuah bahasa memiliki himpunan simbol terminal
token : ‘<’, ‘>’, ‘=’, ‘<=’, ‘>=’, <> Atau bisa dibaca sebagai token : t_L, t_G, t_E, t_LE, t_GE, t_NE (G = greater, L = less, E = equal, N= not) Komentar diawali ’{’ dan diakhiri “}” Setiap scanner menemukan awal komentar atau ‘{’ scanner hanya mengambil simbol yg didapat tanpa menyimpan ke dalam token. Setelah ditemukan akhir komentar atau ‘}’, state di kembalikan ke state awal.
Contoh FSA untuk token operator relasi dan komentar Diagram state untuk himpunan simbol tersebut : =
<
t_L E
t_L
START
> = t_E
>
= t_G
{ }
t_NE
komen tar
t_GE
apa saja selain }
Scanner diimplementasikan sebagai sebuah prosedur yang
dipanggil oleh parser. Contoh prosedur scan sederhana untuk membaca file input dan memberikan token hasilnya. Misal didefinisikan dulu Procedure GetChar yang berguna mengambil sebuah karakter dari input. procedure GetChar begin read(FileInput, Kar); end;
Dimana FileInput : text; Kar : char;
Latihan Lengkapilah potongan coding program tersebut, untuk
mengenali (scanning) token operator-operator logika. Compilator yang digunakan bebas.
Latihan Tentukan Q , Σ, S , F, tabel transisi dan fungsi transisi pada
FSA untuk token operator relasi dan komentar pada slide sebelumnya! Buatlah diagram state untuk sebuah bahasa yang memiliki kompulan token-token sebagai berikut. +
-
/
*
**
<
<=
>
>=
=
<>
integer
identifier
Lakukanlah identifikasi operator relasi pada bahasa C, buatlah
diagram state (FSA)-nya!
