Визначення 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 1 aj +2 ... aj + k для деякого фіксованого k) і нетермінал A. Якщо ці три чинники однозначно визначають, яке правило треба застосувати для розгорнення нетермінала A, то ai +1 точно визначається за ai і k вхідним символам aj 1 aj +2 ... aj + k.
Граматика, в якій кожен лівий висновок, має таку властивість, називається LL (k)-граматикою. Ми побачимо, що для кожної LL (k) - граматики можна побудувати детермінований лівий аналізатор, що працює лінійний час. Дамо кілька визначень: ОПР: Нехай a = xb така левовиводімая ланцюжок у граматиці G = ( N , E , P , S ), що xОE *, а 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 , < b> S ) називається LL (k)-граматикою для деякого фіксованого k, якщо з існування двох лівих висновків
(1) S Юw Aa ` Ю wb` a ` Юwx S Юw Aa ` Ю 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 , < b> S ) без e-правил називається простий LL (k) - граматикою (або розділеної граматикою), якщо для кожного A Про N всі його альтернативи починаються різними термінальними символами.
Пророкує алгоритми розбору.
Розбір для LL (k)-граматики дуже зручно здійснювати за допомогою так званого k-який пророкує алгоритму розбору. k-який пророкує алгоритм використовує вхідну стрічку, магазин і вихідну стрічку. Алгоритм намагається простежити висновок ланцюжка, збережені на його вхідний стрічці. При читанні аналізованої ланцюжка вхідна головка може "заглядати" вперед на чергові k символу. Ці символи називають аванцепочкой. Алгоритм має конфігурацію що представляється трійкою (x, Xa, n ), де
x - невикористана частина вхідний ланцюжка
Xa - ланцюжок у магазині і Х - верхній символ n - ланцюжок на вихідний стрічці
Роботою k-який пророкує алгоритму керує керуюча таблиця, яка задає відповідність між безліччю
((верхній символ магазину) Х (аванцепочка))
і безліччю
((права частина правила і його номер) | помилка | викид | допуск).
Алгоритм є коректним для граматики, якщо для будь-якої ланцюжка з цієї граматики алгоритм дозволяє отримати впорядкований список правил для її розбору. Якщо роботою якогось алгоритму керує якась таблиця і цей алгоритм виявляється коректним для даної граматики, то таблицю називають коректною. ПЗМ:
Нехай дана граматика з правилами: S ® aAS S ® b A ® a 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) - граматики стверджується, що для даної що виводиться ланцюжка wA a ланцюжок w і безпосередньо наступні за нею k вхідних символів однозначно визначають, яку застосувати правило для розгорнення нетермінала A. Тому на перший погляд може здатися, що для визначення потрібного правила треба пам'ятати весь ланцюжок w. Однак це не так. Доведемо теорему, дуже важливу для розуміння LL (k)-граматик: ТРМ: КС-граматика G = ( N , E , P , < b> S ) є LL (k)-граматикою тоді і тільки тоді, коли для двох різних правил A ® b ` і A ® c ` з P перетин FIRST ( b` a `) ЗFIRST ( c` a `) пусто для всіх таких wA a` , що S ЮwA a `. ДКВ: Необхідність. Припустимо, що w, A, a `, b` і c ` задовольняють умовам теореми, а FIRST ( b` a ` ) ЗFIRST ( c `a` ) містить x. Тоді за визначенням FIRST для деяких y і z знайдуться висновки S ЮwA a ` Юw b` a ` Юwxy і S ЮwA a ` Юw c` a ` Юwxz. (Зауважимо, що тут ми використали той факт, що N не містить марних терміналів, як це передбачається для всіх розглянутих граматик.) Якщо | x | b ` № c` , то G не LL (k) - граматика.
Достатність. Припустимо, що G не LL (k) - граматика. Тоді знайдуться такі два висновки S ЮwA a ` Юw b` a ` Юwx і S ЮwA a ` Юw c` a ` Юwy, що ланцюжки x і y збігаються в першу k позиціях, але b` № c ` . Тому A ® b ` і A ® c` - різні правила з P і кожне з множин FIRST ( b `a` ) та FIRST ( c `a` ) містить ланцюжок FIRST (x) збігається з FIRST (y). ЧТД . ПЗМ: Граматика G з правила S ® a S | a, не буде LL (1) - граматикою, тому що FIRST1 (a S ) = FIRST1 (a) = a. Це можна пояснити так - бачачи тільки перший символ ланцюжка ми не можемо визначити який правило необхідно застосувати (ліве або праве). З іншого боку ця граматика є LL2 (k) граматикою - що цілком очевидно. ОПР: Хай G = ( N , E , P , S ) - КС-граматика. Визначимо FOLLOWk ( b `) як множина термінальних символів, які можуть зустрічатися після нетемінала, що є аргументом функції. ТРМ: КС-граматика G = ( N , E , P , < b> 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) - граматика . Проте у ряді випадків таке перетворення можливо. Застосовується два способи:
Перший спосіб - усунення лівої рекурсії. ПЗМ: Хай
