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

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

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

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

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

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

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

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

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

П2. Для кожного елемента ланцюжка Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru будуємо ребро синтаксичного графа та покажемо його таким чином що:

- якщо Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru , де Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru — вихідна лексема, то будуємо таке ребро

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

Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru (1)

Мал.1.

- якщо Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru — нетермінал граматики , то будуємо таке ребро

Ai  
Ai
(2)

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

Мал.2 .

Тоді, коли правило граматики Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru має вигляд Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru для побудови діаграми скористаємося способами (1) та (2):

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

Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Ai:

Коли правило граматики Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru має вигляд Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru , то відповідний синтаксичний граф буде мати вигляд:

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

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

….. …… ……

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

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

Мал. 3.

де замість Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru будуються відповідні синтаксичні діаграми.

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

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

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

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

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

Мал.4.

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

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

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

if (lexema_code==code_x) get_lexema( );

else error( );

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

Ai

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

Мал.5.

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

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

f_Ai( );

// побудованої для нетермінала Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru .

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

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

Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru 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( );

}

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

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

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

….. …… ……

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

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

Мал.7.

для кожного Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru знайдемо такі множини:

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

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

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

Нехай ми знайшли відповідні множини для кожного Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

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

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

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

Оскільки за умовою Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru , то відповідний фрагмент програми на мові С матиме вигляд:

extern int lexema_code;

extern char lexema_text[ ];

…. ….

void Ai (void)

{switch(lexema_code)

{case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :// фрагмент програми для Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru

break;

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :// фрагмент програми для Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru

break;

… …. ….

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :

case code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru :// фрагмент програми для Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru

break;

default: error( );

}

}//кінець функції для нетермінала Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru

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

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

Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru Ai:

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

Мал. 8 .

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

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

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

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

extern int lexema_code;

extern char lexema_text[ ];

void Ai(void)

{ while (lexema_code= =code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru ||

lexema_code= =code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru ||

lexema_code= =code_ Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru )

{// фрагмент програми для ланцюжка Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru

}

}// кінець підпрограми для нетермінала Метод рекурсивного спуску програмування синтаксичних аналізаторів - student2.ru

Виконавши аналіз варіантів побудови синтаксичного аналізатора на основі синтаксичних діаграм, покажемо вигляд основної — main-програми:

int lexema_code;

char lexema_text [500];

int main ( )

{ get_lexema ( );

Axioma_S ( );//процедура, пов'язана з аксіомою граматики

}

Наши рекомендации