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

- ошибка. Допуск* находится в последней колонке. Для входной цепочки 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 с правилами:
S®e
S®abA
A®Saa
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 возникает ряд естественных вопросов:
Является ли G LL(k)- грамматикой для данного k ?
Существует ли такое k, что G - LL(k)- грамматика?
Так как для 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` - цепочка символов после терминала.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: