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

УДАЛЕНИЕ ПРОИЗВОЛЬНОГО ПРАВИЛА

Рассмотрим еще одно полезное преобразование грамматик – удаление произвольного правила вывода. Такое преобразование часто используется при приведении грамматики к заданному классу.

Алгоритм. Удаление произвольного правила вывода из Кс-грамматики

Вход: КС-грамматика G=(N, T, P, S) и правило вывода вида А®aВb Î Р, где А, В Î N и цепочки a, b Î (ТÈN)*.

Выход: КС-грамматика G'=(N, T, P’, S): L(G)=L(G’) и А®aВb Ï Р'.

Описание алгоритма:

1. Пусть B®g₁, B®g₂, … B®g_k – все В-правила грамматики G. Построить P’ следующим образом:

P’=(P-{ А®aВb}) È {А®ag₁b |ag₂b, … | ag_kb }

2. Положить G'=(N, T, P’, S)

Пример. Удалить правило P®(E) из КС-грамматики с правилами:

E® E+T

E®T

T®T*P

T®P

P®i

P®(E)

1. Е-правила грамматики G будут выглядеть следующим образом:

E® E+T

E®T

2. Из множества правил грамматики G необходимо удалить заданное правило P®(E) и добавить P-правила: P® (E+T) P®(T). Новое множество правил грамматики P' имеет вид: { E® E+T E®T T®T*P T®P P®i P® (E+T) P®(T) }

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

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

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

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

X ®ab₁|ab₂|…|ab_n|, b₁, b₂, …,b_n Î S

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

X ®a(b₁| b₂|…| b_n|), b₁, b₂, …,b_n Î S

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

X ®aY, Y ®b₁| b₂|…| b_n

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

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

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

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

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

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

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

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

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