Teknik Kompilasi : ELIMINASI LEFT FACTORING
Pada saat mau melakukan metode Top Down Parsing, jika masih ditemukan Left Factoring pada grammar, maka Left Factoring tersebut harus dieliminasi karena jika tidak melakukan eliminasi left factoring maka grammar tersebut akan mengalami ambigutias. Ambiguitas Grammar adalah grammar yang dapat menghasilkan lebih dari 1 parse tree untuk 1 sentence.
Berikut adalah grammar yang memiliki Left Factoring :
A → αβ1 | αβ2
Dimana α adalah non-empty dan β1 dan β2 memiliki symbol pertama yang berbeda.
Dari grammar di atas dapat dilihat, pada saat memproses α, maka parser akan bingung untuk mengexpand A ke αβ1 atau αβ2
Jika pada grammar terdapat left factoring, maka untuk menghilangkan left factoring tersebut dapat diubah bentuknya menjadi :
A → αA’
A → β1 | β2
Untuk lebih jelasnya dapat dilihat di contoh berikut :
V → Na | Ni
N → ai | ni
Pada grammar V → Na | Ni , terdapat α yaitu N, β1 yaitu adan β2 yaitu i, jadi pada grammar ini terdapat left factoring. Maka bentuknya dapat diubah menjadi :
V → NA
A → a | i
Pada grammar N → ai | ni , terdapat β1 yaitu ai dan β2 yaitu ni, tapi tidak terdapat α, jadi pada grammar ini tidak terdapat left factoring, maka bentuk grammarnya tidak perlu diubah.
Berikut result grammar yang sudah tidak ada left factoringnya dan siap untuk dilanjutkan dengan metode Top Down Parsing
V → NA
A → a | i
N → ai | ni