Лекции.Орг


Поиск:




Категории:

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

 

 

 

 


Синтаксичний аналіз на основі -граматик




Скориставшись означенням -граматики, сформулюємо умови для -граматики: граматика буде -граматикою тоді і тільки тоді, коли кожного А-правила виду

-

- якщо

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

 





Поделиться с друзьями:


Дата добавления: 2015-11-05; Мы поможем в написании ваших работ!; просмотров: 407 | Нарушение авторских прав


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

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

Жизнь - это то, что с тобой происходит, пока ты строишь планы. © Джон Леннон
==> читать все изречения...

2295 - | 2065 -


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

Ген: 0.012 с.