Низхідний синтаксичний аналіз

Низхідний синтаксичний аналіз — один з методів визначення приналежності вхідного рядка деякій формальній мові, описаній 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}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$