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