Алгоритм удаления цепных правил

Удаление цепных правил

Определение: Правило вида называется цепным.

Определение: Циклическим выводом называется вывод вида

;

; .

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

Выход: Грамматика без цепных правил.

Метод:

Шаги 1,2,3,4 повторяются для каждого нетерминала.

1. ;

2. ;

3. Если , то заканчиваем построение множества для текущего нетерминала ;

если , то и переходим к шагу 2;

4. ;

5. ;

;

;

Во множество - заносятся все правила из , кроме цепных.

6. Для всех правил вида , из множества , если нетерминал принадлежит одному из построенных множеств (например ), то во множество правил добавляются правила вида

.

Дата добавления: 2014-01-07