Алгоритм Устранение 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. Т.к. , то введем новый нетерминал С и пополним множество правилом вида . Результирующая грамматика будет иметь вид: с правилами .