Поиск: 
Расширенный поиск | Последние запросы
FREE-REFERATS.ru

Банк бесплатных рефератов

Рефераты по Компьютерные технологии - "LL(k) -грамматики"

Страница: 1 2 3 4
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<=i<m и am=w. Последовательность p0p1.. pm-1 - левый разбор цепочки w.
Допустим, что мы хотим найти этот левый разбор, просматривая 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) (2) SЮwAa`Юwc`a`Юwy для которых FIRST(x) =FIRST(y) , вытекает что b`=c`.
Иначе это определение выражает то, что для имеющейся цепочки и зная следующие k символов можно применить не более одного правила вывода. Грамматика называется LL-грамматикой, если она LL(k) -грамматика для некоторого k.
ПРМ: Пусть G состоит из правил S®aAS|b, A®a|bSA. Интуитивно G является LL(1) - грамматикой, потому что, коль скоро дан самый левый нетерминал С в левовыводимой цепочке и следующий входной символ с, существует не более одного правила, применимого к С и приводящего к терминальной цепочке, начинающейся символом с. Переходя к определению LL(1) - грамматики, мы видим, что если SЮwSa`Юwb`a`Юwx и SЮwSa`Юwc`a`Юwy и цепочки x и y начинаются одним и тем же символом, то должно быть b`=c`. В данном случае если x и y начинаются символом a, то в выводе участвовало правило S®aAS и b`=c`=aAS. Альтернатива S®b здесь невозможна. С другой стороны, если x и y начинаются с b, то должно применяться правило S®b и b`=c`=b. Заметим, что случай x=y=e здесь невозможен, так как из S в грамматике G не выводится e.
Когда рассматриваются два вывода SЮwAa`Юwc`a`Юwy рассуждение аналогично. Грамматика G служит примером так называемой простой LL(1) грамматики (или разделенной грамматики) .
ОПР: КС-грамматика G=(N, E, P, S) без e-правил называется простой LL(k) - грамматикой (или разделенной грамматикой) , если для каждого AОN все его альтернативы начинаются различными терминальными символами.
Предсказывающие алгоритмы разбора.
Разбор для LL(k) -грамматики очень удобно осуществлять с помощью так называемого k- предсказывающего алгоритма разбора. k-предсказывающий алгоритм использует входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки входная головка может “заглядывать” вперед на очередные k символа. Эти символы называют аванцепочкой. Алгоритм имеет конфигурацию представляемую тройкой (x, Xa, n) , где x - неиспользованная часть входной цепочки Xa - цепочка в магазине и Х - верхний символ n - цепочка на выходной ленте Работой k- предсказывающего алгоритма руководит управляющая таблица, которая задает соответствие между множеством {(верхний символ магазина) Х (аванцепочка) } и множеством {(правая часть правила и его номер) |ошибка|выброс|допуск}.

Страница: 1 2 3 4

© 2003-2016 Free-Referat.ru - Рефераты, Курсовые, Дипломы, Доклады, Шпаргалки
Notice: Undefined index: r in /home/bitrix/ext_www/free-referat.ru/index.php on line 264 Notice: Undefined index: in /home/bitrix/ext_www/free-referat.ru/index.php on line 264