Suatu tata bahasa secara alamiah menerangkan struktur hirarki dari banyak bentuk bahasa pemrograman. Misalkan perintah if-else dari bahasa C mempunyai bentuk:
if (ekspresi) perintah else perintah
Ket :
Dalam hal ini suatu perintah adalah gabungan dari :
kata kunci if
kurung buka
ekspresi
kurung tutup
perintah
kata kunci else
perintah lainnya
(Dalam bahasa C tidak ada kata kunci then).
Bila digunakan nama variabel expr untuk menyatakan suatu ekspresi dan variabel stmt untuk menyatakan suatu perintah, maka struktur aturan ini dapat dinyatakan sebagai berikut :
stmt ? if (expr) stmt else stmt
Ket:
? (tanda panah dibaca sebagai) “Dapat berbentuk suatu”.
Aturan diatas disebut juga suatu produksi (production). Dalam suatu produksi seperti ini unsur leksikal seperti kata kunci if dan tanda kurung “(“,”)” disebut suatu token. Variabel seperti expr dan stmt disebut dengan non-terminal.
Secara lengkap suatu tata bahasa bebas konteks dapat mempunyai 4 komponen berikut:
0> Himpunan dari token yang dikenal dengan simbol token.
0> Himpunan dari unsur non-terminal
0> Himpunan dari produksi, di mana masing-masing produksi terdiri dari unsur non-terminal (bagian kiri tanda panah dari suatu produksi). Bagian kanan produksi berupa ? (tanda panah) dan barisan dari token dan/atau non-terminal (sebelah kanan tanda panah).
0> Salah satu unsur non-terminal yang telah ditentukan sebagai awal tata bahasa disebut sebagai simbol awal.
Aturan umum yang digunakan dalam menentukan suatu tata bahasa adalah dengan menuliskan produksi yang ada dengan dimulai dari produksi yang mengandung simbol awal. Terminal dapat berupa angka-angka, tanda-tanda seperti <=, dan rangkaian karakter yang ditulis huruf tebal seperti while dan lain-lainnya juga nama lain yang tidak dicetak miring. Non-teminal dapat berupa nama yang dicetak miring.
Untuk memudahkan penulisan, maka produksi yang mempunyai simbol non-teminal disebelah kiri yang sama bagian kanannya dapat dikelompokkan dengan menggunakan tanda “|” yang memisahkan pilihan bagian kanan yang ada. pengelompokkan seperti ini dapat dibaca sebagai “atau”
Contoh 1:
9-5+2, 3-1, 7 merupakan barisan dari angka-angka yang dipisahkan oleh
tanda ‘+’ atau ‘-’.
Tata bahasa berikut memberkan sintaks dari ekspresi-ekspresi di atas. Produksi yang ada adalah:
list ? list + digiT
list ? list – digit
list ? digit
digit ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Bagian kanan dari produksi untuk unsur non-terminal list
list ? list + digit
list ? list – digit
list ? digit
di bagian kiri dapat dikelompokkan menjadi 1 produksi yang setara, yaitu:
list ? list + digit | list – digit | digit
ü Penulisan Produksi menjadi:
list ? list + digit | list – digit | digit
digit ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
ü Token yang menjadi terminal digunakan adalah simbol +,-,0,1,2,3,4,5,6,7,8,9
0> Sedangkan unsur non-terminal adalah nama-nama yang digaris miring seperti list dan digit
0> Simbol Awal adalah produksi non-terminal list
Suatu unsur non-terminal dapat merupakan suatu produksi bila unsur non-terminal tersebut timbul dibagian kiri dari produksi.
Barisan token adalah barisan dari nol atau lebih token. Unsur yang mengandung nol token ditulis sebagai ?, dan disebut dengan nama barisan kosong.
Suatu bahasa diperoleh dari :
barisan-barisan yang dimulai dari simbol awal
bagian kanan yang masih berupa non-terminal (bukan token/terminal) dari produksi dapat diganti dengan mencari acuan pada bagian kiri dari produksi yang ada dengan non-terminal yang sama.
mengganti unsur non-terminal pada bagian kiri produksi dengan bagian kanan dari produksi non-terminal tersebut.
Barisan token pada bagian kanan produksi yang menjadi pengganti unsur non terminal acuan pada bagian kiri produksi merupakan akhir dalam pembentukan bahasa.
Contoh 2:
Bahasa yang didefinisikan oleh tata bahasa pada contoh 1 terdiri dari barisan angkaangka yang dipisahkan oleh tanda ‘-’ atau ‘+’.
Kesepuluh produksi dari unsur nonterminal digit (digit ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9) dapat digunakan sebagai penganti token-token yang berhubungan dengan angka yaitu 0,1,2,3,4,5,6,7,8,9 dari produksi list ? digit, maka dapat dikatakan bahwa 1 angka yang berdiri sendiri adalah suatu list juga, yaitu :
Pada produksi list ? digit
0 merupakan bahasa yang dibentuk list
1 merupakan bahasa yang dibentuk list
2 merupakan bahasa yang dibentuk list
3 merupakan bahasa yang dibentuk list
4 merupakan bahasa yang dibentuk list
5 merupakan bahasa yang dibentuk list
6 merupakan bahasa yang dibentuk list
7 merupakan bahasa yang dibentuk list
8 merupakan bahasa yang dibentuk list
9 merupakan bahasa yang dibentuk list
Pada produksi lainnya
list ? list + digit
list ? list – digit
Menyatakan bahwa list yang diikuti oleh tanda ‘+’ atau ‘-’ dan diikuti oleh list akan membentuk suatu list baru.
Ternyata semua produksi yang digunakan pada contoh 1 adalah produksi-produksi yang diperlukan untuk dapat mendefinisikan bahasa yang diinginkan untuk ekspresi 9-5+2, 31, 7
9-5+2 merupakan salah satu anggota dari bahasa yang dibentuk list, dimana list adalah simbol awal. Hal ini dapat ditunjukkan sebagai berikut:
ü 9 merupakan list dari produksi “list ? digit” dimana digit membentuk 9 pada
“digit ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9″ atau secara terpisah menjadi
digit ? 0
digit ? 1
digit ? 2
digit ? 3
digit ? 4
digit ? 5
digit ? 6
digit ? 7
digit ? 8
digit ? 9.
0> 9-5 merupakan list dari produksi “list ? list – digit” dimana 9 sudah berupa list dan digit membentuk 5 pada “digit ? 5″.
0> 9-5+2 merupakan list dari produksi “list ? list + digit” = (9-5) + 2. Dimana 9-5 sudah berupa list dan digit membentuk 2 pada “digit ? 2″.
Hal ini dapat dilihat pada gambar 1 berikut ini
Gambar 1 Pohon urai dari ekspresi 9-5+2 menurut tata bahasa contoh 1
Pada gambar ini setiap nodal (titik pertemuan antar garis) pada pohon urai diberi label salah satu simbol tata bahasa.
Nodal dalam (internal node / nodal di atas nodal yang lain) dan anak-anaknya (nodal yang terletak di bawah nodal dalam) berhubungan dengan suatu produksi.
Nodal dalam berhubungan dengan bagian kiri dari produksi, sedangkan anak-anaknya berhubungan dengan bagian kanan dari produksi yang sama.
Pohon demikian disebut pohon urai dari ekspresi yang diberikan.
Contoh 3
Pada bahasa Pascal dapat dijumpai dalam cakupan blok begin-end. Salah satu perbedaan yang sangat mencolok yang terdapat pada contoh adalah adanya list dari perintah-perintah yang mungkin kosong diantara token-token begin dan end.
Untuk itu dikembangkan suatu tata bahasa yang mengandung produksi berikut:
block ? begin opt_stmts end
opt_stmts ? stmt_list | ?
stmt_list ? stmt_list ?stmt | stmt
Pada produksi opt_stmts, kemungkinan ke-2 bagian kanan pada “opt_stmts ? stmt_list | ?” adalah perintah yang boleh memilih “?”, yang mengartikan rangkaian kosong dari simbol-simbol. Jadi suatu blok dapat hanya terdiri dari 2 token yaitu begin dan end
Pada produksi stmt_list sangat mirip dengan produksi list pada contoh 1, dimana tanda “|” menggantikan operator “+” dan “-” (list ? list + digit | list – digit | digit). Unsur non-terminal stmt menggantikan unsur non-terminal digit
Sumber
