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

У формалној теорији језика, контекстно слободна граматика (КСГ) (граматика типа 2 према хијерархији Чомског) је граматика у којој свако правило извођења има облик

V → w

где је V један незавршни симбол, а w је ниска завршних и незавршних симбола (ова ниска може бити и празна).

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

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

Историја

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

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

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

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

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

Дефиниција 1

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

$G=(V\,,\Sigma \,,R\,,S\,)$ где је:

$V\,$ коначан скуп незавршних симбола (помоћних или нетерминалних симбола).

$\Sigma \,$ коначан скуп завршних или терминалних симбола, који је дисјунктан са $V\,$ .

$R\,$ је релација из $V\,$ у $(V\cup \Sigma )^{*}$ , таква да $\exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R$ .

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

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

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

Дефиниција 2

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

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

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

$\!(\alpha ,\beta )$ на $\!u$ .

Дефиниција 3

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

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

Дефиниција 4

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

L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}

.

Кажемо да граматика $G\,$ генерише језик $L\,=\,L(G)$ .

Дефиниција 5

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

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

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

S\Rightarrow ^{*}uXv\Rightarrow ^{*}uxv

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

Дефиниција 6

За граматику $G=(V\,,\Sigma \,,R\,,S\,)$ кажемо да је чиста (енгл. trim) по симболу $S\,$ ако су испуњени следећи услови:

за свако $X\in V$ , језик $L_{G}(X)=\{w\in \Sigma ^{*}:X{\stackrel {*}{\Rightarrow }}w\}\neq \emptyset$
за свако $X\in V$ , постоје $u,v\in \Sigma ^{*}$ такви да $S{\stackrel {*}{\Rightarrow }}uXv$ .

Први услов изражава да сваки помоћни симбол учествује у извођењу ниске завршних симбола, тј. X je продуктиван симбол, док други услов значи да је сваки помоћни симбол доступан из почетног симбола S.

Дефиниција 7

Граматика $G=(V\,,\Sigma \,,R\,,S\,)$ је $\epsilon$ -слободна ако је испуњен један од услова:

у скупу правила R ne postoje $\epsilon$ -правила $(X\longrightarrow \epsilon ,X\in V)$ ;
$S\longrightarrow \epsilon ,\in R$ и S не учествује на десној страни ниједног правила у R.

Дефиниција 8

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

Дефиниција 9

Контекстно слободна граматика $G=(V\,,\Sigma \,,R\,,S\,)$ је својствена (енгл. proper) ако је:

Примери

Пример 1

Једноставна контекстно слободна граматика задата је са:

ab;

овде је | коришћено да се одвоје различита опције за исти нетерминал; ово је исто што и следеће

S → aSb

S → ab

Завршни симболи су a и b, док је једини нетерминал S. Ова граматика генерише језик $\{a^{n}b^{n}:n\geq 1\}$ који није регуларан.

Специјалан карактер ε представља празну ниску. Трансформишемо горњу граматику у: ε која сада генерише језик $\{a^{n}b^{n}:n\geq 0\}$ . Разлика је у томе што језик генерисан трансформисаном граматиком садржи и празну ниску, док језик генерисан оригиналном граматиком не садржи.

Пример 2

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

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:

V

TaT

TbT

bTaT | ε

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

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

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

Пример 4

Још један пример контекстно слободног језика је $\{b^{n}a^{m}b^{2n}:n\geq 0,m\geq 0\}$ . Ово није регуларан језик, али је контекстно слободан јер може бити генерисан следећом контекстно слободном граматиком:

A

ε

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

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

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

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

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

назива и извођење налево. На пример, за следећу граматику:

(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)

→ S + S + S (1)

→ 1 + S + S (2)

→ 1 + 1 + S (2)

→ 1 + 1 + a (3)

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

{ { { 1 }_S + { 1 }_S }_S + { a }_S }_S

где { ... }_S означава подниску која је препозната да припада скупу S. Ова хијерархија може се представити у облику дрвета:

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

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

S → S + S (1)

→ 1 + S (2)

→ 1 + S + S (1)

→ 1 + 1 + S (2)

→ 1 + 1 + a (3)

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

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

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

Нормалне форме

Свака контекстно слободна граматика која је ε-слободна може се трансформисати у граматику чије ниједно правило није ε-правило. Ако, ипак, $\epsilon \in L(G)$ , тада је једино ε-правило $S\rightarrow \epsilon$ , а S се не појављује са десне стране ниједног правила граматике. За сваку ε-слободну контекстно слободну граматику постоји еквивалентна граматика у нормалној форми Чомског или нормалној форми Грибах. Под термином „еквивалентне“ подразумева се да те две граматике генеришу исти језик.

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

Неодлучиви проблеми

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

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

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

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

Проширења

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

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

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

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

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

Напомена ^[а]

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

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

За сваку КС-граматику, постоји њој еквивалентна граматика без лево рекурзивних правила. Лево рекурзивна правила су неподесна за неке од метода синтаксичке анализе, тако да их је понекад погодно елиминисати.

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

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

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

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

Таква правила су још једно стандардно средство традиционалне лингвистике. Међутим, произвољне трансформације не смеју бити дозвољене, јер су превише моћне. Већина производних граматика је посвећен налажењу начина да се профине описни механизми који укључују граматику којом је описана структура реченица и правила трансформације тако да буду дозвољене само оне ствари које природни језик заправо допушта. Његов став да природни језици нису контекстно слободни је актуелан још од тад, иако су његови примери који се тичу неадекватности КСГ касније оборени. Џералд Газдар и Џефри Пулум расправљали су о овом упркос чињеници да је врло мало конструкција природног језика које нису контекстно слободне, док је већина заправо контекстно слободна.

Својства контекстно слободних језика

Алтернативна дефиниција КС-језика: Језик је контекстно слободан ако и само ако постоји потисни аутомат који га прихвата.
Унија, производ (конкатенација) два КС-језика је КС-језик.
Итерација контекстно слободног језика је контекстно слободан језик.
Слика у огледалу контекстно слободног језика је контекстно слободан језик.
Сваки регуларан језик је уједно и контекстно слободан јер се може описати регуларном граматиком.
Пресек КС-језика и регуларног језика је увек контекстно слободан језик.
Пресек два контекстно слободна језика, као и комплемент контекстно слободног језика не мора бити контекстно слободан језик.
Постоје контекстно осетљиви језици који нису контекстно слободни.

Напомене

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

Види још

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

[а]