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<=i), если 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` - цепочка символов после
терминала.
