Изворни код странице Контекстно слободна граматика

У [[формална теорија језика|формалној теорији језика]], '''контекстно слободна граматика (КСГ)''' (граматика типа 2 према [[хијерархија Чомског|хијерархији Чомског]]) је [[формална граматика|граматика]] у којој свако правило извођења има облик
:-{''V'' → ''w''}-
где је ''-{V}-'' један незавршни симбол, а ''-{w}-'' је ниска завршних и незавршних симбола (ова ниска може бити и празна). 

Термин „контекстно слободна“ представља чињеницу да се нетерминал ''-{V}-'' може увек заменити ниском ''-{w}-'' без обзира на контекст у коме се јавља. 
[[Формални језик]] је [[контекст-слободни језик|контекстно слободан]] ако га генерише нека контекстно слободна граматика.

Контекстно слободне граматике имају централну улогу у опису и дизајну [[програмски језик|програмских језика]] и [[компилатор|компајлера]]. Користе се и за анализу [[синтакса|синтаксе]] [[природни језик|природних језика]].


== Историја ==
Формализам контекстно слободних граматика развио је [[Ноам Чомски]] средином [[1950]]-тих година. Контекстно слободна граматика пружа једноставан и прецизан механизам за опис метода којима се реченице природног језика [[рекурзија|рекурзивно]] граде од мањих фраза, и евентуално делова или целих речи.

У току [[Алгол]] пројекта по први пут је контекстно слободна граматика примењена на [[програмски језик|програмске језике]], за опис синтаксе Алгола. То је постао стандардан поступак кад је у питању опис конкретног програмског језика. Најчешће коришћена нотација за запис контекстно слободне граматике програмског језика је [[Бакус–Наурова форма|Бекус-Наурова форма]]. Име је добила по двојици чланова тима који је радио на развоју језика Алгол.

Контекстно слободне граматике су довољно једноставне да омогуће конструкцију ефикасног [[raščlanjivanje|синтаксичког анализатора]], тј. [[raščlanjivanje|парсера]], који за дату ниску утврђује да ли и како се она може извести у датој граматици. Пример опште методе [[raščlanjivanje|синтаксичке анализе]] која допушта да се анализира било која КСГ је [[Erlijev analizator|Ерлијев алгоритам]]. 

Насупрот томе, чешће се користе много ефикаснији алгоритми [[ЛЛ анализатор|ЛЛ]] и [[ЛР анализа|ЛР анализе]] који се могу применити само на поједине класе [[детерминистички контекстно слободан језик|детерминистичких контекстно слободних језика]].



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

'''''Дефиниција 1'''''

Контекстно слободна граматика ''-{G}-'' је уређена четворка:

<math>G = (V\,, \Sigma\,, R\,, S\,)</math>
где је:

* <math>V\,</math> коначан скуп ''незавршних'' симбола (помоћних или нетерминалних симбола).

* <math>\Sigma\,</math> коначан скуп ''завршних'' или ''терминалних'' симбола, који је дисјунктан са <math>V\,</math>.

* <math>R\,</math> је релација из <math>V\,</math> у <math>(V\cup\Sigma)^{*}</math>, таква да <math>\exist\, w\in 

(V\cup\Sigma)^{*}: (S,w)\in R</math>.

* <math>S\in V</math> ''почетни'' или ''стартни'' симбол, која представља целу реченицу (или програм).

Такође, <math>R\,</math> је коначан скуп. Елементи из <math>R\,</math> се називају ''правилима'' граматике. Звездица 

представља операцију [[Клинијево затворење|Клинијевог затворења]] или итерацију.


'''''Дефиниција 2'''''

За сваке две ниске <math>u, v\in (V\cup\Sigma)^{*}</math>, кажемо да <math>u\,</math> изводи <math>v\,</math>, у запису 

<math>u\Rightarrow v\,</math>, ако <math>\exists (\alpha, \beta)\in R, u_{1}, u_{2}\in (V\cup\Sigma)^{*}</math> тако да 

