БОЛЬШАЯ НАУЧНАЯ БИБЛИОТЕКА  
рефераты
Добро пожаловать на сайт Большой Научной Библиотеки! рефераты
рефераты
Меню
Главная
Налоги
Начертательная геометрия
Оккультизм и уфология
Педагогика
Полиграфия
Политология
Право
Предпринимательство
Программирование и комп-ры
Радиоэлектроника
Региональная экономика
Режущий инструмент
Реклама и PR
Ресторанно-гостиничный бизнес бытовое обслуживан
Римское право
Русский язык культура речи
РЦБ ценные бумаги
САПР
Сексология
Семейное право
Социология
Страховое право
Строительство архитектура
Таможенное право
Теория государства и права
Технология
Таможенная система
Транспорт
Физика и энергетика
Философия
Финансы деньги и налоги
Физкультура и спорт
Фотография
Химия
Хозяйственное право
Цифровые устройства
Экологическое право
Экология
Экономика
Экономико-математическое моделирование
Экономическая география
Экономическая теория
Эргономика
Этика и эстетика
Сочинения по литературе и русскому языку
Рефераты по теории государства и права
Рефераты по теории организации
Рефераты по теплотехнике
Рефераты по товароведению
Рефераты по трудовому праву
Рефераты по туризму
Рефераты по уголовному праву и процессу
Рефераты по управлению
Рефераты по менеджменту
Рефераты по металлургии
Рефераты по муниципальному праву
Биографии
Рефераты по психологии
Рефераты по риторике
Рефераты по статистике
Рефераты по страхованию
Рефераты по схемотехнике
Рефераты по науке и технике
Рефераты по кулинарии
Рефераты по культурологии
Рефераты по зарубежной литературе
Рефераты по логике
Рефераты по логистике
Рефераты по маркетингу
Рефераты по международному публичному праву
Рефераты по международному частному праву
Рефераты по международным отношениям
Рефераты по культуре и искусству
Рефераты по кредитованию
Рефераты по естествознанию
Рефераты по истории техники
Рефераты по журналистике
Рефераты по зоологии
Рефераты по инвестициям
Рефераты по информатике
Исторические личности
Рефераты по кибернетике
Рефераты по коммуникации и связи
Рефераты по косметологии
Рефераты по криминалистике
Рефераты по криминологии
Новые или неперечисленные
Без категории

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

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), если 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` - цепочка символов после

терминала.





17.06.2012
Большое обновление Большой Научной Библиотеки  рефераты
12.06.2012
Конкурс в самом разгаре не пропустите Новости  рефераты
08.06.2012
Мы проводим опрос, а также небольшой конкурс  рефераты
05.06.2012
Сена дизайна и структуры сайта научной библиотеки  рефераты
04.06.2012
Переезд на новый хостинг  рефераты
30.05.2012
Работа над улучшением структуры сайта научной библиотеки  рефераты
27.05.2012
Работа над новым дизайном сайта библиотеки  рефераты

рефераты
©2011