BAB I

PENDAHULUAN

A. Latar Belakang

Komputer mengikuti sejumlah prosedur sistematis atau algoritma

yang dapat diaplikasikan untuk serangkaian input (string), yang

menyatakan integer dan menghasilkan jawaban setelah sejumlah berhingga

langkah. Teori otomata adalah studi tentang peralatan atau “mesin”

komputasi abstrak, yang dapat didefinisikan secara matematis. Tahun

1930-an Alan Turing telah mempelajari mesin abstrak yang memiliki

kemampuan seperti komputer sekarang (dalam hal apa yang dihitung).

Mesin abstrak merupakan model teoritis dari perangkat keras atau

perangkat lunak yang digunakan dalam teori otomata.

Teori bahasa merupakan suatu gagasan mendasar dalam komputasi

yang menjadi tools untuk mengenali persoalan. Gagasan dasar tersebut

dimodelkan dengan simbol-simbol yang merepresentasikan juga suatu

fungsi dari komputer digital. Teori bahasa pada awalnya lebih diarahkan

untuk mengenali suatu tata bahasa dan dapat mendefinisikan spesifikasi

formal dari tata bahasa tersebut. Sehingga pada akhirnya dapat

didefinisikan langkah-langkah algoritmik dalam pemrosesan tata bahasa.

Context free grammer (tata bahasa) dan pushdown automata

digunakan dalam spesifikasi bahasa komputer (pemrograman, markup,

kamus data, query, perintah, script, printer). Dalam parser, bagian

kompilator yang memriksa kebenaran sintaks program. Pemahaman

pushdown automata sangat menyederhanakan proses parsing. Proses

parsing yang berlangsung sangat cepat adalah berkat pemahaman

mendalam teknik parsing bebasis pada pengetahuan mengenai context free

grammer.

1

B. Rumusan Masalah

Dalam pembahasan materi mengenai Pohon Penurunan, terdapat beberapa

rumusan masalah. Diantaranya yaitu :

a. Apa yang dimaksud dengan pohon penurunan?

b. Apa saja cakupan bahasan dalam materi pohon penurunan?

C. Tujuan

Terdapat tujuan dalam materi mengenai Pohon Penurunan, yaitu :

a. Mengetahui dan memahami pengertian dari pohon penurunan.

b. Mengetahui dan memahami cakupan bahasan dalam materi pohon

penurunan seperti context free grammar, parsing, dan ambiguitas.

2

BAB II

PEMBAHASAN

A. Pohon Penurunan (Derivation Tree)

Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang

memiliki satu simpul (node) / vertex  disebut akar (root) dan dari situ memiliki

lintasan ke setiap simpul. Pohon sintaks / pohon penurunan (syntax

tree/derivaton tree/parse tree) berguna untuk menggambarkan bagaimana

memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol

variabel menjadi simbol-simbol terminal. Setiap simbol variabel diturunkan

menjadi terminal, sampai tidak ada yang belum tergantikan.

Derivation tree / Pohon Penurunan, disebut juga derivation (parse)

tree : root dari pohon penurunan adalah simbol awal, sedangkan node (daun)

dari pohon penurunan adalah simbol-simbol non terminal atau terminal dari

tata bahasa tersebut atau kemungkinan symbol Ɛ.

Pohon urai (pohon penurunan) untuk menampilkan penguraian, dapat

dilakukan dengan membentuk pohon urai (sayangnya, urutan penguraian tidak

terlihat). Contoh pohon urai :

3

Contoh penurunan :

Misalkan diketahui sebuah context free grammar G3 dengan aturan produksi

sebagai berikut :

E → E + E

E → E - E

E → (E)

E → V

V → x

V → z

V → y

Bagaimana cara menurunkan string x+(y-z)? Kita bisa membuat pohon

penurunan sebagai berikut :

String x+(y-z) diperoleh dengan cara membaca node daun) dari cabang paling

