Определение 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) 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)- грамматики (или разделенной грамматики).
Очень интересно - Реферат: Семантика оператора case
ОПР : КС-грамматика G =(N ,E ,P ,S ) без e -правил называется простой LL (k) - грамматикой ( или разделенной грамматикой ), если для каждого A ÎN все его альтернативы начинаются различными терминальными символами.
Предсказывающие алгоритмы разбора.
Разбор для LL (k)-грамматики очень удобно осуществлять с помощью так называемого k- предсказывающего алгоритма разбора. k-предсказывающий алгоритм использует входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки входная головка может «заглядывать» вперед на очередные k символа. Эти символы называют аванцепочкой . Алгоритм имеет конфигурацию представляемую тройкой (x ,Xa ,n ), где
x - неиспользованная часть входной цепочки
Xa - цепочка в магазине и Х - верхний символ
Вам будет интересно - Реферат: Аналитический обзор книги Программирование на языке ассемблера для микропроцессоров 8080 и 8085
n - цепочка на выходной ленте
Работой k- предсказывающего алгоритма руководит управляющая таблица, которая задает соответствие между множеством
{(верхний символ магазина)Х(аванцепочка)}
и множеством
{(правая часть правила и его номер)|ошибка|выброс|допуск}.
Похожий материал - Реферат: Динамические структуры данных стеки
Алгоритм является корректным для грамматики, если для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный список правил для ее разбора. Если работой некоего алгоритма руководит какая-то таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики, то таблицу называют корректной.
ПРМ :
Пусть дана грамматика с правилами :
(1) S ®aAS