Разработка и реализация простейшего компилятора

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждениевысшего образования

«Тольяттинский государственный университет»

ИНСТИТУТ МАТЕМАТКИ, ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Кафедра « ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА»

Мобильные и сетевые технологии (направленность (профиль)

Курсовая работа

По дисциплине (учебному курсу)

Теоретические основы информатики

На тему Разработка и реализация простейшего компилятора по заданному варианту исходных данных №13

Студент Скоков С.А.

(И.О. Фамилия)

Руководитель Кузьмичев А.Б.

(И.О. Фамилия)



Задание на выполнение курсовой работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение высшего образования

«Тольяттинский государственный университет»

ИНСТИТУТ МАТЕМАТИКИ, ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ (наименование института полностью)

Кафедра « Прикладная математика и информатика»

(наименование кафедры полностью)

Утверждаю

Зав. кафедрой

(подпись) (И.О. Фамилия)

«____»___________20___г.

Студент Скоков Сергей Александрович.

1. Тема работы: Разработка и реализация простейшего компилятора по заданному варианту исходных данных №13

2. Срок сдачи студентом законченной курсовой работы 27.12.2018

3. Исходные данные к курсовой работе исходные данные по варианту №14

4. Содержание расчетно-пояснительной записки(подлежащих разработке вопросов, разделов) введение, разработка таблицы идентификаторов, разработка лексического анализатора, разработка синтаксического анализатора, разработка генератора результирующего кода, заключение, список использованных источников, приложение

5. Ориентировочный перечень графического и иллюстративного материала пояснительная записка (25-40 стр.)

6. Рекомендуемые учебно-методические материалы

Молчанов А.Ю. Системное программное обеспечение: Учебник для вузов. 3-е изд. -СПб.: Питер, 2010 - 400с. ил.

Серебряков В.А. Теория и реализация языков программирования. Учебное пособие./ В.А. Серебряков, М.П. Галочкин, Д.Р. Гончар, М.Г. Фурутян. - М.М.) Пресс, 2006 - 352 с. ил.

Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум. - СПб.: Питер, 2005 -284 с. ил.

7. Дата выдачи задания «20» сентября 2018г.

Руководитель курсовой работы	_____________________ (подпись)	Кузьмичев А.Б. (И.О. Фамилия)
Задание принял к исполнению	_____________________ (подпись)	Скоков С.А. (И.О. Фамилия)

Календарный план

№	Этапы выполнения	% выполнения	Сроки выполнения по этапам	Отметка о выполнении этапа (дата. подпись)
1	Выбор способа описания таблицы идентификаторов и программная реализация выбранного способа	5%	21.09.19
2	Построение лексического анализатора	25%	23.09.19
3	Программная реализация лексического анализатора	5%	27.09.19
4	Построение матрицы предшествования по заданной грамматики	5%	14.10.19
5	Программная реализация синтаксического анализатора	30%	16.10.19
6	Реализация генератора результирующего кода	18%	20.10.19
7	Отладка программы	2%	21.10.19
8	Подготовка пояснительной записки	10%	22.10.19



Содержание

Введение

1. Описание исходных данных для курсовой работы

1.1 Задание по курсовой работе

1.2 Описание грамматики входного языка

2. Разработка лексического анализатора

2.1 Описание выбранного способа организации таблицы идентификаторов

2.2 Описание конечного автомата лексического анализатора

2.3 Описание и разработка лексического анализатора

2.4 Выбор метода взаимодействия лексического анализатора с синтаксическим разборщиком

3. Разработка синтаксического разборщика

3.1 Разработка матрицы предшествования

3.2 Разработка синтаксического разборщика на основе матрицы предшествования

4. Разработка генератора результирующего кода

4.1 Выбор и описание форм внутреннего представления программы, используемых в компиляторе

4.2 Интеграция разработанных компонент в компилятор

4.3 Описание разработанного компилятора

Заключение

Список используемых источников

Приложение



Введение

Компилятор - программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.

Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером.

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

Компилятор состоит из следующих составных частей:

1. Генератор таблицы идентификаторов.

2. Лексический анализатор.

3. Синтаксический разборщик.

4. Генератор результирующего кода.

Для построения компилятора рекомендуется использовать методы, освоенные в ходе выполнения практических работ по курсу «Теоретические основы информатики».

Результатами курсовой работы являются программная реализация заданного компилятора и пояснительная записка, оформленная в соответствии с требованиями стандартов и задания на курсовую работу.

