9.3 Левая факторизация правил

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

Вход: КС-грамматика G=(N, T, P, S) без -правил.

Выход: Эквивалентная КС-грамматика G’=(N, T, P’, S) без одинаковых префиксов в правых частях, определяющих нетерминал.

1. Записать все правила для нетерминала X, имеющие одинаковые префиксы   , в виде одного правила с альтернативами (вариантами):

X ₁|₂|…|_n| , ₁, ₂, …,_n  

2. Вынести за скобки влево префикс  каждой строки-альтернативы:

X (₁| ₂|…| _n|) , ₁, ₂, …,_n  

3. Обозначить новым нетерминалом Y выражение, оставшееся в скобках:

X Y, Y ₁| ₂|…| _n

4. Пополнить множество нетерминалов новым нетерминалом Y и заменить правила, подвергшиеся факторизации, новыми правилами для X и Y.

5. Повторить п.1-4 для всех нетерминалов грамматики, для которых это возможно и нобходимо.

Пример. Ниже показана левая факторизация правил

1) SaSb 2) SaSc 3) Sd грамматики G=({S}, {a, b, c}, P, S)

Шаг алгоритма	Действия и результаты
1	SaSb |aSc
2	SaS(b |c)
3	SaSW W b |c
4	G’=({S, W}, {a, b, c}, P’, S) P’={ SaSW Sd W b |c }
5	Других объектов факторизации нет

Пример. Выполнить левую факторизацию правил КС-грамматики

1) SabSa 2) SaaAb 3) Sb 4) AbaAb 5) Ab грамматики G=({S,A}, {a, b}, P, S)

Шаг алгоритма	Действия и результаты
1	SabSa| aaAb
2	Sa(bSa| aAb)
3	SaW Sb WbSa W aAb
4	AbaAb |b
5	Ab(aAb |)
6	AbZ Z aAb Z 
7	Грамматика после левой факторизации имеет вид: G’=({S, A, W, Z}, {a, b}, P’, S) P’={ SaW Sb WbSa W aAb, AbZ Z aAb Z }, S)
8	Других объектов факторизации нет

9.4 Преобразование к нормальной форме Хомского

Каждая КС-грамматика G=(N, T, P, S) эквивалентна грамматике в нормальной форме Хомского с правилами вида:

1. АВС, где А, В, С N;

2. Аa, где а Т;

3. S, если   L(G), причем S не встречается в правых частях правил.

Дерево разбора любой строки языка в такой грамматике будет бинарным. Преобразование к нормальной форме Хомского (НФХ) полезно, когда требуется простая структура КС-языка. Оно выполняется путем сокращения количества символов правой части правила за счет введения новых обозначений (нетерминалов). Предварительно нужно привести исходную КС-грамматику.

Примечание: КС-грамматика обладает свойствами приведенной грамматики, если она не имеет циклов, -правил и бесполезных символов. Отсутствие циклов означает, что в грамматике невозможны выводы вида А+А, где А  N.

Вход: КС-грамматика G=(N, T, P, S)

Выход: Эквивалентная КС-грамматика G’=(N’, T, P’, S) в НФХ

5. Включить в P’ каждое правило вида 2, т.е. (Аa )  Р;

6. Включить в P’ каждое правило вида 1, т.е. (АВС)  Р;

7. Включить в P’ каждое правило вида 3, т.е. (S)  Р (если оно есть в Р);

8. Для каждого правила (АX₁…X_k)  Р, где k>2, включить в P’ правила:

АX₁^’<X₂…X_k>

<X₂…X_k> X₂’<X₃…X_k>

. . .

<X_k-2 X_k-1X_k> X_k-2’< X_k-1X_k>

< X_k-1X_k> X_k-1’X’_k

г де <X_i…X_k> - новый нетерминал

X_i , если X_i N

X_i’= X’_i , если X_i T

9. Для каждого правила (АX₁X₂)  Р, где хотя бы один из символов X₁ и X₂ является терминалом, включить в P’ согласно обозначениям правило (АX’₁X’₂)

10. Для каждого нового нетерминала вида X’, введенного в п.4 или в п.5, согласно обозначениям, включить в P’ правило X’X, где XT

11. Пополнить множество нетерминалов V’_N = V’ {новые нетерминалы}

При реализации алгоритма полезно иметь таблицу для обозначения терминалов и таблицу для обозначения строк из двух и более символов.

Пример. Преобразование в НФХ грамматики с правилами

SaAВ | BA

АВBB|a

BAS|b

Шаг алгоритма	Действия и результаты
1	P’={ Аa, B|b}
2	P’={ Аa, B|b}  { S BA , BAS }
3	Правила S нет
4	1) SaAВ Терминал а обозначаем N1 Строка АВ обозначаем N2 Новые правила: S N1 N2 , N2 АВ 2) АВВВ Строка ВВ обозначаем N3 Новые правила: А ВN3 , N3 ВВ
5	Таких правил нет
6	Правило N1 а помещаем в P’: { S N1 N2 | ВА , А ВN3| a, BAS| b, N2 АВ, N3 ВВ}  { N1 а }
7	N’=N{обозначения терминалов и строк}={S, A, B, N1, N2 , N3}