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

–          Grammar Sesudah melakukan left factoring

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

www.binus.ac.id