Kontekstno slobodna gramatika

U formalnoj teoriji jezika, kontekstno slobodna gramatika (KSG) (gramatika tipa 2 prema hijerarhiji Čomskog) je gramatika u kojoj svako pravilo izvođenja ima oblik

V → w

gde je V jedan nezavršni simbol, a w je niska završnih i nezavršnih simbola (ova niska može biti i prazna).

Termin „kontekstno slobodna“ predstavlja činjenicu da se neterminal V može uvek zameniti niskom w bez obzira na kontekst u kome se javlja. Formalni jezik je kontekstno slobodan ako ga generiše neka kontekstno slobodna gramatika.

Kontekstno slobodne gramatike imaju centralnu ulogu u opisu i dizajnu programskih jezika i kompajlera. Koriste se i za analizu sintakse prirodnih jezika.

Istorija

Formalizam kontekstno slobodnih gramatika razvio je Noam Čomski sredinom 1950-tih godina. Kontekstno slobodna gramatika pruža jednostavan i precizan mehanizam za opis metoda kojima se rečenice prirodnog jezika rekurzivno grade od manjih fraza, i eventualno delova ili celih reči.

U toku Algol projekta po prvi put je kontekstno slobodna gramatika primenjena na programske jezike, za opis sintakse Algola. To je postao standardan postupak kad je u pitanju opis konkretnog programskog jezika. Najčešće korišćena notacija za zapis kontekstno slobodne gramatike programskog jezika je Bekus-Naurova forma. Ime je dobila po dvojici članova tima koji je radio na razvoju jezika Algol.

Kontekstno slobodne gramatike su dovoljno jednostavne da omoguće konstrukciju efikasnog sintaksičkog analizatora, tj. parsera, koji za datu nisku utvrđuje da li i kako se ona može izvesti u datoj gramatici. Primer opšte metode sintaksičke analize koja dopušta da se analizira bilo koja KSG je Erlijev algoritam.

Nasuprot tome, češće se koriste mnogo efikasniji algoritmi LL i LR analize koji se mogu primeniti samo na pojedine klase determinističkih kontekstno slobodnih jezika.

Formalne definicije

Definicija 1

Kontekstno slobodna gramatika G je uređena četvorka:

$G=(V\,,\Sigma \,,R\,,S\,)$ gde je:

• $V\,$ konačan skup nezavršnih simbola (pomoćnih ili neterminalnih simbola).

• $\Sigma \,$ konačan skup završnih ili terminalnih simbola, koji je disjunktan sa $V\,$.

• $R\,$ je relacija iz $V\,$ u $(V\cup \Sigma )^{*}$, takva da $\exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R$.

• $S\in V$ početni ili startni simbol, koja predstavlja celu rečenicu (ili program).

Takođe, $R\,$ je konačan skup. Elementi iz $R\,$ se nazivaju pravilima gramatike. Zvezdica

predstavlja operaciju Klinijevog zatvorenja ili iteraciju.

Definicija 2

Za svake dve niske $u,v\in (V\cup \Sigma )^{*}$, kažemo da $u\,$ izvodi $v\,$, u zapisu

$u\Rightarrow v\,$, ako $\exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}$ tako da

$u\,=u_{1}\alpha u_{2}$ i $v\,=u_{1}\beta u_{2}$. Stoga, $\!v$ je rezultat primene pravila

$\!(\alpha ,\beta )$ na $\!u$.

Definicija 3

Za svako $u,v\in (V\cup \Sigma )^{*},u{\stackrel {*}{\Rightarrow }}v$ (ili $u\Rightarrow \Rightarrow v\,$ u

nekim knjigama) ako $\exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0$ tako da $u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v$

Definicija 4

Jezik opisan gramatikom $G=(V\,,\Sigma \,,R\,,S\,)$ je skup

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

Kažemo da gramatika $G\,$ generiše jezik $L\,=\,L(G)$.

Definicija 5

Jezik $L\,$ je kontekstno slobodan ako postoji kontekstno slobodna gramatika, $G\,$ takva da je $L\,=\,L(G)$.

Definicija 5½

Simbol $X\in \Sigma \cup V$ je nekoristan u KS-gramatici $G=(V\,,\Sigma \,,R\,,S\,)$ ako ne postoji izvođenje oblika:

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

gde su $u,v,x\in \Sigma ^{*}$. Simbol koji nije nekoristan naziva se koristan.

Definicija 6

Za gramatiku $G=(V\,,\Sigma \,,R\,,S\,)$ kažemo da je čista (engl. trim) po simbolu $S\,$ ako su ispunjeni sledeći uslovi:

1. za svako $X\in V$, jezik $L_{G}(X)=\{w\in \Sigma ^{*}:X{\stackrel {*}{\Rightarrow }}w\}\neq \emptyset$
2. za svako $X\in V$, postoje $u,v\in \Sigma ^{*}$ takvi da $S{\stackrel {*}{\Rightarrow }}uXv$.

Prvi uslov izražava da svaki pomoćni simbol učestvuje u izvođenju niske završnih simbola, tj. X je produktivan simbol, dok drugi uslov znači da je svaki pomoćni simbol dostupan iz početnog simbola S.

Definicija 7

Gramatika $G=(V\,,\Sigma \,,R\,,S\,)$ je $\epsilon$-slobodna ako je ispunjen jedan od uslova:

1. u skupu pravila R ne postoje $\epsilon$-pravila $(X\longrightarrow \epsilon ,X\in V)$;
2. $S\longrightarrow \epsilon ,\in R$ i S ne učestvuje na desnoj strani nijednog pravila u R.

Definicija 8

Za svako pravilo $X\longrightarrow Y,X,Y\in V$ se kaže da je jednostruko pravilo.

Definicija 9

Kontekstno slobodna gramatika $G=(V\,,\Sigma \,,R\,,S\,)$ je svojstvena (engl. proper) ako je:

1. ε-slobodna i
2. nema jednostrukih pravila.

Primeri

Primer 1

Jednostavna kontekstno slobodna gramatika zadata je sa:

ab;

ovde je | korišćeno da se odvoje različita opcije za isti neterminal; ovo je isto što i sledeće

S → aSb

S → ab

Završni simboli su a i b, dok je jedini neterminal S. Ova gramatika generiše jezik $\{a^{n}b^{n}:n\geq 1\}$ koji nije regularan.

Specijalan karakter ε predstavlja praznu nisku. Transformišemo gornju gramatiku u: ε koja sada generiše jezik $\{a^{n}b^{n}:n\geq 0\}$. Razlika je u tome što jezik generisan transformisanom gramatikom sadrži i praznu nisku, dok jezik generisan originalnom gramatikom ne sadrži.

Primer 2

Kontekstno slobodna gramatika za sintaksno ispravne infiksne algebarske izraze nad promenljivama x, y i z:

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

U ovoj gramatici se može, na primer, izvesti niska "(x + y) * x - z * y / (x + x )" na sledeći način:

"S" je početna niska. "S - S" je rezultat primene petog pravila izvođenja: [S → S - S] na neterminal S.

"S * S - S / S" je rezultat primene petog pravila izvođenja na prvo S i sedmog pravila na drugo S.

"(S ) * S - S / (S )" je rezultat primene poslednjeg pravila izvođenja na određene neterminale.

"(S + S) * S - S * S / (S + S )" je rezultat primene četvrtog pravila izvođenja na određene neterminale.

"(x + y) * x - z * y / (x + x )" je konačan rezultat, dobijen primenom prva tri pravila izvođenja kojima se neterminali S zamenjuju sa završnim simbolima x, y i z.

Ova gramatika je višeznačna, što znači da istoj niski odgovara više od jednog drveta izvođenja. Na primer, u niski "x + y * z" može prvo biti analizirano + ili *, što naravno daje različite rezultate.

Primer 3

Kontekstno slobodna gramatika za jezik koji sadrži sve niske nad azbukom {a,b} koje sadrže različiti broj simbola a i b je:

V

TaT

TbT

bTaT | ε

Ovde, nezavršni simbol T može da izgeneriše sve niske koje imaju isti broj simbola a i b. Nezavršni simbol U

generiše sve niske koje imaju više završnih simbola a nego b, dok iz neterminala V mogu se generisati niske sa manjim

brojem pojavljivanja završnog simbola a nego b.

Primer 4

Još jedan primer kontekstno slobodnog jezika je $\{b^{n}a^{m}b^{2n}:n\geq 0,m\geq 0\}$. Ovo nije regularan jezik, ali je kontekstno slobodan jer može biti generisan sledećom kontekstno slobodnom gramatikom:

A

ε

Izvođenje i sintaksičko drvo

Postoje dva uobičajena načina da se opiše kako se data niska može izvesti u datoj gramatici polazeći od startnog simbola.

Najjednostavniji način je da se redom navedu niske simbola, počevši od startnog simbola i završivši sa datom niskom, pri čemu

se u svakom koraku navodi pravilo koje je primenjeno. Ako se prihvati pravilo da se u svakom koraku prvo zamenjuje krajnje levi

