LL (k) - Граматики

[AK1]LL (k) — Грамматики.

Визначення 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 тут неможливий, оскільки з P. 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.

верхній P. 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$, 14 232).

|-(e,$, 14 232).

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` і з` задовольняють умовам теореми, а FIRST (b`a`)?FIRST (c`a`) містить x. Тоді визначенню FIRST декому y і z знайдуться висновки S==>wAa`==>wb`a`==>wxy і S==>wAa`==>wc`a`==>wxz. (Зауважимо, що саме ми використовували те що, що N зовсім позбавлений непотрібних терміналів, як це передбачається всім аналізованих граматик.) Якщо |x| < k то y = z = e. Оскільки b`? з`, то 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? 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граматикою. Замінимо правила на следующие:

P.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 з номером і, то 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, відповідну P. 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) — таблиці утворюють безліч відповідне грамматике.

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 з номером і і 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.

T1 T2aa, 3 T2aa, 3 b, 4.

T2 e, 1 abT3,2.

T3 T2aa, 3 T2aa, 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 виникає чимало природних вопросов:

(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` - ланцюжок символів після терминала.

[AK1].

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