Deterministička kontekstno slobodna gramatika
U teoriji formalnih jezika determinističke kontekstno slobodne gramatike su pravi podskup kontekstno slobodnih gramatika. Determinističke kontekstno slobodne gramatike prepoznaje deterministički potisni automat. Od posebne su važnosti u polju računarstva. Nedeterministički kontekstno slobodni automati zahtevaju znatno složenije programe i potencijalno veći trošak vremenskih i prostornih resursa.
Istorija[uredi | uredi izvor]
Teorijska istraživanja u polju računarstva, tačnije regularnih izraza oko 1960. godine, dovelo je do otkrića da su kontekstno slobodne gramatike ekvivalentne potisnim automatima. Smatralo se da će ove gramatike obuhvatiti sintaksu programskih jezika. Prvi programski jezici su se tada razvijali i bilo je teško pisati kompajlere u tom periodu. Međutim, korišćenje kontekstno slobodnih gramatika je taj posao znatno olakšalo. Determinističke kontekstno slobodne gramatike su tada bile delimično korisne, jer su morale biti sekvencijalno analizirane, a sve to zbog ograničenja memorije računara.
Upotreba[uredi | uredi izvor]
LALR parseri, koji koriste podskup determinističkih kontekstno slobodnih gramatika, imaju praktičnu primenu kao validatori programskog koda. Ovi parseri efikasno obezbeđuju da program može biti generisan iz pravila determinističkih kontekstno slobodnih gramatika. Validacija sintakse je zapravo jedna od operacija koje izvodi kompajler.
Ograničenja[uredi | uredi izvor]
Neke gramatike ne mogu biti prepoznate determinističkim potisnim automatima, tako da ovim gramatika nedostaje potencijal kontekstno slobodnih gramatika.