<math>u\,=u_{1}\alpha u_{2}</math> и <math>v\,=u_{1}\beta u_{2}</math>. Стога, <math>\! v</math> је резултат примене правила 

<math>\! (\alpha, \beta)</math> на <math>\! u</math>.


'''''Дефиниција 3'''''

За свако <math>u, v\in (V\cup\Sigma)^{*}, u\stackrel{*}{\Rightarrow} v</math> (или <math>u\Rightarrow\Rightarrow v\,</math> у 

неким књигама) ако <math>\exists u_{1}, u_{2}, \cdots u_{k}\in (V\cup\Sigma)^{*}, k\geq 0</math> тако да <math>u\Rightarrow 

u_{1}\Rightarrow u_{2}\cdots\Rightarrow u_{k}\Rightarrow v</math> 


'''''Дефиниција 4'''''

Језик описан граматиком <math>G = (V\,, \Sigma\,, R\,, S\,)</math> је скуп

:<math>L(G) = \{ w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\}</math>.
Кажемо да граматика <math>G\,</math> генерише језик <math>L\,=\,L(G)</math>.


'''''Дефиниција 5'''''

Језик <math>L\,</math> је контекстно слободан ако постоји контекстно слободна граматика, <math>G\,</math> таква да је <math>L\,=\,L(G)</math>.

'''''Дефиниција 5½'''''

Симбол <math>X \in \Sigma \cup V</math> је ''некористан'' у КС-граматици <math>G = (V\,, \Sigma\,, R\,, S\,)</math> ако не постоји извођење облика:

<center><math>S \Rightarrow^* uXv \Rightarrow^* uxv</math></center>

где су <math>u, v, x \in \Sigma^{*}</math>. Симбол који није некористан назива се ''користан''.

'''''Дефиниција 6'''''

За граматику <math>G = (V\,, \Sigma\,, R\,, S\,)</math> кажемо да је ''чиста'' ({{јез-енгл|trim}}) по симболу <math>S\,</math> ако су испуњени следећи услови:
# за свако <math>X\in V</math>, језик <math>L_{G}(X)=\{ w\in\Sigma^{*} : X\stackrel{*}{\Rightarrow} w\}\ne\emptyset</math>
# за свако <math>X\in V</math>, постоје <math>u, v\in \Sigma^{*}</math> такви да <math>S\stackrel{*}{\Rightarrow} uXv</math>.
Први услов изражава да сваки помоћни симбол учествује у извођењу ниске завршних симбола, тј. -{X}- je [[продуктиван симбол]], док други услов значи да је сваки помоћни симбол [[доступан симбол|доступан]] из почетног симбола -{S}-.


'''''Дефиниција 7'''''

Граматика <math>G = (V\,, \Sigma\,, R\,, S\,)</math> је <math>\epsilon</math>''-слободна'' ако је испуњен један од услова:
# у скупу правила -{R}- ne postoje <math>\epsilon</math>-''правила'' <math>(X\longrightarrow\epsilon, X \in V)</math>;
# <math>S\longrightarrow\epsilon,\in R</math> и -{S}- не учествује на десној страни ниједног правила у -{R}-.


'''''Дефиниција 8'''''

За свако правило <math>X \longrightarrow Y, X,Y \in V</math> се каже да је ''једноструко'' правило.


'''''Дефиниција 9'''''

Контекстно слободна граматика <math>G = (V\,, \Sigma\,, R\,, S\,)</math> је ''својствена'' ({{јез-енгл|proper}}) ако је:
# [[Елиминација е-правила|ε-слободна]] и 
# [[Елиминација једноструких правила|нема једноструких правила]].

== Примери ==

=== Пример 1 ===
Једноставна контекстно слободна граматика задата је са:
:-{S → aSb | ab}-;
овде је | коришћено да се одвоје различита опције за исти нетерминал; ово је исто што и следеће 
:-{S → aSb}-
:-{S → ab}-
Завршни симболи су ''a'' и ''b'', док је једини нетерминал -{S}-. Ова граматика генерише језик <math> \{ a^n b^n : n \ge 1 \} </math> који није [[regularni jezik|регуларан]].

