Tata Bahasa Bebas Konteks Parsing dan Ambiguitas

Tata Bahasa Bebas Konteks Parsing dan Ambiguitas

A.    Parsing

Untuk mengimplementasikan Parser diperlukan TBBK (Context Free Grammar). TBBK adalah sekumpulan simbol-simbol variabel (non-terminal) yang menunjukkan bagaimana menghasilkan untai-untai, yang masing-masing merepresentasikan bahasa. Bahasa yang direpresentasikan dengan simbol-simbol nonterminal tersebut diproses secara rekursif dengan suatu aturan-aturan yang disebut aturan produksi.

Tata bahasa bebas konteks (tipe 2) memiliki elemen:
1. Terminal : simbol dasar yang tidak dapat diturunkan lagi. Terminal disebut juga token.
2. Non terminal : variabel sintaktik yang masih dapat diturunkan lagi.

Pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) yang disebut akar dan dari situ memiliki lintasan ke setiap simpul. Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal.

Proses penurunan atau parsing bisa dilakukan dengan cara:

·         Penurunan terkiri (leftmost derivation). Simbol variabel terkiri yang diperluas terlebih dahulu.

·         Penurunan terkanan (right derivation). Simbol variabel terkanan yang diperluas terlebuh dahulu.

Misal, terdapat tata bahasa bebas konteks:
S → aAS | a
A → SbA | ba
Untuk memperoleh untai ‘aabbaa’ :
Simbol ( => ) dibaca menurunkan
• Dengan penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa
• Dengan penurunan terkanan: S => aAS => aAa => aSbAa => aSbbaa => aabbaa
Meskipun proses penurunan berbeda, namun akan tetap memiliki pohon penurunan yang sama.

Biasanya persoalan yang diberikan berkaitan dengan pohon penurunan, adalah untuk mencari penurunan yang hasilnya menuju kepada suatu untai yang ditentukan. Dalam hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi.

B.     Ambiguitas

Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda utuk memperoleh
suatu untai. Misal terdapat tata bahasa bebas konteks:
S → SbS | ScS | a
Untuk memperoleh untai ‘abaca’

Cara pertama:
S >> SbS >> SbScS >> SbSca >> Sbaca >> abaca

Cara kedua:
S => ScS => SbScS => abScS => abacS => abaca

Contoh Soal :

1. S -> AA
A -> AAA | a | bA| Ab
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “bbabaaba”

Jawab:

2. S -> AB
A -> Aa| bB
B -> a | Sb
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “baabaab”

Jawab :

3. S -> Ba | Ab
A -> Sa | Aab| a
B -> Sb| Bba| b
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “bbaaaabb”

Jawab :

4. S -> AB | C
A -> aAb| ab
B -> cBd| cd
C -> aCd| aDd
D -> bDc| bc
Buatlah pohon penurunan dari himpunan produksi di atas untuk membangkitkan string dengan susunan “aabbccdd”.

Jawab :

Video penjelasan :