Мережні граматики Вудса

В.А. Вудс запропонував модель, орієнтовану на опис і аналіз природних мов, яку можна вважати однією з найбільш вдалих. Маються на увазі так звані розширені мережі переходів Вудса, вперше введені Конвеєм, які узагальнюють поняття скінченного автомата (розглянутого в …).

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

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

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

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

Побудований в такий спосіб пристрій допускає ті ж мови, що й автомати з магазинною пам'яттю, тобто безконтекстні мови. Перевагою такого підходу є те, що він дозволяє отримати більш компактне подання та більш ефективні алгоритми аналізу КВ-мов, а також те, що дану модель можна природно «розширювати» до більш потужної моделі, що допускає БС-мови.

Приклад 1. Розглянемо приклад рекурсивної мережі переходів і роботи автомата, що відповідає цій мережі та допускає мову, розглянуту в прикладі 2. Ланцюжки цієї мови мають вигляд αβ, де ланцюжок β є «дзеркальним відображенням» ланцюжка а {a, b}. Така мова не є автоматною, тому що можна побудувати граматику, що породжує дану мову, у якій є нетермінальні символи, що вставляються самі.

qS

q3

q₁

qA

a

a

q5/1

q

					qS

qA

qB

q7/1

q_6/1

Рисунок 10.2. – Приклад рекурсивної мережі переходів

Рекурсивна мережа переходів, що відповідає автомату, який допускає дану мову, зображена на рис.10.2. Автомат може перебувати в одному з десяти станів:

q_S, q_A, q_B, q₁, q₂, q₃, q₄, q₅, q₆, q₇.

Заключні стани q₅, q₆, q₇ позначені спеціальним чином:

q_5/1, q_6/1, q_7/1.

Рекурсивна мережа переходів складається з трьох не зв'язаних між собою графів, дуги яких позначені як символами алфавіту {а, b}, так і символами станів.

Роботу автомата ілюструє рис.10.3. Ланцюжок abba допускається даним автоматом, тому що наприкінці його роботи після зчитування останнього символу ланцюжка автомат переходить у заключний стан q₅ при порожньому магазині.

Приклад 1. Розглянемо маленький фрагмент російської мови, що може бути породжений КВ-граматикою, продукції якої задамо за допомогою нормальної форми Бекуса;

<РЕЧЕННЯ>:: = <ПИТАЛЬНЕ> | <СТВЕРДЖ.>

<СТВЕРДЖ.>:: = <ГРУПА ІМ.> <ДІЄСЛОВО> | <ГРУПА СУЩ.>

<ДІЄСЛОВО> <ОБСТ. МІСЦЯ>

<ПИТ.>:: = <ДІЄСЛОВО> <ЧАСТКА> <ГРУПА ІМ.> |

<ДІЄСЛОВО> <ЧАСТКА> <ГРУПА ІМ.>

<ОБСТ. МІСЦЯ>

<ГРУПА ІМ.>:: = <ІМ.> | <ПРИКМ.> <ГРУПА ІМ.>

<ОБСТ. МІСЦЯ>:: = <ПРИЙМЕННИК> <ГРУПА ІМ.>

<ІМ.>:: = (МИША) | (КІШКА) | (СТІЛ) | (ДИВАН)

<ДІЄСЛОВО>:: = (СИДІТИ) | (ЛЕЖАТИ)

