Тема 8 Нормальні форми у різних типах граматик. Приведення до нормальної форми, перетворення ФГ (одне заняття)

8.1 Мета заняття за даною темою

8.2 Методичні вказівки з організації самостійної роботи студентів

Виникає питання, чому мови типу 1 називають контекстно-залежними. Можна довести, що якщо G – контекстно-залежна граматика, то існує еквівалентна їй граматика G1 така, що кожна продукція з P має вигляд:

де α,β є . Інакше кажучи, символ А може бути замінений непустим ланцюжком у певному «контексті». Кажуть, що граматика G1 являє собою так звану нормальну форму контекстно-залежної граматики G. Таким чином нетермінальні символи можна інтерпретувати як металінгвістичні змінні або, іншими словами, конструкції мови, а виведення ланцюжків мови можна розглядати як інформацію про синтаксичну структуру цих ланцюжків.

Існує ще одна нормальна форма для граматик безпосередньо складових, яка називається нормальною формою Куроди.

Граматика задана в нормальній формі Куроди, якщо кожна її продукція має одну з наступних форм:

Можна показати, що для кожної граматики G типу 1 можна побудувати еквівалентну їй граматику G₁ у нормальній формі Куроди.

Як і для БС-граматик, існують нормальні форми й для безконтекстних граматик.

Нормальною формою Хомського будь-якої КВ-граматики G називається така граматика G1, еквівалентна G, якщо кожне правило з P має один з наступних видів:

(1) A→BC, де A, B, C є VN,

(2) A→a, де a є VT;,

(3) S → e якщо e є L(G), причому аксіома S не зустрічається в правих частинах правил підстановки.

Нормальною формою Грейбах будь-якої КВ-граматики G називається така граматика G2, еквівалентна G1, усі продукції якої мають вигляд:

(1) A→aα, де А є VN; a є VT

Строго доведений той факт, що для будь-якої КВ-граматики можна побудувати обидві нормальні форми. Крім того, доведено й те, що будь-яка КВ-мова не є автоматною (належить типу 2, але не належить типу 3) тоді і тільки тоді, коли всі граматики, що задають її, мають хоча б один такий нетермінальний символ А, для якого

де α,β є (VTU V­N)+ (α і β не порожні)

Такі символи називаються самовставляючими, а граматики – граматиками із самовставлянням. Таким чином відсутність властивості самовставляння може свідчити про те, що дана граматика є регулярною (автоматною).

Приведення ФГ до нормальної форми використовується, зокрема, коли потрібна проста форма представлення КВ-мови. Наприклад, нормальна форма Хомського знаходить застосування в синтаксичних аналізаторах, що працюють за алгоритмом Кока-Янгера-Касамі [Ахо, с. 352-358].

Існує простий алгоритм, що дозволяє будь-яку КВ-граматику привести до нормальної фори Хомського.

Основна ідея алгоритму: для кожної підстановки з множини Р виду А → А1,А2…...Ак, де k> 2, включити в множину Р' правил перетвореної граматики підстановки виду

А →A₁'<A₂A₃…A_k>

* < A₂A₃…A_k > → A₂'<A₃…A_k>

< A_k-1…A_k > → A'_k-1…A_k'

де A_i'= A_i, якщо A_i є V_N, i = 1,k, та

A_i' – новий нетермінальний символ, якщо

A_i є V_T, < A_i, A_i-1,….A_k > – новий нетермінал.

Алгоритм приведення КВ-граматики до нормальної форми Хомського:

1) Включити в Р' кожне правило з Р виду А→а.

2) Включити в Р' кожне правило з Р виду А→ВС.

3) Включити в Р' правило А→ λ, якщо воно було в Р.

4) Для кожного правила з Р виду А→ A₁A₂…A_k, де k>2, включити в Р' правила * (див. превед. стор.).

5) Для кожного правила з Р виду А → A₁A₂, де хоча б один із символів A₁ та A₂ є V_T, включити в Р' правило А → A₁'A₂'.

6) Для кожного нового нетермінального символу виду A' a', введеного на кроках 4, 5, включити в Р' правило а' → a, А’ → a.

Нехай V_N' - це V_N разом з усіма новими нетермінальними символами, введеними при побудові Р'.

Тоді шуканою граматикою буде .

КВ-граматика в нормальній формі Хомського еквівалентна вихідній КВ-граматиці: L(G')=L(G).

Необхідно також повторити основні означення та алгоритми щодо перетворення КВ-граматик.

Нехай – КВ-граматика. Тоді кажуть, що нетермінальний символ Х є VN є:

а) недосяжним, якщо Х ≠ S і не існує виведення виду

б) марним, якщо не існує виведення виду

