Dalam Penerapan Ekspresi Reguler: Ekspresi regular biasanya disebut ER, memungkinkan: ................

Dalam penerapan Ekspresi Reguler: Ekspresi regular memberikan suatu pola atau template untuk ..............

Dalam Penerapan Ekspresi Reguler: Untai yang menyusun suatu bahasa regular akan cocok dengan:

Perhatikan Gambar di atas, gambar tersebut merupakan contoh Penerapan Ekspresi Reguler untuk:

Dalam suatu kompilator, Ekspresi regular bisa diaplikasikan untuk melakukan analisis leksikal, yaitu mengidentifikasikan unit-unit leksikal yg dikenal dalam program. Unit leksikal ini biasa disebut

Dalam Penterjemahan FSA menjadi Kode Program: Bila pada bahasa FORTRAN dibatasi panjang identifier maksimal 6, maka ekspresi regular untuk identifier pada FORTRAN bisa dinyatakan sebagai:

Manakah berikut ini yang bukan merupakan penulisan Notasi Ekspresi Reguler?

Manakah yang merupakan Urutan prioritas operator tertinggi dalam ekspresi regular?

Perhatikan gambar di atas, gambar tersebut merupakan"

Tata Bahasa Regular (FSA) bisa kita konstruksikan dengan :

Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunan semua untai yang menggerakkannya dari state awal ke

Dalam batasan Aturan Produksi untuk Bahasa Regular:

α→β (dibaca α menghasilkan β)

α adalah sebuah simbol variabel.

β maksimal memiliki sebuah simbol variabel yang terletak di

Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):

•α atau β bisa berupa simbol terminal atau non-terminal/variabel.

•Simbol variabel/non-terminal adalah simbol yang masih bisa diturunkan. Biasanya dinyatakan dengan:

Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):

•Simbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan dengan

•Suatu tata bahasa (grammar) didefinisikan dengan 4 tupel (G={V, T, P, S}) dimana:

→V=

Dalam mengkontruksi aturan produksi tata bahasa regular dari suatu finite state automata, perlu kita ingat yang menjadi perhatian kita adalah state-state yang bisa menuju ke

•Misalnya kita tentukan simbol awal adalah S, kita identikan simbol S dengan state awal q₀. dari q₀ mendapat input a menjadi q₁.

•E Kita identikkan dengan q₁

•Bisa kita tuliskan sebagai aturan produksi:

Perhatikan gambar di atas:

•Bisa kita lihat hasil pada gambar tersebut akan berkorelasi S dengan q₀, B dengan q₁, dan C dengan q₂.

•Kita lihat S→b, maka kita buat state akhir adalah:

•Jika kita identikan q₂ sebagai A dan q₃ sebagai B.

–dari q₂ mendapat input a tetap ke q₂,

–dari q₃ mendapat input b tetap ke q₃, bisa kita tuliskan:

Dalam Hirarki Chomsky Bahasa Reguler/Type 3 mesin Otomata : Finite State Otomata (FSA) memiliki batasan aturan produksi:

Dalam Hirarki Chomsky Bahasa Untresticted/Phase Structural/Natural Language/Type 0 mesin Otomata : mesin turing memiliki batasan aturan produksi:

Dalam Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis.

Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam .....

Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasil produksinya, maka pada tata bahasa bebas konteks/context free grammar, selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. Pada aturan produksi:a–>b maka:

Suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) /vertex yang disebut akar (root) dan dari root memiliki lintasan ke setiap simpul disebut:

•Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi ....

Misalnya terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S, selanjutnya digunakan sebagai simbol awal untuk tata bahasa bebas konteks adalah S).

S –> AB

A –> aA | a

B –> bB | b

Manakah pernyataan berikut yang salah?

Perhatikan gambar di atas, gambar di atas merupakan Pohon Penurunan untuk untai .....

Ambiguitas/ke-dwi artian terjadi bila terdapat lebih dari satu pohon penurunan yang ......

Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik bahasa alami maupun pada bahasa pemrograman.

Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya menjadi

Penyederhanaan CFG: Untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yg memiliki kerumitan yang tidak perlu atau.........

S→ AB | a

A → a

