Бесплатные рефераты


В мире
Календарь новостей
« Ноя.2017
Пн.Вт.Ср.Чт.Пт.Сб.Вс.
  12345
6789101112
13141516171819
20212223242526
27282930   
ВНИМАНИЕ!!!
УВАЖАЕМЫЕ ПОЛЬЗОВАТЕЛИ!!!
Сайт поменял владельца и на нём грядут большие перемены.
Убедительная просьба не пользоваться покупкой рефератов через смс.
ДАННЫЙ СЕРВИС БОЛЬШЕ НЕ РАБОТАЕТ
Стоит вопрос об его удалении, дабы сделать рефераты бесплатными. Извините за неудобство и спасибо за понимание
Поиск реферата

Реферат, курсовая, контрольная, доклад на тему: LL(k)-грамматики

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.
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
= e. Так как b` № c`, то G не LL(k)- грамматика.
Достаточность. Допустим, что G не LL(k)- грамматика. Тогда найдутся такие два
вывода SЮwAa`Юwb`a`Юwx и SЮwAa`Юwc`a`Юwy, что цепочки x и y совпадают в первых k
позициях, но b`№c`. Поэтому A®b` и A®c` - различные правила из P и каждое из
множеств FIRST(b`a`) и FIRST(c`a`) содержит цепочку FIRST(x) совпадающую с
FIRST(y). ЧТД.
ПРМ: Грамматика G из правила S®aSa, не будет LL(1)- грамматикой, так как
FIRST1(aS)=FIRST1(a)=a. Это можно объяснить так - видя только первый символ
цепочки мы не можем определить какое правило необходимо применить (левое или
правое). С другой стороны эта грамматика является LL2(k) грамматикой - что
вполне очевидно.
ОПР: Пусть G=(N,E,P,S) - КС-грамматика. Определим FOLLOWk(b`) как множество
терминальных символов, которые могут встречаться после нетеминала, являющегося
аргументом функции.
ТРМ: КС-грамматика G=(N,E,P,S) является LL(1)-грамматикой тогда и только тогда,
когда для двух различных правил A®b` и A®c` пересечение FIRST1(b`
FOLLOW1(A))ЗFIRST1(c` FOLLOW1(A)) пусто при всех AОN. (Без ДКВ).
Теорему можно выразить следующим : по первому символу после нетерминала
необходимо выбрать применимое правило - следовательно эти символы различны и
пересечение пусто. Эта теорема может применяться к LL(k)- грамматикам, но не
всегда выполняться. Грамматики для которых выполняется теорема называются
сильными, таким образом все LL(1) грамматики - сильные. Необходимо так же
заметить что каждая LL(k)- грамматика однозначна, поэтому если имеется
неоднозначная грамматика - то она не LL(k). Имеется неразрешимая проблема
распознавания, существует ли для данной КС-грамматики G, не являющейся LL(k),
эквивалентная ей LL(k)- грамматика. Однако в ряде случаев такое преобразование
возможно. Применяется два способа:
Первый способ - устранение левой рекурсии.
ПРМ: Пусть G - грамматика S®Sab которая не является LL- грамматикой. Заменим
правила на следующие:
S ®bS`
S`®aS`e
получив при этом эквивалентную LL(1)- грамматику.
Другой способ - левая факторизация.
ПРМ: Рассмотрим LL(2)- грамматику G с двумя правилами S®aSa. В этих двух
правилах "вынесем влево за скобки" символ a, записав их в виде S®a(Se). Иными
словами, мы считаем что операция конкатенации дистрибутивна относительно
операции выбора альтернативы (обозначаемой вертикальной чертой). Заменим эти
правила на :
S®aA
A®Se
тем самым получим эквивалентную LL(1)-грамматику.


Разбор для LL(1)- грамматик.
Ядром предсказывающего алгоритма является управляющая таблица. В этом и
следующих разделах будет показано как построить корректную управляющую таблицу.
АЛГ 1: Управляющая таблица для LL(1)-грамматики.
Вход : LL(1)- грамматика .
Выход : Корректная управляющая таблица.
Метод : Будем считать, что $-маркер дна магазина. Таблица определяется следующим
образом:

Если A ® a` - правило из P с номером i, то M[A,a]=(a`,i) для всех a№e,
принадлежащих FIRST1(a`). Если eОFIRST1(a`), то M[A,b]=(a`,i) для всех
bОFOLLOW1(A).

M[a,a]=выброс для всех aОE.

M[$,e]=допуск.

В остальных случаях M[X,a]=ошибка для XОNИEИ{$} и aОEИ{e}.

ТРМ: Предложенный алгоритм строит корректную управляющую таблицу для LL(1)-
грамматики G.

Разбор для LL(k)- грамматик.
Построим управляющую таблицу для произвольной грамматики. Если грамматика
сильная, то можно применить предыдущий алгоритм с аванцепочками расширенными до
k символов. В противном случае возникает несколько проблем. В 1-м
предсказывающем алгоритме разбора в магазин помещались только символы из EИN и
оказывалось, что для однозначного определения очередного применяемого правила
достаточно знать нетерминальный символ наверху магазина и текущий входной
символ. Для не сильных грамматик этого может оказаться недостаточно.
ПРМ: Возьмем грамматику
S®aAaabAba
A®be
Если даны нетерминал A и аванцепочка ba, то не известно, какое из правил надо
применить.
Неопределенности такого рода однако можно разрешить, связав с каждым
нетерминалом и частью левовыводимой цепочки (которая может оказаться справа),
специальный символ, называемый LL(k)- таблицей. По данной аванцепочке LL(k)-
таблицабудет однозначно определять какое правило надо применить на очередном
шаге вывода.
ОПР: Пусть E - некоторый алфавит. Если L1 и L2 - подмножества E, то положим L1
Еk L2 = {
w для некоторых xОL1 и yОL2
либо w = xy, если xy Јk
либо w состоит из первых k символов цепочки xy
}
ЛМА: Для любой КС- грамматики G=(N,E,P,S) и любых a`, b`О(NИE) :

FIRSTk(a`b`)=FIRSTk(a`) Еk FIRSTk(b`)

ОПР: Пусть G=(N,E,P,S) - КС- грамматика. Для каждых AОN и LНE определим LL(k)-
таблицу Ta,l, соответствующую A и L, как функцию T(u), значением которой служит
:

=ошибка, если в P нет такого правила A®a`, что FIRSTk(a`) Еk L содержит u;

=(A®a`,), если A®a` - единственное правило из P, для которого
FIRSTk(a`) Еk L содержит u;

