spoPresentation2

Перевод КС грамматики в НФ Хомского

Пример. G = ( {a,q,w}, {X,D,E}, {XoDaqEw; Doq; EoDa | Dw }, X)

1. T’ = {a,q,w}, N’ = {X,D,E}, S’ = X

2. P’ = { Doq}

3. P’ = P’ { p | AoBA’, A’oa; причем AoBa P; A,B N, a T }; N’=N’ {A’}

3.1. EoDa P: P’ = P’ { EoDA’, A’oa}; N’ = N’{A’}

3.2. EoDw P: P’ = P’ { EoDW’, W’ow}; N’ = N’ {W’}

201

Перевод КС грамматики в НФ Хомского

5. P’ = P’ { p | Bi-1oAi’Bi ; i=1,2,…,k-1; B0=A; Bk-1 = Ak’ , где

Ai’=Ai , если Ai N , и P’ = P’ { p’ | Ai’ o Ai } если Ai Т,

причем AoA1A2…Ak P, k>2 }; N’ = N’ {B1, B2,…,Bk-2,

A1’, A2’,…Ak’}

5. XoDaqEw P; K=5;

N’ = N’ {B1, B2, B3, A1’, A2’, A3’, A4’, A5’} P’ = P’ {

B0oA1’B1, B1oA2’B2, B2oA3’B3, B3oA4’B4} ={ XoA1’B1, B1oA2’B2, B2oA3’B3, B3oA4’A5’} ={

XoDB1, B1oA2’B2, B2oA3’B3, B3oEA5’}; P’ =P’ { A2’oa, A3’oq, A5’ow}

202

Перевод КС грамматики в НФ Хомского

G’ = ( {a,q,w},

{ X, D, E, A’, W’, B1, B2, B3, A2’, A3’, A5’ },

{Doq , EoDA’ | DW’ , A’oa, W’ow, XoDB1, B1oA2’B2, B2oA3’B3, B3oEA5’, A2’oa, A3’oq, A5’ow } ,X)

203

Перевод КС грамматики в НФ Грейбах

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

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

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

грамматика G должна быть приведенной

грамматика G не должна содержать левой рекурсии

204

Перевод КС грамматики в НФ Грейбах

1. G’=G;

2. Нетерминалы упорядочиваются N’ =

{A1,A2,…,An} таким образом, что p P’:

AioAjD, Ai,Aj N, D V* , i<j

3. i = |N’|-1;

4. Aj N’ : AioAjD; AjoE1|E2|…|Em

P’ = P’ { AioE1D|E2D|…|EmD } \ {AioAjD }

правило заменяется для всех Aj, где Ek V*, k =

1,2,…m – весь набор правил для Aj5. i--; если i != 0, повторить п.4

205

Перевод КС грамматики в НФ Грейбах

6. pi P’: AobJ1J2…Jm , A N’, b T’, Ji V

P’ = P’ { AobY1Y2…Ym } \ { AobJ1J2…Jm }

где Yi=Ji если Ji N’,

где N’=N’ {Yi }, P’=P’ {YioJi } если Ji T’

Пример. G = { {*,n}, {S,A,B}, {SoB*A, Bon | A*B, Aon }, S}

2-3. S1oB2*A3, B2on | A3*B2, A3on; i = 3-1 = 2;4.1. B2on | A3*B2 B2on | n* B2; i=1

4.2. S1oB2*A3 S1on* A3 | n* B2*A3; i=0;

206

Перевод КС грамматики в НФ Грейбах

6.1. B2on*B2 B2onY1B2; N’=N’ {Y1};

P’=P’ {Y1o*};

6.2. S1on*A3 S1onY1A3

6.3. S1on*B2*A3 S1onY1B2Y1A3

P’={A3on; B2on | nY1B2; Y1o*; S1onY1A3; S1onY1B2Y1A3 };

G’ = ( { *, n }, {S,A,B,Y},

{ Aon; Bon | nYB; SonYA | nYBYA; Yo* } , S)

207

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

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

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

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

1. Y0= ; i=1; Алгоритм работает со

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

208

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

2. Yi = Yi { A | (AoD) P, D (Yi-1 T)*; A N}

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

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

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

5. P’=P’ { p | AoD, A,D(T Yi)* } остаются

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

209

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

Пример. G ( {a,b,c}, {A,B,C,D,E,F,G,S}, P, S); P = { SoaAB | E; AoaA | bB; BoACb | b; CoA | bA | cC | aE; EocE | aE | Eb | ED | FG; Doa | c | Fb; FoBC | EC | AС; GoGa | Gb }

1. Y0= ; i=1

2.1. AoD, D (Y0 T)* = {a,b,c} Y1 = {B,D}

2.2. AoD, D (Y1 T)* = {B,D,a,b,c}

Y2 = {A,B,D}

2.3. (Y2 T)* = {A,B,D,a,b,c} ; Y3 = {S,A,B,C,D}

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

210