Побудова 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 прочитаних лексем рівна , то з вершини магазина зняти та прочитати з вхідного файла додатково одну лексему (звичайно, якщо це можливо).

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

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