(2) Положить вначале TG={T0}.
(3) Для каждой LL(k)-таблицы TÎTG, содержащей элемент T(u)=(A®x0B1x1 .Bmxm,<Y1,Y2 .Ym>) включить в 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 с номером i и TA,LÎTG, то для всех u, для которых TA,L(u)=(A®x0B1x1 .Bmxm,<Y1 .Ym>) полагаем 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} - начальная таблица.
ПРМ: Построим управляющую таблицу для 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]
)