PARSING TREE

Parsing merupakan proses penurunan.
Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node/vertex) yang disebut akar (root) dan memiliki lintasan ke simpul-simpul lain. Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Contoh : Misalkan sebuah tata bahasa bebas konteks (CFG,) memiliki aturan produksi :
S AB
A aA | a
B bB | b
Maka pohon penurunan untuk memperoleh string ‘aabbb’ adalah : symbol awal S akan menjadi akar (root_). Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi. Simbol-simbol variable akan menjadi simpul-simpul yang mempunyai anak. Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal atau £.

Proses penurunan bias dilakukan dengan cara :
 • Penurunan terkiri (leftmost derivation) : symbol variable terkiri yang diproses terlebih dahulu.
 • Penurunan terkanan (rightmost derivation) : symbol variable terkanan yang diperoleh terlebih dahulu.

Misalkan sebuah tata bahasa bebas konteks (CFG), yang memiliki aturan produksi :
S aAS | a
A SbA | ba
Untuk memperoleh string "aabbaa" dari aturan produksi diatas :
• Dengan penurunan terkiri :
S => aAS
   => aSbAS
   => aabAS
   =>aabbaS
   =>.aabbaa
 • Dengan penurunan terkanan :
S => aAS
   => aAa
   => aSbAa
   => aSbbaa
    =>aabbaa
Meskipun proses penurunannya berbeda tetapi pohon penurunannya tetap sama.