Aturan S→ AB tidak berarti karena B

Aturan Produksi berikut:

nS → A

A → B

B → C

C → D

D → a | A

Memiliki kelemahan yaitu terlalu panjang jalannya padahal berujung pada S → a, D → A juga menyebabkan.....

Produksi Useless :

Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan:

Perhatikan penurunan berikut:

S → aSa | Abd | Bde

A → Ada

B → BBB | a

-Simbol A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

-Konsekuensi no 1, aturan produksi S →

Prinsip penyederhanaan adalah: Prinsipnya setiap kali melakukan penyederhanan kita periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah.........

S → Sb

S → C

C → D

C → ef

D → dd

Kita lakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal2 ( ‘→’ dibaca ‘menjadi’):

C → D => C → dd

S → C => S → dd | ef

Sehingga disederhanakan menjadi :

manakah yang salah?

Sederhanakan dengan menghilangkan Unit

S → Sb

S → C dd I ef

C→ ef

D→ dd

Hasil penyederhanaanya adalah:

Penghilangan Produksi Unit:

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalnya : A → B,

C → D.

Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan.

Penyederhanaan ini dilakukan dengan melakukan

Untuk penghilangan Produksi Unit berikut:

S → Cba | D

A → bbC

B → Sc | ddd

C → eA | f | C

D → E | SABC

E → gh

Penggantian yang dilakukan :

D → E => D → gh

C → C dihapus

S → D => S → gh | SABC

Sehingga aturan produksi setelah disederhanakan :(manakah yang salah?)

Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju ........

Dalam Prinsip Penghilangan produksi ε. Prinsip penggantiannya bisa dilihat kasus berikut :

S → bcAd

A → ε

Pada kasus di atas A nullable, serta A → ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi :

S → bcd

Untuk bentuk produksi sebagai berikut:

S → bcAd

A → bd | ε

Pada kasus diatas A nullable, tapi A → ε

bukan satu2nya produksi dari A, maka hasil

penyederhanaan menjadi:

Untuk Produksi:

S → AB

A → abB | aCa | ε

B → bA | BB | ε

C → ε

Variabel yang nullable A, B, C. Dari S → AB, maka S juga

nullable. Kita lakukan penggantian :

A → aCa => A → aa

B → bA => B → bA | b

B → BB => B → BB | B

A → abB => A → abB | ab

S → AB => S → AB | A | B | ε

C → ε, B → ε, A → ε dihapus

Perhatikan : untuk penggantian S → AB kita tetap mempertahankan produksi S → ε, karena S merupakan .....

Perhatikan Bagan Penyederhanaan di Atas, Kota kosong yang berisi tandatangan tersebut berisi.....

Lakukan penghilangan aturan produksi unit, useless, dan ε dari tata bahasa bebas konteks berikut :

S → a | aA | B | C

A → aB | ε

B → Aa

C → cCD

D → ddd

Penghilangan Produksi ε :

A → ε dihilangkan, shg :

A → aB

B → Aa | a

S → a | aA | B | C

Penyederhanaannya Menjadi :

Penghilangan Produksi Useless :

1.C tidak memiliki penurunan, shg C → cCD dihilangkan

2.S → cCD dihilangkan

3.Konsekuensi no 2, D → ddd dihilangkan

Sehingga menjadi :

Penghilangan Produksi Unit :

S → B => S → Aa | a

S → C => S → cCD

Sehingga menjadi :

S → a | aA | Aa | cCD

A → aB

B → Aa | a

C → cCD

D → ddd

Penghilangan Produksi ε :

A → ε dihilangkan, sehingga :

B → bA => B → b

B → ε dihilangkan, shg :

S → aB => S → aB | a

S → aaB => S → aaB | aa

Sehingga Menjadi :

Dalam Penghilangan Produksi Unit :

Tidak ada karena semua aturan produksi tidak ada yang ruas kiri dan kanannya mempunyai .......

Dalam kasus Penghilangan Produksi Useless :

Karena tidak ada yg redundan dan semua aturan produksinya sudah sederhana, maka hasil dari penghilangan produksi useless =

Perhatikan Gambar di Atas:

Gambar tersebut merupakan bagan untuk: