Метод рекурсивного спуску програмування синтаксичних аналізаторів

Означення. Синтаксична діаграма — це орієнтований граф, дуги котрого позначені елементами . Синтаксична діаграма будується для кожного А -правила КС-граматики мови програмування.

Оскільки вершини такого графа не іменуються, то вони припускаються неявно. Синтаксична діаграма позначається іменем нетермінала, для якого вона будується.

Мета побудови синтаксичних діаграм для мови програмування на основі КС-граматики:

- для кожного А -правила КС-граматики будується синтаксична діаграма;

- на основі побудови синтаксичної діаграми для деякого нетермінала будуємо підпрограму, яка аналізує ту частину головної програми, яку вона визначає.

Оскільки у більшості випадків при визначенні синтаксису мови програмування ми користуємося множиною рекурсивних правил, то серед підпрограм, які будуються на основі правил граматики, будуть і рекурсивні процедури (рекурсія буде як явна, так і неявна).

Сформулюємо правила побудови синтаксичного графа:

П₁. Кожен нетермінал з відповідною множиною породжуючих правил відображається в один синтаксичний граф. Отже, кількість синтаксичних графів рівна кількості нетерміналів граматики .

П₂. Для кожного елемента ланцюжка будуємо ребро синтаксичного графа та покажемо його таким чином що:

- якщо , де — вихідна лексема, то будуємо таке ребро

(1)

Мал.1.

- якщо — нетермінал граматики, то будуємо таке ребро

Мал.2.

Тоді, коли правило граматики має вигляд для побудови діаграми скористаємося способами (1) та (2):

A_i:

Коли правило граматики має вигляд , то відповідний синтаксичний граф буде мати вигляд:

….. …… ……

….. …… ……

Мал. 3.

де замість будуються відповідні синтаксичні діаграми.

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

- для кожного правила виду з синтаксичною діаграмою виду (3) необхідне виконання наступної умови: множини повинні попарно не перетинатися. Зрозуміло, що ця умова гарантує детермінований вибір шляху при русі по синтаксичній діаграмі. Подальше програмування синтаксичного аналізатора можна звести до наступних примітивів:

- для фрагмента синтаксичної діаграми виду

Мал.4.

відповідний фрагмент програми (наприклад, мовою С) матиме вигляд:

extern int lexema_code;// код лексеми, яку виділив сканер

extern char lexema_text[ ];// текст лексеми

…

if (lexema_code==code_x) get_lexema();

else error();

- для фрагмента синтаксичної діаграми виду

Мал.5.

відповідний фрагмент програми матиме вигляд:

//виклик функції, яка побудована для синтаксичної діаграми

f_Ai();

// побудованої для нетермінала .

- Для послідовності елементів синтаксичної діаграми виду

A_i:

Мал.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();

}

}//кінець функції для нетермінала

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

Досить часто при визначенні синтаксису мови програмування користуються синтаксичними правилами виду . Тоді синтаксична діаграма буде мати вигляд:

A_i:

…….

Мал. 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 ();//процедура, пов'язана з аксіомою граматики

}

3.6. Побудова LL(k)-синтаксичного аналізатора (k>1).

Повернемось до умови, при якій граматика G буде LL(k)-граматикою, а саме: для довільного виводу:

Оскільки - конструктивна множина, спробуємо побудувати всілякі множини L, які задовольняють попередньо сформульованій умові.

Означення. Множина

Алгоритм. Пошук множини

П₀:

в інших випадках - невизначено.

П₁:

в інших випадках - невизначено.

…. ….. ……

П_n:

в інших випадках - невизначено.

…. …. ….

П_m:

Тоді .

Виходячи з означення , умови для LL(k) -граматики будуть наступними: для довільного А -правила виду:

Як наслідок, з алгоритму пошуку видно, що

Для побудови синтаксичного аналізатора для LL(k)- граматики (k>1) необхідно побудувати множину таблиць, що забезпечать нам безтупиковий аналіз вхідного ланцюжка w (програми) за час пропорційний О(n), де n=| w |.

Побудову множини таблиць для управління LL(k)- аналізатором почнемо з таблиці, яка визначає перший крок безпосереднього виводу w в граматиці G:

Неформально, коли в магазині автомата знаходиться аксіома S, то нас цікавить перших k термінальних символів, які можна вивести з S (аксіома - поняття "програма") при умові, що після неї (програми) буде досягнуто EOF.

Імена інших таблиць Т₁, Т₂, … Т_p визначаються так:

Наступні таблиці визначаються так:

Наступні таблиці визначаються так:

Виходячи з вищенаведеної побудови множини таблиць управління LL(k)- синтаксичним аналізатором видно, що для нетермінала А_i множина таблиць буде наступна:

Приклад. Побудувати множину таблиць управління для LL(2)-граматики з наступною схемою правил:

Для вищенаведеної граматики множини будуть такі:

,

а множини .

Побудуємо першу таблицю Для S- правила відповідні множини u будуть такі:

Таблиця T₀ визначається так:

	aa	ab	ba	bb	a	b

Нова таблиця управління Для A- правила відповідні множини u будуть такі:

	aa	ab	ba	bb	a	b

Нова таблиця управління Для таблиці та S -правила множини u будуть такі:

	aa	ab	ba	bb	a	b

Наступна таблиця Для таблиці та A-правила множини u будуть такі:

	aa	ab	ba	bb	a	b

Нова таблиця

Ми визначили чотири таблиці-рядки (а їх кількість для довільної LL(k)- граматики визначається так:

Об'єднаємо рядки-таблиці в єдину таблицю та виконаємо перейменування рядків:

	aa	ab	ba	bb	a	b

Алгоритм. Синтаксичний аналізатор для LL(k) -граматики (k>1).

П₀: Прочитати k лексем з вхідного файла програми (звичайно, інколи менше ніж k). В магазин занести таблицю Т₀.

…. ….

П_i: - Якщо на вершині магазина знаходиться таблиця T_i, то елемент таблиці М(Т_i, <k-вхідних лексем>) визначає ланцюжок, який T_i заміщає на вершині магазина.

- Якщо на вершині магазина і перша поточна лексема з k прочитаних лексем рівна , то з вершини магазина зняти та прочитати з вхідного файла додатково одну лексему (звичайно, якщо це можливо).

- Якщо досягли кінця вхідного файла програми та магазин порожній, то програма не має синтаксичних помилок.

- В інших випадках - синтаксична помилка.

Поиск по сайту: