Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Побудова 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-11-05; Мы поможем в написании ваших работ!; просмотров: 483 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Студент может не знать в двух случаях: не знал, или забыл. © Неизвестно
==> читать все изречения...

2782 - | 2343 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.01 с.