Специјалан карактер ε представља празну ниску. Трансформишемо горњу граматику у:
-{S → aSb | ε}-
која сада генерише језик <math> \{ a^n b^n : n \ge 0 \} </math>. Разлика је у томе што језик генерисан трансформисаном граматиком садржи и празну ниску, док језик генерисан оригиналном граматиком не садржи.


=== Пример 2 ===
Контекстно слободна граматика за синтаксно исправне инфиксне алгебарске изразе над променљивама -{x, y}- и -{z}-: 

:-{ S → x | y | z | S + S | S - S | S * S | S/S | (S)}-
У овој граматици се може, на пример, извести ниска "-{(x + y) * x - z * y / (x + x )}-" на следећи начин:

"-{S}-" је почетна ниска.
"-{S - S}-" је резултат примене петог правила извођења: -{[S → S - S]}- на нетерминал -{S}-.

"-{S * S - S / S}-" је резултат примене петог правила извођења на прво -{S}- и седмог правила на друго -{S}-.

"-{(S ) * S - S / (S )}-" је резултат примене последњег правила извођења на одређене нетерминале.

"-{(S + S) * S - S * S / (S + S )}-" је резултат примене четвртог правила извођења на одређене нетерминале.

"-{(x + y) * x - z * y / (x + x )}-" је коначан резултат, добијен применом прва три правила извођења којима се нетерминали -{S}- замењују са завршним симболима -{x, y}- и -{z}-.

Ова граматика је [[вишезначна граматика|вишезначна]], што значи да истој ниски одговара више од једног [[дрво извођења|дрвета извођења]]. На пример, у ниски "-{x + y * z}-" може прво бити анализирано + или *, што наравно даје различите резултате.

=== Пример 3 ===
Контекстно слободна граматика за језик који садржи све ниске над азбуком {a,-{b}-} које садрже различити број симбола -{a}- и -{b}- je:

:-{S → U | V}-
:-{U → TaU | TaT}-
:-{V → TbV | TbT}-
:-{T → aTbT | bTaT | ε}-

Овде, незавршни симбол -{T}- може да изгенерише све ниске које имају исти број симбола -{a}- и -{b}-. Незавршни симбол -{U}- 

генерише све ниске које имају више завршних симбола а него -{b}-, док из нетерминала -{V}- могу се генерисати ниске са мањим 

бројем појављивања завршног симбола -{a}- него -{b}-.


=== Пример 4 ===
Још један пример контекстно слободног језика је <math> \{ b^n a^m b^{2n} : n \ge 0, m \ge 0 \} </math>. Ово није регуларан језик, али је контекстно слободан јер може бити генерисан следећом контекстно слободном граматиком:

:-{S → bSbb | A }-
:-{A → aA | ε}-


== Извођење и синтаксичко дрво ==

Постоје два уобичајена начина да се опише како се дата ниска може извести у датој граматици полазећи од стартног симбола. 

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

се у сваком кораку наводи правило које је примењено. Ако се прихвати правило да се у сваком кораку прво замењује крајње леви 

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

назива и извођење налево. На пример, за следећу граматику:
:(1)-{S → S + S}-
:(2)-{S → 1 }-
:(3) -{S → a }-

и ниску "1 + 1 + a" извођењем налево правила извођења примењују се следећим редоследом [ (1), (1), (2), (2), (3)].

Аналогно се може увести извођење надесно, као извођење у коме се сваки пут замењује прво крајње десни нетерминал. У овом 

случају за дату ниску правила извођења се примењују следећим редоследом [ (1), (3), (1), (2), (2)].

Разлика између извођења налево и извођења надесно је важна јер је за већину синтаксичких анализатора трансформација улазне ниске дефинисана додељивањем дела кода за свако правило извођења у граматици који се извршава кад год је правило примењено. Битно је да знамо да ли синтаксички анализатор применом извођења надесно или налево одређује који нетерминал ће бити замењен јер од те одлуке зависи редослед извршавања делова кода. Погледајте, на пример, [[ЛЛ анализатор]]е и [[ЛР анализатор]]е.

