Визначення LL (k)-граматик.
Для початку припустимо, що G = (N, E, P, S) - однозначна граматика і w = a1, a2 ... an - ланцюжок з L (G). Тоді існує єдина послідовність левовиводімих ланцюжків b0, b1 .. bm, для якої S = b0, bi, pi ==> bi +1 при 0wAa `==> wb` a `==> wx
(2) S ==> wAa `==> wc` a `==> wy
для яких FIRST (x) = FIRST (y), випливає що b `= c`.
Інакше це визначення виражає те, що для наявної ланцюжка і знаючи наступні k символів можна застосувати не більше одного правила виводу. Граматика називається LL-граматикою, якщо вона LL (k) - граматика для деякого k.
ПЗМ: Нехай G складається з правил S? AAS | b, A? A | bSA. Інтуїтивно G є LL (1) - граматикою, тому що, якщо дан найлівіший нетермінал С в левовиводімой ланцюжку і наступний вхідний символ с, існує не більше одного правила, що застосовується до С і що приводить до термінальної ланцюжку, що починається символом с. Переходячи до визначення LL (1) - граматики, ми бачимо, що якщо S ==> wSa `==> wb` a `==> wx і S ==> wSa` ==> wc `a` ==> wy та ланцюжки x і y починаються одним і тим же символом, то повинно бути b `= c`. В даному випадку якщо x і y починаються символом a, то у висновку брало участь правило S? AAS і b `= c` = aAS. Альтернатива S? B тут неможлива. З іншого боку, якщо x і y починаються з b, то повинно застосовуватися правило S? B і b `= c` = b. Зауважимо, що випадок x = y = e тут неможливий, так як з S у граматиці G не виводиться e.
Коли розглядаються два висновки S ==> wAa `==> wc` a `==> wy міркування аналогічно. Граматика G є прикладом так званої простої LL (1) - граматики (або розділеної граматики).
ОПР: КС-граматика G = (N, E, P, S) без e-правил називається простий LL (k) - граматикою (або розділеної граматикою), якщо для кожного A? N всі його альтернативи починаються різними термінальними символами.
Пророкує алгоритми розбору.
Розбір для LL (k)-граматики дуже зручно здійснювати за допомогою так званого k-який пророкує алгоритму розбору. k-який пророкує алгоритм використовує вхідну стрічку, магазин і вихідну стрічку. Алгоритм намагається простежити висновок ланцюжка, збережені на його вхідний стрічці. При читанні аналізованої ланцюжка вхідна головка може «заглядати» вперед на чергові k символу. Ці символи називають аванцепочкой. Алгоритм має конфігурацію що представляється трійкою (x, Xa, n), де
x - невикористана частина вхідний ланцюжка
Xa - ланцюжок у магазині і Х - верхній символ
n - ланцюжок на вихідний стрічці
Роботою k-який пророкує алгоритму керує керуюча таблиця, яка задає відповідність між безліччю
((верхній символ магазину) Х (аванцепочка))
і безліччю
((права частина правила і його номер) | помилка | викид | допуск).
Алгоритм є коректним для граматики, якщо для будь-якої ланцюжка з цієї граматики алгоритм дозволяє отримати впорядкований список правил для її розбору. Якщо роботою якогось алгоритму керує якась таблиця і цей алгоритм виявляється коректним для даної граматики, то таблицю називають коректною.
ПЗМ:
Нехай дана граматика з правилами:
(1) S? AAS
(2) S? B
(3) A? A
(4) A? BSA
Для такої граматики буде побудована таблиця:
аванцепочка
a b e
верхній S aAS, 1 b, 2 помилка
символ A a, 3 bSA, 4 помилка
магазину a викид помилка помилка
b помилка викид помилка
$ Помилка помилка допуск
За такої таблиці буде проведений аналіз:
(abbab, S $, e) | - (abbab, aAS $, 1)
| - (Bbab, AS $, 1)
| - (Bbab, bSAS $, 14)
| - (Bab, SAS $, 14)
| - (Bab, bAS $, 142)
| - (Ab, AS $, 142)
| - (Ab, aS $, 1423)
| - (B, S $, 1423)
| - (B, b $, 14232)
| - (E, $, 14232)
k-який пророкує алгоритм розбору КС-граматики G можна моделювати на детермінованому МП-перетворювачі з кінцевим маркером на вхідних стрічці. Так як вхідна головка МП-перетворювача може оглянути тільки один вхідний символ, аванцепочка повинна зберігатися в кінцевій пам'яті керуючого пристрою. Інші деталі моделювання очевидні.
ТРМ: Нехай А - k-який пророкує алгоритм розбору для КС-граматики G. Тоді існує такий детермінований МП-перетворювач, який дозволяє розібрати будь-яку ланцюжок з цієї граматики. Інакше кажучи можна промоделювати будь-який алгоритм на зазначеному перетворювачі.
СЛВ: Нехай А - k-який пророкує алгоритм розбору для КС-граматики G. Тоді для G існує детермінований лівий аналізатор.
Наслідки визначення LL (k)-граматики.
Покажемо що для кожної LL (k) граматики можна механічно побудувати коректний k-який пророкує алгоритм розбору. Так як ядром алгоритму є управляюча таблиця, треба показати, як будувати з граматики таку таблицю. Для цього виведемо деякі слідства визначення LL (k) - граматики.
У визначенні LL (k) - граматики стверджується, що для даної що виводиться ланцюжка wAa ланцюжок w і безпосередньо наступні за нею k вхідних символів однозначно визначають, яку застосувати правило для розгорнення нетермінала A. Тому на перший погляд може здатися, що для визначення потрібного правила треба пам'ятати весь ланцюжок w. Однак це не так. Доведемо теорему, дуже важливу для розуміння LL (k)-граматик:
ТРМ: КС-граматика G = (N, E, P, S) є LL (k)-граматикою тоді і тільки тоді, коли для двох різних правил A? B `і A? C` з P перетин FIRST (b `a `)? FIRST (c` a `) пусто для всіх таких wAa`, що S ==> wAa `.
ДКВ: Необхідність. Припустимо, що w, A, a `,` b і c `задовольняють умовам теореми, а FIRST (b` a `)? FIRST (c` a `) містить x. Тоді за визначенням FIRST для деяких y і z знайдуться висновки S ==> wAa `==> wb` a `==> wxy і S ==> wAa` ==> wc `a` ==> wxz. (Зауважимо, що тут ми використали той факт, що N не містить марних терміналів, як це передбачається для всіх розглянутих граматик.) Якщо | x |
Достатність. Припустимо, що 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? AS | a, не буде 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? Sa | b яка не є LL-граматикою. Замінимо правила на наступні:
S? BS `
S `? AS` | e
отримавши при цьому еквівалентну LL (1) - граматику.
Інший спосіб - ліва факторизація.
ПЗМ: Розглянемо LL (2) - граматику G з двома правилами S? AS | a. У цих двох правилах «вліво винесемо за дужки» символ a, записав їх у вигляді S? A (S | e). Іншими словами, ми вважаємо що операція конкатенації дистрибутивність щодо операції вибору альтернативи (позначається вертикальною рискою). Замінимо ці правила на:
S? AA
A? S | e
тим самим отримаємо еквівалентну LL (1)-граматику.
Розбір для LL (1) - граматик.
Ядром пророкує алгоритму є управляюча таблиця. У цьому і наступних розділах буде показано як побудувати коректну керуючу таблицю.
Алг 1: Керуюча таблиця для LL (1)-граматики.
Вхід: LL (1) - граматика.
Вихід: Коректна керуюча таблиця.
Метод: Будемо вважати, що $-маркер дна магазину. Таблиця визначається наступним чином:
(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).
(2) M [a, a] = викид для всіх a? E.
(3) M [$, e] = допуск.
(4) У решті випадків M [X, a] = помилка для X? N? E? ($) І a? E? (E).
ТРМ: Запропонований алгоритм будує коректну керуючу таблицю для LL (1) - граматики G.
Розбір для LL (k) - граматик.
Побудуємо керуючу таблицю для довільної граматики. Якщо граматика сильна, то можна застосувати попередній алгоритм з аванцепочкамі розширені до k символів. В іншому випадку виникає кілька проблем. У 1-м пророкує алгоритмі розбору в магазин містилися тільки символи з E? N і виявлялося, що для однозначного визначення чергового застосовуваного правила досить знати нетермінальний символ нагорі магазину і поточний вхідний символ. Для не сильних граматик цього може виявитися недостатньо.
ПЗМ: Візьмемо граматику
S? AAaa | bAba
A? B | e
Якщо дані нетермінал 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), значенням якої служить:
(1) = помилка, якщо в P немає такого правила A? A `, що FIRSTk (a`)? K L містить u;
(2) = (A? A `,), якщо A? A` - єдине правило з P, для якого FIRSTk (a `)? K L містить u;
(3) не визначено, якщо в множині знайдуться два і більше правила (цю ситуацію називають конфліктом між правилами)
На нормальною мовою це означає що виробляється значення помилка, якщо u взагалі не є ланцюжком граматики, повертається правило якщо воно існує і тільки одне і якщо кілька правил - то значення не визначається.
Алг 2: Побудова LL (k) - таблиць.
Вхід: LL (k) - граматика G = (N, E, P, S).
Вихід: Безліч TG LL (k) - таблиць, необхідних для побудови управляючої таблиці для G.
Метод:
(1) Побудувати LL (k) - таблицю T0, відповідну S і (e).
(2) Покласти спочатку TG = (T0).
(3) Для кожної LL (k)-таблиці T? TG, яка містить елемент T (u) = (A? X0B1x1 ... Bmxm,) включити в TG LL (k) - таблицю T для 1? I? M, якщо T ще не входить до TG.
(4) Повторювати крок 3 поки в TG можна включати нові таблиці.
ПЗМ: Побудуємо відповідне безліч LL (2) - таблиць для граматики S? AAaa | bAba і A? B | e. Почнемо з 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) - таблиці утворюють безліч відповідне граматиці. < br />
TA, (aa) TA, (ba)
u правило безлічі u правило безлічі
ba A? b - ba A? e -
aa A? e - aa A? b -
Тепер дамо алгоритм, яким можна побудувати коректну керуючу таблицю за відповідним безлічі LL (k) - таблиць. Керований цією таблицею k-який пророкує алгоритм буде як магазинних символів вживати замість нетерміналов LL (k) - таблиці.
Алг 3: Побудова керуючої таблиці для LL (k) - граматики.
Вхід: LL (k) - граматика і відповідне безліч TG LL (k) - таблиць.
Вихід: Коректна керуюча таблиця M для G.
Метод: M визначається на множині (TG? E ?{$})? E * k наступним чином:
(1) Якщо A? X0B1x1 ... Bmxm - правило з P з номером i і TA, L? TG, то для всіх u, для яких TA, L (u) = (A? X0B1x1 ... Bmxm,) вважаємо M [TA, L, u] = (x0TB1, Y1 ... TBm, Ymxm, i).
(2) M [a, av] = викид для всіх v? E * (k-1).
(3) M [$, e] = допуск.
(4) У решті випадків M [X, u] = помилка
(5) TS, (e) - початкова таблиця.
(6)
ПЗМ: Побудуємо керуючу таблицю для LL (2) - граматики
(1) S? AAaa
(2) S? BAba
(3) A? B
(4) A? E
використовуючи відповідне їй безліч LL (2)-таблиць, знайдене в попередньому прикладі. Алгоритм повинен видати таблицю:
aa ab a ba bb b e
T0 aT1aa, 1 aT1aa, 1 bT2ba, 2
T1 e, 4 b, 3
T2 e, 4 b, 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 з правилами:
(1) S? E
(2) S? AbA
(3) A? Saa
(4) A? B
Побудуємо відповідні LL (2)-таблиці. Почнемо з T0 = TS, (e). Потім по T0 знайдемо T1 = TA, (e), далі T2 = TS, (aa) і T3 = TA, (aa):
T0 T2
u правило безлічі u правило безлічі
e S?? e - aa S?? e -
ab S?? abA (e) ab S?? abA (aa)
T1 T3
u правило безлічі u правило безлічі
b A?? b - aa A?? Saa (aa)
aa A?? Saa (aa) ab A?? Saa (aa)
ab A?? Saa (aa) ba A?? b -
По цим таблицям побудуємо керуючу таблицю:
aa ab a ba bb b e
T0 abT1, 2 e, 1
T2 e, 1 abT3, 2
T3 T2aa, 3 T2aa, 3 b, 4
a викид викид викид
b викид викид викид
$ Допуск
(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 виникає ряд природних питань:
(1) Чи є G LL (k) - граматикою для даного k?
(2) Чи існує таке k, що G - LL (k) - граматика?
(3) Так як для 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` - ланцюжок символів після терміналу.
