Kontekstno neovisna gramatika

U lingvistici i računarstvu, kontekstno neovisna gramatika (KNG) (rjeđe još i kontekstno slobodna gramatika ili gramatika neovisna o sadržaju, te još i bezokolinska gramatika) je formalna gramatika u kojoj je svaka produkcija oblika

V → w

gdje je V nezavršni znak a w niz znakova (string) koji se sastoji od završnih i/ili nezavršnih znakova. Termin "kontekstno neovisna" izražava činjenicu da će nezavršni znak V uvijek biti zamijenjen nizom znakova w neovisno o kontekstu u kojem se pojavljuje. Formalni jezik je kontekstno neovisni jezik ako postoji kontekstno neovisna gramatika koja ga generira.

Kontekstno neovisne gramatike su dovoljno moćne da opišu sintaksu većine programskih jezika; ustvari sintaksa većine programskih jezika i jest specificirana koristeći kontekstno neovisne gramatike. U drugu ruku, kontekstno neovisne gramatike su dovoljno jednostavne da dozvole izgradnju učinkovitih algoritama parsiranja koji, za dani niz znakova, određuju može li se i kako niz generirati iz gramatike. Earleyjev parser je primjer takvog algoritma, dok LL i LR parseri barataju tek s nešto ograničenim podskupovima kontekstno neovisnih gramatika.

BNF (Backus-Naurov oblik) je najuobičajenija notacija korištena za izražavanje kontekstno neovisnih gramatika.

Nisu svi formalni jezici kontekstno neovisni; dobro poznat protuprimjer je $\{a^{n}b^{n}c^{n}:n\geq 0\}$, skup svih nizova znakova koji sadrže jednak broj znakova a, nakon kojeg slijedi jednak broj znakova b i jednak broj znakova c.

Formalna definicija

Baš kao i svaka formalna gramatika, kontekstno neovisna gramatika G se može definirati kao uređena četvorka:

$G=(V_{t},V_{n},P,S)$ gdje je

• $V_{t}$ konačan skup završnih znakova
• $V_{n}$ konačan skup nezavršnih znakova
• $P$ konačan skup pravila produkcija
• $S$ je element skupa $V_{n}$, istaknuti početni nezavršni znak
• elementi skupa $P$ su oblika

$V_{n}\longrightarrow (V_{t}\cup V_{n})^{*}$

Za jezik L kažemo da je kontekstno neovisni jezik (KNJ) ako je njegova gramatika kontekstno neovisna. Preciznije, to je jezik čije su riječi, rečenice i fraze načinjene od znakova i riječi iz kontekstno neovisne gramatike. Obično je KNJ oblika L=L(G). Dolje su dani primjeri za KNG ali ne i za KNJ.

Primjeri

Primjer 1

Jednostavna kontekstno neovisna gramatika je zadana sa:

S → aSb | ε

gdje je znak | korišten kao separator višestrukih opcija za isti nezavršni znak, a ε stoji za prazni niz. Ova gramatika generira jezik $\{a^{n}b^{n}:n\geq 0\}$ koji nije regularan.

Primjer 2

Slijedi kontekstno neovisna gramatika za sintaktički ispravne infiksne algebarske izraze nad varijablama x, y i z:

S → x | y | z | S + S | S - S | S * S | S/S | (S)

Ova gramatika može, na primjer, generirati niz znakova "( x + y ) * x - z * y / ( x + x )".

Ova gramatika je nejednoznačna, što znači da može generirati isti niz znakova s više različitih stabala parsiranja.

Primjer 3

Kontekstno neovisna gramatika za jezik koji se sastoji od svih nizova znakova nad abecedom {a,b} koji sadrže različit broj znakova a i b jest

S → U | V

U → TaU | TaT

V → TbV | TbT

T → aTbT | bTaT | ε

Ovdje T može generirati sve nizove znakova s jednakim brojem znakova a i b, U generira sve nizove znakova koji sadrže više znakova a nego b, dok V generira sve nizove znakova koji sadrže manje znakova a nego b.

Primjer 4

Drugi primjer kontekstno neovisnog jezika jest $\{b^{n}a^{m}b^{2n}:n\geq 0,m\geq 0\}$. Ovo nije regularan jezik, ali je kontekstno neovisan i može ga generirati sljedeća kontekstno neovisna gramatika:

S → bSbb | A

A → aA | ε

Drugi primjeri

Kontekstno neovisne gramatike nisu ograničene isključivo u primjeni na matematičke ("formalne") jezike. Na primjer, postoje indicije da je klasa tamilske poezije zvana Venpa upravljana kontekstno neovisnom gramatikom.

Produkcije i sintaksna stabla

Postoje dva uobičajena načina za opis načina na koji se dani niz znakova može izvesti iz početnog nezavršnog znaka dane gramatike. Najjednostavniji način jest navesti uzastopne nizove znakova, počinjući s početnim nezavršnim znakom i završujući s nizom znakova, te produkcijskim pravilima koja su primijenjena. Ako uvedemo strategiju "uvijek prvo zamijeni krajnji lijevi nezavršni znak", tada za je za kontekstno neovisne gramatike sama lista primijenjenih produkcijskih pravila dovoljna. Ova se tehnika zove postupak generiranja niza zamjenom krajnje lijevog nezavršnog znaka (engl. leftmost derivation). Na primjer, ako razmatramo sljedeću gramatiku:

(1) S → S + S

(2) S → 1

(3) S → a

