 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Синтаксичний аналіз без повернення назад
При виводу ланцюжка ω в G на кожному кроку безпосереднього виведення коли ми беремо до уваги виділений нами нетермінал (в залежності від стратегії виведення), виникає питання, яку альтернативу для 
використати. З точки зору практики, нас цікавить така стратегія виведення 
в граматиці 
, коли кожний наступний крок безпосереднього виведення наближав би нас до мети. Ця стратегія дасть можливість виконати виведення в за час пропорційний 
, де 
. Зрозуміло, що не маючи інформації про структуру , досягнути вибраної нами мети в більшості випадків неможливо. Але ж тримати інформацію про весь ланцюжок також недопустимо. З точки зору практики, отримати потрібний результат розумно при наявності локальної інформації, наприклад, 
поточних вхідних лексем програми ( — наперед фіксоване число) достатньо для організації виведення в за час пропорційний . З точки зору синтаксичного аналізу ланцюжка мова ведеться про наступну ситуацію:
S
 |  |
ω1 A ω2
 |  |
ω1 X Y
Мал. 5
Зафіксуємо стратегію виводу: далі будемо розглядати лише лівосторонню стратегію виводу в . Тоді:
- 
(
— перший зліва направо нетермінал);
- 
- термінальна частина ланцюжка , яку вже виведено (проаналізована частина ланцюжка);
- результат 
, який потрібно ще вивести, виводиться з ланцюжка 
;
- щоб зробити вірний крок виведення (без повернення назад) нам було б достатньо поточних вхідних символів з непроаналізованої частини програми .
Сформульовані нами умови забезпечує клас 
-граматик.
Означення. КС-граматика 
називається 
-граматикою для деякого фіксованого , якщо дія двох лівосторонніх виводів виду:
1) 
2) 
, для яких з 
випливає, що 
, де 
.
Неформально, граматика буде -граматикою, якщо для ланцюжка 
перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієї альтернативи виведення ланцюжка, що починається з та продовжується наступними термінальними символами.
Означення.
Сформулюємо основні твердження стосовно класу -граматик:
1) Не існує алгоритма, який перевіряє належність КС-граматики класу -граматик.
2) Існує алгоритм, який для конкретного перевіряє, чи є задана граматика -граматикою.
3) Якщо граматика є -граматикою, то вона є 
-граматикою, (
).
4) Клас -граматик — це підклас КС-граматик, який не покриває його.
Продемонструємо на прикладі справедливість твердження 4. Розглянемо граматику з наступною схемою 
:
Мова, яку породжує наведена вище граматика 
. Візьмемо виведення наступного ланцюжка 
; за означенням LL(K)-граматики 
, тоді 
маємо
Таким чином, КС-граматика не може бути -граматикою для жодного . Як результат, КС-граматика , яка має ліворекурсивний нетермінал (нетермінал називається ліворекурсивний, якщо в граматиці існує вивід виду 
), не може бути -граматикою.
З практичної точки зору в більшості випадків ми будемо користуватися 
-граматиками. У класі -граматик існує один цікавий підклас - це розподілені -граматики.
Означення. -граматика називаються розподіленою, якщо вона задовольняю наступним умовам:
- у схемі граматики відсутні 
-правила (правила виду 
);
- для нетермінала праві частини -правила починаються різними терміналами.
Для подальшого аналізу означення 
-граматики розглянемо алгоритм обчислення функції 
.
Означення: Якщо 
, то 
, де 
— бінарна операція над словарними множинами (мовами):
.
Висновок, якщо 
, де 
, тоді
Очевидно, якщо 
, то 
при 
. Розглянемо алгоритм пошуку 
Алгоритм. Пошук множини 
.
Визначимо значення функції 
для кожного 
.
П1. 
для всіх 
.
П2. 
в інших випадках - невизначено.
Пn.
в інших випадках - невизначено.
Пm. 
для всіх 
.
Очевидно, що:
- послідовність 
— монотонно зростаюча;
- 
— послідовність, обмежена зверху.
Тоді покладемо 
для кожного .
Приклад: Знайти множину Firstk(Ai) для нетерміналів граматики з наступною схемою правил:
S -> BA
A -> +BA | ε
B -> DC
C -> *DC | ε
D -> (S) | a
Нехай k=2.
| Fn\Ai | S | A | B | C | D |
| F0 | -- | { ε } | -- | { ε } | {a} |
| F1 | -- | { ε } | {a} | { ε, *a} | {a} |
| F2 | {a} | {ε, +a} | {a, a*} | { ε, *a} | {a} |
| F3 | {a, a+, a*} | {ε, +a} | {a, a*} | { ε, *a} | {a, (a} |
| F4 | {a, a+, a*} | {ε, +a} | {a, a*, (a} | { ε, *a, *(} | {a, (a} |
| F5 | {a, a+, a*, (a} | {ε, +a, +(} | {a, a*, (a} | { ε, *a, *(} | {a, (a} |
| F6 | {a, a+, a*, (a} | {ε, +a, +(} | {a, a*, (a} | { ε, *a, *(} | {a, (a, ((} |
| F7 | {a, a+, a*, (a} | {ε, +a, +(} | {a, a*, (a, ((} | { ε, *a, *(} | {a, (a, ((} |
| F8 | {a, a+, a*, (a, ((} | {ε, +a, +(} | {a, a*,(a, ((} | { ε, *a, *(} | {a, (a, ((} |
| F9 | {a, a+, a*, (a, ((} | {ε, +a, +(} | {a, a*, (a, ((} | { ε, *a, *(} | {a, (a, ((} |
Скористаємося означенням 
сформулюємо необхідні й достатні умови, за яких КС-граматика буде -граматикою:
для довільного виводу в граматиці G виду 
та правила 
:
(1)
Вище сформульована умова для -граматик може бути перефразована з урахуванням визначення множини 
:
для довільного виводу в граматиці виду та правила :
, де 
(2).
Оскільки 
, то умова (2) є конструктивною умовою і може бути використана для перевірки, чи КС-граматика є -граматикою для фіксованого .
Означення: КС-граматика називається сильною -граматикою, якщо для А -правила виду задовольняється умова:
,
де 
визначається так:
Операції та 
можна узагальнити для словарної множини 
, тоді:
.
Без доведення зафіксуємо наступні твердження:
- кожна -граматика є сильною -граматикою;
- існують -граматики (k>1), які не є сильними -граматиками.
На прикладі продемонструємо останнє твердження. Нехай граматика визначена наступними правилами:
, 
.
Відповідні множини 
, 
, 
,
.
Перевіримо умову для сильної 
-граматики:
а) виконаємо перевірку -умови для правила
б) виконаємо перевірку -умови для правила
Висновок: вище наведена граматика не є сильною -граматикою. Перевіримо цю ж граматику на властивість -граматики. Тут ми маємо два різні варіанти виводу з S:
а) 
б) 
Висновок: наведена вище граматика є -граматикою.
Алгоритм. Обчислення 
.
Для побудови алгоритму пошуку множини розглянемо наступні приклади на синтаксичному дереві, які дозволять перейти до узагальнень.Подивимося на синтаксичне дерево висоти 1 для правила 
S
ω1 A ω2
Мал. 6
Тоді 
.
Далі розглянемо дерево висоти 2:
S
 |
ω1 AJ ω2
 |  |
ω3 A ω4
Мал. 7.
Тоді 
. В силу вищесказаного, будемо знаходити значення функції 
, тобто будемо розглядати всілякі дерева, які можна побудувати, починаючи з аксіоми 
.
П0. 
. Очевидно, за 0 кроків ми виведемо S, після якої знаходиться . У інших випадках 
— невизначено 
.
П1. 
. В інших випадках 
— невизначено.
….
Пn 
. В інших випадках 
— невизначено.
….
Настане крок Пm, коли 
, 
.
Тоді покладемо 
для кожного .
Очевидно, що:
- послідовність 
монотонно зростаюча;
- 
послідовність обмежена зверху.
До того, як перевірити граматику на -властивість необхідно перевірити її на наявність ліворекурсивних нетерміналів та спробувати уникнути лівої рекурсії.
Означення: Нетермінал КС-граматики називається -нетерміналом, якщо 
.
Алгоритм. Пошук -нетерміналів:
….
…. Пn
Тоді множина 
— множина -нетерміналів.
Приклад. Для граматики G з схемою правил Р знайдемо множину -нетерміналів:
= 
Таким чином, множина -нетерміналів для наведеної вище граматики - 
Алгоритм. Тестування нетермінала на ліву рекурсію. Для кожного нетермінала Аi побудуємо наступну послідовність множин S0, S1, ….
, починаємо з нетерміналу Аi.
….
….
Тоді якщо 
, то — ліворекурсивний нетермінал.
Приклад. Для граматики G з схемою правил Р знайдемо множину ліворекурсивних нетерміналів:
1. Виконаємо процедуру тестування для кожного нетермінала окремо:
- наприклад, для нетермінала S:
Запропонуємо декілька прийомів, що дають можливість при побудові 
граматик уникнути лівої рекурсії. Розглянемо граматику зі схемою правил , яка має ліворекурсивний нетермінал . Замінимо схему правил новою схемою з трьома правилами
.
Приклад: Для граматики G з схемою правил Р для кожного нетермінала знайдемо множину 
(k =1):
S -> BA
A -> +BA | ε
B -> DC
C -> *DC | ε
D -> (S) | a
З прикладу, що наведено раніше множини First1(A),будуть такими:
First1(S)= First1(B)= First1(D)={(,a}, First1(A)={+, ε }, First1(C)={*, ε }.
| δn\Ai | S | A | B | C | D |
| δ0 | { ε } | -- | -- | -- | -- |
| δ 1 | { ε } | { ε } | {+, ε } | -- | -- |
| δ 2 | { ε } | {ε} | {+, ε } | {+, ε } | |
| δ 3 | { ε } | {ε} | {+, ε } | {+, ε } | {*, +, ε } |
| δ 4 | { ε,) } | {ε} | {+, ε } | {+, ε } | {*, +, ε } |
| δ 5 | { ε,) } | {ε,)} | {+, ε } | {+, ε,)} | {*, +, ε } |
| δ 6 | { ε,) } | {ε,)} | {+, ε,)} | {+, ε } | {*, +, ε,)} |
| δ 7 | { ε,) } | {ε,)} | {+, ε,)} | {+, ε,)} | {*, +, ε,)} |
Таким чином, Follow1(S) = { ε,) }, Follow1(A) = {ε,)}, Follow1(B) = {+, ε,)}, Follow1(C) = {+, ε,)}, Follow1(D) = {*, +, ε,)}.
3.3. Синтаксичний аналіз на основі -граматик
Скориставшись означенням -граматики, сформулюємо умови для -граматики: граматика буде -граматикою тоді і тільки тоді, коли кожного А-правила виду 
- 
- якщо 
Означення. Таблиця 
управління 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)-синтаксичного аналізатора. При цьому підпрограма аналізу конфліктної ситуації повинна додатково прочитати нову вхідну лексему, далі скориставшись контекстом з двох лексем, визначити номер правила, яке замість нетермінала на вершині стека та повернути додатково прочитану лексему у вхідний файл.
Поиск по сайту: