Учебная работа. Реферат: Построение отдельных фаз компиляции

(Пока оценок нет)

Загрузка...

Учебная работа. Реферат: Построение отдельных фаз компиляции

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

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

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

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

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

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

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

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

1. Организация таблицы идентификаторов

1.1. Начальные данные

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

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

1.2. Предназначение таблицы идентификаторов

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

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

1.3.
способ бинарного дерева

Данный способ организует таблицу идентификаторов в форме бинарного дерева. Любой узел этого дерева представляет собой элемент таблицы идентификаторов, при этом корневым узлом становится 1-ый элемент, встреченный компилятором во входном тексте. Дерево именуется бинарным, потому что любая верхушка в нем может иметь не наиболее 2-ух вершин (для определенности употребляют понятия «правая» и «левая» ветки). Схема метода прибавления идентификатора приведена на рис. 1.1.

Рис. 1.1. Схема метода прибавления идентификатора

Схема метода поиска идентификатора приведена на рис. 1.2.

Рис. 1.2. Схема метода поиска идентификатора

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

1.4. способ
цепочек

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

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

Схема метода прибавления идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема метода прибавления идентификатора

Схема метода поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема метода поиска идентификатора

Плюсы данного способа:

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

— любому идентификатору соответствует строго одна ячейка в таблице идентификаторов.

Недочетом способа является организация работы с динамическими массивами.

1.5. Результаты сопоставления способов

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

На рис. 1.5 представлена экранная форма организации таблицы идентификаторов способом цепочек и способом бинарного дерева.

Рис. 1.5. Экранная форма организации таблицы идентификаторов

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

При добавлении новейшего идентификатора вероятны два варианта:

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

— добавляемый идентификатор в таблице идентификаторов уже существует, в поле ошибок выводится соответственное сообщение, указывается выполненное число сравнений для обнаружения повтора идентификатора по любому способу.

Экранная форма прибавления новейшего идентификатора представлена на рис. 1.6.

Рис. 1.6. Экранная форма прибавления новейшего идентификатора

Экранная форма прибавления имеющегося идентификатора представлена на рис. 1.7.

Рис. 1.7. Экранная форма прибавления имеющегося идентификатора

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

При поиске идентификатора также вероятны два варианта:

— разыскиваемый идентификатор в таблице идентификаторов существует, поиск происходит удачно, указывается положение идентификатора в таблице идентификаторов и выполненное число сравнений для обнаружения идентификатора по любому способу;

— разыскиваемый идентификатор в таблице идентификаторов не существует, выводится сообщение о неуспешном поиске и указывается выполненное число сравнений для обнаружения отсутствия идентификатора в таблице идентификаторов по любому способу.

Экранная форма поиска имеющегося идентификатора представлена на рис. 1.8.

Рис. 1.8. Экранная форма поиска имеющегося идентификатора

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора

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

2. Проектирование лексического анализатора

2.1. Начальные данные

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

Лексемами данного языка являются:

— ключевыеслова (
,
.,
,
,
,
,
,
,
);

— скобки ( «(», «)» );

— оператор присваивания ( := );

— операторы сопоставления ( >, <, = );

— разделитель ( ; );

— арифметические операции ( +, –, ++);

— шестнадцатеричные константы (тип данных
);

— идентификаторы;

— логические операции (

Не считая перечисленных лексем распознаватель должен определять и исключать из входного текста комменты (неограниченной длины). Комменты заключаются в фигурные скобки со звездочкой {*…*}.

2.2. Принцип работы лексического анализатора

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

Основная задачка лексического анализа – разбить входной текст, состоящий из последовательности одиночных знаков, на последовательность слов, либо лексем, другими словами выделить эти слова из непрерывной последовательности знаков с исключением из входного текста объяснений, незначащих пробелов и переводов строк. Все знаки входной последовательности с данной точки зрения делятся на знаки, принадлежащие любым лексемам, и знаки, разделяющие лексемы (разделители).

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

язык описания констант и идентификаторов почти всегда является постоянным, другими словами быть может описан при помощи постоянных грамматик. Распознавателями для постоянных языков являются конечные автоматы (КА).

Хоть какой КА быть может задан при помощи 5 характеристик:

(
,
,δ,
0
,
), (2.1)

где:

конечное огромное количество состояний автомата;

конечное огромное количество допустимых входных знаков (алфавит автомата);

δ – функция переходов, отображающая декартовое произведение множеств
´
во огромное количество подмножеств
:
(
);

0

– изначальное состояние автомата;

– непустое огромное количество конечных состояний автомата.

Работа автомата производится по тактам. На любом следующем такте
автомат, находясь в неком состоянии qi

Î
, считывает очередной знак
Î
из входной цепочки знаков и изменяет свое состояние на
i

+1
=d(qi

,
), опосля чего же указатель в цепочке входных знаков передвигается на последующий знак и начинается такт
+1. Так длится до того времени, пока цепочка входных знаков не завершится. Конец цепочки знаков нередко отмечают особенным эмблемой ^. Считается также, что перед первым тактом автомат находится в исходном состоянии
0
.

Графически автомат отображается нагруженным однонаправленным графом, в каком верхушки представляют состояния, дуги показывают переходы из 1-го состояния в другое, а пометки дуг соответствуют функции перехода. Если функция перехода предугадывает переход из состояния
i

в qi

+1
по нескольким символам, то меж ними строится одна дуга, которая помечается всеми знаками, по которым происходит переход из
i

в
i

+1
.

2.3. Схема распознавателя

Распознавателем лексем входного языка является конечный детерминированный автомат без наружной памяти (приложение Б).

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

В графе также употребляются последующие обозначения:

— ┴ – пробел, табуляция, перевод строчки, +, –, =, <, >, (, ), ;, :, {

— ┴
– перевод строчки

—
0 – хоть какой знак

—
1 – хоть какой знак, не считая знака *

—
2 – хоть какой знак, не считая знака }

—
3 – хоть какой знак, не считая знака ┴

—
4 – хоть какой знак, не считая знака

—
5 – хоть какой знак, не считая знаков 0..9,
..

—
6 – хоть какой знак, не считая знака =

—
7 – хоть какой знак, не считая знака +

—
8 – знаки
..
,
,
..
,
..
,
..
,
,
,
..
, _

—
9 –знаки
..
,
..
,
..
, _

—
10 – хоть какой знак, не считая знаков
..
,
..
, _

—
11 – знаки
..
,
..
,
..
, _

—
12 – знаки
..
,
..
,
..
, _

—
13 – знаки
..
,
..
,
..
, _

—
14 – знаки
..
,
..
, _

—
15 – знаки
..
,
..
,
..
, _

—
16 – знаки
..
,
..
,
..
, _

—
17 – знаки
..
,
..
,
..
, _

—
18 –знаки
..
,
..
,
..
, _

—
19 – знаки
..
,
..
,
..
, _

—
20 – знаки
..
,
..
,
..
, _

—
21 – знаки
..
,
..
,
..
, _

—
22 – знаки
..
,
..
,
,
..
, _

—
23 – знаки
..
,
..
,
..
, _

—
24 – хоть какой знак, не считая знаков
..
,
..
, _, ┴

—
25 – знаки
..
, 0..9

—
26 – хоть какой знак, не считая знаков
..
,
..
, _, ┴, ‘.’

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

G ( {0..9,
..
,
..
, +, – , <, >, =, (, ), ;, :, {, }, *, ‘.’}, {
,
,
1,
2,
3,
4,
5,
1,
2,
3,
4,
5,
1,
2,
3,
4,
1,
2,
1,
2,
3,
4,
,
1,
2,
3,
1,
2,
3,
1,
2,
1,
2,
1,
2,
3,
4,
2,
3,
4},
,
)

1 ®

2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3

5 ®
4
1 ®

2 ®
1
3 ®
2

4 ®
3
5 ®
4

1 ®
2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3 e

2 ®
1
3 ®
2

4 ®
3 .
1 ®

2 ®
1
3 ®
2

1 ®
2 ®
1

1 ® 0
2 ®
1
25

3 ®
2
25
4 ®
3
25

5 ®
4
25
6 ®
5

1 ® :
2 ®
1 =

® ;
® –

® +
®
+

® (
® )

® =
® <

® >

1 ®
2 x1

3 ®
2 *

4 ®
3

®
8|
1
9|
2
11|
3
12|
4
16|
5
14|

14|
1
13|
2
12|
3
15|
4
9|
1
17|
5
14|
1
22|
1
13|
2
9|
3
16|
4
14|
2
14|
1
18|
2
19|
3
11|
4
14|
1
18|
2
14|
1
19|
2
14|
2
20|
3
14|
1
16|
2
21|
3
14|
2
21|
3
14|
4
3|
2
23|
3
9|
1
19|
4
14|

®
1
10|
2
10|
3
10|
4
24|
5
10|
1
10|
1
10|
2
10|
3
10|
4
10|
5
24|
2
24|
1
10|
2
0|
3
10|
4
24|
2
24|

24|
1
10|
2
10|
3
10|
4
24|
1
10|
1
10|
2
24|
1
10|
1
10|
2
10|
3
24|
1
10|
2
10|
3
24|
2
10|
3
26|
4
3|
3|
2
10|
3
10|
4
24|
1
5|

3|
2
5|
3
5|
4
5|
5
4|
6
3|
1
6|
2
3|

3|
1
1|
2 ┴
|
3
2|
4
3

®
5 ┴|
5 ┴|
2 ┴|
4 ┴|
2 ┴|
┴|
4 ┴|
2 ┴|
3 ┴|
3┴|
3 ┴|
4 ┴|
4 ┴|
6 ┴|
2 ┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
2 ┴

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

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

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

Программка делает лексический анализ входного текста в соответствие с данной грамматикой. Результатом выполнения лексического анализа является таблица лексем с указанием их типов, также таблица идентификаторов, сформированная способом цепочек. В таблице лексем имеется поле «Адресок», в каком указывается ссылка на пространство расположения идентификатора в таблице идентификаторов.

Экранная форма работы лексического анализатора представлена на рис.2.1.

Рис. 2.1. Экранная форма работы лексического анализатора

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

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

Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.

Рис. 2.2. Экранная форма при обнаружении лексической ошибки

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

3. Проектирование синтаксического анализатора
3.1. Начальные данные

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

Начальная КС-грамматика имеет вид:

({
,
.
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
,
,
,
,
,
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→

→
<
>
=
(
)
(
)

→
–

→(
)

3.2. Построение синтаксического анализатора

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

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

(
,
,

δ,
0
,
0
,
), (3.1)

где:
– огромное количество состояний автомата;

– алфавит входных знаков автомата;

– особый конечный алфавит магазинных знаков автомата;

δ – функция переходов автомата;

огромное количество конечных состояний;

изначальное состояние автомата;

исходный знак магазина (стека).

Конфигурация МП-автомата определяется 3-мя параметрами: состоянием автомата, текущим эмблемой входной цепочки (положение указателя в цепочке) и содержимым стека.

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

Для построения распознавателя для языка, данного КС-грамматикой, воспользуемся методом «сдвиг-свертка»:

— если на вершине стека МП-автомата находится цепочка знаков g, то ее можно поменять на нетерминальный знак
при условии, что в грамматике языка существует правило вида
→ g, не сдвигая при всем этом считывающую головку автомата («свертка»);

— если считывающая головка автомата обозревает некий знак входной цепочки α, то его можно поместить в стек, сдвинув при всем этом головку на одну позицию на Право («сдвиг»).

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

Для наиболее легкого построения распознавателя, преобразуем начальную КС-грамматику в грамматику операторного предшествования (это таковая приведенная КС-грамматика, в какой правые части всех правил не содержат смежных нетерминальных знаков и для которой дела предшествования можно задать на огромном количестве терминальных знаков). При всем этом для каждой упорядоченной пары терминальных знаков определено не наиболее чем одно из 3-х последующих отношений (=., <., .>).

На базе огромного количества правил грамматики
определим огромного количества последних левых и последних правых знаков
(
),
(
) относительно всех нетерминальных знаков грамматики (табл. 3.1).

Таблица 3.1.

Огромного количества последних левых и последних правых нетерминальных

знаков
(
),
(
) относительно всех нетерминальных знаков грамматики

знак (
)
Шаг 1
Шаг 2

(
)

(,
,

),
,

(,
,

),
,

,
, (,
,

, ),
,

, (,

, )

, (,
,
,

,
, ),
,

,
,
,
, (,
,
,

,
,
, ),
,

,
,
,
,
, (,
,
,

,
,
,
, ),
,

,
,
,

,
,
, ++

,
,
,

,
,
, ),
,
,
, ++

, ;

,
,
,
,
, a

,
,
,),
,
,
, ++, ;

На базе огромного количества правил грамматики
и приобретенных множеств последних левых и последних правых знаков
(
),
(
) построим огромного количества последних левых и последних правых терминальных знаков
t

(
),
t

(
) относительно всех нетерминальных знаков грамматики (табл. 3.2).

Таблица 3.2.

Огромного количества последних левых и последних правых

терминальных знаков
t

(
),
t

(
)

знак (
)
Шаг 1
Шаг 2

t

(
)

(,
,

),
,

(,
,

),
,

-, +
-, +
(,
,
, -, +
),
,
, -, +

<, >, =, (,

<, >, =, )
(,
,
, -, +, <, >, =,

),
,
, -, +, <, >, =

(,
,
, -, +, <, >, =,
,

),
,
, -, +, <, >, =,

(,
,
, -, +, <, >, =,
,
,

),
,
, -, +, <, >, =,
,

,
,
,

,
,
,
, :=, ++

,
,
,

),
,
, -, +,
,
,
,
, :=, ++

