Синтаксичний аналіз на основі -граматик
Скориставшись означенням
-граматики, сформулюємо умови для
-граматики: граматика
буде
-граматикою тоді і тільки тоді, коли кожного А-правила виду 
- 
- якщо 
Означення. Таблиця
управління LL(1)-синтаксичним аналізатором визначається таким чином:
1.
— це номер правила виду
такого, що 
2.
— "виштовхнути" для всіх 
3.
— "допустити"
4. в інших випадках
— невизначено.
Побудуємо таблицю управління для наступної граматики:
| (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 - Якщо на вершині стека знаходиться нетермінал
, то активізувати рядок таблиці, позначений
. Елемент
визначає номер правила, права частина якого заміняє
на вершині стека.
- Якщо на вершині стека лексема
, то з вершини стека зняти
та прочитати нову поточну лексему.
- Якщо стек порожній та досягли кінця вхідного файла, то вхідна програма синтаксично вірна.
- В інших випадках — синтаксична помилка.
У деяких випадках досить складно (а інколи й принципово неможливо побудувати
-граматику для реальної мови програмування. При цьому
-властивість задовольняється майже для всіх правил - лише декілька правил створюють конфлікт, але для цих правил задовольняється сильна
-властивість. Тоді таблиця
визначається в такий спосіб:
-
виду
, такого, що 
-
за умови, що
.
Програма, яка виконує додатковий аналіз вхідного ланцюжка, повинна:
- прочитати додатково одну лексему;
- на основі двох вхідних лексем вибрати необхідне правило або сигналізувати про синтаксичну помилку;
- у випадку, коли правило вибрано, необхідно повернути додатково прочитану лексему у вхідний файл.
Звичайно, необхідно модифікувати алгоритм LL(1)-синтаксичного аналізатора. При цьому підпрограма аналізу конфліктної ситуації повинна додатково прочитати нову вхідну лексему, далі скориставшись контекстом з двох лексем, визначити номер правила, яке замість нетермінала на вершині стека та повернути додатково прочитану лексему у вхідний файл.