Определение 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` - цепочка символов после терминала.