трусики женские украина

На головну

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 при 0 <= iПрипустимо, що ми хочемо знайти цей лівий розбір, переглядаючи w один раз зліва направо. Можна спробувати зробити це, будуючи послідовність левовиводімих ланцюжків b0, b1..bm. Якщо bi = a1, a2 ... ajAB, то до даного моменту аналізу ми вже прочитали перші j вхідних символів і порівняли їх з першими j символами ланцюжка bi. Було б бажано визначити bi + 1, знаючи тільки a1, a2 ... aj (частина вхідний ланцюжка, зчитану до даного моменту), кілька наступних вхідних символів (aj + 1aj + 2 ... aj + k для деякого фіксованого k) і нетермінал A. Якщо ці три чинники однозначно визначають, яке правило треба застосувати для розгортки нетермінала A, то ai + 1 точно визначається за ai та k вхідним символам aj + 1aj + 2 ... aj + k.

Граматика, в якій кожен лівий висновок володіє цією властивістю, називається LL (k) -граматики. Ми побачимо, що для кожної LL (k) - граматики можна побудувати детермінований лівий аналізатор, який працює лінійний час. Дамо кілька визначень:

ОПР: Нехай a = xb така левовиводімая ланцюжок в граматиці G = (N, E, P, S), що xIE *, а b або починається нетерміналом, або порожній ланцюжок. Будемо називати x закінченою частиною ланцюжка a, а b - незакінченої частиною частиною. Межу між x і b будемо називати кордоном.

ПЗМ: Нехай x = abacAaB, тоді abac - закінчена частина ланцюжка x, AaB - незакінчена частина ланцюжка. Якщо x = abc, то abc - закінчена частина і е - незакінчена і кордоном служить кінець ланцюжка.

Іншими словами ідею LL (k) - граматики можна пояснити так: якщо є вже розібрана частина ланцюжка, то на підставі цього і ще кількох нерозібраних символів ми можемо зробити висновок про те, яке правило неоюходімо застосувати. Таким чином граматика посуществу не залежить (не рахуючи k наступних символів) від того, що виводиться з незакінченою частини ланцюжка. У термінах дерев цей процес виглядає наступним чином: дерево виводу ланцюжка будується починаючи з кореня і детерміновано зверху вниз.

Вводять функцію FIRST (x) - повертає перший k символів. Зазвичай приписують в якості індексів k і G - кількість символів і граматика відповідно, але їх можливо опускати, якщо це не викличе непорозумінь.

ОПР: KC- граматика G = (N, E, P, S) називається LL (k) -граматики для деякого фіксованого k, якщо з існування двох лівих висновків

(1) S?wAa`?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) - граматикою (або розділеної граматикою), якщо для кожного AIN всі його альтернативи починаються різними термінальними символами.

Пророчать алгоритми розбору.

Розбір для 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 `) CFIRST (c`a`) порожньо для всіх таких wAa`, що S?wAa`.

ДКВ: Необхідність. Припустимо, що w, A, a`, b` і c` задовольняють умовам теореми, а FIRST (b`a`) CFIRST (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 )) CFIRST1 (c` FOLLOW1 (A)) порожньо при всіх AIN. (Без ДКВ).

Теорему можна виразити таким: по першому символу після нетермінала необхідно вибрати застосовне правило - отже ці символи різні і перетин порожньо. Ця теорема може застосовуватися до 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`). Якщо eIFIRST1 (a`), то M [A, b] = (a`, i) для всіх bIFOLLOW1 (A).

(2) M [a, a] = викид для всіх aIE.

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

(4) В інших випадках M [X, a] = помилка для XINEEE {$} і aIEE {e}.

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

Розбір для LL (k) - граматик.

Побудуємо керуючу таблицю для довільної граматики. Якщо граматика сильна, то можна застосувати попередній алгоритм з аванцепочка розширеними до k символів. В іншому випадку виникає кілька проблем. У 1-му пророкує алгоритм розбору в магазин містилися тільки символи з EEN і виявлялося, що для однозначного визначення чергового застосовуваного правила досить знати нетермінальний символ нагорі магазину і поточний вхідний символ. Для не сильно граматик цього може виявитися недостатньо.

ПЗМ: Візьмемо граматику

S®aAaa | bAba

A®b | e

Якщо дані нетермінал A і аванцепочка ba, то невідомо, яке з правил треба застосувати.

Невизначеності такого роду однак можна дозволити, зв'язавши з кожним нетерміналом та частиною левовиводімой ланцюжка (яка може виявитися праворуч), спеціальний символ, званий LL (k) - таблицею. По даній аванцепочка LL (k) - таблиця буде однозначно визначати яке правило треба застосувати на черговому кроці виводу.

ОПР: Нехай E - деякий алфавіт. Якщо L1 і L2 - підмножини E, то покладемо L1 Ak L2 = {

w | для деяких xIL1 і yIL2

або w = xy, якщо | xy | ? k

або w складається з першого k символів ланцюжка xy

}

ЛМА: Для будь КС- граматики G = (N, E, P, S) і будь-яких a`, b`I (NEE):

FIRSTk (a`b`) = FIRSTk (a`) Ak FIRSTk (b`)

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

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

(2) = (A®a`,), Якщо A®a` - єдине правило з P, для якого FIRSTk (a`) Ak 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) -таблиця TITG, що містить елемент 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 визначається на безлічі (TGEEE {$})'E * k наступним чином:

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

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

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

(4) В інших випадках M [X, u] = помилка

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

ПЗМ: Побудуємо керуючу таблицю для 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`) AkL) C (FIRSTk (c`) AkL), де L = FIRSTk (a`) і a` - ланцюжок символів після терміналу.

[AK1]

Авіація і космонавтика
Автоматизація та управління
Архітектура
Астрологія
Астрономія
Банківська справа
Безпека життєдіяльності
Біографії
Біологія
Біологія і хімія
Біржова справа
Ботаніка та сільське господарство
Валютні відносини
Ветеринарія
Військова кафедра
Географія
Геодезія
Геологія
Діловодство
Гроші та кредит
Природознавство
Журналістика
Зарубіжна література
Зоологія
Видавнича справа та поліграфія
Інвестиції
Інформатика
Історія
Історія техніки
Комунікації і зв'язок
Косметологія
Короткий зміст творів
Криміналістика
Кримінологія
Криптологія
Кулінарія
Культура і мистецтво
Культурологія
Логіка
Логістика
Маркетинг
Математика
Медицина, здоров'я
Медичні науки
Менеджмент
Металургія
Музика
Наука і техніка
Нарисна геометрія
Фільми онлайн
Педагогіка
Підприємництво
Промисловість, виробництво
Психологія
Психологія, педагогіка
Радіоелектроніка
Реклама
Релігія і міфологія
Риторика
Різне
Сексологія
Соціологія
Статистика
Страхування
Будівельні науки
Будівництво
Схемотехніка
Теорія організації
Теплотехніка
Технологія
Товарознавство
Транспорт
Туризм
Управління
Керуючі науки
Фізика
Фізкультура і спорт
Філософія
Фінансові науки
Фінанси
Фотографія
Хімія
Цифрові пристрої
Екологія
Економіка
Економіко-математичне моделювання
Економічна географія
Економічна теорія
Етика

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка