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 последующих
|