не определено, если в множестве найдутся два и более правила (эту ситуацию
называют конфликтом между правилами)

На нормальном языке это означает что вырабатывается значение ошибка, если u
вообще не является цепочкой грамматики, возвращается правило если оно существует
и только одно и если несколько правил - то значение не определяется.
АЛГ 2: Построение LL(k)- таблиц.
Вход: LL(k)- грамматика G=(N,E,P,S).
Выход: Множество TG LL(k)- таблиц, необходимых для построения управляющей
таблицы для G.
Метод:

Построить LL(k)- таблицу T0, соответствующую S и {e}.

Положить вначале TG={T0}.

Для каждой LL(k)-таблицы TОTG, содержащей элемент
T(u)=(A®x0B1x1...Bmxm,) включить в TG LL(k)- таблицу T для 1ЈiЈm,
если T еще не входит в TG.

Повторять шаг 3 пока в TG можно включать новые таблицы.

ПРМ: Построим соответствующее множество LL(2)- таблиц для грамматики S®aAaabAba
и A®be. Начнем с 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правиломножества
baA ® b-baA ® e-
aaA ® e-aaA ® b-
Теперь дадим алгоритм, которым можно построить корректную управляющую таблицу по
соответствующему множеству LL(k)- таблиц. Управляемый этой таблицей k-
предсказывающий алгоритм будет в качестве магазинных символов употреблять вместо
нетерминалов LL(k)- таблицы.
АЛГ 3: Построение управляющей таблицы для LL(k)- грамматики.
Вход : LL(k)- грамматика и соответствующее множество TG LL(k)- таблиц.
Выход : Корректная управляющая таблица M для G.
Метод: M определяется на множестве (TGИEИ{$})ґE*k следующим образом:

Если A®x0B1x1...Bmxm - правило из P с номером i и TA,LОTG, то для всех u, для
которых TA,L(u)=(A®x0B1x1...Bmxm,) полагаем
M[TA,L,u]=(x0TB1,Y1...TBm,Ymxm,i).

M[a,av]=выброс для всех vОE*(k-1).

M[$,e]=допуск.

В остальных случаях M[X,u]=ошибка

TS,{e} - начальная таблица.



ПРМ: Построим управляющую таблицу для LL(2)- грамматики

S®aAaa

S®bAba

A®b

A®e

используя соответствующее ей множество LL(2)-таблиц, найденное в предыдущем
примере. Алгоритм должен выдать таблицу:
aaabababbbe
T0aT1aa,1aT1aa,1bT2ba,2
T1e,4b,3
T2 e,4b,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 с правилами:

S®e

S®abA

A®Saa

A®b

Построим соответствующие LL(2)-таблицы. Начнем с T0=TS,{e}. Затем по T0 найдем
T1=TA,{e}, далее T2=TS,{aa} и T3=TA,{aa}:

T0T2
uправиломножестваuправиломножества
eS ®e-aaS ®e-
abS ®abA{e}abS ®abA{aa}

T1T3
uправиломножества uправиломножества
bA ®b-aaA ®Saa{aa}
aaA ®Saa{aa}abA ®Saa{aa}
abA ®Saa{aa}baA ®b-


По этим таблицам построим управляющую таблицу:
aaabababbbe
T0 abT1,2e,1
T1T2aa,3T2aa,3b,4
T2e,1abT3,2
T3T2aa,3T2aa,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` - цепочка символов после терминала.






ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо А можно заказать оригинальный реферат
Опубликовано: 20.08.10 | [ + ]   [ - ]  
Просмотров: 98
Загрузок: 0
Рекомендуем
{dnmbottom}
БАНК РЕФЕРАТОВ содержит более 70 000 рефератов, курсовых, контрольных работ, сочинений и шпаргалок.