Analisis Sintaks

    Ketika string input (kode sumber atau program dalam beberapa bahasa) diberikan ke kompiler, kompilator memprosesnya dalam beberapa fase, mulai dari analisis leksikal (memindai input dan membaginya menjadi token) hingga pembuatan kode target.

    Analisis Sintaksis atau Parser merupakan tahap kedua, yaitu setelah analisis leksikal. Ia memeriksa struktur sintaksis dari masukan yang diberikan, yaitu apakah masukan yang diberikan dalam sintaks yang benar (dari bahasa di mana masukan telah ditulis) atau tidak. Itu dilakukan dengan membangun struktur data, yang disebut pohon Parse atau pohon Sintaks. Pohon parse dibangun dengan menggunakan Grammar bahasa yang telah ditentukan sebelumnya dan string input. Jika string masukan yang diberikan dapat diproduksi dengan bantuan pohon sintaks (dalam proses derivasi), string masukan ditemukan dalam sintaks yang benar. jika tidak, kesalahan dilaporkan oleh penganalisis sintaks.

    Dalam bahasa pemrograman, yang disebut terminal adalah token. Contoh terminal adalah token. Contoh token misalnya kata kunci (keyword) if, while, dan identifier serta bilangan. Sedangkan non-terminal merupakan variabel-variabel sintak yang menyatakan himpunan terminal maupun non-terminal. Dalam proses parsing terjadi proses penggantian suatu non terminal dengan sederetan himpunan non terminal dan terminal yang berada dalam sisi kanan produksinya.

    Proses ini disebut sebagai derivasi. Contohnya non-terminal if_stmt merupakan himpunan terminal if, then, else, dan non-terminal expr dan stmt, yang membentuk aturan produksi : if_stmt ?? if expr then stmt else stmt. Dari semua simbol non-terminal yang digunakan, ada satu simbol yang bertindak sebagai simbol awal, yaitu simbol yang pertama kali diderivasi. Aturan produksi menggambarkan bagaimana kombinasi non-terminal dan terminal yang benar menurut tata bahasa yanbg bersangkutan. Dalam proses penguraian, token-token yang dihasilkan dalam analisis leksikal dibentuk menjadi pohon urai (parse tree).

Ada dua jenis derivasi, yaitu :

      1. Derivasi terkiri (Left Most Derivation)

   Derivasi terkiri akan menderivasi suatu aturan produksi mulai dari non-terminal yang paling kiri.

      2. Derivasi terkanan (Right Most Derivation).

   Derivasi terkanan akan menderivasi suatu aturan produksi mulai dari non-terminal yang paling kanan.

Grammar

Berdasarkan rule dibagi 4 (Noam Chomsky) :

1. Context Sensitive Grammar

Pada bahasa context sensitive, panjang string pada ruas kiri panjang ruas kanan ()

Contoh : Abc ? Def ; CD ? eF

2. Context Free Grammar

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu proses analisis sintaksis. Pada bahasa bebas konteks, batasannya bertambah lagi dengan ruas kiri haruslah tepat satu symbol variable.

Contoh: B ? CdeFg ; D ? BcDe

3. Regular Grammar

Pada bahasa reguler, batasannya bertambah dengan ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan. Artinya bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bla terdapat simbol variabel tersebut hanya bejumlah satu (1) dan terletak di posisi paling kanan.

4. UnRestricted Grammar 

Tata Bahasa UnRestricted yang tidak merupakan anggota dari klasifikasi lainnya ditandai dengan aturan produksi yang bagian sebelah kirinya lebih panjang dari bagian sebelah kanan. Aturan produksi yang mengandung simbol hampa (^) pasti merupakan Tata Bahasa UnRestricted dan tidak termasuk klasifikasi lainnya.