;
;

,
,
,
, ;
),
,
, -, +,
,
,
,
, :=, ++, ;

На базе приобретенных множеств и правил грамматики
построим матрицу операторного предшествования (приложение В).

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

({
,
.,
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→
|

→
<
|
>
|
=
| (
) |
(
)

→
–
|
+
|

→ (
) |
|

3.3. Итог
работы синтаксического анализатора

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

Экранная форма работы синтаксического анализатора представлена на рис. 3.1.

Рис. 3.1. Экранная форма работы синтаксического анализатора

По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.

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

Экранная форма при обнаружении синтаксической ошибки представлена на рис. 3.2.

Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве среды разработки для реализации {программы|программки} был {использован|применен}

1. Организация таблицы идентификаторов

1.1. {Исходные|Начальные} данные

На входе имеется набор идентификаторов. {Необходимо|Нужно} написать модуль, который организует данный набор идентификаторов в таблицу идентификаторов {методами|способами} цепочек и бинарного дерева с возможностью {осуществления|воплощения} {многократного|неоднократного} поиска идентификатора в {этой|данной|данной нам|данной для нас} таблице. {Список|Перечень} идентификаторов считается {заданным|данным} в виде текстового файла. Идентификаторы также можно вводить вручную в процессе работы {программы|программки}.

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

1.2. {Назначение|Предназначение} таблицы идентификаторов

Проверка {правильности|корректности} семантики и генерация кода требуют {знания|познания} {характеристик|черт} идентификаторов, {используемых|применяемых} в {программе|программке} на {исходном|начальном} языке. Эти {характеристики|свойства} выясняются из описаний и из того, как идентификаторы {используются|употребляются} в {программе|программке} и {накапливаются|скапливаются} в таблице идентификаторов. Таблица идентификаторов состоит из набора полей данных, который содержит всю {необходимую|нужную} компилятору информацию о данном элементе и может пополняться по мере работы компилятора.

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

1.3.
{метод|способ} бинарного дерева

Данный {метод|способ} организует таблицу идентификаторов в форме бинарного дерева. {Каждый|Любой} узел этого дерева представляет собой элемент таблицы идентификаторов, {причем|при этом} корневым узлом становится {первый|1-ый} элемент, встреченный компилятором во входном тексте. Дерево {называется|именуется} бинарным, {так как|потому что} {каждая|любая} {вершина|верхушка} в нем может иметь не {более|наиболее} {двух|2-ух} вершин (для определенности {используют|употребляют} понятия «правая» и «левая» {ветви|ветки}). Схема {алгоритма|метода} {добавления|прибавления} идентификатора приведена на рис. 1.1.

Рис. 1.1. Схема {алгоритма|метода} {добавления|прибавления} идентификатора

Схема {алгоритма|метода} поиска идентификатора приведена на рис. 1.2.

Рис. 1.2. Схема {алгоритма|метода} поиска идентификатора

Для данного {метода|способа} организации таблицы идентификаторов число сравнений зависит от того порядка, {в котором|в каком} поступают идентификаторы, что является {существенным|значимым} {недостатком|недочетом}. Также {недостатком|недочетом} {метода|способа} является необходимость хранить две {дополнительные|доп} ссылки на левую и правую {ветви|ветки} в {каждом|любом} элементе дерева.

1.4. {метод|способ}
цепочек

Данный {метод|способ} основан на хеш-адресации. В таблицу идентификаторов для {каждого|всякого} элемента добавляется {еще одно|очередное} поле, {в котором|в каком} может содержаться ссылка на {любой|хоть какой} элемент таблицы. {Первоначально|Сначало} это поле пустое (никуда не {указывает|показывает}). Также {необходима|нужна} одна {специальная|особая} переменная, которая {всегда|постоянно} будет указывать на первую {свободную|вольную} ячейку в таблице идентификаторов. В ячейках хеш-таблицы храниться {либо|или} пустое {адрес|адресок}, по которому происходит {обращение|воззвание} {сначала|поначалу} к хеш-таблице, а {потом|позже} уже через нее по {найденному|отысканному} адресу – к самой таблице идентификаторов. Для вычисления хеш-функции {используется|употребляется} сумма
-кодов {трех|3-х} первых {символов|знаков} идентификатора. Если идентификатор состоит {менее|наименее} чем из {трех|3-х} {символов|знаков}, то в качестве хеш-функции {используется|употребляется} сумма
-кода имеющихся {символов|знаков} ({либо|или} {только|лишь} первого, {либо|или} первого и второго).

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

Схема {алгоритма|метода} {добавления|прибавления} идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема {алгоритма|метода} {добавления|прибавления} идентификатора

Схема {алгоритма|метода} поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема {алгоритма|метода} поиска идентификатора

{Достоинства|Плюсы} данного {метода|способа}:

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

— {каждому|любому} идентификатору соответствует строго одна ячейка в таблице идентификаторов.

{Недостатком|Недочетом} {метода|способа} является организация работы с динамическими массивами.

1.5. Результаты {сравнения|сопоставления} {методов|способов}

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

На рис. 1.5 представлена экранная форма организации таблицы идентификаторов {методом|способом} цепочек и {методом|способом} бинарного дерева.

Рис. 1.5. Экранная форма организации таблицы идентификаторов

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

При добавлении {нового|новейшего} идентификатора {возможны|вероятны} два {случая|варианта}:

— добавляемого идентификатора в таблице идентификаторов еще нет, добавление происходит {успешно|удачно}, указывается выполненное число сравнений по {каждому|любому} {методу|способу};

— добавляемый идентификатор в таблице идентификаторов уже существует, в поле ошибок выводится {соответствующее|соответственное} сообщение, указывается выполненное число сравнений для обнаружения повтора идентификатора по {каждому|любому} {методу|способу}.

Экранная форма {добавления|прибавления} {нового|новейшего} идентификатора представлена на рис. 1.6.

Рис. 1.6. Экранная форма {добавления|прибавления} {нового|новейшего} идентификатора

Экранная форма {добавления|прибавления} {существующего|имеющегося} идентификатора представлена на рис. 1.7.

Рис. 1.7. Экранная форма {добавления|прибавления} {существующего|имеющегося} идентификатора

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

При поиске идентификатора также {возможны|вероятны} два {случая|варианта}:

— {искомый|разыскиваемый} идентификатор в таблице идентификаторов существует, поиск происходит {успешно|удачно}, указывается положение идентификатора в таблице идентификаторов и выполненное число сравнений для обнаружения идентификатора по {каждому|любому} {методу|способу};

— {искомый|разыскиваемый} идентификатор в таблице идентификаторов не существует, выводится сообщение о неуспешном поиске и указывается выполненное число сравнений для обнаружения отсутствия идентификатора в таблице идентификаторов по {каждому|любому} {методу|способу}.

Экранная форма поиска {существующего|имеющегося} идентификатора представлена на рис. 1.8.

Рис. 1.8. Экранная форма поиска {существующего|имеющегося} идентификатора

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора

В обоих рассмотренных {случаях|вариантах} число сравнений при поиске идентификатора в таблице идентификаторов выполненное {методом|способом} цепочек {существенно|значительно} меньше, чем у {метода|способа} бинарного дерева, {то есть|другими словами} {метод|способ} цепочек {осуществляет|производит} поиск {значительно|существенно} {быстрее|резвее} {метода|способа} бинарного дерева. {Так как|Потому что} {именно|конкретно} время поиска идентификатора {определяет|описывает} эффективность {метода|способа}, то в {дальнейшем|предстоящем} для {заполнения|наполнения} таблицы идентификаторов {исходной|начальной} {программы|программки} будет {использоваться|употребляться} {метод|способ} цепочек.

2. Проектирование лексического анализатора

2.1. {Исходные|Начальные} данные

текст на входном языке задается в виде символьного (текстового) файла. {Необходимо|Нужно} {разработать|создать} модуль, выполняющий лексический анализ входного текста, результатом которого является таблица лексем с указанием их типов и значений. Также должны выдаваться сообщения о наличии во входном тексте ошибок, которые могут быть обнаружены на {этапе|шаге} лексического анализа, с указанием их позиций во входном тексте. При обнаружении ошибки выполнение лексического анализа {должно|обязано} {прекратиться|закончиться}.

Лексемами данного языка являются:

— ключевыеслова (
,
.,
,
,
,
,
,
,
);

— скобки ( «(», «)» );

— оператор присваивания ( := );

— операторы {сравнения|сопоставления} ( >, <, = );

— разделитель ( ; );

— арифметические операции ( +, –, ++);

— шестнадцатеричные константы (тип данных
);

— идентификаторы;

— логические операции (

{Кроме|Не считая} перечисленных лексем распознаватель должен определять и исключать из входного текста {комментарии|комменты} (неограниченной длины). {Комментарии|Комменты} заключаются в фигурные скобки со звездочкой {*…*}.

2.2. Принцип работы лексического анализатора

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

Основная {задача|задачка} лексического анализа – разбить входной текст, состоящий из последовательности одиночных {символов|знаков}, на последовательность слов, {или|либо} лексем, {то есть|другими словами} выделить эти слова из непрерывной последовательности {символов|знаков} с исключением из входного текста {комментариев|объяснений}, незначащих пробелов и переводов строк. Все {символы|знаки} входной последовательности с {этой|данной|данной нам|данной для нас} точки зрения {разделяются|делятся} на {символы|знаки}, принадлежащие {каким-либо|любым} лексемам, и {символы|знаки}, разделяющие лексемы (разделители).

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

язык описания констант и идентификаторов {в большинстве случаев|почти всегда} является {регулярным|постоянным}, {то есть|другими словами} {может быть|быть может} описан {с помощью|при помощи} {регулярных|постоянных} грамматик. Распознавателями для {регулярных|постоянных} языков являются конечные автоматы (КА).

{Любой|Хоть какой} КА {может быть|быть может} задан {с помощью|при помощи} {пяти|5} {параметров|характеристик}:

(
,
,δ,
0
,
), (2.1)

где:

конечное {множество|огромное количество} состояний автомата;

конечное {множество|огромное количество} допустимых входных {символов|знаков} (алфавит автомата);

δ – функция переходов, отображающая декартовое произведение множеств
´
во {множество|огромное количество} подмножеств
:
(
);

0

– {начальное|изначальное} состояние автомата;

– непустое {множество|огромное количество} конечных состояний автомата.

Работа автомата {выполняется|производится} по тактам. На {каждом|любом} {очередном|следующем} такте
автомат, находясь в {некотором|неком} состоянии qi

Î
, считывает очередной {символ|знак}
Î
из входной цепочки {символов|знаков} и изменяет свое состояние на
i

+1
=d(qi

,
), {после|опосля} {чего|чего же|что} указатель в цепочке входных {символов|знаков} передвигается на {следующий|последующий} {символ|знак} и начинается такт
+1. Так {продолжается|длится} до {тех пор|того времени}, пока цепочка входных {символов|знаков} не {закончится|завершится}. Конец цепочки {символов|знаков} {часто|нередко} {помечают|отмечают} {особым|особенным} {символом|эмблемой} ^. Считается также, что перед первым тактом автомат находится в {начальном|исходном} состоянии
0
.

Графически автомат отображается нагруженным однонаправленным графом, {в котором|в каком} {вершины|верхушки} представляют состояния, дуги {отображают|показывают} переходы из {одного|1-го} состояния в другое, а пометки дуг соответствуют функции перехода. Если функция перехода {предусматривает|предугадывает} переход из состояния
i

в qi

+1
по нескольким символам, то {между|меж} ними строится одна дуга, которая помечается всеми {символами|знаками}, по которым происходит переход из
i

в
i

+1
.

2.3. Схема распознавателя

Распознавателем лексем входного языка является конечный детерминированный автомат без {внешней|наружной} памяти (приложение Б).

{Начальное|Изначальное} состояние автомата обозначено
, конечное
. В случае {ошибочной|неверной} входной цепочки автомат попадает в состояние ошибки
. {При этом|При всем этом} работа автомата останавливается. {Остальные|Другие} состояния автомата определяются допустимыми для компилятора {исходного|начального} языка лексемами.

В графе также {используются|употребляются} {следующие|последующие} обозначения:

— ┴ – пробел, табуляция, перевод {строки|строчки}, +, –, =, <, >, (, ), ;, :, {

— ┴
– перевод {строки|строчки}

—
0 – {любой|хоть какой} {символ|знак}

—
1 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символа|знака} *

—
2 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символа|знака} }

—
3 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символа|знака} ┴

—
4 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символа|знака}

—
5 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символов|знаков} 0..9,
..

—
6 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символа|знака} =

—
7 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символа|знака} +

—
8 – {символы|знаки}
..
,
,
..
,
..
,
..
,
,
,
..
, _

—
9 –{символы|знаки}
..
,
..
,
..
, _

—
10 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символов|знаков}
..
,
..
, _

—
11 – {символы|знаки}
..
,
..
,
..
, _

—
12 – {символы|знаки}
..
,
..
,
..
, _

—
13 – {символы|знаки}
..
,
..
,
..
, _

—
14 – {символы|знаки}
..
,
..
, _

—
15 – {символы|знаки}
..
,
..
,
..
, _

—
16 – {символы|знаки}
..
,
..
,
..
, _

—
17 – {символы|знаки}
..
,
..
,
..
, _

—
18 –{символы|знаки}
..
,
..
,
..
, _

—
19 – {символы|знаки}
..
,
..
,
..
, _

—
20 – {символы|знаки}
..
,
..
,
..
, _

—
21 – {символы|знаки}
..
,
..
,
..
, _

—
22 – {символы|знаки}
..
,
..
,
,
..
, _

—
23 – {символы|знаки}
..
,
..
,
..
, _

—
24 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символов|знаков}
..
,
..
, _, ┴

—
25 – {символы|знаки}
..
, 0..9

—
26 – {любой|хоть какой} {символ|знак}, {кроме|не считая} {символов|знаков}
..
,
..
, _, ┴, ‘.’

{Регулярная|Постоянная} грамматика входного языка в форме Бэкуса-Наура имеет вид:

G ( {0..9,
..
,
..
, +, – , <, >, =, (, ), ;, :, {, }, *, ‘.’}, {
,
,
1,
2,
3,
4,
5,
1,
2,
3,
4,
5,
1,
2,
3,
4,
1,
2,
1,
2,
3,
4,
,
1,
2,
3,
1,
2,
3,
1,
2,
1,
2,
1,
2,
3,
4,
2,
3,
4},
,
)

1 ®

2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3

5 ®
4
1 ®

2 ®
1
3 ®
2

4 ®
3
5 ®
4

1 ®
2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3 e

2 ®
1
3 ®
2

4 ®
3 .
1 ®

2 ®
1
3 ®
2

1 ®
2 ®
1

1 ® 0
2 ®
1
25

3 ®
2
25
4 ®
3
25

5 ®
4
25
6 ®
5

1 ® :
2 ®
1 =

® ;
® –

® +
®
+

® (
® )

® =
® <

® >

1 ® {

2 ®
1 * |
2 x1

3 ®
2 *

4 ®
3 }

®
8|
1
9|
2
11|
3
12|
4
16|
5
14|

14|
1
13|
2
12|
3
15|
4
9|
1
17|
5
14|
1
22|
1
13|
2
9|
3
16|
4
14|
2
14|
1
18|
2
19|
3
11|
4
14|
1
18|
2
14|
1
19|
2
14|
2
20|
3
14|
1
16|
2
21|
3
14|
2
21|
3
14|
4
3|
2
23|
3
9|
1
19|
4
14|

®
1
10|
2
10|
3
10|
4
24|
5
10|
1
10|
1
10|
2
10|
3
10|
4
10|
5
24|
2
24|
1
10|
2
0|
3
10|
4
24|
2
24|

24|
1
10|
2
10|
3
10|
4
24|
1
10|
1
10|
2
24|
1
10|
1
10|
2
10|
3
24|
1
10|
2
10|
3
24|
2
10|
3
26|
4
3|
3|
2
10|
3
10|
4
24|
1
5|

3|
2
5|
3
5|
4
5|
5
4|
6
3|
1
6|
2
3|

3|
1
1|
2 ┴
|
3
2|
4
3

®
5 ┴|
5 ┴|
2 ┴|
4 ┴|
2 ┴|
┴|
4 ┴|
2 ┴|
3 ┴|
3┴|
3 ┴|
4 ┴|
4 ┴|
6 ┴|
2 ┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
2 ┴

Результатом работы лексического анализатора является {перечень|список} всех {найденных|отысканных} в тексте {исходной|начальной} {программы|программки} лексем с учетом их {характеристик|черт}. Этот {перечень|список} лексем предоставляется в виде таблицы лексем. информация {об|о} идентификаторах и константах помещается в таблицу идентификаторов.

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

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

{Программа|Программка} {выполняет|делает} лексический анализ входного текста в соответствие с {заданной|данной} грамматикой. Результатом выполнения лексического анализа является таблица лексем с указанием их типов, {а также|также} таблица идентификаторов, сформированная {методом|способом} цепочек. В таблице лексем имеется поле «{Адрес|Адресок}», {в котором|в каком} указывается ссылка на {место|пространство} расположения идентификатора в таблице идентификаторов.

Экранная форма работы лексического анализатора представлена на рис.2.1.

Рис. 2.1. Экранная форма работы лексического анализатора

Лексическая ошибка возникает при обнаружении незакрытого комментария, {неверного|неправильного} {символа|знака} в лексеме {или|либо} если лексема незавершенна (не {обнаружен|найден} признак окончания лексемы).

Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.

Рис. 2.2. Экранная форма при обнаружении лексической ошибки

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

3. Проектирование синтаксического анализатора
3.1. {Исходные|Начальные} данные

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

{Исходная|Начальная} КС-грамматика имеет вид:

({
,
.
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
,
,
,
,
,
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→

→
<
>
=
(
)
(
)

→
–

→(
)

3.2. Построение синтаксического анализатора

Перед синтаксическим анализатором стоят две {основные|главные} {задачи|задачки}: проверить {правильность|корректность} конструкций входной цепочки, которая представляется в виде уже выделенных слов входного языка, и {преобразовать|конвертировать} ее в дерево вывода – вид, {удобный|удачный} для {дальнейшей|предстоящей} семантической обработки и генерации кода.

Основой для построения синтаксического анализатора являются автоматы с магазинной памятью, {или|либо} МП-автоматы. В общем виде МП-автомат можно {определить|найти} {следующим|последующим} образом:

(
,
,

δ,
0
,
0
,
), (3.1)

где:
– {множество|огромное количество} состояний автомата;

– алфавит входных {символов|знаков} автомата;

– {специальный|особый} конечный алфавит магазинных {символов|знаков} автомата;

δ – функция переходов автомата;

{множество|огромное количество} конечных состояний;

{начальное|изначальное} состояние автомата;

{начальный|исходный} {символ|знак} магазина (стека).

Конфигурация МП-автомата определяется {тремя|3-мя} параметрами: состоянием автомата, текущим {символом|эмблемой} входной цепочки (положение указателя в цепочке) и содержимым стека.

При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние {символы|знаки}, {соответствующие|надлежащие} условию перехода, и добавляется цепочка, {соответствующая|соответственная} правилу перехода. {Первый|1-ый} {символ|знак} цепочки становится {верхушкой|вершиной} стека. Если при окончании цепочки автомат находится в одном из {заданных|данных} конечных состояний, а стек пуст, цепочка считается принятой, {иначе|по другому} цепочка {символов|знаков} не принимается.

Для построения распознавателя для языка, {заданного|данного} КС-грамматикой, воспользуемся {алгоритмом|методом} «сдвиг-свертка»:

— если на {верхушке|вершине} стека МП-автомата находится цепочка {символов|знаков} g, то ее можно {заменить|поменять} на нетерминальный {символ|знак}
при условии, что в грамматике языка существует правило вида
→ g, не сдвигая {при этом|при всем этом} считывающую головку автомата («свертка»);

— если считывающая головка автомата обозревает {некоторый|некий} {символ|знак} входной цепочки α, то его можно поместить в стек, сдвинув {при этом|при всем этом} головку на одну позицию {вправо|на право} («сдвиг»).

Распознаватель на {основе|базе} {алгоритма|метода} «сдвиг-свертка» является восходящим распознавателем: он читает входную цепочку {символов|знаков} слева {направо|вправо}, строит правосторонний вывод, а дерево вывода строит снизу {вверх|ввысь} (от корневых вершин к корню).

Для {более|наиболее} легкого построения распознавателя, преобразуем {исходную|начальную} КС-грамматику в грамматику операторного предшествования (это {такая|таковая} приведенная КС-грамматика, {в которой|в какой} правые части всех правил не содержат смежных нетерминальных {символов|знаков} и для которой {отношения|дела} предшествования можно задать на {множестве|огромном количестве} терминальных {символов|знаков}). {При этом|При всем этом} для каждой упорядоченной пары терминальных {символов|знаков} определено не {более|наиболее} чем одно из {трех|3-х} {следующих|последующих} отношений (=., <., .>).

На {основе|базе} {множества|огромного количества} правил грамматики
определим {множества|огромного количества} {крайних|последних} левых и {крайних|последних} правых {символов|знаков}
(
),
(
) относительно всех нетерминальных {символов|знаков} грамматики (табл. 3.1).

Таблица 3.1.

{Множества|Огромного количества} {крайних|последних} левых и {крайних|последних} правых нетерминальных

{символов|знаков}
(
),
(
) относительно всех нетерминальных {символов|знаков} грамматики

{Символ|Знак} (
)
Шаг 1
Шаг 2

(
)

(,
,

),
,

(,
,

),
,

,
, (,
,

, ),
,

, (,

, )

, (,
,
,

,
, ),
,

,
,
,
, (,
,
,

,
,
, ),
,

,
,
,
,
, (,
,
,

,
,
,
, ),
,

,
,
,

,
,
, ++

,
,
,

,
,
, ),
,
,
, ++

, ;

,
,
,
,
, a

,
,
,),
,
,
, ++, ;

На {основе|базе} {множества|огромного количества} правил грамматики
и {полученных|приобретенных} множеств {крайних|последних} левых и {крайних|последних} правых {символов|знаков}
(
),
(
) построим {множества|огромного количества} {крайних|последних} левых и {крайних|последних} правых терминальных {символов|знаков}
t

(
),
t

(
) относительно всех нетерминальных {символов|знаков} грамматики (табл. 3.2).

Таблица 3.2.

{Множества|Огромного количества} {крайних|последних} левых и {крайних|последних} правых

терминальных {символов|знаков}
t

(
),
t

(
)

{Символ|Знак} (
)
Шаг 1
Шаг 2

t

(
)

(,
,

),
,

(,
,

),
,

-, +
-, +
(,
,
, -, +
),
,
, -, +

<, >, =, (,

<, >, =, )
(,
,
, -, +, <, >, =,

),
,
, -, +, <, >, =

(,
,
, -, +, <, >, =,
,

),
,
, -, +, <, >, =,

(,
,
, -, +, <, >, =,
,
,

),
,
, -, +, <, >, =,
,

,
,
,

,
,
,
, :=, ++

,
,
,

),
,
, -, +,
,
,
,
, :=, ++

;
;

,
,
,
, ;
),
,
, -, +,
,
,
,
, :=, ++, ;

На {основе|базе} {полученных|приобретенных} множеств и правил грамматики
построим матрицу операторного предшествования (приложение В).

{Алгоритм|Метод} разбора цепочек грамматики операторного предшествования игнорирует нетерминальные {символы|знаки}. {Поэтому|Потому} {исходную|начальную} КС-грамматику преобразуем так, {чтобы|чтоб} в ней осталось как можно меньше нетерминальных {символов|знаков} (в данном случае два), {то есть|другими словами} преобразуем ее в остовную грамматику:

({
,
.,
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→
|

→
<
|
>
|
=
| (
) |
(
)

→
–
|
+
|

→ (
) |
|

3.3. {Результат|Итог}
работы синтаксического анализатора

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

Экранная форма работы синтаксического анализатора представлена на рис. 3.1.

Рис. 3.1. Экранная форма работы синтаксического анализатора

По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.

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

Экранная форма при обнаружении синтаксической ошибки представлена на рис. 3.2.

Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки

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

Заключение

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

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

Было установлено, что {заданных|данных} {методов|способов} {более|наиболее} {эффективным|действенным} является {метод|способ} цепочек, {так как|потому что} для него время поиска идентификатора в таблице идентификаторов {гораздо|еще} меньше, чем для {метода|способа} бинарного дерева, а {именно|конкретно} операция «поиск» является {основным|главным} {критерием|аспектом} {сравнения|сопоставления} эффективности {методов|способов}.

Во {второй|2-ой} части работы разработан модуль, который {выполняет|делает} лексический анализ входного текста и порождает таблицу лексем с указанием их типов и значений, {а также|также} {методом|способом} цепочек {формирует|сформировывает} таблицу идентификаторов, {при этом|при всем этом} в таблице лексем в поле «{Адрес|Адресок}» указывается {место|пространство} расположения идентификатора в таблице идентификаторов. При обнаружении в {исходном|начальном} тексте лексической ошибки выдается сообщение {об|о} ошибке, а работа лексического анализатора прекращается.

В третьей части курсовой разработан модуль, который на {основе|базе} таблицы лексем {выполняет|делает} синтаксический разбор текста с построением дерева вывода и перечислением всех сработавших правил «свертки». При обнаружении в {исходном|начальном} тексте синтаксической ошибки выдается сообщение {об|о} ошибке, а работа синтаксического анализатора прекращается.

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

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

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

1. Организация таблицы идентификаторов

1.1. Начальные данные

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

1.2. Предназначение таблицы идентификаторов

1.3.
способ бинарного дерева

Рис. 1.1. Схема метода прибавления идентификатора

Схема метода поиска идентификатора приведена на рис. 1.2.

Рис. 1.2. Схема метода поиска идентификатора

1.4. способ
цепочек

Схема метода прибавления идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема метода прибавления идентификатора

Схема метода поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема метода поиска идентификатора

Плюсы данного способа:

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

— любому идентификатору соответствует строго одна ячейка в таблице идентификаторов.

Недочетом способа является организация работы с динамическими массивами.

1.5. Результаты сопоставления способов

Рис. 1.5. Экранная форма организации таблицы идентификаторов

При добавлении новейшего идентификатора вероятны два варианта:

Экранная форма прибавления новейшего идентификатора представлена на рис. 1.6.

Рис. 1.6. Экранная форма прибавления новейшего идентификатора

Экранная форма прибавления имеющегося идентификатора представлена на рис. 1.7.

Рис. 1.7. Экранная форма прибавления имеющегося идентификатора

При поиске идентификатора также вероятны два варианта:

Экранная форма поиска имеющегося идентификатора представлена на рис. 1.8.

Рис. 1.8. Экранная форма поиска имеющегося идентификатора

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора

2. Проектирование лексического анализатора

2.1. Начальные данные

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

Лексемами данного языка являются:

— ключевыеслова (
,
.,
,
,
,
,
,
,
);

— скобки ( «(», «)» );

— оператор присваивания ( := );

— операторы сопоставления ( >, <, = );

— разделитель ( ; );

— арифметические операции ( +, –, ++);

— шестнадцатеричные константы (тип данных
);

— идентификаторы;

— логические операции (

2.2. Принцип работы лексического анализатора

Хоть какой КА быть может задан при помощи 5 характеристик:

(
,
,δ,
0
,
), (2.1)

где:

конечное огромное количество состояний автомата;

конечное огромное количество допустимых входных знаков (алфавит автомата);

0

– изначальное состояние автомата;

– непустое огромное количество конечных состояний автомата.

2.3. Схема распознавателя

В графе также употребляются последующие обозначения:

— ┴ – пробел, табуляция, перевод строчки, +, –, =, <, >, (, ), ;, :, {

— ┴
– перевод строчки

—
0 – хоть какой знак

—
1 – хоть какой знак, не считая знака *

—
2 – хоть какой знак, не считая знака }

—
3 – хоть какой знак, не считая знака ┴

—
4 – хоть какой знак, не считая знака

—
5 – хоть какой знак, не считая знаков 0..9,
..

—
6 – хоть какой знак, не считая знака =

—
7 – хоть какой знак, не считая знака +

—
8 – знаки
..
,
,
..
,
..
,
..
,
,
,
..
, _

—
9 –знаки
..
,
..
,
..
, _

—
10 – хоть какой знак, не считая знаков
..
,
..
, _

—
11 – знаки
..
,
..
,
..
, _

—
12 – знаки
..
,
..
,
..
, _

—
13 – знаки
..
,
..
,
..
, _

—
14 – знаки
..
,
..
, _

—
15 – знаки
..
,
..
,
..
, _

—
16 – знаки
..
,
..
,
..
, _

—
17 – знаки
..
,
..
,
..
, _

—
18 –знаки
..
,
..
,
..
, _

—
19 – знаки
..
,
..
,
..
, _

—
20 – знаки
..
,
..
,
..
, _

—
21 – знаки
..
,
..
,
..
, _

—
22 – знаки
..
,
..
,
,
..
, _

—
23 – знаки
..
,
..
,
..
, _

—
24 – хоть какой знак, не считая знаков
..
,
..
, _, ┴

—
25 – знаки
..
, 0..9

—
26 – хоть какой знак, не считая знаков
..
,
..
, _, ┴, ‘.’

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

G ( {0..9,
..
,
..
, +, – , <, >, =, (, ), ;, :, {, }, *, ‘.’}, {
,
,
1,
2,
3,
4,
5,
1,
2,
3,
4,
5,
1,
2,
3,
4,
1,
2,
1,
2,
3,
4,
,
1,
2,
3,
1,
2,
3,
1,
2,
1,
2,
1,
2,
3,
4,
2,
3,
4},
,
)

1 ®

2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3

5 ®
4
1 ®

2 ®
1
3 ®
2

4 ®
3
5 ®
4

1 ®
2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3 e

2 ®
1
3 ®
2

4 ®
3 .
1 ®

2 ®
1
3 ®
2

1 ®
2 ®
1

1 ® 0
2 ®
1
25

3 ®
2
25
4 ®
3
25

5 ®
4
25
6 ®
5

1 ® :
2 ®
1 =

® ;
® –

® +
®
+

® (
® )

® =
® <

® >

1 ®
2 x1

3 ®
2 *

4 ®
3

®
8|
1
9|
2
11|
3
12|
4
16|
5
14|

14|
1
13|
2
12|
3
15|
4
9|
1
17|
5
14|
1
22|
1
13|
2
9|
3
16|
4
14|
2
14|
1
18|
2
19|
3
11|
4
14|
1
18|
2
14|
1
19|
2
14|
2
20|
3
14|
1
16|
2
21|
3
14|
2
21|
3
14|
4
3|
2
23|
3
9|
1
19|
4
14|

®
1
10|
2
10|
3
10|
4
24|
5
10|
1
10|
1
10|
2
10|
3
10|
4
10|
5
24|
2
24|
1
10|
2
0|
3
10|
4
24|
2
24|

24|
1
10|
2
10|
3
10|
4
24|
1
10|
1
10|
2
24|
1
10|
1
10|
2
10|
3
24|
1
10|
2
10|
3
24|
2
10|
3
26|
4
3|
3|
2
10|
3
10|
4
24|
1
5|

3|
2
5|
3
5|
4
5|
5
4|
6
3|
1
6|
2
3|

3|
1
1|
2 ┴
|
3
2|
4
3

®
5 ┴|
5 ┴|
2 ┴|
4 ┴|
2 ┴|
┴|
4 ┴|
2 ┴|
3 ┴|
3┴|
3 ┴|
4 ┴|
4 ┴|
6 ┴|
2 ┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
2 ┴

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

Экранная форма работы лексического анализатора представлена на рис.2.1.

Рис. 2.1. Экранная форма работы лексического анализатора

Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.

Рис. 2.2. Экранная форма при обнаружении лексической ошибки

3. Проектирование синтаксического анализатора
3.1. Начальные данные

Начальная КС-грамматика имеет вид:

({
,
.
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
,
,
,
,
,
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→

→
<
>
=
(
)
(
)

→
–

→(
)

3.2. Построение синтаксического анализатора

(
,
,

δ,
0
,
0
,
), (3.1)

где:
– огромное количество состояний автомата;

– алфавит входных знаков автомата;

– особый конечный алфавит магазинных знаков автомата;

δ – функция переходов автомата;

огромное количество конечных состояний;

изначальное состояние автомата;

исходный знак магазина (стека).

Для построения распознавателя для языка, данного КС-грамматикой, воспользуемся методом «сдвиг-свертка»:

— если считывающая головка автомата обозревает некий знак входной цепочки α, то его можно поместить в стек, сдвинув при всем этом головку на одну позицию на право («сдвиг»).

Таблица 3.1.

Огромного количества последних левых и последних правых нетерминальных

знаков
(
),
(
) относительно всех нетерминальных знаков грамматики

Знак (
)
Шаг 1
Шаг 2

(
)

(,
,

),
,

(,
,

),
,

,
, (,
,

, ),
,

, (,

, )

, (,
,
,

,
, ),
,

,
,
,
, (,
,
,

,
,
, ),
,

,
,
,
,
, (,
,
,

,
,
,
, ),
,

,
,
,

,
,
, ++

,
,
,

,
,
, ),
,
,
, ++

, ;

,
,
,
,
, a

,
,
,),
,
,
, ++, ;

Таблица 3.2.

Огромного количества последних левых и последних правых

терминальных знаков
t

(
),
t

(
)

Знак (
)
Шаг 1
Шаг 2

t

(
)

(,
,

),
,

(,
,

),
,

-, +
-, +
(,
,
, -, +
),
,
, -, +

<, >, =, (,

<, >, =, )
(,
,
, -, +, <, >, =,

),
,
, -, +, <, >, =

(,
,
, -, +, <, >, =,
,

),
,
, -, +, <, >, =,

(,
,
, -, +, <, >, =,
,
,

),
,
, -, +, <, >, =,
,

,
,
,

,
,
,
, :=, ++

,
,
,

),
,
, -, +,
,
,
,
, :=, ++

;
;

,
,
,
, ;
),
,
, -, +,
,
,
,
, :=, ++, ;

({
,
.,
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→
|

→
<
|
>
|
=
| (
) |
(
)

→
–
|
+
|

→ (
) |
|

3.3. Итог
работы синтаксического анализатора

Экранная форма работы синтаксического анализатора представлена на рис. 3.1.

Рис. 3.1. Экранная форма работы синтаксического анализатора

По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.

Экранная форма при обнаружении синтаксической ошибки представлена на рис. 3.2.

Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки

Заключение

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

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

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

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

1. Организация таблицы идентификаторов

1.1. Начальные данные

1.2. Предназначение таблицы идентификаторов

1.3.
способ бинарного дерева

Рис. 1.1. Схема метода прибавления идентификатора

Схема метода поиска идентификатора приведена на рис. 1.2.

Рис. 1.2. Схема метода поиска идентификатора

1.4. способ
цепочек

Данный способ основан на хеш-адресации. В таблицу идентификаторов для всякого элемента добавляется очередное поле, в каком может содержаться ссылка на хоть какой элемент таблицы. Сначало это поле пустое (никуда не показывает). Также нужна одна особая переменная, которая постоянно будет указывать на первую вольную ячейку в таблице идентификаторов. В ячейках хеш-таблицы храниться или пустое индивидумом общественно-исторического опыта Запечатлено в схемах действий понятиях соц ролях нормах и ценностях Система значений индивидума обусловливает управление действиями его деятельности», или значение указателя на некую область памяти в таблице идентификаторов. Хеш-функция вычисляет адресок, по которому происходит воззвание поначалу к хеш-таблице, а позже уже через нее по отысканному адресу – к самой таблице идентификаторов. Для вычисления хеш-функции употребляется сумма
-кодов 3-х первых знаков идентификатора. Если идентификатор состоит наименее чем из 3-х знаков, то в качестве хеш-функции употребляется сумма
-кода имеющихся знаков (или лишь первого, или первого и второго).

Схема метода прибавления идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема метода прибавления идентификатора

Схема метода поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема метода поиска идентификатора

Плюсы данного способа:

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

— любому идентификатору соответствует строго одна ячейка в таблице идентификаторов.

Недочетом способа является организация работы с динамическими массивами.

1.5. Результаты сопоставления способов

Рис. 1.5. Экранная форма организации таблицы идентификаторов

При добавлении новейшего идентификатора вероятны два варианта:

Экранная форма прибавления новейшего идентификатора представлена на рис. 1.6.

Рис. 1.6. Экранная форма прибавления новейшего идентификатора

Экранная форма прибавления имеющегося идентификатора представлена на рис. 1.7.

Рис. 1.7. Экранная форма прибавления имеющегося идентификатора

При поиске идентификатора также вероятны два варианта:

Экранная форма поиска имеющегося идентификатора представлена на рис. 1.8.

Рис. 1.8. Экранная форма поиска имеющегося идентификатора

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора

2. Проектирование лексического анализатора

2.1. Начальные данные

Лексемами данного языка являются:

— ключевыеслова (
,
.,
,
,
,
,
,
,
);

— скобки ( «(», «)» );

— оператор присваивания ( := );

— операторы сопоставления ( >, <, = );

— разделитель ( ; );

— арифметические операции ( +, –, ++);

— шестнадцатеричные константы (тип данных
);

— идентификаторы;

— логические операции (

2.2. Принцип работы лексического анализатора

Хоть какой КА быть может задан при помощи 5 характеристик:

(
,
,δ,
0
,
), (2.1)

где:

конечное огромное количество состояний автомата;

конечное огромное количество допустимых входных знаков (алфавит автомата);

0

– изначальное состояние автомата;

– непустое огромное количество конечных состояний автомата.

2.3. Схема распознавателя

В графе также употребляются последующие обозначения:

— ┴ – пробел, табуляция, перевод строчки, +, –, =, <, >, (, ), ;, :,

—
3 – хоть какой знак, не считая знака ┴

—
4 – хоть какой знак, не считая знака

—
5 – хоть какой знак, не считая знаков 0..9,
..

—
6 – хоть какой знак, не считая знака =

—
7 – хоть какой знак, не считая знака +

—
8 – знаки
..
,
,
..
,
..
,
..
,
,
,
..
, _

—
9 –знаки
..
,
..
,
..
, _

—
10 – хоть какой знак, не считая знаков
..
,
..
, _

—
11 – знаки
..
,
..
,
..
, _

—
12 – знаки
..
,
..
,
..
, _

—
13 – знаки
..
,
..
,
..
, _

—
14 – знаки
..
,
..
, _

—
15 – знаки
..
,
..
,
..
, _

—
16 – знаки
..
,
..
,
..
, _

—
17 – знаки
..
,
..
,
..
, _

—
18 –знаки
..
,
..
,
..
, _

—
19 – знаки
..
,
..
,
..
, _

—
20 – знаки
..
,
..
,
..
, _

—
21 – знаки
..
,
..
,
..
, _

—
22 – знаки
..
,
..
,
,
..
, _

—
23 – знаки
..
,
..
,
..
, _

—
24 – хоть какой знак, не считая знаков
..
,
..
, _, ┴

—
25 – знаки
..
, 0..9

—
26 – хоть какой знак, не считая знаков
..
,
..
, _, ┴, ‘.’

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

G ( {0..9,
..
,
..
, +, – , <, >, =, (, ), ;, :, , *, ‘.’},
,
,
1,
2,
3,
4,
5,
1,
2,
3,
4,
5,
1,
2,
3,
4,
1,
2,
1,
2,
3,
4,
,
1,
2,
3,
1,
2,
3,
1,
2,
1,
2,
1,
2,
3,
4,
2,
3,
4,
,
)

1 ®

2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3

5 ®
4
1 ®

2 ®
1
3 ®
2

4 ®
3
5 ®
4

1 ®
2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3 e

2 ®
1
3 ®
2

4 ®
3 .
1 ®

2 ®
1
3 ®
2

1 ®
2 ®
1

1 ® 0
2 ®
1
25

3 ®
2
25
4 ®
3
25

5 ®
4
25
6 ®
5

1 ® :
2 ®
1 =

® ;
® –

® +
®
+

® (
® )

® =
® <

® >

1 ®
2 x1

3 ®
2 *

4 ®
3

®
8|
1
9|
2
11|
3
12|
4
16|
5
14|

14|
1
13|
2
12|
3
15|
4
9|
1
17|
5
14|
1
22|
1
13|
2
9|
3
16|
4
14|
2
14|
1
18|
2
19|
3
11|
4
14|
1
18|
2
14|
1
19|
2
14|
2
20|
3
14|
1
16|
2
21|
3
14|
2
21|
3
14|
4
3|
2
23|
3
9|
1
19|
4
14|

®
1
10|
2
10|
3
10|
4
24|
5
10|
1
10|
1
10|
2
10|
3
10|
4
10|
5
24|
2
24|
1
10|
2
0|
3
10|
4
24|
2
24|

24|
1
10|
2
10|
3
10|
4
24|
1
10|
1
10|
2
24|
1
10|
1
10|
2
10|
3
24|
1
10|
2
10|
3
24|
2
10|
3
26|
4
3|
3|
2
10|
3
10|
4
24|
1
5|

3|
2
5|
3
5|
4
5|
5
4|
6
3|
1
6|
2
3|

3|
1
1|
2 ┴
|
3
2|
4
3

®
5 ┴|
5 ┴|
2 ┴|
4 ┴|
2 ┴|
┴|
4 ┴|
2 ┴|
3 ┴|
3┴|
3 ┴|
4 ┴|
4 ┴|
6 ┴|
2 ┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
2 ┴

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

Экранная форма работы лексического анализатора представлена на рис.2.1.

Рис. 2.1. Экранная форма работы лексического анализатора

Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.

Рис. 2.2. Экранная форма при обнаружении лексической ошибки

3. Проектирование синтаксического анализатора
3.1. Начальные данные

Начальная КС-грамматика имеет вид:

(
,
.
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=, ,
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→

→
<
>
=
(
)
(
)

→
–

→(
)

3.2. Построение синтаксического анализатора

(
,
,

δ,
0
,
0
,
), (3.1)

где:
– огромное количество состояний автомата;

– алфавит входных знаков автомата;

– особый конечный алфавит магазинных знаков автомата;

δ – функция переходов автомата;

огромное количество конечных состояний;

изначальное состояние автомата;

исходный знак магазина (стека).

Для построения распознавателя для языка, данного КС-грамматикой, воспользуемся методом «сдвиг-свертка»:

Таблица 3.1.

Огромного количества последних левых и последних правых нетерминальных

знаков
(
),
(
) относительно всех нетерминальных знаков грамматики

Знак (
)
Шаг 1
Шаг 2

(
)

(,
,

),
,

(,
,

),
,

,
, (,
,

, ),
,

, (,

, )

, (,
,
,

,
, ),
,

,
,
,
, (,
,
,

,
,
, ),
,

,
,
,
,
, (,
,
,

,
,
,
, ),
,

,
,
,

,
,
, ++

,
,
,

,
,
, ),
,
,
, ++

, ;

,
,
,
,
, a

,
,
,),
,
,
, ++, ;

Таблица 3.2.

Огромного количества последних левых и последних правых

терминальных знаков
t

(
),
t

(
)

Знак (
)
Шаг 1
Шаг 2

t

(
)

(,
,

),
,

(,
,

),
,

-, +
-, +
(,
,
, -, +
),
,
, -, +

<, >, =, (,

<, >, =, )
(,
,
, -, +, <, >, =,

),
,
, -, +, <, >, =

(,
,
, -, +, <, >, =,
,

),
,
, -, +, <, >, =,

(,
,
, -, +, <, >, =,
,
,

),
,
, -, +, <, >, =,
,

,
,
,

,
,
,
, :=, ++

,
,
,

),
,
, -, +,
,
,
,
, :=, ++

;
;

,
,
,
, ;
),
,
, -, +,
,
,
,
, :=, ++, ;

(
,
.,
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=,
,
,
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→
|

→
<
|
>
|
=
| (
) |
(
)

→
–
|
+
|

→ (
) |
|

3.3. Итог
работы синтаксического анализатора

Экранная форма работы синтаксического анализатора представлена на рис. 3.1.

Рис. 3.1. Экранная форма работы синтаксического анализатора

По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.

Экранная форма при обнаружении синтаксической ошибки представлена на рис. 3.2.

Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки

Заключение

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

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

Перечень литературы

1. Гордеев А.В. Молчанов Л.Ю. Системное программное обеспечение. – СПб.: Питер, 2005. – 734с.: ил.

2. Кампапиец Р. II. Манькоп Е. В., Филатов Н. Е. Системное программирование. Базы построения трансляторов: Учебное пособие для высших и средних учебных заведений. – СПб.: КОРОНА Принт, 2004. – 256с.: ил.

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

]]>

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

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

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

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

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

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

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

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

1. Организация таблицы идентификаторов

1.1. Исходные данные

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

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

1.2. Назначение таблицы идентификаторов

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

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

1.3.
метод бинарного дерева

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

Рис. 1.1. Схема алгоритма добавления идентификатора

Схема алгоритма поиска идентификатора приведена на рис. 1.2.

Рис. 1.2. Схема алгоритма поиска идентификатора

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

1.4. метод
цепочек

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

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

Схема алгоритма добавления идентификатора представлена на рис. 1.3.

Рис. 1.3. Схема алгоритма добавления идентификатора

Схема алгоритма поиска идентификатора представлена на рис. 1.4.

Рис. 1.4. Схема алгоритма поиска идентификатора

Достоинства данного метода:

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

— каждому идентификатору соответствует строго одна ячейка в таблице идентификаторов.

Недостатком метода является организация работы с динамическими массивами.

1.5. Результаты сравнения методов

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

На рис. 1.5 представлена экранная форма организации таблицы идентификаторов методом цепочек и методом бинарного дерева.

Рис. 1.5. Экранная форма организации таблицы идентификаторов

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

При добавлении нового идентификатора возможны два случая:

— добавляемого идентификатора в таблице идентификаторов еще нет, добавление происходит успешно, указывается выполненное число сравнений по каждому методу;

— добавляемый идентификатор в таблице идентификаторов уже существует, в поле ошибок выводится соответствующее сообщение, указывается выполненное число сравнений для обнаружения повтора идентификатора по каждому методу.

Экранная форма добавления нового идентификатора представлена на рис. 1.6.

Рис. 1.6. Экранная форма добавления нового идентификатора

Экранная форма добавления существующего идентификатора представлена на рис. 1.7.

Рис. 1.7. Экранная форма добавления существующего идентификатора

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

При поиске идентификатора также возможны два случая:

— искомый идентификатор в таблице идентификаторов существует, поиск происходит успешно, указывается положение идентификатора в таблице идентификаторов и выполненное число сравнений для обнаружения идентификатора по каждому методу;

— искомый идентификатор в таблице идентификаторов не существует, выводится сообщение о неуспешном поиске и указывается выполненное число сравнений для обнаружения отсутствия идентификатора в таблице идентификаторов по каждому методу.

Экранная форма поиска существующего идентификатора представлена на рис. 1.8.

Рис. 1.8. Экранная форма поиска существующего идентификатора

Экранная форма поиска несуществующего идентификатора представлена на рис. 1.9.

Рис. 1.9. Экранная форма поиска несуществующего идентификатора

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

2. Проектирование лексического анализатора

2.1. Исходные данные

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

Лексемами данного языка являются:

— ключевыеслова (
,
.,
,
,
,
,
,
,
);

— скобки ( «(», «)» );

— оператор присваивания ( := );

— операторы сравнения ( >, <, = );

— разделитель ( ; );

— арифметические операции ( +, –, ++);

— шестнадцатеричные константы (тип данных
);

— идентификаторы;

— логические операции (

Кроме перечисленных лексем распознаватель должен определять и исключать из входного текста комментарии (неограниченной длины). Комментарии заключаются в фигурные скобки со звездочкой {*…*}.

2.2. Принцип работы лексического анализатора

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

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

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

язык описания констант и идентификаторов в большинстве случаев является регулярным, то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы (КА).

Любой КА может быть задан с помощью пяти параметров:

(
,
,δ,
0
,
), (2.1)

где:

конечное множество состояний автомата;

конечное множество допустимых входных символов (алфавит автомата);

δ – функция переходов, отображающая декартовое произведение множеств
´
во множество подмножеств
:
(
);

0

– начальное состояние автомата;

– непустое множество конечных состояний автомата.

Работа автомата выполняется по тактам. На каждом очередном такте
автомат, находясь в некотором состоянии qi

Î
, считывает очередной символ
Î
из входной цепочки символов и изменяет свое состояние на
i

+1
=d(qi

,
), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт
+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед первым тактом автомат находится в начальном состоянии
0
.

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

в qi

+1
по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из
i

в
i

+1
.

2.3. Схема распознавателя

Распознавателем лексем входного языка является конечный детерминированный автомат без внешней памяти (приложение Б).

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

В графе также используются следующие обозначения:

— ┴ – пробел, табуляция, перевод строки, +, –, =, <, >, (, ), ;, :, {

— ┴
– перевод строки

—
0 – любой символ

—
1 – любой символ, кроме символа *

—
2 – любой символ, кроме символа }

—
3 – любой символ, кроме символа ┴

—
4 – любой символ, кроме символа

—
5 – любой символ, кроме символов 0..9,
..

—
6 – любой символ, кроме символа =

—
7 – любой символ, кроме символа +

—
8 – символы
..
,
,
..
,
..
,
..
,
,
,
..
, _

—
9 –символы
..
,
..
,
..
, _

—
10 – любой символ, кроме символов
..
,
..
, _

—
11 – символы
..
,
..
,
..
, _

—
12 – символы
..
,
..
,
..
, _

—
13 – символы
..
,
..
,
..
, _

—
14 – символы
..
,
..
, _

—
15 – символы
..
,
..
,
..
, _

—
16 – символы
..
,
..
,
..
, _

—
17 – символы
..
,
..
,
..
, _

—
18 –символы
..
,
..
,
..
, _

—
19 – символы
..
,
..
,
..
, _

—
20 – символы
..
,
..
,
..
, _

—
21 – символы
..
,
..
,
..
, _

—
22 – символы
..
,
..
,
,
..
, _

—
23 – символы
..
,
..
,
..
, _

—
24 – любой символ, кроме символов
..
,
..
, _, ┴

—
25 – символы
..
, 0..9

—
26 – любой символ, кроме символов
..
,
..
, _, ┴, ‘.’

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

G ( {0..9,
..
,
..
, +, – , <, >, =, (, ), ;, :, {, }, *, ‘.’}, {
,
,
1,
2,
3,
4,
5,
1,
2,
3,
4,
5,
1,
2,
3,
4,
1,
2,
1,
2,
3,
4,
,
1,
2,
3,
1,
2,
3,
1,
2,
1,
2,
1,
2,
3,
4,
2,
3,
4},
,
)

1 ®

2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3

5 ®
4
1 ®

2 ®
1
3 ®
2

4 ®
3
5 ®
4

1 ®
2 ®
1

3 ®
2
4 ®
3

1 ®
2 ®
1

3 ®
2
4 ®
3 e

2 ®
1
3 ®
2

4 ®
3 .
1 ®

2 ®
1
3 ®
2

1 ®
2 ®
1

1 ® 0
2 ®
1
25

3 ®
2
25
4 ®
3
25

5 ®
4
25
6 ®
5

1 ® :
2 ®
1 =

® ;
® –

® +
®
+

® (
® )

® =
® <

® >

1 ® {

2 ®
1 * |
2 x1

3 ®
2 *

4 ®
3 }

®
8|
1
9|
2
11|
3
12|
4
16|
5
14|

14|
1
13|
2
12|
3
15|
4
9|
1
17|
5
14|
1
22|
1
13|
2
9|
3
16|
4
14|
2
14|
1
18|
2
19|
3
11|
4
14|
1
18|
2
14|
1
19|
2
14|
2
20|
3
14|
1
16|
2
21|
3
14|
2
21|
3
14|
4
3|
2
23|
3
9|
1
19|
4
14|

®
1
10|
2
10|
3
10|
4
24|
5
10|
1
10|
1
10|
2
10|
3
10|
4
10|
5
24|
2
24|
1
10|
2
0|
3
10|
4
24|
2
24|

24|
1
10|
2
10|
3
10|
4
24|
1
10|
1
10|
2
24|
1
10|
1
10|
2
10|
3
24|
1
10|
2
10|
3
24|
2
10|
3
26|
4
3|
3|
2
10|
3
10|
4
24|
1
5|

3|
2
5|
3
5|
4
5|
5
4|
6
3|
1
6|
2
3|

3|
1
1|
2 ┴
|
3
2|
4
3

®
5 ┴|
5 ┴|
2 ┴|
4 ┴|
2 ┴|
┴|
4 ┴|
2 ┴|
3 ┴|
3┴|
3 ┴|
4 ┴|
4 ┴|
6 ┴|
2 ┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
┴|
2 ┴

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

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

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

Программа выполняет лексический анализ входного текста в соответствие с заданной грамматикой. Результатом выполнения лексического анализа является таблица лексем с указанием их типов, а также таблица идентификаторов, сформированная методом цепочек. В таблице лексем имеется поле «Адрес», в котором указывается ссылка на место расположения идентификатора в таблице идентификаторов.

Экранная форма работы лексического анализатора представлена на рис.2.1.

Рис. 2.1. Экранная форма работы лексического анализатора

Лексическая ошибка возникает при обнаружении незакрытого комментария, неверного символа в лексеме или если лексема незавершенна (не обнаружен признак окончания лексемы).

Экранная форма при обнаружении лексической ошибки представлена на рис. 2.2.

Рис. 2.2. Экранная форма при обнаружении лексической ошибки

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

3. Проектирование синтаксического анализатора
3.1. Исходные данные

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

Исходная КС-грамматика имеет вид:

({
,
.
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
,
,
,
,
,
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→

→
<
>
=
(
)
(
)

→
–

→(
)

3.2. Построение синтаксического анализатора

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

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

(
,
,

δ,
0
,
0
,
), (3.1)

где:
– множество состояний автомата;

– алфавит входных символов автомата;

– специальный конечный алфавит магазинных символов автомата;

δ – функция переходов автомата;

множество конечных состояний;

начальное состояние автомата;

начальный символ магазина (стека).

Конфигурация МП-автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положение указателя в цепочке) и содержимым стека.

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

Для построения распознавателя для языка, заданного КС-грамматикой, воспользуемся алгоритмом «сдвиг-свертка»:

— если на верхушке стека МП-автомата находится цепочка символов g, то ее можно заменить на нетерминальный символ
при условии, что в грамматике языка существует правило вида
→ g, не сдвигая при этом считывающую головку автомата («свертка»);

— если считывающая головка автомата обозревает некоторый символ входной цепочки α, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо («сдвиг»).

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

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

На основе множества правил грамматики
определим множества крайних левых и крайних правых символов
(
),
(
) относительно всех нетерминальных символов грамматики (табл. 3.1).

Таблица 3.1.

Множества крайних левых и крайних правых нетерминальных

символов
(
),
(
) относительно всех нетерминальных символов грамматики

Символ (
)
Шаг 1
Шаг 2

(
)

(,
,

),
,

(,
,

),
,

,
, (,
,

, ),
,

, (,

, )

, (,
,
,

,
, ),
,

,
,
,
, (,
,
,

,
,
, ),
,

,
,
,
,
, (,
,
,

,
,
,
, ),
,

,
,
,

,
,
, ++

,
,
,

,
,
, ),
,
,
, ++

, ;

,
,
,
,
, a

,
,
,),
,
,
, ++, ;

