Алгоритм преобразования нелеворекурсивной приведенной КС-грамматики к нормальной форме Грейбах

Преобразование нелеворекурсивной приведенной КС-грамматики к нормальной форме Грейбах

Лемма: Пусть грамматика - нелеворекурсивная приведенная грамматика, тогда существует такой линейный порядок на , что если имеется правило вида

,

то

.

Вход: Нелеворекурсивная грамматика .

Выход: Грамматика в нормальной форме Грейбах.

Метод:

1. Строим линейный порядок на множестве нетерминалов таким образом, что каждое правило для нетерминала начинается либо с терминала, либо с нетерминала, для которого выполняется условие

.

Упорядочим таким образом, что

;

2. Полагаем ;

3. Если , то переходим к шагу 5;

если , то заменить каждое правило вида , где , правилами , где- все правила для нетерминала . Далее мы убедимся, что если каждая из цепочек начинается терминалом, то и все правые части правил для нетерминала должны начинаться с терминала;

4. Положим и переходим к шагу 3;

5. В результате выполнения шагов 3,4 все правые части каждого правила (кроме возможно ) будут начинаться с терминалов. Для любого нетерминала , если в правых частях правил терминал находится не на первом месте, то заменяем его на новый нетерминал и в множество правил добавляется правило вида

и записываем результирующую грамматику .

Домашнее задание: Проверить результирующую грамматику, после удаления левой рекурсии.

.

Пример:

.

Решение: После выполнения алгоритма удаления левой рекурсии множество правил примет вид

1. , , .

Строим линейный порядок ;

2. Положим

3. Так как ,то вместо правил добавляем в множество правил правила вида

;

4. Положим и переходим к шагу 3;

3. Так как , то вместо правил добавляем в множество правил правила вида

;

4. Положим и переходим к шагу 3;

3. Так как , то вместо правил добавляем в множество правил правила вида

;

4. Положим и переходим к шагу 3;

3. Так как , то переходим к шагу 5;

5. Выполняем замену всех терминалов , которые находятся не на первом месте на новые нетерминалы и в множество правил добавляются правила вида

.

Записываем результирующую грамматику .

;

;

.

Недостаток: Недостаток описанной техники преобразования грамматики к нормальной форме Грейбах в том, что она дает много новых правил. Чтобы не вводить слишком много правил, можно применить другой метод, который излагается ниже. Однако он может давать больше нетерминалов.

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