Формална граматика
Из пројекта Википедија
Формална граматика је граматика која се може записати и једнозначно тумачити.
Језик је скуп свих реченица које твори одређена граматика.
Граматику чине:
- коначан скуп 'терминалних симбола'.
- коначан скуп 'нетерминалних симбола'.
- продукције за сваки нетерминални симбол.
- 'стартни нетерминални симбол'.
Терминални симболи, краће терминали или токени су заправо оно што обично називамо речима. Зову се терминали, јер се анализа на њима завршава, тј. не растављају се за потребе анализе.
Нетерминални симболи, тзв. нетерминали, су апстрактне ознаке за граматичке конструкције. Они се могу раздвојити анализом у зависности од продукција граматике.
Продукције су усмерене релације између стрингова сачињених од терминалних и нетерминалних симбола. Разликује им се десна страна од леве. Лева страна може да се представи десном, тј. неки случај може да се сажме у оно на левој страни.
Стартни симбол је нетерминал који представља читав језик генерисан граматиком. Од њега полази анализа. Ако нека реченица може да се редукује у овај нетерминал применом продукција граматике, онда се каже да граматика прихвата ову реченицу, да је написана правилно по датој граматици, или да припада језику који твори граматика.
Постоје три врсте формалних граматика, а међу њима влада релација поретка:
- Контекстно зависни језици су надскуп контекстно независних језика. Појам 'контекстно зависно' се употребљава да опише случајеве када нека реч у реченици има другачија значења у зависности од комбинације осталих речи и њене позиције у реченици. Ово је случај са језицима који користе људи за комуникацију.
- Контекстно независни језици су генерисани контекстно слободним граматикама. У реченицама ове граматике значење неке речи не зависи од контекста у ком су употребљене.
- Регуларни језици творени су регуларним граматикама. Они су подскуп контекстно независних језика.
Практична примена
У компјутерским језицима обично фигурише контекстно слободна граматика (engl. Context free grammar - CFG) која креира одговарајуће контекстно независне језике. Програмски језик Ц (енгл. 'C'), нетерминал који представља читав језик генерисан граматиком, је на пример контекстно завистан, али се представља као контекстно независтан с тим да се контекстна зависност решава у приступу изради скенера. Скенер је део преводиоца који програм написан у програмском језику разбије на токене, и саставни је део Front-end преводиоца. Скенер емитује токене парсеру као ток (енгл. 'stream') везујући за сваки семантичку вредност.
Семантичка вредност је придружена токену и служи да пренесе додатне информације битне за рад програма. На пример 2435 је број и токен за њега био би рецимо NUMBER. Међутим када би смо утврдили да је рецимо
а = 2435;
исправно тј. припада неком језику, било би нам потребно да баратамо са конкретном (семантичком) вредношћу која је представљена токеном. Пренос семантичке вредности се решава различито а мени је познат начин да се дефинише тип за ову вредност у облику уније (union за језик Ц) и једна глобална променљива овог типа. Онда скенер уписује у њу семантичку вредност, а парсер чита и ставља привремено на један ред док не прихвати тражени нетерминал. Приликом прихватања датог нетерминала извршава се акција која треба коначно да одради посао везан за препознавање одређеног нетерминала, и евентуална трајнија складиштења одређених семантичких вредности (нпр. листе). И наравно на самом крају генерише се семантичка вредност за дати нетерминал која ће бити враћена на место са кога је рекурзивно позвана текућа продукција.
Регуларне граматике се међутим најчешће користе. На пример када се користити неки шел ('shell'), нпр. у DOS-у стандардни COMMAND.COM и ако је потребно да се виде сви фајлови које је могуће извршити, онда се користи:
DIR *.EXE
Задати параметар *.EXE је заправо прихваћен као регуларни израз (енгл. Regular Expression - RE). Знакови звезда мењају било коју комбинацију састављену из карактера дозвољених за креирање имена...
