You are here: Home > Teknik Kompilasi > Tugas II Teknik Kompilasi

Tugas II Teknik Kompilasi

Mengapa dalam top down parsing tidak boleh ada left recursive atau  left factoring?

Metode Top Down Parsing ada 2 jenis metode:

1. Backtrack/Backup: Brute Force

2. No Backtrack: Recursive Descent Parser

Metode Brute Forcer

Dalam metode Brute Forcer, grammar yang memiliki Left Recursion tidak bisa diperiksa, karena Left Recursion akan mengalami loopng atau perulangan secara terus-menerus atau tak terhingga. Sehingga perlu diubah terlebih dahulu menjadi grammar yang tidak mengandung Left Recursion.

Contoh:

E -> T | T + E | T – E

T -> F | F * T | F / T

F -> i

Grammar ini diterima karena tidak mengalami left recursive.

E -> E+T | E-T  | T

T -> T* F | T / F | F

F -> i

Grammar ini tidak diterima karena mengalami left recursive.

Dalam Top Down Parsing kita harus melakukan left factoring karena jika tidak melakukan left factoring, maka akan ada kemungkinan grammar tersebut mengalami ambiguitas. Left Factoring ini akan memperbaiki grammar yang ambigu (bila digambar dengan tree akan menghasilkan lebih dari 1 sintaks). Pada case – case tertentu, jika kita sudah melakukan eliminasi left recursion dan grammarnya sudah tidak ambigu tetapi kita masih tidak dapat menentukan “first” dari symbol tertentu, maka kita harus melakukan factorial.

Contoh:

–          Grammar sebelum melakukan left factoring

Untitled

–          Grammar Sesudah melakukan left factoring

 Untitled

Source : http://cse.spsu.edu/clo/teaching/cs4713/lecture/node28.html

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Leave a Reply