Актуальность данной работы состоит, в основном, в получении практических навыков разработки системного программного обеспечения. Навыки, полученные в ходе данной курсовой работы, являются необходимыми для любого специалиста в IT-сфере.



1. Описание исходных данных для курсовой работы

1.1 Задание по курсовой работе

Вариант 13: Входной язык компилятора должен удовлетворять следующим требованиям:

1. Входная программа может быть разбита на строки произвольным образом, все пробелы и переводы строки должны игнорироваться компилятором.

2. Текст входной программы может содержать комментарии любой длины, которые должны игнорироваться компилятором (вид комментария может выбран по усмотрению исполнителя работы и согласован с преподавателем при утверждении задания).

3. Должны быть предусмотрены следующие варианты операторов входной программы.

3.1 Оператор присваивания вида <переменная>:=<выражение>;

3.2 составной оператор вида {… };

3.3 оператор условия оператора: if < выражение > then < оператор >;

4. Выражения в операторах должны содержать следующие операции.

4.1 Арифметические операции сложения (+), вычитания (-), умножения (*), деления (/);

4.2 операции сравнения «меньше» (<), «больше» (>), «равно» (=);

5. Операндами в выражениях могут выступать идентификаторы (переменные) и константы.

6. Все идентификаторы, встречающиеся в исходной программе, должны восприниматься как переменные, имеющие тип данных «char» (предварительного описания идентификаторов в исходной программе не требуется).

7. Приоритет операций исполнитель работы должен выбрать самостоятельно (приоритет операций учитывается в грамматике входного языка). Для изменения приоритета операций должны использоваться круглые скобки.

1.2 Описание грамматики входного языка

Входной язык состоит из следующих лексем:

Ключевые слова: if, then;

Разделители: точка с запятой «;», открывающая и закрывающая круглые скобки «()»;

Идентификаторы: произвольная последовательность букв латинского алфавита верхнего и нижнего регистров;

Знаки сравнения: «<,>,=»;

Знак присваивания: «:=»;

Знаки операций: «+, -, *, /»;

Границами лексем служат пробел, знак табуляции, знак перевода строки и возврата каретки, разделители, знаки сравнения, присваивания и операций.

Комментарием в программе считается любая последовательность любых символов, заключённая между символами { и }.

Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

Исходная грамматика в форме Бэкуса-Наура выглядит следующим образом:

G({if, then, a, +, -, *, /,:=, <, >, =, (, ), ;},{S, F,C, T, E,D}, P, S) с правилами P:

S > F;

F > if E then C | a := C

C> C+T|C-T | T

T> T*D|T/D|D

D >a | (E)

E > D < D | D > D | D = D

В результате была представлена исходная грамматика входного языка в форме Бэкуса-Наура. Входной язык содержит логические выражения, разделённые символом ; (точка с запятой). Логические выражения состоят из идентификаторов, знака присваивания (:=), знаков операций: +, -, *, /, знаков сравнения <,>,=, знака присваивания := и круглых скобок, а также условных операторов if, then.

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



2. Разработка лексического анализатора

2.1 Описание выбранного способа организации таблицы идентификаторов

Установим перед собой задачу разработки генератора таблиц идентификаторов и выберем способ организации данной таблицы.

Для этого будем определять индекс элемента в таблице путем применения к нему алгоритма хэширования.

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

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

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

- вычисляется достаточно быстро;

- сводит к минимуму число коллизий

В качестве хэш-функция была выбрана функция:



h(a)=i mod 401

Данный выбор продиктован тем, что процент коллизий для данной хэш-функции составил всего 17%, что подходит для нашей дальнейшей работы. Программный модуль, рассчитывающий процент коллизий для данной хэш-функции приведен в приложении А под именем «Col.cpp».

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

Результат работы данного модуля приведен в таблице 1. С разработанным модулем можно ознакомиться в приложении А. Данный моудль приведен под именем «Analysis.cpp».

Таблица 1 - Сравнение количества тактов для разных способов разрешения коллизий.

Количество идентификаторов	Процент заполнения таблицы	Количество итераций по методу простого рехеширования	Количество итераций по методу рехеширования с использованием псевдослучайных чисел
100	25%	104	105
200	50%	222	232
300	75%	422	471
400	100%	2094	2402

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

Алгоритм данного метода приведен на рисунке 1.



Рисунок 1 -- Метод простого рехеширования.

Таким образом был проведен выбор метода организации таблицы идентификаторов, определена хеш-функция и метод избавления от коллизий а так же рассмотрен алгоритм выбранного метода.

2.2 Описание конечного автомата лексического анализатора

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

Лексемы входного языка могут иметь следующие типы:

Идентификаторы: произвольная последовательность букв латинского алфавита верхнего и нижнего регистров;

Ключевые слова (if, then);

Разделители (точка с запятой, открывающая и закрывающая круглые скобки);

Знаки сравнения (>,<,=);

Знак операции присваивания;

Знаки операций арифметических действий (+,-,*,/);

Лексический анализатор построен на основе конечного автомата.

На рисунке 2 и 3 представлен граф конечного автомата в двух частях. На рисунке 2 представлен граф для распознавания всех лексем, кроме ключевых слов, а на рисунке 2 представлен граф для ключевых слов.

На рисунках используются следующие условные обозначения:

S - начальное состояние;

F -- функция для обработки данных в таблице лексем, которая может принимать аргументы а или v;

а -- текущий символ;

v -- накапливаемая переменная;

H -- непечатаемые символы (перенос строки, возврат каретки, табуляция, пробел и т.п.);

Б - буквы латинского алфавита;

Б(*) - буквы латинского алфавита, кроме тех, что указаны в скобках

G - состояние знака присваивания;

V - состояние идентификатора;

C -- состояние комментария;

I1 -- состояние для ключевого слова if;

T1,T2,T3--состояние для ключевого слова then;

Рисунок 2 -- Первая часть конечного автомата лексического анализатора в виде ориентированного графа



Рисунок 3 -- Вторая часть конечного автомата лексического анализатора

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

2.3 Описание и разработка лексического анализатора

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

Лексический анализ осуществляется при помощи ранее описанного нами конечного автомата (рисунки 2-3).

Принцип работы лексического анализатора состоит в следующем. На вход из файла подается текст исходной программы. Затем происходит считывание файла по одному символу и вызов функции лексического анализа, принцип работы которой указан в блок-схеме на рисунке 5.

После окончания работы анализатора создаётся файл «Lexem Table.txt», содержащий список лексем с определением их типа. На рисунке 4 показан пример содержимого файла при успешном выполнении лексического анализа.

Рисунок 4. Результат работы лексического анализатора

Рисунок 5 -- Работа лексического анализатора

С программной реализацией данного модуля можно ознакомиться в приложении А. Данный модуль приведен под именем «Lexx.cpp».

Таким образом, был разработан алгоритм работы лексического анализатора, в котором происходит посимвольное считывание текста исходной программы до тех пор, пока не закончит свою работу.

2.4 Выбор метода взаимодействия лексического анализатора с синтаксическим разборщиком

Лексический анализатор и синтаксический разборщик могут работать последовательно или параллельно.

При успешном прохождении лексического анализа в программу передаются таблица лексем и таблица идентификаторов.

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

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

Так как данный способ взаимодействия лексического и синтаксического анализатора проще в реализации, чем параллельный именно его и будем использовать в разработке компилятора.

На следующей схеме представлен способ последовательного взаимодействия синтаксическим анализатор (рисунок 6).



Рисунок 6 -Последовательный способ взаимодействия лексического и синтаксического анализатора

В разработанном компиляторе лексический анализатор сначала записывает всех найденные лексемы в таблицу лексем (файл «Lex_Table.txt) и заканчивает свою работу, после чего из этого файла лексемы считывает синтаксический разборщик. Сделано это для того, чтобы, в случае возникновения ошибок в работе компилятора можно было проще отследить на каком этапе работы произошла ошибка

Таким образом, был описан метод взаимодействия лексического анализатора с синтаксическим разборщиком.



3. Разработка синтаксического разборщика

3.1 Разработка матрицы предшествования

Для построения синтаксического анализатора используется алгоритм «сдвиг-свертка» с восходящей грамматикой. Мы можем представить себе этот процесс как "свертку" исходной строки к стартовому нетерминальному символу грамматики.

Исходная грамматика изначально представлена в форме Бэкуса-Наура:

G({if, then, a, +, -, *, /,:=, <, >, =, (, ), ;},{S, F,C, T, E,D}, P, S) с правилами P:

S > F;

F > if E then C | a := C

C> C+T|C-T | T

T> T*D|T/D|D

D >a | (E)

E > D < D | D > D | D = D

Прежде чем приступить к синтаксическому анализу, необходимо построить матрицу операторного предшествования. А для построения матрицы операторного предшествования сначала нужно построить множество крайних правых и крайних левых нетерминальных символов. На первом шаге берутся все крайние левые и крайние правые символы из правил конечной грамматики G. Полученное множество показано в таблице 2.

Таблица 2: Множество крайних правых и крайних левых нетерминальных символов

Символ U	L(U)	R(U)
S	F	;
F	If,a	C
C	C,T	T,
T	T,D	D
D	a,(	a,)
E	D	D

Эта таблица не является конечной, так как множество L(U) для символов S содержит другие терминальные символы, поэтому они должны быть дополнены. Результат представлен в таблице 3.

Таблица 3: Дополненное множество крайних правых и крайних левых нетерминальных символов

Символ U	L(U)	R(U)
S	F, if, a	;
F	If,a	C,T
C	C,T,D,a	T,D,a
T	D, a	D, a
D	a	D,a
E	D,a	D,a

Теперь необходимо построить множество крайних левых и крайних правых терминальных символов. Результат представлен в таблице 4.

Таблица 4: Множество крайних левых и крайних правых терминальных символов

Символ U	Lt(U)	Rt(U)
S	If,a,;	;
F	If,a	then,:=,+,-,*,/
C	+,-,*,/,a,(	+,-,*,/,a,)
T	*,/,a,(	*,/,a,)
D	a,(	a,)
E	<,>,=,a,(	<,>,=,a,)

Теперь необходимо заполнить матрицу предшествования. Для этого мы используем множества крайних левых и правых символов и правила грамматики G. Матрица предшествования предоставлена в таблице 5.



Таблица 5: Матрица предшествования

+

-

/

*

(

)

a

:=

;

if

then

<

>

=

?к

+

>.

>.

<.

<.

<.

>.

<.

>.

<.

>.

-

>.

>.

<.

<.

<.

>.

<.

>.

<.

>.

/

>.

>.

>.

>.

<.

>.

<.

>.

<.

>.

*

>.

>.

>.

>.

<.

>.

<.

>.

<.

>.

(

<.

<.

<.

<.

<.

=.

<.

<.

>.

<.

<.

<.

)

>.

>.

>.

>.

>.

>.

>.

<.

<.

>.

>.

>.

a

>.

>.

>.

>.

>.

>.

=.

>.

<.

>.

<.

<.

<.

:=

<.

<.

<.

<.

<.

<.

>.

>.

;

>.

if

<.

<.

<.

=.

then

>.

>.

>.

>.

<.

>.

<.

>.

>.

>.

>.

>.

<

<.

>.

<.

>.

>.

>

<.

>.

<.

>.

>.

=

<.

>.

<.

>.

>.

?н

<.

<.

<.

<.

<.

<.

<.

<.

Отношения предшествования обознаются знаками «=·», «<·» и «·>». Отношение предшествования зависит от того, в каком порядке стоят символы. Если между терминальными символами нет отношения, то ячейка матрицы остаётся пустой.

На основе конечной грамматики G была построена остовная грамматика: лексический анализатор программа компилятор

