Город бешаных рефератиков
.

.

РАЗДЕЛЫ

РЕКОМЕНДУЕМ

КАТАЛОГ РЕФЕРАТОВ

Реферат 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<=i Допустим, что мы хотим найти этот левый разбор, просматривая w один раз слева направо. Можно попытаться сделать это, строя последовательность левовыводимых цепочек b0,b1..bm. Если bi=a1,a2...ajAB, то к данному моменту анализа мы уже прочли первые j входных символов и сравнили их с первыми j символами цепочки bi. Было бы желательно определить bi+1, зная только a1,a2...aj (часть входной цепочки, считанную к данному моменту), несколько следующих входных символов (aj+1aj+2...aj+k для некоторого фиксированного k) и нетерминал A. Если эти три фактора однозначно определяют, какое правило надо применить для развертки нетерминала A, то ai+1 точно определяется по ai и k входным символам aj+1aj+2...aj+k .
Грамматика, в которой каждый левый вывод обладает этим свойством, называется LL(k)-грамматикой. Мы увидим, что для каждой LL(k)- грамматики можно построить детерминированный левый анализатор, работающий линейное время. Дадим несколько определений :
ОПР: Пусть a=xb такая левовыводимая цепочка в грамматике G=(N,E,P,S), что xE*, а b либо начинается нетерминалом, либо пустая цепочка. Будем называть x законченной частью цепочки a, а b - незаконченной частью частью. Границу между x и b будем называть рубежом.
ПРМ: Пусть x=abacAaB, тогда abac - законченная часть цепочки x, AaB - незаконченная часть цепочки. Если x=abc, то abc - законченная часть и е - незаконченная и рубежом служит конец цепочки.
Иными словами идею LL(k) - грамматики можно объяснить так: если имеется уже разобранная часть цепочки, то на основании этого и еще нескольких неразобранных символов мы можем сделать вывод о том, какое правило неоюходимо применить. Таким образом грамматика посуществу не зависит (не считая k последующих символов) от того, что выводится из незаконченной части цепочки. В терминах деревьев этот процесс выглядит следующим образом: дерево вывода цепочки строится начиная с корня и детерминировано сверху вниз.
Вводят функцию FIRST(x) - возвращающую первых k символов. Обычно приписывают в качестве индексов k и G - количество символов и грамматика соответственно, но их возможно опускать, если это не вызовет недоразумений.
ОПР: KC- грамматика G=(N,E,P,S) называется LL(k)-грамматикой для некоторого фиксированного k, если из существования двух левых выводов
(1) SwAa`wb`a`wx
(2) SwAa`wc`a`wy
для которых FIRST(x)=FIRST(y), вытекает что b`=c`.
Иначе это определение выражает то, что для имеющейся цепочки и зная следующие k символов можно применить не более одного правила вывода. Грамматика называется LL- грамматикой, если она LL(k)- грамматика для некоторого k.




ГОРОДСКИЕ ЗАКОНЫ

Рефераты и/или содержимое рефератов предназначено исключительно для ознакомления, без целей коммерческого использования. Все права в отношении рефератов и/или содержимого рефератов принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием рефератов и/или содержимого рефератов.

РЕКЛАМА









© ReferatCity.ru, рефераты, курсовые, дипломы, 2007-2018
При копирование материалов ссылка на сайт приветствуется.