Apa itu Backus-Naur Form (BNF) dan Context-Free Grammar(CFG)?

Kedua istilah tersebut sering dibahas jika sudah menyangkut tentang kompilasi yang dilakukan oleh compiler bahasa pemrograman. Jujur saja, saya agak bingung saat memahami kedua istilah ini, kali ini saya coba menjelaskan kedua istilah tersebut.

Context-Free Grammar (CFG)

Saat kompilasi, compiler menggunakan grammar atau aturan untuk menghasilkan parse tree atau derivation tree dari source code. CFG merupakan salah satu grammar yang digunakan untuk parsing.

Backus-Naur Form (BNF)

Merupakan salah satu teknik notasi atau meta language dari Context-free grammar (CFG) serta banyak digunakan untuk mendeskripsikan bahasa yang digunakan untuk komputasi, seperti bahasa pemrograman, protokol komunikasi, format dokumen dan masih banyak lagi.

Apakah mereka sama?

Yep! Berdasarkan beberapa jawaban dari forum Stack Overflow (link) Mereka hanya memiliki perbedaan dalam penulisan sintaks.

4 Komponen Context-Free Grammar

1. Terminal merupakan konten asli dari kalimat. Biasa disebut juga token.
2. Non-terminal biasanya berisi himpunan terminal. Biasa disebut syntactic variable.
3. Production yang memiliki non-terminal di sebelah kiri biasa disebut head, panah, dan urutan terminal/non-terminal di sebelah kanan biasa disebut body
4. Start symbol biasa diisi oleh non-terminal

Berikut adalah contoh grammar yang mendeskripsikan angka dengan tanda + atau tanda -, seperti 9-2 atau 9-5+2. Berikut productions-nya :

list -> list + list

list -> list - list

list -> digit

digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Dapat disederhanakan menjadi

list -> list + list | list - list | digit

digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Bisa dilihat terminal dari grammar di atas adalah symbol 0-9. Non-terminal dari grammar di atas adalah list dan digit. Kita bisa membuktikan bahwa 9-5+2 dihasilkan dari grammar di atas, dengan cara menggunakan derivations. Terdapat 2 jenis yaitu :

Leftmost Derivations

Disubtitusi mulai dari kiri. Expand non-terminal sebelah kiri.

list -> list - list

      -> digit - list

      -> 9 - list

      -> 9 - list + list

      -> 9 - digit + list

      -> 9 - 5 + list

      -> 9 - 5 + digit

      -> 9 - 5 + 2

Sehingga parse tree-nya sebagai berikut :

Rightmost Derivations

Disubtitusi mulai dari kanan.

list -> list + list

      -> list + digit

      -> list + 2

      -> list - list + 2

      -> list - digit + 2

      -> list - 5 + 2

      -> digit - 5 + 2

      -> 9 - 5 + 2

Sehingga parse tree-nya sebagai berikut :

Dilihat dari contoh di atas, grammar tersebut menghasilkan 2 parse tree. Sehingga grammar tersebut dikatakan ambigu. Grammar yang tidak ambigu hanya menghasilkan 1 parse tree saja. Contoh grammar yang tidak ambigu adalah berikut :

S-> SS+ | SS* | a

Buktikan string aa+a* bisa digenerate dari grammar di atas?

S-> SS*

  -> SS+S*

  -> aS+S*

  -> aa+S*

  -> aa+a*

Sehingga parse tree nya adalah