1

PERTEMUAN VII

Tata 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 Konteks

Tata 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 tunggal.

Untuk bahasa bebas konteks tidak dibatasi.2

Batasan Tata Bahasa Bebas Konteks

Contoh 1:

Grammar dengan aturan:

Sa|aA AbB Btermasuk tata bahasa apa?

Contoh 2:

Grammar dengan aturan:

Sa|aA AbB|AA BAdalah tata bahasa apa?

Contoh 3:

Tentukan bahasa yang dibangkitkan oleh grammar pada contoh 2.

3

Masalah Ambiguity Dalam CFG

Sebuah tata bahasa bebas konteks dikatakan mendua arti (ambiguous) apabila dalam menurunkan string dapat ditempuh dua atau lebih pohon penurunan string.

Perhatikan CFG berikut ini:

SAB

AaA|a

BbB|b

Suatu string aabbb dapat diturunkan melalui proses penurunan :

SABaABaaBaabBaabbBaabbb

Dapat dicatat bahwa penurunan yang dapat ditulis adalah:

SABAbBAbbBAbbbaAbbbaabbb atau

SABaABaAbBaAbbBaabbBaabbb 4

Masalah Ambiguity Dalam CFG

SABaABaaBaabBaabbBaabbb

Jika digambarkan dalam pohon penurunan diperoleh:

Masih banyak kemungkinan yang lain.

S

A B

a A b B

a b B

b

Untuk penurunan suatu string hanya memiliki satu pohon penurunan yang sama disebut CFG yang tidak mengandung ambiguity.

5

Masalah Ambiguity Dalam CFGPerhatikan CFG berikut ini:

SSbS | ScS | a

Untuk menurunkan string abaca dapat dibuat penurunan:

1. SSbSabSabScSabacSabaca

Atau dapat juga:

2. SScSSbScSSbacSSbacaabaca

Jalur penurunan pertama/kedua dibuat pohon penurunan sbb:

S S

S b S S c S

a 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).. 6

Masalah Ambiguity Dalam CFG

Ambiguity dapat menjadi sebuah masalah untuk bahasa-bahasa tertentu, tapi tidak menjadi masalah apabila konteksnya diketahui:

Contoh:

1.Ali melihat seorang lelaki dengan sebuah teropong.

2.Silahkan makan sama kambing !

3.Dalam bahasa pemrograman BASIC kita jumpai potongan statemen yang mendua arti, misalnya: X=5

dalam 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. 7

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/B

Aa

Ba

Tata bahasa lain yang tidak mendua arti adalah: Sa

Jika 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’

8

Penyederhanaan Tata Bahasa Bebas Konteks

Dalam 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 | abcdef

Akan melahirkan pohon penurunan yang melebar kesebalah kanan.

Sedangkan tata bahasa berikut akan menghasilkan pohon yang tinggi dan sempit:

SA AB BC CD Da|A9

Penyederhanaan Tata Bahasa Bebas Konteks

Jika dicermati grammar diatas terlihat bahwa sebenarnya aturan produksi yang sangat panjang tersebut dapat disederhanakan hanya menjadi : Sa

Dengan 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:

1.Membuang aturan produksi yang tidak berguna

2.Menghilangkan produksi unit

3.Menghilangkan produksi epsilon ()10