Детерминистичка контекстно слободна граматика

Из Википедије, слободне енциклопедије

У теорији формалних језика детерминистичке контекстно слободне граматике су прави подскуп контекстно слободних граматика. Детерминистичке контекстно слободне граматике препознаје детерминистички потисни аутомат. Од посебне су важности у пољу рачунарства. Недетерминистички контекстно слободни аутомати захтевају знатно сложеније програме и потенцијално већи трошак временских и просторних ресурса.

Историја[уреди]

Теоријска истраживања у пољу рачунарства, тачније регуларних израза око 1960. године, довело је до открића да су контекстно слободне граматике еквивалентне потисним аутоматима. Сматрало се да ће ове граматике обухватити синтаксу програмских језика. Први програмски језици су се тада развијали и било је тешко писати компајлере у том периоду. Међутим, коришћење контекстно слободних граматика је тај посао знатно олакшало. Детерминистичке контекстно слободне граматике су тада биле делимично корисне, јер су морале бити секвенцијално анализиране, а све то због ограничења меморије рачунара.

Употреба[уреди]

LALR парсери, који користе подскуп детерминистичких контекстно слободних граматика, имају практичну примену као валидатори програмског кода. Ови парсери ефикасно обезбеђују да програм може бити генерисан из правила детерминистичких контекстно слободних граматика. Валидација синтаксе је заправо једна од операција које изводи компајлер.

Ограничења[уреди]

Неке граматике не могу бити препознате детерминистичким потисним аутоматима, тако да овим граматика недостаје потенцијал контекстно слободних граматика.

Видети[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.