Формална граматика

У формалној теорији језика, у рачунарству и у лингвистици, формална граматика (чешће само граматика) је прецизна дефиниција неког језика, тј. скуп ниски над неком азбуком. Другим речима, граматика описује које од могућих секвенци симбола у језику у ствари формирају валидне речи и реченице у том језику, али не дефинише њихово значење.

За граматику се обично мисли да генерише валидне ниске језика; такође се може користити као основа препознаваоца који одређује да ли нека ниска припада језику. Да би се описао такав препознавалац, формална теорија језика користи одређене формализме, знане као аутомати.

Граматика се такође може користити за анализирање ниски језика - нпр. да опише њихову интерну структуру. У рачунарству, овај процес је познат као парсирање. Већина језика има врло композитну семантику, нпр. значење њихових извођења је структурирано према њиховој синтакси; због тога, први корак у описивању значења неког извођења у језику јесте да се оно анализира и да се погледа његова анализирана форма (у рачунарству је то дрво извођења).

Формална граматика

Граматика се састоји од скупа правила за добијање низа знакова. Приликом генерисања низа знакова у језику, започиње се са симболом који се назива почетни (или стартни) симбол и потом се примењују правила (у било којем броју, у било којем редоследу). Језик се састоји од свих ниски које се могу добити на овај начин. Формална граматика је граматика која се може једнозначно тумачити. Граматика је једнозначна ако свако реченична форма у тој граматици има тачно једно дрво извођења. У супротном случају, граматика је вишезначна (или амбигвитетна). Вишезначност је својство граматике, а не језика. За један исти језик могу постојати и једнозаначне и вишезначне граматике. Уколоко су за неки језик све граматике вишезначне, онда се каже да је то инхерентно вишезначан језик, за њега није могуће наћи еквивалентну једнозначну граматику.

На пример, ако имамо: азбуку (коју чине симболи a и b), S почетни симбол и ако имамо правила:

1. $S\rightarrow aSb$

2. $S\rightarrow ba$

тада се започиње са почетним симболом S и одабира се правило које ће дати жељену ниску. Ако се одабере прво правило, замењује се S са aSb и добија се ниска aSb на коју може да се даље примени неко од датих правила. Ако се опет примени прво правило, добија се aaSbb. Ово се понавља све док у нисци не буду само терминални симболи, односно a и b. Уколико се одабере друго правило - да се S замени са ba, тада ће да се добије ниска aababb и у њој неће бити нетерминалних симбола, па је тиме завршено једно извођење. Ово извођење се записује $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$. На основу тог претходног процеса извођења закључујемо да је језик ове граматике скуп свих ниски које су облика: $\left\{ba,abab,aababb,aaababbb,...\right\}$.

Формална дефиниција

Класичну формализацију формалних граматика први је предложио Наом Чомски 1950. године. Граматику G чине:

