Powered By Blogger

Entri Populer

Selasa, 19 April 2011

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                             → 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

Tidak ada komentar:

Posting Komentar