neterminal, onda je za kontekstno slobodnu gramatiku sasvim dovoljna samo lista primenljivih pravila. Ovaj postupak se još

naziva i izvođenje nalevo. Na primer, za sledeću gramatiku:

(1)S → S + S

(2)S → 1

(3) S → a

i nisku "1 + 1 + a" izvođenjem nalevo pravila izvođenja primenjuju se sledećim redosledom [ (1), (1), (2), (2), (3)].

Analogno se može uvesti izvođenje nadesno, kao izvođenje u kome se svaki put zamenjuje prvo krajnje desni neterminal. U ovom

slučaju za datu nisku pravila izvođenja se primenjuju sledećim redosledom [ (1), (3), (1), (2), (2)].

Razlika između izvođenja nalevo i izvođenja nadesno je važna jer je za većinu sintaksičkih analizatora transformacija ulazne niske definisana dodeljivanjem dela koda za svako pravilo izvođenja u gramatici koji se izvršava kad god je pravilo primenjeno. Bitno je da znamo da li sintaksički analizator primenom izvođenja nadesno ili nalevo određuje koji neterminal će biti zamenjen jer od te odluke zavisi redosled izvršavanja delova koda. Pogledajte, na primer, LL analizatore i LR analizatore.

Izvođenje na neki način nameće i hijerarhijsku strukturu izvedenih niski. Na primer, za nisku "1 + 1 + a“ izvođenje nalevo ovako izgledalo:

S → S + S (1)

   → S + S + S (1)

   → 1 + S + S (2)

   → 1 + 1 + S (2)

   → 1 + 1 + a (3)

struktura niske bi bila:

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

gde { ... }_S označava podnisku koja je prepoznata da pripada skupu S. Ova hijerarhija može se predstaviti u obliku drveta:

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

Ovo drvo se naziva sintaksičko drvo (videti apstraktno sintaksičko drvo) date niske. U ovom slučaju izvođenjem nalevo i izvođenjem nadesno dobija se isto sintaksičko drvo. Ipak, postoji još jedno izvođenje nalevo iste niske:

S → S + S (1)

   → 1 + S (2)

   → 1 + S + S (1)

   → 1 + 1 + S (2)

   → 1 + 1 + a (3)

i ono određuje sledeće sintaksičko drvo:

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

Ako postoji niska jezika generisanog datom gramatikom za koju postoji više od jednog sintaksičkog drveta, onda kažemo da je ta gramatika višeznačna. Za takve gramatike je teško analizirati jer sintaksički analizator ne može uvek da odluči koje gramatičko pravilo treba da primeni. Obično je višeznačnost svojstvo gramatike, a ne jezika i mogu se naći jednoznačne gramatike koje generišu isti kontekstno slobodan jezik. Ipak, postoje jezici za koje su sve gramatike višeznačne. Za takve jezike kažemo da su inherentno višeznačni.

Normalne forme

Svaka kontekstno slobodna gramatika koja je ε-slobodna može se transformisati u gramatiku čije nijedno pravilo nije ε-pravilo. Ako, ipak, $\epsilon \in L(G)$, tada je jedino ε-pravilo $S\rightarrow \epsilon$, a S se ne pojavljuje sa desne strane nijednog pravila gramatike. Za svaku ε-slobodnu kontekstno slobodnu gramatiku postoji ekvivalentna gramatika u normalnoj formi Čomskog ili normalnoj formi Gribah. Pod terminom „ekvivalentne“ podrazumeva se da te dve gramatike generišu isti jezik.

Zbog prilično jednostavnog oblika pravila izvođenja u gramatici koja je u normalnoj formi Čomskog, ovaj normalni oblik ima i teoretske i praktične primene. Na primer, za datu kontekstno slobodnu gramatiku se normalna forma Čomskog može iskoristiti za konstrukciju Kuk-Janger-Kasami algoritma koji proverava da li data niska pripada jeziku generisanom gramatikom ili ne.

Neodlučivi problemi

KSG imaju nekih zanimljivih neodlučivih problema, iako su neke operacije nad kontekstno slobodnim gramatikama odlučive zbog njihove ograničene moći. Jedan od najjednostavnijih i najpoznatijih je problem „da li KSG generiše jezik svih niski“. Ovaj problem možemo posmatrati kao redukciju dobro poznatog neodlučivog problema „da li Tjuringova mašina prihvata određeni ulaz“. Ta redukcija se oslanja na koncept istorije izračunavanja, niske koja u potpunosti opisuje tok izračunavanja Tjuringove mašine. Možemo konstruisati KSG koja generiše sve niske koje nisu prihvatljive istorije izračunavanja za određenu Tjuringovu mašinu za određeni ulaz. Dakle, ta KSG će generisati sve niske samo ako mašina ne prihvati taj ulaz.

