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

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК

Алгоритм устранения недостижимых символов.

Недостижимые терминалы (группа “в” бесполезных символов) и недостижимые нетерминалы, порождающие терминальные строки (группа “б” бесполезных символов), исключаются из грамматики с помощью алгоритма устранения недостижимых символов.

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

Выход: Эквивалентная КС-грамматика G’=(N’, T’, P’, S) у которой L(G)=L(G’) и для всех Z Î S’ существуют выводы SÞ*aZb, где a,bÎ (S’)*.

Здесь, как и в предыдущей задаче, сначала решается обратная задача, т.е. определяется множество W достижимых символов Z:

W={Z | Z Î S, $ SÞ*aZb, где a,bÎ (S’)*}.

1. Положить W₀=S

2. Вычислить W₁= W₀ È {X | X Î S, (A®aXb) ÎP, A Î W₀, a,bÎ (S’)*}

3. Если W₁¹W₀, то положить W₀= W₁ и перейти к п.2; иначе положить W= W₁

4. Вычислить N’=NÇW, T’==TÇW, Б=S-W, P’=P-P_Б, где P_БÍP – это множество правил, содержащих недостижимые символы XÎ Б, т.е. P_Б = {(X ®a)ÎP для всех XÎ Б, где aÎS}

Пример: Преобразование КС-грамматики с правилами

1) Q ® ab 2)B ® b 3)C ® db

в эквивалентную грамматику, не содержащую бесполезных символов.

Шаг алгоритма	Действия и результаты
	W0=Q
	W1 = { Q, a,b }
	W1 = W0? Нет W0 = W1={ Q, a, b }
	W1 = { Q, a, b }
	W1 = W0? Да W={ Q, a, b }
	N’= { Q} T’={a, b} Б={B, C, d} P’= {Q ® ab}

Цепное правило – это правило вида А®В, где А,В Î N. Цепные правила могут быть причиной нежелательных свойств грамматики, таких, например, как циклы. Алгоритм устранения цепных правил осуществляет замещение правой части каждого цепного правила, используя для этого не цепные правила.

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

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

1. Для каждого нетерминала А вычислить N^A = {B | AÞ*B, где BÎ N }:

1.1. Положить N₀^A={A}

1.2. Вычислить N₁^A = N₀^A È{C | (B ® C) Î P, B Î N₀^A, C Î N }

1.3. Если N₁^A ¹ N₀^A, то положить N₀^A = N₁^A и перейти к п.1.2, иначе положить
N^A = N₁^A

2. Построить множество P’ так: если (В ®a) Î P не является цепным правилом (a Ï N), то включить в P’ правило А ®a для каждого А, такого, что В Î N^A, т.е.

P’={ А ®a для всех (В ®a) Î P, где a Ï N и В Î N^A }

Пример: Преобразовать грамматику G с правилами:

G: S® X

X ® Y

Y ® Y; | z

в эквивалентную грамматику без цепных правил:

Шаг алгоритма	Действия и результаты
1.1	N0^S = {S}
1.2	N1^S = {S, X}
1.3	N1^S = N0^S? Нет N0^S = N1^S={S, X}
1.2	N1^S = {S, X, Y}
1.3	N1^S = N0^S? Нет N0^S = N1^S={S, X,Y}
1.2	N1^S = {S, X, Y}
1.3	N1^S = N0^S? Да N^S={S, X,Y}
1.1	N0^X = {X}
1.2	N1^X = {X,Y}
1.3	N1^X = N0^X? Нет N0^X = N1^X={X, Y}
1.2	N1^X = {X,Y}
1.3	N1^X = N0^X? Да N^X={X,Y}
1.1	N0^Y = {Y}
1.2	N1^Y = {Y}
1.3	N1^Y = N0^Y? Да N^Y={Y}
	P’={S®Y;|z, X®Y; |z, Y®Y; |z}

Пример: Преобразовать грамматику G с правилами:

G: E® E+T

E®T

T®T*P

T®P

P®i

P®(E)

1. После выполнения шага 1 алгоритма получаем: N^E ={E, T, P}, N^T ={T, P}, N^P ={P}

2. Выберем первый нетерминал E из множества N^E. Формируя множество правил, левая часть которых - нетерминальный символ Е, а правые части нецепных правил исходной грамматики, в левой части которых находятся символы из множества N^E, получаем: { E® E+T, E®T*P, E®i, E®(E)}. Таким же образом рассматриваем остальные символы из N^E, затем символы из N^T и N^P .

3. Окончательно получаем P’={ E® E+T, E®T*P, E®i, E®(E), T®T*P, T®i, T®(E), P®i, P®(E)}

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