Teknik Kompilasi : ELIMINASI LEFT RECURSION

Pada saat mau melakukan metode Top Down Parsing, jika masih ditemukan Left Recursion pada grammar, maka Left Recursion tersebut harus dieliminasi karena metode Top Down Parsing tidak dapat menghandle left recursive grammar.

Grammar yang disebut left recursive grammar adalah grammar yang memiliki setidaknya 1 α dan 1 β.

A → Aα | β

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

A  → αA’
A’ → βA’ | ε

Untuk lebih jelasnya dapat dilihat di contoh berikut : 

A → Ae | L
L → Lne | Dn
D → en | (A)

Pada grammar A → Ae | L , terdapat α yaitu e dan terdapat β yaitu L, jadi pada grammar ini terdapat left recursion. Maka bentuknya dapat diubah menjadi :

A  → eA’
A’ → LA’ | ε

Pada grammar L → Lne | Dn , terdapat α yaitu ne dan terdapat β yaitu Dn, jadi pada grammar ini terdapat left recursion. Maka bentuknya dapat diubah menjadi :

L  → neL’
L’ → DnL’ | ε

Pada grammar D → en | (A) , terdapat α yaitu en dan (A), tapi tidak terdapat β, jadi pada grammar ini tidak terdapat left recursion, maka bentuk grammarnya tidak perlu diubah.

Berikut result grammar yang sudah tidak ada left recursionnya dan siap untuk dilanjutkan dengan metode Top Down Parsing

A  → eA’
A’ → LA’ | ε
L  → neL’
L’ → DnL’ | ε
D → en | (A)