Langkah Q.....

Sebuah Parser akan membentuk Pohon Sintaks (Parse Tree).
Sebuah tree adalah suatu graph terhubung yang tidak sirkuler dan memiliki satu buah root (akar) dan dari situ memiliki lintasan ke setiap simpul (daun/leaf).
Parse Tree berfungsi untuk menggambarkan bagaimana memperoleh suatu string dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal, sampai tidak adasimbol yang belum tergantikan.


Tata Bahasa Bebas Konteks
Untuk mengimplementasikan Parser diperlukan TBBK (Context Free Grammar)
TBBK adalah sekumpulan simbol-simbol variabel (non-terminal), yang masing-masing merepresentasikan bahasa. Bahasa yang direpresentasikan dengan simbol-simbol non terminal tersebut diproses secara rekursif dengan suatu aturan-aturan yang disebut aturan produksi.
Tata bahasa bebas konteks (tipe 2) memiliki elemen:
Terminal : simbol dasar yang tidak dapat diturunkan lagi. Terminal disebut juga token.
Non terminal : variabel sintaktik yang masih dapat diturunkan lagi.

TBBK
Contoh TBBK untuk pasangan kurung yang selalu berpasangan:
S => R
R => {}
R => (R)
R => RR

Contoh TBBK untuk palindrom:
S => R
R => {} a b
R => aRa bRb

Contoh TBBK lain
S => AB
A => aA a
B => bB b


Contoh TBBK:
S => aS
S => bT
T => a

Maka misalkan untuk string “aaba”maka TBBK diatas dapat diturunkan menjadi :

S –> aS
S => aaS
S => aabT
S => aaba

Artinya string “aaba”cocok dan diterima oleh TBBK diatas.
Misalkan untuk string “aba”dan terdapat aturan produksi sebagai berikut:
S => aS
S => abT
S-> aba
Pohon Sintaks :

Metode Parsing
Ada 2 metoda parsing : top-down dan bottom-up.
Parsing top-down :
Metode ini menelusuri pohon, dari root menuju ke daun (leaf). Metode ini meliputi:
Backtracking Mode : Metode Brute Force
Non Backtracking Mode : Recursive Descent Parser dan Predictive Parser
Top Down memparsing tree secara pre order.
Contoh :
S => cAd
A => ab a
Untuk inputan “cad”
Pohon Sintaks ?

Parsing bottom-up :
Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke kanan sampai tiba di simbol awal S (atau tidak sampai di S jika kalimat x memang tidak bisa diturunkan dari S).
Metode ini menelusuri pohon dari daun menuju ke root. Biasanya mengurangi string/daun sampai pada akarnya.
Contoh :
S => aABe
A => Abc b
B => d
Maka untuk string “abbcde”
@ abbcde
@ aAbcde
@ aAde
@ aABe
@ S


Metode Parsing lainnya
Metode Brutal Force
Metode ini akan melakukan substitusi semua simbol non terminal yang ada. Jika terjadi salah parsing (atau tidak cocok), maka dapat dilakukan backtracking.
Contoh:
S => aAd aB
A => b c
B => ccd ddc
Misal ingin memparsing : “accd”.
S => aAd
S => abd : gagal, maka dilakukan backtrack
S => acd : gagal, maka dilakukan backtrack
S => aB
S => accd : berhasil!
Kelemahan Brutal Force :
Mencoba semua aturan produksi sehingga akan menjadi lambat
Sulit melakukan backtracking dan pemulihan kesalahan
Memakan banyak memori karena perlu mencatat lokasi backtrack

TBBK Rekursif Kiri
TBBK yang memiliki simbol non terminal di ruas kanan dari simbol non terminal yang ada di ruas kiri. Simbol non terminal itu terletak di ruas kanan terdepan. TBBK ini juga tidak memiliki kemungkinan aturan produksi lain yang berupa simbol terminal.
Contoh :
S => Sd
A => Aad

Menyebabkan pohon tumbuh ke kiri
Contoh Pohon
S => aAc
A => Ab {}


TBBK Rekursif Kanan
TBBK Rekursif Kanan: TBBK yang memiliki simbol non terminal di ruas kanan dari simbol non terminal yang ada di ruas kiri. Simbol non terminal itu terletak di ruas kanan terbelakang. TBBK ini juga tidak memiliki kemungkinan aturan produksi lain yang berupa simbol terminal.
Contoh:
S => dS
B => adB
Membuat pohon sintaks melebar ke kanan.