Детерминистичка контекстно слободна граматика
У теорији формалних језика детерминистичке контекстно слободне граматике су прави подскуп контекстно слободних граматика. Детерминистичке контекстно слободне граматике препознаје детерминистички потисни аутомат. Од посебне су важности у пољу рачунарства. Недетерминистички контекстно слободни аутомати захтевају знатно сложеније програме и потенцијално већи трошак временских и просторних ресурса.
Историја
[уреди | уреди извор]Теоријска истраживања у пољу рачунарства, тачније регуларних израза око 1960. године, довело је до открића да су контекстно слободне граматике еквивалентне потисним аутоматима. Сматрало се да ће ове граматике обухватити синтаксу програмских језика. Први програмски језици су се тада развијали и било је тешко писати компајлере у том периоду. Међутим, коришћење контекстно слободних граматика је тај посао знатно олакшало. Детерминистичке контекстно слободне граматике су тада биле делимично корисне, јер су морале бити секвенцијално анализиране, а све то због ограничења меморије рачунара.
Употреба
[уреди | уреди извор]LALR парсери, који користе подскуп детерминистичких контекстно слободних граматика, имају практичну примену као валидатори програмског кода. Ови парсери ефикасно обезбеђују да програм може бити генерисан из правила детерминистичких контекстно слободних граматика. Валидација синтаксе је заправо једна од операција које изводи компајлер.
Ограничења
[уреди | уреди извор]Неке граматике не могу бити препознате детерминистичким потисним аутоматима, тако да овим граматика недостаје потенцијал контекстно слободних граматика.