Pohon Penurunan (Parsing & Ambiguitas) Tata Bahasa Konteks Automata

A. Pengertian Tata Bahasa Bebas Konteks

Pada tata bahasa bebas konteks/context free grammar (CFG) tidak terdapat pembatasan hasil produksinya. Pada aturan produksi :

A → b

Batasannya hanyalah ruas kiri (A) adalah sebuah simbol variabel.

Contoh aturan produksi yang termasuk CFG :

B → CdeFg
D → BcDe

Seperti halnya pada tata bahasa reguler, sebuah tata bahasa bebas konteks adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa.

B. Pohon Penurunan

Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node)/vertex disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Gambar 1 memberikan contoh sebuah tree yang menguraikan kalimat dalam bahasa Inggris: The quick brown fox jumped over the lazy dog Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol- simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

C. Parsing

Proses Parsing merupakan tahapan analisis sintaksis yang berguna untuk memeriksa urutan kemunculan token. Di dalam mengimplementasikan sebuah metode parsing ke dalam program perlu diperhatikan tiga hal sebagai berikut:

Rentang Waktu eksekusi
Penanganan Kesalahan
Penanganan Kode

Metode Parsing digolongkan menjadi:

· Top – Down

Metode ini melakukan penelusuran dari root/puncak ke leaf/bawah (dari symbol awal ke symbol terminal/symbol awal S sampai kalimat x). metode ini meliputi:

§ Backtrack/backup : Brute Force

§ No Backtrack : Recursive Descent Parser2.

· Bottom – Up

Metode ini melakukan penelusuran dari leaf ke root (dari kalimat x sampai symbol awal S).

Proses penurunan atau parsing bila dilakukan dengan cara sebagai berikut

Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang diperluas terlebih dulu.
Penurunan terkanan (rightmost derivation): simbol variabel terkanan yang diperluas terlebih dahulu.

Contoh :

1.S → AA

A → AAA | a | bA | Ab

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbabaaba”.

Jawaban :

· Buatlah akar dari pohonnya terlebih dahulu yaitu S yang menurunkan AA.

· Turunkan simbol-simbol variabelnya (huruf besar) menuju ke solusi (sesuai dengan string yang diminta).

· Huruf yang berwarna merah adalah string hasil penurunan (string dibaca dari ujung pohon terkiri lalu ke kanan) yaitu “bbabaaba”.

2. S → AB

A → Aa | bB

B → a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”.

Jawaban :

· Buatlah akar dari pohonnya terlebih dahulu yaitu S yang menurunkan AB.

· Turunkan simbol-simbol variabelnya (huruf besar) menuju ke solusi (sesuai dengan string yang diminta).

· Penurunan dapat dilakukan dari kiri terlebih dahulu ataupun dari kanan terlebih dahulu, namun di dalam pengerjaan soal ini saya melakukan penurunannya dari kanan terlebih dahulu. Pada soal sebelumnya saya memperluas ruas kanan karena saya mengerjakan pohon penurunan ini dari kanan, namun pada soal ini saya merasa sulit untuk melakukan hal tersebut. Jadi jawaban penurunan pohon saya seperti gambar dibawah ini. Saya menyarankan agar mengerjakan soal ini seteliti mungkin.

· Huruf yang berwarna merah adalah string hasil penurunan (string dibaca dari ujung pohon terkiri lalu ke kanan) yaitu “baabaab”.

3. S → Ba | Ab

A → Sa | Aab | a

B → Sb | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk

membangkitkan string dengan susunan “bbaaaabb”.

Jawaban :

· Buatlah akar dari pohonnya terlebih dahulu yaitu S yang menurunkan Ba atau Ab. Saya memillih S menurunkan Ab karena string yang diminta huruf terakhirnya adalah b yaitu “bbaaaabb”.

· Turunkan simbol-simbol variabelnya (huruf besar) menuju ke solusi (sesuai dengan string yang diminta).

· Huruf yang berwarna merah adalah string hasil penurunan (string dibaca dari ujung pohon terkiri lalu ke kanan) yaitu “bbaaaabb”.

D. Ambiguitas

Ambiguitas / kedwiartian terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai. Misalkan terdapat dua atau lebih pohon yang memiliki penurunan yang berbeda namun hasil untai/stringnya sama, maka hal itu disebut dengan ambiguitas.

Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik bahasa alami maupun pada bahasa pemograman. Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya menjadi ambigu.

Contoh :

1. S → AB | C

A → aAb | ab

B → cBd | cd

C → aCd | aDd

D → bDc | bc

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “aabbccdd”.

Jawaban :

· Buatlah akar dari pohonnya terlebih dahulu yaitu S yang menurunkan AB dan C. Karena ini ambigu maka bisa terdapat dua atau lebih pohon penurunannya. Disoal ini terdapat 2 pohon, pohon pertama yaitu S menurunkan AB dan pohon kedua S menurunkan C.

· Turunkan simbol-simbol variabelnya (huruf besar) menuju ke solusi (sesuai dengan string yang diminta).

· Penurunan dapat dilakukan dari kiri terlebih dahulu ataupun dari kanan terlebih dahulu, namun di dalam pengerjaan soal ini saya melakukan penurunannya dari kanan terlebih dahulu.

Pohon pertama seperti dibawah ini :

Pohon kedua seperti gambar dibawah ini :

· Huruf yang berwarna merah adalah string hasil penurunan (string dibaca dari ujung pohon terkiri lalu ke kanan) yaitu “aabbccdd”.

Diatas adalah Video Penjelasan dari saya semoga dapat di mengerti dan saya sarankan menggunakan headphone atau earphone agar suara yang terdengar lebih jelas lagi

Dan mohon maaf apabila ada salah pengucapan dalam Bahasa yang kurang baku.