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`.