Елиминација ε-правила

Уколико граматика поседује ε-правила, може се догодити да током извођења дужина реченичних форми почне да опада, а пожељно је, због потреба анализе, избећи овакву ситуацију. У поступку елиминације ε-правила из контекстно слободне граматике подразумева се да је из језика евентуално одстрањена празна реч ε.[1]

Алгоритам елиминације

уреди

За задату граматику G, поступак се састоји из два корака:

  1. кострукције скупа   анулирајућих симбола, тј. скупа помоћних симбола који се могу преписати као празна реч.
  2. трансформације правила која садрже анулирајуће симболе


1. корак

За дату КС-граматику G без некорисних симбола, скуп анулирајућих симбола A(G), иницијално празан, се добија применом следећих рекурзивних правила:

  1.   је анулирајући ако је  . Сваки такав X се додаје у скуп A(G).
  2.   је анулирајући постоји бар једно правило   где су сви помоћни симболи у ниски α анулирајући. (  )


2. корак

Када је одређен скуп A(G), модификују се правила граматике G која садрже анулирајуће симболе тако што се у сваком правилу   у ниски α замене анулирајући симболи празном речи ε на све могуће начине, а затим се одстране ε-правила. КС-граматика која се добија као резултат ове трансформације је еквивалентна полазној граматици до на празну реч.

Пример

уреди

Нека је граматика Г над    , P :

 

Једини нетерминал S је и анулирајући. У ниски α = S(S) замењујемо симбол S са ε на све могуће начине што даје ново правило:

 

које описује исти језик али без празне речи. У складу са дефиницијом, граматика се може модификовати увођењем новог почетног симбола T уместо S и додавањем новог правила:

 

граматика са новим скупом правила описује исти језик као полазна.

Погледајте још

уреди


Белешке

уреди
  1. ^ Извор комплетног чланка: „Преводиоци и интерпретатори - увод у теорију и методе компилације програмских језика“ - Душко Витас.