Posledica ovoga je da je problem „da li dve KSG generišu isti jezik“ takođe neodlučiv, jer je neodlučiv problem da li je KSG ekvivalentna trivijalnoj KSG koja odlučuje jezik svih niski.

Problem „da li je neka gramatika višeznačna“ u opštem slučaju je neodlučiv.

Bitno je spomenuti da je problem „da li kontekstno osetljiva gramatika generiše kontekstno slobodan jezik“ takođe neodlučiv.

Proširenja

Očigledan način da se proširi formalizam kontekstno slobodnih gramatika je da se dozvoli da neterminali imaju argumente, vrednosti koje se prosleđuju zajedno sa pravilima. Time je omogućeno da se na prirodan način predstave osobine prirodnih i programskih jezika, kao što su korektna upotreba i definicije identifikatora. Što se tiče prirodnih jezika jednostavno možemo izraziti da se u rečenicama subjekat i predikat moraju slagati po broju.

U računarstvu, proširenja kontekstno slobodnih gramatika se ostvaruju preko afiksnih gramatika, atributskih gramatika, indeksiranih gramatika i engl. Van Wijngaarden gramatika sa dva nivoa.

Slična proširenja postoje u lingvistici.

Postoji još jedno proširenje koje omogućava da se dodatni simboli pojave sa leve strane pravila, ograničavajući njihovu primenu. Na taj način se uvodi formalizam kontekstno osetljivih gramatika

Transformacije KS-gramatika

Napomena

• Svaka KS-gramatika se može efektivno svesti na ekvivalentnu čistu gramatiku eliminacijom nekorisnih simbola.

• Svaka KS-gramatika se može efektivno svesti na ekvivalentnu svojstvenu gramatiku, tako što se prvo oslobodi od ε-pravila, a zatim i od jednostrukih pravila.

• Za svaku KS-gramatiku, postoji njoj ekvivalentna gramatika bez levo rekurzivnih pravila. Levo rekurzivna pravila su nepodesna za neke od metoda sintaksičke analize, tako da ih je ponekad pogodno eliminisati.

Na osnovu prethodnih zaključaka važi i sledeća

Teorema: Za svaki kontekstno slobodni jezik bez prazne reči postoji čista i svojstvena gramatika bez levo rekurzivnih pravila koja generiše taj jezik.

Primene u lingvistici

Čomski se u početku nadao da će prevazići ograničenja kontekstno slobodnih gramatika dodajući pravila transformacije.

Takva pravila su još jedno standardno sredstvo tradicionalne lingvistike. Međutim, proizvoljne transformacije ne smeju biti dozvoljene, jer su previše moćne. Većina proizvodnih gramatika je posvećen nalaženju načina da se profine opisni mehanizmi koji uključuju gramatiku kojom je opisana struktura rečenica i pravila transformacije tako da budu dozvoljene samo one stvari koje prirodni jezik zapravo dopušta. Njegov stav da prirodni jezici nisu kontekstno slobodni je aktuelan još od tad, iako su njegovi primeri koji se tiču neadekvatnosti KSG kasnije oboreni. Džerald Gazdar i Džefri Pulum raspravljali su o ovom uprkos činjenici da je vrlo malo konstrukcija prirodnog jezika koje nisu kontekstno slobodne, dok je većina zapravo kontekstno slobodna.

Svojstva kontekstno slobodnih jezika

• Alternativna definicija KS-jezika: Jezik je kontekstno slobodan ako i samo ako postoji potisni automat koji ga prihvata.
• Unija, proizvod (konkatenacija) dva KS-jezika je KS-jezik.
• Iteracija kontekstno slobodnog jezika je kontekstno slobodan jezik.
• Slika u ogledalu kontekstno slobodnog jezika je kontekstno slobodan jezik.
• Svaki regularan jezik je ujedno i kontekstno slobodan jer se može opisati regularnom gramatikom.
• Presek KS-jezika i regularnog jezika je uvek kontekstno slobodan jezik.
• Presek dva kontekstno slobodna jezika, kao i komplement kontekstno slobodnog jezika ne mora biti kontekstno slobodan jezik.
• Postoje kontekstno osetljivi jezici koji nisu kontekstno slobodni.

Vidi još

• Kontekstno osetljiva gramatika
• Formalna gramatika