Метод рекурсивного спуску програмування синтаксичних аналізаторів
Означення. Синтаксична діаграма — це орієнтований граф, дуги котрого позначені елементами 
. Синтаксична діаграма будується для кожного А-правила КС-граматики мови програмування.
Оскільки вершини такого графа не іменуються, то вони припускаються неявно. Синтаксична діаграма позначається іменем нетермінала, для якого вона будується.
Мета побудови синтаксичних діаграм для мови програмування на основі КС-граматики:
- для кожного А-правила КС-граматики будується синтаксична діаграма;
- на основі побудови синтаксичної діаграми для деякого нетермінала 
будуємо підпрограму, яка аналізує ту частину головної програми, яку вона визначає.
Оскільки у більшості випадків при визначенні синтаксису мови програмування ми користуємося множиною рекурсивних правил, то серед підпрограм, які будуються на основі правил граматики, будуть і рекурсивні процедури (рекурсія буде як явна, так і неявна).
Сформулюємо правила побудови синтаксичного графа:
П1. Кожен нетермінал з відповідною множиною породжуючих правил 
відображається в один синтаксичний граф. Отже, кількість синтаксичних графів рівна кількості нетерміналів граматики 
.
П2. Для кожного елемента ланцюжка 
будуємо ребро синтаксичного графа та покажемо його таким чином що:
- якщо 
, де 
— вихідна лексема, то будуємо таке ребро
(1)
Мал.1.
- якщо 
— нетермінал граматики , то будуємо таке ребро
|
|
 | |
Мал.2 .
Тоді, коли правило граматики має вигляд 
для побудови діаграми скористаємося способами (1) та (2):
 |
|
|
Ai:
Коли правило граматики має вигляд 
, то відповідний синтаксичний граф буде мати вигляд:
….. …… ……
….. …… ……
Мал. 3.
де замість 
будуються відповідні синтаксичні діаграми.
Якщо на основі граматики мови програмування побудована множина синтаксичних графів, то можна спробувати зменшити їх кількість, скориставшись підстановкою одних графів у інші. При цьому замість елемента 
підставляється його синтаксичний граф. Таким чином можна зменшити кількість синтаксичних графів. Для того, щоб забезпечити детермінований синтаксичний аналіз з переглядом вперед на одну лексему, потрібно накласти певні обмеження, а саме:
- для кожного правила виду 
з синтаксичною діаграмою виду (3) необхідне виконання наступної умови: множини 
повинні попарно не перетинатися. Зрозуміло, що ця умова гарантує детермінований вибір шляху при русі по синтаксичній діаграмі. Подальше програмування синтаксичного аналізатора можна звести до наступних примітивів:
- для фрагмента синтаксичної діаграми виду
Мал.4.
відповідний фрагмент програми (наприклад, мовою С) матиме вигляд:
extern int lexema_code;// код лексеми, яку виділив сканер
extern char lexema_text[ ];// текст лексеми
…
if (lexema_code==code_x) get_lexema( );
else error( );
- для фрагмента синтаксичної діаграми виду
|
| | |
Мал.5.
відповідний фрагмент програми матиме вигляд:
//виклик функції, яка побудована для синтаксичної діаграми
f_Ai( );
// побудованої для нетермінала .
- Для послідовності елементів синтаксичної діаграми виду
| |
|
|
Ai:
Мал.6.
відповідний фрагмент програми матиме вигляд:
extern int lexema_code;
extern char lexema_text[ ];
…
{if (lexema_code==code_x1) get_lexema( );
else error( );
f_A1( );
…
if (lexema_code==code_xn) get_lexema( );
else error( );
}
Для фрагменту синтаксичної діаграми, побудованої для А-правила, яка має вигляд:
….. …… ……
….. …… ……
Мал.7.
для кожного 
знайдемо такі множини:
- 
для 
;
- 
для 
;
…
- 
для 
.
Нехай ми знайшли відповідні множини для кожного :
- 
для ;
- 
для ;
…
- 
для .
Оскільки за умовою 
, то відповідний фрагмент програми на мові С матиме вигляд:
extern int lexema_code;
extern char lexema_text[ ];
…. ….
void Ai (void)
{switch(lexema_code)
{case code_ 
:
case code_ 
:
…
case code_ 
:// фрагмент програми для
…
break;
case code_ 
:
case code_ 
:
…
case code_ 
:// фрагмент програми для
…
break;
… …. ….
case code_ 
:
case code_ 
:
…
case code_ 
:// фрагмент програми для
…
break;
default: error( );
}
}//кінець функції для нетермінала
Відмітимо, що до того, як зменшувати кількість синтаксичних діаграм шляхом суперпозиції одних діаграм в інші, необхідно знайти контексти виду 
для тієї синтаксичної діаграми нетермінала 
, для якої ми виконуємо операцію суперпозиції. Ці контексти ми використаємо при програмуванні синтаксичного аналізатора на основі синтаксичної діаграми, у яку підставлено синтаксичну діаграму для нетермінала .
Досить часто при визначенні синтаксису мови програмування користуються синтаксичними правилами виду 
. Тоді синтаксична діаграма буде мати вигляд:
Ai:
……. 
Мал. 8 .
Для вище наведеної синтаксичної діаграми відповідні множини будуть:
- 
для 
;
- 
для непоміченого ребра.
Відповідний фрагмент програми мовою С матиме вигляд:
extern int lexema_code;
extern char lexema_text[ ];
void Ai(void)
{ while (lexema_code= =code_ 
||
lexema_code= =code_ 
||
…
lexema_code= =code_ 
)
{// фрагмент програми для ланцюжка 
…
}
}// кінець підпрограми для нетермінала 
Виконавши аналіз варіантів побудови синтаксичного аналізатора на основі синтаксичних діаграм, покажемо вигляд основної — main-програми:
int lexema_code;
char lexema_text [500];
int main ( )
{ get_lexema ( );
Axioma_S ( );//процедура, пов'язана з аксіомою граматики
}