Формална граматика — разлика између измена

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

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

* '''Десно линеарна (регуларна) граматика''' (језик описан овом граматиком је '''десно линеаран или регуларан језик''')

* '''Контексно слободна граматика''' (језик описан овом граматиком је '''контексно слободан језик''')

* '''Контексно осетљива граматика''' (језик описан овом граматиком је '''контексно осетљив језик''')

* '''Граматика без ограничења, општа''' (језик описан овом граматиком је језикј'''език без ограничења''')

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

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

[[Контекстно слободна граматика]] је граматика у којој се лева страна правила састоји само од једног [[нетерминалан симбол|нетерминалног симбола]]. овоОво ограничење није нетривијално; контексно слободна граматика не може генерисати све језике. Оне које може зовемо контексно слободним језицима.

Језик дефинисан у претходном примеру ''није'' контексно слободан, и то се може строго доказати кориштењем [[леме о проширењу]] за контексно слободне језике, али, на пример језик <math>\left \{ a^{n}b^{n} | n \ge 1 \right \}</math> (тј. бар један знак <math>a</math> након кога следи исто толико знакова <math>b</math>) јесте контексно слободан, пошто га генерише граматика <math>G_2</math> са <math>N=\left \{S\right \}</math>, <math>\Sigma=\left \{a,b\right \}</math>, при чему је <math>S</math> почетни незавршни симбол, а правила су:

Контексно слободан језик може бити препознат у времену <math>O(n^3)</math> користећи алгоритме као што је [[Ојлер|Ојлеров]] алгоритам. Другим речима, за сваки контексно слободан језик се може изградити машинумашина која на улазу прима неки низ знакова и одређује у <math>O(n^3)</math> времену припадада ли ниска припада [[језик|језику]], при чему је <math>n</math> дужина низа симбола за ту ниску. Надаље, неки важни подскупови контекстно слободних језика могу бити препознати у линеарном времену користећи друге алгоритме.

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

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

* ''Top-down parsing language'' (TDPL): минималистички формализам аналитичких граматика развијен у раним 1970им у сврху проучавања [[парсер|парсера]] од врха према дну.

* ''Link grammar'': облик аналитичке граматике дизајниран за [[лингвистика | лингвистику]] који изводи синтаксну структуру проучавањем позицијских односа парова речи.

* ''Parsing expression grammar'' (PEG): уопштење TDPL-a дизајнирано да задовољи практичне потребе експресивности [[програмски језик | програмских језика]] и писаца компилатора.