Построение отдельных фаз компиляции (стр. 1 из 4)

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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