Метод рекурсивного спуску

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод рекурсивного спуску або низхідний розбір — один з методів визначення приналежності вхідного рядка деякій формальній мові, описаній LL(k)-граматикою. Це клас алгоритмів лексичного аналізу, де правила формальної граматики розкриваються, починаючи зі стартового символу до отримання потрібної послідовності токенів.

Ідея методу[ред.ред. код]

Для кожного нетермінального символу K будується функція, яка для будь-якого вхідного слова x робить дві речі:

  • Знаходить найбільший початок z слова x, здатний бути початком виводжуваного з K слова
  • Визначає, чи є початок z виводжуваним з K

Така функція має задовольняти такі критерії:

  • зчитувати із ще необробленого вхідного потоку максимальний початок A, який є початком деякого слова, виводжуваного з K
  • визначати чи є A вивідним з K або просто невивідним початком виводжуваного з K слова

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

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

Найбільш простий і «людяний» варіант створення аналізатора, що використовує метод рекурсивного спуску, - безпосереднє програмування за кожним правилом вводу для нетерміналів граматики.

Умови застосування[ред.ред. код]

Нехай в даній формальній граматиці N — скінченна множина нетермінальних символів; Σ — скінченна множина термінальних символів, тоді метод рекурсивного спуску можна застосувати тільки, якщо кожне правило цієї граматики має такий вигляд:

  • або A \rightarrow \alpha, де \alpha \subset (\Sigma \cup N)*, і це єдине правило виводу для цього нетермінала
  • або A \rightarrow a_1\alpha_1|a_2\alpha_2|...|a_n\alpha_n для всіх i=1,2...n; a_i \ne a_j, i \ne j; \alpha \subset (\Sigma \cup N)*

Алгоритми низхідного розбору[ред.ред. код]


Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.