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 znakovaUredi

Ako se znak X gramatike   koristi u postupku generiranja  , gdje su   i  , 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  , gdje je  , 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  , tada je znak X nedohvatljiv.

Odbacivanje mrtvih znakovaUredi

Neka dana kontekstno neovisna gramatika   generira neprazni jezik, tj.  . Moguće je izgraditi istovjetnu gramatiku   koja nema mrtvih znakova, odnosno za bilo koji   vrijedi  .

Algoritam traženja živih znakova zasniva se na sljedećem svojstvu: Ako su živi svi znakovi   desne strane produkcije

 

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 =  ;
NovaListaŽivih =  ;
dok (StaraListaŽivih   NovaListaŽivih) { StaraListaŽivih = NovaListaŽivih; NovaListaŽivih = NovaListaŽivih  ; }
ListaŽivih = NovaListaŽivih;

Odbacivanje nedohvatljivih znakovaUredi

Moguće je izraditi gramatiku   koja je istovjetna kontekstno neovisnoj gramatici   i koja nema nedohvatljivih znakova, tj. za bilo koji   vrijedi  , gdje je  .

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

 

tada su dohvatljivi svi završni i nezavršni znakovi u nizovima  ,   ... i   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 =  ;
NovaListaDohvatljivih =  ;
dok (StaraListaDohvatljivih   NovaListaNedohvatljivih) { StaraListaDohvatljivih = NovaListaDohvatljivih; NovaListaDohvatljivih = StaraListaDohvatljivih  ; }
ListaDohvatljivih = NovaListaDohvatljivih;

Odbacivanje beskorisnih znakovaUredi

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 da tad neki znakovi mogu ostati dohvatljivi primjenom mrtvih znakova.

Odbacivanje produkcijaUredi

Produkcije oblika   su jedinične produkcije. Sve ostale produkcije, uključujući i produkcije oblika   i  , nazivaju se nejedinične produkcije.

Produkcije oblika   nazivaju se  -produkcije. Njihovo korištenje je moguće izbjeći ukoliko prazni niz nije element jezika kojeg gramatika generira.

Odbacivanje  -produkcijaUredi

Neka gramatika   generira kontekstno neovisni jezik  . Tada je moguće izgraditi istovjetnu gramatiku   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  . 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   se gradi na sljedeći način. Ako je:
     
    produkcija gramatike G, tada se u skup produkcija gramatike   dodaju produkcije oblika:
     
    Oznake   poprimaju sljedeće vrijednosti:
    a) Ako znak   nije prazni znak, onda je oznaka   jednaka  .
    b) Ako je znak   prazni znak, onda je oznaka   jednaka   ili  .
    Produkcije se grade na temelju svih mogućih kombinacija oznaka  . Ako sve oznake   poprime vrijednost  , tada nastaje  -produkcija i ona se ne dodaje u skup produkcija gramatike  . Time se odbace sve  -produkcije iz zadane gramatike G.

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

Odbacivanje jediničnih produkcijaUredi

Neka gramatika   generira kontekstno neovisni jezik  . Moguće je izgraditi istovjetnu gramatiku   koja nema jediničnih produkcija oblika  .

Istovjetna gramatika   koja nema jediničnih produkcija gradi se na sljedeći način:

  1. U skup produkcija gramatike   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.  , gdje su A i B nezavršni znakovi gramatike G. Za sve produkcije   koje nisu jedinične grade se nove produkcije  .