bawah kiri ke kanan.

4

5

B. Latar Belakang Context Free Grammar (CFG)

Terinspirasi dari bahasa natural manusia, ilmuwan-ilmuwan ilmu

komputer yang mengembangkan bahasa pemrograman turut serta memberikan

grammar (pemrograman) secara formal. Grammar ini diciptakan secara bebas-

konteks dan disebut Context Free Grammar (CFG). Hasilnya, dengan

pendekatan formal ini, kompiler suatu bahasa pemrograman dapat dibuat lebih

mudah dan menghindari ambiguitas ketika parsing bahasa tersebut. Contoh

desain CFG untuk parser, misal : B -> BB | (B) | e untuk mengenali bahasa

dengan hanya tanda kurung {‘(’,’)’} sebagai terminal-nya. Proses parsing

adalah proses pembacaan string dalam bahasa sesuai CFG tertentu, proses ini

harus mematuhi aturan produksi dalam CFG tersebut.

C. Tata Bahasa Bebas Konteks (Context Free Grammar)

Context Free Grammar (CFG)/ Bahasa Bebas Konteks adalah sebuah tata

bahasa dimana tidak terdapat pembatasan pada hasil produksinya. Context

Free Grammar ( CFG ) merupakan tata bahasa yang mempunyai tujuan sama

seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk

menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah

bahasa. Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasil

produksinya, maka pada tata bahasa bebas konteks / context free grammar,

selanjutnya disebut CFG, tidak terdapat pembatasan hasil produksinya. Pada aturan

produksi :

α → β

Batasannya hanyalah ruas kiri (α) adalah sebuah simbol variabel. Contoh

aturan produksi yang termasuk CFG :

B→ CDeFg

D → BcDe

Dimana string dari terminal dan atau nonterminal dapat berisi:

Terminal saja

Nonterminal saja

6

Kombinasi terminal dan nonterminal

Empty string

Harus ada minimal sebuah nonterminal S terletak disebelah kiri. Agar

tidak terjadi kekacauan antara terminal dan nonterminal, maka selalu dipakai

huruf kecil untuk terminal dan huruf kapital untuk nonterminal.

Seperti diketahui, pada saat menurunkan suatu string, symbol-simbol

variable akan mewakili bagian-bagian yang belum yang belum terturunkan

dari string tersebut. Bila pada tata bahasa regular, bagian yang belum

terturunkan tersebut selalu terjadi pada suatu ujung, pada tata bahasa bebas

konteks bisa terdapat lebih banyak bagian yang belum terturunkan itu dan bisa

terjadi dimana saja.

Ketika penurunan itu sudah lengkap, semua bagian yang belum

terturunkan telah diganti oleh string-string (yang mungkin saja kosong) dari

himpunan symbol terminal. Bahasa bebas konteks menjadi dasar dalam

pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam

suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebas konteks.

CFG mempunyai 4 tuple, yaitu G=(V,Σ,R,S), dimana :

V adalah himpunan terbatas dari variable (non terminal).

Σ adalah himpunan terbatas dari terminal. Σ V =

R adalah himpunan terbatas dari rules atau productions (menggambarkan

hubungan antara urutan terbatas variabel dan terminal).

S adalah symbol (variabel) awal digunakan untuk mewakili seluruh

kalimat/ program. S ⋲ V

D. Parsing

Context Free Grammar ( CFG ) menjadi dasar dalam pembentukan suatu

parser/ proses analisis sintaksis. Bagian sintaks dalam suatu kompilator

kebanyakan di definisikan dalam tata bahasa bebas konteks. Pohon penurunan

7

(derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol

variabel menjadi simbol-simbol terminal setiap simbol variabel akan di

turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Misal terdapat tata bahasa bebas konteks dengan aturan produksi (simbol

awal S, selanjutnya di dalam bab ini 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’.

Gambar 1. Pohon Penurunan untuk untai ’aabbb’

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

penurunan dipilih aturan produksi yang menuju solusi. Simbol-simbol variabel

akan menjadi simpul-simpul yang tidak mempunyai anak yang akan menjadi

8

simbol terminal. Kalau kita baca simbol terminal yang ada pada gambar 1 dari kiri

ke kanan akan diperoleh untai ’aabbb’.

Proses penurunan atau parsing bisa dilakukan dengan cara :

1. Penurunan terkiri (leftmost derivation) yaitu simbol variabel terkiri yang

diperluas terlebih dahulu.

2. Penurunan terkanan (rightmost derivation) yaitu simbol variabel terkanan

yang diperluas terlebih dahulu.

Misalkan terdapat tata bahasa bebas konteks :

S → aAS │a

A → Sba │ba

Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas konteks di atas (‘→’ bisa

dibaca menurunkan) :

1. Dengan penurunan terkiri: S → aAS → aSbAS → aabAS → aabbaS →

aabbaa

2. Dengan penurunan terkanan :S → aAS → aAa → aSbAa → aSbbaa →

aabbaa

Kita lihat pohon penurunannya pada gambar 2. Meskipun proses penurunannya

berbeda tetapi akan tetap memiliki pohon penurunan yang sama.

9

Gambar 2. Pohon Penurunan untuk untai ’aabbaa’

Biasanya persoalan yang diberikan berkaitan dengan pohon penurunan adalah

untuk mencari penurunan yang hasilnya menuju pada suatu untai yang ditentukan.

Dalam hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang

bisa menuju ke solusi.

E. Metode Parsing

Metode parsing perlu memperhatikan 3 hal:

a. Waktu Eksekusi

b. Penanganan Kesalahan

c. Penanganan Kode

Parsing digolongkan menjadi:

1. Top-Down

Penelusuran dari root ke leaf atau dari simbol awal ke simbol terminal

metode ini meliputi:

a. Backtrack/backup : Brute Force

Memilih aturan produksi mulai dari kiri

10

Meng-expand simbol non terminal sampai pada simbol

terminal

Bila terjadi kesalahan (string tidak sesuai) maka dilakukan

backtrack

Algoritma ini membuat pohon parsing secara top-down,

yaitu dengan cara mencoba segala kemungkinan untuk

setiap simbol non-terminal

Contoh suatu language dengan aturan produksi sebagai

berikut

S aAd | aB

A b | c

B ccd | ddc

Misal ingin dilakukan parsing untuk string ‘accd’

11

Kelemahan dari metode-metode brute-force

Mencoba untuk semua aturan produksi yang ada sehingga menjadi lambat

(waktu eksekusi)

Mengalami kesukaran untuk melakukan pembetulan kesalahan

Memakan banyak memakan memori, dikarenakan membuat backup lokasi

backtrack

Grammar yang memiliki Rekursif Kiri tidak bisa diperiksa, sehingga

harus diubah dulu sehingga tidak rekursif kiri, Karena rekursif kiri akan

mengalami Loop yang terus-menerus

Contoh:

Terdapat grammar/tata bahasa G = (V,T,P,S), dimana V= (“E”,”T”,”F”) .

Simbol NonTerminal (variable).

T= (“i”,”*”,”/” ,”+”,”-”) Simbol Terminal

S=”E” Simbol Awal / Start simbol

String yang diinginkan adalah i * i

Aturan produksi (P) yang dicobakan adalah :

1. E T | T + E | T – E

T F | F * T | F / T

F i

accept (diterima)

2. E T | E+T | E-T

T F | T* F | T / F

F i

accept (diterima)

Meskipun ada rekursif kiri, tetapi tidak diletakkan sebagai aturan yang paling kiri

3. E E+T | E-T | T

T T* F | T / F | F

F i

12

Rekursif kiri, program akan mengalami loop

4. No backtrack : Recursive Descent Parser

a. Parsing dengan Recursive Descent Parser

Salah satu cara untuk meng-aplikasikan bahasa context free

Simbol terminal maupun simbol variabelnya sudah bukan

sebuah karakter

Besaran leksikal sebagai simbol terminalnya, besaran syntax

sebagai simbol variablenya/ non terminalnya

Dengan cara penurunan secara recursif untuk semua variabel

dari awal sampai ketemu terminal

Tidak pernah mengambil token secara mumdur (back tracking)

Beda dengan turing yang selalu maju dan mundur dalam

melakukan parsing

b. Aturan produksi menggunakan Recursive Descent Parser

Semua simbol variabel dijadikan prosedur/fungsi

Jika beretemu simbol terminal pada aturan produksi, maka

panggil prosedurnya

Penelusuran bersifat top down mengikuti sintaks sesuai pola

pada diagram sintaks

Karena memakai prosedur yang rekursif maka dipakai

recursive stacking yang hampir sama dengan metode top down

parsing dengan brute force.

Urutan produksi direalisasikan dengan menggunakan urutan

dari pemanggilan fungsi / prosedur.

13

Fungsi/prosedur ditulis untuk setiap non terminal dari suatu

produksi. Setiap fungsi/prosedur akan melemparkan nilai benar

atau salah bergantung pada apakah fungsi tersebut mengenali

substring yang diterima sebagai ekspansi dari non terminal.

c. Contoh :

Grammar dengan BNF :

<program> ::= t_PROG t_ID t_SEMICOL <block> t_DOT

<block> ::= t_BEGIN <statement> {t_SEMICOL <statement>}

t_END

<statement> ::= t_ID t_ASS <simple exp> |

t_IF <exp> t_THEN <statement>|

t_IF <exp> t_THEN <statement> t_ELSE

<statement>

<exp> ::= <simple_exp> t_EQ <simple exp> |

<simple_exp> t_LT <simple_exp>|

<simple_exp> t_GT <simple_exp>

Dst…….

2. Bottom-Up

Metode ini melakukan penelusuran dari leaf ke root. Salah satu contoh

menarik dari parsing bottom-up adalah parsing pada grammar preseden

sederhana (GPS). Prosedur Parsing Grammar Preseden Sederhana :

1. Membuat tabel 3 kolom dengan label : sentensial dan relasi, handel,

dan ruas kiri produksi.

2. Menuliskan kalimat (atau sentensial) yang diselidiki pada baris

pertama kolom pertama.

3. Dengan menggunakan tabel relasi preseden, mencantumkan relasi

preseden antara setiap dua simbol yang bertetangga.

14

4. Menentukan handel dari sentensial tersebut. Handel adalah string yang

dibatasi “¬“ terakhir dan “<–>“ pertama jika dilakukan penelusuran

dari kiri atau yang saling mempunyai relasi “<–>“. Handel tersebut

pastilah merupakan ruas kanan produksi, karena itu tentukan ruas kiri

dari handel tersebut.

5. Mengganti handel dengan ruas kiri produksinya. GOTO 3.

6. Kalimat yang diselidiki adalah benar dapat diderivasi dari simbol awal

jika kolom “ruas kiri produksi” menghasilkan simbol awal.

Contoh :

Lakukan parsing atas kalimat x = b(aa)b berdasarkan grammar G = {Z →

bMb, M → (L a, L → Ma)}.

sentensial dan relasi handel ruas kiri produksi

b ← (← a → a ↔)→ b a M

b ← (← M ↔ a ↔)→ b Ma) L

b ← (↔ L→ b (L M

b↔M↔b bMb Z

Prosedur parsing sampai di simbol awal (Z). Maka kalimat “b(aa)b”

memang dapat diderivasi dari simbol awal Z dengan menggunakan

grammar G.

F. Ambiguitas

Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang

berbeda untuk memperoleh suatu string. Misalkan terdapat tata bahasa sebagai

berikut :

S → A | B

A → a

B → a

15

Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut:

S => A => a

S => B => a

Contoh ambiguitas lain :

Diketahui grammar G = {S → SOS|A , O → *|+, A → 0|1|2|…|9} String :

2*3+7 mempunyai dua pohon sintaks berikut :

Gambar 3. String ambigu

Sebuah string yang mempunyai lebih dari satu pohon sintaks disebut string

ambigu (ambiguous). Grammar yang menghasilkan paling sedikit sebuah

string ambigu disebut grammar ambigu.

G. Penyederhanaan Tata Bahasa Bebas Konteks ( CFG )

Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan

pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki

kerumitan yang tak perlu atau aturan produksi tak berarti.

Misal :

S → AB | a

16

A → a

Kelemahanya adalah aturan produksi S → AB tidak berarti karena B tidak

memiliki penurunan.

Penyederhanaan tata bahasa bebas konteks dapat di lakukan dengan 3 cara :

1. Penghilangan produksi useless

2. Penghilangan produksi unit

3. Penghilangan produksi Є

1. Penghilangan Produksi Useless

Definisinya sebagai berikut:

a. Produksi yang memuat simbol variabel yang tidak memiliki penurunan

yang akan menghasilkan terminal-terminal seluruhnya.

b. Produksi yang tidak akan pernah dicapai dengan penurunan apapun

dari simbol awal sehingga produksi itu redundan.

Contoh :

S → aSa | Abd | Bde

A → Ada

B → BBB |a

a. Langkah penyederhanaannya :

Hilangkan aturan yang tidak menuju terminal.

Hapus anggota S yang mengandung simbol himpunan ke terminal

yang tidak berguna

Hilangkan Redundan (Anggota yang tidak ada di S dan

Sebaliknya)

17

b. Maka, hasil penyederhanaanya adalah sbb :

S → aSa | Bde

B → BBB | a

Contoh lain :

S → Aa | B

A → ab | D

B → b | E

C → bb

E → aEa

c. Produksi yang useless adalah:

A → D

C → bb

E → aEa

B → E

d. Hasil akhir dari penyederhanaanya adalah :

S → Aa | B

A → ab

B → b

18

2. Penghilangan Produksi Unit

Definisinya sebagai berikut:

Produksi unit adalah produksi dimana ruas kiri dan kanan aturan

produksi hanya berupa satu simbol variabel, misalkan :

A → B, C → D.

Keberadaanya membuat tata bahasa memiliki kerumitan yang tak

perlu, maka bisa dihilangkan.

a. Langkah penyederhanaanya :

Jabarkan masing-masing himpunan.

Sederhanakan ruas kiri dan kanan yang hanya berupa variabel

simbol sama.

Hapus simbol variabel yang tidak berguna / tidak mempunyai

turunan.

Contoh suatu CFG sbb :

S → Sb

S → C

C → D

C → ef

D → dd

19

b. Jabarkan penurunan masing – masing himpunan :

C → D => C → dd

S → C => S → dd | ef

c. Maka hasilnya adalah sbb :

S → Sb

S → dd | ef

C → dd

C → ef

D → dd

D. Penghilangan Produksi Empty ( Є )

Definisinya sebagai berikut:

Produksi empty adalah produksi kosong, (dengan bentuk α → Є)

penghilangan dapat dilakukan dengan penggantian produksi yang memuat

variabel yang menuju ke Є.

a. Langkah Penyederhanaannya :

Hilangkan simbol yang terdapat empty ( Є ) dalam himpunan

produksi

Simbol variabel tidak di hapus jika terdapat cabang terminal /

variabel yang saling berhubungan

Buat himpunan dengan simbol yang dihilangkan dan yang

tidak.

Contoh 1 :

S → bcAd

A → e

20

b. Maka variabel A bisa di hilangkan, sehingga menjadi :

S → bcd

Kasus lain :

S → bcAd

A → bd | Є

c. Maka hasilnya akan menjadi :

S → bcAd | bcd

A → bd

Karena A → Є bukan satu-satunya produksi dari A

Contoh 2 :

S → Ab | Cd

A → d

C → Є

Hasil penyederhanaan sebagai berikut :

S → Ab | d

A → d

21

Contoh 3 :

S → dA | Bd

A → bc

A → Є

B → c

Hasil penyederhanaan sebagai berikut :

S → dA | Bd

A → bc

B → c

Contoh 4 :

S → AaCD

A → CD | AB

B → b | Є

C → d | Є

D → Є

Hasil penyederhanaan sebagai berikut :

S → AaC | aC |Aa | a

A → C | AB | A | B

B → b

C → d

22

BAB III

PENUTUP

A. Kesimpulan

Pohon sintaks / pohon penurunan (syntax tree / derivaton tree / parse

tree) berguna untuk menggambarkan bagaimana memperoleh suatu

string (untai) dengan cara menurunkan simbol-simbol variabel menjadi

simbol-simbol terminal. Setiap simbol variabel diturunkan menjadi

terminal, sampai tidak ada yang belum tergantikan. Pada pohon

penurunan, cara menampilkan penguraian dapat dilakukan dengan

membentuk pohon urai.

B. Kritik dan Saran

Dalam pembuatan makalah ini kami selaku penyusun masih banyak

kekurangan dalam pengetahuan makalah ini. Maka disini kami sebagai

penyusun mengharapkan kritik dan saran yang sifatnya membangun demi

kesempurnaan makalah ini. Atas kritik dan sarannya kami ucapkan terima

kasih.

23

REFERENSI

[1]https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CD8QFjAC&url=http%3A%2F%2Felearning.amikom.ac.id%2Findex.php%2Fdownload%2Fmateri%2F555114-ST110-9%2F2012%2F05%2F20120515_Teori%2520Bahasa%2520dan%2520Otomata%2520&ei=hsZpUbHNEcezrAf87YDoAw&usg=AFQjCNGofXsaNvvb1n_wCYiBLfkQyzTgPA&sig2=QqdAAQiIXOAhhu91sqoLig&bvm=bv.45175338,d.bmk&cad=rja14 April 2013 4.31 AM

[2] http://ekohandoyo.blog.undip.ac.id/2010/01/18/cfg-context-free-grammar/14 April 2013 4.43 AM

[3] http://elib.unikom.ac.id/download.php?id=1435414 April 2013 4.50 AM

[4]https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDkQFjAB&url=http%3A%2F%2Felib.unikom.ac.id%2Fdownload.php%3Fid%3D14354&ei=gd1pUaTaCMXZrQfL44HYAQ&usg=AFQjCNHtmZHwyApfJ9C47DUlxJxoLvcPsA&sig2=C4apkj5QhryI5csLhfaWTw&bvm=bv.45175338,d.bmk&cad=rja14 April 2013 4.50 AM

[5]https://docs.google.com/viewer?a=v&q=cache:aOYYNgFjZ10J:www.ilab.gunadarma.ac.id/modul/NewATA/Modul%2520ATA/Teori%2520Bahasa%2520Otomata/M6.pdf+bottom+up+pada+metode+parsing&hl=id&pid=bl&srcid=ADGEESh3DAMVb_6jrMRh5AKLZ2KCBC839ja1gmL_EU2Qn1ns9coHi_vJsg_uBA7lWlcPpJ_WUHV6bwPPi2qtQuGYj6-Kqx_otRHh-vEu6xozTuhrOxrr4FZnFXFqXumVBPQ9O0-5QlXo&sig=AHIEtbQe6oQ53sC1zRLaAnKvg4VuXOuCpQ

14 April 2013 5.12 AM

[6] http://nurmanto.com/metode-metode-parsing/

14 April 2013 5.15 AM

24