Лабораторная работа: Построение таблицы идентификаторов

Построение таблицы идентификаторов

Введение

программа идентификатор произвольный

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

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

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

1. Теоретические сведения.

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

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

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

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

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

· для переменных: имя переменной; тип данных переменной; область памяти, связанная с переменной;

· для констант: название константы (если оно имеется); значение константы; тип данных константы (если требуется);

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

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

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

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

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

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

Порядок выполнения работы

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

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

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

Лабораторная работа должна выполняться в следующем порядке:

1. Получить вариант задания у преподавателя.

2. Выбрать и описать хэш-функцию.

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

4. Написать и отладить программу в среде Qt-Creator.

5. Подготовить отчет, видеодемонстрациюи защитить ЛР.

Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

· Задание по лабораторной работе;

· Описание выбранной хэш-функции;

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

· Программный код остальных частей программы;

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

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

· Список литературы.

Контрольные вопросы

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

· Какая информация может храниться в таблице символов?

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

· Какими характеристиками могут обладать лексические элементы исходнойпрограммы?

· Какие характеристики лексических элементов являются обязательными?

· Какие существуют способы организации таблиц символов?

· B чем заключается алгоритм логарифмического поиска?

· Какие преимущества алгоритм логарифмического поиска дает по сравнению с простым перебором и какие он имеет недостатки?

· Древовидная организация таблиц идентификаторов. B чем еепреимущества и недостатки?

· Что такое хэш-функция и для чего она используется?

· B чем суть хэш-адресации?

· Что такое коллизия?

· Почему происходит коллизия?

· Можно ли полностыю избежатьколлизий?

· Что такое рехэширование?

· Какие методы рехэширования существуют?

· Преимущества и недостатки организации таблиц идентификаторов с помощью хэш-ацресации и рехэширования.

· B чем заключается метод цепочек?

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

· Как могут быть скомбинированы различные методы организации хэш-таблиц?

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

Варианты заданий

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

Таблица 1.1. Методы организации таблиц идентификаторов

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

Таблица 1.2. Варианты заданий

2. Пример выполнения работы

Задание для примера

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

Выбор и описание хэш-функции с рехэшированием

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

Будем считать, что прописные и строчные буквы в идентификаторе различны. В качестве кодов символов возьмем коды таблицы ASCII, которая используется в вычислительных системах на базе ОС типа Microsoft Windows, тогда, если положить, чтострока из области определения хэш-функции содержит только цифры и буквы англпйского алфавтта, то минимальным значением хэш-фупкции будет сумма трех кодов цифры «0», aмаксимальнымзначением сумма трех кодов литеры «z».

Таким образом, область значений выбранной хэш-функции в терминах языка С может бытъ описана как:

((int)'0' + (int)'0' + (int)'0'). ((int)'z' + (int)'z' + (int)'z')

Для рехэширования с помощью произведения возьмем простейший генератор последовательности псевдослучайных чисел, построенный на основе формулы F= i*Н1 mod Н» где Н1, и Н2 - простые числа, выбранные таким образом, чтобы Н1 было в диапазоне от Н2/2 до Н2. Причем, чтобы этот генератор выдавал максимально длинную последовательность во всем диапазоне от НАSН_MIN до НАSН_МАХ, Н2 должно быть максимально близко к величине НАSН_МАХ-НАSН_MIN + 1. В данном случае диапазон содержит 223 элемента, и поскольку 223 - простое число, то возьмем Н2 = 223. В качестве Н1, возьмем 127: Н1 = 127. Длина таблицы идентификаторов будет иметь значение НАSН_МАХ-НАSН_MIN + 1=223-127+1=97 значений.

Опишем соответствующие константы:

REHASH1 = 127

RЕНАSН2 = 223

Область значений выбранной хэш-функции в терминах языка C++ может быть описана как:

((int)'0' + (int)'0' + (int)'0'). ((int)'z' + (int)'z' + (int)'z')

Сама функция хэш-функция без учета рехэширования будет вычисляться следующим образом:

(int (sName[0]) + int (sName[(sName.size()) / 2]) +

+ int (sName[sName.size() - 1])

Здесь sName - входная строка.

Хэш-функция с учетом рехэширования будет иметь вид:

int VarHash (string sName, int iNum)

{

int HASH_MIN = (int)'0' + (int)'0' + (int)'0';

int HASH_MAX = (int)'z' + (int)'z' + (int)'z';

int REHASH1 = 127;

int REHASH2 = 223;

int result;

result=(int (sName[0])+int (sName[(sName.size()) / 2])

+ int (sName[sName.size() - 1]) - HASH_MIN