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

S®aAaa|bAba

A®b|e

Если даны нетерминал 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), значением которой служит :

(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®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)- условия: