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

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

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

Определение LL(k)-грамматик.

Для начала предположим, что G=(N,E,P,S) - однозначная грамматика и

w=a1,a2...an - цепочка из L(G). Тогда существует единственная

последовательность левовыводимых цепочек b0,b1..bm, для которой S=b0,bi,pi

Ю bi+1 при 0), если 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,) включить в 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,) полагаем

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` - цепочка символов после

терминала.