Pohon Penurunan Tata Bahasa Konteks

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. Pohon sintaks / pohon penurunan (syntax tree/derivaton tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel 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:

a.       Rentang Waktu eksekusi

b.      Penanganan Kesalahan

c.       Penanganan Kode

Metode Parsing digolongkan menjadi:

1.      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.

2.      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 :

1.      Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang diperluas terlebih dulu.

2.      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).

-       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. Maka dari itu saya akan memperluas area di simpul kanan.

-     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).

-       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. Maka dari itu saya akan memperluas area di simpul kanan.

-          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”.

     Berikut adalah video saya yang menjelaskan tentang cara pengerjaan soal-soal diatas, saya menyarankan untuk menggunakan headset atau earphone agar lebih jelas ketika mendengar suara saya.

Nama : Shania Risky Agustin
Kelas : 4C
NPM : 1810631170097

REFERENSI

·         https://www.academia.edu/37758551/Pohon_Penurunan