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

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

Ідея методу

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

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

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

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

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

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

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

Умови застосування

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

• або ${\displaystyle A\rightarrow \alpha }$, де ${\displaystyle \alpha \subset (\Sigma \cup N)*}$, і це єдине правило виводу для цього нетермінала
• або ${\displaystyle A\rightarrow a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}}$ для всіх ${\displaystyle i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*}$

Алгоритми низхідного розбору

• Рекурсивний низхідний парсер
• LL-парсер