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

Программа, которая написана на машинном языке какой-либо конкретно взятой ЭВМ, должным образом может быть выполнена на ней непосредственно.
Однако в наше время программирование на машинном языке является очень трудоемким, и поэтому программы пишутся на языках, имеющих более нужную символическую и стилизованную форму, которая легче для человеческого понимания. Отсюда у нас возникает потребность в переводе текста программы из одной формы представленная в другую. Эту функцию теперь выполняет транслятор – программа, которая переводит входную программу в некотором смысле на исходном языке в эквивалентную ей выходную программу на результирующем языке.
Чтобы нам создать транслятор, нам теперь необходимо выбрать входной и выходной языки. Одной из видов транслятора является компилятор – программа, которая осуществляет перевод, который в исходной программы, в эквивалентную объектную программу на языке машинных команд или языке ассемблера.
Компиляторы на сегодняшний день являются самым распространенным видом трансляторов
. Они имеют самое широкое практическое применение благодаря широкому распространению всевозможных языков программирования.
Целью курсовой работы является изучение составных частей, основных принципов построения и функционирования компиляторов, практическое освоение методов построения простейших компиляторов для заданного входного языка.
Для выполнения курсовой работы использована среда разработки Delphi 7.

1. Организация таблицы идентификаторов
1.1 Исходные данные
Нам требуется написать программу, которая чтобы сравнить два способа организации таблицы идентификаторов. Идентификаторы который нам нужен должным образом считываться из файла и размещаться в таблицах с помощью заданных методов. Программа должна выполнять многократный поиск указанных идентификаторов по требованию пользователя. В процессе поиска идентификатора в таблицах должно подсчитываться количество сравнений и среднее число сравнений для сопоставления эффективности используемых методов.
В курсовом проекте используется сопоставление двух методов: хеш-адресация (метод разрешения коллизий: рехешированием с помощью произведения) и упорядоченный список.
1.2 Назначение таблиц идентификаторов
При выполнении семантического анализа, генерации кода и оптимизации результирующей программы компилятор должен оперировать характеристиками основных элементов исходной программы - переменных, констант, функций и других лексических единиц входного языка. Эти характеристики могут быть получены компилятором на этапе синтаксического анализа входной программы (чаще всего при анализе структуры блоков описаний переменных и констант), а также дополнены на этапе подготовки к генерации кода (например при распределении памяти).
Набор характеристик который соответствующий, каждому элементу исходной программы, должен зависит от типа этого элемента от его смысла (семантики) и, соответственно, от той роли, которую он исполняет в исходной и результирующей программах.
В каждом конкретном случае этот набор характеристик может быть свой в зависимости от синтаксиса и семантики входного языка, от архитектуры целевой вычислительной системы и от структуры компилятора. Но есть типовые характеристики, которые чаще всего присущи тем или иным элементам исходной программы.
Например для переменной - это ее тип и адрес ячейки памяти, для константы - ее значение, для функции - количество и типы формальных аргументов, тип возвращаемого результата, адрес вызова кода функции.
Главной характеристикой любого элемента исходной программы является его имя.
Именно с именами переменных, констант, функций и других элементов входного языка оперирует разработчик программы - поэтому и компилятор должен уметь анализировать эти элементы по их именам.
Имя каждого элемента должно быть уникальным. Многие современные языки программирования допускают совпадения (неуникальность) имен переменных, и функций в зависимости от их области видимости и других условий исходной программы.
Таким образом, задача компилятора заключается в том, чтобы хранить некоторую информацию, связанную с каждым элементом исходной программы, и иметь доступ к этой информации по имени элемента.
Для решения этой задачи компилятор организует специальные хранилища данных, называемые таблицами идентификаторов, или таблицами символов. Таблица идентификаторов состоит из набора полей данных (записей), каждое из которых может соответствовать одному элементу исходной программы. Запись содержит всю необходимую компилятору информацию о данном элементе и может пополняться по мере работы компилятора. Количество записей зависит от способа организации таблицы идентификаторов, но в любом случае их не может быть меньше, чем элементов в исходной программе. В принципе, компилятор может работать не с одной, а с несколькими таблицами идентификаторов - их количество и структура зависят от реализации компилятора.
1.3 Принципы организации таблиц идентификаторов

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

1.4 Простейшие методы построения таблиц идентификаторов

В ㅤ простейшем ㅤ случае ㅤ таблица ㅤ идентификаторов ㅤ представляет ㅤ собой ㅤ линейный ㅤ неупорядоченный ㅤ список, ㅤ или ㅤ массив, ㅤ каждая ㅤ ячейка ㅤ которого ㅤ содержит ㅤ данные ㅤ о ㅤ соответствующем ㅤ элементе ㅤ таблицы. ㅤ Размещение ㅤ новых ㅤ элементов ㅤ в ㅤ такой ㅤ таблице ㅤ выполняется ㅤ путем ㅤ записи ㅤ информации ㅤ в ㅤ очередную ㅤ ячейку ㅤ массива ㅤ или ㅤ списка ㅤ по ㅤ мере ㅤ обнаружения ㅤ новых ㅤ элементов ㅤ в ㅤ исходной ㅤ программе.
Поиск ㅤ нужного ㅤ элемента ㅤ в ㅤ таблице ㅤ будет ㅤ в ㅤ этом ㅤ случае ㅤ выполняться ㅤ путём ㅤ последовательного ㅤ перебора ㅤ всех ㅤ элементов ㅤ и ㅤ сравнения ㅤ их ㅤ имени ㅤ с ㅤ именем ㅤ искомого ㅤ элемента, ㅤ пока ㅤ не ㅤ будет ㅤ найден ㅤ элемент ㅤ с ㅤ таким ㅤ же ㅤ именем. ㅤ Тогда ㅤ если ㅤ за ㅤ единицу ㅤ времени ㅤ принять ㅤ время, ㅤ затрачиваемое ㅤ компилятором ㅤ на ㅤ сравнение ㅤ двух ㅤ строк ㅤ (в ㅤ современных ㅤ вычислительных ㅤ системах ㅤ такое ㅤ сравнение ㅤ чаще ㅤ всего ㅤ выполняется ㅤ одной ㅤ командой), ㅤ то ㅤ для ㅤ таблицы, ㅤ содержащей ㅤ N ㅤ элементов, ㅤ в ㅤ среднем ㅤ будет ㅤ выполнено ㅤ N/2 ㅤ сравнений.
Время, ㅤ требуемое ㅤ на ㅤ добавление ㅤ нового ㅤ элемента ㅤ в ㅤ таблицу ㅤ (Тд), ㅤ не ㅤ зависит ㅤ от ㅤ числа ㅤ элементов ㅤ в ㅤ таблице ㅤ (N). ㅤ Но ㅤ если ㅤ N ㅤ велико, ㅤ то ㅤ поиск ㅤ потребует ㅤ значительных ㅤ затрат ㅤ времени. ㅤ Время ㅤ поиска ㅤ (Ти) ㅤ в ㅤ такой ㅤ таблице ㅤ можно ㅤ оценить ㅤ как ㅤ Ти ㅤ = ㅤ O(N). ㅤ Поскольку ㅤ именно ㅤ поиск ㅤ в ㅤ таблице ㅤ идентификаторов ㅤ является ㅤ наиболее ㅤ часто ㅤ выполняемой ㅤ компилятором ㅤ операцией, ㅤ такой ㅤ способ ㅤ организации ㅤ таблиц ㅤ идентификаторов ㅤ является ㅤ неэффективным. ㅤ Он ㅤ применим ㅤ только ㅤ для ㅤ самых ㅤ простых ㅤ компиляторов, ㅤ работающих ㅤ с ㅤ небольшими ㅤ программами.
Поиск ㅤ может ㅤ быть ㅤ выполнен ㅤ более ㅤ эффективно, ㅤ если ㅤ элементы ㅤ таблицы ㅤ отсортированы ㅤ (упорядочены) ㅤ естественным ㅤ образом. ㅤ Поскольку ㅤ поиск ㅤ осуществляется ㅤ по ㅤ имени, ㅤ наиболее ㅤ естественным ㅤ решением ㅤ будет ㅤ расположить ㅤ элементы ㅤ таблицы ㅤ в ㅤ прямом ㅤ или ㅤ обратном ㅤ алфавитном ㅤ порядке. ㅤ Эффективным ㅤ методом ㅤ поиска ㅤ в ㅤ упорядоченном ㅤ списке ㅤ из ㅤ N ㅤ элементов ㅤ является ㅤ бинарный, ㅤ или ㅤ логарифмический; ㅤ поиск.
Алгоритм ㅤ логарифмического ㅤ поиска ㅤ заключается ㅤ в ㅤ следующем: ㅤ искомый ㅤ символ ㅤ сравнивается ㅤ с ㅤ элементом ㅤ (N+ ㅤ 1)/2 ㅤ в ㅤ середине ㅤ таблицы; ㅤ если ㅤ этот ㅤ элемент ㅤ не ㅤ является ㅤ искомым, ㅤ то ㅤ мы ㅤ должны ㅤ просмотреть ㅤ только ㅤ блок ㅤ элементов, ㅤ пронумерованных ㅤ от ㅤ 1 ㅤ до ㅤ (N+ ㅤ 1)/2 ㅤ - ㅤ 1, ㅤ или ㅤ блок ㅤ элементов ㅤ от ㅤ (N+ ㅤ 1)/2 ㅤ + ㅤ 1 ㅤ до ㅤ N ㅤ в ㅤ зависимости ㅤ от ㅤ того, ㅤ меньше ㅤ или ㅤ больше ㅤ искомый ㅤ элемент ㅤ того, ㅤ с ㅤ которым ㅤ его ㅤ сравнили. ㅤ Затем ㅤ процесс ㅤ повторяется ㅤ над ㅤ нужным ㅤ блоком ㅤ в ㅤ два ㅤ раза ㅤ меньшего ㅤ размера. ㅤ Так ㅤ продолжается ㅤ до ㅤ тех ㅤ пор, ㅤ пока ㅤ либо ㅤ искомый ㅤ элемент ㅤ не ㅤ будет ㅤ найден, ㅤ либо ㅤ алгоритм ㅤ не ㅤ дойдет ㅤ до ㅤ очередного ㅤ блока, ㅤ содержащего ㅤ один ㅤ или ㅤ два ㅤ элемента ㅤ (с ㅤ которыми ㅤ можно ㅤ выполнить ㅤ прямое ㅤ сравнение ㅤ искомого ㅤ элемента).
Так ㅤ как ㅤ на ㅤ каждом ㅤ шаге ㅤ число ㅤ элементов, ㅤ которые ㅤ могут ㅤ содержать ㅤ искомый ㅤ элемент, ㅤ сокращается ㅤ в ㅤ два ㅤ раза, ㅤ максимальное ㅤ число ㅤ сравнений ㅤ равно ㅤ 1 ㅤ + ㅤ log2 ㅤ N. ㅤ Тогда ㅤ время ㅤ поиска ㅤ элемента ㅤ в ㅤ таблице ㅤ идентификаторов ㅤ можно ㅤ оценить ㅤ как ㅤ Тп ㅤ = ㅤ O(log2 ㅤ N). ㅤ Для ㅤ сравнения: ㅤ при ㅤ N=128 ㅤ бинарный ㅤ поиск ㅤ требует ㅤ самое ㅤ большее ㅤ 8 ㅤ сравнений, ㅤ а ㅤ поиск ㅤ в ㅤ неупорядоченной ㅤ таблице ㅤ — ㅤ в ㅤ среднем ㅤ 64 ㅤ сравнения. ㅤ Метод ㅤ называют ㅤ «бинарным ㅤ поиском», ㅤ поскольку ㅤ на ㅤ каждом ㅤ шаге ㅤ объем ㅤ рассматриваемой ㅤ информации ㅤ сокращается ㅤ в ㅤ два ㅤ раза, ㅤ а ㅤ «логарифмическим» ㅤ — ㅤ поскольку ㅤ время, ㅤ затрачиваемое ㅤ на ㅤ поиск ㅤ нужного ㅤ элемента ㅤ в ㅤ массиве, ㅤ имеет ㅤ логарифмическую ㅤ зависимость ㅤ от ㅤ общего ㅤ количества ㅤ элементов ㅤ в ㅤ нем.
Недостатком ㅤ логарифмического ㅤ поиска ㅤ является ㅤ требование ㅤ упорядочивания ㅤ таблицы ㅤ идентификаторов. ㅤ
Так ㅤ как ㅤ массив ㅤ информации, ㅤ в ㅤ котором ㅤ выполняется ㅤ поиск, ㅤ должен ㅤ быть ㅤ упорядочен, ㅤ время ㅤ его ㅤ заполнения ㅤ уже ㅤ будет ㅤ зависеть ㅤ от ㅤ числа ㅤ элементов ㅤ в ㅤ массиве. ㅤ