Aturan produksi yang rekursif dibagi
menjadi dua, yaitu rekursif kiri dan rekursif kanan.
Aturan produksi dikatakan rekursif kiri
jika pada awal hasil produksi mengandung variabel yang sama dengan ruas kiri.
Bentuk umum aturan produksi rekursif
kiri :
A ® Ab ; b = (V⋃T)*
Sebagai contoh:
S ® Sa
A ® Ab
B ® Bad
Aturan produksi dikatakan rekursif kanan
jika pada akhir hasil produksi mengandung variabel yang
sama dengan ruas kiri.
Bentuk umum aturan produksi rekursif
kanan :
A ® bA ; b = (V⋃T)*
Sebagai contoh:
S ® aS
A ® bdA
B ® aB
Produksi yang
rekursif kanan menyebabkan pohon penurunan tumbuh ke kanan, sedangkan produksi yang
rekursif kiri menyebabkan pohon penurunan tumbuh ke kiri.
Sebagai contoh:
S ® aAc
A ® Ab
Dalam banyak penerapan tata bahasa ,
rekursif kiri tak diinginkan karena mengakibatkan penurunan yang menghasilkan loop,
sehingga kita perlu menghilangkan rekursif kiri dari aturan produksi.
Tahapan Penghilangan Rekursif Kiri
Langkah-langkah penghilangan
penghilanganrekursif kiri.
i)
Pisahkan
aturan produksi yang rekursif kiri dengan
yang tidak rekursif kiri.
Sebagai
contoh:
Aturan
produksi yang rekursif kiri,
A
® Aa1 | Aa2 | Aa3 | … | Aan
Aturan
produksi yang bukan rekursif kiri,
A
® b1 | b2 | b3 | … | bm
Tahapan Penghilangan Rekursif Kiri
Langkah-langkah penghilangan
penghilanganrekursif kiri.
i)
Pisahkan
aturan produksi yang rekursif kiri
dengan
yang tidak rekursif kiri.
Sebagai
contoh:
Aturan
produksi yang rekursif kiri,
A
® Aa1 | Aa2 | Aa3 | … | Aan
Aturan
produksi yang bukan rekursif kiri,
A
® b1 | b2 | b3 | … | bm
Contoh :
Hilangkan rekursif kiri dari aturan
produksi berikut!
S ®Sab | aSc
| dd | ff | Sbd
Penyelesaian:
Aturan produksi rekursif kiri:
S ®Sab | Sbd
a1 = ab ;
a2 = bd
Aturan produksi tidak rekursif kiri:
S ® aSc | dd
| ff
b1 = aSc ; b2 = dd; b3 = ff
Aturan produksi
rekursif kiri, S ®Sab | Sbd
digantikan oleh:
S ® aScZ1
| dd Z1 | ff Z1
Z1 ® ab | bd
Z1 ® abZ1
| bdZ1
Hasil akhir
setelah penghilangan rekursif kiri adalah:
S ® aSc | dd
| ff
S ® aScZ1
| dd Z1 | ff Z1
Z1 ® ab | bd