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

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

,

то

.

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

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

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

Метод:

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

.

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

;

2. Полагаем ;

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

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

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

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

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

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

.

Пример :

.

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

1.  , , .

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

2. Положим

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

;

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

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

;

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

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

;

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

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

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

.

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

;

;

.

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

1.3.2.3. Другой способ преобразования кс-грамматики к нормальной форме Грейбах (Метод Розенкранца)

Рассмотрим другой способ построения грамматики, в которой каждое правило имеет вид , где , , . Здесь грамматика переписывается только один раз. Пусть - КС-грамматика, в которой нет пустых правил (даже вида ) и цепных правил.

Определение: Пусть и - два непересекающихся алфавита. Системой определяющих уравнений в алфавитах , называется система уравнений вида

, (1)

где

, , .

Если , то уравнение записывается .

Определение: Решением системы (1) называется отображение вида , и это отображение называется наименьшей неподвижной точкой системы определяющих уравнений.

Определение: Матричная форма записи системы уравнений выглядит следующим образом

, (2)

где

-вектор строка;

- матрица порядка (квадратная матрица);

-вектор строка.

Причем , (3)

где

.

Если во множестве правил для -го нетерминала существуют правила вида

,

где

, ,

то выполняется условие (3), иначе , если таких правил нет, то .

Рассматриваем множество правил для -го нетерминала, которые начинаются с -го нетерминала.

Если существуют правила вида

,

тогда

.

Если множество правил для данного нетерминала пусто, то .

.

Построим для системы (1) эквивалентную систему определяющих уравнений.

Лемма: Пусть система (1) – система определяющих уравнений, тогда наименьшей неподвижной точкой данной системы будет выражение вида

, (4)

где

;

- единичная матрица, на главной диагонали которой находятся , все остальные элементы данной матрицы – пустые выражения.

Если положить

,

то наименьшую неподвижную точку матричного уравнения

можно записать в виде

.

К сожалению, для данной системы нельзя найти соответствующую грамматику: она не является системой определяющих уравнений, так как элементы матрицы могут буть бесконечными суммами членов исходных уравнений. Однако можно заменить новой матрицей «неизвестных» , каждый элемент которой, расположенный в -й строке и -м столбце, - новый символ.

Тогда, заметив, что

,

можно получить систему определяющих уравнений

с неизвестными . Отметим, что если матрицы и - матрицы порядка , то система состоит из уравнений.

Лемма: Пусть система – система определяющих уравнений в алфавитах и и пусть матрица - матрица того же порядка что и . Причем, все её элементы –различные новые символы, тогда система определяющих уравнений вида

имеет наименьшую неподвижную точку, которая совпадает с наименьшей неподвижной точкой системы .