POHON PENURUNAN PARSING/PARSE TREE

April 17, 2020

POHON PENURUNAN PARSING/PARSE TREE

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

Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol non terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampaitidakadayangbelumtergantikan.

Contoh

1. Misalnya terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S, selanjutnya digunakan sebagai simbol awal untuk tata Bahasa bebas konteks adalah S).

S → AB

A → aA | a

B → bB | b

Akan kita gambarkan pohon penurunan untuk memperoleh untai : ‘aabbb’.

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

Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi.

Simbol-simbol variabel (huruf besar) akan menjadi simpul-simpul yang mempunyai anak.

Kalau kita baca simbol terminal yang ada pada gambar dari kiri kekanan akan diperoleh untai ‘aabbb’ :

Proses penurunan atau parsing bisa dilakukan dengan cara sebagai berikut

Penurunan terkiri (leftmost derivation) : simbol variabel terkiri yang diperluas terlebih dahulu

Penurunan terkanan ( rightmost derivation) : simbol variabel terkanan yang diperluas terlebihdahul

2. Misal, terdapat tata bahasa bebas konteks :

S → aAS | a

A → SbA | ba

Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas konteks diatas (‘=>’ bisa dibaca ‘menurunkan’):

Dengan penurunan terkiri:

S => aAS => aSbAS => aabAS => aabbaS => aabbaa,

Dengan penurunan terkanan :

S => aAS => aAa =>aSbAa =>aSbbaa =>aabbaa.

Kita dapat melihat pohon penurunannya pada gambar meskipun proses penurunannya berbeda, namun akan tetap memiliki pohon penurunan yang sama.

3. 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 pemilihanaturanproduksiyangbisamenujuke solusi.

Misalnya sebuah tata bahasa bebas konteks memiliki aturanproduksisebagaiberikut.

S → aB | bA

A → a | aS | bAA

B → b | bS | Abb

AMBIGUITAS

Ambiguitas/ke-dwi artian terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.

Misalkan terdapat tata bahasa bebas konteks :

S → A|B A → a B → a

Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan berikut ini.

S=>A=>a

S=>B=>a

Contoh yang lain, terdapat tata bahasa bebas konteks:

S–>SbS | ScS | a

Kita bisa menurunkan untai ‘abaca’ dalam dua caraberikutini

S=>SbS => SbScS => SbSca => Sbaca => abaca

S=>ScS => SbScS => abScS => abacS => abaca

Pohon Untaian 1

Pohon Untaian 2

Kita bisa melihat bahwa untuk untai yang sama (‘abaca’) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambigu. Jadi,untukmenunjukanbahwasuatutatabahasa bebas konteks ambigu, bisa dilakukan dengan menemukan untai yang memungkinkan pembentukan lebih dari satu pohon penurunan.