LL(k) - Грамматики

Страница 3

(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]