• Коначан скуп N незавршних симбола
• Коначан скуп Σ завршних симбола (још важи да су Σ и N дисјунктни скупови)
• Коначан скуп Р правила, и за свако правило важи: $(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$

где је ${}^{*}$ Клинијева звездица а ${}^{\cup }$ скуповна унија. Дакле, свако извођење пресликава један низ знакова у други, при чему први низ знакова садржи барем један незавршни симбол. У случају да је други низ празан низ, тј. не садржи ниједан симбол, онда се пише грчко слово епсилон ε.

• почетни нетерминални симбол S.

Грамтика се формално дефинише као уређена четворка (N, Σ, P, S). Језик формалне граматике G = (N, Σ, P, S) означен са L(G) је дефинисан као скуп свих оних ниски завршних симбола које могу бити генерисане од стартног незавршног симбола S применом правила P граматике G.

Терминални симболи, тзв. „терминали“ или „токени“, су заправо оно што обично називамо речима. Зову се терминали, јер се анализа на њима завршава, тј. не растављају се за потребе анализе.

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

Извођења су усмерене релације између стрингова сачињених од терминалних и нетерминалних симбола. Разликује им се десна страна од леве. Лева страна може да се представи десном, тј. неки случај може да се сажме у оно на левој страни.

Стартни симбол је нетерминал који представља читав језик генерисан граматиком. Од њега полази анализа. Ако нека реченица може да се редукује у овај нетерминал применом продукција граматике, онда се каже да граматика прихвата ову реченицу, да је написана правилно по датој граматици, или да припада језику којег генерише граматика.

Пример

Посматрајмо граматику $G$ где $N=\left\{S,B\right\}$, $\Sigma =\left\{a,b,c\right\}$, $S$ је почетни симбол, и $P$ је скуп следећих правила:

1. $S\rightarrow aBSc$

2. $S\rightarrow abc$

3. $Ba\rightarrow aB$

4. $Bb\rightarrow bb$

Неки примери генерисаних ниски у ${\boldsymbol {L}}(G)$ су:

• ${\boldsymbol {S}}\Rightarrow _{2}{\boldsymbol {abc}}$
• ${\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{2}aB{\boldsymbol {abc}}c\Rightarrow _{3}a{\boldsymbol {aB}}bcc\Rightarrow _{4}aa{\boldsymbol {bb}}cc$
• ${\boldsymbol {S}}\Rightarrow _{1}{\boldsymbol {aBSc}}\Rightarrow _{1}aB{\boldsymbol {aBSc}}c\Rightarrow _{2}aBaB{\boldsymbol {abc}}cc\Rightarrow _{3}a{\boldsymbol {aB}}Babccc\Rightarrow _{3}aaB{\boldsymbol {aB}}bccc$$\Rightarrow _{3}aa{\boldsymbol {aB}}Bbccc\Rightarrow _{4}aaaB{\boldsymbol {bb}}ccc\Rightarrow _{4}aaa{\boldsymbol {bb}}bccc$

(напомена: $L\Rightarrow _{i}R$ читамо: "L генерише R коришћењем правила под редним бројем i" и генерисани део у међунисци је сваки пут подебљан.)

Ова граматика дефинише језик $L=\left\{a^{n}b^{n}c^{n}|n\geq 1\right\}$ где $a^{n}$ подразумева ниску која има n узастопних појављивања симбола $a$-ова. Дакле, језик ове граматике је скуп свих низова симбола који се састоје од једног или више симбола $a$, након којих следи исто толико појављивања симбола $b$, за којим следи толико појављивања симбола $c$.

Хијерархија Чомског

Када је Ноам Чомски изнео формализам фомалних граматика 1956. године, класификовао их је у типове данас знано као хијерархија Чомског. Постоје следећа подела:

• Десно линеарна (регуларна) граматика (језик описан овом граматиком је десно линеаран или регуларан језик)
• Контексно слободна граматика (језик описан овом граматиком је контексно слободан језик)
• Контексно осетљива граматика (језик описан овом граматиком је контексно осетљив језик)
• Граматика без ограничења, општа (језик описан овом граматиком је језик без ограничења)

Разлика између ових типова јесте у томе што неки типови граматика имају строжа правила па могу изразити и мање формалне језике. Два важна типа су контексно слободне граматике (тип 2) и регуларне граматике (тип 3). Језици који се могу описати оваквим граматикама се зову контексно слободни језици и регуларни језици. Иако нешто мање моћне од граматика без ограничења (тип 0), које могу изразити било који језик који прихвата Тјурингова машина, ова два ограничена типа граматика су најчешће кориштена јер се парсер за њих може врло успешно имплементирати. На пример, све регуларне језике може препознати коначни аутомат, а за корисне подскупове контексно слободних граматика постоје добро познати алгоритми за генерисање ефикасних LL анализатора и LR анализатора који препознавају одговарајуће језике које граматика генерише.

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

Контекстно слободна граматика је граматика у којој се лева страна правила састоји само од једног нетерминалног симбола. Ово ограничење није нетривијално; контексно слободна граматика не може генерисати све језике. Оне које може зовемо контексно слободним језицима. Језик дефинисан у претходном примеру није контексно слободан, и то се може строго доказати кориштењем леме о разрастању за контексно слободне језике, али, на пример језик $\left\{a^{n}b^{n}|n\geq 1\right\}$ (тј. бар један знак $a$ након кога следи исто толико знакова $b$) јесте контексно слободан, пошто га генерише граматика $G_{2}$ са $N=\left\{S\right\}$, $\Sigma =\left\{a,b\right\}$, при чему је $S$ почетни незавршни симбол, а правила су:

1. $S\rightarrow aSb$

2. $S\rightarrow ab$

Контексно слободан језик може бити препознат у времену $O(n^{3})$ користећи алгоритме као што је Ојлеров алгоритам. Другим речима, за сваки контексно слободан језик се може изградити машина која на улазу прима неки низ знакова и одређује у $O(n^{3})$ времену да ли ниска припада језику, при чему је $n$ дужина низа симбола за ту ниску. Надаље, неки важни подскупови контекстно слободних језика могу бити препознати у линеарном времену користећи друге алгоритме.

Други облици генеративних граматика

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

• Граматике са придруженим дрветом су граматике које повећавају експресивност конвенционалних генеративних граматика дозвољавањем правилима преписивања да оперишу на стаблима парсирања уместо на обичним низовима знакова.
• афиксне граматике дозвољавају правилима преписивања да буду обогаћена семантичким атрибутима и операцијама, што се показало корисно за повећање експресивности граматике, као и за изградњу практичних алата за превођење језика.

Аналитичка граматика

Иако су алгоритми парсирања јако дуго проучавани и њихова својства добро схваћена и документована у огромном писаном опусу, већина њих подразумева да је језик који се парсира иницијално описан преко генеративне формалне граматике, те да је циљ генератора парсера трансформисати ту генеративну граматику у парсер. Строго говорећи, генеративна граматика ни на који начин не одговара алгоритму кориштеном за парсирање језика, и различити алгоритми постављају различита ограничења на облик правила које схватају као добро обликоване.

Алтернативни приступ је формализација језика у облику аналитичке граматике, која пак знатно више одговара структури и семантици парсера за језик. Примери формализма аналитичких граматика укључују:

• Машина за језик - директно имплементира неограничене аналитичке граматике (аналитичке граматике неограничених правила). Правила супституције се користе за трансформисање улаза и генерисање излаза и понашања. Систем такође може генерисати Им - дијаграм који показује шта се дешава приликом примене правила аналитичке граматике неограничених правила.
• Синтаксичку анализу наниже (енгл. Top-down parsing language, TDPL): минималистички формализам аналитичких граматика развијен у раним 1970им у сврху проучавања парсера од врха према дну.
• Граматика везе: облик аналитичке граматике дизајниран за лингвистику који изводи синтаксну структуру проучавањем позицијских односа парова речи.
• Синтаксно изражену граматику (eng. Parsing expression grammar, PEG): уопштење TDPL-a дизајнирано да задовољи практичне потребе експресивности програмских језика и писаца компилатора.

Практична примена

У компјутерским језицима обично фигурише контекстно слободна граматика (енгл. Context free grammar - CFG) која креира одговарајуће контекстно независне језике. На пример, програмски језик C, нетерминал који представља читав језик генерисан граматиком, је контекстно зависан али се представља као контекстно независан с тим да се контекстна зависност решава у приступу изради скенера. Скенер је део преводиоца који програм написан у програмском језику разбија на терминалне симболе, и саставни је део front-end преводиоца. Скенер емитује терминалне симболе парсеру као ток (енгл. stream) везујући за сваки семантичку вредност.

Семантичка вредност је придружена терминалном симболу и служи да пренесе додатне информације битне за рад програма. На пример 2435 је број и токен за њега би нпр. био БРОЈ. Међутим када бисмо утврдили да је нпр.

а = 2435;

исправно, тј. да припада неком језику, било би нам потребно да баратамо са конкретном (семантичком) вредношћу која је представљена токеном. Пренос семантичке вредности се решава различито а постоји начин да се дефинише тип за ову вредност у облику уније и једна глобална променљива овог типа. Онда скенер уписује у њу семантичку вредност, а парсер чита и ставља привремено на један ред док не прихвати тражени нетерминал. Приликом прихватања датог нетерминала извршава се акција која треба коначно да одради посао везан за препознавање одређеног нетерминала, и евентуална трајнија складиштења одређених семантичких вредности (нпр. листе). И наравно на самом крају генерише се семантичка вредност за дати нетерминал која ће бити враћена на место са кога је рекурзивно позвана текућа продукција.

Регуларне граматике се најчешће користе. Нпр. када се користи неки љуска (нпр. љуска Беш у Јуниксу или COMMAND.COM у Досу) и ако је потребно да се виде сви фајлови које је могуће извршити, онда се користи:

dir *.exe

Задати параметар *.exe је заправо прихваћен као регуларни израз. Знак звезда замењује било коју комбинацију састављену из карактера дозвољених за креирање имена.