Ukoliko gramatika poseduje ε-pravila, može se dogoditi da tokom izvođenja dužina rečeničnih formi počne da opada, a poželjno je, zbog potreba analize, izbeći ovakvu situaciju. U postupku eliminacije ε-pravila iz kontekstno slobodne gramatike podrazumeva se da je iz jezika eventualno odstranjena prazna reč ε.[1]

Algoritam eliminacije

уреди

Za zadatu gramatiku G, postupak se sastoji iz dva koraka:

  1. kostrukcije skupa   anulirajućih simbola, tj. skupa pomoćnih simbola koji se mogu prepisati kao prazna reč.
  2. transformacije pravila koja sadrže anulirajuće simbole


1. korak

Za datu KS-gramatiku G bez nekorisnih simbola, skup anulirajućih simbola A(G), inicijalno prazan, se dobija primenom sledećih rekurzivnih pravila:

  1.   je anulirajući ako je  . Svaki takav X se dodaje u skup A(G).
  2.   je anulirajući postoji bar jedno pravilo   gde su svi pomoćni simboli u niski α anulirajući. (  )


2. korak

Kada je određen skup A(G), modifikuju se pravila gramatike G koja sadrže anulirajuće simbole tako što se u svakom pravilu   u niski α zamene anulirajući simboli praznom reči ε na sve moguće načine, a zatim se odstrane ε-pravila. KS-gramatika koja se dobija kao rezultat ove transformacije je ekvivalentna polaznoj gramatici do na praznu reč.

Neka je gramatika G nad    , P :

 

Jedini neterminal S je i anulirajući. U niski α = S(S) zamenjujemo simbol S sa ε na sve moguće načine što daje novo pravilo:

 

koje opisuje isti jezik ali bez prazne reči. U skladu sa definicijom, gramatika se može modifikovati uvođenjem novog početnog simbola T umesto S i dodavanjem novog pravila:

 

gramatika sa novim skupom pravila opisuje isti jezik kao polazna.

Pogledajte još

уреди


Beleške

уреди
  1. ^ Izvor kompletnog članka: „Prevodioci i interpretatori - uvod u teoriju i metode kompilacije programskih jezika“ - Duško Vitas.