Pohon Penurunan Tata Bahasa Bebas Konteks

"Pohon Penurunan Tata Bahasa Bebas Konteks"

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

Contoh Soal :
1. 
S → AA
A → AAA | a | bA | Ab
Untai yang dicari : bbabaaba

Jawaban :
S => AA => bAA => bbAA => bbaA => bbaAAA => bbaAAA => bbabAAA => bbabaAA => bbabaAbA => bbabaabA => bbabaaba

Pohon Penurunan :

2.
S → AB
A → Aa | bB
B → a | Sb
Untai yang dicari : baabaab
Jawaban :
S => AB => AaB => AaSb => bBaSb => baaSb => baaABb => baabBBb => baabaab

Pohon Penurunan :

3.

S → Ba | Ab

A → Sa | Aab | a

B → Sb | Bba | b

Untai yang dicari : bbaaabb

Jawaban :

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

Pohon Penurunan :

Ambiguitas

Terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda utuk memperoleh suatu untai.

Contoh Soal :
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | ADd
D → bDc | bc
Untai yang dicari : aabbccdd

Jawaban :
(1)
S => AB => AcBd => Accdd => aAbccdd => aabbccdd

Pohon Penurunan :

(2)

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

Pohon Penurunan :

Bisa dilihat diatas ada 2 pohon penurunan yang berbeda untuk memperoleh untai aabbccdd

Video Penjelasan :

Daftar Pustaka :

• https://dinus.ac.id/repository/docs/ajar/bab%2010_file_2013-05-31_080824_dr.r._heru_tjahjana_s.si_m.si__.pdf
• http://apranolo.tif.uad.ac.id/wp-content/uploads/2014/12/TBA_TID_Kelompok-7_TATA-BAHASA-BEBAS-KONTEKS.pdf