Grammar dan Turunan (Derivasi) Dalam Bahasa Pemrograman

Derivasi atau turunan adalah pengaplikasian sejumlah rules untuk menghasilkan suatu statement (sentence).

Contoh: diberikan grammar untuk suatu bahasa pemrograman singkat sebagai berikut:

Suatu derivasi terhadap suatu program dengan bahasa ini dapat berupa: 

Pada contoh di atas, derivasi atau proses perubahan non-terminal symbols menjadi terminal symbols dilakukan berlulang dan bertahap satu per satu hingga semua non-terminal telah berubah menjadi terminal. 

Dengan kata lain, derivasi adalah penerapan rule secara berulang dimulai dari start symbol (elemen tertentu di dalam himpunan non-terminal di dalam grammar) dan berakhir dengan suatu kalimat (seluruh elemennya adalah terminal symbols). Derivasi seperti di atas, dimana pengubahan non terminal menjadi terminal selalu dimulai dari yang paling kiri, disebut leftmost derivation.


Contoh lain (unambiguous) grammar dan disertai left-most dan right-most derivation:

unambiguous grammar

Grammar di samping adalah unambigious, memberikan sebuah parse tree yang unique bagi sentence A = B + C * A, serta dapat merepresentasikan leftmost maupun rightmost derivation seperti berikut:

Leftmost derivation:

leftmost derivation

Rightmost derivation:

rightmost derivation