На основе множества правил грамматики
и полученных множеств крайних левых и крайних правых символов
(
),
(
) построим множества крайних левых и крайних правых терминальных символов
t

(
),
t

(
) относительно всех нетерминальных символов грамматики (табл. 3.2).

Таблица 3.2.

Множества крайних левых и крайних правых

терминальных символов
t

(
),
t

(
)

Символ (
)
Шаг 1
Шаг 2

t

(
)

(,
,

),
,

(,
,

),
,

-, +
-, +
(,
,
, -, +
),
,
, -, +

<, >, =, (,

<, >, =, )
(,
,
, -, +, <, >, =,

),
,
, -, +, <, >, =

(,
,
, -, +, <, >, =,
,

),
,
, -, +, <, >, =,

(,
,
, -, +, <, >, =,
,
,

),
,
, -, +, <, >, =,
,

,
,
,

,
,
,
, :=, ++

,
,
,

),
,
, -, +,
,
,
,
, :=, ++

;
;

,
,
,
, ;
),
,
, -, +,
,
,
,
, :=, ++, ;

На основе полученных множеств и правил грамматики
построим матрицу операторного предшествования (приложение В).

Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому исходную КС-грамматику преобразуем так, чтобы в ней осталось как можно меньше нетерминальных символов (в данном случае два), то есть преобразуем ее в остовную грамматику:

({
,
.,
,
,
,
,
,
,
,
,
,
, =, <, >, (, ), -, +, ++,
,
, ;, :=}, {
,
},
,
)

→
.

→
|
;
|
;

→
(
)
|
|
|
(
)
|
:=
|
++

→
|

→
<
|
>
|
=
| (
) |
(
)

→
–
|
+
|

→ (
) |
|

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

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

Экранная форма работы синтаксического анализатора представлена на рис. 3.1.

Рис. 3.1. Экранная форма работы синтаксического анализатора

По последовательности сработавших правил «свертки» строится цепочка вывода и дерево вывода.

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

Экранная форма при обнаружении синтаксической ошибки представлена на рис. 3.2.

Рис. 3.2. Экранная форма при обнаружении синтаксической ошибки

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

Заключение

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

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

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

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

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

Отдельные фазы компиляции, разработанные в данной курсовой работе, дают http://wpgrabbestrefedu.loc/2019/02/14/utchebnaya-rabota-referat-yazki-programmirovaniya-ponyatie-i-vid/

1. Оглавление

СОДЕРЖАНИЕ. 1

2.Введение. 2

3.Что такое язык программирования. 3

4.Этапы решения задачки на ЭВМ .5

5.Для что необходимы языки программирования. 7

6.Какие есть языки программирования. 9

1.1. Фортран. 9

1.2. Алгол. 10

1.3. Кобол. 11

1.4. Лисп. 12

1.5. Бейсик. 14

1.6. Форт. 15

1.7. Паскаль. 16

1.8. Ада. 17

1.9. Си. 19

1.10Пролог. 20

1.11Java. 22

1.12Object Pascal23

1.13Система зрительного объектно-ориентированного проектирования Delphi.25

7.Перечень литературы:36

1. Введение

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

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

2. Что такое язык программирования

Язык программирования
— формальная знаковая система, созданная для описания алгоритмов в форме, которая комфортна для исполнителя (к примеру, компа). язык программирования описывает набор лексических, синтаксических и семантических правил, применяемых при составлении компьютерной программки. Он дозволяет программеру буквально найти то, на какие действия будет реагировать комп, как будут храниться и передаваться данные, также какие конкретно деяния следует делать над этими при разных обстоятельствах.

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

Создатели языков по-разному толкуют понятие
. Посреди общиx мест, признаваемых большинством разрабов, находятся последующие:

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

·
язык программирования различается от естественных языков тем, что предназначен для передачи установок и данных от человека компу, в то время как естественные языки употребляются только для общения людей меж собой. В принципе, можно обобщить определение «языков программирования» — это метод передачи установок, приказов, чёткого управления к действию; тогда как людские языки служат также для обмена информацией.

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

3.
Этапы решения задачки на ЭВМ .

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

Этот шаг заключается в содержательной (физической) постановке задачки и определении конечных решений.

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

Так как ЭВМ может делать только простые операции, она «не соображает» постановки задачки, даже в математической формулировке. Для ее решения должен быть найден численный способ, позволяющий свести задачку к некому вычислительному методу. В любом определенном случае нужно избрать подходящее решение из уже разработанных обычных.

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

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

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

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

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

4.
Для что необходимы языки программирования

процесс работы компа заключается в выполнении программки, другими словами набора полностью определённых установок во полностью определённом порядке. Машинный вид команды, состоящий из нулей и единиц, показывает, какое конкретно действие должен выполнить центральный микропроцессор. Означает, чтоб задать компу последовательность действий, которые он должен выполнить, необходимо задать последовательность двоичных кодов соответственных установок. Программки в машинных кодах состоят из тыщи установок. Писать такие программки – занятие сложное и мучительное. Программер должен держать в голове комбинацию нулей и единиц двоичного кода каждой программки, также двоичные коды адресов данных, применяемых при её выполнении. Еще проще написать программку на каком-нибудь языке, наиболее близком к естественному людскому языку, а работу по переводу данной программки в машинные коды поручить компу. Так появились языки, предназначенные специально для написания программ, — языки программирования.

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

Всё огромное количество языков программирования можно поделить на две группы: языки низкого уровня
и языки высочайшего уровня.

К языкам низкого уровня относятся языки ассемблера (от англ. toassemble – собирать, компоновать). В языке ассемблера употребляются символьные обозначения установок, которые просто понятны и стремительно запоминаются. Заместо последовательности двоичных кодов установок записываются их символьные обозначения, а заместо двоичных адресов данных, применяемых при выполнении команды, — символьные имена этих данных, избранные программером. время от времени язык ассемблера именуют мнемокодом либо автокодом.

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

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

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

5.
Какие есть языки программирования

1.1 Фортран

Языки программирования стали появляться уже с середины 50-х годов. Одним из первых языков такового типа стал язык Фортран (англ. FORTRAN от FORmulaTRANslator – переводчик формул), разработанный в 1957 году. Фортран применяется для описания метода решения научно-технических задач при помощи ЦВМ. Так же, как и 1-ые вычислительные машинки, этот язык предназначался, в главном, для проведения естественно-научных и математических расчётов. В улучшенном виде этот язык сохранился до нашего времени. Посреди современных языков высочайшего уровня он является одним из более применяемых при проведении научных исследовательских работ. Более всераспространены варианты Фортран-II, Фортран-IV, EASICFortran и их обобщения.

1.2
Алгол

Опосля Фортрана в 1958-1960 годах возник язык Алгол (Алгол-58, Алгол-60) (англ. ALGOL от ALGOrithmicLanguage – алгоритмический язык). Алгол был усовершенствован в 1964-1968 годах – Алгол-68. Алгол был разработан комитетом, в который входили европейские и южноамериканские учёные. Он относится к языкам высочайшего уровня (high-level language) и дозволяет просто переводить алгебраические формулы в программные команды. Алгол был популярен в Европе, в том числе СССР

Обычно под понятием Алгол предполагается язык
, в то время как
рассматривается как самостоятельный язык. Даже когда язык Алгол практически не стал употребляться для программирования, он ещё оставался официальным языком для публикации алгоритмов.

1.3 Кобол