G`({if, then, a, +, -, *, /,:=, <, >, =, (, ), ;},{E}, P`, E) с правилами P`:

E > E; - правило 1;

E > if E then E | a := E правила 2 и 3;

E> E+E|E-E | E правила 4, 5 и 6;

E> E*E|E/E|E правила 7, 8 и 9

E >a | (E) правила 10 и 11

E > E < E | E > E | E = E правила 12, 13, 14

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

3.2 Разработка синтаксического разборщика на основе матрицы предшествования

Синтаксический анализатор получает на входе цепочку из лексем, осуществляет проверку на правильность синтаксических конструкций, используя матрицу операторного предшествования, затем преобразует их в список правил. Синтаксический анализ выполняется по алгоритму «перенос-свертка» с восходящей грамматикой.

Перед началом разбора формируется входная цепочка из структур лексем, стек, списков правил, в конец входной цепочки помещается символ, в стек помещается начальный символ. Далее выполняется цикл, алгоритм которого изображен на рисунке 7. Весь процесс разбора выводится в файл Syntax.txt. Содержимое файла продемонстрировано на рисунке 8.

Рисунок 7. Алгоритм синтаксического разбора



Рисунок 8 -- Результат работы синтаксического разборщика

С программной реализацией данного модуля можно ознакомиться в приложение А. Данный модуль приведен под именем «GenTr».

Таким образом была описана разработка матрицы предшествования для реализации синтаксического анализатора путём применения алгоритма «сдвиг-- свёртка» и рассмотрена реализация синтаксического анализатора в программе.

В результате третьего раздела было рассмотрено построение синтаксического разборщика, описана его реализация.



4. Разработка генератора результирующего кода

4.1 Выбор и описание форм внутреннего представления программы, используемых в компиляторе

Известны следующие формы внутреннего представления программ:

Структуры связных списков, представляющие синтаксические деревья.

Многоадресный код с неявно именуемым результатом (триады);

Обратная (постфиксная) польская запись операций;

Ассемблерный код или машинные команды.

При сравнении с другими формами внутреннего представления триады обладают следующими преимуществами:

Являются линейной последовательность операций, в отличие от синтаксического дерева, и потому проще преобразуются в результирующий код.

Занимают меньше памяти, чем тетради, дают больше возможностей по оптимизации программы, чем обратная польская запись.

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

Триада - это запись любой операции в форме, содержащей три составляющих: <операция>(<операнд1>, <операнд2>). Каждый из операндов или оба сразу могут являться указателями на другую триаду, и в таком случае в качестве операндов выступает результат выполнения триады, на которую ссылаются операнды.

Таким образом, основываясь данными преимуществами триад перед другими формами представления, сделаем выбор в их пользу и будем применять в компиляторе именно эту форму внутреннего представления.

Описание разработанного алгоритма порождения результирующего кода

Сначала считывается строка из исходного кода, определяются операции и порядок их выполнения, а также операнды, которые участвуют в этих операциях. Затем, функция выводит триады в текстовый файл, название которого указано в качестве второго ключа при запуске компилятора. Если операнд ссылается на предыдущую триаду, то для обозначения операнда используется конструкция «T» с номером соответствующей триады.

Пример дерева операций для входных данных представлен на рисунке 9. Пример получившегося файла представлен на рисунке 10. На вход был подан следующий код:

a:=f/c*e-b+d;

Рисунок 9 -- Дерево операций для входных данных.



Рисунок 10 -- Результат работы генератора результирующего кода

С программной реализацией данного метода можно ознакомиться в приложении А. Данный модуль приведен под именем «Syntax.txt».

Таким образом, был приведен пример преобразования входной программы в триады. В дальнейшем эти триады можно использовать для преобразования результирующего кода в машинный язык, к примеру, на языке Ассемблера.

4.2 Интеграция разработанных компонент в компилятор

Для того, чтобы собрать разрабатываемый нами компилятор, нужно интегрировать все созданные в предыдущих подразделах компоненты в единый файл. Для это все необходимые компоненты были реализованы в виде функций и представлены в одном файле «Compiler_S_S_A.cpp».

Помимо этого все составные компоненты компилятора были вынесены в отдельные файлы и имеют формат .cpp. Компилятор не нуждается в подключении файлов формата .hpp, так как все его составные части реализованы в виде функций в одном коде. Структура компилятора приведена в таблице 6.



Таблица 6. Структура компилятора.

Название файла	Назначение файла
Compiler_S_S_A.cpp	Исходный файл, в который интегрированы все главные модули и реализована логика программы.
GenID.cpp	Исходный файл, содержащий код генератора идентификаторов.
Lexx.cpp	Исходный файл, содержащий код лексического анализатора.
Syntax.cpp	Исходный файл, содержащий код синтаксического разборщика
GenTr.cpp	Исходный файл, содержащий код генератора триад
Col.cpp	Исходный файл, содержащий код дополнительного модуля расчета процента коллизий
Analysis.cpp	Исходный файл, содержащий код дополнительного модуля расчета эффективности методов разрешения коллизий.
Comment_check.cpp	Исходный файл, содержащий код модуля проверки комментариев
LSort.cpp	Исходный файл, содержащий код дополнительного модуля сортировка таблицы лексем
File1.txt	Текстовый файл, содержащий входные данные для компилятора.
ID.txt	Текстовый файл, содержащий таблицу идентификаторов
Lexem_Table.txt	Текстовый файл, содержащий таблицу лексем
LexTabSort.txt	Текстовый файл, содержащий отсортированную таблицу лексем

Продолжение таблицы 6.Структура компилятора.

Syntax.txt	Текстовый файл, содержащий результат работы синтаксического анализатора.
Rezult.txt	Текстовый файл, содержащий результат работы компилятора в виде триад. Необходим для указания в качестве второго ключа
Man.txt	Описание компилятора

Таким образом был описан способ интеграции исходных компонентов в итоговую программу, описан разработанный компилятор, перечислены создаваемые в процессе компиляции файлы.

4.3 Описание разработанного компилятора

Для запуска компилятора необходимо запустить командую строку либо терминал и указать исполнительный файл Compiler_S_S_A.exe и два текстовых файла (по умолчанию File1.txt и Rezult.txt). В первом ключе должны быть указаны исходные данные для работы компилятора, а во второй программа выведет результат работы. Пример команды для запуска компилятора:

Compiler_S_S_A File1 Rezult

Для вывода полного описания компилятора следует ввести команду Compiler_S_S_A man

Пример вывода приведен на рисунке 11.

Рисунок 11.Вывод информации о компиляторе

Таким образом была описан разработанный компилятора и приведены пояснения к команде, необходимой для запуска и корректной работы компилятора.



Заключение

В результате выполнения курсовой работы были выявлены и реализованы основные шаги при разработке компилятора:

Разработка таблицы идентификаторов;

Разработка лексического анализатора;

Разработка синтаксического разборщика;

Разработка программного модуля генерации результирующего кода.

В разделе 1 были описаны исходные данные для курсовой работы

В подразделе 1.1 было изложено задание на курсовую работу. Оно состоит в разработке простейшего компилятора по заданной контекстно-зависимой грамматике.

В подразделе 1.2 была описана заданная грамматика входного языка.

В разделе 2 был описан и разработан лексический анализатор и всё необходимое для его работы.

В подразделе 2.1 был определен оптимальный метод организации таблицы идентификаторов и подобрана хеш-функция, подходящая для выполнения данной курсовой работы.

В подразделе 2.2 был описан и разработан конечный автомат лексического анализатора. Данный конечный был представлен в графическом виде на рисунках 1 и 2.

В подразделе 2.3 был описан и разработан лексический анализатор.

В подразделе 2.4 были описан и выбран оптимальный метод взаимодействия лексического анализатора с синтаксическим разборщиком, нужный для выполнения данной курсовой работы.

В разделе 3 был разработан и описан синтаксический разборщик.

В подразделе 3.1 на основе множеств крайних левых и крайних правых терминальных символов была разработана матрица предшествования.

В подразделе 3.2 был разработан синтаксический разборщик на основе матрицы предшествования.

В разделе 4 был разработан и описан генератор результирующего кода, способы интеграции отдельных модулей в компилятор и был описан сам компилятор.

В подразделе 4.1 был обоснован выбор формы внутреннего представления программы.

В подразделе 4.2 был описан метод построения триад и приведены примеры дерева входных данных и результат работы генератора результирующего кода.

В подразделе 4.3 был описан метод интеграции модулей в компилятор и описана файловая структура компилятора.

В подразделе 4.4 были приведены пояснения к команде, необходимой для запуска компилятора и описаны действия компилятора во время работы.

Таким образом, в ходе выполнения данной курсовой работы были выполнены все необходимые шаги и отработаны теоретические и практические навыки для разработки простейшего компилятора.



Список используемых источников

1. Молчанов А. Ю. Системное программное обеспечение [Текст]: Учебник для вузов. 3-е изд. - СПб.: Питер, 2010. - 400 с.: ил.

2. Молчанов А. Ю. Системное программное обеспечение [Текст]: Лабораторный практикум. - СПб.: Питер, 2005. - 284 с.: ил.

3. Конечный автомат: теория и реализация

4. Основные принципы работы синтаксического анализатора

5. Compiler Explorer is an interactive online compiler which shows the assembly output of compiled C++, Rust, Go (and many more) code.



Приложение

К курсовой работе прилагается CD-диск, на котором находятся все файлы, необходимые для работы компилятора. Также на диске расположены «List», в котором листинг всего компилятора представлен в виде текста. Назначение остальных файлов, записанных на диске приведено в параграфе 4.3 На рисунке 12 представлено содержимое прилагаемого диска.

Пример входной программы записан на диске в файле «File1.txt», а результат в файле «Rezult.txt».

Рисунок 12 -- Содержимое диска

Размещено на Allbest.ru