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

Метод рекурсивного спуску або низхідний розбір — один з методів визначення приналежності вхідного рядка деякій формальній мові, описаній 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)*$