Построим управляющую таблицу для произвольной грамматики. Если грамматика сильная, то можно применить предыдущий алгоритм с аванцепочками расширенными до k символов. В противном случае возникает несколько проблем. В 1-м предсказывающем алгоритме разбора в магазин помещались только символы из E È N и оказывалось, что для однозначного определения очередного применяемого правила достаточно знать нетерминальный символ наверху магазина и текущий входной символ. Для не сильных грамматик этого может оказаться недостаточно.
ПРМ: Возьмем грамматику
S ®aAaa|bAba
A®b| e
Если даны нетерминал A и аванцепочка ba, то не известно, какое из правил надо применить.
Неопределенности такого рода однако можно разрешить, связав с каждым нетерминалом и частью левовыводимой цепочки (которая может оказаться справа), специальный символ, называемый LL (k)- таблицей. По данной аванцепочке LL (k)- таблица будет однозначно определять какое правило надо применить на очередном шаге вывода.
ОПР: Пусть E - некоторый алфавит. Если L 1 и L 2 - подмножества E, то положим L 1 Åk L 2 = {
w | для некоторых xÎ L 1 и yÎ L 2
либо 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`,<Y1,Y2...Ym>), если 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, соответствующую S и { e }.
(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® S aa
(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 ® S aa {aa}
aa A ® S aa {aa} ab A ® S aa {aa}
ab A ® S aa {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 - длинна входной цепочки.