\documentclass[12pt]{article}
\usepackage{setspace}
\usepackage{ucs}
\usepackage[utf8x]{inputenc} % Включаем поддержку UTF8
\usepackage[russian]{babel} % Включаем пакет для поддержки русского языка
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\usepackage[pdftex]{graphicx, color}
\usepackage{subfigure}
\usepackage{color}
\usepackage{listings}
\usepackage[nooneline]{caption} \captionsetup[table]{justification=raggedleft} \captionsetup[figure]{justification=centering,labelsep=endash}
\renewcommand{\baselinestretch}{1.5}
\lstset{inputencoding=utf8x, extendedchars=false, keepspaces = true,
language=c}
\renewcommand{\lstlistingname}{Листинг}
\begin{document} % начало документа
\setcounter{tocdepth}{4} % chapter, section, subsection, subsubsection и paragraph
\graphicspath{{CourseProject/Chapter1/}, {CourseProject/Chapter2/}, {CourseProject/Chapter3/}, {CourseProject/Chapter4/}, {CourseProject/Chapter5/}}
\DeclareGraphicsExtensions{.png,.pdf,.jpg,.mps}
\renewcommand{\contentsname}{\centering Содержание}
\parindent = 0.7cm
\begin{titlepage} % начало титульной страницы
\begin{center} % включить выравнивание по центру
\textit {Государственное образовательное учреждение высшего профессионального образования}\\[1.0cm]
\huge«Московский государственный технический университет имени Н.Э. Баумана»\\
\Large {(МГТУ им. Н.Э. Баумана)}\\[0.2cm]
\rule[+3mm]{7.5cm}{0.80mm}
\end{center}
\begin{flushleft} % выровнять содержимое по левому краю
\begin{tabbing}
MMMMММММMМ \= \kill
\large{ФАКУЛЬТЕТ} \> \large{\textit{ИНФОРМАТИКА И СИСТЕМЫ УПРАВЛЕНИЯ}} \\
\large{КАФЕДРА} \> \large{\textit{ТЕОРЕТИЧЕСКАЯ ИНФОРМАТИКА}} \\
\> \large{\textit{И КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ}}
\\[0.2cm]
\end{tabbing}
\end{flushleft}
\begin{center}
\Huge{РАСЧЕТНО-ПОЯСНИТЕЛЬНАЯ ЗАПИСКА}\\
к курсовому проекту на тему:\\
EDSL для написания синтаксического анализатора на С++\\[0.1cm]
\begin{tabbing}
MMMMММММMMMMMMMMMM \= \kill
\Large{Студент} \> \Large{\textit{С. А. Сорокина}} \\
\Large{Руководитель курсового проекта} \> \Large{\textit{А. В. Коновалов}}\\[0cm]
\end{tabbing}
\largeМосква 2013
\end{center}
\thispagestyle{empty} % не нумеровать страницу
\end{titlepage} % конец титульной страницы
\renewcommand{\abstractname}{\Huge{Аннотация\\[1.5cm]}}
\begin{abstract}
Целью данного проекта является создание библиотеки, генерирующей по заданной грамматике синтаксический LALR(1) анализатор, а также EDSL (Embedded Domain Specific Language) этой библиотеки для задания самой грамматики. Эта задача будет реализована с помощью метапрограммирования шаблонов на языке C++, поэтому в курсовой работе будет приведена базовая информация о шаблонах и списках типов, а также будут рассмотрены основные методы, применяемые с использованием данной технологии. Кроме этого, планируется на конечном этапе сравнить в плане выразительных возможностей на примере простого языка реализованную библиотеку и генератор синтаксических анализаторов Bison.
\end{abstract}
\clearpage
\tableofcontents %Содержание
\newpage
\part*{\large \centering ВВЕДЕНИЕ}
\addcontentsline{toc}{part}{ВВЕДЕНИЕ}
\hspace{\parindent}На данный момент существует три способа создания синтаксического анализатор: с использованием метода рекурсивного спуска, сторонних приложений или с помощью предметно-ориентированного языка. Метод рекурсивного спуска плох тем, что годится только для LL(1) грамматик. Предметно-ориентированный язык даёт возможность написать синтаксический анализатор, описав только грамматику, семантические действия и лексический анализатор.\\\indent
Предметно-ориентированный язык (англ. Domain Specific language) — это язык программирования, специально разработанный для определённого круга задач, в отличие от языка общего назначения, применимого к широкому спектру областей и не учитывающего особенности конкретных сфер знаний. Примерами таких языков могут служить TeX/LaTeX для подготовки (компьютерной вёрстки) текстовых документов, SQL для СУБД и многие другие. Использование DSL вместо языков общего назначения существенно повышает уровень абстрактности кода, что позволяет вести разработку быстро и эффективно и создавать программы, которые легки в понимании и сопровождении; а также делает возможным или существенно упрощает решение многих задач, связанных с манипулированием программами, например, порождение программ. Эти преимущества DSL привели к возникновению такой парадигмы программирования, как языково-ориентированное программирование, решающей проблему сложности программирования и заключающейся в разбиении процесса разработки программного обеспечения на разные стадии: разработка DSL и решение задачи с использованием этих DSL. При этом стадии могут вестись последовательно или параллельно, однократно или рекурсивно \cite{edsl}.\\\indent
Существует несколько основных подходов к разработке DSL: реализация независимого компилятора, встраивание интерпретатора в язык общего назначения, метапрограммирование и чистое встраивание. С помощью первых друх можно создать внешний DSL, то есть имеющий свой собственный синтаксис, для него реализован парсер, свой интерпретатор или компилятор. Программы на таких языках можно встраивать в другие языки. Классическим примером такого языка является язык регулярных выражений. Последние два подхода позволят создать встроенный DSL (реализованный внутри основного языка программирования с использованием его синтаксиса) и имеют фундаментальное преимущество перед первыми двумя — DSL не заменяет, а расширяет язык общего назначения, повторно используя весь инструментарий базового языка, начиная с парсера, благодаря чему:
появляется возможность комбинировать в едином коде возможности базового языка, общих библиотек к нему, и разработанных DSL, применяя устоявшиеся для базового языка трюки; устраняется необходимость реализовывать с нуля тривиальные вещи — достаточно адаптировать синтаксис; устраняется необходимость разработки полного комплекса инструментария разработки (оптимизирующего транслятора с информативными сообщениями об ошибках, отладчика и пр.).\\\indent
\newpage
\section[Общие сведения о метапрограммировании шаблонов на C++]{\large \centering Общие сведения о метапрограммировании шаблонов на C++}
\hspace{\parindent}Бывает так, что в программе один и тот же алгоритм используется в разных местах и оперирует переменными различных типов. Для того, чтобы избежать дублирования кода, в C++ существует средство под названием шаблоны. Шаблон даёт алгоритм, используемый для автоматической генерации экземпляров функций и классов с различными типами, то есть шаблон позволяет создавать параметризованные классы и функции \cite{template}.
\subsection[Частичная специализация шаблонов]{\large Частичная специализация шаблонов}
\hspace{\parindent}
Частичная специализация шаблонов поволяет специализировать шаблонный класс с помощью подмножества его возможных параметров конкретизации (листинг~\ref{list:example0}).
{
\singlespacing
\begin{lstlisting}[label=list:example0, caption=Примеры специализаций]
template <class Window, class Controller>
class Widget
{
обобщенная реализация...
};
template <>
class Widget<modalDialog, MyController>
{
полная специализированная реализация...
};
template <class Window>
class Widget<Window, MyController>
{
частичная специализированная реализация...
};
\end{lstlisting}
}
В приведённом примере параметр Window может принимать любые значения.\\\indent
В полной специализации параметры шаблона в угловых скобках не указываются, вместо этого после имени шаблона указываются конкретные аргументы шаблона. Конкретизируя шаблон, компилятор выполняет сопоставление с образцом существующих частичных и полных специализаций. Частичную шаблонную специализацию невозможно применить к функциям. Больше всего на частичную специализацию шаблонных функций похож процесс их перегрузки.
\subsection[Перегрузка функций]{\large Перегрузка функций}
\hspace{\parindent}
Рассмотрим функцию (листинг~\ref{list:example01}).
{
\singlespacing
\begin{lstlisting}[label=list:example01, caption=Функция Create]
template <class T, class U>
T* Create(const U& arg)
{
return new T(arg);
};
\end{lstlisting}
}
Функция Create создает новый объект, передавая аргумент его конструктору.\\\indent
Пусть объект типа Widget содержит недоступный унаследованный код, и для его создания нужны два аргумента, один из которых число -1. На производный от Widget класс такие ограничения не накладываются. Требуется специализировать функцию Create так, чтобы она обрабатывала объекты класса Widget иначе, чем объекты других классов. В этом поможет класс Type2Type, объект которого есть идентификатор, несущий информацию о типе (листинг~\ref{list:example02}).
{
\singlespacing
\begin{lstlisting}[label=list:example02, caption=Класс Type2Type и перегрузка функции Create]
template <typename T>
struct Type2Type
{
typedef T OriginalType;
};
template <class T, class U>
T* Create(const U& arg, Type2Type<T>)
{
return new T(arg);
};
template <class U>
Widget* Create(const U& arg, Type2Type<Widget>)
{
return new Widget(arg, -1);
};
String* pStr = Create("Hello", Type2Type<String>());
Widget* pW = Create(100, Type2Type<Widget>());
\end{lstlisting}
}
Второй параметр функции Create предназначен только для выбора подходящей перегрузки. Теперь эту функцию можно специализировать различными конкретизациями класса Type2Type.
\subsection[Списки типов]{\large Списки типов}
\hspace{\parindent}
Списки типов - средство для манипулирования коллекциями типов, позволяет применять к типам все основные операции, предусмотренные для обычных списков. Иногда нужно написать один и тот же код для большого количества разных типов, но шаблоны невозможно использовать. Тогда на помощь приходят списки типов. Вот как они выглядят (листинг~\ref{list:example1}).
{
\singlespacing
\begin{lstlisting}[label=list:example1, caption=Список типов]
template <class T, class U>
struct Typelist
{
typedef T Head;
typedef U Tail;
};
\end{lstlisting}
}
Списки типов не содержат никаких значений, их предназначение - предоставлять информацию о типах, поэтому любая обработка списков типов возможна лишь на этапе компиляции, а не в ходе выполнения программы.\\\indent
Для описания списков, не содержащих никаких типов или содержащих только один тип используется нулевой тип списка и класс NullType. При этом каждый список типов должен заканчиваться классом NullType, служащим маркером конца списка (листинг~\ref{list:example2}).
{
\singlespacing
\begin{lstlisting}[label=list:example2, caption=Класс Typelist из одного элемента]
class NullType {};
typedef Typelist<int, NullType> OneTypeOnly;
\end{lstlisting}
}
Класс Typelist содержит 2 типа, доступ к которым осуществляется посредством внутренних имён Head и Tail. Создание списка типов, содержащего более двух типов, предполагает комбинацию списков типов, причём список типов, содержащий n типов, является комбинацией n списков типов, например (листинг~\ref{list:example3}).
{
\singlespacing
\begin{lstlisting}[label=list:example3, caption=Класс Typelist из трёх типов char]
typedef Typelist<char, Typelist<signed char,
Typelist<unsigned char, NullType> > > AllCharTypes;
\end{lstlisting}
}
Подобная конструкция выглядит достаточно громоздко. Для устранения этого можно определить макросы, преобразующие рекурсию в перечисление (листинг~\ref{list:example4}).
\begin{lstlisting}[label=list:example4, caption=Макросы для определения списка из нескольких типов и класс Typelist из целочисленных типов]
#define TYPELIST_1(T1) Typelist<T1, NullType>
#define TYPELIST_2(T1, T2) Typelist<T1, TYPELIST_1(T2) >
#define TYPELIST_1(T1, T2, T3) Typelist<T1, TYPELIST_2(T2, T3) >
#define TYPELIST_4(T1, T2, T3, T4) Typelist<T1, TYPELIST_3(T2, T3, T4) >
typedef TYPELIST_4(signed char, short int int long int) SignedIntegrals;
\end{lstlisting}
Идея, лежащая в основе большинства операций со списками типов, заключается в применении рекурсивных шаблонов, использующих для своего определения собственные конкретизации (листинг~\ref{list:example5}). Реализация структуры Length использует частичную специализацию шаблона, позволяющую различать нулевой тип и список типов.
{
\singlespacing
\begin{lstlisting}[label=list:example5, caption=Вычисление длины списка типов]
template <class TList> struct Length;
template <> strucn Length<NullType>
{
enum { value = 0 };
}
template {class T, class U}
struct Lenght< Typelist<T, U> >
{
enum { value = 1 + Length<U>::value };
};
\end{lstlisting}
}
А вот пример алгоритма для операции индексации списка (листинг~\ref{list:example6}). При попытке выйти за границы списка компилятор сообщит, что специализация TypeAt<NullType, x> не существует, где x - величина, на которую превышен размер списка.
{
\singlespacing
\begin{lstlisting}[label=list:example6, caption=Алгоритм TypeAt]
template <class Head, class Tail>
struct TypeAt<Typelist<Head, Tail>, 0>
{
typedef Head Result;
}
template <class Head, class Tail, unsigned int i>
struct TypeAt<Typelist<Head, Tail>, i>
{
typedef typename TypeAt<Tail, i-1>::Result Result;
};
\end{lstlisting}
}
\subsection[Класс Any]{\large Класс Any}
\hspace{\parindent}
Класс Any позволяет хранить внутри себя значения любого типа. Функция set(x) сохраняет в переменной типа Any некоторое значение, функция get<T>() получает к нему доступ, функция reset() удаляет сохранённое значение (листинг~\ref{list:example7}).
{
\singlespacing
\begin{lstlisting}[label=list:example7, caption=Класс Any]
struct AnyHolderBase {
virtual ~AnyHolderBase() {}
};
template <typename T>
struct AnyHolderT: public AnyHolderBase {
T value;
AnyHolderT(const T& new_value): value(new_value)
{
}
};
class Any {
Any(const Any&);
Any& operator=(const Any&);
AnyHolderBase *m_holder;
public:
struct NullDereference {};
struct BadCast{};
Any():
m_holder(0)
{
}
~Any() {
reset();
}
template <typename T>
T& get() {
if (! m_holder)
throw NullDereference();
AnyHolderT<T> *holderT = dynamic_cast<AnyHolderT<T>*>(m_holder);
if (! holderT)
throw BadCast();
return holderT->value;
}
template <typename T>
void set(const T& new_value) {
reset();
m_holder = new AnyHolderT<T>(new_value);
}
void reset() {
if (m_holder) {
delete m_holder;
m_holder = 0;
}
}
};
\end{lstlisting}
}
Такой класс Any, в отличие от использования простого указателя void, позволит проверять соответствие типов и выдавать сообщения об ошибке BadCast при попытке привести хранимое в Any значение к типу, к которому это значение не приводится. Также сообщение об ошибке NullDereference будет выдаваться при попытке вызвать у экземпляра класса Any метод get, если значение предварительно не установлено (то есть не был вызван метод set) или же если значение было установлено, но затем удалено с помощью метода reset (листинг~\ref{list:example8}).
{
\singlespacing
\begin{lstlisting}[label=list:example8, caption=Пример использования класса Any]
Any a;
a.set(10);
std::cout << "Stored int " << a.get<int>() << std::endl;
std::string s = "Hello";
a.set(s);
std::cout << "Stored string " << a.get<std::string>() << std::endl;
std::cout << "Stored int " << a.get<int>() << std::endl;
// !!!! Приведёт к выбросу исключения BadCast.
a.reset();
std::cout << "Stored string " << a.get<std::string>() << std::endl;
// !!!! Приведёт к выбросу исключения NullDereference.
\end{lstlisting}
}
\clearpage
\newpage
\section[Релизация библиотеки описания синтаксиса]{\large \centering Релизация библиотеки описания синтаксиса}
\hspace{\parindent}
\subsection[Описание синтаксиса библиотеки]{\large Описание синтаксиса библиотеки}
\hspace{\parindent}
В библиотеке были реализованы такие типы как: Term - соответствующий терминальным символам, NTerm - нетерминальным символам и Rule, являющийся маркером начала правила. Также в библиотеке перегружены операторы <{}<, используемый для формирования правила, и |, позволяющий определять несколько правил для одного нетерминального символа. Для того, чтобы реализовать библиотеку, понадобилось к тому же несколько промежуточных типов.\\\indent
Итак, нетерминалы типа NTerm задаются с помощью правил вида:
NTerm<Тип токена, тип атрибута> Нетерминал = Альтернатива | Альтернатива | ...;
где тип токена - это перечисление, состоящее из тэгов терминальных символов. Тип атрибута - это тип атрибута нетерминала (число или указатель на дерево разбора и т. д.) или просто void, если атрибута нет. Нетерминал - это имя нетерминала, глобальная переменная. Альтернатива - это правило, задающееся в виде:
Rule() << элемент << элемент... [<< функция обработки],
где Rule() - это маркер начала правила, а элементом может быть нетерминал или терминал. У терминала также может быть атрибут, тогда терминал задаётся в виде:
Term<тип атрибута>(значение типа токена),
а может и не быть, тогда терминал просто задаётся значением типа токена.\\\indent
Функция обработки должна возвращать значение типа атрибута нетерминала и принимать значения атрибутов, представленных в данной альтернативе (как нетерминалами с непустым типом атрибута, так и терминалами с атрибутами). Функция обработки может отсутствовать, если нетерминал имеет пустой (void) атрибут и элементы в альтернативе атрибутов не несут, или если нетерминал имеет непустой атрибут и только один элемент несёт атрибут, причём типы атрибутов должны совпадать. Атрибут нетерминала получает значение атрибута элемента.
\\\indent
\clearpage
\newpage
\section[Релизация LALR(1) анализатора]{\large \centering Релизация LALR(1) анализатора}
\hspace{\parindent}
Существуют различные алгоритмы синтаксического анализа: восходящие и нисходящие, с предпросмотром - и без. Один из алгоритмов - это LALR(1) (look ahead left-to-right) алгоритм. Как можно понять из названия, это алгоритм с предпросмотром одного символа, при котором строится правый вывод. Данный алгоритм относится к классу восходящих, и класс грамматик, разбираемых по LALR(1) шире, чем класс SLR(1)-грамматик. При этом большинство реально используемых языков программирования имеют LALR(1)-грамматики, поэтому алгоритм имеет практическое применение, например, в генераторе синтаксических анализаторов yacc и его производных, таких, как GNU bison.
Синтаксический анализ с использованием алгоритма LALR(1) можно логически разбить на два этапа: построение таблиц ACTION и GOTO и непосредственно сам анализ с использованием этих таблиц.
\subsection[Построение таблиц action и goto]{\large Построение таблиц action и goto}
\subsection[Алгоритм LALR(1)]{\large Алгоритм LALR(1)}
\subsection[Разница между LALR(1) и SLR]{\large Разница между LALR(1) и SLR}
\cite{lalr}
\clearpage
\newpage
\section[Сравнение реализованной библиотеки с GNU bison на примере простого языка]{\large \centering Сравнение реализованной библиотеки с GNU bison на примере простого языка}
\hspace{\parindent}
\subsection[Обзор GNU bison]{\large Обзор GNU bison}
\hspace{\parindent}
\cite{bison}
\subsection[Сравнительный анализ выразительных возможностей реализованной библиотеки и GNU bison]{\large Сравнительный анализ выразительных возможностей реализованной библиотеки и GNU bison}
\hspace{\parindent}
\newpage\newpage
\part*{\large \centering ЗАКЛЮЧЕНИЕ}
\addcontentsline{toc}{part}{ЗАКЛЮЧЕНИЕ}
\clearpage
\newpage
\bibliographystyle{utf8gost705u} %% стилевой файл для оформления по ГОСТу
\begin{flushleft}
\bibliography{biblio} %% имя библиографической базы (bib-файла)
\end{flushleft}
\end{document} % конец документа