Regular Expression (RegEx)

Regular Expression (RegEx)

Regular Expression, sering ditulis/disebut juga Regex / Regexp, adalah deretan karakter spesial yang mendefinisikan sebuah pola dalam pencarian teks. Regular Expressions atau yang sering disebut dengan Regex adalah notasi yang digunakan dalam manipulasi teks dan data, contohnya untuk pada parsing, validasi input, atau pada find and replace text.

Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya. Bahasa-bahasa yang diterima oleh suatu finite state automata bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression).

• Ekspresi regular selanjutnya kita sebut sebagai ER, memungkinkan menspesifikasikan atau mendefinisikan bahasa-bahasa.
• Ekspresi regular memberikan suatu pola (pattern) atau template untuk untai/string dari suatu bahasa.
• Untai yang menyusun suatu bahasa regular akan cocok (match) dengan pola bahasa itu.

Banyak masalah pada perancangan perangkat lunak yang bisa disederhanakan dalam dengan melakukan pengubahan notasi ekspresi regular ke dalam implementasi computer dari finite state automata yang bersangkutan.

Penerapan ekspresi regular misalnya : pencarian (searching) untai karakter (string) pada suatu file, biasanya fasilitas ini ada pada text editor.

Dalam kasus itu dilakukan penerapan finite state automata pada untai-untai yang terdapat dalam file tersebut.

Contoh penerapan yang lain adalah pembatasan data masukan yang diperkenankan, misalnya suatu field masukan hanya menerima input bilangan (0..9). Bisa kita lihat otomatanya pada gambar 1.

Gambar 1. FSA menerima bilangan integer tak bertanda

Bila dalam bahasa Indonesia bisa dikatakan bahwa otomata pada gambar menerima masukan symbol input antara 0 sampai 9 sedang ekspresi regularnya dinyatakan sebagai berikut:

(digit)digit)*

dengan digit adalah 0..9

Dalam suatu kompilator, ekspresi regular bisa diaplikasikan untk melakukan analisis leksikal, yaitu mengidentifikasikan unit-unit leksikal yang dikenal dalam program. Unit leksikal ini biasanya disebut dengan token. Token-token pada suatu bahsa pemrograman kebanyakan tanpa kecuali dinyatakan sebagai ekspresi regular . Misalkan suatu identifier baik huruf besar atau huruf kecil yang kemudian diikuti huruf atau digit, dengan tanpa pembatasan jumlah panjang bisa dinyatakan sebagai:

(huruf)(huruf+digit)*

Contoh otomata pada gambar 2 berguna mengenali identifier, bila huruf A..Z, a..z, dan digit berupa 0..9.

Bila dalam bahasa FORTRAN dibatasi panjang identifier maksimal 6 (enam), maka ekspresi regular untuk identifier pada FORTRAN bisa dinyatakan sebagai:

(huruf)(huruf+digit)⁵

Dalam implementasinya suatu finite state automata akan diterjemahkan menjadi kode dalam sebuah bahasa pemrograman.

Gambar 2. FSA mengenali identifier

Notasi Ekspresi Regular

Notasi dasar Ekspresi Reguler( * ⁺ + È .) yaitu :

* (karakter asterisk), berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n)

⁺ (pada posisi superscript/diatas) berarti minimal muncul satu kali (1-n)

+ atau È berarti union

. (titik) berarti konkatensi, biasanya titik bisa dihilangkan,

misal ab bermakna seperti a.b

Contoh ekspresi regular

(selanjutnya kita singkat ER):

• ER: ab*cc

contoh string yang dibangkitkan : abcc, abbcc, abbbcc, abbbbcc, acc, (b bisatidakmunculataumunculsejumlahberhingga kali)

• ER: 010*

contoh string yang dibangkitkan : 01, 010, 0100, 01000

(jumlah 0 diujung bisa tidak muncul, bisa muncul berhingga kali)

• ER: a*d

contoh string yang dibangkitkan : d, ad, aad, aaad

• ER: a⁺d

contoh string yang dibangkitkan: ad, aad, aaad

(a minimal munculsekali)

• ER: a*Èb*( ‘È’ berarti atau)

contoh string yang dibangkitkan: a, b, aa, bb, aaa, bbb, aaaa, bbbb

• ER: (aÈb)

contoh string yang dibangkitkan: a, b

• ER: (aÈb)*

contoh string yang dibangkitkan: a, b, ab, ba, abb, bba, aaaa, bbbb

(untai yang memuat a atau b)

* perhatikan : notasi ‘È’ kadang dituliskan juga sebagai ‘+’

• ER: 01*+0

contoh string yang dibangkitkan: 0, 01, 011, 0111, 01111,

(string yang berawalan dengan 0, dan selanjutnya boleh diikuti deretan 1)

Bahasa Regular

Misalkan S merupakan sebuah abjad. Kumpulan dari bahasa regular berdasar S didefinisikan secara rekursif sebagai berikut [1] :

a.       Æadalahsebuahbahasa regular

b.      {l} adalahsebuahbahasa regular

c.       untuksetiap a ÎS, {a} merupakanbahasa regular. Disebutjugabahasasingleton

d.      Jika A dan B bahasa regular maka AÈB, A.B, dan A* atau B* merupakanbahasa regular.

e.       TidakadabahasalainberdasarkanS yang regular.

Contoh 1 : MisalkanS = {a,b}, makaberikutinimerupakanbahasa-bahasa regular berdasarkanSyaituÆ , {l},{a},{b},{a,b},{ab},{a,ab,b},{aⁱ | i ³0},  {(ab)ⁱ | i ³ 0}

Hubungan ER dengan FSA

§  Untuk setiap ER ada satu NFA dengan transisi  ε  (NFA ε-move) yang ekivalen. 

§  Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA. 

§  Hubungannya dapat digambarkan sebagai berikut