vrpca

3. Izvođenje i transformiranje gramatika

to je zgodno društvo veseljaka
koji lijegaju u zoru i kasno ustaju
misleći samo na ljubav i sviranje gitare
jedina im je životna filozofija
"imamo čitav život za zabavljanje
imamo cijelu smrt za odmaranje"
ne rade ništa drugo do slavljenja
svakoga trenutka
pozdrava punom mjesecu, proslave
proljeća
pa im i ne preostaje vremena za rad
jedina im je životna filozofija
"imamo čitav život za zabavljanje
imamo cijelu smrt za odmaranje"
i često se prepoznam u njima
kao i oni tratio sam život na svim
vjetrovima
i govorim si da su mi to braća ili djeca jedina im je životna filozofija
"imamo čitav život za zabavljanje
imamo cijelu smrt za odmaranje"
ako proðu kraj vas dobro ih
pogledajte
i kao oni budite ludi i kao oni budite
pijani
jer njihova jedina ludost je želja da
budu slobodni
jedina im je
životna filozofija
"imamo čitav život za zabavljanje
imamo cijelu smrt za odmaranje"
i oni će ostariti, neka ostanu to što
jesu
sa starim utopijama na čudne
načine
ljubavnika, poeta i onih što spjevaju
pjesme
jedina im je životna filozofija
"imamo čitav život za zabavljanje
imamo cijelu smrt za odmaranje"
filozofija
la philosophie
(georges moustaki/dubravka stojnić)

  1. IZVOÐENJE GRAMATIKA
  2. TRANSFORMIRANJE GRAMATIKA
  3. Pitanja i zadaci

I ovo je poglavlje posvećeno gramatikama. Prvi, "empirijski" dio, bavi se pokušajem dobivanja odgovora na pitanje: Kako za dani jezik izvesti odgovarajuću gramatiku? U drugom dijelu poglavlja, polazeći od pretpostavke da smo izveli kakvu-takvu gramatiku nekog jezika, dani su postupci transformiranja gramatike u jednostavniji oblik, a ponekad i u zadani oblik ili "formu".

3.1 IZVOÐENJE GRAMATIKA

Vidjeli smo da je za danu gramatiku moguće promatrati sve nizove izvoðenja i dobiti skup svih rečenica jezika kojeg generira. Meðutim, pitanje je kako se za dani jezik može definirati (izvesti) odgovarajuća gramatika i je li ona jedinstvena. Nažalost, ne postoji gotov "recept" koji bi propisao kako za dani jezik izvesti gramatiku.
Ponekad ćemo u nekom jeziku prepoznati podjezik za koji znamo gramatiku pa neće biti problema da se dodaju produkcije koje će generirati zadani jezik. Na primjer, ako smo definirali gramatiku prirodnih brojeva, neće biti problema da definiramo gramatiku parnih ili neparnih prirodnih brojeva, ili, ako smo definirali gramatiku cijelih brojeva, neće biti problema da definiramo gramatiku realnih brojeva napisanih u normalnom ili eksponencijalnom obliku kao što je, na primjer, u Pascalu.

Primjer 3.1

Izvedimo gramatiku jezika {anbn:   n≥l}. Prvo, ab je u jeziku, pa se može napisati:

S → ab

Sljedeća je rečenica aabb, gdje smo s ab označili prvu rečenicu. Ta se rečenica dobila dopisujući na početak prve rečenice znak a, na kraj znak b. Treća je rečenica aaabbb, dobila se istom operacijom, ali primijenjenoj na drugu rečenicu, itd. Dakle, ako je α rečenica, tada je i aαb takoðer rečenica, a to je "klasični" primjer rekurzije, pa je gramatika danog jezika:

S → ab | aSb

Primjer 3.2

No, izvoðenje gramatike jezika {anbncn: n≥l} sigurno je složenije. Započet ćemo najjednostavnijom rečenicom: abc koja nam daje produkciju:

(1)S → abc

Iduća je rečenica aabbcc. Ne možemo je izravno dobiti iz prve. Ideja je da se krene slijeva i ispred prvog b u abc umetne ponovo abc, pa imamo aabcbc, a to je nova alternativa:

(2)S → aSQ

Iz niza izvoðenja

     S => aSQ => aabcQ

bolje se vidi značenje novo uvedenog simbola Q. On mora biti zamijenjen na neki način s bc, a to se može postići ovako:

cQ → Qc

bQc → bbcc

Dakle, gramatika s produkcijama:

S → abc | aSQ

bQc → bbcc

cQ → Qc

generira jezik {anbncn: n≥l}. Na primjer:

S => aSQ => aaSQQ => aaaSQQQ    => aaaabcQQQ

  => aaaabQcQ     => aaaabbccQQ => aaaabbcQcQ

  => aaaabbQccQ   => aaaabbbcccQ => aaaabbbccQc

  =>  aaaabbbcQcc => aaaabbbQccc => aaaabbbbcccc

Primjer 3.3

Izvedimo gramatiku jezika prirodnih brojeva {1,2,3, . . .}. Prvo, 1, 2, ..., 9 su u jeziku:

N → B

B → 1| 2| 3| 4| 5| 6| 7| 8| 9

Drugo, ako prirodni broj ima više od jedne znamenke, mora započeti s B, potom slijedi niz znamenki, npr. C

N → BC

C → B| 0| CC| ε

Primijetiti da se umjesto ove dvije produkcije u proširenom BNF-u može napisati:

N → B{C}

C → B| 0

Sada ne bi bio problem izvesti gramatike jezika parnih ili neparnih prirodnih brojeva, što vam ostavljamo za vježbu.

Primjer 3.4

Izvedimo gramatiku jezika {4,8,12,16,20/...}, tj. jezika koji sadrži prirodne brojeve djeljive s četiri. U matematici smo naučili da su to brojevi 4 i 8, odnosno, ako broj ima više od jedne znamenke, djeljiv je s četiri ako je broj sačinjen od njegove dvije posljednje znamenke djeljiv s četiri ili se završava s 00. Na primjer, u jeziku su nizovi 20, 1004, 12345678900 ili 101010196. Dakle, na najvišoj razini, možemo definirati gramatiku:

S → 4| 8| D| NE

gdje je N prirodni broj kako je definirano u primjeru 3.3, D predstavlja sve dvoznamenkaste brojeve djeljive sa četiri:

D → PX| QY

P → 1| 3| 5| 7| 9

X → 2| 6

Q → 2| 4| 6| 8

Y → 0| 4| 8

a E je:

E → 0Y| D

na primjer, rečenica 1004 može se izvesti u nizu izvoðenja:

S => NE => BCE => 10E => 100Y => 1004

Primjer 3.5

A sada pokušajmo izvesti gramatiku jezika {3, 6, 9,12,15,18, . . .}, tj. jezika koji sadrži prirodne brojeve djeljive s 3. Znamo da je broj djeljiv s 3 ako je zbroj njegovih znamenki djeljiv s 3. Ali, kako u produkcijama beskontekstne gramatike zadovoljiti taj uvjet? Je li to moguće, kad znamo da u gramatici nisu definirane nikakve operacije?!

Dakako, iz promatranja beskonačnog skupa jezika brojeva djeljivih s 3 ne bismo mogli doći do rješenja. No, pokušajmo razmišljati ovako: ako je broj djeljiv s 3, zbroj ostataka dijeljenja svih njegovih znamenki s 3 jednak je nula ili je neki broj koji je takoðer djeljiv s 3. To, na primjer, znači da ako broj započinje s 1, 4 ili 7 (ostatak dijeljenja s 3 jednak je 1), drugi dio broja mora sadržavati znamenku čiji je ostatak dijeljenja s tri jednak 2 (a to su 2, 5 ili 8) ili dvije znamenke čiji je ostatak dijeljenja jednak 1. Na primjer, brojevi 18, 111 ili 147 djeljivi su s 3. Dakle, na najvišoj razini, možemo definirati gramatiku:

S → AB| BA| C

gdje A predstavlja niz brojki od kojih je zbroj ostataka dijeljenja s 3 jednak 1, B niz brojki od kojih je zbroj ostataka dijeljenja s 3 jednak 2, a C niz brojeva koji počinju s 3, 6, ili 9. Dalje je:

A → 1| 4| 7

B → 2| 5| 8| BX| AA

A → 1| 4| 7| AX| BB

Na kraju, kompletna gramatika koja generira brojeve djeljive s 3 je:

S → AB| BA| C

A → 1| 4| 7| AX| BB

B → 2| 5| 8| BX| AA

C → Y| CX| CS

X → 0| Y| XS

Y → 3| 6| 9

Na primjer, rečenice 1200, 2322543 i 111 može se izvesti u nizu izvoðenja:

S => AB => 1B => 1BX => 1BXX => 12XX => 120X => 1200

S => BA => BXA => 2XA => 2YA => 23A => 23BB => 232B

  => 232AA => 232BBA => 2322BA => 23225A => 23225AX

  => 2322254X => 232254Y => 2322543

S => AB => 1B => 1AA => 11A => 111

3.2. TRANSFORMIRANJE GRAMATIKA

U primjeru 2.9 dana je kontekstna gramatika koja generira isti jezik kao gramatika iz primjera 2.10. Usporeðujući te dvije gramatike sigurno ćemo zaključiti da nisu nimalo slične, ali su ekvivalentne! Što to znači?

Definicija 3.1

Kaže se da su dvije gramatike, G1 i G2, ekvivalentne ako je ispunjen uvjet:

L(G1) = L(G2)

Iz ove definicije slijedi zaključak da općenito skupovi neterminalnih znakova, produkcija i početni znak gramatika G1 i G2 mogu biti različiti. Isti je samo skup terminalnih znakova (alfabet).Ekvivalentnost gramatika jedini je uvjet koji mora biti ispunjen pri transformiranju jedne gramatike u drugu.
Kao što je već rečeno, ne postoje algoritmi niti nešto slično što bi moglo pomoći u automatskom izvoðenju gramatike danog jezika. Najčešće će se do "prave" gramatike doći u nekoliko iteracija, podijelivši prije toga jezik na nekoliko disjunktnih skupova (podjezika) i potom čineći uniju dobivenih gramatika. Pri tome je korisno znati koje su transformacije dopuštene da bi se sačuvalo prvobitno značenje.
Transformacije imaju i šire značenje. Ponekad će se koristiti da bi se, na primjer, eliminirale rekurzije slijeva, izbacile prazne produkcije, ili, općenito, gramatika svela na neku formu ili tip. Kao što ćemo vidjeti u idućim poglavljima, posebno je važno gramatike svesti na odgovarajuće forme podesne za primjenu postupaka sintaksne analize. Ovdje su opisani mnogi postupci transformacija gramatika. Počinjemo s dva načina izravnog transformiranja gramatike, a to su supstitucija i faktorizacija.

Supstitucija

Neka je dana gramatika G1 = (N1, T1, P1, S), gdje je P

S → 0A1

OA → 00A1

A → ε

Pokažimo na primjeru ove gramatike kako se supstitucijom može izvesti ekvivalentna gramatika. Prije toga treba uočiti da G1 generira jezik

L(G1) = {01, 0011,000111,... } = {0nln: n≥1}

Najprije možemo uvesti novi neterminal, na primjer B, i produkciju

B → 0A

pa se G1 transformira u G2 kojoj je skup produkcija:

S → BI

B → OBI

B → 0A

A → ε

Dakle, svako pojavljivanje niza 0A zamijenjeno je s B i dodana je produkcija OA. Primijetiti da je gramatika G2 beskontekstna, dok je G1 gramatika tipa 0.
Dalje se, s obzirom da je A → ε jedina alternativa za A, G2 može transformirati u gramatiku G3 s produkcijama:

S → B1

B → OB1 | 0

To nije sve. Promatrajući jezik koji gramatike G1, G2 i G3 generiraju, može se izvesti gramatika G4 (primjer 3.1, samo umjesto terminala a i b imamo 0 i 1) s produkcijama:

S → 01 | OSI

Faktorizacija

Pokažimo postupak faktorizacije na primjeru gramatike G4. Obje alternative za S i počinju i završavaju istim znakom, s 0, odnosno s 1. Zbog toga se faktorizacija može sprovesti slijeva ili zdesna. Na primjer, zdesna bi bilo:

S → (0 | OS) 1

Ako se dio u zagradi (zagrade ovdje imaju ulogu metasimbola) zamijeni novim neterminalom, na primjer X, dobilo bi se

S → X1

X → 0 | OS

Dalje se produkcija za X može faktorizirati slijeva:

X → 0 (ε | S)

pa se uvoðenjem smjene, na primjer Y → ε|S, dobiva gramatika G5 ekvivalentna svim prethodnim gramatikama:

S → X1

X → 0Y

Y → ε | S

Izbacivanje neupotrebljivih simbola

Ponekad beskontekstna gramatika može sadržavati neupotrebljive neterminale, terminale ili, općenito, produkcije. Na primjer, gramatika s produkcijama:

S → aba

A → c

generira jezik {aba}. U izvoðenju tog jezika neterminal A neće nikada bit upotrijebljen, niti znak c, pa se izbacivanjem produkcije za A dobiva ekvivalentna gramatika.

Definicija 3.2

Kaže se daje simbol XεNUT neupotrebljiv u beskontekstnoj gramatici G={N, T, P, S) ako ne postoji izvoðenje S*=>;wXy*=>wxy, gdje su w,x,y &epsilon T*.

Da bi se utvrdilo je li neterminal A neupotrebljiv u gramatici G treba prvo znati je li L(G) neprazan skup. Za to će nam trebati sljedeći algoritam:

Algoritam 3.1

Je li L(G) neprazan?

Ulaz

Beskontekstna gramatika G=( N,T,P,S).

Izlaz

"Da" ako je L(G)≠Ø, "ne" inače.

Postupak

Izgrade se skupovi No, Ni, ... rekurzivno, kao što slijedi:

  1. Neka je No≠Ø i i=l.
  2. Neka je Ni={A: A →α je u P, αε (Ni-1UT *}U Ni-1
  3. Ako je NiNi-1, tada i=i+l, ide se na korak (2). Inače, Ne=Ni
  4. Ako je SεNe, ispisati "da", inače ispisati "ne".

Budući da je NecN, postupak će se završiti poslije najviše n+1 koraka.

Osim provjere je li L(G) neprazan treba provjeriti sadrži li gramatika G i nedokučive simbole.

Definicija 3.3

Kaže se da je simbol XεNUT nedokučiv u beskontekstnoj gramatici G=( N,T,P,S) ako se X ne pojavljuje niti u jednoj rečeničnoj formi.

Algoritam 3.2

Izbacivanje nedokučivih simbola.

Ulaz

Beskontekstna gramatika G=( N,T,P,S).

Izlaz

Ekvivalentna gramatika G'=(N',T',P',S') tako da je L(G)=L(G') i za svaki XεN'UT' postoje αßε(N'UT' )* tako da je S*=>αXß u G' .

Postupak

  1. Vo{S}, i=l.
  2. Vi={X: (A→ αXß) ε P ^ AεVi-1}UVi-1.
  3. Ako je Vi≠Vi-1, i=i+l i ide se na korak (2). Inače:

N' = ViN

T' = ViT

P' će biti one produkcije iz P koje sadrže samo simbole iz Vi

G' = (N',T',P',S')

Sada se može dati algoritam za izbacivanje neupotrebljivih simbola.

Algoritam 3.3

Izbacivanje neupotrebljivih simbola.

Ulaz

