Menghilangkan Left Recursive (perulangan)

Ketika kita menghilangkan left recursive pada sebuah grammar, perlu diperhatikan bahwa tidak semuanya grammar hanya memiliki jenis left recursive yang terlihat secara langsung (immediate left-recursive). Dibawah ini adalah contoh immediate left recursive dimana dapat dilihat bawah S memanggil dirinya sendiri secara langsung dan terletak disebelah kiri.

S -> Sab | AbA

A -> a | b

Ada juga left recursive yang tidak dapat langsung dikenali, contohnya adalah pada CFG dibawah ini.

S -> Aa | b

A -> Ac | Sd | f

Pada CFG diatas kita melihat adanya left recursive secara langsung di unit produksi A (A -> Ac), namun kita tidak melihat adanya left recursive secara langsung di unit produksi S. Jika diperhatikan lagi unit produksi S dapat diderivasi menjadi Aa (S -> Aa), lalu A dapat diderivasi lagi menjadi Ac |Sd |f. Jika A diderivasi menjadi Sd maka sebenarnya terjadi perulangan (inner-loop) yang mengandung left recursive (karena letak perulangan berada di sisi kiri). Oleh karena itu kita perlu melakukan eliminasi left recursive langsung dan tidak langsung ini secara bertahap.

Cara pertama yang dapat dilakukan adalah dengan menggantikan aturan produksi S pada unit produksi A. Jadi S yang terdapat pada aturan A -> Sd dapat diganti dengan kemungkinan pilihan derivasi untuk S tersebut (S -> Aa | b) sehingga akan menjadi A -> Aad | bd.

S -> Aa | b

A -> Ac | Aad | bd | f

Setelah menggantikan S tersebut maka kita dapat mehilangkan left recursive yang berada pada unit produksi A.

Sehingga CFG yang akan dihasilkan adalah seperti dibawah ini.

S -> Aa | b

A -> bdA’ | fA’

A’ -> cA’ | adA’ | e

References:

Aho, A.V., Ravi, S., & Ullman, J.D. (2007). Compiler : Principle, techniques and tools. 2nd. Addison-Wesley. New York. ISBN : 0321491696