<ПРИЙМ.>:: = (ЧОРНИЙ) | (М'ЯКИЙ)

<ПРИЙМЕННИК>:: = (ЗА) | (НА)

<ЧАСТКА>:: = (ЧИ)

a b b a a b b a a b b a a b b a

q₃ q₃

a b b a a b b a a b b a a b b a

q₅ q₅ q₃

q₃ q₃

a b b a a b b a

q₅ q₅

Рисунок 10.3. – Етапи аналізу ланцюжка abba автоматом, що відповідає рекурсивній мережі переходів

За допомогою цієї граматики можна породжувати речення, що відповідають, наприклад, таким фразам російської мови:

МИХАЙЛО СИДИТЬ ЗА СТОЛОМ.

ЧОРНА КІШКА ЛЕЖИТЬ НА М'ЯКОМУ ДИВАНІ.

ЧИ СИДИТЬ МИША ЗА СТОЛОМ?

ЧИ ЛЕЖИТЬ КІШКА?

На рис. 10.4 наведено рекурсивну сітку переходів для автомата, що допускає мову, яка породжується описаною вище граматикою. Відзначимо, символи ланцюжків, що допускаються автоматом (породжуваних граматикою), у цьому випадку являють собою так звані «нормалізовані» слова російської мови, взяті в дужки. Так, фразі МИХАЙЛО СИДИТЬ ЗА СТОЛОМ відповідає ланцюжок (МИХАЙЛО) (СИДІТИ) (ЗА) (СТІЛ).

«Нормалізація» звичайно передує етапу синтаксичного аналізу фрази.

(СИДІТИ)

<ДІЄСЛОВО>

<IМ.>

Рис. 10.4 – Рекурсивна мережа переходів для фрагменту української мови

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

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

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

Таким чином вводяться наступні розширення в рекурсивні мережі переходів:

– дозволено використовувати довільні умови на дугах, істинність яких є критерієм проходження дуги;

– введено необхідну кількість регістрів, що працюють за принципом магазинної пам'яті, у яких зберігаються фрагменти синтаксичних підструктур і індикатори, що керують процесом аналізу вхідної фрази;

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

Механізм інтерпретації РМП називається мережною граматикою. Більш формально мережна граматика визначається наступною трійкою:

де V - опис словників, що використовуються при розборі вхідного ланцюжка;

L – опис нестандартних функцій, необхідних для ефективного розбору;

N – опис РМП, що представляє собою опис множини так званих кущів.

Кущем будемо називати вершину РМП із множиною дуг, що виходять з цієї вершини.

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

Опис мережної граматики зручно задати за допомогою нормальної форми Бекуса, розширеної за рахунок використання метасимволів {, }, що специфікують можливість повторення розміщених в них конструкцій будь-яке (у тому числі нульове) число разів, а також метасимволів [, ], що вказують на необов'язковість конструкції в таких дужках.

Отже:

<мережна граматика>:: = (<опис словників> [<опис нестандартних процедур>] <розширена мережа переходів>)

<опис словників>:: = (VOCAB {<опис словника>})

<опис словника>:: = <ім’я словника> (<функція введення>) | <ім’я словника> ({<словникова стаття>})

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

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

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

У відповідності з вказаними типами поміток вводяться поняття: CAT-дуги, TST-дуги та PUSH-дуги. Крім того, для індикації заключних станів в мережі та побудови структур (форм) розібраних часток фрази вводиться POP-дуга. Тоді <дуга>:: = (CAT <категорія> <умова> {<дія>} <заключна дія>) | (TST <умова> {<дія>} <заключна дія>) (PUSH <стан> <умова> {<дія>} <заключна дія>) | (POP <форма> < умова>)

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

<умова>:: = <И-умова> | <ИЛИ-умова> | <НЕ-умова> <РАВНО-умова>

<И-умова>:: = (AND <аргумент> <аргумент> {<аргумент>})

<ИЛИ-умова>:: = (OR <аргумент> <аргумент> {<аргумент>})

<НЕ-умова>:: = <NOT <аргумент>)

<РАВНО-умова>:: = (EQUAL <аргумент> <аргумент>)

В якості аргументів використовуються Т, NIL, (ім’я) (в цьому випадку береться значення заданого імені, а якщо його немає — NIL) чи (умова).

Що ж стосується необхідних умов – вони різні для різних типів дуг і забезпечуються деякими вбудованими механізмами. Зокрема, для дуг TST та POP необхідні умови виконуються завжди. Для дуги CAT необхідна умова приймає значення Т в тому випадку, якщо поточне слово вхідної фрази, попередньо занесене в деякий регістр (будемо називати його *), збігається з одним зі слів у словнику, ім'я якого задано в (категорії), або текстуально збігається з позначкою дуги.

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

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

При виконанні необхідних і достатніх умов дозволяється прохід по дузі, що супроводжується виконанням дій.

По визначенню

<дія>:: = <дія над вмістом> | <дія над показником>

<дія над вмістом>:: = (SETR <ім’я регістра> <фор­ма>) | (SENDR <ім’я регістра> <форма>) | (LIFTR <ім’я регістра> <форма>)

<дія над показником>:: = (UP <ім’я регістра>)

Функція SETR специфікує присвоювання на поточному рівні; SENDR - заміну інформації в регістрі, значення якої зберігається у верхній комірці системного регістра повернень, а LІFTR - заміну інформації в позиції на одиницю нижче верхньої комірки поточного регістра. Функція UP працює тільки на поточному рівні й виштовхує вміст верхньої комірки відповідного регістра.

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

<заключна дія>:: = <перехід зі зчитуванням> | <перехід без зчитування>

< перехід зі зчитуванням>:: = (ТО <ім’я переходу>)

<перехід без зчитування>:: = (JUMP < ім’я переходу>)

< ім’я переходу>:: = <стан> | <ім’я регістра>.

Залишилося розглянути можливі форми, які використаються у визначеннях POP-дуги та діях. У підсумку форми потрібні для побудови деяких структур і присвоювання їх як значення певним регістрам. Мінімальний набір форм повинен забезпечувати одержання наступних значень:

поточного слова (*);

заданої властивості для поточного слова з регістра * (GETF);

довільної структури (QUOTE);

вмісту довільного регістра (GETR);

списку, складеного з інших форм (APPEND).

Приклад 10.2. Розглянемо опис фрагменту аналізатора простих речень російської мови, що породжуються відповідно до граматики, представленої на рис. 10.5:

(ПРЕДЛ (PUSH ИМГР Т (SETR R ИМГР*) (SETR R РДИМГР (GETR RРД))

(SETR R ЧСИМГР (GETR R ЧС)) (SETR R СЕМИМГР (GETR RCEM)) (JUMP Ql)))

(Ql (PUSH ГЛГР T (SETR R ГЛГР*) (JUMP Q2)))

