АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Синтаксичний аналіз без повернення назад

Читайте также:
  1. Ad fontes — Назад к источникам
  2. D. Аналізатор спектру шуму
  3. FTA – Аналіз «дерева відмов».
  4. LL(1)-синтаксичний аналізатор для мови Pascal
  5. SWOT-аналіз підприємства та складання профілю середовища.
  6. А. Макроаналіз по виду зламів.
  7. Алонж аналіз
  8. Альтернативний аналіз (Alternative Analysis)
  9. Аналіз алгоритмів
  10. Аналіз асортименту і структури продукції.
  11. Аналіз беззбитковості
  12. АНАЛІЗ БІОСИГНАЛІВ

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.046 сек.)