Pojednostavljenje gramatike

Pojednostavljenje gramatike je skupni naziv za postupke odbacivanja beskorisnih znakova i produkcija, odnosno za postupke transformacije zapisa gramatike u neki oblik pogodniji za obradu. Za danu formalnu gramatiku gradimo istovjetnu gramatiku (tj. gramatiku koja generira isti jezik) bez zalihosnih znakova i produkcija.

Odbacivanje znakova

Ako se znak X gramatike $G=(V,T,P,S)$ koristi u postupku generiranja $S\Rightarrow \alpha X\beta \Rightarrow w$, gdje su $\alpha ,\beta \in (V\cup T)*$ i $w\in T*$, onda je znak x koristan. U suprotnom, znak je beskoristan.

Dva su vida beskorisnosti: znak može biti mrtav ili nedohvatljiv, Ako iz znaka X nije moguće generirati niz završnih znakova, tj. ne postoji postupak generiranja $X\Rightarrow w_X$, gdje je $w_X\in T*$, tada je znak X mrtav. Nije li znak mrtav, kaže se da je živ. Ako se znak X ne nalazi ni u jednom nizu koji se generira iz početnog nezavršnog znaka, tj. ne postoji postupak generiranja $S\Rightarrow \alpha X\beta$, tada je znak X nedohvatljiv.

Odbacivanje mrtvih znakova

Neka dana kontekstno neovisna gramatika $G=(V,T,P,S)$ generira neprazni jezik, tj. $L(G)\ne \mathrm{\varnothing }$. Moguće je izgraditi istovjetnu gramatiku $G^{\prime }=(V^{\prime },T^{\prime },P^{\prime },S)$ koja nema mrtvih znakova, odnosno za bilo koji $A\in V^{\prime }$ vrijedi $A\Rightarrow w,w\in T*$.

Algoritam traženja živih znakova zasniva se na sljedećem svojstvu: Ako su živi svi znakovi $X_1,X_2,...,X_n$ desne strane produkcije

$A\to X_1{X}_2...X_n$

onda je živ i nezavršni znak A lijeve strane produkcije.

Algoritam traženja živih znakova izvodi se u tri koraka:

1. U listu živih znakova stave se lijeve strane produkcija koje na desnoj strani nemaju nezavršnih znakova.
2. Ako su na desnoj strani produkcije isključivo živi znakovi, onda se nezavršni znak lijeve strane produkcije doda u listu živih znakova.
3. Ako nije moguće proširiti listu živih znakova, algoritam se zaustavlja. Svi znakovi koji nisu u listi živih znakova su mrtvi znakovi.

Pseudokod opisanog algoritma jest sljedeći:

StaraListaŽivih = $\mathrm{\varnothing }$;
NovaListaŽivih = $\{A|A\to w,\mathrm{i}w\in T*\}$;

dok (StaraListaŽivih $\ne$ NovaListaŽivih)
{
  StaraListaŽivih = NovaListaŽivih;
  NovaListaŽivih = NovaListaŽivih $\cup \left\{A|A\to \alpha ,\alpha \in (T\cup StaraListaZivih)*\right\}$;
}

ListaŽivih = NovaListaŽivih;

Odbacivanje nedohvatljivih znakova

Moguće je izraditi gramatiku $G^{\prime }=(V^{\prime },T^{\prime },P^{\prime },S)$ koja je istovjetna kontekstno neovisnoj gramatici $G=(V,T,P,S)$ i koja nema nedohvatljivih znakova, tj. za bilo koji $X\in V^{\prime }\cup T^{\prime }$ vrijedi $S\Rightarrow \alpha X\beta$, gdje je $\alpha ,\beta \in (V^{\prime }\cup T^{\prime })*$.

Algoritam traženja dohvatljivih znakova zasniva se na sljedećem svojstvu:
Ako je dohvatljiv nezavršni znak A lijeve strane produkcije:

$A\to {\alpha }_1|{\alpha }_2|...|{\alpha }_n$

tada su dohvatljivi svi završni i nezavršni znakovi u nizovima ${\alpha }_1$, ${\alpha }_2$ ... i ${\alpha }_n$ desne strane produkcije.

Algoritam traženja dohvatljivih znakova izvodi se u tri koraka:

1. U listu dohvatljivih znakova stavi se početni nezavršni znak gramatike.
2. Ako je znak lijeve strane produkcije u listi dohvatljivih znakova, onda se svi znakovi desne strane produkcije dodaju u listu dohvatljivih znakova.
3. Ako listu dohvatljivih znakova nije moguće proširiti, algoritam se zaustavlja. Svi znakovi koji nisu u listi dohvatljivih znakova su nedohvatljivi.

Pseudokod opisanog algoritma jest sljedeći:

StaraListaDohvatljivih = $\mathrm{\varnothing }$;
NovaListaDohvatljivih = $\left\{S|S\mathrm{j}\mathrm{e}\mathrm{p}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{t}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{z}\mathrm{a}\mathrm{v}\mathrm{r}\mathrm{s}\mathrm{n}\mathrm{i}\mathrm{z}\mathrm{n}\mathrm{a}\mathrm{k}\right\}$;

dok (StaraListaDohvatljivih $\ne$ NovaListaNedohvatljivih)
{
  StaraListaDohvatljivih = NovaListaDohvatljivih;
  NovaListaDohvatljivih = StaraListaDohvatljivih $\cup \left\{X|X\mathrm{j}\mathrm{e}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{z}\mathrm{u}{\alpha }_i,A\to {\alpha }_i\wedge A\in StaraListaDohvatljivih\right\}$;
}

ListaDohvatljivih = NovaListaDohvatljivih;

Odbacivanje beskorisnih znakova

Primjenom algoritma odbacivanja mrtvih znakova, a potom algoritma odbacivanja nedohvatljivih znakova, iz gramatike se odbacuju svi beskorisni znakovi. Primjena algoritma obrnutim redoslijedom neće nužno odbaciti sve beskorisne znakove, s obzirom na to da tad neki znakovi mogu ostati dohvatljivi primjenom mrtvih znakova.

Odbacivanje produkcija

Produkcije oblika $A\to B$ su jedinične produkcije. Sve ostale produkcije, uključujući i produkcije oblika $A\to a$ i $A\to ϵ$, nazivaju se nejedinične produkcije.

Produkcije oblika $A\to ϵ$ nazivaju se $ϵ$-produkcije. Njihovo korištenje je moguće izbjeći ako prazni niz nije element jezika kojeg gramatika generira.

Odbacivanje $ϵ$-produkcija

Neka gramatika $G=(V,T,P,S)$ generira kontekstno neovisni jezik $L(G)-\left\{\epsilon \right\}$. Tada je moguće izgraditi istovjetnu gramatiku $G^{\prime }=(V^{\prime },T^{\prime },P^{\prime },S)$ koja nema $ϵ$-produkcija.

Algoritam odbacivanja $ϵ$-produkcija se izvodi u dva osnovna koraka:

1. Pronađu se svi nezavršni znakovi koji generiraju prazni niz. Prazni znakovi su oni znakovi za koje vrijedi $A\Rightarrow ϵ$. Prazni se znakovi traže sljedećim iterativnim algoritmom:
   1. U listu prazni znakova se stave lijeve strane svih $ϵ$-produkcija.
   2. Ako su svi znakovi desne strane neke od produkcija zapisani u listu praznih znakova, tada se lista praznih znakova nadopuni lijevom stranom te produkcije.
   3. Ako više nije moguće proširiti listu praznih znakova, algoritam se zaustavlja.
      
      
2. Skup produkcija gramatike $G^{\prime }$ se gradi na sljedeći način. Ako je:
   $A\to X_1{X}_2...X_n$
   produkcija gramatike G, tada se u skup produkcija gramatike $G^{\prime }$ dodaju produkcije oblika:
   $A\to {\xi }_1{\xi }_2...{\xi }_n$
   Oznake ${\xi }_i$ poprimaju sljedeće vrijednosti:
   a) Ako znak $X_i$ nije prazni znak, onda je oznaka ${\xi }_i$ jednaka $X_i$.
   b) Ako je znak $X_i$ prazni znak, onda je oznaka ${\xi }_i$ jednaka $ϵ$ ili $X_i$.
   Produkcije se grade na temelju svih mogućih kombinacija oznaka ${\xi }_1{\xi }_2...{\xi }_n$. Ako sve oznake ${\xi }_i$ poprime vrijednost $ϵ$, tada nastaje $ϵ$-produkcija i ona se ne dodaje u skup produkcija gramatike $G^{\prime }$. Time se odbace sve $ϵ$-produkcije iz zadane gramatike G.

Općenito će ovim algoritmom, ako produkcija na desnoj strani ima k praznih znakova, biti potrebno izgraditi najviše $2^k$ novih produkcija. Ako je na desnoj strani barem jedan znak koji nije prazan, tada je potrebno dodati točno $2^k$ novih produkcija. Ako su na desnoj strani svi znakovi prazni, tada je potrebno dodati $2^k-1$ novih produkcija (produkcija $A\to ϵϵ...ϵ$ se ne dodaje u skup produkcija).

Odbacivanje jediničnih produkcija

Neka gramatika $G=(V,T,P,S)$ generira kontekstno neovisni jezik $L(G)\mathrm{\setminus }\left\{\epsilon \right\}$. Moguće je izgraditi istovjetnu gramatiku $G^{\prime }=(V^{\prime },T^{\prime },P^{\prime },S)$ koja nema jediničnih produkcija oblika $A\to B$.

Istovjetna gramatika $G^{\prime }$ koja nema jediničnih produkcija gradi se na sljedeći način:

1. U skup produkcija gramatike $G^{\prime }$ stave se sve produkcije gramatike G koje nisu jedinične.
2. Neka se postupkom generiranja iz nezavršnog znaka A dobije nezavršni znak B, tj. $A\Rightarrow B$, gdje su A i B nezavršni znakovi gramatike G. Za sve produkcije $B\to \alpha$ koje nisu jedinične grade se nove produkcije $A\to \alpha$.