![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Скориставшись означенням -граматики, сформулюємо умови для
-граматики: граматика
буде
-граматикою тоді і тільки тоді, коли кожного А-правила виду
1.
2. якщо
Означення. Таблиця управління LL(1)-синтаксичним аналізатором визначається таким чином:
- — це номер правила виду
такого, що
- — "виштовхнути" для всіх
- — "допустити"
- в інших випадках — невизначено.
Побудуємо таблицю управління для наступної граматики:
![]() | (1) | ![]() | ![]() |
![]() | (2) | ![]() | ![]() |
![]() | (3) | ![]() | |
![]() | (4) | ||
![]() | (5) | ![]() | ![]() |
![]() | (6) | ![]() | ![]() |
![]() | (7) | ![]() | |
![]() | (8) |
Знайдемо множини .
Правило | Номер правила | ![]() |
![]() | (1) | ![]() |
![]() | (2) | ![]() |
![]() | (3) | ![]() |
![]() | (4) | ![]() |
![]() | (5) | ![]() |
![]() | (6) | ![]() |
![]() | (7) | ![]() |
![]() | (8) | ![]() |
При побудові таблиці управління
-синтаксичним аналізатором достатньо лише побудувати першу її частину, тобто
, оскільки "діагональ" таблиці
та
визначаються стандартно.
Ai\Σ | a | ( | ) | + | * | ![]() |
S | ||||||
A | ||||||
B | ||||||
C | ||||||
D |
Алгоритм. Побудова - синтаксичного аналізатора на основі таблиці управління
:
П0 Прочитаємо поточну лексему з вхідного файла, у стек магазинного автомата занесемо аксіому S.
….
Пi - Якщо на вершині стека знаходиться нетермінал , то активізувати рядок таблиці, позначений
. Елемент
визначає номер правила, права частина якого заміняє
на вершині стека.
3. Якщо на вершині стека лексема , то з вершини стека зняти
та прочитати нову поточну лексему.
4. Якщо стек порожній та досягли кінця вхідного файла, то вхідна програма синтаксично вірна.
5. В інших випадках — синтаксична помилка.
У деяких випадках досить складно (а інколи й принципово неможливо побудувати -граматику для реальної мови програмування. При цьому
-властивість задовольняється майже для всіх правил - лише декілька правил створюють конфлікт, але для цих правил задовольняється сильна
-властивість. Тоді таблиця
визначається в такий спосіб:
- виду
, такого, що
- за умови, що
.
Програма, яка виконує додатковий аналіз вхідного ланцюжка, повинна:
- прочитати додатково одну лексему;
- на основі двох вхідних лексем вибрати необхідне правило або сигналізувати про синтаксичну помилку;
- у випадку, коли правило вибрано, необхідно повернути додатково прочитану лексему у вхідний файл.
Звичайно, необхідно модифікувати алгоритм LL(1)-синтаксичного аналізатора. При цьому підпрограма аналізу конфліктної ситуації повинна додатково прочитати нову вхідну лексему, далі скориставшись контекстом з двох лексем, визначити номер правила, яке замість нетермінала на вершині стека та повернути додатково прочитану лексему у вхідний файл.
Дата публикования: 2015-04-06; Прочитано: 300 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!