documentclass 12pt article usepackage setspace usepackage ucs usepacka

  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
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
\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}В данном проекте для создания EDSL, позволяющего пользователю задать грамматику, с которой генерируемый синтаксический анализатор будет сопоставлять входящую последовательность токенов, будет использовано такое средство языка 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} Для задания пользователем грамматики, с которой генерируемый синтаксический анализатор будет сопоставлять входящую последовательность токенов, являющуюся результатом выполнения лексического анализа, и выполнять указанные пользователем функции --- семантические действия, был создан EDSL. Ниже будет приведён синтаксис библиотеки, предоставляющей возможность использовать данный встроенный язык, и описано её внутреннее устройство.
\subsection[Описание синтаксиса библиотеки]{\large Описание синтаксиса библиотеки}
\hspace{\parindent}
В библиотеке с помощью шаблонов реализованы такие типы как: Term, соответствующий терминальным символам, NTerm --- нетерминальным символам, которые могут иметь или не иметь атрибут, и Rule, являющийся маркером начала правила. Также в библиотеке перегружены операторы <{}< и |. Первый используется для формирования правила, второй позволяет определять несколько правил для одного нетерминального символа. К тому же в библиотеке присутствует класс Lexer, который нужен для того, чтобы осуществлять лексический анализ. Виртуальный метод этого класса возвращает значение реализованных в библиотеке типов Token и AttrToken. Указание координат токена происходит с помощью типа Coord. Для того, чтобы реализовать библиотеку, понадобилось также несколько промежуточных типов.\\\indent
Итак, нетерминалы типа NTerm задаются с помощью правил вида:\\\indent
NTerm<Тип токена, тип атрибута> Нетерминал = Альтернатива | Альтернатива | ...;\\
где тип токена --- это перечисление, состоящее из тэгов терминальных символов. Тип атрибута --- это тип атрибута нетерминала (число или указатель на дерево разбора и т. д.) или просто void, если атрибута нет. Нетерминал --- это имя нетерминала, глобальная переменная.\\\indent
Альтернатива --- это правило, задающееся в виде:\\\indent
Rule() <{}< элемент <{}< элемент... [<{}< функция обработки],\\
где Rule() - это маркер начала правила, а элементом может быть нетерминал или терминал. У терминала также может быть атрибут, тогда терминал задаётся в виде:\\\indent
Term<тип атрибута>(значение типа токена),\\
а может и не быть, тогда терминал просто задаётся значением типа токена.\\\indent
Функция обработки (семантическое действие) должна возвращать значение типа атрибута нетерминала и принимать значения атрибутов, представленных в данной альтернативе (как нетерминалами с непустым типом атрибута, так и терминалами с атрибутами). Функция обработки может отсутствовать, если нетерминал имеет пустой (void) атрибут и элементы в альтернативе атрибутов не несут, или если нетерминал имеет непустой атрибут и только один элемент несёт атрибут, причём типы атрибутов должны совпадать. Атрибут нетерминала получает значение атрибута элемента.\\\indent
От класса Lexer<Тип токена>, где тип токена --- это перечисление, пользователь должен унаследовать свой класс, осуществляющий лексический анализ входной последовательности символов. В этом классе должен быть переопределён виртуальный метод класса nexttoken(), возвращающий значение типа Token<Тип токена>*, если у текущего токена нет атрибутов, и AttrToken<Тип токена, тип атрибута>*, если они есть (AttrToken --- наследник класса Token). При вызове оператора new для данных типов в качестве параметров конструктору соответствующего класса должны передаваться параметры (Тип токена, координаты токена) --- для класса Token и (Тип токена, тип атрибута, координаты токена) --- для класса AttrToken, где координаты имеют тип Coord.\\\indent
Структура Coord имеет три поля: file типа std::string --- для указания имени файла, парсинг которого осуществляется, line и col типа int --- для определения номера строки и номера столбца во входном файле (координат токена).
\subsection[Внутреннее устройство библиотеки]{\large Внутреннее устройство библиотеки }
\hspace{\parindent}
Для сохранения правил определены следующие структуры. GeneralizedSymbol является общим представлением для терминальных и нетерминальных символов. SeqInfo хранит цепочку, состоящую из GeneralizedSymbol, которая идентифицирует правую часть правила, и указатель на функцию, выполняющую семантическое действие. AltInfo хранит для правил с одинаковым нетерминалом в левой части альтернативы левых частей (листинг~\ref{list:lib}).\\\indent
{
\singlespacing
\begin{lstlisting}[label=list:lib, caption=Структуры для сохранения правил]
struct Action {
virtual void changeStack(Stack&) = 0;
virtual ~Action() {}
};
template <typename TokenType>
struct AltInfo;
template <typename TokenType>
struct GeneralizedSymbol
{
bool isTerm;
AltInfo<TokenType> *nterm;
TokenType term;
};
template <typename TokenType>
struct SequenceInfo
{
std::vector<GeneralizedSymbol<TokenType>> symbols;
Action *action;
};
template <typename TokenType>
struct AltInfo
{
std::vector<SequenceInfo<TokenType>> alt;
};
\end{lstlisting}
}
\clearpage
\newpage
\section[Релизация LALR(1) анализатора]{\large \centering Релизация LALR(1) анализатора}
\hspace{\parindent}
Существуют различные алгоритмы синтаксического анализа: восходящие и нисходящие, с предпросмотром - и без. Один из алгоритмов - это LALR(1) (look ahead left-to-right) алгоритм. Как можно понять из названия, это алгоритм с предпросмотром одного символа, при котором строится правый вывод. Данный алгоритм относится к классу восходящих, он является подмножеством LR(1) (без предпросмотра), реализующий более компактную таблицу переходов. Класс грамматик, разбираемых по LALR(1) шире, чем класс SLR(1)-грамматик. При этом большинство реально используемых языков программирования имеют LALR(1)-грамматики, поэтому алгоритм имеет практическое применение, например, в генераторе синтаксических анализаторов yacc и его производных, таких как GNU bison.\\\indent
Восходящий синтаксический анализ можно рассматривать как процесс <<свертки>> строки к стартовому символу грамматики по приведённым правилам. На каждом шаге <<свертки>> определённая подстрока, соответствующая правой части правила, заменяется нетерминалом из левой части. Синтаксический LALR(1)-анализ представляет собой разновидность восходящего анализа, в которой для хранения состояний используется стек, а для хранения остающейся непроанализированной части входной строки --- входной буфер. При этом анализатор может выполнять всего четыре действия: перенос очередного состояния на вершину стека, свертку по определенному правилу, принятие, то есть успешное завершение анализа, и выдача сообщения об ошибке \cite{lalr}. Сам LALR(1) анализ можно логически разбить на три этапа: построение множества пунктов, таблиц ACTION и GOTO и непосредственно сам алгоритм с использованием этих таблиц.
\subsection[Построение множества пунктов]{\large Построение множества пунктов}
LR-анализатор принимает решение о выборе <<перенос-свёртка>>, поддерживая состояния, идентифицирующие положение в процессе синтаксического анализа. Состояние представляет собой множество пунктов. Пункт --- это правило с точкой в некоторой позиции правой части и терминалы, которые могут стоять на позиции точки. Интуитивно, пункт указывает, какая часть правила уже просмотрена с данный момент.\\\indent
Для определения терминалов, имеющих возможность стоять на позиции точки, реализована фукция First(a), где а - это строка, состоящая из терминальных и нетерминальных символов. First(a) возвращает множество терминалов, с которых могут начинаться строки, порождённые a.\\\indent
Состояния строятся с помощью функции Closure, находящей замыкание множества пунктов. Смысл замыкания в том, что если в пункте за точкой следует нетерминал, мы добавляем к состоянию все правила для этого нетерминала, включая в перечень терминалов, которые могут стоять на позиции точки, First от цепочки символов, следующей за нетерминалом в изначальном пункте. Самое первое состояние представляет собой замыкание для одного пункта. В этом пункте правило --- вывод из нового стартового символа исходного стартового символа, точка находится в нулевом полодении, а в перечне последующих нетерминалов содержится лишь символ конца ввода. Последующие состояния строятся с помощью функции Goto --- замыканием множеств пунктов, образующихся при получении того или иного терминального или нетерминального символа\\indent
Для представления пунктов в библиотеке используется следующая структура (листинг~\ref{list:item}).
{
\singlespacing
\begin{lstlisting}[label=list:item, caption=Структура для представления пункта]
struct Item
{
SequenceInfo<TokenType>* seqInfo;
AltInfo<TokenType>* altInfo;
std::unordered_set<GeneralizedSymbol<TokenType>> nextTerms;
int cursor;
...
};
\end{lstlisting}
}
При этом altInfo определяет нетерминал из левой части правила, seqInfo --- последовательность из правой части правила, cursor --- позицию точка, а nextTerms --- множество терминалов, которые могут находиться на позиции за точкой.\\\indent
Можно объединить состояния, имеющие одинаковые поля seqInfo, altInfo и cursor, слив при этом наборы nextTerms. Таким образом мы получим редуцированное множество пунктов. При подобном редуцировании возможно лишь появление конфликта типа <<свёртка-свёртка>>.
\subsection[Построение таблиц Action и Goto]{\large Построение таблиц Action и Goto}
Для редуцированных состояний создаются таблицы Action и Goto. Первая определяет действие, совершаемое при получении нового токена: перенос, свёртка, принятие или ошибка. Вторая определяет состояние, в которое мы перейдём при той или иной свёртке. Алгоритм построения данных таблиц приведён ниже (Рис. \ref{ris:conv1}).
\begin{figure}[h!]
\center{\includegraphics[width=0.7\linewidth]{alg.png}}
\caption{Алгоритм построения Goto и Action}
\label{ris:conv1}
\end{figure}
Конфликт — это когда мы не можем заполнить таблицу action[]. Например, если во множестве Ii есть пункт [A → x·ay, b] и пункт [B → z·, a], то имеем конфликт «перенос-свёртка» (между переносом a в первом случае и свёрткой B → z во втором). В этом случае грамматика не является LR(1) — надо кидать исключение о том, что грамматика не верна.
В незаполненные ячейки action[] автомат попадает при синтаксических ошибках во входном потоке. Тоже надо кидать исключение, когда при разборе грамматики туда попадём
\subsection[Алгоритм LALR(1)]{\large Алгоритм LALR(1)}
Этот алгоритм использует стек состояний и стек атрибутов. Для того, чтобы в стеке атрибутов могли храниться значения любых типов, но при этом выбрасывалось исключение при несоответствии в правиле атрибутов символов и параметров функции, отвечающей за семантическое действие, используется тип, аналогичный типу Any (листинг~\ref{list:anyhold}).
{
\singlespacing
\begin{lstlisting}[label=list:anyhold, caption=Тип AnyHolder]
struct AnyHolder {
virtual ~AnyHolder() {}
};
template <typename T>
struct AnyHolderT: public AnyHolder
{
T value;
AnyHolderT(const T& new_value) :
value(new_value)
{
/* пусто */
}
};
struct Stack {
std::vector<AnyHolder*> s;
public:
template <typename Attr>
void popBack(Attr& item)
{
if (s.empty())
throw StackError("Stack is empty");
AnyHolderT<Attr> *h;
if ((h = dynamic_cast<AnyHolderT<Attr>*>(s.back())) == 0)
throw StackError("Bad type");
item = h->value;
s.pop_back();
delete h;
}
...
};
\end{lstlisting}
}
Если во входном тексте есть синтаксические ошибки, то тоже выбрасывается исключение, содержащее информацию о позиции ошибки.
\subsection[Разница между LALR(1) и SLR]{\large Разница между LALR(1) и SLR}
В отличие от алгоритма SLR, пункты представляют собой не только правило+позиция, но также содержат множество символов, следующих за данным нетерминалом. В ряде случаев LALR(1) работает тогда, когда построение SLR(1) таблицы разбора для данной грамматики невозможно из-за конфликтов <<сдвиг-свертка>> или <<свертка-свертка>>.
\clearpage
\newpage
\section[Сравнение реализованной библиотеки с GNU bison на примере простого языка]{\large \centering Сравнение реализованной библиотеки с GNU bison на примере простого языка}
\hspace{\parindent}
\subsection[Обзор GNU bison]{\large Обзор GNU bison}
\hspace{\parindent}
GNU bison — программа, предназначенная для автоматической генерации синтаксического анализатора по заданному описанию грамматики. Программа bison относится к свободному ПО, разработана в рамках проекта GNU и портирована под все традиционные операционные системы. Bison используется для описания грамматики, построенной на базе алфавита токенов, и используется для генерации программы (кода на языке C, C++ или Java), которая получает на вход поток токенов и находит в этом потоке структурные элементы (нетерминальные токены) согласно заданной грамматике \cite{bison}.
\subsection[Сравнительный анализ выразительных возможностей реализованной библиотеки и GNU bison]{\large Сравнительный анализ выразительных возможностей реализованной библиотеки и GNU bison}
\hspace{\parindent}
\newpage\newpage
\part*{\large \centering ЗАКЛЮЧЕНИЕ}
\addcontentsline{toc}{part}{ЗАКЛЮЧЕНИЕ}
В данной курсовой работе были рассмотрены основные подходы к использованию метапрограммирования шаблонов. С использованием данных подходов была создана библиотека, генерирующая по заданной грамматике синтаксический LALR(1) анализатор, а также EDSL этой библиотеки для задания самой грамматики. Также была проведена сравнительная характеристика в плане выразительных возможностей на примере простого языка реализованной библиотеки и генератора синтаксических анализаторов Bison.
\clearpage
\newpage
\bibliographystyle{utf8gost705u} %% стилевой файл для оформления по ГОСТу
\begin{flushleft}
\bibliography{biblio} %% имя библиографической базы (bib-файла)
\end{flushleft}
\end{document} % конец документа