Teori Bahasa dan Automata: Tata Bahas Bebas Konteks (parse tree / pohon penurunan)

Agung Prabowo
4 min readJul 27, 2021

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parse / proses analisis sintaksis. bagian sintaksis dalam suatu kompilator kebanyakan didefinisikan dalam bahasa bebas konteks. Tata bahasa bebas konteks ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.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

batasannya hanyalah ruas kiri (a) adalah sebuah symbol variabel.
Contoh aturan produksi yang termasuk CFG:

B → CDeFg

D → BcDe

Parsing

Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) / vertex yang disebut akar (root) dan dari root memiliki lintasan kesetiap simpul. Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Proses penurunan atau parsing bisa dilakukan dengan cara berikut :

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

Contoh 1 : Parse tree

S → AA

A → AAA|a|bA|Ab

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

Penurunan terkiri :

(‘=>’ bisa dibaca ‘menurunkan’)

S => AA => AAAA => bAAAA => bbAAAA => bbaAAA => bbabAAA => bbabaAA => bbabaAbA => bbabaabA => bbabaaba

Pohon penurunan untuk untaian ‘bbabaaba’

Contoh 2 : Parse tree

S → AB

A → Aa|bB

B → a|Sb

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

Penurunan terkiri :

(‘=>’ bisa dibaca ‘menurunkan’)

S => AB => AaB => bBaB => baaB => baaSb => baaABb => baabBBb => baabaBb => baabaab

Pohon penurunan untuk untaian ‘baabaab’

Contoh 3 : Parse tree

S → Ba|Ab

A → Sa|Aab|a

B → Sb|Bba|b

Buatlah pohon penuruan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbaaaabb”

Penurunan terkiri :

(‘=>’ bisa dibaca ‘menurunkan’)

S => Ab => Aabb => Saabb => Baaabb => Bbaaaabb => bbaaaabb

Pohon penurunan untuk untaian ‘bbaaaabb’

Ambiguitas

Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.

Contoh : Ambiguitas

S → AB|C

A → aAb|ab

B → cBb|cd

C → aCd|aDd

D → bDc|bc

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

cara 1 :

S => AB => AcBb => Accdd => aAbccdd => aabbccdd

Pohon penurunan untuk untaian ‘aabbccdd’

cara 2 :

S => C => aCd => aaDdd => aabDcdd => aabbccdd

Pohon penurunan untuk untaian ‘aabbccdd’

Kita bisa melihat bahwa untuk untai yang sama (‘aabbccdd’) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambigu. jadi, untuk menunjukan sifat ambigu, bisa dilakukan dengan menemukan untai yang memungkinkan pembentukan lebih dari satu pohon penurunan. ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik bahasa alami maupun bahasa pemrograman. bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya menjadi ambigu.

--

--

Agung Prabowo

Interested and learn about programming, web development, and machine learning