POHON PENURUNAN LATIHAN PARSING

POHON PENURUNAN

LATIHAN PARSING

Sebelum kita membahas tentang pohon derivatif tata bahasa bebas konteks,mari kita sejenak mengulas kembali apa definisi dari tata bahasa bebas konteks. 

Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisissintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasabebaskonteks.

 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 simbol variabel.

• ContohaturanproduksiyangtermasukCFG: 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 bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol non terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Contoh 1

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

 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. 

• Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal (huruf kecil).

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

Proses penurunan atau parsing bisa dilakukandengancarasebagaiberikut

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

• Penurunan terkanan ( rightmost derivation) : simbol variabel terkanan yang diperluas terlebih dahulu

Latihan 1 Parsing/Parse tree

S → AA

A → AAA | a | bA| Ab

No 1. Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbabaaba”.

Hasil:

Setelah kita melakukan penurunan untuk memenuhi untaian “bbabaaba” maka susunlah terminal dari yang paling kiri ke kanan,bukan dari paling kanan ke kiri bukan juga dari paling kanan atau atas.

Latihan 2 Parsing/Parse tree

S → AB

A → Aa| bB

B → a | Sb

No 2. Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”

Setelah kita melakukan penurunan untuk memenuhi untaian “baabaab” maka susunlah terminal dari yang paling kiri ke kanan,bukan dari paling kanan ke kiri bukan juga dari paling kanan atau atas.

Latihan 3 Parsing/Parse tree

S → Ba | Ab

A → Sa | Aab| a

B → Sb| Bba| b

No 3. Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbaaaabb”

Setelah kita melakukan penurunan untuk memenuhi untaian “bbaaaabb” maka susunlah terminal dari yang paling kiri ke kanan,bukan dari paling kanan ke kiri bukan juga dari paling kanan atau atas.

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

Jadi,untuk menunjukan bahwa suatu tatabahasa bebas konteks 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 pada bahasa pemrograman.
• Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinyamenjadiambigu.

Latihan 1 Ambiguitas

Latihan1 Ambiguitas

S →  AB | C

A →  aAb| ab

B →  cBd| cd

C →  aCd| aDd

D →  bDc| bc

No 1 Ambiguitas. Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “aabbccdd”

Cara 1

Cara 2

Setelah kita melakukan penurunan untuk memenuhi untaian “aabbccdd” maka susunlah terminal dari yang paling kiri ke kanan,bukan dari paling kanan ke kiri bukan juga dari paling kanan atau atas.dari hasil ini bisa kita lihat bahwa  ambiguitas itu bisa diselesaikan dengan 2 atau lebih penyelesaian untuk menyelesaikan suatu permasalahan yang sama.Bila suatu permasalahan tidak bisa diselesaikan dengan 2 atau lebih penyelesaian maka aturan produksi tersebut tidak ambiguitas.