spoPresentation2

Удаление бесполезных символов

2.5. (Y4 T)* = {S,A,B,C,D,F,a,b,c};

Y5 = {S,A,B,C,D,F}; Y4=Y5;

4. N’=Y5={S,A,B,C,D,F}; T’=T={a,b,c}; S’=S={S}

5. P’={ SoaAB; AoaA | bB; BoACb | b; CoA | bA | cC; Doa | c | Fb; FoBC | AС;}

211

Удаление недостижимых символов

Дано: КС грамматика G(T,N,P,S)

Получить: эквивалентную ей КС грамматику G’(T’,N’,P’,S’), не содержащую недостижимых символов, задающую тот же язык L(G) = L(G’)

Дополнительные условия: нет

1. Y0={S}; i=1. Алгоритм работает с множеством достижимых символов Yi , которое итерационно пополняется

212

Удаление недостижимых символов

2. Yi = Yi-1 { x | (AoDxE) P, A Yi-1; D,EV* ; x V } включаются символы из правых

частей правил, в левых частях которых только символы, включенные на предыдущем шаге;

3. Если YizYi-1, то i++ и перейти к шагу 2

4. N’ = N Yi; T’ = T Yi; S’=S;

5. P’ = { pi | AoD, A Yi, DYi* } остаются

только правила, которые содержат используемые символы

213

Удаление недостижимых символов

Пример.

S = ( {S,A,B,C,D,F}; {a,b,c}; P; S); P = {

SoaAB; AoaA | bB; BoACb | b; CoA | bA | cC; Doa | c | Fb; FoBC | AС }

1. Y0={S}; i=1;

2.1. Y0={S}: Y1 = {S} { a,A,B } = { a,A,B,S }

2.2. Y2 = {a,A,B,S} { a,A,B,b,C } = { a,b,A,B,C,S }

2.3. Y3 = {a,b,A,B,C,S}

{a,A,B,b,C,c}={a,b,c,A,B,C,S}

214

Удаление недостижимых символов

2.4. Y4 = {a,b,c,A,B,C,S} {a,A,B,b,C,c} =

{a,b,c,A,B,C,S} = Y3

4. N’ = N Yi = { A,B,C,S }; T’ = T Yi = {a,b,c};

S’=S

5. P’ = { pi | AoD, A,D Yi }

P’ = { SoaAB; AoaA | bB; BoACb | b; CoA | bA | cC }

215

Удаление O-правил

Дано: КС грамматика G(T,N,P,S)

Получить: эквивалентную ей КС грамматику G’(T’,N’,P’,S’), не содержащую O-правил,

задающую тот же язык L(G) = L(G’)

Дополнительные условия: нет

1. Y0 = { A | (AoO) P }; i=1

2. Yi = Yi-1 { A | (AoD) P, DYi-1* }

включаются нетерминалы левых частей правил, в правых частях которых только ранее включенные нетерминалы

216

Удаление O-правил

3. Если YizYi-1, то i++ и перейти к шагу 2

4. N’ = N; T’ = T; S’ = S; P’ = P \ {AoO}

5. P’ = P’ { p | A o W1E1W2E2…WnEn , причем AoX1E1X2E2…XnEn P , Xj Yi , где Wk = { Xk ; O } если Xk Yi ; Xk, если Xk Yi } \ {AoO; AoA}

Для всех правил, в правых частях которых

встречаются нетерминалы из множества Yi к правилам добавляется множество, в котором правые части представляют собой все возможные комбинации с заменой нетерминалов множества Y на O

217

Удаление O-правил

6. Если S Yi N’ = N’ {S’}, P’ = P’ {S’oO |

S}, S’ = {S’} если OL(G), то вводится новый

нетерминал, который становится аксиомой

идва новых правила

Пример. G ( {a,b,c}, {A,B,C,S}, P, S); P = { SoAaB | aB | cC; AoAB | a | b | B; BoBa | O; CoAB | c

}

1. Y0 = {B}; i =1

2.1. (AoB), B Y0* Y1 = Y0 { A } = { A, B }

2.2. (CoAB; AoAB; AoB), A,B Y1* Y2 =

{ A,B,C } = { A, B, C} 2181

Удаление O-правил

2.3. ( CoAB; AoAB; AoB), A,B Y2* Y3 = Y2 { A, B, C } = { A, B, C }; Y3 = Y2;

4. N’ = { A,B,C,S }; T’= { a,b,c }; P’ = { SoAaB | aB | cC; AoAB | a | b | B; BoBa; CoAB | c }

5.1. SoAaB; A,B Y3; P’ = P’ { SoAaB | Aa | aB | a }

5.2. SoaB; B Y3 P’ = P’ { SoaB | a }

5.3. So cC; C Y3 P’ = P’ { SocC | c }

5.4. AoAB; A, B Y3 P’ = P’ { AoAB | A | B } \ { AoA }

219

Удаление O-правил

5.5. AoB; B Y3 P = P { AoB }

5.6. BoBa; B Y3 P = P { BoBa | a }

5.7. CoAB; A, B Y3 P = P { CoAB | A | B }

6. S Y3

P’ = { SoAaB | aB | cC | Aa | a | c; AoAB | a | b | B; BoBa | a; CoAB | c | A | B }

220