Специфікація та синтаксичний аналіз із використанням контекстно-вільних граматик

Перераховані нижче правила визначають граматику для простих транзитивних речень типу «Людина любить собаку». Для зручності ці правила пронумеровані.

1. sentence noun_phrase verb_phrase

2. noun_phrase noun

3. noun_phrase article noun

4. verb_phrase verb

5. verb_phrase verb noun_phrase

6. article a

7. article the

8. noun man

9. noun dog

10. verb likes

11. verb bites

У правій частині правил 6 –11 знаходяться англійські слова. Ці правила формують словник доступних слів, які можуть з'являтися в реченні. Ці слова є терміналами (terminal) граматики та визначають лексикон (lexicon). Терміни, що визначають лінгвістичні поняття більш високого рівня (sentence, noun_phrase), називаються нетермінальними й виділяються стилем формул. Відзначимо, що термінали не зустрічаються в лівій частині правил.

Коректне речення – це будь-який рядок терміналів, який можна розділити на частини за допомогою цих правил. Трансформація починається з нетермінального символу sentence і в результаті серії послідовних підстановок, визначених правилами граматики, приводить до формування рядка терміналів. Коректна підстановка - це заміна символу, що відповідає лівій частині правила, символом із правої частини цього правила. На проміжних стадіях виведення рядки можуть включати як термінали, так і нетермінальні вирази. Таке представлення називається сентенціальною формою (sentential form). Трансформація речення «The man bites the dog» буде виглядати наступним чином (табл. 1).

Таблиця 1. – Трансформація речення

Рядок	Правило, що застосовується
Sentence noun_phrase verb_phrase article noun verb_phrase The noun verb_phrase The man verb_phrase The man verb noun_phrase The man bites noun_phrase The man bites article noun The man bites the noun The man bites the dog

Це приклад трансформації зверху вниз (top-down derivation). Вона починається із символу sentence і завершується рядком терміналів. Трансформація знизу вверх починається з рядка терміналів, включаючи заміну елементів правої частини правила відповідними елементами з лівої частини та завершується символом sentence.

Трансформацію можна представити у вигляді дерева, що отримало назву дерева граматичного розбору (parse tree), у якому кожний вузол – це символ з набору правил граматики. Внутрішні вузли дерева – нетермінальні. Кожний вузол і його нащадки – це ліва й права частини деякого правила граматики відповідно. Листові вузли – це термінали, а символ sentence – корінь дерева. Дерево розбору для речення «The man bites the dog» показане на рис. 2.

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

Розбір речень – це задача побудови трансформації або дерева граматичного розбору для вхідного рядка на основі формального визначення граматики. Алгоритми граматичного розбору діляться на два класи: аналізатори зверху вниз (top-down parser), які починають свою роботу з високорівневого символу sentence і будують дерево, листи якого становлять цільове речення, і аналізатори знизу вверх (down-top parser), робота яких починається зі слів речення (терміналів), і в результаті послідовних операцій формується символ sentence.

Основні труднощі рішення задачі граматичного розбору полягають у виборі з існуючого набору правила, яке варто використовувати на кожному кроці трансформації. При неправильному виборі аналізатор може не розпізнати коректно речення. Наприклад, при розборі речення «The dog bites» методом знизу вверх в результаті застосування правил 7, 9 і 11 буде отриманий рядок article noun verb. Після цього помилкове застосування правила 2 генерує рядок article noun_phrase verb, який не можна привести до символу sentence. Насправді аналізатор повинен використовувати правило 3. Аналогічні проблеми виникають при розборі зверху вниз.

Рисунок 2 – Дерево граматичного розбору для речення «The man bites the dog»

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

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

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