Parsing atau Proses Penurunan

Parsing dari sebuah kalimat adalah konstruksi atau pembentukan pohon sintaks untuk kalimat tersebut.

Parsing dapat dilakukan dengan cara :

• Penurunan terkiri (Leftmost derivation) : symbol variabel yang paling kiri diturunkan (tuntas) dahulu
• Penurunan terkanan (Rightmost derivation) : symbol yang paling kanan diturunkan (tuntas) dahulu

Contoh : ingin dihasilkan string aabbaa dari

        Context free language :     S → aAS │ a

A → SbA │ ba

Penurunan kiri                      Penurunan kanan

S  → aAS                            S  → aAS

   → aSbAS                             → aAa

   → aabAS                             → aSbAa

   → aabbaS                            → aSbbaa

   → aabbaa                            → aabbaa

Metode Parsing

Pada metode parsing ada tiga hal yang perlu diperhatikan, yaitu :

1. waktu eksekusi
2. penanganan kesalahan
3. penanganan kode

Parsing digolongkan menjadi :

1. Top Down

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

Metode ini meliputi :

1. Backtrack / back up : Brute Force

·         Memilih produksi mulai dari kiri

·         Meng-expand symbol non terminal sampai pada symbol 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 non terminal

Back Up : pengulangan suatu produksi dengan alternatif produksi yang lain, bila produksi yang digunakan tidak sesuai dengan symbol input.

Contoh :

Grammar :   1.    S → aAd

2.       S → aB

3.       A → b

4.       A → c

5.       B → ccd

6.       B → ddc

S, A dan B adalah symbol non terminal dengan S adalah symbol start. Sementara itu a, b, c dan d adalah symbol terminal