LL (k) - граматики.


Визначення LL (k)-граматик.
Для початку припустимо, що G = (N, E, P, S) - однозначна граматика і w = a1, a2 ... an
- Ланцюжок з L (G). Тоді існує єдина послідовність
левовиводімих ланцюжків b0, b1 .. bm, для якої S = b0, bi, pi Ю bi 1 при 0
= E. Так як b `№ c`, то G не LL (k) - граматика.
Достатність. Припустимо, що G не LL (k) - граматика. Тоді знайдуться такі два
виведення SЮwAa `Юwb` a `Юwx і SЮwAa` Юwc `a` Юwy, що ланцюжки x і y збігаються в першу k
позиціях, але b `№ c`. Тому A ® b `і A ® c` - різні правила з P і кожне з
множин FIRST (b `a`) і FIRST (c `a`) містить ланцюжок FIRST (x) збігається з
FIRST (y). ЧТД.
ПЗМ: Граматика G з правила S ® aSa, не буде LL (1) - граматикою, тому що
FIRST1 (aS) = FIRST1 (a) = a. Це можна пояснити так - бачачи тільки перший символ
ланцюжка ми не можемо визначити який правило необхідно застосувати (ліве або
праве). З іншого боку ця граматика є LL2 (k) граматикою - що
цілком очевидно.
ОПР: Нехай G = (N, E, P, S) - КС-граматика. Визначимо FOLLOWk (b `) як безліч
термінальних символів, які можуть зустрічатися після нетемінала, що є
аргументом функції.
ТРМ: КС-граматика G = (N, E, P, S) є LL (1)-граматикою тоді і тільки тоді,
коли для двох різних правил A ® b `і A ® c` перетин FIRST1 (b `
FOLLOW1 (A)) ЗFIRST1 (c `FOLLOW1 (A)) пусто при всіх AОN. (Без ДКВ).
Теорему можна сформулювати так: по першому символу після нетермінала
необхідно вибрати застосовне правило - отже ці символи різні і
перетин порожньо. Ця теорема може застосовуватися до LL (k) - граматики, але не
завжди виконуватися. Граматики для яких виконується теорема називаються
сильними, таким чином всі LL (1) граматики - сильні. Необхідно так само
помітити що кожна LL (k) - граматика однозначна, тому якщо є
неоднозначна граматика - то вона не LL (k). Є нерозв'язна проблема
розпізнавання, чи існує для даної КС-граматики G, що не є LL (k),
еквівалентна їй LL (k) - граматика. Проте у ряді випадків таке перетворення
можливо. Застосовується два способи:
Перший спосіб - усунення лівої рекурсії.
ПЗМ: Нехай G - граматика S ® Sab яка не є LL-граматикою. Замінимо
правила на наступні:
S ® bS `
S `® aS` e
отримавши при цьому еквівалентну LL (1) - граматику.
Інший спосіб - ліва факторизація.
ПЗМ: Розглянемо LL (2) - граматику G з двома правилами S ® aSa. У цих двох
правилах "вліво винесемо за дужки" символ a, записав їх у вигляді S ® a (Se). Іншими
словами, ми вважаємо що операція конкатенації дистрибутивність щодо
операції вибору альтернативи (позначається вертикальною рискою). Замінимо ці
правила на:
S ® aA
A ® Se
тим самим отримаємо еквівалентну LL (1)-граматику.


Розбір для LL (1) - граматик.
Ядром пророкує алгоритму є управляюча таблиця. У цьому і
наступних розділах буде показано як побудувати коректну керуючу таблицю.
Алг 1: Керуюча таблиця для LL (1)-граматики.
Вхід: LL (1) - граматика.
Вихід: Коректна керуюча таблиця.
Метод: Будемо вважати, що $-маркер дна магазину. Таблиця визначається наступним
чином:

Якщо A ® a `- правило з P з номером i, то M [A, a] = (a`, i) для всіх a № e,
належать FIRST1 (a `). Якщо eОFIRST1 (a `), то M [A, b] = (a`, i) для всіх
bОFOLLOW1 (A).

M [a, a] = викид для всіх aОE.

M [$, e] = допуск.

У решті випадків M [X, a] = помилка для XОNІEІ ($) і aОEІ (e).

ТРМ: Запропонований алгоритм будує коректну керуючу таблицю для LL (1) -
граматики G.

Розбір для LL (k) - граматик.
Побудуємо керуючу таблицю для довільної граматики. Якщо граматика
сильна, то можна застосувати попередній алгоритм з аванцепочкамі розширеними до
k символів. В іншому випадку виникає кілька проблем. У 1-м
пророкує алгоритмі розбору в магазин містилися тільки символи з EІN і
виявлялося, що для однозначного визначення чергового застосовуваного правила
досить знати нетермінальний символ нагорі магазину і поточний вхідний
символ. Для не сильних граматик цього може виявитися недостатньо.
ПЗМ: Візьмемо граматику
S ® aAaabAba
A ® be
Якщо дані нетермінал A і аванцепочка ba, то не відомо, яке з правил треба
застосувати.
Невизначеності такого роду однак можна дозволити, зв'язавши з кожним
нетерміналом і частиною левовиводімой ланцюжка (яка може виявитися праворуч),
спеціальний символ, званий LL (k) - таблицею. По даній аванцепочке LL (k) -
табліцабудет однозначно визначати яке правило треба застосувати на черговому
кроці виводу.
ОПР: Нехай E - деякий алфавіт. Якщо L1 і L2 - підмножини E, то покладемо L1
Еk L2 = (
w для деяких xОL1 і yОL2
або w = xy, якщо xy Јk
або w складається з першого k символів ланцюжка xy
)
ЛМА: Для будь-якої КС-граматики G = (N, E, P, S) і будь-яких a `, b` О (NІE):

FIRSTk (a `b`) = FIRSTk (a `) Еk FIRSTk (b`)

ОПР: Нехай G = (N, E, P, S) - КС-граматика. Для кожних AОN і LНE визначимо LL (k) -
таблицю Ta, l, відповідну A і L, як функцію T (u), значенням якої служить
:

= помилка, якщо в P немає такого правила A ® a `, що FIRSTk (a`) Еk L містить u;

= (A ® a `,), якщо A ® a` - єдине правило з P, для якого
FIRSTk (a `) Еk L містить u;

не визначено, якщо в множині знайдуться два і більше правила (цю ситуацію
називають конфліктом між правилами)

На нормальною мовою це означає що виробляється значення помилка, якщо u
взагалі не є ланцюжком граматики, повертається правило якщо воно існує
і тільки одне і якщо кілька правил - то значення не визначається.
Алг 2: Побудова LL (k) - таблиць.
Вхід: LL (k) - граматика G = (N, E, P, S).
Вихід: Безліч TG LL (k) - таблиць, необхідних для побудови управляючої
таблиці для G.
Метод:

Побудувати LL (k) - таблицю T0, відповідну S і (e).

Покласти спочатку TG = (T0).

Для кожної LL (k)-таблиці TОTG, що містить елемент
T (u) = (A ® x0B1x1 ... Bmxm,) включити в TG LL (k) - таблицю T для 1ЈiЈm,
якщо T ще не входить до TG.

Повторювати крок 3 поки в TG можна включати нові таблиці.

ПЗМ: Побудуємо відповідне безліч LL (2) - таблиць для граматики S ® aAaabAba
і A ® be. Почнемо з TG = (TS, (e)). Так як TS, (e) (aa) = (S ® aAaa, (aa)), то в TG треба
включити TA, (aa). Аналогічно, так як T0 (bb) = (S ® bAba, (ba)), то в TG потрібно так
ж включити. (Елементи LL (2) - таблиць TA, (aa) і TA, (ba), відмінні від значення
помилка, наведено в таблиці нижче). Зараз TG = (TS, (e), TA, (aa), TA, (ba)), і
алгоритм вже не може включити в TG нових таблиць, так що це три LL (2) - таблиці
утворюють безліч відповідне граматиці.
TA, (aa) TA, (ba)
uправіломножестваuправіломножества
baA ® b-baA ® e-
aaA ® e-aaA ® b-
Тепер дамо алгоритм, яким можна побудувати коректну керуючу таблицю по
відповідному безлічі LL (k) - таблиць. Керований цією таблицею k-
пророкує алгоритм буде як магазинних символів вживати замість
нетерміналов LL (k) - таблиці.
Алг 3: Побудова керуючої таблиці для LL (k) - граматики.
Вхід: LL (k) - граматика і відповідне безліч TG LL (k) - таблиць.
Вихід: Коректна керуюча таблиця M для G.
Метод: M визначається на множині (TGІEІ ($)) ґE * k наступним чином:

Якщо A ® x0B1x1 ... Bmxm - правило з P з номером i і TA, LОTG, то для всіх u, для
яких TA, L (u) = (A ® x0B1x1 ... Bmxm,) вважаємо
M [TA, L, u] = (x0TB1, Y1 ... TBm, Ymxm, i).

M [a, av] = викид для всіх vОE * (k-1).

M [$, e] = допуск.

У решті випадків M [X, u] = помилка

TS, (e) - початкова таблиця.



ПЗМ: Побудуємо керуючу таблицю для LL (2) - граматики

S ® aAaa

S ® bAba

A ® b

A ® e

використовуючи відповідне їй безліч LL (2)-таблиць, знайдене в попередньому
прикладі. Алгоритм повинен видати таблицю:
aaabababbbe
T0aT1aa, 1aT1aa, 1bT2ba, 2
T1e, 4b, 3
T2 e, 4b, 3
aвибросвибросвиброс
b вибросвибросвиброс
$ допуск *
де T0 = TS, (e), T1 = TA, (aa) і T2 = TA, (ba). Мається на увазі, що в порожніх осередках -
помилка. Допуск * знаходиться в останній колонці. Для вхідних ланцюжка bba
2-який пророкує алгоритм видасть таку послідовність тактів:
(bba, T0 $, e) - (bba, bT2ba $, 2)

(ba, T2ba $, 2)

(ba, ba $, 24)

(a, a $, 24)

(e, $, 24)

ТРМ: Описаний алгоритм будує для LL (k) - граматики G = (N, E, P, S) коректну
таблицю, що керує роботою відповідного k-який пророкує алгоритму.
ПЗМ: Розглянемо LL (2) - граматику G з правилами:

S ® e

S ® abA

A ® Saa

A ® b

Побудуємо відповідні LL (2)-таблиці. Почнемо з T0 = TS, (e). Потім по T0 знайдемо
T1 = TA, (e), далі T2 = TS, (aa) і T3 = TA, (aa):

T0T2
uправіломножестваuправіломножества
eS ® e-aaS ® e-
abS ® abA (e) abS ® abA (aa)

T1T3
uправіломножества uправіломножества
bA ® b-aaA ® Saa (aa)
aaA ® Saa (aa) abA ® Saa (aa)
abA ® Saa (aa) baA ® b-


По цим таблицям побудуємо керуючу таблицю:
 aaabababbbe
T0 abT1, 2e, 1
T1T2aa, 3T2aa, 3b, 4
T2e, 1abT3, 2
T3T2aa, 3T2aa, 3 b, 4
aвибросвибросвиброс
b вибросвибросвиброс
$ допуск


Алгоритм побудований за таблицею розбере ланцюжок abaa наступним чином:
(abaa, T0 $, e) - (abaa, abT1 $, 2)
- (Baa, bT1 $, 2)
- (Aa, T1 $, 2)
- (Aa, T2aa $, 23)
- (Aa, aa $, 231)
- (A, a $, 231)
- (E, $, 231)
ТРМ: Число кроків, які виконуються k-пророкує алгоритмом з керуючою
таблицею, побудованої попереднім алгоритмом за LL (k) - граматики G, лінійно
завісітот n, де n - довжина вхідної ланцюжка.

Перевірка LL (k) - умови.
По відношенню до довільної даній граматиці G виникає ряд природних
питань:

Чи є G LL (k) - граматикою для даного k?

Чи існує таке k, що G - LL (k) - граматика?

Так як для LL (1) ліві розбори будуються особливо просто, то якщо G не LL (1) -
граматика, то чи існує еквівалентна їй LL (1) - граматика G ', для
якої L (G) = L (G ')?

На жаль, тільки для першого питання є що відповідає на нього алгоритм. Можна
показати, що другий і третій проблеми алгоритмічно нерозв'язних, але це
доказ не наводиться. Наведемо алгоритм перевірки LL (k) - умови:
Алг 4: Перевірка LL (k) - умови.
Вхід: КС-граматика G = (N, E, P, S) і ціле число k.
Вихід: "Так" - якщо G - LL (k) - граматика і "Ні" в іншому випадку.
Метод:
Суть алгоритму зводиться до наступного: Для кожного нетермінала, що має дві або
більш правила розкрутки обчислюється перетин перших k-символів всіх
можливих ланцюжків розкрутки. Якщо це безліч пусто, то переходять до наступного
терміналу, інакше закінчують зі значенням "Ні". Якщо все перетину порожні -
закінчують зі значенням "Так". Для отримання перетину двох правил можна
скористатися записом: (FIRSTk (b `) ЕkL) З (FIRSTk (c`) ЕkL), де L = FIRSTk (a `) і
a `- ланцюжок символів після терміналу.