Tata Bahasa Bebas Konteks (POHON PENURUNAN)

Dalam tata bahasa regular grammar akan ditemukan pembatasan pada ruas kanan yang merupakan hasil produksinya. Maka dalam tata bahasa bebas konteks atau context free grammar tidak ditemuka adanya pembatasan. Dalam menurunkan string, simbol-simbol variabel akan mewakili bagian-bagian yang belum diturunkan dalam string tersebut. Dalam tata bahasa regular grammar, bagian yang belum terturunkan terletak pada bagian ujung string, sedangkan pada CFG bisa lebih banyak bagian yang belum terturunkan. Contoh produksi CFG adalah sebagai berikut : 

B → CDeFg

D → BcDe

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator umumnya didefinisikan menggunakan tata bahasa bebas konteks. Terinspirasi dalam bahasa manusia, ilmuwan-ilmuwan menciptaka bahasa pemograman turut serta memberikan grammar, grammar ini disebut Context Free Grammar (CFG). Hasilnya, kompiler suatu bahasa pemograman dibuat lebih mudah dan menghindari ambiguitas ketika parsing bahasa tersebut. Proses parsing merupakan proses pembacaan string dalam bahasa sesuai CFG tertentu, sesuai dengan aturan. 

Pohon(tree) merupakan suatu graph terhubung tidak sirkuler yang memiliki satu simpul(node) atau vertex yang disebut akar. Pohon penurunan atau derivation tree atau parse tree berguna untuk menggambarkan bagaimana memperoleh suatu string dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Setiap simbol diturunkan menjadi terminal sampai tidak ada yang bisa diturunkan lagi. 

Proses penurunan atau parsing bila dilakukan dengan cara sebagai berikut :

1. Penurunan terkiri (leftmost derivation) : Simbol variabel terkiri yang diperluas terlebih dahulu.
2. Penurunan terkanan (rightmost derivation) : Simbol variabel terkanan yang diperluas terlebih dahulu.

                                                     

Soal Latihan 1 Parsing/Parse Tree

S → AA

A → AAA | a | bA | Ab

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

Jawab :

Soal Latihan 2 Parsing/Parse Tree

S → AB

A → Aa | bB

B → a | Sb

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

Soal Latihan 3 Parsing/Parse Tree

S → Ba | Ab

A → Sa | Aab | a

B → Sb | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbaaaabb".

Soal Ambiguitas 

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

Jawab : 

Untuk menjawab soal latihan ini ada dua cara penyelesaian :

Pohon 1

Pohon 2

Untuk pembelajaran lebih lengkapnya bisa di cek video berikut : 

https://drive.google.com/file/d/11GCki0KrssInWsmcdKuNG4ubOJr5nxf7/view?usp=sharing

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