Beskontekstna gramatika G=(N, T, P, S), tako da je L(G)≠Ø.

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S') tako da je L(G) = L'(G'), i ne postoji nijedan neupotrebljiv simbol u N'UT'.

Postupak

(1) Upotrijebiti algoritam 3.1 da bi se dobio skup Ne. Tada je gramatika G1=(N≠Ne,T,P1, S), gdje P1 sadrži samo one produkcije iz P koje uključuju simbole iz NeUT.

(2) Primijeniti algoritam 3.2 na G1 da bi se dobilo G' = (N',T',P',S')

Korak (1) algoritma 3.3 izbacuje sve neterminale iz G koji ne mogu izvesti niz terminala. Potom se u koraku (2) izbacuju svi nedokučivi simboli. Svaki simbol X u rezultirajućoj gramatici mora se pojaviti najmanje jedanput u izvoðenju S*=>wXy*=>wxy. Da smo najprije upotrijebili algoritam 3.2, potom algoritam 3.1, ne bismo uvijek dobili konačnu gramatiku bez neupotrebljivih simbola.

Primjer 3.6

Neka je G= ({S,A,B},{a,b}, P, S), gdje je skup produkcija P.

S → a|A      A → AB      B → b

Primijenimo algoritam 3.3 na tu gramatiku. U koraku (1) je Ne={a,b}, tako da je G1= ({S,B}, {a, b}, {S→a, B→b}, S). Dalje, primjenom algoritma 3.2, dobili bismo V2=V1={S, a}. Dakle, G' = ({S}, {a}, {S→}, S).

Da smo prvo upotrijebili algoritam 3.2 na gramatiku G zaključili bismo da su svi simboli dokučivi, pa bi gramatika ostala nepromijenjena. Primjenom potom algoritma 3.1, dobili bismo Ne={S,B} tako da bi rezultirajuća gramatika bila Gi, a ne G'.

Izbacivanje ε-produkcija

Često će biti potrebno transformirati izvornu gramatiku koja ima ε-produkcije u ekvivalentnu gramatiku bez njih. Dakako, ako je εeL(G), tada mora postojati produkcija S→ε.

Definicija 3.4

Kaže se da je gramatika G= (N, T, P, S) bez ε-produkcija ako

(1) P ne sadrži produkcije, ili

(2) Postoji samo jedna ε-produkcija S→ε i S se ne pojavljuje niti u jednoj alternativi (desnoj strani) ostalih produkcija iz P.

Algoritam 3.4

Izbacivanje ε-produkcija.

Ulaz

Beskontekstna gramatika G=(N, T, P, S)

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S').

Postupak

(1) Izgraditi Ne={A: AeN i A+=>ε} slično kao u algoritmu 3.1.

{2) Neka je P' skup produkcija izgraðen na sljedeći način:

    (a) Ako je A→αoB1α1B2...Bkαk u P, k≥0, i za l≥i≥k svaki Bi je u Ne, ali nijedan simbol iz αj nije u Ne, 0≥j≥k, dodati u P' sve produkcije oblika:

A→α1X1α1...Bkαk

          gdje je X1 ili B1 ili ε, bez dodavanja A→ε u P'(to će se dogoditi ako su svi αi=ε ).

    (b)Ako je SeNe, dodati u P' produkcije:

S'→&epsilon|S

          gdje je S' novi (početni) simbol i N'=NU{S'}. Inače je N'=N i S' =S.

(3) Nova ekvivalentna gramatika je G'=(N', T', P', S').

Primjer 3.7

Primijenimo algoritam 3.4. na gramatiku G s produkcijama:

S → aSbS | bSaS | ε

Konačno će se dobiti gramatika G' s produkcijama:

S'→S| ε          S →aSbS| bSaS| aSb| abS| ab| bSa| baS| ba

Izbacivanje jediničnih produkcija

Korisna transformacija gramatika jest izbacivanje produkcija oblika A→B ili tzv. jediničnih produkcija.

Algoritam 3.5

Izbacivanje jediničnih produkcija.

Ulaz

Beskontekstna gramatika G=(N, T, P, S) bez ε-produkcija.

Izlaz

Ekvivalentna beskontekstna gramatika G' bez jediničnih produkcija i bez ε-produkcija.

Postupak

(1)Izgraditi za svaki A iz N skup NA={B: A*=>B} na sljedeći način:

(a)No={A}, i=l.

(b)Ni={C: (B→C)e P ^ BeNi-1}UN1-i.

(c)Ako je Ni≠N1-i, i=i+l i ide se na korak (b). Inače, NA=Ni.

(2) Izgraditi P' tako da ako je B→α u P i nije jedinična produkcija, produkcijama P' dodati sve A→α za koje jeBeNA.

(3) Nova ekvivalentna gramatika je G'=(N', T', P', S').

Primjer 3.8

Primijenimo algoritam 3.5. na gramatiku G s produkcijama

E → E+T | T

T → T*F | F

F → (E) | a

U koraku (1) je Ne={E,T,F}, NT={T,F}, NF={F}. Poslije koraka (2), P' postaje:

E → E+T | T*F | (E) | a

T → T*F | (E) | a

F → (E) | a

Definicija 3.5

Beskontekstna gramatika G je svojstvena (engl. proper) ako nema produkcija A→ε i nema petlji, tj. ne postoji niz izvoðenja A+=>A.

Chomskyjeva normalna forma (CNF)

Dosad smo se bavili transformacijama gramatika kojima smo iz nekih razloga "popravljali" prvobitno definiranu gramatiku dobijajuvći ekvivalentne gramatike bez praznih ili jediničnih produkcija, ili izbacujući suvišne produkcije. Sada ćemo definirati posebnu formu gramatika poznatu kao "Chomskvjeva normalna forma" (CNF), koja je posebno važna za primjene nekih postupaka sintaksne analize danih u petom poglavlju ove knjige.

Definicija 3.6

Kaže se da je gramatika G=(N, T, P, S) u Chomskvjevoj normalnoj formi (CNF) ako je svaka produkcija u Poblika:

(1) A→BC, A,B,CeN, ili

(2) A→a, aeT, ili

           (3) Ako je ε u jeziku L=(G), tada je S→ε i S se ne pojavljuje niti u jednoj alternativi (desnoj strani) ostalih produkcija iz P.

Može se dokazati da svaka beskontekstna gramatika ima ekvivalentnu gramatiku u CNF. Za takvu je transformaciju dobrodošao sljedeći algoritam:

Algoritam 3.6

Konverzija u CNF.

Ulaz

Svojstvena beskontekstna gramatika G=(N, T, P, S).

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S') u CNF.

Postupak

Skup produkcija P' izgraditi na sljedeći način:

(1)Dodati sve produkcije iz P oblika A→a u P'.

(2)Dodati sve produkcije iz P oblika A→BC u P'.

(3)Ako je S→ε u P dodati S→ε skupu produkcija P' <P'.

(4)Za sve produkcije oblika A→Xi. . .xk iz P, k≥2, iz P dodati u P' sljedeći skup produkcija. Neka X'i stoji za Xi, XieNUT, i X'i je novi neterminal ako je XiT. Preureðene produkcije su:

           A   → X'i<X2...Xk>

    <X2... Xk>  → X'2<X3... Xk

   <Xk-2... Xk> → X'k-2<Xk-1Xk>;

   <Xk-1... Xk> → X'k-1X'k

gdje je svaki <Xi...Xk> novi neterminal.

(5)Za sve produkcije oblika A→X1X2 iz P, gdje je X1eT v X2eT dodati u P' produkciju A→X'1X'2.

(6)Za svaki neterminal oblika a', uvedenog u koracima (4) i (5), dodati u produkciju a'→a. Konačno, skup neterminala N' je skup N kojem su dodani svi novouvedeni neterminali, pa je gramatika u CNF.

Primjer 3.9

Primijenimo algoritam 3.6 na gramatiku G s produkcijama

S → aAB | BA

A → BBB | a

B → AS | b

Najprije se, prema koracima (1) i (2) u P' mogu prenijeti produkcije:

S → BA

A → a

B → AS | b

Zatim zamjenjujemo S→aAB s S→a'<AB> i <AB> s <AB>→AB. Potom je zamijenjeno A→BBB s A→B<BB> i <BB> s <BB>→BB. Konačno, u P' se dodaje produkcija a'→a, pa je rezultirajuća gramatika sa skupom produkcija P':

   S → a'<AB> | BA

   A → B<BB> | a

   B → AS | b

<AB> → AB

<BB> → BB

  a' → a

Ako uvedemo supstituciju X za a', Y za <AB> i Z za <BB>, s ciljem da neterminale prikažemo samo jednim slovom, dobili bismo pregledniju gramatiku:

S → XY | BA

A → BZ | a

B → AS | b

Y → AB

Z → BB

X → a

Eliminiranje rekurzija slijeva

Transformacija gramatike koja je rekurzivna slijeva u ekvivalentnu gramatiku koja to nije, česta je u teoriji formalnih jezika, posebno u teoriji sintaksne analize.

Teorem 3.1

Svaki beskontekstni jezik ima gramatiku nerekurzivnu slijeva.

Dokaz teorema 3.1 nije važan za naše bavljenje teorijom formalnih jezika. Važno je samo upamtiti tu činjenicu. Takoðer je korisno znati i sljedeći teorem.

Teorem 3.2

Ako je G gramatika G=(N, T, P, S) u kojoj su:

A → Aα1|...|Aαm1|...|ßn

sve A-produkcije u P i nijedan ßi ne počinje s A, tada je G'gramatika ekvivalentna gramatici G, G'= (NU{A'}, T, P', S), gdje je A' novi neterminal, a P' je dobiveno iz P u kojem su produkcije zamijenjene sa:

A → ß1|...|ßn1A'|...|ßnA'

A' → α1|...|αm1A'|...α|mA'

Primjer 3.9

Primijenimo transformaciju iz teorema 3.2. na gramatiku G s produkcijama:

E → E + T | T

T → T*F | F

F → (E) | a

Dobit ćemo gramatiku G' s produkcijama:

E →  T   | TE'

E'→ +T   |+TE'

T → F    | FT'

T'→ *F   |*FT'

F → (E)  |a

odnosno, ako E' zamijenimo s X, a T' s Y, imamo:

E →  T   | TX

X → +T   |+TX

T →  F   | FY

Y → *F   |*FY

F → (E)  |a

Algoritam 3.7

Eliminiranje rekurzija slijeva.

Ulaz

Svojstvena beskontekstna gramatika G=(N, T, P, S).

.

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S') nerekurzivna slijeva.

Postupak

Teorem 3.2 je temeljni za eliminiranje rekurzija slijeva. Skup produkcija P' izgraditi na sljedeći način:

(l)Neka je N={A1, . . ., An}. Treba transformirati G tako da ako je Ai→α produkcija, tada α počinje ili terminalom ili neterminalom Aj tako da je j>i. Postaviti i=l.

(2)Neka je Ai-produkcija oblika Ai→Aiαi|...|Aiαm|ßi|...|ßp gdje nijedan ßj ne počinje s Ak ako je k≤i. (Uvijek će to biti moguće.) Zamijeniti Ai-produkcije sa:

A1 → ß1|...|ßp1A'i|...|ßpA'i

A'1 → α1|...|αm1A'i|...|αmA'i

gdje je A'i novi neterminal. Sada sve Ai-produkcije počinju terminalom ili s Ak, k>i.

(3)Ako je i=n, G' će biti rezultirajuća gramatika i prekida se daljnje izvoðenje postupka. Inače, i=i+l i j=l.

(4)Zamijeniti sve produkcije oblika Ai→Ajα, gdje je Aj→ß1|...|ßm, produkcijama Ai→ß1α|...|ßmα. Ako je Aj-produkcija počinjala terminalom ili s Ak, k>j, isto svojstvo će sada imati Ai-produkcija.

(5) Ako je j=i-l, ide se na korak (2). Inače, j=j + l i ide se na korak (4).

Primjer 3.10

Primijenimo algoritam 3.7 na gramatiku G s produkcijama:

A → BC | a

B → CA | Ab

C → AB | CC | a

Odmah uočavamo da je C-produkcija rekurzivna slijeva, dok A i B imaju skrivene rekurzije, takoðer slijeva. Neka je A1=A, A2=B i A3=C. Prikazana je promjena gramatika poslije svake primjene koraka (2) ili (4), ali samo nove produkcije neterminala čije su produkcije promijenjene:

(2), i=l:             nema promjene

(4), i=2, j=l: B → CA|BCb|ab

(2), i=2:             B → CA|ab|CAB'|abB'

                      B'→ CbB*|Cb

(4), i=3, j=l: C → BCB|aB|CC|a

(4), i=3, j=2: C → CACB|abCB|CAB'CB|abB'CB|aB|CC|a

(2), i=3:          C → abCB|abB'CB|aB|a|abCBC'|abB'CBC' |aBC'|aC

                  C' → ACBC'|AB'CBC'|CC'|ACB|AB'CB|C

Konačno, uvodeći smjenu X za B' i Y za C', rezultirajuća gramatika bez rekurzija slijeva ima produkcije:

A → BC | a

B → CA | ab | CAX | abX

X → CbX | Cb

C → abCB | abXCB | aB | a | abCBY | abXCBY | aBY | aY

Y → ACBY | AXCBY | CY | ACB | AXCB | C

Greibachova normalna forma (GNF)

Završavamo ovo poglavlje s još jednom formom beskontekstnih gramatika, tzv. "Greibachovom normalnom formom2"(GNF). Karakteristika je te forme da svaka produkcija mora početi terminalom (iz čega slijedi da ne može biti rekurzivna slijeva). Kao što ćemo vidjeti, prvi preduvjet transformacije gramatike u tu formu jest da gramatika ne smije biti rekurzivna slijeva, pa već imamo primjenu algoritma 3.7. Najprije definicija Greibachove normalne forme:

Definicija 3.7

Kaže se da je gramatika G=(N, T, P, S) u Greibachovoj normalnoj formi (GNF) ako je G bez ε-produkcija i ako je svaka produkcija iz P oblika:

A → aα    aeT,     αeN*

Ako gramatika nije rekurzivna slijeva, moguve je naći linearno ureðenje označeno s < na skupu neterminala N tako da ako je A→Bα produkcija u P, vrijedi A<B.

Algoritam 3.8

Konverzija gramatike u Greibachovu normalnu formu (GNF).

Ulaz

Svojstvena beskontekstna gramatika G=(N, T, P, S) koja nije rekurzivna slijeva.

Izlaz

Ekvivalentna gramatika G'=(N', T, P', S) u Greibachovoj normalnoj formi.

Postupak

(1) Linearno urediti skup neterminala, N={A1,..., An} tako da vrijedi:

A1<A2<...<An

(2) i = n - 1

(3) Ako je i=0 ide se na korak (5). Inače, zamijeniti svaku produkciju oblika Ai→Ajα, j>i, s Ai→ß1α|...|ßmα, gdje je Aj→ß1|...|ßm, tj. ßk su sve alternative od Aj koje počinju terminalom.

(4) i = i - 1 i vraća se na korak (3).

(5) Sada sve produkcije (osim S→ε, ako postoji) počinju terminalom. U svakoj produkciji, A→aX1...Xk, treba zamijeniti Xj, ako je terminal, s X'j, gdje je X'j novi neterminal.

(6) Za sve X'j uvedene u koraku (5) dodati produkciju X'j→Xj.

Primjer 3. 11

Transformirajmo rezultirajuću gramatiku iz primjera 3.9 u GNF:

E →  T   | TX

X → +T   |+TX

T →  F   | FY

Y → *F   |*FY

F → (E)  |a

Prvo uvedimo linearno ureðenje na skupu neterminala: X<E<Y<T<F. Neterminal F je najveći u tom ureðenju i sve njegove alternative počinju terminalom. T je sljedeći simbol s produkcijama T→F|FY, tako da se F supstituira sa svojim alternativama, pa se dobije:

T → (E)|a|(E)Y|aY

Sada je Y na redu, ali sve njegove alternative počinju terminalom pa nema promjena. Slijedi zamjena E-produkcija sa:

E → (E)| a| (E)Y| aY| (E)X| aX| (E)YX| aYX

X-produkcije započinju terminalom pa nije potrebna transformacija. Koraci (5) i (6) uvode novi neterminal ) ' i produkciju:

) ' → )

Na svim mjestima pojavljivanja terminala ) treba stajati )', no mi ćemo, opet radi preglednosti, umjesto ) pisati Z, pa je rezultirajuća gramatika u Greibachovoj normalnoj formi:

E → (EZ| a | (EZY | aY | (EZX | aX | (EZYX | aYX

X → +T| +TX

T → (EZ | a | (EZY | aY

Y → *F | *FY

F → (E) | a

Z → )

Neželjena posljedica transformacije gramatike u GNF, što je vidljivo i iz prethodnog primjera, jest veliki broj produkcija, pa je takva gramatika nepreglednija od svojeg originala.

Pitanja i zadaci

1) Transformirajte sintaksne dijagrame iz primjera 2.12 u jednostavniji oblik.

2) Pokažite da se gramatika G s produkcijama

S → B1         B → OB1 | 0

može transformirati u ekvivalentnu gramatiku s produkcijama

S → 01 | OS1

3) Naðite gramatiku bez ε-produkcija ekvivalentnu gramatici:

S → ABC              A → BB | ε

B → CC | a           C → AA | b

4) Naðite svojstvenu gramatiku ekvivalentnu gramatici:

S → A | B         A → C | D             B → D|E

C → S |a |ε       D → S | b             E → S | c | ε

5) Transformirajte sljedeće gramatike u Chomskyjevu normalnu formu:

a) S → OS1 | 01

b) S → aB | bA

  A → aS | bAA | a

  B → bS | aBB | b

6) Transformirajte iduću gramatiku u Greibachovu normalnu formu:

S → Ba | Ab         A → Sa | AAb | a               B → Sb | BBa | b

Sadržaj