Алгоритмы и преобразования.

Во многих приложениях формальных грамматик используются различные алгоритмы над формальными грамматиками и их преобразования. Для этих целей была разработана библиотека классов FGAlgoritms. Экземпляры классов этой библиотеки представляют собой функционалы или объекты функции. Т.е. у них перегружена операция (). Это позволяет использовать эти алгоритмы более широко, например мы можем использовать "побочные" результаты алгоритмов для различных нужд, или передавать алгоритм-преобразование, как параметр другого алгоритма.

Преобразования формальных грамматик

Формальные грамматики были разработаны для того, чтобы описывать некоторый язык. Основная их цель- давать формальной описание всем цепочкам, которые могут принадлежать некоторому языку. Однако, для одного языка могут существовать несколько формальных грамматик его описывающих. Причем их различие может заключаться на только в названиях термов или порядке правил, но и в самих правилах. Другими словами, грамматики могут "существенно" отличаться, т.е. никакая перестановка правил местами или переименование термов не приведут одну грамматику к другой. И несмотря на это языки, которые они порождают будут совпадать.

В качестве простого примера рассмотрим две язык, состоящий из всех цепочек из одной или более единиц. L={ (1)+ }. Для него можно написать две различные грамматики:

ФГ1:

ФГ2:

Сразу видно, что эти две грамматики существенно отличаются. У них даже количество нетерминальных символов различно. Подобные различия грамматик порой очень сильно влияют на то, каким образом можно построить анализатор языка для данной грамматики. Для одного языка можно построить грамматики различных классов, с разным уровнем сложности разбора. Возникает задача- определить, порождают ли грамматики один и тот же язык, или нет. В общем случае эта задача не разрешима, однако есть некоторые преобразования грамматик, которые позволяют изменить грамматику, не изменив при этом язык, который она порождает.

Удаление бесполезных символов

Чтобы определить, что такое "бесполезный" символ, надо сначала дать два других определения:

Недостижимый символ- символ, который не может появится ни в одной сентенциальной форме.

Производящий нетерминал- символ, из которого можно вывести терминальную цепочку. Т.е. A=>+x

Теперь можно дать определение бесполезному символу. Символ называется бесполезным если он непроизводящий или недостижимый.

Алгоритм удаления бесполезных символов разбивается на четыре части: удаление непроизводящих символов, удаление правил, содержащих эти символы, удаление недостижимых символов, удаление правил, содержащих эти символы.

Удаление e-правил (пустых правил)

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

Для удаления этих пустых правил используется класс makeUnShorteningGrammar. Оператор () для этого класса преобразует формальную грамматику к форме без пустых правил.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG до удаления пустых правил"<<a_fg->toString();
makeUnShorteningGrammar a_musg;
a_fg = a_musg(a_fg);
cout<<"FG после удаления пустых правил"<<a_fg->toString();


Удаление цепных правил

Цепные правила- это правила вида : A::=B, где A и B- нетерминалы. Такие правила удлиняют вывод, замедляя работу анализаторов. Удаление подобных правил из формальной грамматики позволяет ускорить разбор цепочек.

Для удаления цепных правил используется класс delChainRules. Оператор () для этого класса преобразует формальную грамматику к форме без цепных правил.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG до удаления цепных правил"<<a_fg->toString();
delChainRules a_dcr;
a_fg = a_dcr(a_fg);
cout<<"FG после удаления цепных правил"<<a_fg->toString();


Удаление левой рекурсии

Этот алгоритм крайне важен, поскольку целый класс формальных грамматик не может содержать левую рекурсию. Это класс ЛЛ1-грамматик. Разбор этих грамматик крайне прост и в то же время многие конструкции могут быть представлены в виде ЛЛ1-грамматик. Сначала дадим определение прямой левой рекурсии.

Грамматика называется грамматикой с прямой левой рекурсией, если содержит хотя бы одно правило вида A::=A w.

Грамматика называется грамматикой с левой рекурсией, если в ней возможен вывод A=>*Aw, для некоторого нетерминала A.

Удаление левой рекурсии часто приводит к тому, что грамматика становится ЛЛ1-грамматикой. Однако у этого алгоритма есть один недостаток- несмотря на то, что язык, который описывает грамматика остается прежним, сама грамматика может стать неузнаваемой. Появляется много новых правил, нетерминалов, исчезает много старых правил.

Для удаления левой рекурсии используется класс delLeftRecursion. Оператор () для этого класса преобразует формальную грамматику к форме без левой рекурсии.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG до удаления левой рекурсии"<<a_fg->toString();
delLeftRecursion a_dlr;
a_fg = p_dlr(a_fg);
cout<<"FG после удаления левой рекурсии"<<a_fg->toString();


Алгоритмы над формальными грамматиками

Формальные грамматики сами по себе не представляют практического интереса. Интересны анализаторы построенные на их основе. Для построения этих алгоритмов необходимы некоторые вспомогательные результаты, которые могут быть получены с помощью алгоритмов, которые рассматриваются в этом разделе.

Построение множества укорачивающих символов

Укорачивающим символом называют такой символ для, которого верно: A=>*e. Множество таких символов используется во многих других алгоритмах, например для построения множеств ПЕРВ, ПОСЛ, СЛЕД.

Для получения этого множества используются объекты класса makeUnshortening. Его метод getShorteningTerms возвращает искомое множество термов.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG\n"<<a_fg->toString();
makeUnShortening a_gs();
SetOfTerms::ptr a_st = p_gs.getShorteningTerms(a_fg);
cout<<"Shortening terms :\n"<<a_gs->toString();


Получение множества ПЕРВ (First).

Множество ПЕРВ рассматривается для термов и правил. Неформально это множество представляет собой набор терминалов, которыми могут начинаться все сентенциальные формы, выводимые их терма A (для терма). Для правила это множество термов, которыми может начинаться цепочка выводимая из правой части правила.

Формально множество ПЕРВ(A) для терма определяется так:

ПЕРВ(A) = { a | a in Vt, A=>aw }

Для правила множество ПЕРВ(R) определяется похожим образом:

ПЕРВ(R) = { a | a in Vt, R=>aw }

Для получения этого множества используются объекты класса getFirst.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
getFirst a_gf(a_fg);
SetOfTerms::ptr a_st = p_gf(a_fg->getStartSymbol());
cout<<"First(S)="<<a_st->toString();


Получение множества ПОСЛ (Last).

Множество ПОСЛ рассматривается для термов и правил. Неформально это множество представляет собой набор терминалов, которыми могут заканчиваться все сентенциальные формы, выводимые их терма A (для терма). Для правила это множество термов, которыми может заканчиваться цепочка выводимая из правой части правила.

Формально множество ПОСЛ(A) для терма определяется так:

ПОСЛ(A) = { a | a in Vt, A=>wa }

Для правила множество ПОСЛ(R) определяется похожим образом:

ПОСЛ(R) = { a | a in Vt, R=>wa }

Для получения этого множества используются объекты класса getLast.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
getLast a_gl(a_fg);
SetOfTerms::ptr a_st = p_gl(a_fg->getStartSymbol());
cout<<"Last(S)="<<a_st->toString();


Получение множества След (Follow).

Множество СЛЕД рассматривается для термов. Неформально это множество представляет собой набор термов, которые могут встретиться следом за термом A в какой-нибудь сентенциальной форме.

Формально множество СЛЕД(A) для терма определяется так:

СЛЕД(A) = { a | a in Vt, S=>wAv, a in ПЕРВ(v) }

Для получения этого множества используются объекты класса getFollow.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
getFollow a_gf(a_fg);
SetOfTerms::ptr a_st = p_gf(a_fg->getStartSymbol());
cout<<"Follow(S)="<<a_st->toString();


ЛЛ1-грамматики

ЛЛ1 грамматики являются одними из самых простых грамматик с точки зрения сложности разбора. Однако очень много языковых конструкций могут быть описаны с их помощью. Анализ для ЛЛ1 грамматик интуитивно понятен и не требует сложных объяснений.

Анализ ЛЛ1 грамматик строит дерево разбора сверху вниз и называется нисходящим. Это означает, что алгоритм пытается сначала построить верхушку синтаксического дерева, спускаясь постепенно к листьям.

Неформально можно так описать ЛЛ1 грамматики. Грамматика, для которой на каждом шаге разбора можно сделать вывод о том, какое правило следует применить, зная лишь первый символ не прочитанной части входной цепочки называется ЛЛ1 грамматикой.

Это определение можно пояснить, рассмотрев алгоритм разбора ЛЛ1 грамматик. Для анализа цепочки используется стек, в который помещают символы из полного словаря грамматики. Начальная конфигурация анализатора подразумевает, что в стеке находится лишь стартовый символ грамматики. Зная первый символ входной цепочки мы сразу должны определить, чем мы заменим верхний символ в стеке (т.е. правой частью какого правила мы заменим символ S в стеке). Сразу становится ясно, что если в грамматике два правила S::=a w и S::=a v и входная цепочка начинается символом a, то мы не сможем определить, каким правилом в стеке заменить начальный символ.

Если мы все-таки определили, каким правилом следует заменить начальный символ, то нужно извлечь S из стека, и положить туда всю правую часть правила (чтобы первый символ правила оказался наверху). На следующем шаге мы вновь смотрим на верхний символ стека, и первый символ оставшейся непрочитанной цепочки. Если на вершине стека терминал и он совпадает с первым символом цепочки, то мы просто удаляем его из стека. Если же это нетерминал, то снова заменяем его каким-нибудь правилом. В конце концов, если цепочка принадлежит искомому языку мы должны оказаться в состоянии, в котором стек пуст и прочитана вся входная цепочка. В противном случае, на каком-то шаге мы либо не сможем сделать вывод о том, на какое правило следует заменить нетерминал на вершине магазина, либо первый символ входной цепочки не совпадет с терминалом в стеке.

Определение принадлежности к классу ЛЛ1

Итак выше было неформально дано определение ЛЛ1-грамматикам. Теперь дадим формальное определение.

Грамматика называется ЛЛ1-грамматикой, если из существования двух левых выводов:

S =>* wAv => wqv =>* wx

S =>* wAv => wpv =>* wy

для которых ПЕРВ(x) = ПЕРВ(y), следует, что q=p (p,q- цепочки символов полного словаря).

На практике, конечно такое определения сложно использовать, поэтому используют следующую теорему:

КС-грамматика G является ЛЛ1-грамматикой тогда и только тогда, когда для двух различных правил A::=w и A::=v ПЕРВ(w СЛЕД(A)) x ПЕРВ(v СЛЕД(A)) = {e}

Для неукорачивающих грамматик эту теорему можно сформулировать проще: G-ЛЛ1 <=> множества ПЕРВ на для каких двух правил одного нетерминала не пересекаются. Фактически это означает, что мы анализатор должен быть всегда в состоянии определить, какое правило необходимо применить на следующем шаге, зная лишь первый символ непрочитанной цепочки.

Для определения принадлежности грамматики к классу ЛЛ1 используется класс isLL1.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
isLL1 a_isLL1();
if ( a_isLL1( a_fg ) )
  cout<<"Grammar is LL1."
else
  cout<<"Grammar is not LL1."


Если окажется, что грамматика не принадлежит к классу ЛЛ1, то после анализа можно вызвать метод errMsg, чтобы получить строку, содержащую "пояснения" почему это так. Это может помочь провести необходимые преобразования грамматики.

Алгоритм разбора для ЛЛ1 грамматик

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

Реализация такого алгоритма разбора очень проста. Поэтому ЛЛ1 грамматики получили распространение, несмотря на то, что их класс не слишком широк.

Построение управляющей таблицы для ЛЛ1-анализатора

