PENGHILANGAN REKURSIF KIRI

 12. PENGHILANGAN REKURSIF KIRI

2 12.1 Aturan Produksi Rekursif
Aturan produksi yang rekursif adalah aturanproduksi yang hasil produksinya (ruas kanan)mengandung variabel yang sama dengan ruas kiri.Aturan produksi berikut adalah aturan produksi yang rekursif,S  dSA  AbB  adBPerhatikan aturan produksi diatas!Setiap hasil produksi (ruas kanan) mengandung variabel yang sama dengan ruas kiri.

3 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  A ;  = (V⋃T)*Sebagai contoh:S  SaA  AbB  Bad

4 Aturan produksi dikatakan rekursif kanan jika pada akhir hasil produksi mengandung variabel yang sama dengan ruas kiri.Bentuk umum aturan produksi rekursif kanan :A  A ;  = (V⋃T)*Sebagai contoh:S  aSA  bdAB  aB

5 a A c bProduksi yang rekursif kanan menyebabkan pohon penurunantumbuh ke kanan, sedangkan produksi yang rekursif kirimenyebabkan pohon penurunan tumbuh ke kiri.Sebagai contoh:S  aAcA  AbDalam banyak penerapan tata bahasa , rekursif kiri tak diinginkan karena mengakibatkan penurunan yang menghasilkan loop, sehingga kita perlu menghilangkan rekursif kiri dari aturan produksi.

6 12.2 Tahapan Penghilangan Rekursif Kiri
Langkah-langkah penghilangan penghilanganrekursif kiri.Pisahkan aturan produksi yang rekursif kiridengan yang tidak rekursif kiri.Sebagai contoh:Aturan produksi yang rekursif kiri,A  A1 | A2 | A3 | … | AnAturan produksi yang bukan rekursif kiri,A  1 | 2 | 3 | … | m

7 ii) Tentukan simbol-simbol 1, 2, 3, … , n dan
1, 2, 3, … , m dari setiap aturan produksiyang memiliki simbol ruas kiri yang sama.iii) Lakukan penggantian aturan produksi yangrekursif kiri menjadi sebagai berikut:A  1 Z | 2 Z | 3 Z | … | m ZZ  1 | 2 | 3 | … , nZ  1 | 2 | 3 | … | m

8 aturan produksi rekursif kiri
CFG yang mengandungaturan produksi rekursif kiriAturan produksi yang tidak rekursif kiriAturan produksi yang rekursif kiriLakukanpenggantianCFG yang bebas dari aturan produksi yangrekursif kiri

9 Contoh 12.1Hilangkan rekursif kiri dari aturan produksi berikut!S Sab | aSc | dd | ff | SbdPenyelesaian:Aturan produksi rekursif kiri:S Sab | Sbd1 = ab ; 2 = bdAturan produksi tidak rekursif kiri:S  aSc | dd | ff1 = aSc ; 2 = dd ; 3 = ff

10 Aturan produksi rekursif kiri, S Sab | Sbd digantikan oleh:
S  aScZ1 | dd Z1 | ff Z1Z1  ab | bdZ1  abZ1 | bdZ1Hasil akhir setelah penghilangan rekursif kiri adalah:S  aSc | dd | ff

11 Contoh 12.2Hilangkan rekursif kiri dari aturan produksi berikut!S Sab | Sb | cAA Aa | a | bdPenyelesaian:Aturan produksi rekursif kiri, S Sab | Sb1 = ab ; 2 = bAturan produksi rekursif kiri, A Aa1 = aAturan produksi tidak rekursif kiri, S  cA1 = cAAturan produksi tidak rekursif kiri, A  a | bd1 = a ; 2 = bd

12 Pergantian aturanproduksi rekursif kiri:S Sab | Sb digantikanoleh:S  caZ1Z1  ab | bZ1  abZ1 | bZ1A Aa digantikanA  aZ2 | bdZ2Z2  aZ2  aZ2Hasil akhir setelahpenghilangan rekursifkiri adalah:S  cAA  a | bdS  caZ1Z1  ab | bZ1  abZ1 | bZ1A  aZ2 | bdZ2Z2  aZ2  aZ2

13 Contoh 12.3Hilangkan rekursif kiri dari aturan produksi berikut!S Sa | aAc | c | A Ab | baPenyelesaian:Aturan produksi rekursif kiri, S Sa1 = aAturan produksi rekursif kiri, A Ab1 = bAturan produksi tidak rekursif kiri, S  aAC | c | 1 = aAc ; 2 = c ; 3 = Aturan produksi tidak rekursif kiri, A  ba1 = ba

14 Pergantian aturanproduksi rekursif kiri:S Sa digantikanoleh:S  aAcZ1 | cZ1 | Z1Z1  aZ1  aZ1A Ab digantikanA  baZ2Z2  bZ2  bZ2Hasil akhir setelahpenghilangan rekursifkiri adalah:S  aAC | c | S  aAcZ1 | cZ1 | Z1A  baA  baZ2Z1  aZ1  aZ1Z2  bZ2  bZ2

15 LatihanLakukan penghilangan rekursif kiri padatata bahasa bebas konteks berikut!A  Aa | aBc2. A  Aa | aBcB  BAa | A | 