Аналізатори на основі мережі переходів

Аналізатор на основі мережі переходів представляє граматику у вигляді набору скінченних автоматів або мереж переходів. Кожна мережа відповідає одному нетермінальному елементу граматики. Дуги в таких мережах позначені термінальними або нетермінальними символами. Всі шляхи в такій мережі, що ведуть від початкового стану до кінцевого, відповідають деякому правилу для нетермінальних елементів. Послідовність міток дуг такого шляху - це послідовність символів у правій частині правила. Граматика, розглянута в розділі 1, може бути описана за допомогою мереж переходів, показаних на рис. 3. Якщо граматика містить декілька правил для нетермінальних елементів, то у відповідній мережі міститься декілька шляхів від початку до мети (цілі). Наприклад, правила noun_phrase <-> noun і noun_phrase <-> article noun зображаються у вигляді різних шляхів у мережі noun_phrase на рис. 3.

Пошук успішного переходу в мережі для нетермінального елементу складається в заміні цього елементу вмістом правої частини граматичного правила. Наприклад, для розбору речення аналізатор повинен знайти перехід у мережі речення sentence. Він починається з вихідного стану (S_initial), включає перехід noun_phrase, потім перехід verb_phrase і завершується в кінцевому стані S_final. Цей процес еквівалентний заміні вихідного символу sentence парою символів noun_phrase і verb_phrase.

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

Рисунок 3 – Визначення мережі переходів простої граматики англійської мови

Розглянемо просте речення “Dog bites” («Собака кусається»). Перші кроки розбору цього речення показані на рис. 4.

Рисунок 4 – Аналіз речення «Dogs bites» за допомогою мережі переходів

1. Аналізатор починає свою роботу з мережі sentence і намагається зробити перехід по дузі з міткою noun_phrase. Для цього він переходить до мережі noun_phrase.

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

3. У мережі article не можна знайти шлях до кінцевого вузла, оскільки жодна з дуг не позначена першим словом речення «dog». В результаті безуспішної спроби пошуку шляху аналізатор вертається до мережі noun_phrase.

4. Аналізатор намагається пройти по дузі noun у мережі noun_phrase і переходить до мережі noun.

5. Прохід по дузі з міткою «dog» завершується успішно, а саме вона відповідає першому слову вхідного потоку.

6. Результат пошуку в мережі noun позитивний. Це значить, що дуга з міткою noun у мережі noun_phrase веде до кінцевого стану.

7. Мережа noun_phrase повертає успішний результат мережі найвищого рівня, дозволяючи перехід по дузі noun_phrase.

8. Аналогічна послідовність кроків приводить до розбору частини речення verb_phrase.

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

function parse (символ_граматики);

begin

зберегти покажчик на поточну позицію у вхідному потоці;

case

символ_граматики є термінальним:

if символ_граматики відповідає наступному слову у вхідному потоці

then return (success)

else begin

переустановити вхідний потік;

return (failure)

end;

символ_граматики є нетермінальним:

begin

перейти до мережі переходів, що відповідає символу граматики;

стан:=початковий стан мережі;

if transition (стан) повертає success

then return (success)

else begin

переустановити вхідний потік;

return (failure)

end;

end;

end;

end.

function transition (поточний_стан)

begin

case

поточний_стан - це кінцевий стан:

return (success)

поточний_стан - це не кінцевий стан:

while існують неперевірені переходи з поточного стану

do begin

символ_граматики:= мітка наступного неперевіреного

переходу;

if parse (символ_граматики) повертає success

then begin

наступний стан:= стан наприкінці переходу;

if transition (наступний_стан)

повертає success

then return (success)

end;

end;

return (failure)

end;

end.

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

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

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

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

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