З даного визначення стає зрозумілим, що недосяжні нетермінали ніколи не з'являються в жодному з вивідних ланцюжків, а марні символи не відіграють ніякої ролі в побудові правильних термінальних ланцюжків. Такі символи можуть з'являтися в КВ-граматиці в основному не через помилки розробника мови - вони можуть бути введені в граматику алгоритмами, призначеними для модифікації граматик.

КВ-граматика називається граматикою без e– правил (e– вільною), якщо або множина Р не містить e – правил, тобто правил виду Х → e, де Х єV_N, e – порожній символ, або є рівно одне e – правило виду S→e, і при цьому S не зустрічається в правих частинах інших правил.

КВ-граматика називається граматикою без циклів, якщо в ній немає виведень виду для

Розглянемо тепер алгоритми, що дозволяють спрощувати КВ-граматику шляхом видалення з неї марних і недосяжних символів, (e-правил і ланцюгових (циклічних) правил.

Алгоритм усунення в КВ- граматиці недосяжних символів:

Вхід: КВ-граматика G=(V_N,V_T,P,S).

Вихід: еквівалентна КВ-граматика G' = V'_N,V'_T,P',S') без недосяжних символів.

Метод:

а) нехай множина V₀={S} та i =1;

б) нехай множина V_i = V_i-1 U{X | A → α χ β є P та A є V_i-1};

в) якщо V_i ≠ V_i-1 , то i=i+1 та перейти до кроку Б). У противному випадку

V'_N= V_N ∩ V_i, V'_T= V_T ∩ V_i. Шукана множина правил Р' що містить символи з V_i;

г) G' =(V'_N,V'_T,P',S').

Алгоритм усунення марних символів:

Вхід: КВ-граматика G=(V_N,V_T,P,S).

Вихід: еквівалентна КВ-граматика G’=(V'_N,V'_T,P',S') без недосяжних символів.

Метод:

а) нехай множина N₀=0 i =1;

б) нехай множина N_i= N_i-1 U{A | A → α є P та α є (N_i-1 U V_T)*};

в) якщо N_i ≠ N_i-1 , то i=i+1 та перейти до кроку б). У противному випадку

нехай N₀= N_i;

г) нехай G1=< N₀ ∩ N_i, N_T, P', S > P' ≤ P складається з правил множини Р, що містять символи з N₀ є N_N;

д) застосувавши до G₁ алгоритм усунення в КВ-граматиці недосяжних символів, отримаємо G' =(V'_N,V'_T,P',S).

Алгоритм перетворення граматики в граматику без e – правил:

Вхід: КВ-граматика G=(V_N,V_T,P,S).

Вихід: еквівалентна λ-вільна КВ-граматика G' =(V'_N,V'_T,P',S')

Метод:

а) Застосовуємо кроки а) – в) алгоритму усунення марних символів, визначаємо множину N₀={A | A → V_N , A *=> λ(е) };

б) Множину P' будуємо в такий спосіб:

- якщо підстановка А → а₀ В₁ а₁ В₂ а₂ …… В_К а_К є Р, де К ≥ 0 і В_i є N₀, але жоден символ у ланцюжку а_j є V* (0≤ а_j ≤) не належить N₀ , додамо до Р’ продукції виду А → а₀ Х₁ а₁ Х₂ а₂ …… Х_К а_К, де Х _i є або B _i або e, не включаючи в Р' продукцію А → e (це можна було б зробити, якби B _i співпали з e _i);

- якщо S є N₀ , то включивши в Р' продукцію виду S' → e | S, де S'- новий нетермінал, і нехай N'_n = V_n U {S'}, у противному випадку V'_n = V_n , S'=S.

в) нехай G' =(V'_N,V'_T,P',S').

8.3 Контрольні запитання і завдання

1. Наведіть означення нормальних форм НС-граматик.

2. Наведіть означення нормальних форм НС-граматик.

3. Для чого використовуються нормальні форми ФГ?

4. Побудувати нормальну форму Хомського для граматик, заданих своїми правилами:

G₁: Р ={S → ADFB, S →KH, F →DS, H →C, K →DC }, S – аксиома, V_T ={A,B,C,D} V_N ={S,F,H,K};

G_2: P={ A → (B), B → CDC, C → a, D → ∗};

G₃: P={μ → α, μ →α∗μ, α→m, α→(q)};

G₄: P={A→1, A→1B, A→(A), B→0, B→0B};

G₅: P={ S → BAC, S → BA, A → Сab, B → b, A → a, C → c}.

5. Перетворити задану граматику в еквівалентну, виключивши Х → e, де Х є V_N, де Х ≠ S.

G: _: P={(1) <S> → <A><B><C>|<B><B>; (2) <A> → <B><B>| e;

(3) <B> → a<C>; (4) <C> →a}.

8.4 Приклади аудиторних і домашніх задач

Приклад 1.

Задана КВ-граматика своїми правилами

