Алгоритм Устранение e-правил

Вход: КС-грамматика .

Выход: Эквивалентная КС-грамматика без e-правил для всех нетерминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики.

Шаг 1. В исходной грамматике найти e-порождающие нетерминальные символы , такие, что .

1.1 Положить .

1.2 Вычислить .

1.3 Если , то положить i:=i+1 и перейти к пункту 1.2, иначе считать .

Шаг 2. Из множества правил исходной грамматики перенести во множество все правила, за исключением e-правил, т.е. для всех

Шаг 3. Пополнить множество правилами, которые получаются из каждого правила этого множества путем исключения всевозможных комбинаций e-порождающих нетерминалов в правой части. Полученные при этом e-правила во множество не включать.

Шаг 4. Если , то , где ; иначе

ПримерДана грамматика с правилами . Преобразуем ее в эквивалентную грамматику по алгоритму 4.4.

Шаг 1. N₀ = {A, B};

N₁ = {S, A, B};

N₂ = {S, A, B}.

Т.к. N₁ = N₂, то искомое множество построено и N = {S, A, B}.

Шаг 2, 3. Множество 1) ; 2) ; 3)

Шаг 4. Т.к. , то введем новый нетерминал С и пополним множество правилом вида . Результирующая грамматика будет иметь вид: с правилами .