i niz znakova "1 + 1 + a", tada tom tehnikom dobijemo listu produkcijskih pravila [ (1), (1), (2), (2), (3) ]. Analogno možemo definirati postupak generiranja niza zamjenom krajnje desnog nezavršnog znaka (engl. rightmost derivation). U tom slučaju lista glasi [ (1), (3), (1), (2), (2)].

Razlika između postupaka generiranja zamjenom krajnje lijevog i krajnje desnog nezavršnog znaka je važna pošto je za većinu parsera transformacija ulaznog niza znakova definirana davanjem dijela koda za svaku produkciju gramatike koji se izvršava kadgod je produkcija primijenjena. Stoga je važno znati odlučuje li parser primjenom tehnike zamjene krajnje lijevog ili krajnje desnog nezavršnog znaka, pošto ova odluka određuje redoslijed izvršavanja dijelova koda. Za detalje pogledati na primjer LL parsere i LR parsere.

Produkcija također na neki način nameće hijerarhijsku strukturu izvedenog niza znakova. Na primjer, struktura niza znakova "1 + 1 + a" bi, sudeći po postupku generiranja niza zamjenom krajnje lijevog nezavršnog znaka, bila:

S→S+S (1)

S→S+S+S (1)

S→1+S+S (2)

S→1+1+S (2)

S→1+1+a (3)

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

gdje { ... }_S označava podniz koji je prepoznat da pripada skupu S. Ova se hijerarhija također može shvatiti kao stablo:

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

Ovo se stablo zove konkretno sintaksno stablo (vidi također apstraktno sintaksno stablo) niza znakova. U ovom slučaju predstavljeni postupci generiranja zamjenom krajnje lijevog i desnog nezavršnog znaka definiraju isto sintaksno stablo, iako se međutim isti niz znakova može generirati još jednim postupkom generiranja zamjenom krajnje lijevog nezavršnog znaka

S→ S + S (1)

S→ 1 + S (2)

S→ 1 + S + S (1)

S→ 1 + 1 + S (2)

S→ 1 + 1 + a (3)

koji definira sljedeće sintaksno stablo:

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

Ako za neke nizove znakova jezika gramatike postoji više od jednog stabla parsiranja, tada za gramatiku kažemo da je nejednoznačna gramatika. Takve gramatike je obično teško parsirati jer parser ne može uvijek odlučiti koje pravilo gramatike treba primijeniti.

Normalne forme

Svaka kontekstno neovisna gramatika koja ne generira prazni niz se može preoblikovati u istovjetnu gramatiku u Chomskyjevom normalnom obliku ili Greibachovom normalnom obliku. Ovdje "istovjetan" označava da gramatike generiraju iste jezike.

Zbog osobito jednostavnog oblika produkcija gramatika u Chomskyjevom normalnom obliku, ovaj normalni oblik ima i teoretske i praktične implikacije. Na primjer, za danu kontekstno neovisnu gramatiku se Chomskyjev normalni oblik može iskoristiti za konstrukciju polinomnog algoritma koji odlučuje pripada li dani niz znakova jeziku kojeg gramatika generira ili ne (CYK algoritam).

Neodlučivi problemi

Iako su neke operacije nad kontekstno neovisnim gramatikama odlučive zbog njihove ograničene moći, KNG imaju nekih zanimljivih neodlučivih problema. Jedan od najjednostavnijih i najpoznatijih jest problem odlučivanja generira li KNG jezik svih nizova znakova. Može se demonstrirati redukcija na ovaj problem iz dobro poznatog neodlučivog problema određivanja prihvaća li Turingov stroj neki pojedinačni ulaz. Ta redukcija koristi koncept povijesti izračuna, niz znakova koji u cijelosti opisuje tijek izračuna (komputacije) Turingovog stroja. Možemo konstruirati KNG koja generira sve nizove znakova koji nisu prihvatljive povijesti izračuna za neki pojedinačni Turingov stroj za neki pojedinačni ulaz, te će stoga KNG generirati sve nizove znakova samo ako stroj ne prihvaća taj ulaz.

Kao posljedica toga, također je neodlučivo opisuju li dvije KNG isti jezik, pošto ionako ne možemo odlučiti je li KNG istovjetna trivijalnoj KNG koja odlučuje jezik svih nizova znakova.

U drugu ruku, problem određivanja prihvaća li KNG barem jedan niz znakova jest odlučiv.

Također je korisni napomenuti da je problem određivanja opisuje li kontekstno ovisna gramatika kontekstno neovisan jezik također neodlučiv.

Svojstva kontekstno neovisnih jezika

• Alternativna i istovjetna definicija kontekstno neovisnih jezika koristi nedeterminističke potisne automate: jezik je kontekstno neovisan ako i samo ako ga takav automat može prihvatiti.
• Jezik se također može modelirati kao skup svih slijedova završnih znakova koje gramatika generira. Ovaj model je koristan u razumijevanju skupovnih operacija nad jezicima.
• Unija i nadovezivanje (konkatenacija) dvaju kontekstno neovisnih jezika je kontekstno neovisan jezik, ali presjek ne mora biti.
• Prevrtanje kontekstno neovisnog jezika je kontekstno neovisan jezik, ali komplement ne mora biti.
• Svaki regularni jezik je kontekstno neovisan pošto može biti opisan regularnom gramatikom.
• Presjek kontekstno neovisnog jezika i regularnog jezika je uvijek kontekstno neovisan.
• Postoje kontekstno ovisni jezici koji nisu kontekstno neovisni.
• Da bi se dokazalo da je dani jezik kontekstno ovisan, može se koristiti svojstvo napuhavanja za kontekstno ovisne jezike.

Vidi još

• Formalna gramatika

Izvori

• Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X

• Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3