В 1959 – 1960 годах был разработан язык Кобол (англ. COBOL от COmmom Business Oriented Language – общий язык, направленный на бизнес). Это язык программирования третьего поколения, предназначенный, сначала, для разработки бизнес приложений. Также Кобол предназначался для решения экономических задач, обработки данных для банков, страховых компаний и остальных учреждений подобного рода. Разрабом первого одного эталона Кобола являлась Грейс Хоппер (

Кобол обычно критикуется за многословность и громоздкость, так как одной из целей создателей языка было очень приблизить конструкции к британскому языку. (До сего времени Кобол считается языком программирования, на котором было написано больше всего строк кода). В то же время, Кобол имел красивые для собственного времени средства для работы со структурами данных и файлами, что обеспечило ему долгую жизнь в бизнес приложениях, по последней мере, в США .

Неважно какая программка на Лиспе состоит из последовательности
(форм). Итог работы программки состоит в вычислении этих выражений. Все выражения записываются в виде
— одной из главных структур Лиспа, потому они могут просто быть сделаны средством самого языка. Это дозволяет создавать программки, изменяющие остальные программки либо макросы, дозволяющие значительно расширить способности языка.

Главный смысл Лисп-программы «жизнь» в символьном пространстве: перемещение, творчество, мозга , знак, метафора сигнала: «Как происходит био анализ сигналов мозгом

1.5
Бейсик

Посреди 60-х годов (1963 г.) в Дартмутском институте (США

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

1.6
Форт

В конце 60-х – начале 70-х годов возник язык Форт (англ. FOURTH – четвёртый). Этот язык стал применяться в задачках управления разными системами опосля того, как его создатель Чарльз Мур написал на нём программку, созданную для управления радиотелескопом Аризонской обсерватории.

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

1.7
Паскаль

Показавшийся в 1972 году язык Паскаль был назван так в честь величавого французского математика XVII века, изобретателя первой в мире арифметической машинки Блеза Паскаля. Этот язык был сотворен швейцарским учёным, спецом в области информатики Никлаусом Виртом как язык для обучения способам программирования. Паскаль – это язык программирования общего предназначения.

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

язык Паскаль учит не только лишь тому, как верно написать программку, да и тому, как верно создать способ решения задачки, подобрать методы представления и организации данных, применяемых в задачке. С 1983 года язык Паскаль введён в учебные курсы информатики средних школ США

Конкретными предшественниками Ada являются Pascal и его производные, включая Euclid, Lis, Mesa, Modula и Sue. Были применены некие концепции ALGOL-68, Simula, CLU и Alphard.

Создатели Ada до этого всего волновались о:

· надежности и эксплуатационных качествах программ;

· программировании как разновидности людской деятель;

· эффективности.

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

Переменные экземпляра
способы экземпляра
Переменные класса
Способы класса
Да
Да
Нет
Нет

Переменных
Способов
Открытые, закрытые
Открытые, закрытые

Разновидности модулей
Пакет

Наследование
Шаблоны
Метаклассы
Нет (заходит в Ada9x)
Да
Нет

Мощная типизация
Полиморфизм
Да
Нет (заходит в Ada9x)

Многозадачность
Да

Долгоживущие объекты
Нет

Таблица 1. Ada.

1.9
Си

В истинное время пользующимся популярностью посреди программистов является язык Си (С – буковка британского алфавита). язык Си берёт своё начало от 2-ух языков — BCPL и B. В 1967 году Мартин Ричардс разработал BCPL как язык для написания системного программного обеспечения и компиляторов. В 1970 году Кен Томпсон употреблял В для сотворения ранешних версий операционной системы UNIX на компе DEC PDP-7. Как в BCPL, так и в В переменные не делились на типы — каждое к примеру, целых и реальных чисел полностью ложилась на плечи программера.язык Си был разработан (на базе В) Деннисом Ритчи из Bell Laboratories и в первый раз был реализован в 1972 году на компе DEC PDP-11. Известность Си получил в качестве языка ОС unix. Сейчас фактически все главные операционные системы были написаны на Си либо С++. По прошествии 2-ух десятилетий Си имеется в наличии на большинстве компов. Он не зависит от аппаратной части.В конце 70-х годов Си перевоплотился в то, что мы называем «обычный Си». В 1983 году Южноамериканским комитетом государственных эталонов в области компов и обработкиинформации был учрежден единый эталон этого языка. Этот язык имеет богатые средства, дозволяет писать гибкие программки, использующие все способности современных индивидуальных компов.
1.10 Пролог

Ещё один язык, который считается языком грядущего, был сотворен сначала 70-х годов группой профессионалов Марсельского института. Это язык Пролог. Своё заглавие он получил от слов «ПРОграммирование на языке ЛОГики». В базе этого языка лежат законы математической логики. Как и язык Лисп, Пролог применяется, в главном, при проведении исследовательских работ в области программной имитации деятельности мозга человека. В отличие от обрисованных выше языков, этот язык не является алгоритмическим. Он относится к так именуемым дескриптивным
(от англ. descriptive – описательный) – описательным языкам. Дескриптивный язык не просит от программера разработки всех шагов выполнения задачки. Заместо этого, в согласовании с правилами такового языка, программер должен обрисовать базу данных, подобающую решаемой задачке, и набор вопросцев, на которые необходимо получить ответы, используя данные из данной базы.

В крайние десятилетия в программировании появился и получил существенное развитие объектно-ориентированный
подход. Это способ программирования, имитирующий настоящую картину мира: информация, применяемая для решения задачки, представляется в виде огромного количества взаимодействующих объектов. Любой из объектов имеет свои характеристики и методы поведения. Взаимодействие объектов осуществляется с помощью передачи сообщений: любой объект может получать сообщения от остальных объектов, запоминать информацию и обрабатывать её определённым методом и, в свою очередь, посылать сообщения. Так же, как и в настоящем мире, объекты хранят свои характеристики и Идеология употребляется во всех современных программных продуктах, включая операционные системы.

1-ый объектно-ориентированный язык

был сотворен как средство моделирования работы разных устройств и устройств. Большая часть современных языков программирования – объектно-ориентированные. Посреди их крайние версии языка

и остальные.

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

и остальные. Они разрешают создавать сложные прикладные пакеты, владеющие обычным и комфортным пользовательским интерфейсом.

1.11 Java

С 1995 года стал обширно распространяться новейший объектно-ориентированный язык программирования Java, направленный на сети компов и, до этого всего, на Internet. Синтаксис этого языка припоминает синтаксис языка C++, но эти языки имеют не много общего. Java интерпретируемый язык: для него определены внутреннее на данный момент реализованы на большинстве платформ. Интерпретатор упрощает отладку программ, написанных на языке Java, обеспечивает их переносимость на новейшие платформы и адаптируемость к новеньким окружениям. Он дозволяет исключить воздействие программ, написанных на языке Java, на остальные программки и файлы, имеющиеся на новейшей платформе, и тем обеспечить сохранность при выполнении этих программ. Эти характеристики языка Java разрешают употреблять его как главный язык программирования для программ, распространяемых по сетям (а именно, по сети Internet).

1.12 Object Pascal

Object Pascal создавался сотрудниками компании Apple Computer (некие из которых были участниками проекта Smalltalk) вместе с Никлаусом Виртом (Niklaus Wirth), создателем языка Pascal. Object Pascal известен с 1986 года и является первым объектно-ориентированным языком программирования, который был включен в Macintosh Programmer’s Workshop (MPW), среду разработки для компов Macintosh конторы Apple.

В этом языке нет способов класса, переменных класса, множественного наследования и метаклассов. Эти механизмы исключены специально, чтоб создать язык обычным для исследования начинающими «объектными» программерами.

В табл. 2 приведены общие свойства Object Pascal.

Переменные экземпляра
способы экземпляра
Переменные класса
Способы класса
Да
Да
Нет
Нет

Переменных
Способов
Открытые
Открытые

Разновидности модулей
Модуль (unit)

Наследование
Шаблоны
Метаклассы
Одиночное
Нет
Нет

Мощная типизация
Полиморфизм
Да
Да (одиночный)

Многозадачность
Нет

Долгоживущие объекты
Нет

Таблица 2. Object Pascal.

В крайние годы этот язык стал весьма популярен благодаря системе Delphi конторы Borland.

1.13 Система зрительного объектно-ориентированного проектирования Delphi.

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

Система Delphi дозволяет решать огромное количество задач, а именно:

· Создавать законченные приложения для Windows самой различной направленности: от чисто вычислительных и логических, до графических и мультимедиа.

· стремительно создавать (даже начинающим программерам) мастерски выглядящий оконный интерфейс для всех приложений.

· Создавать массивные системы работы с локальными и удаленными базами данных

· Создавать справочные системы (файлы .hlp) для собственных приложений и мн. др.

Delphi – очень стремительно развивающаяся система. 1-ая версия – Delphi 1.0 была выпущена в феврале 1995 г. А потом новейшие версии выпускались раз в год.

Любая следующая версия Delphi дополняла предшествующую.Большая часть версий Delphi выпускается в нескольких вариантах: Standart – обычном, Professional – проф, Client/Server – клиент/сервер, Enterprise – разработка баз данных предметных областей. Различаются варианты в главном различным уровнем доступа к системам управления базами данных. Крайние варианты — Client/Server и Enterprise, тут более массивные.

Delphi — это композиция нескольких важных технологий:

· Высокопроизводительный компилятор в машинный код

· Объектно-ориентированная модель компонент

· Зрительное (а, как следует, и высокоскоростное) построение приложений из программных прототипов

· Масштабируемые средства для построения баз данных

Структура экрана в среде Delphi.

Опосля вызова Delphi в Windows возникают несколько окон (рис 1.):

-главное окно,

-окно формы,

-окно инспектора объектов,

-окно дерева объектов,

-окно кода программки.

Рис1. структура экрана в среде Delphi.

Разглядим расположенное в верхней части экрана графическое меню системы Delphi, составленное из пиктограмм.В левой части графического меню находится панель инструментов. Инструменты делают некие команды головного меню — такое дублирование нередко практикуется в инструментальных средах.На данной панели есть, а именно, клавиша сохранения проекта на диске, клавиша открытия проекта, клавиша пуска программки на выполнение.

Последующая часть графического меню — гамма компонент, устроенная в виде наборов пиктограмм. совокупа наборов составляет библиотеку зрительных компонент (VCL). Имеется несколько категорий компонент, любая из которых связана со собственной закладкой. При помощи палитры компонент мы будем создавать экземпляры компонент (либо объекты) в форме.

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

Окно Object Inspector — это окно, отображающее характеристики или формы, или расположенного на форме объекта. В нашем случае текущим компонентом является форма, потому на рисунке окно параметров указывает характеристики формы.

Окно параметров имеет две закладки — Properties и Еvents, при помощи которых можно получить в окне строчки (поля) для задания, соответственно, параметров компонента (т. е. объекта либо формы) и его реакции на разные действия. Свойство описывает атрибут компонента, к примеру, размер клавиши либо шрифт метки. Событие значит, к примеру, такие деяния, как щелчок мыши на кнопочке либо закрытие окна.

Окно дерева объектов возникло в версии 6 и создано для приятного отображения связей меж отдельными объектами, размещенными на активной форме либо в активном модуле данных.

Окно кода программки создано для сотворения и редактирования текста программки. Сначало оно содержит малый начальный текст.

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

Создающиеся в процессе проектирования файлы показаны в табл. 3.

Главной частью приложения является файл проекта (.dpr), содержащий код на языке Object Pascal, с которого начинается выполнение программки и который обеспечивает инициализацию остальных модулей. Он создается и модифицируется Delphi автоматом в процессе разработки приложения. имя, которое дается файлу проекта в процессе сохранения, становится именованием исполняемого файла.

файл проекта (.dpr)
Этот текстовый файл употребляется для хранения инфы о формах и модулях. В нем содержатся операторы инициализации и пуска программ на выполнение

файл модуля (.pas)
Каждой создаваемой вами форме соответствует текстовый файл модуля, применяемый для хранения кода. Можно создавать модули, не связанные с формами. Почти все из функций и процедур Delphi хранятся в модулях.

файл формы (.dfm)
Это двоичный либо текстовый файл, который создается Delphi для хранения инфы о формах. Любому файлу формы соответствует файл модуля (.pas)

Файл характеристик проекта(.dfo)
В этом файле хранятся установки характеристик проекта

файл ресурсов(.res)
Этот бинарный файл содержит применяемую проектом пиктограмму и остальные ресурсы

Файлы запасных копий (.~dpr, .~dfm, .~pas)
Это соответственно файлы запасных копий для файлов проекта, формы и модуля. Если что-то безвыходно испорчено в проекте, можно соответственно поменять расширения этих файлов и таковым образом возвратиться к предшествующему не испорченному варианту

Файлконфигурации окон (.dsk)
файл хранит конфигурацию всех окон среды разработки

Исполняемыйфайл (.exe)
Это исполняемый файл приложения. Он является автономным исполняемым файлом, для которого больше ничего не требуется, если лишь не употребляются библиотеки, находящиеся в DLL, OCX и т.д.

Объектный файлмодуля (.dcu)
Это откомпилированный файл модуля (.pas), который компонуется в окончательный исполняемый файл.

Таблица 3. Файлы, создающиеся в процессе проектирования.

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

Дерево эволюции программирования

Набросок 1Дерево эволюции программирования

6.
Перечень литературы:

1. И.Т. Зарецкая, Б.Г. Колодяжный, А.Н. Гуржий, А.Ю. Соколов. Информатика 10-11 класс. — К.: «Форум», 2001 г.

1.
структура экрана в среде Delphi (http://textbook.keldysh.ru/distant/delphi/del_2.htm)

2.
Патрикеев Ю. Н. «Объектно-ориентированное проектирование» (HTTP://www.object.newmail.ru/oop1.html)

3.
С. Немнюгин, Л. Перколаб «Изучаем TurboPascal» — СПб.: Питер, 2002.

2. Х.М. Дейтел. Как программировать на С. – М.: «Двучлен», 2000 г.

3. веб-страница: http://ru.wikipedia.org/wiki/LISP

]]>

Перейти и растаять в своей любимой социалке

Учебная работа. Реферат: Построение отдельных фаз компиляции

Учебная работа. Реферат: Построение отдельных фаз компиляции

Как? Вы еще не читали? Ну это зря...