Р={ S→aBA

S→AB

A→BBB

A→a

B→AA

B→b}

S – шукана граматика. V_T={а,в}, V_N={S,A,B}.

Необхідно отримати еквівалентну їй граматику в нормальній формі Хомського.

Розв’язання:

Побудуємо нові правила Р'. Включимо до Р' без змін наступні правила исходной (початкової, вихідної) граматики:

S →AB, A →a, B →AA, B →b.

Таким чином необхідно перетворити лише правила: S →aBA, A →BBB Для першого з них отримуємо: S →CD, D →BA, C →a.

Аналогічно виконаємо перетворення другого правила

A →BBB: A →BH, H → BB.

Включимо знов утворені правила в Р', а нові нетермінальні символи - в V'_N, одержуємо

G'=(V_N',V_T,P',S), де

Р'={ S →AB, A →a, B →AA, B →b, S →CD, D →BA, C →a, A →BH, H → BB}

V_N'={S,A,B,C,D,H}

Приклад 2

Нехай G=({S,A},{a,b,c},P,S) і множина Р містить наступні підстановки:

1. S → aSb

2. S → c

3. A → bS

4. A → a

Застосуємо до цієї граматики алгоритми усунення недосяжних символів:

А) V₀ ={S}={S,a,b}, i=1;

Б) V₁ = V₀ U {c | S → c є P і S є V₀ }={S,a,b,c}

В) V₀ ≠ V₁ то i=2 та переходимо до кроку Б);

Б) V₂ = { V₁} U { c | S → c є P и S є V₀ }={S,a,b,c} U {c}= {S,a,b,c}= V₁;

В) V₂ = V₁, тоді

V'_N = V_N ∩V₂ = {S,A} ∩ {S,a,b,c}= {S}

V'_T = V_T∩V₂ = {a,b,c} ∩ {S,a,b,c) ={a,b,c}

P'={S → aSb; S → c}

Г) G' =(V'_N,V'_T,P',S), при цьому L(G) = L(G').

Приклад 3

Розглянемо граматику

G = <{A,B,C,D},{x,y,p,q,w,a},P,{A}>, де

P={ A → x | y D C | D

B → q | B x

C → C x | y C

D → D a | C w | p }

Для виведення та усунення марних символів в G скористаємося алгоритмом 2:

А) N₀ =0, i=0

Б) N₁ ={A | A → x є P, x є V_T} U N₀ ={A}

В) N₁ ≠ N₀ , i=2

Б) N₂ ={A} U {D | D → p є P, p є V_T }= {A,D}

B) N₂ ≠ N₁ , i=3

Б) N₃ ={A,D} U {B | B →q є P, q є V_T}={A,D,B}

B) N₃ ≠ N₂ , i=4

Б) N₄ = N₃ U 0 = N₃ ={A,D,B}

B) N₄ = N₃, N₀ ={A,D,B}

Г) G₁=({A,D,B},{x,y,p,q}, P₁,{A})

P₁={ A → x |D

B → q |B x

D → Da|p

Таким чином, ми усунули всі нетермінали, які не можуть породжувати термінальні ланцюжки.

Тепер застосуємо до G₁ алгоритм усунення недосяжних символів.

Д) V₀={A}, i=1

V₁={A} U {x | A→ x є P і A є V₀} = {A, x}

V₁ ≠ V₀,i=2

V₂={ V₁} U {D |A→D є P і A є V₁ }={A, x, D}

V₂ ≠ V₁, i=3

V₃= { V₂} U {a | D →Da є P і D є V₂}={A,x,D,a}

V₃ ≠ V₂, i=4

V₄={ V₃} U {p | D → p є P і D є V₃}={A,x,D,a,p}

V₄ ≠ V₃,i=5

V₅= V₄, тоді V₅={ V₄} U 0

V'_N= V₁∩ V₅={A,D}

V'_T= V_T ∩ V₅={x,a,p}

P'={ A → x |D

D → Da| p}

G' =(V'_N, V'_T, P', {A})

Як бачимо, у исходной граматиці G нетермінал В – недосяжний, а нетермінал С – марний. Результуюча грамматика G' не містить недосяжних марних символів.

Приклад 4

Розглянемо граматику

G=({S},{a,b},P,S) де

P={a S b S | b S a S | λ}.

Визначимо e – вільну граматику G', еквівалентну G.

N₀ =0, i=0

N₁ = N₀ U {S | S → λ є P}={S};

N₁ ≠ N₀ , i=2;

N₂ = N₁ U N₀ ={S} = N₁ N₀ ={S}

Будуємо множину P':

S → a b | a S b S | b a | b S a S | a S b | b a S | b S a

S' → S| e

(V'_N) таким чином N' N'_N = {S, S'}; S' – аксіома;

P'={ S' → S| e

