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

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

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

ОПР: Пусть 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 Sa|b которая не является LL- грамматикой. Заменим правила на следующие:

S bS`

S` aS`|e

получив при этом эквивалентную LL(1)- грамматику.

Другой способ - левая факторизация.

ПРМ: Рассмотрим LL(2)- грамматику G с двумя правилами S aS|a. В этих двух правилах "вынесем влево за скобки" символ a, записав их в виде S a(S|e). Иными словами, мы считаем что операция конкатенации дистрибутивна относительно операции выбора альтернативы (обозначаемой вертикальной чертой). Заменим эти правила на :

S aA

A S|e

тем самым получим эквивалентную LL(1)-грамматику.

Разбор для LL(1)- грамматик.

Ядром предсказывающего алгоритма является управляющая таблица. В этом и следующих разделах будет показано как построить корректную управляющую таблицу.

АЛГ 1: Управляющая таблица для LL(1)-грамматики.

Вход : LL(1)- грамматика .

Выход : Корректная управляющая таблица.

Метод : Будем считать, что $-маркер дна магазина. Таблица определяется следующим образом:

(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).

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

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

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

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

Разбор для LL(k)- грамматик.

Построим управляющую таблицу для произвольной грамматики. Если грамматика сильная, то можно применить предыдущий алгоритм с аванцепочками расширенными до k символов. В противном случае возникает несколько проблем. В 1-м предсказывающем алгоритме разбора в магазин помещались только символы из E N и оказывалось, что для однозначного определения очередного применяемого правила достаточно знать нетерминальный символ наверху магазина и текущий входной символ. Для не сильных грамматик этого может оказаться недостаточно.

ПРМ: Возьмем грамматику

S aAaa|bAba

A b|e

Если даны нетерминал 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), значением которой служит :

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

(2) =(A a`,Y1,Y2...Ym), если 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,Y1,Y2...Ym) включить в 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)- таблицы образуют множество соответствующее грамматике.

Теперь дадим алгоритм, которым можно построить корректную управляющую таблицу по соответствующему множеству 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,Y1...Ym) полагаем 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)-таблиц, найденное в предыдущем примере. Алгоритм должен выдать таблицу:

где 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}:

По этим таблицам построим управляющую таблицу:

Алгоритм построенный по таблице разберет цепочку 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)- условия.

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


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