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

[AK1] 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) 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 все его альтернативы начинаются различными терминальными символами.

Предсказывающие алгоритмы разбора.