S → a b | b a | a S b | a b S | b S a | b a S | b S a b | a S b S }

Вхід: e-вільна КВ-граматика G =(V_N, V_T, P, S)

Вихід: еквівалентна КВ-граматика G' =(V'_N, V'_T, P', S')

без ланцюгових та e-правил.

Метод:

а) для кожного А є V_N побудуємо множину

V_NA = { B| A *=>B є P} нетермінальних символів, виведених з А в такий спосіб:

аа) нехай N₀ ={A} та i =1

аб) нехай N_i ={C | B → C є P і B є N_i-1} U N_i-1

ав) якщо N_i ≠ N_i-1, то положим i=i+1 та повторимо крок АБ). У противному випадку N_A=Ni:

б) побудуємо множину P':

якщо (B → a) є P і не є ланцюговим правилом, то включимо в P' правило А → а для всіх таких А, що В є N_A;

в) положим G = ((N)V_N, (T)V_T, P', S)

Зауважимо, що даний алгоритм дозволяє усунути з граматики й цикли, тобто виведення виду , де А є N.

Приклад 5

1) Для записаної граматики одержати еквівалентну без марних, недосяжних символів і марних продукцій:

V_T={a,b,d}, V_N={<S>,<A>,<B>,<C>},

P={ 1.<S> → <A>|<B>,

2.<A> → a<B>|b<S>|ba,

3.<B> → (3,1)<A><B>|<B>a(3,2),

4. <C> → <A><S>|d, }

S=<S>

Розв’язання:

А) Марні символи Х такі, що

S *=> α χ β * w, де w є V_T*, тобто продовжуючи виведення від цього символу, не можна одержати термінальний ланцюжок.

Б) Недосяжні – такі символи, що S * α χ β тобто немає виведення цього символу з аксіоми (С) α і β можуть бути порожніми підланцюжками.

Недосяжні продукції – ті продукції, які не беруть участь у повному виведенні - від аксіоми до термінального ланцюжка.

<C> у лівій частині і-ої продукції не може бути отриманий виведенням з аксіоми, тому він недоступний. Продукція 4 ніколи не буде застосована у виведенні, тому d ніколи не буде виведений. Він також недосяжний.

Застосування продукций 3.1 і 3.2 призведе до виведень

<B> => <A><B> =>……

<B> => <B>a => ……….

де нетермінал <B> залишається невизначеним через термінали, тому він марний.

Марна й продукція 3. Ніяких інших марних і недосяжних символів граматика G не має.

Залишається з продукцій, що залишилися, виділити такі, які в правих частинах мають марні символи. Це продукції 1.2, 2.1.

Тепер побудуємо нову граматику, еквівалентну даній, тобто таку, що виводить ті ж термінальні ланцюжки:

G₁ = (V¹_N,V¹_T,P¹,S¹)

V¹_T = {a,b}, V¹_N = {<S>,<A>}, ]

P:

1. <S> → <A>,

2. <A> → b<S>|ba,

S = <S>.

Приклад

2) Для записаної граматики одержати еквівалентну без марних, недосяжних символів і марних продукций:

V_T={a,b,d}, V_N={<S>,<A>,<B>,<C>},

P={

1. <S> → <A> | <B>,

2. <A> → a<B> | b<S> | ba,

3. <B> → (3.1) <A> <B> | (3.2) <B> a,

4. <C> → <A> <S> |d }.

S = <S>

Розв’язання:

а) марні символи Х такі, що

S *=> α X β * ≠> w, де w є V_T*, тобто продовжуючи виведення від цього символу, не можна одержати термінальний ланцюжок.

б) недосяжні – такі символи, що S * ≠> α Х β, тобто немає виведення цього символу з аксіоми граматики. При цьому α і β можуть бути порожніми підланцюжками.

Недосяжні продукції - ті які не беруть участь у повному виведенні - від аксіоми до термінального ланцюжка.

<C> у лівій частині четвертої продукції не може бути отриманий виведенням з аксіоми, тому він недоступний. Продукція 4 ніколи не буде застосована у виведенні, тому d ніколи не буде виведений. Він також недосяжний.

Застосування продукций 3.1 і 3.2 приведе до виведень

<B> => <A> <B> =>……

<B> => <B> a => ……….

де нетермінал <B> залишається невизначеним через термінали, тому він марний.

Марна й продукція 3. Ніяких інших марних і недосяжних символів граматика G не має.

Залишається виділити продукції, що залишилися, які в правих частинах мають марні символи. Це продукції 1,2, 2,1.

Тепер побудуємо нову граматику, еквівалентну даній, тобто таку, що виводить ті ж термінальні ланцюжки:

G₁=(V¹_N,V¹_T,P¹,S¹)

V¹_T ={a,b}, V¹_N ={<S>,<A>}, ]

