Eliminacija nekorisnih simbola se odvija u dva koraka:[1]

1. korak

U prvom koraku se eliminišu oni pomoćni simboli X iz kojih se ne može izvesti nijedna reč koja se sastoji od završnih simbola. Eliminacija se vrši na osnovu sledećih rekurzivnih definicija:

  1. je koristan ako u gramatici postoji bar jedno pravilo oblika
  2. je koristan ako postoji bar jedno pravilo takvo da je , a α se sastoji samo od korisnih simbola iz N i simbola iz Σ

Simboli koji nisu korisni se ukljanjaju iz skupa N i tako se dobija novi skup pomoćnih simbola N' i pravila P'. Ovako modifikovana gramatika ekvivalentna je polaznoj gramatici.

2. korak

U drugom koraku se eliminišu nedostupni simboli iz . Eliminacija se vrši na osnovu sledećih rekurzivnih pravila:

  1. je dostupan simbol.
  2. Simboli koji se pojavljuju na desnoj strani pravila dostupnih simbola su dostupni simboli.

Simboli koji se ne identifikuju u ovom koraku su nedostupni, pa se odstranjuju iz skupa N’, što daje novi skup pomoćnih simbola N’’. Dobijena gramatika je ekvivalentna polaznoj gramatici.

Neka je gramatika G nad  , gde je  , S početni simbol, a skup pravila P:

 

 

 

 

 

 

Prema prvom koraku, kao korisni simboli prvo se identifikuju A i C, a zatim još S i D. Tada,  , a skup pravila P’ postaje:

 

 

 

 

U drugom koraku biće eliminisan simbol D jer je nedostupan iz simbola S. Tada  , a skup pravila P’’:

 

 

 

Pogledajte još

уреди

Beleške

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