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

При виводу ланцюжка ω в G на кожному кроку безпосереднього виведення коли ми беремо до уваги виділений нами нетермінал (в залежності від стратегії виведення), виникає питання, яку альтернативу для використати. З точки зору практики, нас цікавить така стратегія виведення в граматиці , коли кожний наступний крок безпосереднього виведення наближав би нас до мети. Ця стратегія дасть можливість виконати виведення в за час пропорційний , де . Зрозуміло, що не маючи інформації про структуру , досягнути вибраної нами мети в більшості випадків неможливо. Але ж тримати інформацію про весь ланцюжок також недопустимо. З точки зору практики, отримати потрібний результат розумно при наявності локальної інформації, наприклад, поточних вхідних лексем програми ( — наперед фіксоване число) достатньо для організації виведення в за час пропорційний . З точки зору синтаксичного аналізу ланцюжка мова ведеться про наступну ситуацію:

S

ω₁ A ω₂

ω_{1 X Y}

Мал. 5

Зафіксуємо стратегію виводу: далі будемо розглядати лише лівосторонню стратегію виводу в . Тоді:

- ( — перший зліва направо нетермінал);

- - термінальна частина ланцюжка , яку вже виведено (проаналізована частина ланцюжка);

- результат , який потрібно ще вивести, виводиться з ланцюжка ;

- щоб зробити вірний крок виведення (без повернення назад) нам було б достатньо поточних вхідних символів з непроаналізованої частини програми .

Сформульовані нами умови забезпечує клас -граматик.

Означення. КС-граматика називається -граматикою для деякого фіксованого , якщо дія двох лівосторонніх виводів виду:

1)

2) , для яких з випливає, що , де .

Неформально, граматика буде -граматикою, якщо для ланцюжка перших символів (за умови, що вони існують) решти непроаналізованого ланцюжка визначають, що з існує не більше однієї альтернативи виведення ланцюжка, що починається з та продовжується наступними термінальними символами.

Означення.

Сформулюємо основні твердження стосовно класу -граматик:

1) Не існує алгоритма, який перевіряє належність КС-граматики класу -граматик.

2) Існує алгоритм, який для конкретного перевіряє, чи є задана граматика -граматикою.

3) Якщо граматика є -граматикою, то вона є -граматикою, ( ).

4) Клас -граматик — це підклас КС-граматик, який не покриває його.

Продемонструємо на прикладі справедливість твердження 4. Розглянемо граматику з наступною схемою :

Мова, яку породжує наведена вище граматика . Візьмемо виведення наступного ланцюжка ; за означенням LL(K)-граматики , тоді маємо

Таким чином, КС-граматика не може бути -граматикою для жодного . Як результат, КС-граматика , яка має ліворекурсивний нетермінал ( нетермінал називається ліворекурсивний, якщо в граматиці існує вивід виду ), не може бути -граматикою.

З практичної точки зору в більшості випадків ми будемо користуватися -граматиками. У класі -граматик існує один цікавий підклас - це розподілені -граматики.

Означення. -граматика називаються розподіленою, якщо вона задовольняю наступним умовам:

- у схемі граматики відсутні -правила (правила виду );

- для нетермінала праві частини -правила починаються різними терміналами.

Для подальшого аналізу означення -граматики розглянемо алгоритм обчислення функції .

Означення: Якщо , то , де — бінарна операція над словарними множинами (мовами):

.

Висновок, якщо , де , тоді

Очевидно, якщо , то при . Розглянемо алгоритм пошуку

Алгоритм. Пошук множини .

Визначимо значення функції для кожного .

П₁. для всіх .

П₂.

в інших випадках - невизначено.

П_n.

в інших випадках - невизначено.

П_m. для всіх .

Очевидно, що:

- послідовність — монотонно зростаюча;

- — послідовність, обмежена зверху.

Тоді покладемо для кожного .

Приклад: Знайти множину First_k(A_i) для нетерміналів граматики з наступною схемою правил:

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

ω₁ A ω₂

Мал. 6

Тоді .

Далі розглянемо дерево висоти 2:

S

ω₁ A_J ω₂

ω₃ A ω₄

Мал. 7.

Тоді . В силу вищесказаного, будемо знаходити значення функції , тобто будемо розглядати всілякі дерева, які можна побудувати, починаючи з аксіоми .

П₀. . Очевидно, за 0 кроків ми виведемо S, після якої знаходиться . У інших випадках — невизначено .

П₁. . В інших випадках — невизначено.

….

П_n . В інших випадках — невизначено.

….

Настане крок П_m, коли , .

Тоді покладемо для кожного .

Очевидно, що:

- послідовність монотонно зростаюча;

- послідовність обмежена зверху.

До того, як перевірити граматику на -властивість необхідно перевірити її на наявність ліворекурсивних нетерміналів та спробувати уникнути лівої рекурсії.

Означення: Нетермінал КС-граматики називається -нетерміналом, якщо .

Алгоритм.Пошук -нетерміналів:

….

…. П_n

Тоді множина — множина -нетерміналів.

Приклад. Для граматики G з схемою правил Р знайдемо множину -нетерміналів:

=

Таким чином, множина -нетерміналів для наведеної вище граматики -

Алгоритм.Тестування нетермінала на ліву рекурсію. Для кожного нетермінала А_i побудуємо наступну послідовність множин S₀, S₁, ….

, починаємо з нетерміналу А_i.

….

….

Тоді якщо , то — ліворекурсивний нетермінал.

Приклад. Для граматики G з схемою правил Р знайдемо множину ліворекурсивних нетерміналів:

1. Виконаємо процедуру тестування для кожного нетермінала окремо:

- наприклад, для нетермінала S:

Запропонуємо декілька прийомів, що дають можливість при побудові граматик уникнути лівої рекурсії. Розглянемо граматику зі схемою правил , яка має ліворекурсивний нетермінал . Замінимо схему правил новою схемою з трьома правилами

.

Приклад: Для граматики G з схемою правил Р для кожного нетермінала знайдемо множину (k=1):

S -> BA

A -> +BA | ε

B -> DC

C -> *DC | ε

D -> (S) | a

З прикладу, що наведено раніше множини First₁(A) ,будуть такими:

First₁(S)= First₁(B)= First₁(D)={(,a}, First₁(A)={+, ε }, First₁(C)={*, ε }.

δn\Ai	S	A	B	C	D
δ0	{ ε }	--	--	--	--
δ 1	{ ε }	{ ε }	{+, ε }	--	--
δ 2	{ ε }	{ε}	{+, ε }	{+, ε }
δ 3	{ ε }	{ε}	{+, ε }	{+, ε }	{*, +, ε }
δ 4	{ ε, ) }	{ε}	{+, ε }	{+, ε }	{*, +, ε }
δ 5	{ ε, ) }	{ε, )}	{+, ε }	{+, ε, )}	{*, +, ε }
δ 6	{ ε, ) }	{ε, )}	{+, ε , )}	{+, ε }	{*, +, ε , )}
δ 7	{ ε, ) }	{ε, )}	{+, ε , )}	{+, ε , )}	{*, +, ε , )}

Таким чином, Follow₁(S)= { ε, ) }, Follow₁(A)= {ε, )}, Follow₁(B)= {+, ε, )}, Follow₁(C)= {+, ε , )}, Follow₁(D)= {*, +, ε , )}.