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

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Реферат. Файл: Word (.doc) в архиве zip. Категория: Информатика, IT
Адрес этого реферата http://referat-kursovaya.repetitor.info/?essayId=8845 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 3 из 3 [Всего 3 записей]« 1 2 3

По отношению к произвольной данной грамматике 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` - цепочка символов после терминала.

RSSСтраница 3 из 3 [Всего 3 записей]« 1 2 3


При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
www.megastock.ru
Проверить аттестат