Повернемось до умови, при якій граматика G буде LL(k)-граматикою, а саме: для довільного виводу:
Оскільки - конструктивна множина, спробуємо побудувати всілякі множини L, які задовольняють попередньо сформульованій умові.
Означення. Множина
Алгоритм. Пошук множини
П0:
в інших випадках - невизначено.
П1:
в інших випадках - невизначено.
…. ….. ……
Пn:
в інших випадках - невизначено.
…. …. ….
Пm:
Тоді .
Виходячи з означення , умови для LL(k) -граматики будуть наступними: для довільного А -правила виду:
Як наслідок, з алгоритму пошуку видно, що
Для побудови синтаксичного аналізатора для LL(k)- граматики (k>1) необхідно побудувати множину таблиць, що забезпечать нам безтупиковий аналіз вхідного ланцюжка w (програми) за час пропорційний О(n), де n=| w |.
Побудову множини таблиць для управління LL(k)- аналізатором почнемо з таблиці, яка визначає перший крок безпосереднього виводу w в граматиці G:
Неформально, коли в магазині автомата знаходиться аксіома S, то нас цікавить перших k термінальних символів, які можна вивести з S (аксіома - поняття "програма") при умові, що після неї (програми) буде досягнуто EOF.
Імена інших таблиць Т1, Т2, … Тp визначаються так:
Наступні таблиці визначаються так:
Наступні таблиці визначаються так:
Виходячи з вищенаведеної побудови множини таблиць управління LL(k)- синтаксичним аналізатором видно, що для нетермінала Аi множина таблиць буде наступна:
Приклад. Побудувати множину таблиць управління для LL(2)-граматики з наступною схемою правил:
Для вищенаведеної граматики множини будуть такі:
,
а множини .
Побудуємо першу таблицю Для S- правила відповідні множини u будуть такі:
Таблиця T0 визначається так:
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).
П0: Прочитати k лексем з вхідного файла програми (звичайно, інколи менше ніж k). В магазин занести таблицю Т0.
…. ….
Пi: - Якщо на вершині магазина знаходиться таблиця Ti, то елемент таблиці М(Тi, <k-вхідних лексем>) визначає ланцюжок, який Ti заміщає на вершині магазина.
- Якщо на вершині магазина і перша поточна лексема з k прочитаних лексем рівна , то з вершини магазина зняти та прочитати з вхідного файла додатково одну лексему (звичайно, якщо це можливо).
- Якщо досягли кінця вхідного файла програми та магазин порожній, то програма не має синтаксичних помилок.
- В інших випадках - синтаксична помилка.