Извођење на неки начин намеће и хијерархијску структуру изведених ниски. На пример, за ниску "1 + 1 + а“ извођење налево овако изгледало: 

:-{S → S + S (1)}-
:-{&nbsp;&nbsp; → S + S + S (1)}-
:-{&nbsp;&nbsp; → 1 + S + S (2)}-
:-{&nbsp;&nbsp; → 1 + 1 + S (2)}-
:-{&nbsp;&nbsp; → 1 + 1 + a (3)}-

структура ниске би била:

: -{{ { { 1 }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub> + { a }<sub>S</sub> }<sub>S</sub>}-
где { ... }<sub>S</sub> означава подниску која је препозната да припада скупу -{S}-. Ова хијерархија може се представити у облику дрвета:

            S
           /|\
          / | \
         /  |  \
        S  '+'  S
       /|\      |
      / | \     |
     S '+' S   'a'
     |     |
    '1'   '1'

Ово дрво се назива ''синтаксичко дрво'' (видети [[апстрактно синтаксичко дрво]]) дате ниске. У овом случају извођењем налево и извођењем надесно добија се исто синтаксичко дрво. Ипак, постоји још једно извођење налево исте ниске:

:-{S → S + S (1)}-
:-{&nbsp;&nbsp; → 1 + S (2)}-
:-{&nbsp;&nbsp; → 1 + S + S (1)}-
:-{&nbsp;&nbsp; → 1 + 1 + S (2) }-
:-{&nbsp;&nbsp; → 1 + 1 + a (3)}-

и оно одређује следеће синтаксичко дрво:

            S 
           /|\
          / | \
         /  |  \
        S  '+'  S
        |      /|\
        |     / | \
       '1'   S '+' S
             |     |
            '1'   'a'

Ако постоји ниска језика генерисаног датом граматиком за коју постоји више од једног синтаксичког дрвета, онда кажемо да је та граматика ''[[вишезначна граматика|вишезначна]]''. За такве граматике је тешко анализирати јер синтаксички анализатор не може увек да одлучи које граматичко правило треба да примени. Обично је вишезначност својство граматике, а не језика и могу се наћи једнозначне граматике које генеришу исти контекстно слободан језик. Ипак, постоје језици за које су све граматике вишезначне. За такве језике кажемо да су инхерентно вишезначни.


== Нормалне форме ==
Свака контекстно слободна граматика која је -{ε}--слободна може се трансформисати у граматику чије ниједно правило није -{ε}--правило. Ако, ипак, <math>\epsilon \in L(G)</math>, тада је једино -{ε}--правило <math>S \rarr \epsilon</math>, а -{S}- се не појављује са десне стране ниједног правила граматике.
За сваку -{ε}--слободну контекстно слободну граматику постоји еквивалентна граматика у [[нормална форма Чомског|нормалној форми Чомског]] или [[нормална форма Грибах|нормалној форми Грибах]]. Под термином „еквивалентне“ подразумева се да те две граматике генеришу исти језик.

Због прилично једноставног облика правила извођења у граматици која је у нормалној форми Чомског, овај нормални облик има и теоретске и практичне примене. На пример, за дату контекстно слободну граматику се нормална форма Чомског може искористити за конструкцију [[Кук-Јангер-Касами алгоритам|Кук-Јангер-Касами алгоритма]] који проверава да ли дата ниска припада језику генерисаном граматиком или не.

== Неодлучиви проблеми ==
КСГ имају неких занимљивих неодлучивих проблема, иако су неке операције над контекстно слободним граматикама одлучиве због њихове ограничене моћи. Један од најједноставнијих и најпознатијих је проблем „да ли КСГ генерише језик свих ниски“. Овај проблем можемо посматрати као редукцију добро познатог неодлучивог проблема „да ли [[Тјурингова машина]] прихвата одређени улаз“. Та редукција се ослања на концепт ''историје израчунавања'', ниске која у потпуности описује ток израчунавања Тјурингове машине. Можемо конструисати КСГ која генерише све ниске које нису прихватљиве историје израчунавања за одређену Тјурингову машину за одређени улаз. Дакле, та КСГ ће генерисати све ниске само ако машина не прихвати тај улаз.

Последица овога је да је проблем „да ли две КСГ генеришу исти језик“ такође неодлучив, јер је неодлучив проблем да ли је КСГ еквивалентна тривијалној КСГ која одлучује језик свих ниски.

Проблем „да ли је нека граматика вишезначна“ у општем случају је неодлучив.

Битно је споменути да је проблем „да ли [[контекстно-сензитивна граматика|контекстно осетљива граматика]] генерише контекстно слободан језик“ такође неодлучив.

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

У рачунарству, проширења контекстно слободних граматика се остварују преко [[афиксна граматика|афиксних граматика]], [[атрибутска граматика|атрибутских граматика]], [[индексирана граматика|индексираних граматика]] и {{јез-енгл|Van Wijngaarden}} [[граматика са два нивоа]].

Слична проширења постоје у лингвистици.

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

== Трансформације КС-граматика ==

Напомена {{напомена|У одељку 2, Формалне дефиниције, дате су дефиниције некорисних симбола, једноструких правила, као и чистих, ε-слободних и својствених граматика.}}

* Свака КС-граматика се може ефективно свести на еквивалентну ''чисту'' граматику [[Елиминација некорисних симбола|елиминацијом некорисних симбола]].

* Свака КС-граматика се може ефективно свести на еквивалентну ''својствену'' граматику, тако што се прво [[Елиминација е-правила|ослободи од ε-правила]], а затим и од [[Елиминација једноструких правила|једноструких правила]].

* За сваку КС-граматику, постоји њој еквивалентна граматика без лево рекурзивних правила. [[Лева рекурзија|Лево рекурзивна правила]] су неподесна за неке од метода [[raščlanjivanje|синтаксичке анализе]], тако да их је понекад погодно елиминисати.

На основу претходних закључака важи и следећа

'''Теорема:''' За сваки [[контекст-слободни језик|контекстно слободни језик]] без празне речи постоји чиста и својствена граматика без лево рекурзивних правила која генерише тај језик.

== Примене у лингвистици ==

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

Таква правила су још једно стандардно средство традиционалне лингвистике. Међутим, произвољне трансформације не смеју бити дозвољене, јер су превише моћне. Већина производних граматика је посвећен налажењу начина да се профине описни механизми који укључују граматику којом је описана структура реченица и правила трансформације тако да буду дозвољене само оне ствари које природни језик заправо допушта. Његов став да природни језици нису контекстно слободни је актуелан још од тад, иако су његови примери који се тичу неадекватности КСГ касније оборени. [[Џералд Газдар]] и [[Џефри Пулум]] расправљали су о овом упркос чињеници да је врло мало конструкција природног језика које нису контекстно слободне, док је већина заправо контекстно слободна.
 
== Својства контекстно слободних језика ==
* Алтернативна дефиниција КС-језика: Језик је контекстно слободан ако и само ако постоји потисни аутомат који га прихвата.
* Унија, производ (конкатенација) два КС-језика је КС-језик.
* Итерација контекстно слободног језика је контекстно слободан језик. 
* Слика у огледалу контекстно слободног језика је контекстно слободан језик.
* Сваки [[regularni jezik|регуларан језик]] је уједно и контекстно слободан јер се може описати [[regularni jezik|регуларном граматиком]].
* Пресек КС-језика и регуларног језика је увек контекстно слободан језик.
* Пресек два контекстно слободна језика, као и комплемент контекстно слободног језика не мора бити контекстно слободан језик. 
* Постоје [[контекст-сензитивни језик|контекстно осетљиви језици]] који нису контекстно слободни.

{{Формални језици и граматике}}

== Напомене ==
{{напомене}}

== Види још ==
* [[Контекстно-сензитивна граматика|Контекстно осетљива граматика]]
* [[Формална граматика]]

{{нормативна контрола}}

[[Категорија:Преводиоци (рачунарство)]]
[[Категорија:Формални језици]]