записон

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
\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} % конец документа