Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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





Дата публикования: 2015-04-06; Прочитано: 268 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...