section_heading: Chomskyjeva hijerarhija
paragraph_text: Kada je Noam Chomsky prvi iznio formalizam generativnih gramatika 1956., klasificirao ih je u tipove danas poznate kao dio Chomskyjeve hijerarhije. Razlika između ovih tipova jest što imaju povećavajuće stroga produkcijska pravila i stoga mogu izraziti sve manje formalnih jezika. Dva važna tipa su kontekstno neovisne gramatike (tip 2) i regularne gramatike (tip 3). Jezici koji se mogu opisati ovakvim gramatikama se respektivno zovu kontekstno neovisni jezici i regularni jezici. Premda nešto manje moćne od gramatike neograničenih produkcija (tip 0), koje mogu izraziti bilo koji jezik koji prihvaća Turingov stroj, ova dva ograničena tipa gramatika su najčešće korištena jer se parser za njih može učinkovito implementirati. Na primjer, sve regularne jezike može prepoznati konačni automat, a za korisne podskupove kontekstno neovisnih gramatika postoje dobro poznati algoritmi za generiranje učinkovitih LL parsera i LR parsera koji prepoznaju odgovarajuće jezike koje gramatike generiraju.