реферат, рефераты скачать Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
реферат, рефераты скачать
реферат, рефераты скачать
МЕНЮ|
реферат, рефераты скачать
поиск
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` - цепочка символов после

терминала.



© 2003-2013
Рефераты бесплатно, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.