Фактически алгоритм определения принадлежности грамматики к классу ЛЛ1 в процессе работы выполняет построение такой таблицы. После успешного завершения его работы (грамматика оказалась ЛЛ1-грамматикой) необходимо вызвать метод getLL1Table, чтобы получить объект класса LL1Table, который представляет собой управляющую таблицу для ЛЛ1 анализатора.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
isLL1 a_isLL1();
if ( a_isLL1( a_fg ) )
{
  cout<<"Grammar is LL1.\n"
  LL1Table::ptr a_lt = a_isLL1->getLL1Table();
  cout<<"LL1 table"a_lt->toString();
}
else
  cout<<"Grammar is not LL1."


Грамматики предшествования

Грамматики предшествования позволяют описывать более широкий класс языков чем ЛЛ1-грамматики, однако менее чем SLR-грамматики. Алгоритм разбора грамматик предшествования относится к восходящим методам разбора, т.е. дерево разбора строится снизу вверх (листья и "ветки" соединяются в более крупные "ветки"). Работает алгоритм по принципу "перенос-свертка".

Центральное место во всем, что касается грамматик предшествования занимают отношения предшествования (бинарные отношения между символами полного словаря грамматики и допустимыми символами магазина). Фактически это три отношения: < = > (сворачивается раньше, сворачивается вместе, сворачивается после).

Отношения < = определяется для множеств (V + ^)x(V + e). Следующим образом:

X < Y если имеется правило A::=wXBv и B=>+Yq

^ < Y если S=>+Yw

X = Y если есть правило A::=wXYv

Отношение > определяется для множества (V + ^)x(Vt + e). Следующим образом:

X > a если имеется правило A::=wBYv и B=>+qX и Y=>*ap

X > e если S=>*wX.

Вычисление матрицы предшествования

Матрица предшествования представляет собой таблицу следующего вида:

На пересечении столбцов и строк этой таблицы стоят соответствующие отношения предшествования. Фактически такая таблица служит двум целям: по ней можно определить принадлежность грамматики к классу грамматик предшествования и она управляет работой анализатора. Строится такая таблица с помощью тех правил вычисления отношений предшествования, которые были определены выше.

Класс makePrecedenceMatrix позволяет построить такую таблицу.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
makePrecedenceMatrix a_mpm();
PrecedenceMatrix::ptr a_pm = a_mpm( a_fg );
cout<<"PrecedenceMatrix : \n"<<a_pm->toString()


Определение принадлежности грамматики к классу простого предшествования

Класс простого предшествования определяется очень просто: грамматика является грамматикой простого предшествования, если для любых двух символов полного словаря существует не более одного отношения предшествования. Неформально, это значит, что в каждой клетке матрицы предшествования должно находится не более одного отношения.

Проверку производит класс isPrecedence. Этот класс получает матрицу предшествования и по ней определяет является ли она грамматикой простого предшествования.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
makePrecedenceMatrix a_mpm();
PrecedenceMatrix::ptr a_pm = a_mpm( a_fg );
isPrecedence a_ip;
if( a_ip( m_pm ) )
  cout<<"Grammar is precedence";
else
  cout<<"Grammar is not precedence";

Определение принадлежности грамматики к классу слабого предшествования

Класс слабого предшествования определяется чуть сложнее: грамматика является грамматикой слабого предшествования, если отношение > не пересекается с объединением отношений < = и для A::=wXv и B::=v не выполняется ни X < B ни X = B. Неформально, это значит, что в каждой клетке матрицы предшествования могут находиться либо < и = либо только >.

Проверку производит класс isWeakPrecedence. Этот класс получает матрицу предшествования и по ней определяет является ли она грамматикой слабого предшествования.

FormalGrammar::ptr a_fg = new FormalGrammar(a_fileName);
cout<<"FG "<<a_fg->toString();
makePrecedenceMatrix a_mpm();
PrecedenceMatrix::ptr a_pm = a_mpm( a_fg );
isWeakPrecedence a_iwp;
if( a_iwp( m_pm ) )
  cout<<"Grammar is weak precedence";
else
  cout<<"Grammar is not weak precedence";