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 → αβ₁ | αβ₂

Dimana α adalah non-empty dan β₁  dan β₂ memiliki symbol pertama yang berbeda.

Dari grammar di atas dapat dilihat, pada saat memproses α, maka parser akan bingung  untuk mengexpand A ke  αβ₁ atau αβ₂

Jika pada grammar terdapat left factoring, maka untuk menghilangkan left factoring tersebut dapat diubah bentuknya menjadi :

A → αA’
A → β₁ | β₂

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