[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 и 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)- грамматики.
В определении LL(k)- грамматики утверждается, что дляданной выводимой цепочки wAa цепочкаw инепосредственно следующие за ней k входных