P:

1. <S> → <A>,

2. <A> → b<S>|ba,

S = <S>.

Зауваження: якби символу а не було в продукції 2,3 (ba) исходной граматики, його не було б і в термінальному следствии. Ми позбулися б від нього разом із продукцією 3.2 (<B>a).

Трансформована, тобто перетворена граматика G₁ не містить марних і недосяжних символів.

9.3 Контрольні запитання і завдання

9.4 Приклади аудиторних і домашніх задач

Тема 10. Граматики, що використовуються в машинних лінгвістичних процесорах. Мережеві граматики Вудса. Формалізм посилених мереж переходів. Скінченні автомати і діаграми переходів (два заняття).

10.1 Мета заняття за даною темою

10.2 Методичні вказівки з організації самостійної роботи студентів

Теорія формальних граматик, елементи якої розглядалися в попередніх темах, своїй появі багато в чому зобов'язана численним дослідженням природних мов, таких як англійська, французька, російська. Так, наприклад, виникнення понять автоматної мови, регулярної множини, марківского ланцюга було пов'язано зі статистичним дослідженням послідовностей голосних та приголосних у літературному тексті; введене Н. Хомським поняття формальної граматики виникло в результаті зусиль, спрямованих на створення строгих описів граматичних закономірностей природної мови.

У цей час природна мова продовжує залишатися об'єктом пильного вивчення фахівців в області кібернетики. Основна мета досліджень природної мови - це побудова таких мов, які могли б бути повністю формалізовані за допомогою абстрактного автомата, формальної граматики або якої-небудь алгебраїчної конструкції. Ці роботи, крім важливого теоретичного значення, мають і практичну цінність. Вони важливі, наприклад, для автоматизації синтезу текстів за допомогою ЕОМ.

Природна мова є найбільш універсальним засобом для моделювання й опису творчого мислення людини в СШІ, у системах, що використовують спілкування людини з ЕОМ, де актуально ставиться питання про розширення семантичної функції машини, для того щоб вона могла «розуміти» природно-мовну інформацію й «розумно» відповідати на питання.

Як показали численні дослідження, опис механізмів побудови та розуміння висловлень людьми, які базуються на використанні традиційних граматик, досить недосконалий. Насамперед було встановлено, що природні мови не можна розглядати як безконтекстні. Однак КВ-граматики є найбільш дослідженою моделлю для опису штучних мов (наприклад, мов програмування), а також обмежених природних мов. Глибина теоретичних досліджень і великий досвід застосування безконтекстних граматик у практичних прикладаннях свідчать про те, що вони все-таки можуть бути використані для синтаксичного опису правильних фраз природної мови, що при цьому не буде мати достатньої пояснювальної сили. Пояснювальною силою опису фрази мови називають [54] здатність синтаксичної структури цієї фрази (наприклад, дерева виведення) забезпечувати її семантичну інтерпретацію. А без семантичної інтерпретації не має смислу говорити про моделювання процесу розуміння природної мови.

Граматики безпосередніх складових (БС-граматики) являють собою клас граматик, достатній для опису природних мов у їхньому повному обсязі.

Однак використання БС-мов на практиці в значній мірі гальмується відсутністю прийнятних по ефективності й спільності алгоритмів аналізу таких мов і великою кількістю алгоритмічно нерозв'язних проблем.

Крім того, БС-граматики, як і всі породні (розпізнавальні) механізми, дають лише правила генерації (аналізу) ланцюжків мови. У них відсутні багатомісні операції – правила перетворення правильно побудованих виразів. Для природної мови це приводить до того, що істотно збільшується складність опису. Так, опис активної й пасивної форми речень, стверджувальних і питальних речень і т.д. вимагає введення самостійних породних правил. З іншого боку, очевидно, що зміст фрази не залежить, принаймні, так жорстко, від способу його вираження.

Через те що синтаксичний аналіз відіграє важливу роль у системах, призначених для розуміння природної мови, насамперед розглянемо методи граматичного розбору мов, породжуваних різними класами граматик, а також більш детальну класифікацію формальних граматик, накладену на базову класифікацію. Вводячи різні класи граматик, ми не акцентували увагу на тому, що їх визначення дають, по суті, механізми породження ланцюжків. Разом з тим очевидно, що ті ж пристрої при інвертуванні продукцій, тобто при зміні порядку проходження лівої та правої частин продукцій, дозволяють говорити про аналіз (розпізнавання, допущенні) ланцюжків мови.

Метою синтаксичного аналізу (граматичного розбору) є не тільки одержання відповіді на питання, належить чи ні до даної мови вхідний ланцюжок символів, але й побудова структури вхідного ланцюжка (дерева його виведення). Саме цим питанням приділяється найбільша увага при реалізації мов програмування в роботах зі створення трансляторів. При цьому розробників крім зручності опису цікавить ефективність аналізу мов, породжуваних різними класами граматик.

