*PERTEMUAN VIITata Bahasa Bebas Konteks (Context Free Grammar)Tujuan Instruksional:Diharapkan mahasiswa dapat menguasai konsep tentang tata bahasa dalam kelas bebas konteks dan bahasa bebas konteks.Bentuk tata bahas bebas konteks yang hanya mengikat simbol di sebelah kiri, yaitu panjangnya 1 non terminal, sedang di sebelah kanan tidak terikat menyebabkan tata bahasa ini bebas untuk ruas kanannya, sehingga kadang perlu penyederhanaan

Batasan Tata Bahasa Bebas KonteksTata bahasa bebas konteks (Context Free Grammar) disingkat CFG memiliki batasan sbb:Tata-bahasa Tipe-2 (Context-Free Grammar) G(,N,S,P), adalah tata-bahasa tipe-1 yang memiliki aturan produksi: dengan tambahan batasan:: HANYA terdiri dari 1 simbol Non terminal saja, atau N: tidak dibatasi, atau : (N)*Perbedaan bahasa reguler dengan bahasa bebas konteks:Pada string sisi kanan tanda panah untuk bahasa regular harus satu terminal tunggal atau terminal tunggal diikuti non terminal.Untuk bahasa bebas konteks tidak dibatasi.

*

Batasan Tata Bahasa Bebas KonteksContoh 1:Grammar dengan aturan:Sa|aA AbBBtermasuk tata bahasa apa?Contoh 2:Grammar dengan aturan:Sa|aAAbB|AABAdalah tata bahasa apa?Contoh 3:Tentukan bahasa yang dibangkitkan oleh grammar pada contoh 2.*

Masalah Ambiguity Dalam CFGSebuah tata bahasa bebas konteks dikatakan mendua arti (ambiguous) apabila dalam menurunkan string dapat ditempuh dua atau lebih pohon penurunan string.Perhatikan CFG berikut ini:SABAaA|aBbB|bSuatu string aabbb dapat diturunkan melalui proses penurunan :SABaABaaBaabBaabbBaabbbDapat dicatat bahwa penurunan yang dapat ditulis adalah:SABAbBAbbBAbbbaAbbbaabbb atauSABaABaAbBaAbbBaabbBaabbb*

Masalah Ambiguity Dalam CFGSABaABaaBaabBaabbBaabbbJika digambarkan dalam pohon penurunan diperoleh:Masih banyak kemungkinan yang lain.SA Ba A b B a b B b Untuk penurunan suatu string hanya memiliki satu pohon penurunan yang sama disebut CFG yang tidak mengandung ambiguity.

*

Masalah Ambiguity Dalam CFGPerhatikan CFG berikut ini:SSbS | ScS | aUntuk menurunkan string abaca dapat dibuat penurunan:1. SSbSabSabScSabacSabacaAtau dapat juga:2. SScSSbScSSbacSSbacaabacaJalur penurunan pertama/kedua dibuat pohon penurunan sbb:S SS b SS c Sa S c S S b S a a a a a1. Untuk pohon I: S sebelah kanan diturunkan rekursif baru ke terminal, 2. Untuk pohon II: S sebelah kiri yang diturunkan rekursif baru ke terminal (grammar yang punya sifat ambiguity)..*

Masalah Ambiguity Dalam CFGAmbiguity dapat menjadi sebuah masalah untuk bahasa-bahasa tertentu, tapi tidak menjadi masalah apabila konteksnya diketahui:Contoh:Ali melihat seorang lelaki dengan sebuah teropong.Silahkan makan sama kambing !Dalam bahasa pemrograman BASIC kita jumpai potongan statemen yang mendua arti, misalnya: X=5dalam konteks IF X=5 THEN berarti membandingkan isi variabel X apabila sama dengan 5 atau tidak, dalam konteks LET X=5 berarti menugasi variabel X untuk menampung nilai data 5.*

Masalah Ambiguity Dalam CFGJika suatu tata bahasa bebas kontek memiliki ambiguity, tata bahasa yang lain yang menghasilkan bahasa yang sama dapat dibuat meskipun tidak selalu dapat dibuat.Misalnya tata bahasa berikut:SA/BAaBaTata bahasa lain yang tidak mendua arti adalah: SaJika suatu tata bahasa bebas konteks yang mendua arti tidak dapat dicari padanan tata bahasa lain yang tidak mendua arti, maka tata bahasa tersebut disebut sebagai Inherently ambiguous context free grammar*

Penyederhanaan Tata Bahasa Bebas KonteksDalam tata bahasa bebas konteks terdapat aturan produksi yang tidak berperan dalam penurunan string, atau aturan produksi yang terlalu panjang sehingga pada pohon penurunan berakibat percabangan terlalu lebar dan sulit dikendalikan.Perhatikan tata bahasa berikut:SabcdefS | abcdefAkan melahirkan pohon penurunan yang melebar kesebalah kanan.Sedangkan tata bahasa berikut akan menghasilkan pohon yang tinggi dan sempit:SA AB BC CD Da|A*

Penyederhanaan Tata Bahasa Bebas KonteksJika dicermati grammar diatas terlihat bahwa sebenarnya aturan produksi yang sangat panjang tersebut dapat disederhanakan hanya menjadi : SaDengan membuang SABCDA yang merupakan proses penurunan yang melingkar dan dapat ditiadakan tanpa mengurangi bahasa yang dihasilkan oleh tata bahasa tersebut.Garis besarnya penyederhanaan tata bahasa bebas konteks dapat ditempuh dengan:Membuang aturan produksi yang tidak bergunaMenghilangkan produksi unitMenghilangkan produksi epsilon ()

*