Xreferat.com » Рефераты по информатике и программированию » LL(k)-грамматики
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}:
По этим таблицам построим управляющую таблицу:
Алгоритм построенный по таблице разберет цепочку 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` - цепочка символов после терминала.
(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.
Помогаем в публикации. Правки вносим бесплатно.