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