У ході досліджень по методах аналізу мовних текстів (ланцюжків мови) були запропоновані дві стратегії граматичного розбору: спадна й висхідна. Відповідно до цього всі розпізнавачі (аналізатори або парсери, від англійського parse - розбір) діляться на спадні й висхідні. Однак на практиці часто використовуються й змішані стратегії.

Робота спадного розпізнавача теоретично ґрунтується на ідеї використання породної граматики при генерації всіх можливих ланцюжків мови, поки не буде породжений ланцюжок, що відповідає вхідному. Для цього необхідно передбачити перевірку альтернатив і спосіб виходу з тупиків. Така ситуація виникає, коли серед продукцій граматики є продукції з однаковими лівими частинами виду

А→α, А→β,

де А V_N; α, β (V_T UV_N).

Стратегія висхідного розбору полягає в тому, що у вхідному рядку шукаються деякі підрядки – праві частини продукцій. Вони заміняються відповідними лівими частинами (згортаються), і процес повторюється до одержання початкового символу граматики. Основною проблемою для висхідного розпізнавача є проблема ефективного пошуку частини, що згортається, вхідного рядка та вибору альтернатив, коли виділений підрядок редукується (згортається) неоднозначно. Формально така ситуація характеризується наявністю продукцій з однаковими правими частинами виду

А→α, В→α,

де А, В V_N; α (V_T UV_N).

Таким чином, і спадний, і висхідний розпізнавачі при розборі вихідного ланцюжка можуть робити невірні редукції (заміни, згортки). Звідси випливає необхідність повернень і, як наслідок, ускладнення аналізу. У випадку граматичного розбору фраз природної мови ця проблема не є критичною в силу невеликої довжини вихідних ланцюжків. Якщо ж ланцюжками, що аналізуються, є тексти програм на мовах програмування, повернення в більшості випадків неприпустимі. Тому всі методи граматичного розбору, запропоновані для ефективного аналізу текстів на штучних мовах, використовують повне виключення або істотне скорочення повернень і повторного аналізу вхідного рядка.

Специфіка цих методів привела до розробки спеціальних алгоритмів для спеціальних підкласів граматик.

Найпростішим типом аналізаторів є такий, у якому реалізуються регулярні або автоматні граматики. Такі аналізатори можуть бути використані в системах спілкування на природних мовах на етапі морфологічного аналізу, тобто аналізу окремих слів, з яких будуються речення природної мови, а також у процесі розбору простих конструкцій природної мови. Як було показано раніше, для аналізу ланцюжків, що породжуються такими граматиками, з успіхом застосовуються кінцеві автомати.

Існує багато різних алгоритмів граматичного розбору регулярних мов, однак загальним для всіх цих алгоритмів є наявність у тому або іншому представленні діаграми (мережі, графа) переходів. Вузли такої мережі позначаються нетермінальними символами граматики, а умовою проходження будь-якої дуги є збіг термінального символу, яким вона позначена, із черговим символом, що переглядається, із вхідного рядка.

Така діаграма дозволяє відповістити на запитання, чи належить деякий ланцюжок мові. Однак кінцевою метою аналізатора є не тільки це, але й семантична обробка виділених понять. Для здійснення такої обробки дуги позначаються не тільки термінальними символами, але й командами обробки, що переглядаються символом. Таким чином, у цьому випадку ми маємо справу не з кінцевим автоматом, а з кінцевим перетворювачем.

Розглянемо тепер методи граматичного розбору безконтекстних мов.

Одним з найбільш відомих і широко використовуваних методів, що дозволяють здійснити ефективний висхідний розбір, є метод Флойда, запропонований для аналізу спеціального підкласу безконтекстних граматик, що називаються граматиками передування (предшествования) Флойда. На множині термінальних символів такої граматики вводяться так звані відношення передування (предшествования) =, ·>, <·, суть яких наступна.

Розглянемо пару (а, b), де а, b — термінальні символи словника граматики G = (V_T, V_N, Р, S).

Будемо говорити, що для цієї пари виконується відношення =, якщо серед множини продукцій Р є продукція виду

А→α ab β,

где А V_N; α, β V (V = V_T UV_N).

Будемо говорити, що для пари (а, b) виконується відношення <·, якщо серед множини продукції Р є продукція виду

А→αaBβ,

а з В виведений ланцюжок, що починається із символу b, тобто

B=>*bγ,

де А, В V_N; α, β, γ V.

Будемо говорити, що для пари (а, b) виконується відношення ·>, якщо справедливе хоча б одне з наступних тверджень:

1) серед множини продукцій Р міститься продукція виду

А→αBbβ,

і з В виведений ланцюжок, що закінчується символом а, тобто

