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

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

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

Разбор для LL(k)-грамматики очень удобно осуществлять с помощью так называемого k- предсказывающего алгоритма разбора. k-предсказывающий алгоритм использует входную ленту, магазин и выходную ленту. Алгоритм пытается проследить вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки входная головка может «заглядывать» вперед на очередные k символа. Эти символы называют аванцепочкой. Алгоритм имеет конфигурацию представляемую тройкой (x,Xa,n), где

x - неиспользованная часть входной цепочки

Xa - цепочка в магазине и Х - верхний символ

n- цепочка на выходной ленте

Работой k- предсказывающего алгоритма руководит управляющая таблица, которая задает соответствие между множеством

{(верхний символ магазина)Х(аванцепочка)}

и множеством

{(правая часть правила и его номер)|ошибка|выброс|допуск}.

Алгоритм является корректным для грамматики, если для любой цепочки из этой грамматики алгоритм позволяет получить упорядоченный список правил для ее разбора. Если работой некоего алгоритма руководит какая-то таблица и этот алгоритм оказывается корректным для рассматриваемой грамматики, то таблицу называют корректной.

ПРМ:

Пусть дана грамматика с правилами :

(1) S®aAS

(2) S®b

(3) A®a

(4) A®bSA

Для такой грамматики будет построена таблица:

аванцепочка

a b e

верхний S aAS,1 b,2 ошибка

символ A a,3 bSA,4 ошибка

магазина a выброс ошибка ошибка

b ошибка выброс ошибка

$ ошибка ошибка допуск

По такой таблице будет проведен анализ:

(abbab,S$,e) |-( abbab,aAS$,1)

|-( bbab,AS$,1)

|-( bbab,bSAS$,14)

|-( bab,SAS$,14)

|-( bab,bAS$,142)

|-( ab,AS$,142)

|-( ab,aS$,1423)

|-( b,S$,1423)

|-( b,b$,14232)

|-(e,$,14232)

k- предсказывающий алгоритм разбора КС-грамматики G можно моделировать на детерминированном МП- преобразователе с концевым маркером на входной ленте. Так как входная головка МП- преобразователя может обозреть только один входной символ, аванцепочка должна храниться в конечной памяти управляющего устройства. Остальные детали моделирования очевидны.

ТРМ: Пусть А - k- предсказывающий алгоритм разбора для КС-грамматики G. Тогда существует такой детерминированный МП- преобразователь, который позволяет разобрать любую цепочку из этой грамматики. Иначе говоря можно промоделировать любой алгоритм на указанном преобразователе.

СЛВ: Пусть А - k- предсказывающий алгоритм разбора для КС-грамматики G. Тогда для G существует детерминированный левый анализатор.

Следствия определения LL(k)-грамматики.

Покажем что для каждой LL(k) грамматики можно механически построить корректный k- предсказывающий алгоритм разбора. Так как ядром алгоритма является управляющая таблица, надо показать, как строить по грамматике такую таблицу. Для этого выведем некоторые следствия определения LL(k)- грамматики.