spoPresentation2

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

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

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

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

1. Yx0 = { X }; X N; i = 1; Для каждого

нетерминала X строится специальное множество цепных символов Yx

221

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

2. Yxi = Yxi-1 { B | AoB P, A Yxi-1 };

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

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

4. Yx = Yxi \ { X }

5. N’ = N; T’ = T; P’ = P \ {AoB}; S’ = S;

6. P’ = P’ { BoD | AoD P’, A YB , B z A };

идет замена цепных правил непосредственно на нетерминал-источник

222

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

Пример. G = ( { +, -, /, *, a, b }, { S,T,E }, P, S); P = { S o S+T | S-T | T; To T*E | T/E | E; E o (S) | a |

b }

1.1. Ys0 = { S }; i = 1

1.2.1. SoT, S Ys0 Ys1 = Ys0 { T } = { S,T }

1.2.2. SoT, ToE, S,T Ys1 Ys2 = Ys1 { T, E } = {

S,T, E }

1.2.3. SoT, ToE, S,T Ys2 Ys3= Ys2 { T, E } = {

S,T,E }; Ys3 = Ys2

1.4. Ys = Ys3 \ { S } = { T, E }

223

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

2.1. YT0 = { T }; i = 1

2.2.1. YT1 = YT0 { E } = { T, E }

2.2.2. YT2 = YT1 { E } = { T, E }

2.4. YT = YT2 \ { T } = { E }

3.1. YE0 = { E }; i = 1

3.2.1. YE1 = YE0

	3.4. YE = YE1 \ { E } =
	5. N’ = { S,T,E }; T’ = { +, -, /, *, a, b }; P’ = { SoS+T |
	S-T; ToT*E | T/E; Eo(S) | a | b }; S’=S

224

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

6.1. S YS, S YT S YE

6.2. T YS; ToT*E | T/E P’ = P’ {SoT*E | T/E }

6.3. E YS, E YT; Eo(S) | a | b P’ = P’ { So(S) | a | b; To(S) | a | b }

P’ = { SoS+T | S-T | T*E | T/E | (S) | a | b; ToT*E | T/E | (S) | a | b ; Eo(S) | a | b }

225

Удаление левой рекурсии

Любая КС-грамматика может быть как леворекурсивной, так и праворекурсивной, а также одновременно и право- и леворекурсивной

Полностью исключить рекурсию невозможно, однако один вид рекурсии можно заменить на другой

Значительные неудобства чаще всего создает левая рекурсия

226

Удаление левой рекурсии

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

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

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

1. S’=S, i = 1

2. P’ = P’ { p P | AioBE, B V, EV*, Ai z B }

N’ = N’ { Ai | AioE P’ }; т.е. если все

правила для A не содержат левой рекурсии, они переносятся без изменений

227

Удаление левой рекурсии

3. P’ = P’ { { AioE1 | E2 |…| Ep | E1Ai’ | E2Ai’ |…| EpAi’; Ai’oD1 | D2 |…| Dm | D1Ai’ | D2Ai’ |…| DmAi’ }

AioAiE P, E V* и Ai=AiD1 | AiD2 |…| AiDm | E1 |

E2 | Ep, где j, 1djdp, не Ej = AkJ, k d i }

N’ = N’ { Ai, Ai’ }; если есть хотя бы одно

леворекурсивное правило для Ai все правила для Ai переписываются с добавлением нового нетерминала

4. Если i = |N|, то все нетерминалы рассмотрены, конец алгоритма

228

Удаление левой рекурсии

5. i++; j = 1

6. P = P { { AioZ1J | Z2J |…| ZqJ , J V*, причем { AjoZ1 | Z2 |…| Zq } P’ и p = AioAjJP } \ p; в исходной грамматике для правил

данного вида каждое из них меняется на множество правил

7. j++; если j < i, перейти к п.6

8. Перейти к п.2

229

Удаление левой рекурсии

Пример G ( { a,b,c,d,z }, { S,A,B,C }, P, S)

P = { SoAa; AoBb; BoCc | d; CoAz | a }

1. S’ = S; i = 1; // Ai = S;

2.1. SoAa P’ = P’ { SoAa }; N’ = N’ {S};

//P’ = { SoAa }

4.1. i z 4

5.1. i =2; j =1; // Ai = A; Aj = S;

6.1.1. правил в P вида AoSJ нет

7.1.1. j = 2, переход к п.2

2.2. AoBb P’ = P’ { AoBb }; N’ = N’ {A};

//P’ = { SoAa; AoBb }

230