Eliminacija nekorisnih simbola se odvija u dva koraka:Izvor kompletnog članka: „Prevodioci i interpretatori - uvod u teoriju i metode kompilacije programskih jezika“ - Duško Vitas.
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:
je koristan ako u gramatici postoji bar jedno pravilo oblika 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:
je dostupan simbol. 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.
Primer
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’’}-:
Види још Leva rekurzija Eliminacija e-pravila Eliminacija jednostrukih pravila
Beleške
Категорија:Преводиоци (рачунарство) Категорија:Формални језици