pohon pnurunan

POHON PENURUNAN

1. CONTEXT FREE GRAMMAR (CFG)

• Pada tata bahasa bebas konteks / Context Free Grammar (CFG) tidak terdapat pembatasan hasil produksinya. Beda halnya dengan tata bahasa reguler yang ada pembatasan pada ruas kanan atau hasil produksinya.

• Contoh aturan produksi yang termasuk tata bahasa reguler :

S 􀃆 abA | baB

A 􀃆 Bs

B 􀃆 As

Bagian yang belum terturunkan selalu terjadi pada ujung.

• Contoh aturan produksi yang termasuk CFG :

B 􀃆 CdeFg

C 􀃆 BcDe

Bagian yang belum terturunkan bisa terjadi dimana saja.

• CFG merupakan suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa

• CFG menjadi dasar dalam pembentukan suatu parser (proses analisis sintaksis) dimana bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam CFG

2. PARSING

• Pohon penurunan (derivation tree / parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal

• Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

• Misal terdapat CFG dengan aturan produksi (dengan simbol awal S) :

S 􀃆 AB

A 􀃆 Aa | a

B 􀃆 Bb | b

Akan digambarkan pohon penurunan untuk memperoleh untai ‘aabbb’.

Pada pohon tersebut simbol awal S akan menjadi akar (root).

Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi.

Simbol-simbol variabel akan menjadi simpul-simpul yang mempunyai anak.

Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal, seperti gambar berikut :

S

A

B

a

A

b

B

b

B

b

a

• Proses penurunan / parsing dapat dilakukan dengan 2 cara :

- Penurunan terkiri (leftmost derivation)

Simbol variabel terkiri yang diperluas terlebih dulu

- Penurunan terkanan (rightmost derivation)

Simbol variabel terkanan yang diperluas terlebih dulu

21

• Contoh :

Diberikan CFG : (‘􀃆’ dibaca ‘menurunkan’)

S 􀃆 Aas | a

A 􀃆 SbA | ba

Untuk memperoleh untai ‘aabbaa’ dari CFG :

- Penurunan terkiri (leftmost derivation)

S 􀃆 Aas 􀃆 aSbAS 􀃆 aabAS 􀃆 aabbaS 􀃆 aabbaa

- Penurunan terkanan (rightmost derivation)

Simbol variabel terkanan yang diperluas terlebih dulu

S 􀃆 Aas 􀃆 aAa 􀃆 aSbAa 􀃆 aSbbaa 􀃆 aabbaa

Proses penurunannya berbeda tetapi akan diperoleh pohon yang sama :

S

S

b

a

S

b

a

a

a

A

S

A

b

S

a

B

a

B

B

a

B

B

b

b

S

A

b

B

a

a

b

• Biasanya persoalan yang berkaitan dengan pohon penurunan adalah mencari penurunan yang hasilnya menuju kepada suatu untai yang ditentukan yang dalam hal ini perlu dilakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi

• Contoh : CFG

S 􀃆 Ab | Ba

A 􀃆 a | As | Baa

B 􀃆 b | Bs | Abb

Berikut pohon penurunan untuk memperoleh string ‘aaabbabbba’

3. AMBIGUITAS (Kedwiartian)

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

• Misal terdapat CFG :

S 􀃆 A | B

A 􀃆 a

B 􀃆 a

22

Untuk memperoleh untai ‘a’ bisa dengan 2 penurunan, yaitu :

- S 􀃆 A 􀃆 a

- S 􀃆 B 􀃆 a

• Misal : CFG

S 􀃆 SbS | ScS |a

Untuk memperoleh untai ‘abaca’ bisa dengan 2 cara, yaitu :

S

S

S

b

a

S

c

S

a

- S 􀃆 SbS 􀃆 SbScS 􀃆 SbSca 􀃆 Sbaca 􀃆 abaca

S

a

- S 􀃆 ScS 􀃆 SbScS 􀃆 abScS 􀃆 abacS 􀃆 abaca

S

S

S

a

c

b

S

a

S

a