(Q2 (POP (BUILDQ (ПРЕДЛ++) R ИМГР R ГЛГР) (EQUAL (GETR*)

NIL))) (ИМГР (PUSH ГРПР T (SETR R ГРПР*) (JUMP Q3)))

(Q3 (CAT сущ (AND (EQUAL RP Д (GETF РОД)) (EQUAL R ЧС (GETF ЧИСЛО)) (EQUAL RП (GETF ПАДЕЖ)) (SETR RC*) (SETR RCEM (GETF ФИЗОБ)) TO Q4)))

(Q4 (POP (BUILDQ (ИМГР + (С (+))) R ГРПР RC) T)) (ГРПР (CAT ПРИЛ T (SETR R РД (GETF РОД)) (SETR R ЧС (GETF ЧИСЛО)) (SETR RП (GETF ПАДЕЖ)) (SETR RПP *) (TO Q5)) (TST (EQUAL R ПР NIL) (JUMP Q5)))

(Q5 (CAT прил (AND (EQUAL R РД (GETF РОД)) (EQUAL R ЧС GETF ЧИСЛО)) (EQUAL RП (GETF ПАДЕЖ))) APPEND R ПР*) (TO Q5)) (POP (BUILDQ (ГРПР (ПР (+))) R ПР) Т)) (ГЛГР (CAT гл (AND (EGUAL R РДИМГР (GETF РОД)) (EQUAL R ЧС ИМГР (GETF ЧИСЛО))) (SETR R ГЛ*) (TO Q6»

(Q6 (......))

Нехай на вхід аналізатора надходить фраза:

БОЛЬШОЙ ЧЕРНЫЙ КОТ ВСКОЧИЛ НА СКОЛЬЗКУЮ ПОДНОЖКУ МОСКОВСКОГО ТРАМВАЯ.

Для розбору її необхідно звернутися до вбудованої функції (PARSE <фраза>). Основні дії функції PARSE зводяться до запису в регістр * першого слова фрази (БОЛЬШОЙ) і передачі управління в стан ПРЕДЛ.

Рисунок 10.2. – Елемент розширеної мережі переходів для фрагменту російської мови

Опис куща, позначеного цим символом, містить єдину дугу (PUSH ИМГР.........). Для проходу по цій дузі необхідно знайти іменну групу ИМГР. В свою чергу аналіз іменної групи припускає послідовний пошук групи прикметника (ГРПР) і іменника (СУЩ), які повинні бути погоджені по роду, числу, відмінку та семантичним ознакам, збереженим у словниках.

Для приклада розглянемо процес аналізу групи іменника стану Q3. Як видно з фрагменту аналізатора, до цього моменту стани введених регістрів будуть наступними:

(RГРПР)= (ГРПР(ПР(БОЛЬШОЙ ЧЕРНЫЙ)))

(RПД) = МУЖСКОЙ

(RЧC) = ЕДИНСТВЕННОЕ

(RП) = ИМЕНИТЕЛЬНЫЙ

(*) = КОТ

Єдина дуга, що виходить зі стану Q3 - це САТ-дуга, позначена ім'ям категорії СУЩ. Тому аналізатор звертається до словника іменників для пошуку слова (точніше, його основи) у регістрі *. Припустимо, що слово знайдене в словнику. Тоді його характеристики переносяться зі своїми найменуваннями в спеціальний регістр властивостей, а як результат цієї процедури видається значення Т (TRUE). Таким чином, необхідна умова переходу по САТ-дузі виконано. В якості достатньої умови в цьому випадку обчислюється значення предикату (AND....), де перевіряється узгодження властивостей поточного слова (КОТ) зі значеннями регістрів RРД, RЧС та RП. Значенням цього предиката є Т і, отже, прохід по дузі можливий. Прохід по дузі супроводжується виконанням присвоювання значення поточного слова (КОТ) регістру RC і значення семантичної ознаки ФИЗОБ семантичному регістру RCEM. Далі відповідно до заключної дії (ТО Q4) зчитується чергове слово вхідної фрази (ВСКОЧИЛ) і здійснюється перехід у стан Q4.

Стан Q4 заключний та містить єдину POP-дугу з тотожно істинною достатньою умовою. В результаті проходу по цій дузі у верхній комірці регістра формується наступна структура:

(ИМГР(ГРПР(ПР(БОЛЬШОЙ ЧЕРНЫЙ))) (С(КОТ))).

На цьому аналіз іменної групи закінчується і аналізатор повертається до того моменту, де розбір був припинений на дузі (PUSH ИМГР) перевіркою необхідної умови. У цей момент вміст регістрів наступний:

(RГРПР) = Ø

(RРД) = МУЖСКОЙ

(RЧC) = ЕДИНСТВЕННОЕ

(RП) = ИМЕНИТЕЛЬНЫЙ

(RCEM) = ОДУШЕВЛЕННЫЙ

(*) = (ИМГР(ГРПР(ПР(БОЛЫПОЙ ЧЕРНЫЙ))) (С(КОТ))) (ВСКОЧИЛ)

Аналіз частини речення, що залишилася, легко може бути продовжений.