Analisis Sintaksis

Pohon (tree) adalah suatu graph terhubung yang tidak sirkuler, memiliki satu buah simpul (vertex/node) yaitu akar (root) dan dari akar ini memiliki lintasan (edge) ke setiap simpul yang lain. 

Pohon penurunan (derivation tree / syntax tree / parse tree) berguna untuk menggambarkan bagaimana cara memperoleh suatu untai (string) dengan cara menurunkan atau mengganti simbol-simbol variabel menjadi terminal. Setiap simbol variabel akan diturunkan atau diganti menjadi terminal. 

Simbol variabel     => dinotasikan dengan huruf besar (kapital).

Simbol terminal    => dinotasikan dengan huruf kecil, menempati posisi daun (leaf).

Simbol awal          => variabel S, menempati posisi puncak pohon (root).

Proses penurunan (parsing) bisa dilakukan antara lain dengan cara: 

1. penurunan melalui arah kiri (leftmost derivation): simbol variabel terkiri yang diperluas lebih dulu.
2. penurunan melalui arah kanan (rightmost derivation): simbol variabel terkananyang diperluas lebih dulu.

Contoh :

Tata bahasa bebas konteks memiliki aturan produksi: 

S -> AB               {S menurunkan variabel A B}

A-> aA | a           {A menurunkan terminal a variabel A atau terminal a}

B-> bB | b           {B menurunkan terminal b variabel B atau terminal b}

Berikut ini adalah gambar pohon penurunan untuk memperoleh untai ‘aabbb’

Catatan, melalui aturan produksi yang samadapat dihasilkan beberapa buah untai. 

Contoh: ‘aabbb’, ‘ab’, ‘aaaabbbb’, dan lain-lain.

Metode parsing 

Analisis sintaksis (proses parsing) berguna untuk memeriksa urutan kemunculan token. Pada proses ini, hal yang perlu diperhatikan adalah: 

1. Kebutuhan waktu eksekusi.
2. Penanganan kesalahan.
3. Penanganan kode

Metode parsing dapat dilakukan secara top down atau bottom up, dimana untai masukan akan dibaca (scan) dari arah kiri ke kanan. 

Metode parsing top down

Membangun pohon parse dari puncak pohon (root) menuju ke daun (leaf). Penelusuran dilakukan dari simbol awal sampai dengan simbol terminal. 

Metode parsing top down  dapat dilakukan menggunakan proses: 

1. backtrack (dikerjakan secara brute force).
2. no backtrack (dikerjakan secara recursive descent parser).

Proses backtrack: proses ini dilakukan seandainya pada saat mengerjakan suatu langkah x menyebabkan kesalahan, maka akan melakukan proses backtrack yaitu proses kembali ke kondisi terakhir sebelum langkah x dikerjakan. 

Proses brute force: mencoba semua kemungkinan secara terstruktur. Kelemahan proses brute force adalah relatif membutuhkan waktu yang lamakarena mencoba semua aturan produksi yang ada, dan membutuhkan alokasi memori yang besar untuk mencatat lokasi proses, sehingga dimungkinkan untuk melakukan proses backtrack. 

Metode parsing bottom up

Pohon parse dibangun dari daun (leaf) menuju ke puncak pohon (root). Penelusuran dilakukan dari simbol terminal menuju ke simbol awal. Kebalikan dari metode parsing top down. 

Metode parsing bottom up  dapat dilakukan menggunakan proses: 

1. shift reduce parsing
2. operator precedence parsing
3. simple precedence grammars parsingd.LR grammars parsing