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

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

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

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

Оскільки Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru - конструктивна множина, спробуємо побудувати всілякі множини L, які задовольняють попередньо сформульованій умові.

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

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

Алгоритм. Пошук множини Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru

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

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

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

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

…. ….. ……

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

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

…. …. ….

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

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

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

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

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

Як наслідок, з алгоритму пошуку Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru видно, що

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

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

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

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

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

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

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

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

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

Наступні таблиці Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru визначаються так:

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

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

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

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

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

Для вищенаведеної граматики множини Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru будуть такі:

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

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

Побудуємо першу таблицю Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Для S-правила відповідні множини u будуть такі:

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

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

Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru aa ab ba bb a b Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru   Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru         Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru

Нова таблиця управління Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Для A-правила відповідні множини u будуть такі:

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

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

Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru aa ab ba bb a b Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru       Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru  

Нова таблиця управління Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Для таблиці Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru та S-правила множини u будуть такі:

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

Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru aa ab ba bb a b Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru          

Наступна таблиця Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Для таблиці Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru та A-правила множини u будуть такі:

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

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

Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru aa ab ba bb a b Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru        

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

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

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

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

Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru aa ab ba bb a b Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru   Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru         Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru       Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru  
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru          
Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru Побудова LL(k)-синтаксичного аналізатора (k>1) - student2.ru        

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

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

…. ….

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

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

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

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

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