B=>*bа,

де А, В V_N; α, β, γ V*.

2) серед множини продукцій Р міститься продукція виду

А→αBСβ,

причому В => *γа, С => *bδ,

де А, В, С V_N; a, b V_T; α, β, γ V*.

Флойд запропонував алгоритм, що дозволяє без повернень аналізувати будь-який ланцюжок, породжуваний граматикою передування (предшествования), якщо на цю граматику накладені наступні обмеження:

- немає продукцій виду А→α, B→α а, де

А, В V_N; α (V_N V_T);

- немає продукцій виду А→αBCβ, де А, В, С V_N;

α, β (V_N V_T);

визначені раніше відношення передування (предшествования) однозначні, тобто для будь-яких двох термінальних символів існує не більше одного відношення передування (предшествования).

У силу введених обмежень граматики передування (предшествования) допускають досить обмежений клас безконтекстних мов. Тому В.Вірт і X.Вебер, а надалі Дж. Маккіман розширили цей клас послідовним ослабленням обмежень: Вірт і Вебер ввели відношення передування (предшествования) також для нетермінальних символів, а Маккіман допустив неоднозначність цих відношень. Однак при цьому ефективність розбору зменшилася за рахунок істотного збільшення необхідних для зберігання спеціальних таблиць пам'яті.

Всі перераховані методи передування (предшествования) базуються на використанні контексту з одного символу (у методі Вірта) або двох символів (у методі Маккімана). Подальшим розвитком такого підходу стали LR (k)-граматики Кнута. У них для керування розбором використовується принцип зчитування вперед на задані к символів, що дозволяє на кожному кроці розбору однозначно вибирати вірний шлях його продовження. Однак, на жаль, для реалізації таких алгоритмів на кожному кроці доводиться будувати всю множину можливих продовжень доти, поки можлива неоднозначність не буде усунута. Тому, хоча й було показано, що для будь-якої безконтекстної граматики можна побудувати еквівалентну їй LR (k)-граматику для к» 1, на практиці вони використовуються в основному лише для к = 1.

З погляду стратегії розбору LR (k)-розпізнавачі займають проміжне положення між висхідною та спадною стратегіями. Однак умовно їх можна віднести до класу спадних розпізнавачів, тому що в них все-таки переважає спадна стратегія розбору.

Слід зазначити, що застосування висхідної стратегії при аналізі фраз природної мови представляється мало перспективним, тому що пошук дерев виведення в цьому випадку в деякій мірі «сліпий» та пов'язаний з перебором. Тому весь подальший розгляд методів граматичного розбору буде стосуватися лише спадних (або переважно спадних) розпізнавачів.

До найбільш відомих розпізнавачів такого типу можна віднести так звані розпізнавачі з повільним і швидким поверненням, а також глобальні аналізатори. У них використовується наступний принцип роботи.

Нехай граматика G = (V_T, V_N, Р, S) містить до продукції виду

S→α_i1 A_i1 α_i2 …A_in-1 α_in,

де α_i1 V_T, A_ij V_N (i = 1, 2, …..., k).

Нехай β —ланцюжок, що аналізується. Тоді, якщо вибрати одну з к цих продукцій, ланцюжок β повинен містити в якості подланцюжків ланцюжки α_i1, α_i2 …, α_in, що містяться в правій частині обраної продукції. Якщо це не так, то дана продукція вважається непридатною та здійснюється перехід до розгляду іншої продукції. В свою чергу, для кожного нетермінального символу A_ij здійснюється точно така ж перевірка, як і для символу S. Таким чином, аналіз у даному випадку представляється у вигляді рекурсивної процедури, причому він повинен закінчуватися за скінченну кількість кроків, якщо в граматиці немає виведень з повторюваними ланцюжками. Необхідність здійснювати повернення в цьому випадку пов'язана з недетермінованістю розглянутого процесу аналізу.

Процедура перевірки може бути істотно прискорена за рахунок розгляду індивідуальних особливостей використовуваної в аналізаторі граматики. При цьому застосовують так звані прискорювальні тести. Нехай, наприклад, ланцюжок β, що аналізується, має вигляд: аbcaba, а продукція, для якої перевіряється вивідність цього ланцюжка, така:

C→AbB.

Можливі дві розбивки ланцюжка β, але при цьому, наприклад, відомо, що із символу В виводяться тільки такі ланцюжки, які починаються із символу с. Тому із двох розбивок відразу ж залишаємо тільки одну, що задовольняє цьому обмеженню.

Аналізатори розглянутого типу працюють швидше, ніж LR (k)-аналізатори, особливо при вдалому виборі прискорювальних тестів.

Використання контексту може ще більше збільшити ефективність граматичного розбору. У зв'язку з цим відзначимо, що програмні й індексні граматики, які породжують мови із класу більш ширшого, ніж клас безконтекстних мов, можуть бути основою для побудови ефективних аналізаторів, що використовують контекстні умови.

Із сучасних методів граматичного розбору, безпосередньо пов'язаних з аналізом речень природною мовою, відзначимо два найбільш відомих. По-перше, це так званий процедурний метод граматичного розбору Винограда, що базується на використанні системних граматик Холідея. По-друге, це так званий мережний метод, оснований на застосуванні розширених мереж переходів Вудса. В обох цих методах використовується спадна стратегія розпізнавання. Системні граматики Холідея, а також розширені мережі переходів Вудса являють собою дуже потужні механізми, що дозволяє використовувати їх для аналізу досить багатих підмножин природної мови. Зокрема, розширені мережі переходів мають потужність машин Т’юринга, тому можуть обробляти граматику будь-якого типу.

Розглянемо процедурний метод граматичного розбору Винограда. На відміну від традиційних методів розбору в цьому методі синтаксис мови тісно пов'язаний із семантикою. Такий підхід аргументується тим, що природна мова виникла як засіб комунікації між людьми. При цьому мовець кодує зміст (значення) вимовної фрази, закладаючи його в ряд синтаксичних ознак, які він вносить у цю фразу в процесі її породження (генерації). Проблема для слухача полягає в тому, щоб пізнати присутність таких ознак і використовувати їх для семантичної інтерпретації цієї фрази. Для системних граматик Холідея, що лежать в основі методу синтаксичного аналізу Винограда, таке розпізнавання синтаксичних ознак має першорядне значення, так як передбачається, що значення (зміст) фрази відіграє найважливішу роль у формуванні її структури. При цьому досліджуються системні мережі, що описують способи, за допомогою яких різні ознаки взаємодіють і впливають одна на одну.

До синтаксичних ознак відносяться, наприклад, такі ознаки категорії РЕЧЕННЯ (CLAUSE): MAJOR (головне), SEC (другорядне), DECLARATIVE (стверджувальне), IMPERATIVE (спонукальне), QUESTION (питальне) і т.д.

Робота зі співвіднесення набору ознак з фактичною фразою на природній мові виконується в системній граматиці правилами реалізації. При використанні цієї граматики для синтаксичного аналізу речень на природній мові замість правил реалізації розглядають зворотні їм правила інтерпретації, які сприймають вхідний рядок (фразу), ідентифікують її структуру та розпізнають її ознаки.

Процедурний метод синтаксичного аналізу Винограда як формалізм для опису граматики використовує спеціальну мову програмування PROGRAMMAR, а система граматичного розбору являє собою інтерпретатор з цієї мови. Він виконує розбір, використовуючи спадну стратегію. При цьому характерною рисою й безсумнівним достоїнством процедурного методу Винограда є те, що безпосередньо в сам процес граматичного розбору внесена семантична інтерпретація, яка активно керує процесом розбору. Для цього в ході розбору підключаються ті чи інші семантичні програми, що відіграють тут роль прискорювальних тестів, як це робиться в глобальному аналізаторі.

Штучні мови (мови програмування)

Автоматні мови

Тип 3 Тип 2 Тип 1 Тип 0

	Діаграми зі скінченним числом станів

Рисунок 10. 1. – Класифікація граматик з точки зору їхнього використання в синтаксичних аналізаторах

Завдяки семантичній інтерпретації в ході розбору PROGRAMMAR не має автоматичного механізму повернення, тому що «сліпе» повернення дуже неефективне.

Питання семантичної інтерпретації, що відіграють безсумнівно визначальну роль при синтаксичному аналізі природної мови, базуються на проблемі подання знань і в даному курсі не розглядаються.

Іншим перспективним підходом до побудови машинних лінгвістичних аналізаторів у системах спілкування людини з ЕОМ природною мовою є мережний метод Вудса. Цей метод синтаксичного аналізу базується на понятті розширеної мережі переходів, що в свою чергу є розширенням поняття рекурсивної мережі переходів, яке лежить в основі аналізатора безконтекстних граматик, вперше запропонованого Конвеєм. У свою чергу рекурсивна мережа переходів являє собою розвиток ідеї розпізнавального автомата зі скінченною кількістю станів (скінченного автомата).

Рекурсивні й розширені мережі будуть докладно розглянуті далі.

Наведений раніше огляд методів граматичного розбору, що включає два найбільш відомі методи синтаксичного аналізу природних мов, дозволяє з цієї точки зору розглянути більш детальну класифікацію формальних граматик як кібернетичних моделей розпізнавання мов різних класів. На рис. 1 представлена дана класифікація. Напрямок осі вказує на зростання потужності мов. Відзначено також місце штучних мов (мов програмування) і мов, близьких до природної, у класичній класифікації Xомського.