Cara Membuat Parse Tree

Pada proses tahapan kompilasi terdapat salah satu langkah yaitu syntax analysis. Di tahap ini input string yang ada akan diperiksa mengenai aturan produksinya, atau yang biasa kita sebut dengan check grammar. Aturan produksi dari sebuah language tertuang dalam Context Free Grammar (CFG). Langkah yang akan dilakukan untuk pengecekan grammar tersebut adalah mencoba melakukan parsing terhadap input string yang masuk berdasarkan pada aturan produksinya.

Contoh diberikan sebuah CFG seperti dibawah ini.

S -> aBa

B -> bB | ɛ

Pada CFG tersebut kita dapat melihat aturan produksi S hanya ada 1 yaitu S dapat diderivasi menjadi aBa. Disisi lain aturan produksi B memiliki 2 pilihan aturan yaitu B dapat diderivasi menjadi bB atau empty string (epsilon). Seperti yang kita ketahui bahwa CFG memiliki symbol terminal dan non-terminal (variable). Simbol non-terminal pada grammar tersebut adalah S dan B, sedangkan symbol terminal adalah a, b dan juga ada empty production.  Ketika proses parsing mencapai symbol terminal maka derivasi tidak dapat dilakukan lagi untuk terminal tersebut.

Jika terdapat sebuah input string abba dan kita ingin melakukan pengecekan apakah input tersebut sudah sesuai dengan aturan produksi yang kita miliki, maka kita dapat mencoba untuk membuat parse tree. Contoh parse tree yang dapat terbentuk dari CFG diatas adalah seperti gambar dibawah ini.

Kita akan memulai membuat syntax tree dari Start symbol. Pada umumnya start symbol akan diletakkan dipaling atas dari sebuah CFG. Pada contoh diatas start symbol kita adalah S yang akan diderivasi menjadi aBa (karena hanya ada 1 aturan jadi kita tidak bisa memilih aturan lainnya). Kita akan melakukan derivasi menggunakan left-most derivation. Karena node paling kiri merupakan node terimal symbol yang tidak dapat diderivasi maka kita akan melanjutkan dengan node berikutnya yaitu B. B dapat diderivasi menjadi bB atau ɛ. Jika kita memilih aturan ke 2 (derivasi menjadi ɛ) maka input string yang akan diterima adalah aa, bukan abba. Oleh karena itu kita harus memilih aturan yang pertama yaitu B diderivasi menjadi bB. Proses terus dilakukan sampai mendapatkan hasil terminal symbol yang sama dengan input string. Jika sebuah input string tidak dapat dibentuk syntax tree nya maka berarti string tersebut tidak sesuai dengan grammar yang ada (syntax error).