ALGORITMA PEMOGRAMAN

HIRARKI CHOMSKY

NOAM CHOMSKY melakukan penggolongan tingkatan bahasa menjadi 4, disebut dengan hirarki Chomsky

CHOMSKY LANGUAGE CLASS	GRAMMAR
3  _______	REGULAR
2  _______	Bebas konteks / contex free grammar
1  ­_______	Contex sensitive
0  _______	unrestricted

® Bahasa bebas konteks/CFG menjadi dasar pembentukkan suatu parser/proses analisis sintaksis

® Bagian sintaks dalam suatu kompilator kebanyakkan di definisikkan dalam tata bahasa bebas konteks yang didekskripsikan secara formal dengan notasi BNF (Backus Normal Form)

Beberapa symbol yang dipakai dalam notasi BNF :

::             =   identic dengan symbol  -> pada aturan produksi

|                   idem dengan symbol  serupa pada aturan produksi

< >               mengapit symbol /non terminal pengulanhan

{ }               0 sampai N kali

Contoh : terdapat aturan produksi

                       E -> T | T + E | T – E, T -> a

NOTASI BNF : E ::= < T > | < T > + < E > | < T > - < E >, T ::= a

® PARSING

Parser adalah mesibn yang mengarahkan kompilator dan mengontrol scanner.

® ADA 2 ALGORITMA

1.       TOP DOWN , membentuk abstrak sintaks tree mulai dari atas

2.       BOTTOM UP, parsing dimulai pada token dan membentuk pohon. Cabang demi cabang, menggabungkan menjadi pohon yang besar.